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

Каждой задаче линейного программирования

со смешанными ограничениями вида

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

при ограничениях

Обе приведенные выше задачи образуют так называемую двойственную пару. Совместное рассмотрение таких пар задач позволяет исследовать влияние изменения управляемых и неуправляемых переменных системы на значение целевой функции, проводить экономический анализ результатов расчетов. Сопоставляя записи прямой и двойственной задач, можно установить следующие взаимосвязи:

· если прямая задача является задачей максимизации, то двойственная – минимизации и наоборот;

· коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

· свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

· матрица ограничений двойственной задачи получается транспонированием матрицы ограничений прямой задачи;

· число переменных двойственной задачи равно числу ограничений прямой задачи и наоборот.

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

Основное содержание связи между задачами двойственной пары заключается в том, что решая симплекс-методом одну из них, автоматически получается решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач и оценок в последней симплекс-таблице:

		...		...				...		...
		...		...				...		...
		...		...				...		...

Отсюда имеем оптимальный план двойственной задачи.

· Если прямая задача решается на максимум:

· Если прямая задача решается на минимум:

Рассмотрим пример.

Приведем задачу к каноническому виду

Таблица I.

№ 1

Здесь в условиях наших обозначений: (количество истинных переменных) и (количество дополнительных переменных = количеству ограничений задачи):

Заметим так же, что задача решается на максимум.

Таблица II.

№ 2
				-2

Таблица III.

№ 3
							-
							-

Оптимальный план двойственной задачи, судя по вектору , будет иметь вид

Поиск по сайту: