1)Определить сбалансированность задачи. 2) Найти начальное опорное решение методом минимальной стоимости. 3) Найти оптимальное решение, используя

1)Определить сбалансированность задачи. 2) Найти начальное опорное решение методом минимальной стоимости. 3) Найти оптимальное решение, используя метод потенциалов. Решить следующую транспортную задачу: 21) аі

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 ден ед