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

Конечно же, ничего не мешает использовать другие переменные при построении уравнений, необходимых для определения значений переменных двойственной задачи. Например, ограничения, ассоциируемые с переменными хх и х3, порождают следующие уравнения (проверьте!):

у, + 2у2-5 = 0, у, + Зу2-4=.

Решение этой системы уравнений также приводит к оптимальным значениям двойственной задачи у, = 29/5 и у2 = -2/5. Однако эти уравнения уже не так просты, как уравнения, ассоциируемые с переменными xt и R. (Убедитесь самостоятельно, что уравнения, ассоциированные с любыми двумя переменными из множества xv х2, х3, xt, R, дают одни и те же значения переменных двойственной задачи.)

УПРАЖНЕНИЯ 4.2.3

1. С помощью программы TORA решите двойственную к следующей задачу ЛП и затем найдите оптимальное решение прямой задачи.

Минимизировать z = 5х, + 6х2 + Зх3

при ограничениях

5*, + Ьх2 + Зх3 > 50, х, + хг - хг > 20, 7х, + 6х2 - 9х, > 30, 5х,+ 5х2 + 5х3>35, 2х, + 4х2- 15х3>10,

12х,+ юх2>90,

х2 - 10х3 > 20, х хг, х3>0.

2. Дана следующая задача линейного программирования.

Максимизировать z = Ьхх + 2хг + Зх3

при ограничениях

х,+ 5х2 + 2Хз = 30, х, - 5х2 - 6х3 < 40, х х2, х3>0.

Оптимальное решение этой задачи удовлетворяет уравнению (получено из z-строки симплекс-таблицы)

z + 0х, + 23х2 + 7х3 + (5 + M)xt + 0х5 = 150,

где искусственная переменная х4 и дополнительная переменная х6 входили в начальное базисное решение. Запишите соответственную двойственную задачу и найдите ее оптимальное решение, исходя из приведенного уравнения.

3. Дана следующая задача линейного программирования.

Максимизировать z = хх + Ъхг + Злг3

при ограничениях

хх + 2х2 + х3 = 3, 2л:, - х2 = 4, х х2, х3>0.

a) Запишите соответствующую двойственную задачу.

b) Используя информацию о том, что оптимальное базисное решение этой задачи содержит переменные л:, и х3, найдите оптимальное решение двойственной задачи.

4. Дана следующая задача линейного программирования.

Максимизировать z = 2хх + 4х2 + 4х3 - 3xt при ограничениях

хх + 4х2 + xt = 8,

1 2> 3> 4 ~

Оптимальное решение этой задачи удовлетворяет уравнению (получено из 2-строки симплекс-таблицы)

2 + 2л:, + 0л:2 + 0л:3 + Зх4 = 16.

Используя эту информацию, найдите оптимальное решение двойственной задачи.

5. С помощью двойственной задачи найдите допустимое решение следующей системы неравенств:

2л:,+ 3л:2<12, -Зл:,+ 2л:2<-4, Зл:, - 5л:2<2,

хх - свободная переменная, л:2>0.

(Совет. Добавьте к этой системе неравенств тривиальную целевую функцию максимизировать z - Оле, + 0х2 и решите двойственную задачу.)

6. Найдите оптимальное значение целевой функции следующей задачи, основываясь только на свойствах ее двойственной задачи (т.е. не применяя симплекс-метод к двойственной задаче).

Минимизировать z = 10л:, + 4лс2 + 5х3

при ограничениях

5л:,- 7лг2 + Зл:3>50, *р х2, х3>0.

4.2.4. Вычисление симплекс-таблиц

В этом разделе будет показано, как на основе исходных данных задачи вычисляется симплекс-таблица и как вычисляется обратная матрица на каждой итерации. С учетом структуры симплекс-таблиц, показанной на рис. 4.1, все эти вычисления можно разбить на две группы.

1. Вычисление значений в столбцах ограничений симплекс-таблицы (как левой, так и правой частей ограничений).

2. Вычисление значений в 2-строке.

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

Столбец коэффициентов ограничений на i-й итерации

(Обратная матрица на /-й итерации )

Столбец исходных коэффициентов ограничений J

Вычисление значений z-строки. На произвольной симплекс-итерации значения коэффициентов в z-строке вычисляются по следующей формуле 2.

Коэффициент при j-n f переменной в z-строке прямой задачи

Значение левой части j-ro неравенства двойственной задачи

Значение правой части у-го неравенства двойственной задачи

Отметим, что формула 2 такая же, какая используется в методе 2 (раздел 4.2.3) для определения оптимального решения двойственной задачи.

Пример 4.2.2

На основе задачи из примера 4.2.1 покажем, как использовать формулы 1 и 2. Из оптимальной симплекс-таблицы этой задачи получаем

обратная матрица =

2/5 -1/5 1/5 2/5

С помощью формулы 1 вычислим коэффициенты в столбцах ограничений оптимальной симплекс-таблицы.

Столбец коэффициентов ограничений, соответствующий переменной х,

Обратная матрица

из оптимальной симплекс-таблицы,

(2/5 -ф] (1 1/5 2/5 J [2

Столбец исходных коэффициентов ограничений, соответствующий переменной х,

Аналогично вычисляются другие столбцы коэффициентов ограничений.

Столбец коэффициентов ограничений, соответствующий переменной х2

Столбец коэффициентов ограничений, соответствующий переменной х3

< Столбец коэффициентов ограничений, соответствующий переменной xt

2/5 1/5

2/5 1/5

-1/5 2/5

-1/5 2/5

-1/5 7/5