1. Indledning.

De senere års stærke vækst i litteraturen om matematiske programmeringsproblemer vidner om en stadig voksende interesse for emnet, vel nok fremkaldt af de elektroniske cifferregnemaskiners udbredelse kombineret med et vågent blik for anvendelsesmulighedernes mangfoldighed. Som et enkelt resultat af de bestræbelser, der er udfoldet på dette område, foreligger idag en række effektive algoritmer til behandling af specielle matematiske programmeringsproblemer, hvis formulering er nært knyttet til netværksbetragtninger. Dette gælder især problemer, der involverer en eller anden form for transport i vid forstand, og hvor en netværksbeskrivelse derfor korresponderer nøje med problemernes natur, men det gælder også en række rent kombinatoriske problemstillinger, der i deres originale præsentation ikke umiddelbart har haft noget med netværk at gøre.

Den del af den matematiske programmerings teori, der er udviklet på dette felt, omfatter behandlingen af, hvad man i den angelsaksiske litteratur samler under fællesbetegnelsen »transportation problems« eller »network flow problems«. Den sidste benævnelse er så afgjort at foretrække,da den langt bedre karakteriserer emnets matematiske indhold og ikke begrænser anvendelsesmulighederne til et enkelt område. Vi

---

1) Foredrag i DORS, Dansk Selskab for Operationsanalyse, den 25. februar 1966 som oplæg til et senere foredrag om løsning af ikke-lineære problemer ved hjælp af »network flow« metoder.

2) Civilingeniør, Instituttet for Matematisk Statistik og Operationsanalyse, Danmarks tekniske Højskole.

savner en tilfredsstillende betegnelse på dansk, hvilket hænger sammenmed den vanskelige oversættelse af ordet flow. Ved flow forstås simpelthen »alt det, der flyder« i det aktuelle distribuerings-, kommunikations - eller for den sags skyld også gerne elektriske netværk, der vælges som model for et givet programmeringsproblem. Da ordet strøm hyppigt identificeres som et elektrisk begreb, og da flow må karakteriseressom et langt videre begreb end strøm i denne betydning, er der grunde, der taler for en indførelse af den ikke-oversatte betegnelse i dansk sprogbrug.

Teorien for flow i netværk er nært beslægtet med grafteorien, hvis
oprindelse i hvert fald kan spores tilbage til 1736, hvor Euler dyrkede
det berømte Konigsberg-problem:

Byen Konigsberg deles af floden Pregel i fire dele, der atter er forbundet
af de syv viste broer.

Problemet, der optog den daværende befolkning, var: Er det muligt
at foretage en spadseretur således, at enhver af de syv broer passeres
een og kun een gang?

Da Euler fik problemet forelagt, lod han i sin model enhver bydel repræsentere af et punkt og enhver bro af en gren og havde hermed bestemt problemets graf. Et studium af grafers karakteristika i almindelighed førte til, at den her viste graf ikke besad de fundamentale egenskaber, der var nødvendige for at gøre turen mulig.

Grænsen mellem grafteorien og teorien for flow i netværk er ikke skarp, men vil man alligevel forsøge at drage en skillelinie, kommer denne højst til at vedrøre målsætningerne. Grafteorien beskæftiger sig fortrinsvis med de kvalitative eller topologiske egenskaber og forsyner os med de nødvendige theoremer for eksistens og eentydighed eller giver os med andre ord svar på spørgsmål om, hvorvidt denne eller hin

egenskab er til stede. Teorien for flow i netværk, hvis fornemste opgave
så afgjort er algoritmeudviklingen, giver derimod de rent kvantitative
metoder til bestemmelse af dette eller hint.

Hvornår teorien for flow i netva^rk er opstået som en selvstændig
disciplin, er et højst diskutabelt spørgsmål. Flere forfattere refererer i
denne forbindelse gerne til det såkaldte klassiske transportproblem:

Lad der være givet m producenter og n forbrugere af en enkelt varetype. Den øvre grænse for hver enkelt fabriks produktion pr. tidsenhed samt den nedre grænse for hver enkelt forbrugers efterspørgsel pr. tidsenhed er kendt. Der findes direkte transportveje fra enhver fabrik til enhver forbruger, og til hver af de ialt mXn transportveje er knyttet en given enhedspris. Bestem en varefordeling i nettet, der imødekommer kravene om kapacitet og efterspørgsel og som minimaliserer de totale transportomkostninger.

