Учебная работа. Транспортная задача
Транспортная задача
Транспортная задача
Вар 3
Никита Пазенко
151516151519211712243019619591975246131929222157
Потребителей 5, Поставщиков 4
Проверим ТЗ на замкнутость: .
, т.е. задача замкнутого типа.
Решением ТЗ будет служить минимальное значение целевой функции и значения xij
B1=15B2=15B3=16B4=15B5=15UA1=1921 1517 — 412 +2430U1=0A2=196 1 + 119 — 859U2=-16A3=197524 86 1113U3= -1A4=192922215 47 15U4= -2VV1=21V2=17V3=25V4=7V5=91 = 21*15+4*17+11+72+24*8+66+20+7*15=315+68+11++72+192+86+105=849
Итерация 1
u1= 0
v1= 21
v2= 17
v3=25
u2= — 16
v4= 7
u3= — 1
u4= — 2
Проверим план на оптимальность.
признак оптимальности:sij= cij -(ui+vj) ≥ 0 opt, для всех i, j.
S13= -13= 17= 21= 1= 14= 16= 27= — 11= 5= 1042= 7
S43= — 2
План не оптимален. наиболее потенциальной является клетка (1,3). Для нее «невязка» равна -13. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (1,3), построим граф и запишем цикл.
-23-22-12
+ — + —
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (1, 2) с грузом 4.
Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15B2=15B3=16B4=15B5=15UA1=1921 — 151712 + 42430U1=0A2=1961 159 459U2=-3A3=197 +524 — 86 1113U3=12A4=192922215 47 15U4=11VV1=21V2=4V3=12V4= -6V5=-4L2=315+48+15+36+192+66+20+105=797
Итерация 2
u1= 0
v1= 21
v2= 4
v3=12
u2= — 3
v4= — 6
u3= 12
u4= 11
Проверим план на оптимальность.
Определим значения оценок sij= cij — (ui+vj) ≥ 0 для всех свободных клеток:
S12= 13= 30= 34= -12= 14= 16= — 27= — 11= 5= -342= 7
S43= -2
План не оптимален. наиболее потенциальной является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (3,1), построим граф и запишем цикл.
-11-13-33
+ — + —
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (3,3) с грузом 8.
Перемещаем по циклу груз величиной в 8 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15B2=15B3=16B4=15B5=15UA1=1921 — 717 12+ 122430U1=0A2=196 1 159- 45 +9U2= -3A3=197 + 85246 — 1113U3=-14A4=192922215 47 15U4=- 15VV1=21V2=4V3=12V4= 20V5=22=147+144+15+36+56+66+20+105=589
Итерация 3= 0= 21= 4=12= -3= 20= — 14= — 15
Проверим план на оптимальность.
признак оптимальности: sij= cij -(ui+vj) ≥ 0 opt, для всех i, j.
Определим значения оценок sij= cij — (ui+vj) ≥ 0 для всех свободных клеток:
S12= 13= 4= 8=- 12= — 12= — 10= 15= 26=5= 23
S42= 33= 24
План не оптимален. наиболее потенциальной является клетка (2,4). Для нее «невязка» равна -12. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (2,4), построим граф и запишем цикл.
+ — + — + —
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (2,3) с грузом 4.
Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15B2=15B3=16B4=15B5=15UA1=1921 317 12 162430U1=0A2=196 1 159 5 49U2= — 15A3=197 125246 713U3=- 14A4=192922215 47 15U4=- 15VV1=21V2=16V3=12V4=20V5= 22транспортный задача перевозка цикл
L4=63+192+15+20+84+42+20+105=541
Итерация 3
u1= 0
v1= 21
v2=16
v3=12
u2= — 15
v4= 20
u3= — 14
u4= — 15
v5= 22
Проверим план на оптимальность.
признак оптимальности:sij= cij -(ui+vj) ≥ 0 opt, для всех i, j.
Определим значения оценок sij= cij — (ui+vj) ≥ 0 для всех свободных клеток:
S12= 1= 4= 8= 0= 12= 2= 3= 26= 5=23= 21= 24
Ответ: L=541=3=1622=15
X31=12
X34=7
X44=4
X45=15