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

 

Алгоритм построения взаимно-двойственных задач

 

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

• в задаче (1) требуется минимизировать целевую функцию: , а в задаче (2) - максимизировать: ;
• все ограничения задачи (1) – неравенства вида , все ограничения задачи (2) – неравенства –вида ;
• в задаче (1) n неизвестных и m ограничений (без учета условий неотрицательности), в задаче (2) m неизвестных и n ограничений (без учета условий неотрицательности);
• матрицы из коэффициентов при переменных , ,…, задач (1) и при переменных , , …, задачи (2) являются взаимно транспонированными;
• правые части системы ограничений задачи (1) – это коэффициенты целевой функции задачи (2); коэффициенты целевой функции задачи (1) – это правые части системы ограничений задачи (2);
• каждому ограничению задачи (1) в виде неравенства соответствует условие неотрицательности ассоциированной с этим ограничением переменной задачи; каждому ограничению задачи (1) в виде равенства соответствует переменная задачи (2) без ограничений на знак
• каждому ограничению задачи (2) в виде неравенства соответствует неотрицательная переменная задачи (1), каждому ограничению задачи (2) в виде равенства соответствует переменная задачи (1) произвольного знака.

 

Такие задачи называют парой двойственных задач линейного программирования (или просто двойственной парой).

 

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

Пример 1. Построить задачу, двойственную следующей задаче линейного программирования:

Решение

Умножим первое ограничение – неравенство на -1. Задача примет вид задачи (2) симметричной пары двойственных задач:

Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функцию.

.

Функция максимизируется, так как целевая функция исходной задачи минимизируется.

Умножаем коэффициенты при на соответствующие переменные двойственной задачи и складываем их:

.

Данная сумма меньше или равна коэффициенту при в целевой функции:

.

Неравенство имеет вид «», потому что целевая функция двойственной задачи максимизируется. Аналогично составляются еще два ограничения двойственной задачи (соответствуют переменным , ):

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

Поскольку все ограничения задачи (1) имеют вид , то переменные задачи (2)все неотрицательны:

Окончательно двойственная задача имеет вид:

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

Решение

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

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

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

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

 

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

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

(1)

(2)

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

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

 

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

Решение

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

 

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

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

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

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

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

.

Ответ:

 

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

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

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

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

 

y1	y2
5,8	-0,4		54,8
			>=
	-1		>=
		4,6	>=

 

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

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

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