Æren for denne formulering tilskrives ofte F. Hitchcock, der publicerede et arbejde herom i 1941 [1] og heri fremkom med en algoritme, der har flere træk fælles med den af G. B. Dantzig i 1947 udviklede Simplex-metode [2]. Men uafhængigt af Hitchcock blev det kontinuerte tilfælde studeret af russeren Kantorovich [3], og atter uafhængigt af sine forgængere publicerede T. G. Koopmans i 1947 sit betydelige bidrag [4] på basis af sine erfaringer fra 2. verdenskrig. Problemet har idag fundet sin plads i den omfangsrige litteratur under betegnelsen: The Hitchcock- Koopmans Transportation Problem. På denne baggrund er det pudsigt at notere sig følgende problemstilling, der forblev übemærket af alle indtil 1956, hvor S. Ulam påviste identiteten mellem denne og det kontinuerte tilfælde af det ovenfor nævnte transportproblem:

Lad der være givet et område, der er ensartet dækket med jord. Al jorden ønskes fordelt på et andet område på en foreskreven måde, og flytningen ønskes udført således, at det totale arbejde minimaliseres. (G. Monge: Déblai et remblai. Mémoires de l'Academie des Sciences, Paris 1781).

De senere års udvikling er domineret af navnene G. B. Dantzig, L. R. Ford og D. R. Fulkerson, hvor de to sidstnævnte i bogen »Flows in Network« [5] har opsamlet andres og egne bidrag i en ypperlig og afrundet fremstilling, der giver en klar fornemmelse af metodernes alsidighed. I de følgende afsnit behandles - efter en nødtørftig omtale af visse fundamentale begreber - en typisk problemstilling fra denne bog: Det såkaldte minimalomkostningsproblem formuleres; dernæst gennemgås Ford-Fulkersons algoritme og sluttelig gives nogle eksempler på forskellige

2. Definitioner.

Et orienteret netværk er opbygget af:

a) En mængde, JV, hvis elementer kaldes netværkets knudepunkter
eller blot punkter.

b) En mængde, A, hvis elementer kaldes netværkets grene. Elementerne i A består af ordnede elementpar, der er udtaget af mængden N; [a,b] s A 4> a e N, b e N. [a,b] repræsenteres på papiret som en kontinuert kurve, der forbinder a (grenens startpunkt) med b (grenens slutpunkt). Til markering af orienteringen forsynes grenen med en pil, der peger fra a mod b.

Det netværk, der således er defineret ved mængderne N og A, betegnes ved symbolet G = [N; A], og den figur, der er afbildningen af netværkets punkter og grene, kaldes nettets graf. Idet vi med \X\ betegner antallet af elementer i den vilkårlige mængde, X, antages det, at \N\ og \A\ er endelige tal.

Eksempel:

For det orienterede netvaer'k, G = [N;A] siges enhver gren ;' = [x,y], hvor ;' s A, at vaere positiv incident til x og negativ incident til y. Til alle Bvrige punkter i nettet er gren j ikke incident. Ved indforelse af nettets sakaldte incidens-matrix kan vi under eet beskrive incidensen for samtlige grene til samtlige punkter. Incidensmatricen indeholder jiVJ raskker og \A\ sojler, og det vilkarlige element, m[i,j], der udtrykker incidensen af gren ; til punkt i, bestemmes som:

Til den på fig. 2 viste graf svarer incidensmatricen:

Såfremt nettet ikke indeholder sløjfer, der defineres som grene med sammenfaldende start- og slutpunkt, vil incidensmatricen eentydigt beskrive nettets struktur. Således vil figurerne 2 og 3 indeholde nøjagtig samme information, men figur 3 indeholder denne information på en form, der umiddelbart er tilgængelig for elektronisk databehandling.

Endvidere defineres:

Vej Lad x[l], x[2], . . . , x[n] vaere en felge af forskellige punkter
i nettet, saledes at

Vi kalder da felgen af grene
[*[I], x[2]], [x[2], x[3]], . . . , [*[fi-l]. x[n]]
for en simpel vej, der ferer fra x[l] til x[n].

Led Hvis enten [x,y] e A eller [y,x] e A, da kaldes elementet
[x,y] (eller [y,x]) et led.

Kcede Lad x[l], x[2], . . . , x[n] vaere en felge af forskellige
punkter i nettet, saledes at

er et led. Vi kalder da felgen af led
[*[I], *[2]], [*[2], *[S]]f . . . , [x[n~l] ,x[n]]
for en simpel kaede, der forbinder x[l] med x[n].

Cykle Hvis x[l] — x[n], kaldes felgen en simpel cykle.

f[x,y], For det orienterede netvaerk G = [iV;./4] vil vi med f[x,y],
I [x,y], bvor [x,y] eA, betegne den msengde flow, der pr. tidsenhed
u[;c,;y] flyder i gren [x,y] fra x til y. Desuden vil vi til enhver gren
eller knytte to reelle tal, l[x,y] og wf^r,^], som hhv. nedre og
fxy, Uy, eyre graense for f[x,y].

Uxy (Ved skrivning af indicerede variable er det bekvemt at benytte den viste notation med skarpe parenteser om indices. Undertiden benyttes dog i de følgende afsnit almindelige subscripts (fodtegn) på steder, hvor en overflod af parenteser måske ville vanskeliggøre oversigten).

