Решение задачи 1.2

Максимизировать целевую функцию:

Y=2x₁-5x₂+7x₃ → max

При ограничениях:

0x₁-2x₂+x₃ ≤ 1

2x₁+x₂+x₃ ≤ 4

-x₁-2x₂+0x₃ ≤ -1

0x₁+2x₂+0x₃≤3

 

x_1,2,3 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x₄, x₅, x₆ и х₇.

0x₁-2x₂+x₃+1x₄+0x₅+0x₆+0x₇ = 1

2x₁+x₂+x₃+0x₄+1x₅+0x₆+0x₇ = 4

x₁+2x₂+0x₃+0x₄+0x₅+1x₆+0x₇ = 1

0x₁+2x₂+0x₃+0x₄+0x₅+0x₆+1x₇=3

Выразим допустимый базис в форме Таккера:

X₄=1-(0x₁-2x₂+x₃)

X₅=4-(2x₁+x₂+x₃)

X₆=-1-(-x₁-2x₂+0x₃)

X₇=3-(0x₁+2x₂+0x₃)

Целевая функция в форме Таккера:

Y=0-(-2x₁+5x₂-7x₃)

На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.5).

Таблица 1.5

БП	СЧ	X1	X2	X3	X4	X5	X6	X7
X4			-2
X5
X6	-1	-1	-2
X7
Y		-2		-7

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.6.

Таблица 1.6

БП	СЧ	X1	X2	X3	X4	X5	X6	X7
X4			-2
X5			-3
X1							-1
X7
Y				-7			-2

 

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X4. Результат отображен в таблице 1.7.

Таблица 1.7

БП	СЧ	X1	X2	X3	X4	X5	X6	X7
X3			-2
X5			-1		-1
X1							-1
X7
Y			-5				-2

 

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X1. Результат отображен в таблице 1.8.

Таблица 1.8

БП	СЧ	X1	X2	X3	X4	X5	X6	X7
X3							-1
X5	3/2	1/2			-1		3/2
X2	1/2	1/2					-1/2
X7		-1
Y	23/2	5/2					-9/2

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X6, выводим из базиса X5. Результат отображен в таблице 1.9.

Таблица 1.9

БП	СЧ	X1	X2	X3	X4	X5	X6	X7
X3		4/3			1/3	2/3
X6		1/3			-2/3	2/3
X2		2/3			-1/3	1/3
X7		-4/3			2/3	-2/3
Y

 

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

 

Ответ: Решение оптимально

Y=16

X=(0;1;3;0;0;1;1)

Количество итераций=4