Решение задачи методом потенциалов

Итерация 1

Шаг 1.

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

~ X1 X2 X3 X4 X5 X6 X7

~ Х1 = 0 0 24 27 16 0 500

Z = 6*0 + 8*0 + 0*24 + 0*27 + 0*16 - 0*0 – 500*М = - 500М

Шаг 2

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

Пусть ∆Х1 = 1

Тогда ∆Х3 = - 0,02

∆Х4 = - 0,01

∆Х5 = - 0,03

∆Х7 = -1

∆Z = 6*1 + 8*0 + 0*(- 0,02) + 0*(- 0,01) + 0*(- 0,03) - 0*0 + (- 1)*(-М)= 6 + М >0

Вывод: переменную x1 целесообразно ввести в базис, так как значение целевой функции увеличивается.

Шаг 3

Определяем какая из прежних базисных переменных должна быть выведена из базиса и в каком уравнении это произойдет.

24 ÷ 0,02 = 1200

27 ÷ 0,01 = 2700

16 ÷ 0,03 = 533,3

500 ÷ 1 = 500 (*)

Таким образом, в новом базисе будут находиться переменные x_1, x_3, x₄

и x₅, а переменная x₇ должна покинуть базис т.е стать небазисной.

Шаг 4

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

0,04Х2 + Х3 + 0,02Х6 - 0,02Х7 = 14

Х4 + 0,02Х6 - 0,02Х7 = 22

0,04Х2 + Х5 + 0,02Х6 - 0,02Х7 = 1

Х1 + Х6 - Х7 = 500

Итерация 2

Шаг 1

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

x1 x2 x3 x4 x5 x6 x7

Х2 = 500 0 14 22 1 0 0 0

Z = 6*500 + 8*0 + 0*14 + 0*22 + 0*1 - 0*0 -M*0 = 3000

Шаг 2.

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

Пусть ∆x2 = 1

Тогда ∆x3 = - 0,04

∆x4 = 0

∆x5 = - 0,04

∆x1 = 0

∆Z = 6*0 + 8*1 + 0*(- 0,04) + 0*0 + 0*(- 0,04) + 0*0 + 0*0 = 8 > 0

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

Шаг 3.

Определяем какая из прежних базисных переменных должна быть выведена из базиса и в каком уравнении это произойдет.

14 ÷ 0,04 = 350

22 ÷ - = -

1 ÷ 0,03 = 25 (*)

500 ÷ - = -

Таким образом, в новом базисе будут находиться переменные x_1,x_2,x₄ и x_3,

а переменная x₅ должна покинуть базис т.е стать небазисной.

Шаг 4.

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

x3 - x5 - 0,01x6 + 0,02x7 = 13

x4 + 0,01x6 - 0,01x7 = 22

x2 + 25x5 + 0,75 x6 - 0,75x7 = 0

x1 - x6 + x7 = 533.33

Итерация 4.

Шаг 1.

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

x1 x2 x3 x4 x5 x6 x7

Х3 = 500 25 13 22 0 0 0

Z = 6*500 + 8*25 + 0*13 + 0*22 + 0*1 + 0*0 + 0*0 = 3200

Шаг 2.

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

Пусть ∆Х5 = 1

Тогда ∆Х3 = 0

∆Х4 = 0

∆Х2 = - 25

∆Х1 = 0

∆Z = 6*0 + 8*(- 25) + 0*0 + 0*0 + 0*1 + 0*0 + 0*0 = - 200 < 0

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

Шаг 2 продолжается.

Пусть ∆Х6 = 1

Тогда ∆Х3 = 0,01

∆Х4 = - 0,01

∆Х2 = - 0,75

∆Х1 = 1

∆Z = 6*0 + 8*(- 0,75) + 0*0,01 + 0*(- 0,01) + 0*0 + 0*1 + 0*0 = - 6 < 0

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

Общий вывод по шагу 2: Х3 – оптимальное решение,

Х1 = 500,

Х2 = 25,

Z = 3200

1.5 РЕШЕНИЕЗАДАЧИ НА ПК В ПАКЕТЕ SIMPLEX.

При решении задачи на ПК в пакете Simplex ответы сошлись с ответами ручного и графического методов.

1.6 РЕШЕНИЕ ЗАДАЧИ В EXCEL.

При решении задачи на ПК в среде Excel ответы сошлись с ответами всех предыдущих методов.

С трех полей, имеющих запасы силоса, соответственно 560, 200 и 320 тонн требуется отвезти его в 4 траншей емкостью, соответственно 500, 150, 80 и 100 тонн.