Cirku- Vi taler om cirkulation i nettet, når det for ethvert x s N
Jation gælder, at den flowmængde, der løber til punktet x er lig
den flowmængde, der udgår fra x. Idet / betegner flowvektoren
og incidensmatricen kaldes /, kan man let verificere,
at cirkulationsbetingelsen er ækvivalent med

(2-1)

Ved en brugbar cirkulation forstås en flowfordeling, /, der
tilfredsstiller såvel (2-1) som

(2-2)

Lad X og Y være to delmængder af mængden N. Med symbolet
(X, Y) betegnes mængden af alle de grene i nettet,
hvis startpunkt tilhører X, og hvis slutpunkt tilhører Y:

For en vilkårlig funktion, g, der er defineret i mængden A,
indføres endvidere symbolet

Under anvendelse heraf kan cirkulationsbetingelsen skrives:

(2-3)

Snit Mængden N opdeles i to disjunkte delmængder, X og X:
X X=o (den tomme mængde);
X^X=N;

Mængden af grene, (X,X) kaldes da et snit.

Eksempel:

3. Minimalomkostningsproblemet på cirkulationsform.

Bestem en cirkulation, f, i nettet G = [N; A], der minimaliserer

under begræsningerne

hvor /, u og c er givne, reelle tal.

Hvis alle data er heltallige, og hvis en brugbar cirkulation existerer, da kan en optimal cirkulation bestemmes med Ford-Fulkersons algoritme: Out-of-kilter. (Out-of-kilter kan oversættes ved: Ude af balance som modsætning til in-kilter, der er udtryk for en ligevægtstilstand). Algoritmen er første gang beskrevet i en artikel fra 1961 [6] og senere gjort til genstand for en udvidet behandling i [s], pp. 162-169.

Algoritmen bygger pa folgen.de princip, der gaelder ethvert lineaert
programmeringsproblem:

Bestem en vektor,

der minimaliserer

(3-1)

under begrænsningerne

(3-2)

og

hvor an, bj og a er givne, reelle tal

En vektor, x, der tilfredsstiller (3-2), kaldes brugbar for det pågældende program. En brugbar vektor, der tillige minimaliserer objektfunktionen (3-1), kaldes optimal. Af dette såkaldte primalprogram kan vi direkte aflede dualprogrammet (se appendix II i [7]):

Bestem en vektor,

der maximerer

(3-3)

under begrænsningerne

(3-4)

og

Den fundamentale dualitetssætning for lineær programmering fastslår, at hvis der blot findes en optimal vektor (og hermed brugbare vektorer) for det ene af de to programmer, da gælder dette også det andet. Ydermere vil de to objéktfunktioner antage samme værdi i løsningspunktet

Vi antager nu, at der findes et sæt optimale vektorer, x° og f\ hvis
elementer alle er endelige tal. Da vil

For alle sæt af brugbare, men ikke optimale vektorer, x og y', gælder

eller

(3-5)

Da

gælder endvidere

(3-6)

Vi kan fortolke vektorerne v og w som de ikke-negative tillæg (slack),
der bevirker, at hhv. (3-2) og (3-4) omformes til ligheder. (3-6) ses at

være summen af to skalarprodukter, og da alle elementerne i de fire
vektorer, x, w, y og v er ikke-negative, kan summen kun blive nul, såfremt

(3-7)

Dette sæt af betingelser forekommer undertiden under navnet: Complementary
Slackness Condition, eller blot: CSC. Vi aflæser heraf:

Bemærk iøvrigt, at dersom det for nogle j gælder, at

eller

da vil kravet

kunne opfyldes, selv om vi ophæver begrænsningen yj 0.

Konklusionen bliver, at uligheder i det ene program korresponderer med ikke-negative variable i det andet, samt at lighedstegn korresponderer med übegrænsede variable. Omvendt fås, at dersom der eksisterer brugbare vektorer, x og y, for hhv. det primale og det duale program, der tillige tilfredsstiller CSC, da vil

eller

eller

