Определение оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой

Пусть исходная задача дана в канонической форме Оптимальное решение получено симплекс-методом, — базисная матрица оптимального решения.

Оптимальное решение двойственной задачи (по первой теореме двойственности).

.

элементы строки оценок в оптимальной симплекс-таблице прямой задачи вычисляются по формулам Памятуя о том, что ограничение двойственной задачи, соответствующее переменной прямой задачи, имеет вид.

.

.

выводим важное свойство оценок :

Оценка переменной в симплекс-таблице равна разнице левой и правой части соответствующего ограничения двойственной задачи.

Из соотношения легко найти компоненты оптимального решения двойственной задачи.

Действительно, пусть — единичный вектор с единицей в i-ой строке. В исходной симплекс-таблице всегда есть такие вектора.

Оценка переменной согласно (6) запишется.

.

Откуда Таким образом, для определения компоненты оптимального решения двойственной задачи следует в исходной симплекс-таблице выбрать единичный столбец с единицей в i-ой строке. Тогда компонента равна оценке переменной из оптимальной симплекс-таблицы плюс коэффициент критерия этой переменной.

Пример:

Найдем оптимальное решение двойственной задачи к задаче раздела 5.2 о работе предприятия по двум технологиям.

Воспроизведем для наглядности решение симплекс-методом Единичная матрица в исходной симплекс таблице расположена в столбцах 3, 4, 5.

Оптимальное решение двойственной задачи будет находиться в строке оценок оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы: