Шаг 41.
Соотношения между оптимальными решениями прямой и двойственной задач

    На этом шаге мы рассмотрим соотношения между оптимальными решениями прямой и двойственной задач.

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

    Соотношение 1. Для любой симплекс-итерации прямой или двойственной задачи.

    Это соотношение симметрично относительно прямой и двойственной задач. Его можно использовать для определения оптимального решения одной задачи непосредственно из симплекс-таблицы, содержащей оптимальное решение другой. Данное обстоятельство обуславливает возможность проведения вычислений именно по той задаче (прямой или двойственной), которая требует меньших вычислительных ресурсов. Например, если прямая задача имеет 100 переменных и 500 ограничений, то предпочтительнее нахождение оптимального решения двойственной задачи, так как она будет содержать только 100 ограничений.

    Представим еще одно соотношение между прямой и двойственной задачами, которое совместно с соотношением 1 предлагает интересную экономическую интерпретацию задачи линейного программирования.

    Соотношение 2. Для любой пары допустимых решений прямой и двойственной задач

    В точке оптимума это соотношение принимает вид строгого равенства.

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




Предыдущий шаг Содержание Следующий шаг