men da (x\ y') 4= (x°, y°)

må

4. Reformulering og løsning af minimalomkostningsproblemet

For at løse minimalomkostningsproblemet under anvendelse af dette
princip må vi indledningsvis bestemme det duale program samt opstille

Eksempel:

Primalprogram: Bestem en cirkulation,

der minimaliserer

under begrænsningerne

Dersom begraensningerne udtrykkes pa formen (3-2), fas:

eller (se (3-2)): 2 aaxi^bj; xr. Übegraenset
i

Svarende til de |N| + 2X|^4| = 16 begramsninger i primalprogrammet
indferes 16 duale variable:

Übegrænsede; korresponderer
med lighedstegn i
primalprogrammet

Ikke-negative; korresponderer
med uligbeder i primalprogrammet

Dualprogrammet — sammenlign (3-3) og (3—4) — bliver herefter

Maximer

(4-2)

under begrænsningerne

(4-3)

(4-4)

Complementary Slackness Condition (se (3-7)):

der - taget sammen med (4-4) - giver:

(4-5)

Af beregningsmæssige grunde er det bekvemt at sætte

hvorved

Der bliver fire tilfælde:

Dersom punktet (f, c) for hver gren afsættes i det for grenen specifikke diagram, skal dette punkt, når cirkulationen er optimal, være beliggende på den kraftigt optrukne knæklinie. Grenen siges så at være i en in-kilter tilstand; i modsat fald er grenen out-of-kilter. Bemærk, at grene for hvilke f [x,y] — f [x,y] -= u [x,y] vil være i ligevægt for alle værdier af c [x,y]; her udarter knæklinien til en ret linie.

Mmimalomkostningsproblemet kan nu reformuleres:

Bestem en p-værdi for hvert punkt i nettet samt en f -værdi for hver
gren, således at:

Det antages, at alle data er heltallige, samt at initialcirkulationen er
brugbar. Betragtes ( f,c)-diagrammet, ses det, at vi under denne forudsætning
kun behøver at interessere os for planstrimlen

Enhver gren må være i en af følgende fem tilstande (se fig. 6):

Til hver tilstand knyttes et ikke-negativt tal, k [x,y], det såkaldte kiltertal:

Til balancetilstande svarer kiltertallet nul, mens der til tilstandene h og h svarer positive kiltertal, der kan fortolkes som mål for, hvormeget optimalitetskriterierne (4-7) mangler i at være opfyldt. Algoritmen udvælgernu successivt alle grene, der ikke er i balance, og søger at bringe

dem i balance på en sådan måde, at alle øvrige grenes kiltertal enten
forbliver uændrede eller antager en mindre, men stadig ikke-negativ
værdi.

Ethvert forsøg på tilstandsændringer kan kun ske ved flytninger langs vandrette og lodrette linier i diagrammet. Den viste gren i tilstand i\ kan bringes nærmere mod en balancetilstand enten ved at mindske f [x,y] med beløbet s eller ved at mindske c [x,y] med beløbet å. Det fremgår, at

Algoritmebeskrivelse.

Indledningsvis vælges en vilkårlig, heltallig og brugbar initialcirkulation samt vilkårlige, heltallige duale variable (p-værdier). Desuden oprettes to vektorer, z og eps, til lagring af den løbende information om hvert punkt i nettet.

Det antages, at gren [s,t] er ude af balance, f. eks. i tilstand h. Vi søger nu gennem e markeringsprocedure at konstruere et snit, (X, X), for derved om muligt at bestemme en simpel cykle, hvori gren [s,t] indgår. Cyklen skal endvidere bestemmes således, at en flowændring i denne medfører, at mindst et kiltertal bliver mindre, mens alle øvrige enten forbliver uændrede eller formindskes. Vi starter i punktet t og sætter

Nu er punktet t markeret (t e X), mens alle evrige punkter er umarkerede,
(y s X, y 4= t).

Generelt foretages følgende:

Hvis x a X, ye X og enten

1)

eller 2)

da skal også y s X. Vi markerer y

Hvis 1):

Hvis 2):

Dette fortsættes, indtil

a) sBX: Gennembrud

!b) Videre markering kan ikke foretages, og seX:
Ikke-gennembrud.

Ved genembrud foretages flowændring i den simple cykle

hvor cyklen spores tilbage fra s til t ved hjælp af z-vektoren. Idet cyklen
tillægges samme orientering som gren [s,t], består cyklen af en mængde,
F, af fremadrettede grene samt en mængde, B, af bagudrettede grene.

Vi sætter

(4-6)

idet fortegnet på de enkelte elementer i 2-vektoren indicerer, om de pågældende
grene er fremad- eller bagudrettede.

Bemærk, at eps [s] på denne måde bliver lig

(4-7)

således at cirkulationen efter flowændringen vedblivende er brugbar.

Hvis markeringsprocessen stopper med et ikke-gennembrud, ændres
de duale variable på følgende vis:

Vi definerer to delmængder af grene:

(4-8)

og sætter

(4-9)

samt

hvorefter

(4-10)

