Приклад рішення задачі симплекс – методом з штучним базисом

Умова:

Z = 8x₁ + 5x₂ (min)

1.5x₁ + 2x₂ 35

50x₁ + 30x₂ 900

6x₁ + 5x₂ = 100

x_j 0

Приводимо систему обмежень до канонічного виду. Для цього в перше та друге обмеження вводяться доповнюючи змінні x₃, та x₄. Задача прийме такий вигляд:

Z = 8x₁ + 5x₂ + 0x₃ + 0x₄ (min)

1.5x₁ + 2x₂ + x₃ = 35

50x₁ + 30x₂ + x₄ = 900

6x₁ + 5x₂ = 100

x_j 0

Система обмежень має два одиничних вектори - А₃ та А₄ . Для того, щоб отримати базис вводимо штучну змінну А₅. Система прийме вигляд:

Z = 8x₁ + 5x₂ + 0x₃ + 0x₄ + 0x₅ (min)

1.5x₁ + 2x₂ + x₃ = 35

50x₁ + 30x₂ + x₄ = 900

6x₁ + 5x₂ + x₄ = 100

x_j 0

Змінні третя четверта та п’ята створюють базис. Можемо записати симплексну таблицю і знайти оптимальне рішення.

Базис	Сi базис	План А0					М
А1	А2	А3	А4	А5
А3			1.5					35/2
А4								900/30
А5	М							100/5
Zj - Cj		-8	-5
	5M	5M
А2		17.5	0.75		0.5			17.5|0.75
А4		37.5	27.5		-15			37.5/27.5
А5	M	12.5	1.25		-2.5			12.5/1.25
Zj - Cj	87.5	-4.25		2.5
12.5	1.25M		-2.5M
А2					-1
А4					-70		-
А1							-
Zj - Cj				-6		-
-	-	-	-	-	-

Оскільки всі Z_j - C_j 0 ми знайшли оптимальний план, який надає мінімального значення цільовій функції. Оптимальній план має вигляд:

Х_опт( х₁ = 10,.х₂ = 10,.х₃ = 0,.х₄ = 0,.х₅ = 0.), Z_min= 130

Дата добавления: 2014-01-07