Определить сбалансированность задачи. Найти начальное опорное решение методом минимальной стоимости

1) Проверим необходимое и достаточное условие разрешимости задачи:
a=40+30+50=120 b=20+18+44+75=157a<b.
Суммарная потребность груза больше запасов груза у поставщиков. Следовательно, задача является открытой. Чтобы получить закрытую модель, введем фиктивного поставщика А4 с запасом, равным 157-120=37. Тарифы перевозки единицы груза от поставщика всем потребителям положим равными нулю. Запасы фиктивного поставщика будем рассматривать в последний момент.
2) Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A4B1 и равен 0. Запасы поставщика A4 составляют 17 ед. Потребность потребителя B1 составляет 20 ед. От поставщика A4 к потребителю B1 будем доставлять 17 ед. Мы полностью исчерпали запасы поставщика А4. Вычеркиваем строку 4 таблицы, т.е. исключаем ее из дальнейшего рассмотрения. Продолжая данные рассуждения аналогичным образом получим опорное решение:
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
    40  
a2= 30
      30
a3= 50
  1 4 45
a4= 37
20 17    
Проверим полученный опорный план на невырожденность . Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=7, n+m=4+4=8 , что удовлетворяет условию невырожденности плана. 
Вычислим общие затраты на перевозку всей продукции.
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
 
 
 
 
40
2
 
 
a2= 30
 
 
 
 
 
 
30
1
a3= 50
 
 
1
3
4
5
45
3
a4= 37
20
0
17
0
 
 
 
 
Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения. 
Pнач= 268
3)Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат. Ui+Vj=Pij
b1
b2
b3
b4
a1
    2   u1= 0
a2
      1 u2= 1
a3
  3 5 3 u3= 3
a4
0 0     u4= 0
v1= 0
v2= 0
v3= 2
v4= 0
Порядок вычисления потенциалов был следующий:   1) Пусть V4 = 0 ;   2) U2 = P2,4 - V4 ;   3) U3 = P3,4 - V4 ;   4) V2 = P3,2 - U3 ;   5) V3 = P3,3 - U3 ;   6) U4 = P4,2 - V2 ;   7) U1 = P1,3 - V3 ;   8) V1 = P4,1 - U4 ;Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj 
b1
b2
b3
b4
a1
1 7 2 5 u1= 0
a2
2 7 1 1 u2= 1
a3
3 3 5 3 u3= 3
a4
0 0 -2 0 u4= 0
v1= 0
v2= 0
v3= 2
v4= 0
Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
 
 
 
 
40
 
 
 
a2= 30
 
 
 
 
 
 
30
 
a3= 50
 
 
1
+
4
-
45
 
a4= 37
20
 
17
-
 
+
 
 
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
    40  
a2= 30
      30
a3= 50
  5   45
a4= 37
20 13 4  
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
a1
-1 5 2 3 u1= 2
a2
2 7 3 1 u2= 1
a3
3 3 2 3 u3= 3
a4
0 0 0 0 u4= 0
v1= 0
v2= 0
v3= 0
v4= 0
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
 
+
 
 
40
-
 
 
a2= 30
 
 
 
 
 
 
30
 
a3= 50
 
 
5
 
 
 
45
 
a4= 37
20
-
13
 
4
+
 
 
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
20   20  
a2= 30
      30
a3= 50
  5   45
a4= 37
  13 24  
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
b1
b2
b3
b4
a1
1 5 2 3 u1= 2
a2
3 7 3 1 u2= 1
a3
4 3 2 3 u3= 3
a4
1 0 0 0 u4= 0
v1= -1
v2= 0
v3= 0
v4= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
b1= 20
b2= 18
b3= 44
b4= 75
a1= 40
20
1
 
 
20
2
 
 
a2= 30
 
 
 
 
 
 
30
1
a3= 50
 
 
5
3
 
 
45
3
a4= 37
 
 
13
0
24
0
 
 
Общие затраты на перевозку всей продукции, для оптимального плана составляют: 
Pопт= 240
Ответ:
Х=2002000003005045013240
Ххчч
Рmin = 240 ден ед