Hvis Qi = 0, saettes d( = + <*>; i: = 1,2;

Hvis gren [s,i] efter en ændring af de primale variable (ved gennembrud) eller ændring af de duale variable (i tilfælde af ikke-gennembrud) stadig ikke er i balance, konstrueres snittet (X,X) påny med t som udgangspunkt, ganske som før. Processen gentages, indtil gren [s,t] er i ligevægt, og dernæst opsøges en ny gren, der ikke er i ligevægt. Dersom denne er i tilstand ii, forløber iterationen helt som beskrevet bortset fra starten, hvor vi denne gang markerer s:

og konstruerer snittet for om muligt at bestemme en simpel kæde mellem
s ogt.

Hvis en afsøgning viser, at alle grene er i balance, er dette tilstrækkeligt
til at sikre, at den fundne cirkulation er optimal.

For i første omgang blot at sandsynliggøre, at disse manøvrer virkelig
fører til det ønskede resultat, illustreres situationerne med et par
eksempler.

Et gennembrud er vist på figur 8. De understregede tal: Omkostningskoefficienter,
c[#,3;]. Tal i parenteser: Flow. Øvrige tal: Duale
variable. Det konstateres, at gren [s,t] er ude af balance, i tilstand ir.

Markering af t:

Gren [t,a]:

Markering af a:

Gren [b,a]:

Idet viser bort fra den øvrige - og i denne forbindelse uinteressante
del af nettet - slutter processen med:

Fremadrettede grene:

Bagudrettede - :

I skemaform bevirker flowændringen:

Objektfunktionen mindskes med beløbet

svarende til ændringen i summen af kiltertallene. Dette forhold er en
følge af, at

En ikke-gennembrudssituation er vist på figur 9, hvor tallene har
samme betydning som på forrige figur.

Det antages for en simpelheds skyld, at

Gren [s,t] ses at være i tilstand 22, og idet alle detailler ved marke
ringen udelades, fås:

Gren [s,t]:
og derefter:

Alle grene, der kan komme på tale, er nu undersøgt, og dernæst fås af
(4-8) - (4-10):

Ændring af duale variable: p[x]: = p[x] +1; xe X

En skematisk opstilling af forløbet viser

Objektfunktionens værdi forbliver naturligvis uændret.

Konvergens.

Reglerne for snittets konstruktion er vist så klart gennemskuelige, at der næppe er tvivl om, at objéktfunktionen vil blive formindsket med et positivt beløb ved et gennembrud og efterfølgende flowændring. Af (4-7) ses, at dette positive beløb bestemmes som en differens mellem to heltal og følgelig bliver mindst +1. Måske er konsekvenserne af (4-8) - (4-10) knapt så indlysende og kræver en kommentar.

Det antages, at snittet er konstrueret på sædvanlig måde, samt at
processen er afsluttet med et ikke-gennembrud. Lad [x,y] være en vilkårlig
gren i snittet (X, X). Denne gren må da være i en af tilstandene

thi ellers skulle y e X. Hvis grenen er i en af tilstandene b\ eller z'i, da
tilhører den mængden Qi; i modsat fald er den i balance.

Omvendt, lad [y,x] være en vilkårlig gren i snittet (X, X). Denne
gren må da være i en af tilstandene

thi ellers skulle x sX. Hvis grenen er i en af tilstandene fa eller i-2, da
tilhører den mængden Qr, i modsat fald er den i balance.

Det ses heraf, at mængderne Qi og Q2 begge vil være tomme, hvis og kun hvis alle grene i snittene (X,X) og (X,X) er balance. Men dette strider mod, at gren [s,t] var ude af balance, hvilket var motiveringen for overhovedet at konstruere snittet.

Af (4-10) fremgår, at ændringen af de duale variable højst influerer på grene i snittene {X,X) og (X,X). Af (4-9) ses endvidere, at d må være endelig og +1. Konklusionen bliver, at mindst een gren, nemlig [s,t], i hver iteration får sit kiltertal mindsket med mindst +1, mens kiltertallene for alle øvrige grene i nettet vil være monotont aftagende under iterationerne. Dette er tilstrækkeligt til at sikre konvergensen.

Da alle beregninger er rene heltalsoperationer, følger desuden, at løsningen
selv må være heltallig.

5. Anvendelser

I dette afsnit præsenteres en række problemer, der alle kan transformeres til og løses som minimalomkostningsproblemer på cirkulationsform, uden at det dog hermed er sagt, at en sådan fremgangsmåde altid vil være den mest hensigtsmæssige i de pågældende tilfælde. Listen tilstræber på ingen måde at være komplet men er blot et skønsomt udvalg af typiske problemstillinger, der ofte mødes såvel i teori som i praksis.

5.1 Hitchcock-Koopmans Transportation Problem

Med m kilder (producenter), n terminaler (forbrugere) samt mXn
transportveje kan dette problem, der allerede er omtalt i indledningen,
formuleres:

Bestem de mXn værdier, f[i,j]

der minimaliserer

(5-1)

nar

(5-2)

(5-3)

hvor a, b og c er givne, reelle tal.

Summeres (5—2) og (5-3) over hhv. i og j, bliver de to venstre sider
identiske. Systemet er således kun konsistent, såfremt

(5-4)

Dersom (5-2) og (5-3) var givet på formen

kunne man blot ved indførelse af slackvariable atter opnå lighedstegn,
uden at det forelagte problem ændredes herved. Den viste formulering
med bibetingelsen (5-4) er således helt generel.

Det klassiske transportproblem er ikke umiddelbart et cirkulationsproblem,
men kan let transformeres til et sådant. Idet kilder og terminaler
betegnes med hhv.

udvides nettet med en masterkilde, s, og dito terminal, t, samt grenene
0, s[i]], [t[j]}, t] og returlederen, [t,s].