Составить оптимальный маршрут перевозок силоса от полей к траншеям, обеспечивающий минимальные транспортные затраты. Расстояния от каждого поля до каждой траншеи представлены в таблице 2.1

Таблица 2.1.Исходные данные для транспортной задачи

Проверка задачи на разрешимость. ∑A_i =1080, ∑B_j=830, так как ∑A_i ≠ ∑B_j, ∑A_i>∑B_j задача закрытая.

Матрица модели

Решение задачи методом потенциалов

Таблица 2.2 Транспортная схема 1

Проверим построенный план на вырожденность. Число занятых клеток = 6, следовательно, план вырожденный.

Чтобы сделать его невырожденным добавим в клетку (1,2) ноль. Теперь ЧЗК=m+n-1=7, план невырожденный.

Итерация 1.

Шаг 1.

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

560 0 0 0 0

X₁ = 0 150 50 0 0

0 0 30 100 190

Z1=3*560+6*0+2*150+2*50+13*30+11*100+0*190=3570

Шаг 2.

Проверим полученный план на оптимальность. Так как количество занятых клеток равно величине m+n-1=6, а сумма строк и столбцов составляет m+n-1=7. В связи с этим некоторому потенциалу первой строки придаем нулевое значение.

С1,3=2≥6+0 -

С1,4=2≥0+4 -

С1,5=0≥0-7 +

С2,1=5≥-4+3 +

С2,4=6≥-4+4 +

С2,5=0≥-4-1 +

С3,1=10≥3+7 + (*)

С3,2=9≥7+6 -

Вывод: так как не для всех пустых клеток выполняется требование, план, представленный в транспортной схеме 1 неоптимален. Его можно улучшить

Шаг 3.

«Плохая клетка» С3,1. Строим замкнутый маршрут.

Шаг 4.

Построение нового плана перевозок с намеченными на шаге 3 изменениями. Новый план занесем в транспортную схему 2.

Таблица 2.3 Транспортная схема 2

Итерация 2.

Шаг 1.

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

560 0 0 0 0

0 150 50 0 0

Х2= 0 0 30 100 190

Z2=3*560+2*0+2*150+2*50+13*30+11*100+0*190=3570

Шаг 2.

Проверим полученный план на оптимальность.

С1,2=6≥2+0 +

С1,4=3≥0+0 +

С1,5=0≥-11+0 +

С2,1=5≥0+3 +

С2,4=6≥0+0 +

С2,5=0≥-11+0 +

С3,1=10≥3+11 - (*)

С3,2=9≥2+11 -

Вывод: так как не для всех пустых клеток выполняется требование, план, представленный в транспортной схеме 2 неоптимален. Его можно улучшить.

Шаг 3.

Выполним процесс улучшения плана. «Плохая клетка» С3,1. Строим замкнутый маршрут.

Шаг 4.

Построение нового плана перевозок с намеченными на шаге 3 изменениями. Новый план занесем в транспортную схему 3.

Таблица 2.4 Транспортная схема 3.

Итерация 3.

Шаг 1.

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

530 0 30 0 0

X₃= 0 150 50 0 0

30 0 0 100 190

Z3=3*530+2*30+2*150+0*190+2*50+10*30+11*100 =3450

Шаг 2.

Проверим полученный план на оптимальность.

С1,2=6≥2+0 +

С1,4=3≥0+4 + (*)

С1,5=0≥-7+0 +

С2,1=5≥0+3 +

С2,4=6≥4+0 +

С2,5=0≥-7+0 -

С3,2=9≥2+7 +

С3,3=13≥7+2 +

Вывод: так как не для всех пустых клеток выполняется требование, план, представленный в транспортной схеме 3 неоптимален. Его можно улучшить.

Шаг 3.

Выполним процесс улучшения плана. «Плохая клетка» С1,4. Строим замкнутый маршрут.

Шаг 4.

Построение нового плана перевозок с намеченными на шаге 3 изменениями. Новый план занесем в транспортную схему 4.

Итерация 4.

Шаг 1.

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

430 0 30 100 0

X₄= 0 150 50 0 0

130 0 0 0 190

Z4=3*430+2*30+2*150+3*100+2*50+10*130+0*190=3350

Шаг 2.

Проверим полученный план на оптимальность.

С1,2=2≥2+0 +

С1,5=0≥0-7 +

С2,1=5≥3+0 +

С2,4=6≥0+3 +

С2,5=0≥-7+0 +

С3,2=9≥7+2 +

С3,3=13≥2+7 +

С3,4=11≥7+3 +

План в транспортной схеме 4 оптимальный, т.к для всех пустых клеток выполняется требование (*).

Не нашли, что искали? Воспользуйтесь поиском: