Решение

Будем использовать условия, которым должны удовлетворять двойственные задачи. Умножим ограничения – неравенства на (-1), так как в задаче на максимум они должны иметь вид « ». Исходная задача запишется в виде:

Составим двойственную задачу:

Переменная , соответствующая ограничению равенства, может быть любого знака.

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

Теорема 1. Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение, причем значения целевых функций задач на своих оптимальных решениях совпадают. Если же одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.

Теорема 2. Для того, чтобы допустимые решения , являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства:

(1)

(2)

Иначе, если при подстановке оптимального решения в систему ограничений i-е ограничение исходной задачи выполняется как строгое неравенство, то i-я координата оптимального решения двойственной задачи равна нулю, и, наоборот, если i-я координата оптимального решения двойственной задачи отлична от нуля, то i-е ограничение исходной задачи удовлетворяется оптимальным решением как равенство.

Задача 1	Задача 2
Подставим оптимальное решение в систему ограничений Пусть, например, , тогда Если, например, , то	Подставим оптимальное решение в систему ограничений Пусть, например, , тогда Если, например, , то
Если среди ограничений имеется ограничение-равенство, то соответствующая переменная двойственной задачи может быть любого знака

Пример 3. Найти решение исходной задачи, зная решения двойственной и используя вторую теорему двойственности.

Решение

Составим двойственную задачу:

Оптимальное решение двойственной задачи:

Подставим оптимальное решение в систему ограничений. Получим, что, первое, второе и пятое ограничения выполняются как строгие неравенства.

По теореме 2 следует, что соответствующие координаты оптимального решения исходной задачи (двойственной задачи), равны нулю .

Учитывая это, из системы ограничений исходной задачи получим:

Оптимальное решение исходной задачи:

.

Ответ:

Пример 4. Для ЗЛП построить двойственную задачу. Найти решение исходной задачи, зная решения двойственной:

Решение. Двойственная задача:

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

Решим двойственную задачу средствами Ms.Excel:

y1	y2
5,8	-0,4		54,8
10	8
1	2	5	>=	5
2	-1	12	>=	12
1	3	4,6	>=	4

Поскольку и отличны от нуля, то все ограничения исходной задачи выполняются в виде равенств: , а как видно из таблицы Excel, третье ограничение оптимальными значениями удовлетворяется в виде строгого неравенства, значит, , т.е.

, решая систему, получаем:

Ответ в исходной задаче: