1.5.3. Геометрическая интерпретация двойственных задач

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

1) обе задачи имеют оптимальные планы;

2) планы имеет только одна задача;

3) для каждой задачи двойственной пары множество планов пусто.

Пример 15. Пусть дана пара двойственных задач. Найти графическое решение обеих задач.

Прямая задача Двойственная задача

Решение. Обе задачи содержат по две переменных. Следовательно, они разрешимы. По системе ограничений исходной задачи строим область допустимых решений (Рис.1.13). Затем строим линию уровня для функции , и передвигаем её параллельно самой себе в направлении вектора , пока не достигнем крайней точки области допустимых решений.

Этой точкой будет являться точка А(8/3;2/3), то есть, . В точке А целевая функция достигает максимума .

Графическое решение для двойственной задачи (Рис 1.14). Строим область допустимых решений в соответствие с ограничениями. Затем строим линию уровня для функции , и перемещаем её параллельно самой себе в направлении вектора до тех пор, пока она коснётся области допустимых решений. Этой точкой будет являться точка В(1/3;8/3), то есть . В точке В целевая функция достигает минимума и будет равна .

Между переменными существует взаимно однозначное соответствие .

Базисным переменным исходной задачи и соответствуют свободные переменные двойственной и . Свободным переменным исходной задачи и , соответствуют базисные переменные двойственной и .