Пример 17.

Найти максимальное значение функции при условиях

Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях

Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции

(57)

при условиях

(58)

(59)

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

(60)

при условиях

(61)

(62)

Выбрав в качестве базиса векторы и , составим симплексную таблицу (табл. 16) для исходной задачи (57) – (59).

Таблица 16

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–4 –6	–1 –1	–2

Из этой таблицы видим, что планом двойственной задачи (57) – (59) является . При этом плане Так как в столбце вектора Р ₀ таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р ₄и Р ₅ имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р ₀. В данном случае это число –6. Следовательно, из базиса исключаем вектор Р ₅. Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем

Значит, в базис вводим вектор P ₂. Переходим к новой симплекс–таблице (табл. 17).

Таблица 17

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 2		–7	1/2 –3/2 1/2 1/2				1/2 1/2 –1/2 1/2

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

Так как в столбце вектора Р ₀ таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18).

Таблица 18

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 1 p 2		8/3 14/3 2/3 32/3				1/3 –2/3 1/3 1/3	2/3 –1/3 –1/3 2/3

Как видно из таблицы 18, найдены оптимальные планы исходной и двойственной задач. Ими являются и . При этих планах значения линейных форм исходной и двойственной задач равны между собой:

Дата добавления: 2015-07-26