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
( Столбец коэффициентов ограничений, соответствующий
переменной R
(2/5 -1/5
( Столбец коэффициентов ! хг правых частей ограничений ) \х,
1/5 2/5
2/5 -1/5 1/5 2/5
-1/51 2/5
12/5 26/5
Теперь применим формулу 2 для вычисления коэффициентов в г-строке. Оптимальные значения двойственных переменных у2) =(29/5,-2/5) вычислены в примере 4.2.1 двумя различными методами. Эти значения используются для вычисления коэффициентов в г-строке.
Коэффициент при xi = y1 + 2y2-5 = 29/5 + 2х(-2/5) -5 = 0. Коэффициент при х2 = 2j/, - у2 - 12 = 2х(29/5) - (-2/5) -12 = 0. Коэффициент при х3 = г/, + Зу2 - 4 = 29/5 + Зх(-2/5) - 4 = 3/5. Коэффициент при xt = уг - 0 = 29/5 - 0 = 29/5. Коэффициент при R = y2- (-М) = -2/5 - (-М) = -2/5 + М.
Важно отметить, что формулы 1 и 2 можно применять на любой симплекс-итерации как к прямой, так и к двойственной задаче.
УПРАЖНЕНИЯ 4.2.4
1. В задаче из примера 4.1.2 с помощью программы TORA (выполнив команду Iterations oM-method) определите элементы симплекс-таблицы первой итерации. Затем с помощью формул 1 и 2 найдите значения всех элементов оптимальной симплекс-таблицы.
2. Дана следующая задача ЛП.
Максимизировать г = 4лс1 + 14х2
при ограничениях
2x1 + 7x2 + x3 = 21, 1хх + 2хг + xt = 2l,
jc,, х2, JCg, х4 0.
Проверьте оптимальность и допустимость следующих базисных решений.
f 1/7 0 ,-2/7 1,
(0 1/2 1 -7/2 J
а) Базисные переменные (х2, xt), обратная матрица:
Ь) Базисные переменные (х2, хг), обратная матрица =
ч * г7/45 -2/451
c) Базисные переменные (х2, XJ, обратная матрица = I
( 1/2 0\
d) Базисные переменные (лс,, xt), обратная матрица =
1-7/2 \/