Методы решения задач транспортного типа

 

Найдём  строку с min суммой грузов, заполненных ячеек. Это будет 4 строка => u₄=0 => v₄=4, v₅=3.

Вычисляем u и v по формуле: 
 

V₅ = 27

V₄ = 4

V₃ = 3

V₂ = 13 - u₃ = 13 - (-1) = 14

V₁ = 22 - u₂ = 22 - 4 = 18

u₄ = 0

u₃ = 2 - V₃ = 2 – 3 = -1

u₂ = 18 - V₂ = 18 – 14 = 4

u₁ = 12 - V₁ = 12 – 18 = -6 

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

9 ≥ 18-1 = 17 – не верно

26 ≥  18+0 = 26 – верно

11 ≥  14-6 = 8 – верно

21 ≥  14+0 = 14 – верно

25 ≥  3-6 = -3 – верно

14 ≥  3+4 = 7 – верно

17 ≥  4-6 = -2 – верно

8 ≥  4+4 = 8 – верно

28 ≥  4-1 = 3 – верно

21 ≥  27-6 = 21 – верно

1 ≥ 27+4 = 31 – не верно

15 ≥ 27-1 = 26 – не верно 

Таблица 6.

 

Перенесём 12 из ячейки с₂₂ в ячейку с₄₂, а из ячейки с₄₅ перенесём 12 в ячейку с₂₅. Найдём строку с max числом заполненных ячеек. Это будет 4 строка => u₄=0 => v₁=48, v₂=21, v₄=4.

Вычисляем u и v по формуле: 
 

V₅ = 27

V₄ = 4

V₃ = 3

V₂ = 21

V₁ = 22 - u₂ = 22 - (-26) = 48

u₄ = 0

u₃ = 2 - V₃ = 2 -3 = -1

u₂ = 1 - V₅ = 1 – 27 = -26

u₁ = 12 - V₁ = 12 – 48 = -36

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

9 ≥ 48-1 = 47 – не верно

26 ≥ 48+0 = 48 – не верно

11 ≥  21-36 = -15 – верно

18 ≥ 21-26 = -5 – верно

25 ≥  3-36 = -33 – верно

14 ≥  3-26 = -23 – верно

17 ≥  4-36 = -32 – верно

8 ≥  4-26 = -22 – верно

28 ≥  4-1 = 3 – верно

21 ≥  27-36 = -9 – верно

15 ≥ 27-1 = 26 – не верно

Таблица 7.

 

Перенесём 11 из ячейки с₁₁ в ячейку с₃₁, и 11 из ячейки с₃₃ в ячейку с₁₃.

Найдём  строку с min суммой грузов, заполненных ячеек. Это будет 4 строка => u₄=0 => v₃=3, v₄=4, v₅=3.

Вычисляем u и v по формуле: 
 

V₅ = 27

V₄ = 4

V₃ = 3

V₂ = 21

V₁ = 22 - u₂ = 22 - (-26) = 48

u₄ = 0

u₃ = 13 - V₂ = 13 – 21 = -8

u₂ = 1 - V₅ = 1 – 27 = -26

u₁ = 12 - V₁ = 12 – 48 = -36 

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

26 ≥ 48-0 = 48 – не верно

11 ≥ 21-36 = -15 – верно

18 ≥  21-26 = -5 – верно

14 ≥  3-26 = -23 – верно

2 ≥  3-8 = -5 - верно

17 ≥  4-5 = -1 – верно

8 ≥  4-26 = -22 – верно

28 ≥  4-8 = -4 – верно

21 ≥ 27-36 = -9 – верно

15 ≥ 27-8 = 21 – не верно 

Таблица 8.

 

Перенесём 2 из ячейки с3₁ в ячейку с₄₁, и 2 из ячейки с₄₅ в ячейку с₃₅.

Найдём  строку с min суммой грузов, заполненных ячеек. Это будет 4 строка => u₄=0 => v₁=26, v₂=21, v₃=3.

Вычисляем u и v по формуле: 
 

V₅ = 1 - u₂ = 1- (-4) = 5

V₄ = 4

V₃ = 3

V₂ = 21

V₁ = 26

u₄ = 0

u₃ = 9 – V₁ = 9 – 26 = -17

u₂ = 22 – V₁ = 22 - 26 = -4

u₁ = 12 - V₁ = 12 - 26 = -14

 

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

11 ≥  21-14 = 7 – верно

18 ≥  21-4 = 17 – верно

14 ≥  3-4 = -1 – верно

2 ≥  3-17 = -5 - верно

17 ≥  4-14 = -10 – верно

8 ≥  4-4 = 0 – верно

28 ≥  4-17 = -5 – верно

21 ≥  5-14 = -9 – верно

27 ≥  5+0 = 5 - верно 

W_пот. = 6∙12+11∙25+2∙22+12∙1+9∙9+10∙13+2∙15+2∙26+12∙21+12∙3+17∙4 = 1052 

    1.2.5. Венгерский метод. 

В каждой строке выбираем минимальный элемент. 
 
 

Таблица 9.

 

В каждой строке обнуляем минимальный элемент. По зануленным ячейкам выставляем максимально  возможное количество единиц груза.

Таблица 10.

 

Q_1min= {5, 17, 19, 41}

Обнуляем  стоимость, которая и в строке и в столбце будет минимальной, и отмечаем ее красным цветом.

Таблица 11.