Имеются пять районов промысла и четыре порта назначения

Построим математическую модель представленной транспортной задачи.
Данные задачи занесем в таблицу:
Владивосток Холмск Петропавловск Находка Поставщики
П1 77 74 83 74 250
П2 65 68 71 65 210
П4 37 35 34 37 140
П3 80 82 87 80 130
П6 51 54 57 52 70
Потребители 170 190 210 180
Обозначим через хij – объём перевозки груза из i-го пункта отправления в j-й пункт назначения. Тогда общие затраты на перевозку грузов F(x) составят:
Проверим необходимое и достаточное условие разрешимости задачи:
a=250+210+140+130+70=800b=170+190+210+180=750a>b.
Суммарная потребность груза меньше запасов груза у поставщиков. Следовательно, задача является открытой. Чтобы получить закрытую модель, введем фиктивного потребителя с запасом, равным 800-750=50. Тарифы перевозки единицы груза от поставщика всем потребителям положим равными нулю. Запасы фиктивного потребителя будем рассматривать в последний момент.
Владивосток Холмск Петропавловск Находка потребитель Поставщики
П1 77 74 83 74 0 250
П2 65 68 71 65 0 210
П4 37 35 34 37 0 140
П3 80 82 87 80 0 130
П6 51 54 57 52 0 70
Потребители 170 190 210 180 50
Заданные количества запасов груза в пунктах отправления и потребности в пунктах назначения накладывают ограничения на значения перевозок груза xij.
а) Ограничения по запасам груза в пунктах отправления:
б) Ограничения по потребностям в пунктах назначения:
в) Объемы перевозимого груза не могут быть отрицательными:
.
Математическая модель представленной транспортной задачи составлена.
Найдем начальное решение методом минимального элемента . Минимальный элемент матрицы тарифов находится в ячейке (3,3) и равен 34. Запасы поставщика П4 составляют 140 ед. Потребность потребителя Петропавловск составляет 210 ед. От поставщика П4 к потребителю Петропавловск будем доставлять 140 ед. Мы полностью исчерпали запасы поставщика П4. Вычеркиваем строку 3 таблицы, т.е. исключаем ее из дальнейшего рассмотрения. Продолжаем аналогичные рассуждения и получим опорное решение:
Владивосток Холмск Петропавловск Находка потребитель
П1   190   10 50
П2 100     110  
П4     140    
П3     70 60  
П6 70        
Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=9, n+m=5+5=10 , что удовлетворяет условию невырожденности плана. 
Вычислим общие затраты на перевозку всей продукции.
Владивосток Холмск Петропавловск Находка потребитель
П1  
 
190
74
 
 
10
74
50
0
П2 100
65
 
 
 
 
110
65
 
 
П4  
 
 
 
140
34
 
 
 
 
П3  
 
 
 
70
87
60
80
 
 
П6 70
51
 
 
 
 
 
 
 
 
Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения. 
Pнач= 47670
Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат: Ui+Vj=PijПорядок вычисления потенциалов был следующий:   1) Пусть V5 = 0 ;   2) U1 = P1,5 - V5 ;   3) V2 = P1,2 - U1 ;   4) V4 = P1,4 - U1 ;   5) U2 = P2,4 - V4 ;   6) U4 = P4,4 - V4 ;   7) V1 = P2,1 - U2 ;   8) V3 = P4,3 - U4 ;   9) U5 = P5,1 - V1 ;   10) U3 = P3,3 - V3 ;
Владивосток Холмск Петропавловск Находка потребитель
П1   74   74 0 u1= 0
П2 65     65   u2= -9
П4     34     u3= -47
П3     87 80   u4= 6
П6 51         u5= -23
v1= 74
v2= 74
v3= 81
v4= 74
v5= 0
Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij = Pij – Ui - Vj .
Владивосток Холмск Петропавловск Находка потребитель
П1 3 74 2 74 0 u1= 0
П2 65 3 -1 65 9 u2= -9
П4 10 8 34 10 47 u3= -47
П3 0 2 87 80 -6 u4= 6
П6 51 3 -1 1 23 u5= -23
v1= 74
v2= 74
v3= 81
v4= 74
v5= 0
Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю.
Владивосток Холмск Петропавловск Находка потребитель
П1  
 
190
 
 
 
10
+
50
-
П2 100
 
 
 
 
 
110
 
 
 
П4  
 
 
 
140
 
 
 
 
 
П3  
 
 
 
70
 
60
-
 
+
П6 70
 
 
 
 
 
 
 
 
 
Владивосток Холмск Петропавловск Находка потребитель
П1   190   60  
П2 100     110  
П4     140    
П3     70 10 50
П6 70        
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
Владивосток Холмск Петропавловск Находка потребитель
П1 3 74 2 74 6 u1= -6
П2 65 3 -1 65 15 u2= -15
П4 10 8 34 10 53 u3= -53
П3 0 2 87 80 0 u4= 0
П6 51 3 -1 1 29 u5= -29
v1= 80
v2= 80
v3= 87
v4= 80
v5= 0
Ячейка (2,3), транспортной таблицы, должна загрузиться.
Владивосток Холмск Петропавловск Находка потребитель
П1  
 
190
 
 
 
60
 
 
 
П2 100
 
 
 
 
+
110
-
 
 
П4  
 
 
 
140
 
 
 
 
 
П3  
 
 
 
70
-
10
+
50
 
П6 70
 
 
 
 
 
 
 
 
 
Владивосток Холмск Петропавловск Находка потребитель
П1   190   60  
П2 100   70 40  
П4     140    
П3       80 50
П6 70        
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.
Владивосток Холмск Петропавловск Находка потребитель
П1 3 74 3 74 6 u1= -6
П2 65 3 71 65 15 u2= -15
П4 9 7 34 9 52 u3= -52
П3 0 2 1 80 0 u4= 0
П6 51 3 0 1 29 u5= -29
v1= 80
v2= 80
v3= 86
v4= 80
v5= 0
В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно достигнуто оптимальное решение.
Владивосток Холмск Петропавловск Находка потребитель
П1  
 
190
74
 
 
60
74
 
 
П2 100
65
 
 
70
71
40
65
 
 
П4  
 
 
 
140
34
 
 
 
 
П3  
 
 
 
 
 
80
80
50
0
П6 70
51
 
 
 
 
 
 
 
 
Общие затраты на перевозку всей продукции, для оптимального плана составляют: 
Pопт= 47300
Среди найденных оценок нет отрицательных, значит, найден оптимальный план.
Х*=0190060010007040000140000008050700000
Ххчч
Среди оценок есть нулевые, поэтому план не единственный:
Х**=0190060020070120000140008000050700000
Ропт =47300 ден ед
Среди оценок есть нулевые, поэтому план не единственный:
Х***=019006001700040000140000008050007000
Ропт =47300 ден ед
Ответ:
Общие затраты на доставку всей продукции составляют 47300 ден ед
Х*=0190060010007040000140000008050700000,Х**=0190060020070120000140008000050700000
Х***=019006001700040000140000008050007000