(5-5)

Hvis alle data er heltallige, kan den optimale cirkulation nu bestem
mes. At en brugbar cirkulation eksisterer, er sikret gennem (5—4).

Men vil det overhovedet være nødvendigt at ændre det forelagte problem til et cirkulationsproblem? For alle de tilføjede grene gælder, at nedre grænse sættes lig øvre grænse, og begge er atter lig flow under forudsætning af en brugbar initialcirkulation. Vi kan med andre ord aldrig ændre flow i de tilføjede grene, der alle altid vil være i ligevægt, og som derfor atter kan fjernes, uden at algoritmen på nogen måde påvirkes heraf.

Der foreligger i dag et stort antal algoritmer til løsning af det klassiske transportproblem. For hovedparten gælder, at omkostningskoefficienterne, c[i,j], er begrænsede til at være ikke-negative. Dette krav stilles ikke her; hvis det er ønskeligt, kan vi derfor også maximere (5-1) ved blot at skifte fortegn på alle omkostningskoefficienterne og derved bestemme den dyreste løsning.

Bemærk iøvrigt, at løsningen forbliver uændret, hvis vi adderer en
vilkårlig konstant til alle elementerne i en række eller søjle i ornatrisen.
Antag f. eks. at vi sætter

Problemet er nu ændret til under samme begrænsninger som før at
minimere

Det første led er konstant, så problemstilling og løsning er uændret.
Denne invarians optræder desuden, hvis alle omkostningskoefficienter
multipliceres med en positiv konstant eller hvis vi sætter

I det sidste tilfælde fås løsningen af den originale ved en multiplikation
med K.

Disse omstændigheder kan udnyttes, hvis man med direkte trial and error metoder søger et skøn over den optimale løsning til et problem af overskuelig størrelse. Betragt f. éks. det først publicerede transportproblem [1]:

Hitchcock angiver en optimal løsning (der er flere):

Ved subtraktion af det mindste element i hver søjle og derefter det
mindste element i hver række samt ved division af produktion og efterspørgsel
med 5, fås:

Umiddelbart sættes: f [1,4]: =5; f [2,4]: =2; f [3,3]: =6; hvilket
giver omkostningen nul i det ændrede problem. Tilbage står det indrammede

der altid vil give omkostningen +4, uanset hvilken fordeling vi vælger.
Nederste række kan aldrig give en mindre omkostning end +4, så alle
de fundne løsninger er optimale.

5.2 Personnel Assignment Problem.

Lad der være givet m ansøgere til n ledige stillinger, hvor m n, og lad c[i,j] være et mål for, hvor kvalificeret ansøger nr. i er til stilling nr. ;'. De n stillinger ønskes besat på en sådan måde, at summen af kvalifikationsmålene for de udvalgte ansøgere maximeres.

Da den optimale løsning for et heltalligt transportproblem med heltallige
data selv vil være heltallig - jfr. bemærkningerne i pkt. 4 om
algoritmens konvergens - kan problemet formuleres:

(stillingen skal besættes)

(- men ikke alle ansegere
kan komme i betragtning,
hvis m > n)

Bortset fra den omstændighed, at objektfunktionen her skal maximeres i stedet for minimeres, genkendes problemet som en speciel version af det forrige omtalte. Et fortegnsskifte på alle kvalitetsmålene gør dog ligheden fuldkommen.

5.3 Capacitated Transportation Problem.

Ved mange praktiske anvendelser er det realistisk at antage, at der findes en øvre grænse for den mængde, der kan transporteres ad en bestemt rute. Det er endog muligt, at visse transportveje helt ønskes undgået; vi kan for sådanne grene sætte den øvre grænse til nul som et alternativ til muligheden blot at vælge en meget høj omkostningskoefficient. Det kan endvidere tænkes, at omkostningskoefficienten for en bestemt transportvej ikke er kendt med sikkerhed; vi kan i så fald være interesserede i at bestemme en optimal flowfordeling i nettet, der ikke benytter denne transportvej. Af de duale variables værdi i løsningen (punktets beliggenhed i (f,c) -diagrammet) kan vi aflæse en nedre grænse for den værdi, som den übestemte koefficient skal overskride, for at transportvejen ikke bliver benyttet.

De ønskede kapaciteter indsættes som øvre grænse jfr. (5-5), hvorefter
resten forløber som ovenfor beskrevet.

5.4 Transshipment.

