Проверяем необходимое и достаточное условие разрешимости задачи

Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 Запасы
A1 19 20 17 25 28 60
A2 27 33 24 18 23 100
A3 22 24 26 21 25 55
A4 0 0 0 0 0 15
Потребности 50 60 45 35 40
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Отыскиваемый элемент равен c13=17. Для этого элемента запасы равны 60, потребности 45. Т.к. минимальным является 45, то вычитаем его.x13 = min(60,45) = 45.
19 20 17 25 28 60 - 45 = 15
27 33 x 18 23 100
22 24 x 21 25 55
0 0 x 0 0 15
50 60 45 - 45 = 0 35 40
Отыскиваемый элемент равен c24=18. Для этого элемента запасы равны 100, потребности 35. Т.к. минимальным является 35, то вычитаем его.x24 = min(100,35) = 35.
19 20 17 x 28 15
27 33 x 18 23 100 - 35 = 65
22 24 x x 25 55
0 0 x x 0 15
50 60 0 35 - 35 = 0 40
Отыскиваемый элемент равен c11=19. Для этого элемента запасы равны 15, потребности 50. Т.к. минимальным является 15, то вычитаем его.x11 = min(15,50) = 15.
19 x 17 x x 15 - 15 = 0
27 33 x 18 23 65
22 24 x x 25 55
0 0 x x 0 15
50 - 15 = 35 60 0 0 40
Отыскиваемый элемент равен c31=22. Для этого элемента запасы равны 55, потребности 35. Т.к. минимальным является 35, то вычитаем его.x31 = min(55,35) = 35.
19 x 17 x x 0
x 33 x 18 23 65
22 24 x x 25 55 - 35 = 20
x 0 x x 0 15
35 - 35 = 0 60 0 0 40
Отыскиваемый элемент равен c25=23 . Для этого элемента запасы равны 65, потребности 40. Т.к. минимальным является 40, то вычитаем его.x25 = min(65,40) = 40.
19 x 17 x x 0
x 33 x 18 23 65 - 40 = 25
22 24 x x x 20
x 0 x x x 15
0 60 0 0 40 - 40 = 0
Отыскиваемый элемент равен c32=24. Для этого элемента запасы равны 20, потребности 60. Т.к. минимальным является 20, то вычитаем его.x32 = min(20,60) = 20.
19 x 17 x x 0
x 33 x 18 23 25
22 24 x x x 20 - 20 = 0
x 0 x x x 15
0 60 - 20 = 40 0 0 0
Отыскиваемый элемент равен c22=33. Для этого элемента запасы равны 25, потребности 40. Т.к. минимальным является 25, то вычитаем его.x22 = min(25,40) = 25.
19 x 17 x x 0
x 33 x 18 23 25 - 25 = 0
22 24 x x x 0
x 0 x x x 15
0 40 - 25 = 15 0 0 0
Отыскиваемый элемент равен c42=0. Для этого элемента запасы равны 15, потребности 15. Т.к. минимальным является 15, то вычитаем его.x42 = min(15,15) = 15.
19 x 17 x x 0
x 33 x 18 23 0
22 24 x x x 0
x 0 x x x 15 - 15 = 0
0 15 - 15 = 0 0 0 0
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 19[15] 20 17[45] 25 28 60
A2 27 33[25] 24 18[35] 23[40] 100
A3 22[35] 24[20] 26 21 25 55
A4 0 0[15] 0 0 0 15
Потребности 50 60 45 35 40
Значение целевой функции для этого опорного плана равно:F(x) = 19∙15 + 17∙45 + 33∙25 + 18∙35 + 23∙40 + 22∙35 + 24∙20 + 0∙15 = 4675
Проверяем оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 19; 0 + v1 = 19; v1 = 19u3 + v1 = 22; 19 + u3 = 22; u3 = 3u3 + v2 = 24; 3 + v2 = 24; v2 = 21u2 + v2 = 33; 21 + u2 = 33; u2 = 12u2 + v4 = 18; 12 + v4 = 18; v4 = 6u2 + v5 = 23; 12 + v5 = 23; v5 = 11u4 + v2 = 0; 21 + u4 = 0; u4 = -21u1 + v3 = 17; 0 + v3 = 17; v3 = 17
v1=19 v2=21 v3=17 v4=6 v5=11
u1=0 19[15] 20 17[45] 25 28
u2=12 27 33[25] 24 18[35] 23[40]
u3=3 22[35] 24[20] 26 21 25
u4=-21 0 0[15] 0 0 0
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 21 > 20; ∆12 = 0 + 21 - 20 = 1 > 0(2;1): 12 + 19 > 27; ∆21 = 12 + 19 - 27 = 4 > 0(2;3): 12 + 17 > 24; ∆23 = 12 + 17 - 24 = 5 > 0max(1,4,5) = 5
Выбираем максимальную оценку свободной клетки (2;3): 24
Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 19[15][+] 20 17[45][-] 25 28 60
2 27 33[25][-] 24[+] 18[35] 23[40] 100
3 22[35][-] 24[20][+] 26 21 25 55
4 0 0[15] 0 0 0 15
Потребности 50 60 45 35 40
Цикл приведен в таблице (2,3 → 2,2 → 3,2 → 3,1 → 1,1 → 1,3).
Из грузов хij которые стоят в минусовых клетках, выбираем наименьшее, т.е