В примере задачи 7.3 у ребра (4, 6) наименьшая отрицательная характеристика (–3). Рисуем к нему стрелку от вершины с меньшим потенциалом (4) к вершине с большим потенциалом (6).
Образуется замкнутый контур из стрелок 4 – 6 – 7 – 5 – 4 (при этом неважно, двигаемся мы по стрелкам или против них). В этом контуре направление стрелок 7 → 6 и 4 → 5 противоположно направлению новой стрелки 4 → 6.
Определим минимум среди поставок для стрелок 7 → 6 и 4 → 5: min (30, 130) = 30.
Для контура 4 – 6 – 7 – 5 – 4 поставки на стрелках в направлении новой стрелки 4 → 6 (4 → 6 и 7 → 5) увеличим на этот минимум: 0 + 30 = 30 и 120 + 30 = 150 соответственно.
Поставки для стрелок вне контура остаются без изменений. Число стрелок равно 6 и равно число вершин минус 1. Получаем следующий план поставок. Исследуем его на оптимальность.
Припишем вершине 1 потенциал 0 и пересчитаем потенциалы других вершин.
У нас четыре ребра без стрелок: (1, 6), (2, 4), (3, 4), (4, 5). Найдем их характеристики.
Характеристика ребра (1, 6) = стоимость перевозки единицы груза для ребра (1,6) – больший потенциал вершин ребра (1, 6) + меньший потенциал вершин ребра (1, 6) = 4 – 6 + 0 = – 2 < 0.
Характеристика ребра (2, 4) = стоимость перевозки единицы груза для ребра (2, 4) – больший потенциал вершин ребра (2, 4) + меньший потенциал вершин ребра (2, 4) = 7 – 3 + 1 = 5.
Характеристика ребра (3, 4) = стоимость перевозки единицы груза для ребра (3, 4) – больший потенциал вершин ребра (3, 4) + меньший потенциал вершин ребра (3, 4) = 4 – 3 + 3 = 4.
Характеристика ребра (4, 5) = стоимость перевозки единицы груза для ребра (4, 5) – больший потенциал вершин ребра (4, 5) + меньший потенциал вершин ребра (4, 5) = 2 – 3 + 2 = 1.
Образуется замкнутый контур из стрелок 1 – 6 – 7 – 5 – 1 (при этом не важно, двигаемся мы по стрелкам или против них). В этом контуре направление стрелок 7 → 6 и 1 → 5 противоположно направлению новой стрелки 1 → 6.
Определим минимум среди поставок для стрелок 7 → 6 и 1 → 5: min (100, 0) = 0. Поэтому все поставки остаются без изменений. Стрелку 1 → 5 ликвидируем.
Число стрелок равно 6 и равно число вершин минус 1. Получаем следующий план поставок. Проверим его на оптимальность.
Убеждаемся, что нет ребер с отрицательными характеристиками, то есть это оптимальный план поставок.
Затраты на перевозку равны 120*1 + 70*3 + 0*4 + 30*3 + 150*3 + 100*7 = 1570.
Задача 7.5. Открытая модель
Открытая модель сводится к закрытой модели
Фиктивный потребитель
Задание
Найти оптимальный план поставок в примере задачи 7.5.1.
Теоретические положения
Если суммарная мощность поставщиков больше суммарного спроса потребителей, то вводится фиктивный потребитель (фиктивная вершина), которому приписывается спрос, равный разности между суммарной мощностью поставщиков и суммарным спросом потребителей. Фиктивная вершина соединяется непосредственно со всеми поставщиками.
Стоимость перевозки единицы груза от поставщиков до фиктивного потребителя следует брать одинаковой и сравнительно большой, чтобы исключить возможность использования фиктивной вершины в качестве промежуточного пункта. Груз, предназначенный фиктивному потребителю, остается у поставщика.