Не все сетевые линейные программы включают транспортировку вещей или минимизацию затрат. Мы опишем здесь три хорошо известных модельных класса - максимальный поток, кратчайший путь и транспорт / назначение - которые используют одни и те же виды переменных и ограничений для разных целей.
В некоторых приложениях проектирования сети задача состоит в том, чтобы посылать как можно больший поток через сеть, а не отправлять поток с наименьшими затратами. С этой альтернативой легко справиться, отбросив ограничения баланса в источниках и местах назначения потока, заменив цель, которая в некотором смысле обозначает общий поток.
В качестве конкретного примера на рисунке:
Рисунок 1: Сеть потоков трафика представлена схема простой сети трафика. Узлы и дуги.
Узлы и дуги представляют перекрестки и дороги. Пропускная способность, указанная цифрами рядом с маршрутами, выражена в автомобилях в час. Мы хотим найти максимальный поток трафика, который может войти в сеть в точке a и выйти в точке g.
Модель для этой ситуации начинается с набора узлов и символических параметров, указывающих узлы, которые служат в качестве входа и выхода в дорожную сеть:
set INTER; param entr symbolic in INTER; param exit symbolic in INTER, <> entr;
Набор дорог определяется как подмножество пар пересечений:
set ROADS within (INTER diff {exit}) cross (INTER diff {entr});
Это определение гарантирует, что ни одна дорога не начинается на выезде и не заканчивается на въезде. Далее, пропускная способность и транспортная нагрузка определяются для каждой дороги:
set INTER; # intersections
param entr symbolic in INTER; # entrance to road network
param exit symbolic in INTER, <> entr; # exit from road network
set ROADS within (INTER diff {exit}) cross (INTER diff {entr});
param cap {ROADS} >= 0; # capacities
var Traff {(i,j) in ROADS} >= 0, <= cap[i,j]; # traffic loads
maximize Entering_Traff: sum {(entr,j) in ROADS} Traff[entr,j];
subject to Balance {k in INTER diff {entr,exit}}:
sum {(i,k) in ROADS} Traff[i,k] = sum {(k,j) in ROADS} Traff[k,j];
data;
set INTER := a b c d e f g ;
param entr := a ;
param exit := g ;
param: ROADS: cap :=
a b 50, a c 100
b d 40, b e 20
c d 60, c f 20
d e 50, d f 60
e g 70, f g 70 ;
(netmax.mod)
param cap {ROADS} >= 0;
var Traff {(i,j) in ROADS} >= 0, <= cap[i,j];
Ограничения говорят, что за исключением входа и выхода, поток на каждом перекрестке равен потоку:
subject to Balance {k in INTER diff {entr,exit}}: sum {(i,k) in ROADS} Traff[i,k] = sum {(k,j) in ROADS} Traff[k,j];
Учитывая эти ограничения, входящий поток должен быть полным потоком через сеть, который должен быть максимальным:
maximize Entering_Traff: sum {(entr,j) in ROADS} Traff[entr,j];
Мы могли бы также максимизировать общий поток на выходе. Вся модель вместе с данными:
set INTER; # intersections
param entr symbolic in INTER; # entrance to road network
param exit symbolic in INTER, <> entr; # exit from road network
set ROADS within (INTER diff {exit}) cross (INTER diff {entr});
param cap {ROADS} >= 0; # capacities
var Traff {(i,j) in ROADS} >= 0, <= cap[i,j]; # traffic loads
maximize Entering_Traff: sum {(entr,j) in ROADS} Traff[entr,j];
subject to Balance {k in INTER diff {entr,exit}}:
sum {(i,k) in ROADS} Traff[i,k] = sum {(k,j) in ROADS} Traff[k,j];
data;
set INTER := a b c d e f g ;
param entr := a ;
param exit := g ;
param: ROADS: cap :=
a b 50, a c 100
b d 40, b e 20
c d 60, c f 20
d e 50, d f 60
e g 70, f g 70 ;
Любой решатель линейного программирования найдет максимальный поток равный 130 автомобилям в час.
