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

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

• в задаче (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. Построить задачу, двойственную данной задаче линейного программирования: