Теорема 10

Если основная задача линейного программирования имеет оптимальный план X^*, то является оптимальным планом двойственной задачи.

Таким образом, если найти симплексным методом оптимальный план задачи (43) – (45), то, используя последнюю симплекс–таблицу, можно определить и и с помощью соотношения найти оптимальный план двойственной задачи (46), (47).

В том случае, когда среди векторов , составленных из коэффициентов при неизвестных в системе уравнений (44), имеется т единичных, указанную матрицу образуют числа первых т строк последней симплекс–таблицы, стоящие в столбцах данных векторов. Тогда нет необходимости определять оптимальный план двойственной задачи умножением на , поскольку компоненты этого плана совпадают с соответствующими элементами (m +1)–й строки столбцов единичных векторов, если данный коэффициент , и равны сумме соответствующего элемента этой строки и если

Сказанное выше имеет место и для симметричной пары двойственных задач. При этом так как система ограничений исходной задачи содержит неравенства вида “ ”, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m +1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным.

Date: 2015-06-06; view: 476; Нарушение авторских прав