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

Проверим условие разрешимости задачи.
A=i=1mai=25+25+25+25=100
B=j=1nbj=10+10+10+35+35=100
Условие баланса соблюдается. Следовательно, модель исходной транспортной задачи является замкнутой.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Поставщики Потребители запасы
1 2 3 4 5
1 10 18 12 8
25 13 25
2 17 2
10 18 13 7
15 25
3 4
10 3 1
10 6
5 12 25
4 12 16 8 14
5 15
20 25
Потребность потребителей 10 10 10 35 35
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 =8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
FX0=8∙25+2∙10+7∙15+4∙10+1∙10+6∙5+14∙5+15∙20=775
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β4=8
α2+β2=2; α2+β5=7
α3+β1=4; α3+β3=1; α3+β4=6
α4+β4=14; α4+β5=15
Проверим оптимальность опорного плана . Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=-2; α3=-2; α4=6;
β1=6; β2=4; β3=3; β4=8; β5=9.
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=10-0-6=4; ∆12=18-0-4=14; ∆13=12-0-3=9; ∆15=13-0-9=4
∆21=17+2-6=13; ∆23=18+2-3=17; ∆24=13+2-8=7
∆32=3+2-4=1; ∆35=12+2-9=5
∆41=12-6-6=0; ∆42=16-6-4=6; ∆43=8-6-3=-1
Опорный план не является оптимальным, так как существует отрицательная оценка свободной клетки: ∆43=-1.
Для этого в клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Поставщики Потребители запасы
1 2 3 4 5
1 10 18 12 8
25 13 25
2 17 2
10 18 13 7
15 25
3 4
10 3 - 1
10 + 6
5 12 25
4 12 16 + 8 - 14
5 15
20 25
Потребность потребителей 10 10 10 35 35
Цикл приведен в таблице 4,3→4,4→3,4→3,3.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках