Решить задачу симплекс- методом

Решение: В первом уравнении нет оснований вводить переменную искусственного базиса, поэтому в нем можно выделить в базис переменную х₃. Во второе и третье уравнения введем две искусственные переменные у₁ и у₂ (для удобства, в правые части уравнений). Т.о. получаем: (х₃; y₁; y₂)- базис, (х₁; х₂; x₄; x₅) – свободные.

Z = 0 – (- х₁ – 2х₂) → min

Составим симплекс-таблицу №1.

Св. Баз.	х1	х2	х4	х5	в1
х3		-5
у1	-2		-1
у2	-1		-2
Z	-1	-2
М	-3		-3

(в строке (m + 2), т.е в М выбираем наибольший положительный элемент, т.е. 5, т.к. он максимально «тянет» в положительную сторону функцию цели в задаче на минимум).

Переходим к симплекс-таблице №2.

Св. Баз.	х1	y2	х4	х5	в1
х3	4/3		-4/3	5/3	28/3
у1	-4/3		1/3	1/3	2/3
х2	-1/3		-2/3	1/3	5/3
Z	-5/3		-4/3	2/3	10/3
М	-4/3		1/3	1/3	2/3

(в данной таблице значения 1/3 расположены в двух столбцах, поэтому выбираем наиболее для нас удобный).

Симплекс-таблица №3.

Св. Баз.	х1	y1	х5	bi
х3	-4
x4	-4
х2	-3
Z	-7
М

(после заполнения с.-т. № 3 мы пришли к строке М, которая является нулевой и ее отбрасывают вместе с у и получают первое допустимое базисное решение: столбец b_i не отрицателен, поэтому теперь задачу можно решать, как на максимум, так и на минимум).

Анализируя строку Z видим, что х₅ входит в целевую функцию Z со знаком «+», поэтому продолжаем переход к с.-т. № 4.

Симплекс- таблица № 4.

Св. Баз.	х1	х4	bi
х3		-3
x5	-4
х2		-1
Z		-2

Симплекс- таблица № 5.

Св. Баз.	х3	х4	bi
х1	1/8	-3/8	¾
x5	½	-1/2
х2	-1/8	-5/8	¼
Z	-1/8	-13/8	10/8

Т.к. в строке Z все коэффициенты отрицательные, следовательно, решение оптимальное:

Х(3/4;1/4;0;0;5); Z_min = 10/8.

Дата добавления: 2014-11-08