Алгоритм двойственного симплекс-метода

1. Построение псевдоплана в канонической форме задачи и заполнение симплекс-таблицы

2. Выбор разрешающей строки, для которой b_i< 0. Если все b_i > 0, то псевдоплан является оптимальным опорным планом, т. е. найдено решение задачи.

3. Выбор разрешающего столбца по наименьшему по абсолютной величине отношению элементов нулевой строки к соответствующим отрицательным элементам разрешающей строки.

4. На пересечении разрешающей строки и разрешающего столбца находится разрешающий.

5. Пересчет элементов таблицы – по формулам Жордана Гаусса (2.7)

Зависимость оптимальных решений пары двойственных задач.

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

2. Коэффициенты при Х_j в строке функции цели на последней итерации симплекс-метода представляют собой разность между левыми и правыми частями j-го ограничения двойственной задачи.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов вузов. М.: Высш. шк., 1986. с.88-116.

2. Исследование операций в экономике: Учебн. пособ. Для вузов /Н.Ш. Кремер, Б.А. Путко и др.; Под. ред. проф. Н.Ш.Кремера. М.: Банки и биржи, ЮНИТИ, 1997. 99-121.

3. Деордица Ю.С., Нефедов Ю.М. Исследование операций в планировании и управлении: Учебн. пособ. К.: Вища школа, 1991. с.54-65.

4. Зайченко Ю.П., Шумилова С.А. Исследование операций: сборник задач, 2-е изд. К.: Вища школа, 1990. с.25-35

ЗАДАЧА 4

Решить задачу параметрического программирования

Рекомендации к решению задачи

Решение задачи с параметром в целевой функции заключается в нахождении для каждого значения параметра t из промежутка [,] максимального значения функции

(4.1)

(4.2)

(4.3)

Процесс решения задачи включает следующие этапы:

1. Считая значение параметра t равным некоторому числу t₀[,], находят оптимальный план Х^* или устанавливают неразрешимость задачи.

2. Определяют множество значений параметра t[,], для которых найденный оптимальный план остается оптимальным, или задача неразрешима. Эти значения в дальнейшем исключают из рассмотрения.

3. Полагают значение параметра t равным некоторому числу из оставшейся части промежутка [,], и симплекс-методом находят решение для полученной задачи.

4. Определяют множество значений параметра t[,], для которых найденный оптимальный план остается оптимальным, или задача неразрешима. Вычисления повторяют до тех пор, пока не будет исследован весь промежуток [,].

Решение задачи с параметром в правых частях ограничений заключается в нахождении для каждого значения параметра t из промежутка [,] максимального значения функции

(4.4)

(4.5)

(4.6)

Процесс решения задачи включает следующие этапы:

1. Считая значение параметра t равным некоторому числу t₀[,], находят оптимальный план Х^* или устанавливают неразрешимость задачи.

2. Определяют множество значений параметра t[,], для которых найденный оптимальный план остается оптимальным, или задача неразрешима. Эти значения в дальнейшем исключают из рассмотрения.

3. Полагают значение параметра t равным некоторому числу из оставшейся части промежутка [,], и двойственным симплекс-методом находят решение для полученной задачи.

4. Определяют множество значений параметра t [,], для которых найденный оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяют до тех пор, пока не будет исследован весь промежуток [,].

Пример Для каждого значения параметра t (—,) найти максимальное значение функции

(4.7)

при условиях

(4.8)

Решение. Считая значение параметра t в системе уравнений (4.8) равным нулю, находим решение задачи (4.7)—(4.8). (Таблица 1.)

Таблица 1.

Базис	3	-2	5	0		-4
	х1	х2	х3	х4	х5	Bi
3	1	1	1	0	0	12+t
4	2	-1	0	1	0	8+4t
5	-2	2	0	0	1	10-6t
f	10	-1	0	0	0	20+29t
Вторая симплекс-таблица
3	2	0	1	0	-1/2	7+4t
4	1	0	0	1	½	13+t
2	-1	1	0	0	½	5-3t
f	9	0	0	0	½	25+26t

