Решение. Предположим, торговая фирма имеет восемь складов, на которых сосредоточены все имеющиеся в наличии запасы товара

Пример

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

На рис. 8 представлена схема размещения складов, на которой указаны:

а) склады в виде узлов сети с номерами от 1 до 8;

б) избыток товара на складе, который должен быть перераспределен в системе складов (указан в квадратных скобках рядом с узлом сети положительным числом и выражен в единицах измерения товара);

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

г) возможность перевозки товара со склада i на склад j (ориентированная дуга от круга с номером i к кругу с номером j);

д) затраты, связанные с перевозкой единицы товара со склада i на склад j (величина c_ij рядом с соответствующей ориентированной дугой, выраженная в денежных единицах).

На рис 8 видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 той же системы. Перераспределение товара может происходить через склады с номерами 2, 4-7, которые в рассматриваемой задаче и являются промежуточными или транзитными пунктами. Истинным пунктом отправления является лишь склад с номером 1, на котором имеется избыток товара и с которого товар можно только вывозить, а истинными пунктами назначения являются склады с номерами 3 и 8, на которых есть недостаток товара, и на эти склады товары можно только завозить. Заметим также, что между складами с номерами 4 и 5 возможны перевозки в обоих направлениях, но в общем случае c₄₅ ¹ c₅₄ (например, наличие одностороннего движения по кратчайшему маршруту). Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом:

Объем предложения истинного пункта отправления = объем исходного предложения.

Объем предложения транзитного пункта = объем исходного предложения + объем буфера.

Объем спроса истинного пункта назначения = объем исходного спроса.

Объем спроса транзитного пункта = объем исходного спроса + объем буфера.

Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса).

Пусть J — множество номеров складов, на которые товар может быть доставлен с k -го склада, а I — множество номеров складов, с которых товар может быть доставлен на k -й склад. T_k — величина чистого запаса товара, равная объему исходного предложения или исходного спроса. Тогда математическую модель данной задачи можно представить следующим образом:

В специальной литературе по исследованию операций[1] приводится доказательство того, что рассматриваемая транспортная задача с промежуточными пунктами эквивалентна классической транспортной задаче.