Найти решение транспортной задачи для заданных параметров

Найдем опорный план методом «северо-западного угла», методом наименьшей стоимости и методом Фогеля.
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
15 23 26 19 18 300
A2
18 30 35 25 40 350
A3
12 14 22 20 35 130
A4
10 28 23 19 30 70
Потребности 145 195 200 140 170
Проверим задачу на сбалансированность по следующей формуле:
i=1mai=j=1nbj.
В условии данной задачи m=4;n=5. Определим суммарный объем запасов и суммарный объем потребностей, сравним полученные результаты.
i=14ai=300+350+130+70=850 ед.
j=15bj=145+195+200+140+170=850 ед.
Задача является закрытой (сбалансированной).
метод «северо-западного угла»
Вписываем в ячейку 1,1 (самая северо-западная ячейка) наименьшее из значений a1 и b1 x11=min300;145=145 и исключаем из дальнейшего рассмотрения 1-й столбец. Вычеркнув 1-й столбец, корректируем запасы первого поставщика на величину x11=145, a1=300-145=155. Далее в ячейку (1,2) записываем наименьшее из значений a1 и b2 x12=min155;195=155 и исключаем из дальнейшего рассмотрения 1-ю строку. Потребности второго потребителя уменьшаются на величину x12=155, b2=195-155=40. С оставшейся матрицей поступаем аналогично.
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
15
145 23
155 26
19
18
300
A2
18
30
40 35
200 25
110 40
350
A3
12
14
22
20
30 35
100 130
A4
10
28
23
19
30
70 70
Потребности 145 195 200 140 170 850
ZXсев-зап0=15∙145+23∙155+30∙40+35∙200+25∙110+20∙30+35∙100+30∙70=22890 (усл.ед.).
метод наименьшей стоимости
Вписываем в ячейку 4,1 (имеет наименьший тариф 10) наименьшее из значений a4 и b1 x41=min70, 145=70 и исключаем из дальнейшего рассмотрения 4-ю строку. Вычеркнув 4-ю строку, корректируем потребности первого потребителя на величину x41=70, b1=145-70=75. Далее в ячейку (3,1) записываем наименьшее из значений a3 и b1 x31=min130, 75=75 и исключаем из дальнейшего рассмотрения 1-й столбец. Запасы третьего поставщика уменьшаются на величину x31=75, a3=130-75=55. С оставшейся матрицей поступаем аналогично.
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
15
23
26
19
130 18
170 300
A2
18
30
140 35
200 25
10 40
350
A3
12
75 14
55 22
20
35
130
A4
10
70 28
23
19
30
70
Потребности 145 195 200 140 170 850
ZXнаим . ст.0=19∙130+18∙170+30∙140+35∙200+25∙10+12∙75+14∙55+10∙70=19350 (усл.ед.).
метод Фогеля
Согласно алгоритму решения транспортной задачи с дополнительными ограничениями составим новую таблицу для построения начального плана методом Фогеля.
B1
B2
B3
B4
B5
Разности по
строкам
ai/bj
145 195 200 140 170
300 15
23
26
130 19
18
170 3 4 4 4 - - - -
350 18
75 30
65 35
70 25
140 40
7 7 7 7 7* 5* 5* 0
130 12
14
130 22
20
35
2 2 - - - - - -
70 10
70 28
23
19
30
9 9 9* - - - - -
Разности
по столбцам 2 9 1 0 12*
2 9* 1 0 -
2 5 1 0 -
3 7 9* 6 -
0 0 0 0 -
- 0 0 0 -
- 0 0 - -
- - 0* - -
Вычисляя разности между минимальным и следующим за ним тарифом в каждой строке и столбце (вычисления приведены в дополнительных строках и столбцах), последовательно заполняем
x15=170, столбец B5 исключаем из рассмотрения;
x32=130, строку A3 исключаем из рассмотрения;
x41=70, строку A4 исключаем из рассмотрения;
x13=130, строку A1 исключаем из рассмотрения;
x21=75, столбец B1 исключаем из рассмотрения;
x24=140, столбец B4 исключаем из рассмотрения;
x22=65, столбец B2 исключаем из рассмотрения;
x23=70, столбец B3 исключаем из рассмотрения.
Определим полную стоимость перевозок по найденному опорному плану:
ZXфогеля0=26∙130+18∙170+18∙75+30∙65+35∙70+25∙140+14∙130+10∙70=18210 (усл.ед.).
Наименьшие затраты дает план, найденный методом Фогеля. Проверим его на оптимальность методом потенциалов.
С помощью метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен ui, то vj=cij-ui, если известен vj, то ui=cij-vj. Положим, например, u1=0. Тогда будут вычислены и остальные потенциалы строк и столбцов.
u1=0;
v3=c13-u1=26-0=26;
v5=c15-u1=18-0=18;
u2=c23-v3=35-26=9;
v1=c21-u2=18-9=9;
v2=c22-u2=30-9=21;
v4=c24-u2=25-9=16;
u4=c41-v1=10-9=1;
u3=c32-v2=14-21=-7;
vj
ui v1=9
v2=21
v3=26
v4=16
v5=18
u1=0
15
23
26
130 19
18
170
u2=9
18 +
75 30
65 35 -
70 25
140 40
u3=-7
12
14
130 22
20
35
u4=1
10 -
70 28
23 +
19
30
Для незагруженных клеток вычислим величины превышения стоимости ∆ij=cij-ui-vj:
∆11=15-0-9=6; ∆12=23-0-21=2;
∆14=19-0-16=3; ∆25=40-9-18=13;
∆31=12--7-9=10; ∆33=22--7-26=3;
∆34=20--7-16=11; ∆35=35--7-18=24;
∆42=28-1-21=6;∆43=23-1-26=-4<0;
∆44=19-1-16=2;∆45=30-1-18=11.
Полученный план не оптимален