Как видно из таблицы, Х^*₀= (0; 5-3t; 7+4t; 13+t; 0) при t=0 есть оптимальный план задачи. Очевидно, Х^*₀ является оптимальным планом и тогда, когда среди его компонент не окажется отрицательных чисел, т. е. при 5-3t0; 7+4t0; 13+t0 или при -7/4t5/3. Таким образом, если t. [-7/4, 5/3], то Х^*₀=(0; 5-3t, 7+4t; 13+t; 0) – оптимальный план задачи (4.7)—(4.8), при котором F_max=25+26t.

Исследуем теперь, имеет ли задача оптимальные планы при t> 5/3. Если t>5/3, то 5-3t< 0 и, следовательно, Х= (0; 5-3t;.7+4t; 13+t; 0) не является планом задачи. Поэтому при t> 5/3 нужно перейти к новому плану, который был бы в то же время и оптимальным. Это можно сделать в том случае, когда в строке вектора Р₂ имеются отрицательные числа х^’_2j . В данном случае это условие выполняется. Поэтому переходим к новому опорному плану, для чего введем в базис вектор Pi и исключим из него вектор Р₂. (Таблица 2)

Таблица 2.

Базис	3	-2	5	0		-4
	х1	х2	х3	х4	х5	Bi
3	0	2	1	0	½	17-2t
4	0	1	0	1	1	18-2t
1	1	-1	0	0	-1/2	-5+3t
f	0	9	0	0	5	70-t

Как видно из табл.2, X*₁ =(-5+3t; 0; 17-2t; 18-2t; 0)— оптимальный план задачи для всех t, при которых 17-2t0; 18-2t0; -5+3t0, т.е. при 5/3t17/2. Следовательно, если t[5/3, 17/2], то Х*₁=(-5+3t; 0; 17-2t; 18-2t; 0) является оптимальным планом исходной задачи, причем F_max =70-t.

Если t> 17/2, то X₁= (-5+3t; 0; 17-2t; 18-2t/ 0) не является планом задачи, так как третья компонента 17—2t есть отрицательное число. Поскольку среди элементов 1-й строки табл. 2. нет отрицательных, при t> 17/2 исходная задача неразрешима.

Исследуем теперь разрешимость задачи при t<-7/4. В этом случае Х= (0; 5-3t; 7+4t; 13+t;0) (см. табл. 2.) не является планом задачи, так как третья компонента 7+4t есть отрицательное число. Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Рз стоит отрицательное число -1/2), нужно исключить из базиса вектор Рз и ввести в базис вектор Р₅ (табл. 3).

Таблица 3

базис	3	-2	5	0		-4
	х1	х2	х3	х4	х5	Bi
5	-4	0	-2	0	1	-14-8t
4	3	0	1	1	0	20+5t
1	1	1	1	0	0	12+t
f	11	0	1	0	0	32+30t

Как видно из табл.3, Х^*₂=(0; 12+t; 0; 20+5t; -14-8t) является оптимальным планом задачи для всех значений параметра t, при которых –14-8t0; 20+5t0; 12+t0, т.е. при-4  t  -7/4. Таким образом, если -4  t  -7/4, то задача (4.7)—(4.8) имеет оптимальный план Х^*₂=(0; 12+t; 0; 20+5t; -14-8t), при котором F_max=32+30t.

Из табл.3 также видно, что при t<-4 задача неразрешима, поскольку в строке вектора Р₄ нет отрицательных элементов.

Итак, если t (-, -4), то задача не имеет оптимального плана; если t [-4,-7/4], то Х^*₂=(0; 12+t; 0; 20+5t; -14-8t), при котором F_max=32+30t; если t [-7/4, 5/3], то Х^*₀=(0; 5-3t, 7+4t; 13+t; 0) – оптимальный план задачи, при котором F_max=25+26t; если t [5/3, 17/2], то Х*₁=(-5+3t; 0; 17-2t; 18-2t; 0) является оптимальным планом исходной задачи, причем F_max =70-t., если t[17/2, ], то задача неразрешима.