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

Задача является сбалансированной:
40+35+15+25+35=30+5+45+70.
Транспортная таблица для данной задачи имеет вид:
B1
B2
B3
B4
B5
ai
A1
3
x11
7
x12
1
x13
5
x14
4
x15
30
A2
7
x21
5
x22
8
x23
6
x24
3
x25
5
A3
6
x31
4
x32
8
x33
3
x34
2
x35
45
A4
3
x41
1
x42
7
x43
4
x44
2
x45
70
bj
40 35 15 25 35
Найдем начальное допустимое решение с помощью метода минимального элемента:
B1
B2
B3
B4
B5
ai
Ui
A1
3
15
7
0
1
15
5
0
4
0
30 0
A2
7
0
5
0
8
0
6
5
3
0
5 2
A3
6
0
4
0
8
0
3
10
2
35
45 -1
A4
3
25
1
35
7
0
4
10
2
0
70 0
bj
40 35 15 25 35
Vj
3 1 1 4 3
Вычислим суммарную стоимость перевозок по данному плану:
C=3∙15+1∙15+6∙5+3∙10+2∙35+3∙25+1∙35+4∙10=340;
Проверяем опорный план на оптимальность. Для этого вычислим потенциалы строк ui и потенциалы столбцов vi.
Эти числа определяются из условий:
ui+vi=cij,
где cij- стоимость (цена) заполненных клеток, причем принимаем u1=0.
Запишем результаты вычислений в таблицу.
Оценки пустых клеток находим по формулам: ∆ij=ui+vi-cij
∆12=0+1-7=-6, ∆14=0+4-5=-1, ∆15=0+3-4=-1,
∆21=2+3-7=-2, ∆22=2+1-5=-2, ∆23=2+1-8=-5,
∆25=2+3-3=2,γ31=-1+3-6=-4,
γ32=-1+1-4=-4, γ33=-1+1-8=-8,
γ43=0+1-7=-6,γ45=0+3-2=1.
Поскольку ∆25=2>0 и γ45=1>0, то рассматриваемое решение не является оптимальным.
Строим для клетки (2,5) цепь, находим ∆=min(5,35)=3.
47371019812000492760188595006
5 - 4057651866903
0 +
3
10 + -269875188595002
35 -
Вносим изменения в транспортную таблицу и проверяем новое решение на оптимальность:
B1
B2
B3
B4
B5
ai
Ui
A1
3
15
7
0
1
15
5
0
4
0
30 0
A2
7
0
5
0
8
0
6
0
3
5
5 0
A3
6
0
4
0
8
0
3
15
2
30
45 -1
A4
3
25
1
35
7
0
4
10
2
0
70 0
bj
40 35 15 25 35
Vj
3 1 1 4 3
Вычислим суммарную стоимость перевозок по данному плану:
C=3∙15+1∙15+3∙5+3∙15+2∙30+3∙25+1∙35+4∙10=330;
Проверяем опорный план на оптимальность