На четырех базах Аi находиться однородный груз

Проверим необходимое и достаточное условие разрешимости задачи:
a=830+540+700+830=2900,b=700+970+600+440+690=3400a<b.
Суммарная потребность груза больше запасов груза у поставщиков. Следовательно, задача является открытой. Чтобы получить закрытую модель, введем фиктивного поставщика А5 с запасом, равным 3400-2900=500. Тарифы перевозки единицы груза от поставщика всем потребителям положим равными нулю.
Запасы фиктивного поставщика будем рассматривать в последний момент.
Пункты отправления Пункты назначения Запасы груза

9 10 5 3 6 830
8 4 1 5 9 540
9 3 6 7 1 700
1 8 3 9 5 830
0 0 0 0 0 500
Потребности 700 970 600 440 690
Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 1. Запасы поставщика A2 составляют540 ед. Потребность потребителя B3 составляет 600 ед. От поставщика A2 к потребителю B3 будем доставлять 540 ед. Мы полностью исчерпали запасы поставщика А2. Вычеркиваем строку 2 таблицы, т.е. исключаем ее из дальнейшего рассмотрения . Продолжаем аналогичные рассуждения и получим опорное решение
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
 
 
390
10
 
 
440
3
 
 
a2= 540
 
 
 
 
540
1
 
 
 
 
a3= 700
 
 
10
3
 
 
 
 
690
1
a4= 830
200
1
570
8
60
3
 
 
 
 
a5= 500
500
0
 
 
 
 
 
 
 
 
Значение целевой функции для данного опорного плана равно:
F(Х) = 390*10+440*3+540*1+10*3+690*1+200*1+570*8+60*3=11420 ден ед
Число занятых клеток таблицы равно 10, их должно быть m + n - 1 = 10 . Значит, опорный план является невырожденным.
Проведем поэтапное улучшение начального решения, используя метод потенциалов.Ui+Vj=Pij
b1
b2
b3
b4
b5
a1
  10   3   u1= 8
a2
    1     u2= 4
a3
  3     1 u3= 1
a4
1 8 3     u4= 6
a5
0         u5= 5
v1= -5
v2= 2
v3= -3
v4= -5
v5= 0
Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj 
b1
b2
b3
b4
b5
a1
6 10 0 3 -2 u1= 8
a2
9 -2 1 6 5 u2= 4
a3
13 3 8 11 1 u3= 1
a4
1 8 3 8 -1 u4= 6
a5
0 -7 -2 0 -5 u5= 5
v1= -5
v2= 2
v3= -3
v4= -5
v5= 0
Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю (
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
 
 
390
 
 
 
440
 
 
 
a2= 540
 
 
 
 
540
 
 
 
 
 
a3= 700
 
 
10
 
 
 
 
 
690
 
a4= 830
200
+
570
-
60
 
 
 
 
 
a5= 500
500
-
 
+
 
 
 
 
 
 
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
  390   440  
a2= 540
    540    
a3= 700
  10     690
a4= 830
700 70 60    
a5= 500
  500      
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
6 10 0 3 -2 u1= 8
a2
9 -2 1 6 5 u2= 4
a3
13 3 8 11 1 u3= 1
a4
1 8 3 8 -1 u4= 6
a5
7 0 5 7 2 u5= -2
v1= -5
v2= 2
v3= -3
v4= -5
v5= 0
Ячейка а1,b5, транспортной таблицы, должна загрузиться.
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
 
 
390
-
 
 
440
 
 
+
a2= 540
 
 
 
 
540
 
 
 
 
 
a3= 700
 
 
10
+
 
 
 
 
690
-
a4= 830
700
 
70
 
60
 
 
 
 
 
a5= 500
 
 
500
 
 
 
 
 
 
 
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
      440 390
a2= 540
    540    
a3= 700
  400     300
a4= 830
700 70 60    
a5= 500
  500      
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
8 2 2 3 6 u1= 6
a2
9 -2 1 4 5 u2= 4
a3
13 3 8 9 1 u3= 1
a4
1 8 3 6 -1 u4= 6
a5
7 0 5 5 2 u5= -2
v1= -5
v2= 2
v3= -3
v4= -3
v5= 0
Ячейка а2,b2, транспортной таблицы, должна загрузиться.
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
 
 
 
 
 
 
440
 
390
 
a2= 540
 
 
 
+
540
-
 
 
 
 
a3= 700
 
 
400
 
 
 
 
 
300
 
a4= 830
700
 
70
-
60
+
 
 
 
 
a5= 500
 
 
500
 
 
 
 
 
 
 
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
      440 390
a2= 540
  70 470    
a3= 700
  400     300
a4= 830
700   130    
a5= 500
  500      
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
b5
a1
6 2 0 3 6 u1= 6
a2
9 4 1 6 7 u2= 2
a3
11 3 6 9 1 u3= 1
a4
1 2 3 8 1 u4= 4
a5
5 0 3 5 2 u5= -2
v1= -3
v2= 2
v3= -1
v4= -3
v5= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
b1= 700
b2= 970
b3= 600
b4= 440
b5= 690
a1= 830
 
 
 
 
 
 
440
3
390
6
a2= 540
 
 
70
4
470
1
 
 
 
 
a3= 700
 
 
400
3
 
 
 
 
300
1
a4= 830
700
1
 
 
130
3
 
 
 
 
a5= 500
 
 
500
0
 
 
 
 
 
 
Таким образом, оптимальный план перевозок груза:
Минимальные общие затраты на перевозку грузов составят:
F(x)min = 440*3+390*6+70*4+470+400*3+300*1+700*1+130*3+500*0=7000
Ответ