Расчёт оптимального плана возврата порожняка. Решение транспортной задачи начинается с разработки допустимого исходного плана, который разрабатывается в табличной форме. В матрицу условий (таблица 4) вводится дополнительный столбец и строка.

В строке записываются значения индексов Vj, а в столбце - значения индексов Ui. Для дальнейших расчётов необходимо определить количество автомобиле-ездок, их находим по формуле:

Ze= Q/ q* g, где Q - объём перевозок;

q - грузоподъёмность автомобиля (т);

g - коэффициент использования грузоподъёмности.

Значения q и g возьмём из таблицы 3. Результаты вычисления занесём в таблицу 4.

Ze (А1Б1) =126/5*0,9=28

Ze (А1Б7) =126/5*0,9=28

Ze (А1Б8) =27/5*0,9=6

Ze (А2Б2) =81/5*0,9=18

Ze (А3Б5) =81/5*0,9=18

Ze (А4Б3) =72/5*0,9=16

Ze (А4Б4) =108/5*0,9=24

Ze (А5Б1) =81/5*0,9=18

Ze (А5Б3) =72/5*0,9=16

Ze (А6Б5) =72/5*0,9=16

Ze (А6Б6) =108/5*0,9=24

Таблица 4

Расчёт ездок от объёма перевозки грузов (в тоннах)

В правом верхнем углу клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами; условие S bj= S аi = 212 (ездки) выполняется. Таблица 5.

Таблица 5

Допустимый исходный план

План разрабатывается методом минимального элемента.

i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей X_i,j - перевозка между поставщиком A_i и потребителем B_j.

D_i,j - ограничение между поставщиком A_i и потребителем B_j.

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.

Находим опорный план для задачи с ограничениями.

Введем некоторые обозначения:

A_i^* - излишек нераспределенного груза от поставщика A_i B_j^* - недостача в поставке груза потребителю B_j

Находим незанятую клетку с минимальным расстоянием: (1,2).

Помещаем туда меньшее из чисел A₁^*=62, B₂^*=18 Находим незанятую клетку с минимальным расстоянием: (2,6).

Помещаем туда меньшее из чисел A₂^*=18, B₆^*=24 Находим незанятую клетку с минимальным расстоянием: (5,5).

Помещаем туда меньшее из чисел A₅^*=34, B₅^*=34 Находим незанятую клетку с минимальным расстоянием: (1,6).

Помещаем туда меньшее из чисел A₁^*=44, B₆^*=6 Находим незанятую клетку с минимальным расстоянием: (6,8).

Помещаем туда меньшее из чисел A₆^*=40, B₈^*=6 Находим незанятую клетку с минимальным расстоянием: (6,1).

Помещаем туда меньшее из чисел A₆^*=34, B₁^*=46 Находим незанятую клетку с минимальным расстоянием: (1,1).

Помещаем туда меньшее из чисел A₁^*=38, B₁^*=12 Находим незанятую клетку с минимальным расстоянием: (1,3).

Помещаем туда меньшее из чисел A₁^*=26, B₃^*=32 Находим незанятую клетку с минимальным расстоянием: (3,7).

Помещаем туда меньшее из чисел A₃^*=18, B₇^*=28 Находим незанятую клетку с минимальным расстоянием: (4,3).

Помещаем туда меньшее из чисел A₄^*=40, B₃^*=6 Находим незанятую клетку с минимальным расстоянием: (4,4).

Помещаем туда меньшее из чисел A₄^*=34, B₄^*=24 Находим незанятую клетку с минимальным расстоянием: (4,7).

Помещаем туда меньшее из чисел A₄^*=10, B₇^*=10

Транспортная работа будет равна

Р=12*5+18*1+26*7+18*1+18*12+6*15+24*15+15*10+34*1+34*3+6*2=1254 т. км

Опорный план является вырожденным, так как число занятых клеток, удовлетворяющих условию 0 < X_i,j < D_i,j меньше, чем m+n-1=13.

Перечислим эти клетки: (1,1) (1,2) (1,3) (1,6) (2,6) (3,7) (4,3) (4,4) (4,7) (5,5) (6,1) (6,8)

