Решить транспортную задачу методом потенциалов

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 Запасы
A1 6 7 5 15
A2 5 6 4 8
A3 9 10 6 20
Потребности 16 20 35
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 15 + 8 + 20 = 43∑b = 16 + 20 + 35 = 71
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 28 (71-43). Тарифы перевозки единицы груза из базы ко всем потребителям полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 Запасы
A1 6 7 5 15
A2 5 6 4 8
A3 9 10 6 20
A4 0 0 0 28
Потребности 16 20 35
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=6. Для этого элемента запасы равны 15, потребности 16. Поскольку минимальным является 15, то вычитаем его.x11 = min(15,16) = 15.
6 x x 15 - 15 = 0
5 6 4 8
9 10 6 20
0 0 0 28
16 - 15 = 1 20 35
Искомый элемент равен c21=5. Для этого элемента запасы равны 8, потребности 1. Поскольку минимальным является 1, то вычитаем его.x21 = min(8,1) = 1.
6 x x 0
5 6 4 8 - 1 = 7
x 10 6 20
x 0 0 28
1 - 1 = 0 20 35
Искомый элемент равен c22=6. Для этого элемента запасы равны 7, потребности 20. Поскольку минимальным является 7, то вычитаем его.x22 = min(7,20) = 7.
6 x x 0
5 6 x 7 - 7 = 0
x 10 6 20
x 0 0 28
0 20 - 7 = 13 35
Искомый элемент равен c32=10. Для этого элемента запасы равны 20, потребности 13. Поскольку минимальным является 13, то вычитаем его.x32 = min(20,13) = 13.
6 x x 0
5 6 x 0
x 10 6 20 - 13 = 7
x x 0 28
0 13 - 13 = 0 35
Искомый элемент равен c33=6. Для этого элемента запасы равны 7, потребности 35. Поскольку минимальным является 7, то вычитаем его.x33 = min(7,35) = 7.
6 x x 0
5 6 x 0
x 10 6 7 - 7 = 0
x x 0 28
0 0 35 - 7 = 28
Искомый элемент равен c43=0 . Для этого элемента запасы равны 28, потребности 28. Поскольку минимальным является 28, то вычитаем его.x43 = min(28,28) = 28.
6 x x 0
5 6 x 0
x 10 6 0
x x 0 28 - 28 = 0
0 0 28 - 28 = 0
В результате получен первый опорный план, который является допустимым, так как все грузы из швейных фабрик вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 Запасы
A1 6[15] 7 5 15
A2 5[1] 6[7] 4 8
A3 9 10[13] 6[7] 20
A4 0 0 0[28] 28
Потребности 16 20 35
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 6∙15 + 5∙1 + 6∙7 + 10∙13 + 6∙7 + 0∙28 = 309.
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 6; 0 + v1 = 6; v1 = 6u2 + v1 = 5; 6 + u2 = 5; u2 = -1u2 + v2 = 6; -1 + v2 = 6; v2 = 7u3 + v2 = 10; 7 + u3 = 10; u3 = 3u3 + v3 = 6; 3 + v3 = 6; v3 = 3u4 + v3 = 0; 3 + u4 = 0; u4 = -3
v1=6 v2=7 v3=3
u1=0 6[15] 7 5
u2=-1 5[1] 6[7] 4
u3=3 9 10[13] 6[7]
u4=-3 0 0 0[28]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(4;1): -3 + 6 > 0; ∆41 = -3 + 6 - 0 = 3 > 0
(4;2): -3 + 7 > 0; ∆42 = -3 + 7 - 0 = 4 > 0
max(3,4) = 4
Выбираем максимальную оценку свободной клетки (4;2): 0
Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 Запасы
1 6[15] 7 5 15
2 5[1] 6[7] 4 8
3 9 10[13][-] 6[7][+] 20
4 0 0[+] 0[28][-] 28
Потребности 16 20 35
Цикл приведен в таблице (4,2 → 4,3 → 3,3 → 3,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е