Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Как видно из таблицы, дальнейшее улучшение решения невозможно, так как во 2-й оценочной строке нет отрицательных элементов. Следовательно, достигнуто оптимальное решение задачи. Но

искусственные переменные z1 , z2 не выведены из базиса и не равны

нулю, следовательно, исходная задача не имеет решения, так как ее допустимое множество пусто.

Задачи для самостоятельного решения

Решить методом исскуственного базиса:

108

4.5. Двойственные задачи линейного программирования

Рассмотрим задачу линейного программирования, записанную в произвольной форме:

xj 0 ( , неттребованийна знак) , j 1, n .

Данную задачу будем называть исходной. Под двойственной задачей (ДЗ) к исходной понимается задача линейного программирования, которая строится по правилам, приведенным в таблице 4.5.1, при этом в случае, когда целевая функция в исходной задаче минимизируется, таблица прочитывается справа налево.

Таблица 4.5.1

110

Данная таблица позволяет сформулировать несколько общих правил построения двойственных задач:

• каждому i-му ограничению исходной задачи соответствует переменная yi в ДЗ, и, наоборот, каждому k-му

ограничению ДЗ соответствует переменная xk исходной задачи;

•матрицы ограничений в исходной и двойственной задачах взаимно транспонированы;

•правые части ограничений исходной задачи становятся коэффициентами целевой функции в ДЗ, а коэффициенты целевой функции исходной задачи - правыми частями ограничений в ДЗ;

•если целевая функция в исходной задаче максимизировалась (минимизировалась), то в ДЗ целевая функция минимизируется (максимизируется).

Используя данные правила, построим ДЗ к ЗЛП, записанной в симметричной форме. В ДЗ целевая функция минимизируется:

m

bi yi min .

i 1

Все ограничения в симметричной форме задачи имеют вид

n

aij x j bi , поэтому на все переменные ДЗ будет присутствовать

j 1

требование неотрицательности yi 0 , i 1, m . На все переменные в симметричной форме присутствует требование неотрицательности,

111

Аналогично, нетрудно получить ДЗ для ЗЛП, записанной в канонической форме:

Заметим, что, прежде чем строить двойственную задачу, удобно исходную вначале привести к симметричной или канонической форме, а затем по шаблону к полученной форме задачи построить двойственную. При этом полученные разными способами двойственные задачи будут эквивалентными.

Выпишем основные свойства, которые справедливы для пары двойственных задач. Рассмотрим, например, в качестве пары двойственных задач симметричную и двойственную к ней. В матричной форме они записываются следующим образом:

Свойство 1. Задача двойственная к двойственной является исходной.

Свойство 2. Для любых х допустимых в исходной задаче, и у, допустимых в двойственной, справедливо неравенство

cT x bT y .

Свойство 3. Если исходная задача не имеет решения из-за неограниченности целевой функции на допустимом множестве, то допустимое множество двойственной задачи пусто.

Свойство 4. Возможен вариант, когда допустимые множества исходной и двойственной задач одновременно пусты.

Например:

112