Сделаем план невырожденным, добавляя (в случае X_i,j = 0) или отнимая (в случае X_i,j = D_i,j) бесконечно малые, не равные между собой фиктивные перевозки 0 в клетки с координатами (i,j): (5,2) Введение в план фиктивных перевозок необходимо для избежания зацикливания в ходе решения задачи. При их введении будем модифицировать потребности/запасы груза соответствующих потребителей/поставщиков для сохранения баланса между запасами/потребностями.

Таблица 6

Опорный план

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i: U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 V₆=C_1,6-U₁= 2 U₆=C_1,6-V₁= - 2 U₅=C_2,5-V₂= 0 U₄=C_3,4-V₃= 8 U₂=C_6,2-V₆= - 1 V₄=C_4,4-U₄= 7 V₇=C_4,7-U₄= 7 V₅=C_5,5-U₅= 1 V₈=C_6,8-U₆= 4 U₃=C_7,3-V₇= 5

Определяем потенциальные клетки. Находим такие незагруженные клетки в матрице, для которых сумма индексов была бы меньше указанного расстояния (такие клетки называются потенциальными).

Определяем значения оценок S_i,j=C_i,j- (V_j-U_i) для всех свободных клеток.

Клетки с отрицательными значениями будут потенциальными. Если имеются неоптимальные оценки и для случая X_i,j = 0, и для случая X_i,j = D_i,j, то наиболее потенциальной (неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (4,6). Для нее оценка равна - 5. Таблица 7.

S_1,4 = c_1,4 - (v₄ + u₁) = 1. S_1,5 = c_1,5 - (v₅ + u₁) = 3. S_1,7 = c_1,7 - (v₇ + u₁) = 7.

S_1,8 = c_1,8 - (v₈ + u₁) = 11. S_2,1 = c_2,1 - (v₁ + u₂) = 1. S_2,2 = c_2,2 - (v₂ + u₂) = 13.

S_2,3 = c_2,3 - (v₃ + u₂) = 2. S_2,4 = c_2,4 - (v₄ + u₂) = 0. S_2,5 = c_2,5 - (v₅ + u₂) = 3.

S_2,7 = c_2,7 - (v₇ + u₂) = 1. S_2,8 = c_2,8 - (v₈ + u₂) = 0. S_3,1 = c_3,1 - (v₁ + u₃) = 2.

S_3,2 = c_3,2 - (v₂ + u₃) = - 2. S_3,3 = c_3,3 - (v₃ + u₃) = 2. S_3,4 = c_3,4 - (v₄ + u₃) = 1.

S_3,5 = c_3,5 - (v₅ + u₃) = 5. S_3,6 = c_3,6 - (v₆ + u₃) = - 3. S_3,8 = c_3,8 - (v₈ + u₃) = 1.

S_4,1 = c_4,1 - (v₁ + u₄) = 3. S_4,2 = c_4,2 - (v₂ + u₄) = - 2. S_4,5 = c_4,5 - (v₅ + u₄) = 4.

S_4,6 = c_4,6 - (v₆ + u₄) = - 5. S_4,8 = c_4,8 - (v₈ + u₄) = 0. S_5,1 = c_5,1 - (v₁ + u₅) = 4.

S_5,3 = c_5,3 - (v₃ + u₅) = 6. S_5,4 = c_5,4 - (v₄ + u₅) = - 1. S_5,6 = c_5,6 - (v₆ + u₅) = - 1.

S_5,7 = c_5,7 - (v₇ + u₅) = - 3. S_5,8 = c_5,8 - (v₈ + u₅) = - 3. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,4 = c_6,4 - (v₄ + u₆) = - 2.

S_6,5 = c_6,5 - (v₅ + u₆) = 9. S_6,6 = c_6,6 - (v₆ + u₆) = 10. S_6,7 = c_6,7 - (v₇ + u₆) = - 2.

Таблица 7

Нахождение потенциальных клеток

Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу груз величиной в 6 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 8.

Таблица 8

Опорный план

Транспортная работа будет равна

Р=12*5+18*1+32*7+6*2+18*1+18*12+6*15+24*15+6*5+10*15+34*1+34*3+6*2=1224т. км

Опорный план является вырожденным, так как число занятых клеток, удовлетворяющих условию 0 < X_i,j < D_i,j меньше, чем m+n-1=13.

Перечислим эти клетки: (1,1) (1,2) (1,3) (2,6) (3,7) (4,4) (4,6) (4,7) (5,2) (5,5) (6,1) (6,8) Сделаем план невырожденным, добавляя (в случае X_i,j = 0) или отнимая (в случае X_i,j = D_i,j) бесконечно малые, не равные между собой фиктивные перевозки в клетки с координатами (i,j): (5,6). Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки. Потенциалы U_i:

U₁=0,V₁=C_1,1-U₁= 5, V₂=C_1,2-U₁= 1, V₃=C_1,3-U₁= 7, U₆=C_1,6-V₁= - 2,U₅=C_2,5-V₂= 0V₅=C_5,5-U₅= 1, V₆=C_5,6-U₅= 1, V₈=C_6,8-U₆= 4, U₂=C_6,2-V₆= 0, U₄=C_6,4-V₆= 4, V₄=C_4,4-U₄= 11, V₇=C_4,7-U₄= 11, U₃=C_7,3-V₇= 1.

S_1,4 = c_1,4 - (v₄ + u₁) = - 3. S_1,5 = c_1,5 - (v₅ + u₁) = 3. S_1,6 = c_1,6 - (v₆ + u₁) = 1.

S_1,7 = c_1,7 - (v₇ + u₁) = 3. S_1,8 = c_1,8 - (v₈ + u₁) = 11. S_2,1 = c_2,1 - (v₁ + u₂) = 0.

S_2,2 = c_2,2 - (v₂ + u₂) = 12. S_2,3 = c_2,3 - (v₃ + u₂) = 1. S_2,4 = c_2,4 - (v₄ + u₂) = - 5.

S_2,5 = c_2,5 - (v₅ + u₂) = 2. S_2,7 = c_2,7 - (v₇ + u₂) = - 4. S_2,8 = c_2,8 - (v₈ + u₂) = - 1.

S_3,1 = c_3,1 - (v₁ + u₃) = 6. S_3,2 = c_3,2 - (v₂ + u₃) = 2. S_3,3 = c_3,3 - (v₃ + u₃) = 6.

S_3,4 = c_3,4 - (v₄ + u₃) = 1. S_3,5 = c_3,5 - (v₅ + u₃) = 9. S_3,6 = c_3,6 - (v₆ + u₃) = 2.

S_3,8 = c_3,8 - (v₈ + u₃) = 5. S_4,1 = c_4,1 - (v₁ + u₄) = 7. S_4,2 = c_4,2 - (v₂ + u₄) = 2.

S_4,3 = c_4,3 - (v₃ + u₄) = 4. S_4,5 = c_4,5 - (v₅ + u₄) = 8. S_4,8 = c_4,8 - (v₈ + u₄) = 4.

S_5,1 = c_5,1 - (v₁ + u₅) = 4. S_5,3 = c_5,3 - (v₃ + u₅) = 6. S_5,4 = c_5,4 - (v₄ + u₅) = - 5.

S_5,7 = c_5,7 - (v₇ + u₅) = - 7. S_5,8 = c_5,8 - (v₈ + u₅) = - 3. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,4 = c_6,4 - (v₄ + u₆) = - 6. S_6,5 = c_6,5 - (v₅ + u₆) = 9.

S_6,6 = c_6,6 - (v₆ + u₆) = 11. S_6,7 = c_6,7 - (v₇ + u₆) = - 6.

Таблица 9

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (5,7). Для нее оценка равна - 7. Таблица 9. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу фиктивную загрузку груз величиной в 0 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

Таблица 10

Опорный план

Транспортная работа будет равна:

Р=1224т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 U₆=C_1,6-V₁= - 2 U₅=C_2,5-V₂= 0 V₅=C_5,5-U₅= 1 V₇=C_5,7-U₅= 4V₈=C_6,8-U₆= 4 U₃=C_7,3-V₇= 8 U₄=C_7,4-V₇= 11 V₄=C_4,4-U₄= 4 V₆=C_4,6-U₄= - 6 U₂=C_6,2-V₆= 7

S_1,4 = c_1,4 - (v₄ + u₁) = 4. S_1,5 = c_1,5 - (v₅ + u₁) = 3. S_1,6 = c_1,6 - (v₆ + u₁) = 8.

S_1,7 = c_1,7 - (v₇ + u₁) = 10. S_1,8 = c_1,8 - (v₈ + u₁) = 11. S_2,1 = c_2,1 - (v₁ + u₂) = - 7.

S_2,2 = c_2,2 - (v₂ + u₂) = 5. S_2,3 = c_2,3 - (v₃ + u₂) = - 6. S_2,4 = c_2,4 - (v₄ + u₂) = - 5.

S_2,5 = c_2,5 - (v₅ + u₂) = - 5. S_2,7 = c_2,7 - (v₇ + u₂) = - 4. S_2,8 = c_2,8 - (v₈ + u₂) = - 8.

S_3,1 = c_3,1 - (v₁ + u₃) = - 1. S_3,2 = c_3,2 - (v₂ + u₃) = - 5. S_3,3 = c_3,3 - (v₃ + u₃) = - 1.

S_3,4 = c_3,4 - (v₄ + u₃) = 1. S_3,5 = c_3,5 - (v₅ + u₃) = 2. S_3,6 = c_3,6 - (v₆ + u₃) = 2.

S_3,8 = c_3,8 - (v₈ + u₃) = - 2. S_4,1 = c_4,1 - (v₁ + u₄) = 0. S_4,2 = c_4,2 - (v₂ + u₄) = - 5.

S_4,3 = c_4,3 - (v₃ + u₄) = - 3. S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = - 3.

S_5,1 = c_5,1 - (v₁ + u₅) = 4. S_5,3 = c_5,3 - (v₃ + u₅) = 6. S_5,4 = c_5,4 - (v₄ + u₅) = 2.

S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = - 3. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,4 = c_6,4 - (v₄ + u₆) = 1. S_6,5 = c_6,5 - (v₅ + u₆) = 9.

S_6,6 = c_6,6 - (v₆ + u₆) = 18. S_6,7 = c_6,7 - (v₇ + u₆) = 1.

Таблица 11

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (2,8). Для нее оценка равна - 8. Таблица 11. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу фиктивную загрузку груз величиной в 0 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 12.

Таблица 12

Опорный план

Транспортная работа будет равна:

Р=1224т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 U₆=C_1,6-V₁= - 2 V₈=C_6,8-U₆= 4 U₂=C_8,2-V₈= - 1 V₆=C_2,6-U₂= 2 U₄=C_6,4-V₆= 3 V₄=C_4,4-U₄= 12 V₇=C_4,7-U₄= 12 U₃=C_7,3-V₇= 0 U₅=C_7,5-V₇= - 8 V₅=C_5,5-U₅= 9

S_1,4 = c_1,4 - (v₄ + u₁) = - 4. S_1,5 = c_1,5 - (v₅ + u₁) = - 5. S_1,6 = c_1,6 - (v₆ + u₁) = 0.

S_1,7 = c_1,7 - (v₇ + u₁) = 2. S_1,8 = c_1,8 - (v₈ + u₁) = 11. S_2,1 = c_2,1 - (v₁ + u₂) = 1.

S_2,2 = c_2,2 - (v₂ + u₂) = 13. S_2,3 = c_2,3 - (v₃ + u₂) = 2. S_2,4 = c_2,4 - (v₄ + u₂) = - 5.

S_2,5 = c_2,5 - (v₅ + u₂) = - 5. S_2,7 = c_2,7 - (v₇ + u₂) = - 4. S_3,1 = c_3,1 - (v₁ + u₃) = 7.

S_3,2 = c_3,2 - (v₂ + u₃) = 3. S_3,3 = c_3,3 - (v₃ + u₃) = 7. S_3,4 = c_3,4 - (v₄ + u₃) = 1.

S_3,5 = c_3,5 - (v₅ + u₃) = 2. S_3,6 = c_3,6 - (v₆ + u₃) = 2. S_3,8 = c_3,8 - (v₈ + u₃) = 6.

S_4,1 = c_4,1 - (v₁ + u₄) = 8. S_4,2 = c_4,2 - (v₂ + u₄) = 3. S_4,3 = c_4,3 - (v₃ + u₄) = 5.

S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = 5. S_5,1 = c_5,1 - (v₁ + u₅) = 12.

S_5,2 = c_5,2 - (v₂ + u₅) = 8. S_5,3 = c_5,3 - (v₃ + u₅) = 14. S_5,4 = c_5,4 - (v₄ + u₅) = 2.

S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = 5. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,4 = c_6,4 - (v₄ + u₆) = - 7. S_6,5 = c_6,5 - (v₅ + u₆) = 1.

S_6,6 = c_6,6 - (v₆ + u₆) = 10. S_6,7 = c_6,7 - (v₇ + u₆) = - 7.

Таблица 13

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (6,4). Для нее оценка равна - 7. Таблица 13. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 6 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 14.

Таблица 14

Опорный план

Транспортная работа будет равна:

Р=1182т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки. Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 U₆=C_1,6-V₁= - 2 V₄=C_6,4-U₆= 5 U₄=C_4,4-V₄= 10 V₆=C_4,6-U₄= - 5 V₇=C_4,7-U₄= 5 U₂=C_6,2-V₆= 6 U₃=C_7,3-V₇= 7 U₅=C_7,5-V₇= - 1 V₈=C_2,8-U₂= - 3 V₅=C_5,5-U₅= 2

S_1,4 = c_1,4 - (v₄ + u₁) = 3. S_1,5 = c_1,5 - (v₅ + u₁) = 2. S_1,6 = c_1,6 - (v₆ + u₁) = 7.

S_1,7 = c_1,7 - (v₇ + u₁) = 9. S_1,8 = c_1,8 - (v₈ + u₁) = 18. S_2,1 = c_2,1 - (v₁ + u₂) = - 6.

S_2,2 = c_2,2 - (v₂ + u₂) = 6. S_2,3 = c_2,3 - (v₃ + u₂) = - 5. S_2,4 = c_2,4 - (v₄ + u₂) = - 5.

S_2,5 = c_2,5 - (v₅ + u₂) = - 5. S_2,7 = c_2,7 - (v₇ + u₂) = - 4. S_3,1 = c_3,1 - (v₁ + u₃) = 0. S_3,2 = c_3,2 - (v₂ + u₃) = - 4. S_3,3 = c_3,3 - (v₃ + u₃) = 0. S_3,4 = c_3,4 - (v₄ + u₃) = 1.

S_3,5 = c_3,5 - (v₅ + u₃) = 2. S_3,6 = c_3,6 - (v₆ + u₃) = 2. S_3,8 = c_3,8 - (v₈ + u₃) = 6.

S_4,1 = c_4,1 - (v₁ + u₄) = 1. S_4,2 = c_4,2 - (v₂ + u₄) = - 4. S_4,3 = c_4,3 - (v₃ + u₄) = - 2.

S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = 5. S_5,1 = c_5,1 - (v₁ + u₅) = 5.

S_5,2 = c_5,2 - (v₂ + u₅) = 1. S_5,3 = c_5,3 - (v₃ + u₅) = 7. S_5,4 = c_5,4 - (v₄ + u₅) = 2.

S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = 5. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,5 = c_6,5 - (v₅ + u₆) = 8. S_6,6 = c_6,6 - (v₆ + u₆) = 17.

S_6,7 = c_6,7 - (v₇ + u₆) = 0. S_6,8 = c_6,8 - (v₈ + u₆) = 7.

Таблица 15

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (2,1). Для нее оценка равна - 6. Таблица 15. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу груз величиной в 12 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 16.

Таблица 16

Опорный план

Транспортная работа будет равна:

Р=1110т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 U₂=C_1,2-V₁= 0 U₆=C_1,6-V₁= - 2 V₈=C_2,8-U₂= 3 V₄=C_6,4-U₆= 5 U₄=C_4,4-V₄= 10 V₆=C_4,6-U₄= - 5 V₇=C_4,7-U₄= 5 U₃=C_7,3-V₇= 7 U₅=C_7,5-V₇= - 1 V₅=C_5,5-U₅= 2

S_1,4 = c_1,4 - (v₄ + u₁) = 3. S_1,5 = c_1,5 - (v₅ + u₁) = 2. S_1,6 = c_1,6 - (v₆ + u₁) = 7.

S_1,7 = c_1,7 - (v₇ + u₁) = 9. S_1,8 = c_1,8 - (v₈ + u₁) = 12. S_2,2 = c_2,2 - (v₂ + u₂) = 12.

S_2,3 = c_2,3 - (v₃ + u₂) = 1. S_2,4 = c_2,4 - (v₄ + u₂) = 1. S_2,5 = c_2,5 - (v₅ + u₂) = 1.

S_2,6 = c_2,6 - (v₆ + u₂) = 6. S_2,7 = c_2,7 - (v₇ + u₂) = 2. S_3,1 = c_3,1 - (v₁ + u₃) = 0.

S_3,2 = c_3,2 - (v₂ + u₃) = - 4. S_3,3 = c_3,3 - (v₃ + u₃) = 0. S_3,4 = c_3,4 - (v₄ + u₃) = 1.

S_3,5 = c_3,5 - (v₅ + u₃) = 2. S_3,6 = c_3,6 - (v₆ + u₃) = 2. S_3,8 = c_3,8 - (v₈ + u₃) = 0.

S_4,1 = c_4,1 - (v₁ + u₄) = 1. S_4,2 = c_4,2 - (v₂ + u₄) = - 4. S_4,3 = c_4,3 - (v₃ + u₄) = - 2.

S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = - 1. S_5,1 = c_5,1 - (v₁ + u₅) = 5.

S_5,2 = c_5,2 - (v₂ + u₅) = 1. S_5,3 = c_5,3 - (v₃ + u₅) = 7. S_5,4 = c_5,4 - (v₄ + u₅) = 2.

S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = - 1. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,5 = c_6,5 - (v₅ + u₆) = 8. S_6,6 = c_6,6 - (v₆ + u₆) = 17.

S_6,7 = c_6,7 - (v₇ + u₆) = 0. S_6,8 = c_6,8 - (v₈ + u₆) = 1.

Таблица 17

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (3,2). Для нее оценка равна - 4. Таблица 17. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу груз величиной в 6 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 18.

Таблица 18

Опорный план

Транспортная работа будет равна:

Р=1086т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 U₂=C_1,2-V₁= 0 U₆=C_1,6-V₁= - 2 U₃=C_2,3-V₂= 3 V₈=C_2,8-U₂= 3 V₇=C_3,7-U₃= 9 V₄=C_6,4-U₆= 5 U₄=C_7,4-V₇= 6 U₅=C_7,5-V₇= - 5 V₆=C_4,6-U₄= - 1 V₅=C_5,5-U₅= 6

S_1,4 = c_1,4 - (v₄ + u₁) = 3. S_1,5 = c_1,5 - (v₅ + u₁) = - 2. S_1,6 = c_1,6 - (v₆ + u₁) = 3.

S_1,7 = c_1,7 - (v₇ + u₁) = 5. S_1,8 = c_1,8 - (v₈ + u₁) = 12. S_2,2 = c_2,2 - (v₂ + u₂) = 12.

S_2,3 = c_2,3 - (v₃ + u₂) = 1. S_2,4 = c_2,4 - (v₄ + u₂) = 1. S_2,5 = c_2,5 - (v₅ + u₂) = - 3.

S_2,6 = c_2,6 - (v₆ + u₂) = 2. S_2,7 = c_2,7 - (v₇ + u₂) = - 2. S_3,1 = c_3,1 - (v₁ + u₃) = 4.

S_3,3 = c_3,3 - (v₃ + u₃) = 4. S_3,4 = c_3,4 - (v₄ + u₃) = 5. S_3,5 = c_3,5 - (v₅ + u₃) = 2.

S_3,6 = c_3,6 - (v₆ + u₃) = 2. S_3,8 = c_3,8 - (v₈ + u₃) = 4. S_4,1 = c_4,1 - (v₁ + u₄) = 5.

S_4,2 = c_4,2 - (v₂ + u₄) = 0. S_4,3 = c_4,3 - (v₃ + u₄) = 2. S_4,4 = c_4,4 - (v₄ + u₄) = 4.

S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = 3. S_5,1 = c_5,1 - (v₁ + u₅) = 9.

S_5,2 = c_5,2 - (v₂ + u₅) = 5. S_5,3 = c_5,3 - (v₃ + u₅) = 11. S_5,4 = c_5,4 - (v₄ + u₅) = 6.

S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = 3. S_6,2 = c_6,2 - (v₂ + u₆) = 2.

S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,5 = c_6,5 - (v₅ + u₆) = 4. S_6,6 = c_6,6 - (v₆ + u₆) = 13.

S_6,7 = c_6,7 - (v₇ + u₆) = - 4. S_6,8 = c_6,8 - (v₈ + u₆) = 1.

Таблица 19

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (6,7). Для нее оценка равна - 4. Таблица 19. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу груз величиной в 12 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 20.

Таблица 20

Опорный план

Транспортная работа будет равна:

Р=1038т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₂=C_1,2-U₁= 1 V₃=C_1,3-U₁= 7 U₂=C_1,2-V₁= 0 U₆=C_1,6-V₁= - 2 U₃=C_2,3-V₂= 3 V₈=C_2,8-U₂= 3 V₄=C_6,4-U₆= 5 V₇=C_6,7-U₆= 5 U₄=C_7,4-V₇= 10 U₅=C_7,5-V₇= - 1 V₆=C_4,6-U₄= - 5 V₅=C_5,5-U₅= 2

S_1,4 = c_1,4 - (v₄ + u₁) = 3. S_1,5 = c_1,5 - (v₅ + u₁) = 2. S_1,6 = c_1,6 - (v₆ + u₁) = 7.

S_1,7 = c_1,7 - (v₇ + u₁) = 9. S_1,8 = c_1,8 - (v₈ + u₁) = 12. S_2,2 = c_2,2 - (v₂ + u₂) = 12.

S_2,3 = c_2,3 - (v₃ + u₂) = 1. S_2,4 = c_2,4 - (v₄ + u₂) = 1. S_2,5 = c_2,5 - (v₅ + u₂) = 1.

S_2,6 = c_2,6 - (v₆ + u₂) = 6. S_2,7 = c_2,7 - (v₇ + u₂) = 2. S_3,1 = c_3,1 - (v₁ + u₃) = 4.

S_3,3 = c_3,3 - (v₃ + u₃) = 4. S_3,4 = c_3,4 - (v₄ + u₃) = 5. S_3,5 = c_3,5 - (v₅ + u₃) = 6.

S_3,6 = c_3,6 - (v₆ + u₃) = 6. S_3,7 = c_3,7 - (v₇ + u₃) = 4. S_3,8 = c_3,8 - (v₈ + u₃) = 4.

S_4,1 = c_4,1 - (v₁ + u₄) = 1. S_4,2 = c_4,2 - (v₂ + u₄) = - 4. S_4,3 = c_4,3 - (v₃ + u₄) = - 2.

S_4,4 = c_4,4 - (v₄ + u₄) = 0. S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = - 1.

S_5,1 = c_5,1 - (v₁ + u₅) = 5. S_5,2 = c_5,2 - (v₂ + u₅) = 1. S_5,3 = c_5,3 - (v₃ + u₅) = 7.

S_5,4 = c_5,4 - (v₄ + u₅) = 2. S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = - 1.

S_6,2 = c_6,2 - (v₂ + u₆) = 2. S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,5 = c_6,5 - (v₅ + u₆) = 8.

S_6,6 = c_6,6 - (v₆ + u₆) = 17. S_6,8 = c_6,8 - (v₈ + u₆) = 1.

Таблица 21

Нахождение потенциальных клеток

Транспортная работа будет равна:

Р=1038т. км Наиболее потенциальной является клетка (4,2). Для нее оценка равна - 4. Таблица 21. Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу груз величиной в 0 оборотов, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 22.

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Таблица 22

Опорный план

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₃=C_1,3-U₁= 7 U₂=C_1,2-V₁= 0 U₆=C_1,6-V₁= - 2 V₈=C_2,8-U₂= 3 V₄=C_6,4-U₆= 5 V₇=C_6,7-U₆= 5 U₄=C_7,4-V₇= 10 U₅=C_7,5-V₇= - 1 V₂=C_4,2-U₄= - 3 V₆=C_4,6-U₄= - 5 V₅=C_5,5-U₅= 2 U₃=C_2,3-V₂= 7

S_1,2 = c_1,2 - (v₂ + u₁) = 4. S_1,4 = c_1,4 - (v₄ + u₁) = 3. S_1,5 = c_1,5 - (v₅ + u₁) = 2.

S_1,6 = c_1,6 - (v₆ + u₁) = 7. S_1,7 = c_1,7 - (v₇ + u₁) = 9. S_1,8 = c_1,8 - (v₈ + u₁) = 12.

S_2,2 = c_2,2 - (v₂ + u₂) = 16. S_2,3 = c_2,3 - (v₃ + u₂) = 1. S_2,4 = c_2,4 - (v₄ + u₂) = 1.

S_2,5 = c_2,5 - (v₅ + u₂) = 1. S_2,6 = c_2,6 - (v₆ + u₂) = 6. S_2,7 = c_2,7 - (v₇ + u₂) = 2.

S_3,1 = c_3,1 - (v₁ + u₃) = 0. S_3,3 = c_3,3 - (v₃ + u₃) = 0. S_3,4 = c_3,4 - (v₄ + u₃) = 1.

S_3,5 = c_3,5 - (v₅ + u₃) = 2. S_3,6 = c_3,6 - (v₆ + u₃) = 2. S_3,7 = c_3,7 - (v₇ + u₃) = 0.

S_3,8 = c_3,8 - (v₈ + u₃) = 0. S_4,1 = c_4,1 - (v₁ + u₄) = 1. S_4,3 = c_4,3 - (v₃ + u₄) = - 2.

S_4,4 = c_4,4 - (v₄ + u₄) = 0. S_4,5 = c_4,5 - (v₅ + u₄) = 1. S_4,8 = c_4,8 - (v₈ + u₄) = - 1.

S_5,1 = c_5,1 - (v₁ + u₅) = 5. S_5,2 = c_5,2 - (v₂ + u₅) = 5. S_5,3 = c_5,3 - (v₃ + u₅) = 7.

S_5,4 = c_5,4 - (v₄ + u₅) = 2. S_5,6 = c_5,6 - (v₆ + u₅) = 7. S_5,8 = c_5,8 - (v₈ + u₅) = - 1.

S_6,2 = c_6,2 - (v₂ + u₆) = 6. S_6,3 = c_6,3 - (v₃ + u₆) = 0. S_6,5 = c_6,5 - (v₅ + u₆) = 8.

S_6,6 = c_6,6 - (v₆ + u₆) = 17. S_6,8 = c_6,8 - (v₈ + u₆) = 1.

Таблица 23

Нахождение потенциальных клеток

Наиболее потенциальной является клетка (4,3). Для нее оценка равна - 2. Таблица 23 Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус". Перемещаем по циклу груз величиной в 4 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план. Таблица 24.

Таблица 24

Опорный план

Транспортная работа будет равна:

Р=1030т. км Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_j+V_i=C_i,j (i=1. m, j=1. n), просматривая все занятые клетки.

Потенциалы U_i:

U₁=0 V₁=C_1,1-U₁= 5 V₃=C_1,3-U₁= 7 U₂=C_1,2-V₁= 0 U₄=C_3,4-V₃= 8 V₈=C_2,8-U₂= 3 V₂=C_4,2-U₄= - 1 V₆=C_4,6-U₄= - 3 V₇=C_4,7-U₄= 7 U₃=C_2,3-V₂= 5 U₅=C_7,5-V₇= - 3 U₆=C_7,6-V₇= - 4 V₅=C_5,5-U₅= 4 V₄=C_6,4-U₆= 7

S_1,2 = c_1,2 - (v₂ + u₁) = 2. S_1,4 = c_1,4 - (v₄ + u₁) = 1. S_1,5 = c_1,5 - (v₅ + u₁) = 0.

S_1,6 = c_1,6 - (v₆ + u₁) = 5. S_1,7 = c_1,7 - (v₇ + u₁) = 7. S_1,8 = c_1,8 - (v₈ + u₁) = 12.

S_2,2 = c_2,2 - (v₂ + u₂) = 14. S_2,3 = c_2,3 - (v₃ + u₂) = 1. S_2,4 = c_2,4 - (v₄ + u₂) = - 1.

S_2,5 = c_2,5 - (v₅ + u₂) = - 1. S_2,6 = c_2,6 - (v₆ + u₂) = 4. S_2,7 = c_2,7 - (v₇ + u₂) = 0.