Общий подход имеет преимущество в том, что он способен учитывать любые схемы поставок, спроса и связей между городами. Например, простого изменения данных будет достаточно, чтобы смоделировать завод в одном из распределительных центров или разрешить связи отгрузки между некоторыми из складов.
Недостатком общей формулировки является то, что она не может четко показать, какой уровень предложения и спроса ожидается. Если мы знаем, что ситуация будет похожа на ту, что показана на рисунке 1, с поставкой с одного завода, который отгружает в распределительные центры, а затем отправляется на склады, удовлетворяющие спрос, модель может быть специализирована для демонстрации и обеспечения соблюдения требований структуры.
Чтобы явно показать, что в специализированной модели есть три разных типа городов, мы можем объявить их отдельно. Мы используем символический параметр, а не набор для хранения имени завода, чтобы указать, что ожидается только один завод:
param p_city symbolic; set D_CITY; set W_CITY;
Между заводом и каждым распределительным центром должна быть связь, поэтому нам нужно подмножество пар только для того, чтобы указать, какие ссылки соединяют распределительные центры со складами:
set DW_LINKS within (D_CITY cross W_CITY);
С помощью деклараций, организованных таким образом, невозможно указать неподходящие виды связей, например, между двумя складами или со склада обратно на завод.
Один параметр определяет предложение на заводе, а набор параметров спроса индексируется по складам:
param p_supply >= 0;
param w_demand {W_CITY} >= 0;
Эти декларации позволяют определять спрос и предложение только там, где они имеются. На этом этапе мы можем определить наборы CITIES и LINKS, а также параметры спроса и предложения в соответствии с требованиями нашей предыдущей модели:
set CITIES = {p_city} union D_CITY union W_CITY;
set LINKS = ({p_city} cross D_CITY) union DW_LINKS;
param supply {k in CITIES} = if k = p_city then p_supply else 0;
param demand {k in CITIES} = if k in W_CITY then w_demand[k] else 0;
Тогда остальная часть модели может быть:
param p_city symbolic;
set D_CITY;
set W_CITY;
set DW_LINKS within (D_CITY cross W_CITY);
param p_supply >= 0; # amount available at plant
param w_demand {W_CITY} >= 0; # amounts required at warehouses
check: p_supply = sum {k in W_CITY} w_demand[k];
set CITIES = {p_city} union D_CITY union W_CITY;
set LINKS = ({p_city} cross D_CITY) union DW_LINKS;
param supply {k in CITIES} =
if k = p_city then p_supply else 0;
param demand {k in CITIES} =
if k in W_CITY then w_demand[k] else 0;
### Remainder same as general transshipment model ###
param cost {LINKS} >= 0; # shipment costs/1000 packages
param capacity {LINKS} >= 0; # max packages that can be shipped
var Ship {(i,j) in LINKS} >= 0, <= capacity[i,j];
# packages to be shipped
minimize Total_Cost: sum {(i,j) in LINKS} cost[i,j] * Ship[i,j];
subject to Balance {k in CITIES}: supply[k] + sum {(i,k) in LINKS} Ship[i,k] = demand[k] + sum {(k,j) in LINKS} Ship[k,j];
В качестве альтернативы можно поддерживать ссылки на разные типы городов и ссылки всей модели. Это означает, что мы должны декларировать два типа затрат, мощностей и перевозок:
param pd_cost {D_CITY} >= 0;
param dw_cost {DW_LINKS} >= 0;
param pd_cap {D_CITY} >= 0;
param dw_cap {DW_LINKS} >= 0;
var PD_Ship {i in D_CITY} >= 0, <= pd_cap[i];
var DW_Ship {(i,j) in DW_LINKS} >= 0, <= dw_cap[i,j];
Количество ‘‘pd’’ связано с поставками с завода в распределительные центры. Поскольку все они относятся к отгрузкам с одного и того же завода, их нужно индексировать только по D_CITY. Количества «dw» связаны с отгрузкой из распределительных центров на склады и поэтому естественным образом индексируются по DW_LINKS.
Общая стоимость доставки теперь может быть представлена как двойная сумма:
minimize Total_Cost:
sum {i in D_CITY} pd_cost[i] * PD_Ship[i] + sum {(i,j) in DW_LINKS} dw_cost[i,j] * DW_Ship[i,j];
Наконец, должно быть три вида ограничений баланса, по одному для каждого вида города. Отгрузки с завода в распределительные центры должны равняться предложению завода:
subject to P_Bal: sum {i in D_CITY} PD_Ship[i] = p_supply;
В каждом распределительном центре, отгрузки с завода, должны быть равны отгрузкам на все склады:
subject to D_Bal {i in D_CITY}:
PD_Ship[i] = sum {(i,j) in DW_LINKS} DW_Ship[i,j];
И на каждом складе, поставки из всех распределительных центров должны равняться спросу:
subject to W_Bal {j in W_CITY}: sum {(i,j) in DW_LINKS} DW_Ship[i,j] = w_demand[j];
Подходы, показанные выше, эквивалентны в том смысле, что они вызывают решение одной и той же линейной программы. Первый более удобен для экспериментов с различными сетевыми структурами, поскольку любые изменения влияют только на данные для начальных объявлений в модели, вторая форма (для случая когда структура сети вряд ли изменится) облегчает изменения, которые затрагивают только определенные виды городов.
Вся модель с соответствующими данными показана ниже.
set D_CITY;
set W_CITY;
set DW_LINKS within (D_CITY cross W_CITY);
param p_supply >= 0; # amount available at plant
param w_demand {W_CITY} >= 0; # amounts required at warehouses
check: p_supply = sum {j in W_CITY} w_demand[j];
param pd_cost {D_CITY} >= 0; # shipment costs/1000 packages
param dw_cost {DW_LINKS} >= 0;
param pd_cap {D_CITY} >= 0; # max packages that can be shipped
param dw_cap {DW_LINKS} >= 0;
var PD_Ship {i in D_CITY} >= 0, <= pd_cap[i];
var DW_Ship {(i,j) in DW_LINKS} >= 0, <= dw_cap[i,j];
# packages to be shipped
minimize Total_Cost:
sum {i in D_CITY} pd_cost[i] * PD_Ship[i] +
sum {(i,j) in DW_LINKS} dw_cost[i,j] * DW_Ship[i,j];
subject to P_Bal: sum {i in D_CITY} PD_Ship[i] = p_supply;
subject to D_Bal {i in D_CITY}:
PD_Ship[i] = sum {(i,j) in DW_LINKS} DW_Ship[i,j];
subject to W_Bal {j in W_CITY}:
sum {(i,j) in DW_LINKS} DW_Ship[i,j] = w_demand[j];
set D_CITY := NE SE ; set W_CITY := BOS EWR BWI ATL MCO ; set DW_LINKS := (NE,BOS) (NE,EWR) (NE,BWI) (SE,EWR) (SE,BWI) (SE,ATL) (SE,MCO); param p_supply := 450 ; param w_demand := BOS 90, EWR 120, BWI 120, ATL 70, MCO 50; param: pd_cost pd_cap := NE 2.5 250 SE 3.5 250 ; param: dw_cost dw_cap := NE BOS 1.7 100 NE EWR 0.7 100 NE BWI 1.3 100 SE EWR 1.3 100 SE BWI 0.8 100 SE ATL 0.2 100 SE MCO 2.1 100 ;
