Математическая постановка задачи

Одно практически важное обобщение классической транспортной задачи связано с учетом возможности доставки товара от i-го поставщика к j-му потребителю по маршруту, проходящему через промежуточные пункты (склады). Так, например, промежуточные пункты являются составной частью распределительной системы любой крупной компании, имеющей сеть универсальных магазинов во многих городах. Такая компания обычно имеет зональные оптовые базы (поставщики), снабжающие товарами более мелкие региональные склады (промежуточные пункты), откуда эти товары поступают в розничную торговую сеть (потребители). При этом товар для каждого фиксированного потребителя в общем случае может быть доставлен от любого поставщика и по маршрутам, не обязательно проходящим через все промежуточные пункты. Кроме того, промежуточные пункты могут обладать вполне определенной спецификой. Так, например, при транспортировке товара от поставщика к потребителю по маршруту, проходящему через склад, часть товара может быть использована для создания неприкосновенного запаса на складе.

Задачу выбора плана перевозок товаров от поставщиков к потребителям с учетом промежуточных пунктов, обеспечивающего минимальные транспортные затраты и спрос потребителей, в исследовании операций называют транспортной задачей с промежуточными пунктами. Для приобретения практических навыков в построении математических моделей таких задач обратимся к следующему примеру. На рис.8 представлена схема размещения складов, на которой указаны:

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

	Рис.8. Схема размещения складов

 

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

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

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

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

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

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

Объем буфера В определяется по следующему правилу:

(4)

B = общий объем предложения = S₁+S₂

или

B = общий объем спроса =D₆+D₅

 

(5б)

(5в)

(5г)

(5а)

(5ж)

(5е)

(5д)

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