Учебная работа. Транспортная задача

Транспортная задача

Транспортная задача

Вар 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

Учебная работа. Транспортная задача