В качестве конкретного примера представим, что узлы и дуги на рисунке 1 представляют города и междугородние транспортные связи.
Завод-изготовитель в городе с маркировкой PITT производит 450 упаковок определенного продукта на следующей неделе, как показано 450 в левой части диаграммы. Города, обозначенные NE и SE, являются распределительными центрами на северо-востоке и юго-востоке, которые получают посылки с завода и доставляют их на склады в городах, обозначенных как BOS, EWR, BWI, ATL и MCO. (Частые пассажиры узнают Бостон, Ньюёрк, Балтимор, Атланту и Орландо.) Потребность складов составляет 90, 120 , 120, 70 и 50 упаковок соответственно, как указано цифрами справа. Для каждой междугородней связи имеется стоимость доставки на единицу упаковок и максимальное количество упаковок, которые могут быть отправлены по маршруту, обозначенные двумя числами рядом с соответствующей стрелкой на диаграмме.
Задача оптимизации в этой сети состоит в том, чтобы найти план поставок с наименьшими затратами, который использует только доступные маршруты, учитывает указанные пропускные способности и удовлетворяет спрос складов. Сначала мы смоделируем это как общую проблему сетевого потока, а затем рассмотрим альтернативы, которые специализируют модель для конкретной ситуации.
В заключение мы представим несколько наиболее распространенных вариантов ограничений сетевого потока.
Общая модель транспортировки
Чтобы написать модель для любой проблемы перевозок из города в город, мы можем начать с определения набора городов и набора ссылок. Каждая ссылка в свою очередь определяется начальным городом и конечным городом, поэтому мы хотим, чтобы набор ссылок был подмножеством набора упорядоченных пар городов:
set CITIES; set LINKS within (CITIES cross CITIES);
В каждом городе существует потенциальное предложение и спрос на пакеты:
param supply {CITIES} >= 0;
param demand {CITIES} >= 0;
В случае задачи, описанной на рисунке 1, единственным ненулевым значением supply может быть предложение PITT (в этом узле упаковка изготавливается и поставляется в распределительную сеть). Ненулевыми значениями demand должны быть значения для пяти складов.
Стоимость перевозки и пропускная способность индексируются по ссылкам:
param cost {LINKS} >= 0;
param capacity {LINKS} >= 0;
как и переменные решения, которые представляют количества упаковок которые подлежат отправке по маршрутам. Эти переменные неотрицательны и ограничены пропускной способностью маршрута:
var Ship {(i,j) in LINKS} >= 0, <= capacity[i,j];
Целевая функция:
minimize Total_Cost:
sum{(i,j) in LINKS} cost[i,j]*Ship[i,j];
которая представляет собой сумму затрат на доставку по всем LINKS.
Осталось описать ограничения. В каждом городе сумма поставленных и отправленных пакетов должна быть равна сумме спроса и предложения:
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];
Так как выражение:
sum {(i,k) in LINKS} Ship[i,k]
появляется в пределах определения фиктивного индекса k, суммирование интерпретируется так, чтобы охватить все города i, так что (i, k) находится в LINKS. Это соглашение об индексировании, которое было объяснено в разделе, часто полезно при алгебраическом описании ограничений баланса сети. На рисунках ниже показана полная модель и данные для проблемы, изображенной на рисунке 1.
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/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];
set CITIES := PITT NE SE BOS EWR BWI ATL MCO ; set LINKS := (PITT,NE) (PITT,SE) (NE,BOS) (NE,EWR) (NE,BWI) (SE,EWR) (SE,BWI) (SE,ATL) (SE,MCO); param supply default 0 := PITT 450 ; param demand default 0 := BOS 90, EWR 120, BWI 120, ATL 70, MCO 50; param: cost capacity := PITT NE 2.5 250 PITT SE 3.5 250 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 ;
Если все переменные переместить влево от знака =, а константы - вправо, ограничение Balance становится:
subject to Balance {k in CITIES}: sum {(i,k) in LINKS} Ship[i,k] - sum {(k,j) in LINKS} Ship[k,j] = demand[k] - supply[k];
Это изменение может быть истолковано так, что в каждом городе к, поставки "в" минус отгрузка "из" должны равняться «чистому спросу». Если в узле имеется завод и склад (как в нашем примере), то положительный чистый спрос всегда указывает на складские узлы, отрицательный чистый спрос указывает на узлы завода, а нулевой чистый спрос указывает на города перевалки. Таким образом, мы могли бы обойтись только с одним параметром net_demand вместо спроса и предложения, со знаком net_demand [k], указывающим, что происходит в городе k. представленную логику рассуждений можно изобразить графически в следующем виде:
Альтернативные формулировки такого рода часто встречаются в описании моделей сетевых потоков.
