Симплексный метод решения задачи линейного программирования

Шаг1. Выписываем исходное допустимое базисное решение и соответствующее ему значение целевой функции.

х3, х4, х5 - базисные переменные.

х1 х2 х3 х4 х5

Х = 0 0 18000 3000 1000

Z = 150·0+300·0+0·18000+0·300+0·1000 = 0.

Шаг2. Проверяем оптимальность полученного решения. Если решение не оптимально, то переходим к шагу 3. В противном случае записываем ответ.

Пусть ∆ х1 =1, тогда ∆ х3 =-7, ∆ х4 =-2, ∆ Х5 =-1

∆Z=150·1+300·0+0·(-7)+0·(-2)+0·(-1)=150. Так как ∆Z ³ 0, то переменную х1 целесообразно ввести в базис.

Шаг3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

х3 ³ 0 х3 =18000 - 7х1, 18000 - 7х1³ 0, х1 £ 257,1,

х4 ³ 0 х4 =300 - 2х1, 300-2х1 ³ 0, х1 £ 1500,

х5 ³ 0 х5 =100 - х1, 100 - х1 ³ 0, х1 £ 100.

Решением системы неравенств является третье неравенство, поэтому из базиса выводим переменную х5.

Шаг 4. Пересчитываем систему уравнений задачи с учетом нового состава базисных переменных.

уравнение х1 +х2+х5 =1000,

уравнение _7х1 +40х2 +х3 =18000

х1 +7х2+7х5 =7000

х2 +х3 - 7х5 =11000,

уравнение _2х1 +9х2 +х4 =3000

х1 +2х2+2х5 =2000

х2+х4 - 2х5 = 1000.

В результате имеем следующую систему уравнений:

х2 +х3 - 7х5 = 11000,

х2+х4 - 2х5 = 1000,

х1 +х2+х5 =1000.

Итерация 2.

Шаг1. Выписываем исходное допустимое базисное решение.

х3, х4, х1 - базисные переменные.

х1 х2 х3 х4 х5

Х = 1000 0 11000 1000 0

Z=150·1000+300·0+0·11000+0·1000+0·0=150000

Шаг2. Проверяем оптимальность полученного решения.

Пусть ∆ х2 =1, тогда ∆ х3 =-33, ∆ х4 = -7, ∆ Х5 = -1

∆Z=150·(-1)+300·1+0·(-33)+0·(-7)+0·0=150. Так как ∆Z ³ 0, то переменную х2 целесообразно ввести в базис.

Шаг 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

х3 ³ 0 х3 =11000 - 33х2, 11000 - 33х2 ³ 0, х2 £ 333,3,

х4 ³ 0 х4 =1000 - 7х2, 1000 -7х2 ³ 0, х2 £ 142,9,

х1 ³ 0 х1 =1000 - х2, 1000 - х2 ³ 0, х2 £ 1000.

Переменную х4 выводим из базиса.

Шаг4. Пересчитываем систему уравнений задачи с учетом нового состава базисных переменных.

уравнение 7х2+х4 - 2х5 = 1000,

х2+1/7х4 - 2/7х5 = 1000/7,

уравнение _х1 +х2+х5 =1000

х2+1/7х4 - 2/7х5 = 1000/7

х1- 1/7х4 +9/7х5 = 857,4,

уравнение _33х2 +х3 - 7х5 = 11000

х2+33/7х4 - 66/7х5 = 33000/7

х3 - 67,15х4 + 2,42х5 = 6285,7.

В результате имеем следующую систему уравнений:

х3 - 67,15х4 + 2,42х5 = 1571,5,

х2+1/7х4 - 2/7х5 = 1000/7,

х1- 1/7х4 +9/7х5 = 6285,7.

Итерация 3.

Шаг1. Выписываем исходное допустимое базисное решение.

х3, х2, х1 - базисные переменные.

х1 х2 х3 х4 х5

Х = 857,4 142,9 6285,7 0 0

Z=150·857,4+300·142,9+0·6285,7+0·0+0·0 = 171429.

Шаг2. Проверяем оптимальность полученного решения.

Пусть ∆ х4 =1, тогда ∆ х3 = 67,15, ∆ х2 = -1/7, ∆ Х1 = -1/7.