Сетевая структура полезна, главным образом, как руководство для формулирования модели и интерпретации результатов. Многие из описанных нами моделей принадлежат к более ограниченному классу задач, которые (что сбивает с толку) также известны как «сетевые линейные программы». В терминах моделирования переменные сетевой LP должны представлять потоки на дугах сети, и ограничения должны быть только двух типов: ограничения на потоки по дугам и ограничения на баланс в узлах. Более технический способ сказать то же самое состоит в том, что бы каждая переменная сетевой линейной программы присутствовала не более чем в двух ограничениях (помимо нижней или верхней границ переменных), так что переменная имеет коэффициент +1 и -1 не более чем в одном ограничении.
«Чистые» сетевые линейные программы такого типа обладают некоторыми очень сильными свойствами, которые делают их использование особенно желательным. До тех пор, пока предложение, потребность и границы являются целыми числами, сетевая линейная программа должна иметь оптимальное решение, в котором все потоки являются целыми числами. Более того, если решатель относится к типу решателя, который находит «оптимум» решения (например, основанные на симплекс методе), он всегда найдет одно из полностью целочисленных оптимальных решений. Мы воспользовались этим свойством, не упоминая его явно, предполагая, что переменные в задаче кратчайшего пути и в некоторых задачах присваивания оказываются равными нулю или единице, и никогда не носит промежуточные (нецелые) значения.
Сетевые линейные программы также могут быть решены намного быстрее, чем другие линейные программы сопоставимого размера, за счет использования решателей, которые специализируются на использовании преимуществ сетевой структуры. Если написать модель в терминах объявлений узлов и дуг, AMPL автоматически передает сетевую структуру решающей программе, и любые специальные сетевые алгоритмы, доступные в решающей программе, могут применяться автоматически. С другой стороны, сеть, выраженная алгебраически с использованием var и subject, может быть или не распознана решателем, и, возможно, придется установить определенные параметры, чтобы гарантировать ее распознавание. Например, при использовании алгебраической модели:
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];
можно увидеть обычный ответ общего алгоритма LP:
ampl: model net3.mod; data net3.dat; solve; CPLEX 8.0.0: optimal solution; objective 1819 1 dual simplex iterations (0 in phase I)
Но при использовании эквивалентной формулировки с использованием node и arc:
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;
minimize Total_Cost;
node Plant: net_out = p_supply;
node Dist {i in D_CITY};
node Whse {j in W_CITY}: net_in = w_demand[j];
arc PD_Ship {i in D_CITY} >= 0, <= pd_cap[i],
from Plant, to Dist[i], obj Total_Cost pd_cost[i];
arc DW_Ship {(i,j) in DW_LINKS} >= 0, <= dw_cap[i,j],
from Dist[i], to Whse[j], obj Total_Cost dw_cost[i,j];
можно получить несколько иной ответ, отражающий применение специального сетевого алгоритма LP:
ampl: model net3node.mod ampl: data net3.dat ampl: solve; CPLEX 8.0.0: optimal solution; objective 1819 Network extractor found 7 nodes and 7 arcs. 7 network simplex iterations. 0 simplex iterations (0 in phase I)
Чтобы определить, как решатель ведет себя в этой ситуации, необходимо обратиться к документации по конкретному решателю, которая поставляется с установкой AMPL.
Поскольку сетевые линейные программы намного проще решать, особенно с целочисленными данными, успех крупномасштабного приложения может зависеть от того, возможна ли чистая сетевая формулировка. В случае модели многопродуктового потока:
set LINKS within (CITIES cross CITIES);
set PRODS;
param supply {CITIES,PRODS} >= 0; # amounts available at cities
param demand {CITIES,PRODS} >= 0; # amounts required at cities
check {p in PRODS}:
sum {i in CITIES} supply[i,p] = sum {j in CITIES} demand[j,p];
param cost {LINKS,PRODS} >= 0; # shipment costs/1000 packages
param capacity {LINKS,PRODS} >= 0; # max packages shipped
param cap_joint {LINKS} >= 0; # max total packages shipped/link
minimize Total_Cost;
node Balance {k in CITIES, p in PRODS}: net_in = demand[k,p] - supply[k,p];
arc Ship {(i,j) in LINKS, p in PRODS} >= 0, <= capacity[i,j,p],
from Balance[i,p], to Balance[j,p], obj Total_Cost cost[i,j,p];
subject to Multi {(i,j) in LINKS}: sum {p in PRODS} Ship[i,j,p] <= cap_joint[i,j];
например, ограничения совместной мощности нарушают структуру сети - они представляют собой третье ограничение, в котором фигурирует каждая переменная, - но их присутствия невозможно избежать при правильном представлении задачи. Таким образом, задачи с потоками нескольких товаров не обязательно имеют целочисленные решения, и их, как правило, решить гораздо сложнее, чем с одним потоком товаров сопоставимого размера.
В некоторых случаях разумная переформулировка может превратить то, что кажется более общей моделью, в чистую сетевую модель. Рассмотрим, например, модель в которой мощности определены как в узлах, так и вдоль дуг:
param city_cap {CITIES} >= 0;
param link_cap {LINKS} >= 0;
Пропускная способность дуги, как и прежде, представляет собой максимальный объем перевозок между городами. Пропускная способность узла ограничивает общий поток, обрабатываемый в городе, который может быть записан как предложение в городе плюс сумма входящих потоков или, что эквивалентно, как спрос в городе плюс сумма исходящих потоков. Используя первое, мы приходим к следующему ограничению:
subject to through_limit {k in CITIES}:
supply[k] + sum {(i,k) in LINKS} Ship[i,k] <= node_cap[k];
С этой точки зрения ограничение пропускной способности является еще одним примером «побочного ограничения», которое нарушает структуру сети путем добавления третьего коэффициента для каждой переменной. Но мы можем достичь того же эффекта без побочного ограничения, используя два узла для представления каждого города. Один получает поток в город плюс любое предложение, а другой отправляет поток из города плюс любой спрос:
node Supply {k in CITIES}: net_out = supply[k];
node Demand {k in CITIES}: net_in = demand[k];
Связь отгрузки между городами i и j представлена дугой, которая соединяет узел Demand [i] с узлом Supply [j]:
arc Ship {(i,j) in LINKS} >= 0, <= link_cap[i,j],
from Demand[i], to Supply[j], obj Total_Cost cost[i,j];
Пропускная способность в городе k представлена дугой нового типа, от Supply[k] к Demand[k]:
arc Through {k in cities} >= 0, <= city_cap[k],
from Supply[k], to Demand[k];
Предел пропускной способности теперь представлен верхней границей потока этой дуги, а не боковым ограничением, и сетевая структура модели сохраняется. Полная версия модели:
set CITIES;
set LINKS within (CITIES cross CITIES);
param supply {CITIES} >= 0; # amounts available at cities
param demand {CITIES} >= 0; # amounts required at cities
check: sum {i in CITIES} supply[i] = sum {j in CITIES} demand[j];
param cost {LINKS} >= 0; # shipment costs per ton
param city_cap {CITIES} >= 0; # max throughput at cities
param link_cap {LINKS} >= 0; # max shipment over links
minimize Total_Cost;
node Supply {k in CITIES}: net_out = supply[k];
node Demand {k in CITIES}: net_in = demand[k];
arc Ship {(i,j) in LINKS} >= 0, <= link_cap[i,j],
from Demand[i], to Supply[j], obj Total_Cost cost[i,j];
arc Through {k in CITIES} >= 0, <= city_cap[k],
from Supply[k], to Demand[k];
Предыдущий пример демонстрирует дополнительное преимущество использования объявлений узла и дуги при разработке сетевой модели. Если использовать только узел и дугу в их простых формах - без переменных в условиях узла и без дополнительных факторов в фразах from и to - модель гарантированно приведет только к чисто сетевым линейным программам. Напротив, если использовать var и subject to, тогда пользователь несет ответственность за то, чтобы полученная линейная программа имела необходимую сетевую структуру.
Некоторые из предыдущих комментариев могут быть расширены до линейных программ «обобщенной сети», в которых каждая переменная все еще фигурирует максимум в двух ограничениях, но не обязательно с коэффициентами +1 и –1. Мы видели примеры обобщенных сетей в случаях, когда есть потеря потока или изменение единиц измерения для разных дуг. Обобщенные сетевые LP не обязательно имеют целочисленные оптимальные решения, но для них существуют быстрые алгоритмы. Решатель, который обещает решить «сетевой» алгоритм, может иметь или не иметь расширение для решения задач обобщенной сети. Поэтому прежде чем делать какие-либо предположения, необходимо проверить документацию по конкретному решателю.
