Дано: Потребители Вj поставщики Ai 70 50 70 60 4 3 1 40 2 1 4 90 2 4 8 Составить

Дано: Потребители Вj поставщики Ai 70 50 70 60 4 3 1 40 2 1 4 90 2 4 8 Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной.

I=1nai=j=1mbj⇒ задача закрытого типа.
Опорный план должен содержать 3+3-1=5 заполненных клеток.
Составим первый план транспортной задачи методом северо-западного угла. Заполнение клеток таблицы начнем с новой верхней клетки.
B1 B2 B3
A1 4
60 3
1 60
A2 2
10 1
30 4
40
A3 2 4
20 8
70 90
70 50 70 190
X1=60001030002070
S1=60∙4+10∙2+30∙1+20∙4+70∙8=240+20+30+80+560=930
Попробуем составить первый план методом минимальной стоимости. Будем стараться заполнить клетки с минимальными тарифами
B1 B2 B3
A1 4
3
1
60 60
[0]
A2 2
1
40 4
40
[0]
A3 2
70 4
8
90
[20]
70
[0] 50
[10] 70
[10] 190
Опорный план имеет следующий вид:
X=00600400701010
При этом плане стоимость перевозок вычисляется так:
S=60∙1+40∙1+70∙2+10∙4+10∙8=60+40+140+40+80=360
Стоимость при таком плане перевозок почти в два с половиной раза меньше.
Начнем решение задачи с этого плана

. Проверим его на оптимальность. Введем потенциалы αi – соответственно отправления, βj – соответственно назначения. По занятым клеткам составляем систему уравнений αi + βj=cij
β3-α1=1β2-α2=1β1-α3=2β2-α3=4β3-α3=8
Полагая α1=0, находим
β3-α1=1, α1=0β2-α2=1, β3=1β1-α3=2, β1=-5β2-α3=4, β2=-3β3-α3=8,α3=-7 α2=-4
α2=-4;α3=-7;β1=-5;β2=-3;β3=1
Для каждой свободной клетки вычисляем числоail=βj-αi-cij
a11=β1-α1-c11=-5-0-4=-9
a12=β2-α1-c12=-3-0-3=-6
a21=β1-α2-c21=-5--4-2=-3
a23=β3-α2-c23=1--4-4=1
Полученные числа заключаем в рамки и записываем их в соответствующие клетки таблицы:
B1 B2 B3
A1 4
-9 3
-6 1
60 60
A2 2
-3 1
40 4
1 40
A3 2
70 4
10 8
10 90
70 50 70 190
Среди чисел αij есть положительные. Следовательно, данный опорный план не является оптимальным. Наибольшее положительное число 1 находится в пересечении строки A2 и столбца B3