SHPORA.net :: PDA | |
Main FAQ гуманитарные науки естественные науки математические науки технические науки Правило приведения ЗЛП к каноническому виду: 1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «?» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «?» - со знаком «-» (2.10) Вводим переменную . Тогда неравенство (2.10) запишется в виде: (2.11) В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений. 2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных , l - свободный индекс 3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1) 4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F1 = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F1. Таким образом, всякую задачу линейного программирования можно сформулировать в канонической форме. В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны. (2.12) Всякую задачу линейного программирования можно сформулировать в стандартной форме. Преобразование задачи на минимум в задачу на максимум, а также обеспечение не отрицательности переменных производится так же, как и раньше. Всякое равенство в системе ограничений равносильно системе взаимопротивоположных неравенств: Существует и другие способы преобразования системы равенств в систему неравенств, т.е. всякую задачу линейного программирования можно сформулировать в стандартной форме. |