Mens de forrige problemstillinger vedrørte specielle net, de såkaldte bipartitte net, hvor ethvert punkt var enten kilde eller terminal, betragtes nu vilkårlige net med grene af uendelig kapacitet, og hvor flow i visse punkter hverken tilføres eller forlader nettet men blot videresendes. Til hver gren er knyttet en given omkostningskoefficient, og der ønskes bestemt en flowfordeling, der imødekommer en vis efterspørgsel i nogle punkter fra forsyninger i andre, og som minimerer de totale omkostninger.

Lad S og T være mængderne af hhv. kilder og terminaler, og lad R
være mængden af de resterende, såkaldt mellemliggende punkter i nettet
[N;A].

Minimalis er

under begrænsningerne

Transshipment-problemet kan umiddelbart omformes til et cirkulationsproblem;
dog kan vi også her udelade grene, for hvilke

5.5 Maximum Flow Problem.

Maximer den variable, v, (en skalar)
under begrænsningerne

hvor kilden, s, og terminalen, t, er to givne punkter i nettet
G= [N;A].

Nettet udvides med returlederen [t,s], og vi sætter

hvor K vælges så stor, at den med sikkerhed vil være en øvre grænse
for v.

løsning af problemet har vi minimeret

som atter er ensbetydende med en maximering af v, hvilket netop var
hensigten.

Problemet kan naturligvis også løses for ikke-orienterede net, idet
hvert led blot erstattes af to modsat orienterede grene i parallelkobling.

Et af Ford-Fulkersons vægtigste bidrag til teorien om flow i netværk
er det såkaldte max-flow min-cut theorem:

For et vilkårligt netværk vil den maximale flow fra s til t være lig
den mindste snitkapacitet for samtlige snit, der adskiller s og t, eller

hvor

Denne sætning, hvoraf flere andre kan afledes, blev først bevist for plane netværk (1954) og senere udvidet til at omfatte vilkårlige net (1956). (Et netværk kaldes plant, hvis dets graf kan tegnes således, at ingen grene skærer hinanden).

