Пример 14

Найти решение двойственной пары задач.

Исходная задача;

Двойственная задача:

Решение. Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8). Из рис. 7 видно, что исходная задача не имеет оптимального плана из-за неограниченности снизу ее целевой функции на множестве допустимых решений.

Из рис. 10 следует, что двойственная задача не имеет планов, поскольку многоугольник решений ее пуст. Это означает, что если исходная задача двойственной пары не имеет оптимального плана из-за неограниченности на множестве допустимых решений ее целевой функции, то двойственная задача также не имеет планов.

Нахождение решения двойственных задач. Рассмотрим пару двойственных задач – основную задачу линейного программирования (43) – (45) и двойственную к ней задачу (46), (47).

Предположим, что с помощью симплексного метода найден оптимальный план X^* задачи (43) – (45) и этот план определяется базисом, образованным векторами .

Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции (43) задачи (43) – (45), а через – матрицу, обратную матрице Р, составленной из компонент векторов базиса. Тогда имеет место следующее утверждение.