отличающимся значениями величин х23, х24, х33 и х34 (подчеркнутые равны нулю).

Чтобы лучше понять основную идею, стоит рассмотреть следующий улучшающий шаг. Добавив к набору звеньев А\Вг9 А2ВЪ А2ВА, А4В4, АВЬ (рис. 14) звено А{В5, получаем цикл

(1, 5) -> (4, 5) -> (4, 4) -> (2, 4) -> (2, 2) -> (1, 2) -> (1, 5),

самый дешевый маршрут в котором А{В$ не используется (соответствующая клетка свободна), а все остальные задействованы (соответствующие клетки базисные). В таблице 5 стоимости соответствующих перевозок подчеркнуты. Беря, как и раньше, стоимости перевозки единицы груза в нечетных клетках со знаком +, а в четных со знаком -, получим

4 -14+ 9- 5 + 7- 6 = 20-25 = -5

и в соответствии с этим переместим наименьший из грузов в четных клетках в клетку (1, 5) по маршруту АХВ5. Сравнивая грузы 23,18 и 15, получаем, что перемещаемый груз должен быть равен 15 (таблица 6).

Рис. 14

Таблица б

На рисунках 15 иД 6 показано, как именно изменяются маршруты. Общая сумма перевозки станет равной

1255 -75= 1180.

®

®

Рис. 15

Рис. 16

Таким образом, отыскивая в таблице (и/или на соответствующем рисунке) свободные клетки (незадействованные маршруты), ищем цикл с отрицательной ценой и перебрасываем по нему наибольшее возможное количество единиц груза, уменьшая тем самым общую стоимость перевозок.

Поступая так, мы рано или поздно придем к оптимальной схеме перевозок.

На рисунках 17-37 и в таблицах 6-13 показаны шаги, завершающие решение рассматриваемой задачи.

Обратимся к таблице 6. Перебрасывая по циклу

(в таблице 6 стоимости соответствующих перевозок подчеркнуты) наибольшее возможное количество единиц груза (8), уменьшаем общую стоимость перевозок на 9 8 = 72,

(4, 1) -> (1, 1) -> (1, 5) -> (4, 5) -> (4, 1)

с отрицательной ценой

13 - 12 + 4 - 14 = -9

1180-72 = 1108

Рис. 17 Рис. 18 Рис. 19

Таблица 7

Перебрасывая по циклу

(1, 4) -> (4, 4) -> (4, 1) -> (1, 1) -> (1, 4) с отрицательной ценой

6 - 12 + 13 - 9 = -2

(в таблице 7 стоимости соответствующих перевозок подчеркнуты) наибольшее возможное количество единиц груза (9), уменьшаем общую стоимость перевозок на 2 9 = 18,

1108- 18 = 1090