Кружки – пункты потребления.

 

Схема 1. Первоначальный план перевозки

Исходя из первого условия критерия оптимальности, а именно: a_js – a_is = C_s для X_s > 0 определяем систему оценочных чисел (потенциалов).

Пусть а_А = 100 (первый потенциал задаём произвольно), тогда следуя по сети участков где осуществляются перевозки, определяем оценочные числа для других пунктов (если перевозки (стрелки) совпадают с направлением движения – суммируем затраты по перевозке на участке, если направлены против движения – вычитаем), таким образом получим:

а_Е = 100 + 25 = 125

а_L = 100 + 28 = 128

a_F = 128 – 30 = 98

a_K = 98 + 30 = 128

a_D = 98 + 60 = 158

a_C = 158 – 100 = 58

a_B = 58 + 80 = 138

Проверяем выполнение второго условия критерия оптимальности, а именно: a_js – a_is ≤ C_s для участков, на которых не осуществляется перевозка.

a_B – a_A = 138 – 100 = 38 < 60

a_D – a_A = 158 – 100 = 58 < 60

a_K – a_C =128 – 58 = 70 > 50

Из проверки видно, что на участке КС не выполнено второе условие критерия оптимальности (70 > 50). Следовательно, по участку СК нужно осуществлять перевозку.

Для того, чтобы определить, какое количество груза следует везти из пункта С в пункт К, нужно:

во-первых, построить кольцо, связывающее пункты, между которыми есть связь перевозок (кольцо включает один свободный участок с нарушением, а остальные участки обязательно должны быть заняты) - это кольцо пройдёт по участкам СК, KF, FD, DC;

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

Наименьшим количеством грузов, перевозимым на указанных участках будет 45 ед. (участок DC). Снимаем это количество груза с участка СD и направляем его по участку СК.

Чтобы сохранился баланс перевозок – эти 45 ед. снимаем с участков кольца, по которым грузопоток идёт в противоположном кольцу направлению, и добавляем к участкам кольца, по которым грузопоток идёт в направлении кольца.

Таким образом, мы приходим к плану (схема 2).