Max-flow problemer opstar bl. a. ved besternmelse af flaskehalse i transportsystemer men har interesse derudover, idet flere problemer kan formuleres som max-flow problemer, end man umiddelbart skulle formode. Det blev i de indledende definitioner fremhcevet, at f[x,y] var den maengde flow, der pr. tidsenhed flyder fra x til y. Dette er definitionen af statisk flow i modsaetning til dynamisk flow, der betegnes med symbolet f[x,y;r]. I problemer med dynamisk flow opererer man med en sakaldt passagetid, £[#,;y], for gren [x,y], og f[x,y;t] er den flowmaengde, der til tiden r forlader x i gren [x,y].

Et typisk problem for dynamisk flow er:

Til hver gren i nettet er knyttet en given passagetid samt en vis øvre grænse (kapacitet). En flowmængde kan i ethvert punkt enten videresendes umiddelbart efter ankomsten eller forsinkes til et senere tidspunkt. Bestem den maximale flowmængde, der kan flyde fra kilde til terminal i et specificeret antal tidsperioder.

Dette og beslægtede problemer kan løses som successive, statiske
max-flow problemer, se f. eks. [5] eller [B].

5.6 Korteste vej.

For det givne net, [N;A], hvor længderne af enhver gren er kendte,
ønskes bestemt den korteste vej mellem to vilkårlige punkter, s og t.

Idet længden af gren [x,y] betegnes med c[x,y], og

og nettet udvides med den fiktive returleder, [t,s], hvor

da er problemet omformet til et cirkulationsproblem, hvor vi »trækker«
1 flowenhed ud af terminalen, t, og føder nettet i kilden, s. Ved løsningen

hvorved den korteste vej fra s til t bliver følgen af grene, hvori flow
er lig 1.

For ikke-orienterede net kan vi som ovenfor erstatte hvert led af to
parallelkoblede grene; vi taler i så kald om den korteste kæde mellem
s og t.

At løse det foreliggende problem med Out-of-kilter er just ikke anbefalelsesværdigt, da andre og langt enklere algoritmer er udviklet specielt til dette formål. Problemet om den korteste vej eller kæde er blot medtaget her som illustration af begrebet duale net og i forbindelse hermed det ovenfor nævnte max-flow fin-cut theorem.

Lad der være givet et plant, ikke-orienteret net med kilden, s, terminalen,t,
og tallet u [x,y] knyttet til leddet [x,y]. Lad endvidere kilde
og terminal være de punkter, der afbildes hhv. længst til venstre og

Eksempel:

længst til højre i nettets graf. Den såkaldte duale graf konstrueres på
følgende måde:

De halvuendelige linier fra kilden mod uendeligt til venstre og fra terminalen mod uendeligt til højre samt grafens øvrige led deler planen i to halvuendelige områder samt et antal endelige områder, der er begrænset af grafens led. Vi markerer et punkt i hvert område og forbinder disse punkter med led, der ikke skaber hinanden; til hvert af de nye led knyttes tallet på det led i det originale net, der blev overskåret. .Det resulterende net kaldes det duale, og dualitetsrelationen ses at være symmetrisk.

Lad Ni. og Ns, være to givne, duale net. Hvis kilde og terminal for Ni er s og t, bliver punkterne i de to halvuendelige områder kilde og terminal for N2. Vi fortolker de tal, der er knyttet til de sammenhørende led, som kapaciteter for led i Ni og længder af led i N2. Betragtes et snit, der adskiller s og t i Ni, vil de tilsvarende led i N2 udgøre en kæde mellem kilde og terminal i N2. Mængden af alle sådanne snit i Ni svarer

til mængden af alle kæder mellem kilde og terminal i N2, og endelig vil snittet med minimal kapacitet i N2 svare til den korteste kæde i N2. De to grafer på figurerne 11 og 12 er duale; begge grafer er indtegnet på figur 13, hvoraf sætningens gyldighed konstateres.

6. Afsluttende bemærkninger.

Algoritmen er kun gennemgået under forudsætning af en brugbar initialcirkulation. Denne forudsætning er imidlertid ikke nødvendig, men blot gjort for at forenkle fremstillingen. Hermed retfærdiggøres tillige, at konstruktionen af en brugbar initialcirkulation intet steds er omtalt; dette vil ofte ikke frembyde noget alvorligt problem, men i særligt komplicerede tilfælde kan vi dog om ikke andet blot sætte al flow lig nul, hvorved

Med en ikke-brugbar initialcirkulation følges ganske de samme principper som beskrevet, idet der blot må betragtes to ekstra tilfælde ved snittets konstruktion. Derimod kan den mulighed foreligge, at en brugbar cirkulation ikke eksisterer.

En nødvendig og tilstrækkelig betingelse for eksistensen af en brugbar
cirkulation er, at

for ethvert X C N

(Hoffmans sætning, se [9] eller [s]).

Dersom denne sætning, der her fremsættes uden bevis, ikke er opfyldt
for et givet net, tilkendegives det ved, at mængderne Q\ og Q2 på
et eller andet tidspunkt bliver tomme. Da

betyder dette, at

eller

og enten

eller

summation fås:

hvilket strider mod eksistenssætningen.

Eksempel:

Snit, for hvilket Hoffmans sætning ikke er opfyldt.

Der eksisterer en meget intim sammenhæng mellem løsningen af et cirkulationsproblem og bestemmelse af strømme og spændinger i et elektrisk netværk. Analogien beror på den fysiske realitet, at dersom man lader problemets data repræsentere af påtrykte strømme og spændinger, da vil strømmene i den elektriske netværksmodel automatisk indstille sig på de værdier, der svarer til den søgte, optimale løsning af cirkulationsproblemet.

Det vil føre for vidt her i detailler at redegøre for disse forhold; det skal blot i korthed nævnes, at der er tale om jævnstrømsnetværk, sammensat af ideelle komponenter, der alle er abstraktioner og derfor kun praktisk realisable med en vis tilnærmelse. De primalé variable repræsenteres af nettets grenstrømme, og de duale variable svarer til potentialerne i nettets punkter. Det duale program fås direkte ved opstilling af simple relationer mellem potentialerne, og endelig konstateres overensstemmelse med Kirchhoffs to love:

At summen af grenstrømmene, der løber til eller udgår fra et punkt
er lig nul, samt at summen af grenspændingerne rundt i en cykle ligeledes
er nul.

Referencer:

[1] Hitchcock, F.: The Distribution of a Product from Several Sources to Numerous
Localities. J. Math. Phys. 20 (1941).

[2] Dantzig, G. B.: Linear Programming and Extensions. Princeton University Press
(1963).

[3] Kantorovich, L.: On the Translocation of Masses. Compt. Rend. (Doklady) Acad
Sci. Vol. 37 (1942).

[4] Koopmans, T. C: Optimum Utilization of the Transportation System. Proc. of the
Int. Stat. Conf., Washington (1947).

[5] Ford, L. R., Fulkerson, D. R.: Flows in Networks. Princeton University Press
(1962).

[6] Ford, L. R., Fulkerson, D. R.: An Out-of-Kilter Method for Minimal Cost Flow
Problems. J. Soc. Indust. Appl. Math. Vol. 9 (1961).

[7] Bellman, R., Dreyfus, S.: Applied Dynamic Programming. Princeton University
Press (1962).

[8] Berge, C: The Theory of Graphs and its Applications. Methuen and Go. (1962).

[9] Hoffman, A. J.: Some Recent Applications of the Theory of Linear Equalities to
Ertremal Combinatorial Analysis. Proc. Symp. on Appl. Math. (1960).