 |
Математическая постановка двухэтапной транспортной задачи
|
|
|
|
Пусть массив предприятий-отправителей состоит из m станций Ab={Ab1, Ab2,..,Abm} с ресурсами продукции Rb={R1, R2,..,Rm}, rоторые подлежат отправки или вывозу. Пусть также известны станции назначения Ap={Ap1, Ap2,..,Apn}, потребности в продукции которых составляют Pp={P1, P2,..,Pn}. Кроме того, будем считать, что на пути от отправителей к получателям каждая единица продукции должна быть завезена на один из складов At={At1, At2,..,Atr}, вместимости которых соответственно равны Dt={D1, D2,..,Dr}. Пусть Cik заранее вычисленные стоимости перевозки от произвольного отправителя Abi до произвольного склада Atk. Ckj - цены на перевозку от каждого из складов до каждого из получателей. Пусть Sk – это затраты, связанные с хранением и обработки единицы продукции на складе Atk. Будем считать, что суммарная мощность складов меньше количества продукции, подлежащей перевозки. 
(1). В свою очередь, будем считать, что суммарное количество продукции 
(2).
Будем считать, что наша транспортная сеть не содержит ребер или дуг, которые на прямую связывают станции-отправители со станциями-получателями. То есть, такая связь – отправителей с получателями всегда опосредована по крайней мере с одним из складов.
С каждым ребром (i,j) транспортной сети свяжем некоторые объем перевозок. В результате транспортной сети можно поставить в соответствие некоторый массив X, который мы будем называть планом перевозок.
Понятно, что значение X(i,j) в данной транспортной сети должны удовлетворять ряду ограничений.
Например, пусть Xik – объем поставок от станции-отправителя Abi на склад Atk, при условии, что существует ребро, которое их соединяет. Пусть Xkj – объем поставок со склада Atk на станцию-получатель Apj, тогда должны выполнятся следующие условия:
|
|
|
1) 
- не превышение пропускной способности пути.
2) каждая из станций назначения Apj должна получит продукцию равную объему ее потребностей.
3) каждая из станций отправителей Abi должна вывести свою продукцию в полном объеме
4) объем продукции, поступивший на каждый склад, не может превышать мощности или вместимости склада
5) общее количество продукции, поступающей на склад, должно быть в точности равно общему объему продукции, вывозимому со склада:
План перевозок Х будем называть допустимым, если для него выполняются условия (1-5).
Для того, чтобы составить математическую постановку задачи формализируем суммарные затраты, связанные с определенным планом перевозок.
Пусть, Cik – затраты на перевозку единицы продукции от станции отправителя Abi в склад Atk при условии, что существует ребро [i,k]
Ckj – затраты на перевозку единицы продукции со склада Atk к станции получателя Apj [k,j]
Sk – затраты на хранение единицы продукции на складе Atk.
В результате имеет три позиции:
I1. 
- сумма затрат на вывоз всей продукции из станции отправителя.
I2. 
- вывоз из складов до инцидентных с ними станций получателей и перераспределение продукции между станциями получателями в соответствии с их потребностями.
I3. 
- суммарные затраты на переработку и хранение продукции на складах.
Таким образом, каждому допустимому плану перевозок Х можно поставить в соответствие связанные с ним суммарные затраты: I(x) = I1+I2+I3
То есть, сетевая транспортная задача состоит в нахождении такого плана Хopt для которого суммарные затраты были бы минимальными.
Транспортную сетевую задачу будем называть регулярной, если при существующих ограничениях на пропускную способность сети множество допустимых планов не пусто.
Будем различать два вида таких задач:
- когда суммарная мощность складов будет равна общей потребности станций получателей
-
В первом случае, каждый из складов должен полностью использовать свои мощности, каков бы не был после этого план перевозок продукции со складов к получателям. По этой причине исходная задача (1) распадается на две независимые транспортные задачи, каждую из которых можно решить известными методами.
|
|
|
|
|
|
