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

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

Никита Пазенко

Потребителей 5, Поставщиков 4

Проверим ТЗ на замкнутость: .

т. е. задача замкнутого типа.

Решением ТЗ будет служить минимальное значение целевой функции и значения xij

L1 = 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.

Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:

S13= -13

S14= 17

S15= 21

S21= 1

S24= 14

S25= 16

S31= 27

S32= - 11

S35= 5

S41= 10

S42= 7

S43= - 2

План не оптимален. Наиболее потенциальной является клетка (1,3). Для нее «невязка» равна -13. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.

Введем перевозку (1,3), построим граф и запишем цикл.

13−23−22−12

+ - + ;

Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (1, 2) с грузом 4.

Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.

Итерация 2

u1= 0

v1= 21

v2= 4

v3=12

u2= - 3

v4= - 6

u3= 12

u4= 11

Проверим план на оптимальность.

Признак оптимальности: sij= cij -(ui+vj)? 0 opt, для всех i, j.

Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:

S12= 13

S14= 30

S15= 34

S21= -12

S24= 14

S25= 16

S31= - 27

S32= - 11

S35= 5

S41= -3

S42= 7

S43= -2

План не оптимален. Наиболее потенциальной является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.

Введем перевозку (3,1), построим граф и запишем цикл.

31−11−13−33

+ - + ;

Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (3,3) с грузом 8.

Перемещаем по циклу груз величиной в 8 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.

L3=147+144+15+36+56+66+20+105=589

Итерация 3

u1= 0

v1= 21

v2= 4

v3=12

u2= -3

v4= 20

u3= - 14

u4= - 15

Проверим план на оптимальность.

Признак оптимальности: sij= cij -(ui+vj)? 0 opt, для всех i, j.

Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:

S12= 13

S14= 4

S15= 8

S21=- 12

S24= - 12

S25= - 10

S32= 15

S33= 26

S35=5

S41= 23

S42= 33

S43= 24

План не оптимален. Наиболее потенциальной является клетка (2,4). Для нее «невязка» равна -12. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.

Введем перевозку (2,4), построим граф и запишем цикл.

24−34−31−11−13−23

+ - + - + ;

Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (2,3) с грузом 4.

Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.

транспортный задача перевозка цикл

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

S14= 4

S15= 8

S21= 0

S23= 12

S25= 2

S32= 3

S33= 26

S35= 5

S41=23

S42= 21

S43= 24

Ответ: L=541

X11=3

X13=16

X22=15

X24=4

X31=12

X34=7

X44=4

X45=15