1. Det lineære transportproblem.

Når en virksomhed består af et antal geografisk adskilte afdelinger (fabrikker, hovedlagre etc.), der er beliggende i forskellige byer eller landsdele, bliver det et væsentligt problem for den at planlægge transporterne mellem disse afdelinger således, at de totale transportomkostninger bliver så små som muligt. I mange tilfælde kan denne opgave formuleres og løses som et linea^rt programmeringsproblem.

Lad os først illustrere problemstillingen ved et simpelt eksempel på
det nu klassiske lineære transportproblem.

En virksomhed tænkes at producere den samme vare i 2 forskellige fabrikker, en i Århus og en i København, og skal derfra forsyne 3 hovedlagre (hoveddepoter, pakhuse), der dækker hver sin landsdel. Den samlede produktion pr. uge, henholdsvis 2 og 4 tons, skal fordeles på de tre depoter, der aftager henholdsvis 3, I og 2 tons pr. uge. Opgaven er nu at planlægge transporterne fra fabrikker til depoter - d. v. s. bestemme, hvor meget hver enkelt fabrik skal levere til hvert enkelt depot - på en sådan måde, at de samlede transportomkostninger bliver mindst mulige.

Problemets übekendte kan stilles op i følgende skema, hvor Xij betegner
leverance (i tons pr. uge) fra fabrik i til depot nr. j; der er 2 • 3 = 6
sådanne übekendte at bestemme.

---

1) p. t. Associate Professor, University of Illinois.

Hver af disse variable svarer til en mulig transportrute, som det ses
af nedenstående diagram:

Til hver variabel er der knyttet en omkostningskoefficient oj, der
angiver transportomkostning pr. ton fra fabrik nr. i til depot nr. j, jfr.
flg. tabel:

Det gælder da om at finde minimum af de samlede transportomkostninger, c = 2'j2'jCjjXij, under de restriktioner på Xii'erne, der følger af. at den samlede afsendte mængde for hver fabrik og den samlede modtagne mængde for hvert depot er givet, nemlig som angivet i marginen af den første tabel. Idet c er en lineær funktion af Xij'erne og bibetingelserne er simple summeringer af disse variable (der iøvrigt skal være ikke-negative, idet forsendelserne kun går den ene vej), har vi benbart et lineært programmeringsproblem at gøre:

2. Numerisk løsning af transportproblemet.

a. Problemer af denne type kan naturligvis løses ved hjælp af simplexmetoden, den hyppigst anvendte fremgangsmåde til numerisk løsning af lineære programmeringsproblemer²). Det letter i høj grad beregningerne, at transportproblemets koefficientskema er af en særlig enkel karakter; koefficienterne til Xij'erne i bibetingelserne er nemlig - i kraft af selve problemstillingen - lutter nuller og ettaller, arrangeret på en regelmæssig måde:

og dette går naturligvis igen i det regneskema, der benyttes (simplextavlen for det første beregningstrin). Og på de senere beregningstrin vil koefficienterne i simplex-tavlerne ikke kunne antage andre værdier end 0, +1 og —1, som man let viser i et eksempel.

Et blik på eksemplet viser i øvrigt, at enhver af de 5 ligninger kan udledes af de øvrige, således at problemet kun har 4 uafhængige bibetingelser;adderer man nemlig de to første ligninger — dem, der svarer til fabrikkerne - får man samme resultat som ved addition af de tre ligninger, der svarer til depoterne, nemlig at summen af samtlige variableer lig med den samlede mængde, der skal transporteres. Dette gælder naturligvis helt generelt for problemer af denne type; er der m afsendelses- og n modtagelsessteder, kan (og bør) man udelade en af de m+n bibetingelser, ligegyldigt hvilken, og der skal ikke m+n? men kun m-j-n—l variable til at danne en basis. Idet den optimale løsning skal søges blandt basis løsningerne, betyder dette, at man i optimum højst vil tage m+n- 1 af de rn-n mulige transportruter i

---

2) Se f. eks. Sven Danø, Numerisk løsning af lineære programmeringsproblemer, København 1957 (udg. af Universitetets økonomiske Laboratorium; stencileret), eller Niels Nielsen, „Simplexmetoden", Mercantilia,, nr. 2, 1956.

brug3). Det er vanskeligt at se, hvorledes man kunne være kommet til
dette resultat uden at formulere opgaven som et lineært programmeringsproble
m4).

Ved den numeriske løsning af problemet ovenfor skal man altså begyndemed at finde en initialbasis bestående af m+ n—l=4 variable. Den normale procedure går ud på at tilføje et sæt hjælpevariable (artificial variables), der i omkostningsudtrykket tildeles en vilkårligt stor koeificient M, og bruge dem som initialbasis^fi); men transportproblemetssærligt simple karakter gør det muligt straks at finde en udgangsbasisaf struktuelle variable, hvorved der spares en del beregningstrin.Det sker ved hjælp af den s. k. nordvestregel, der i eksempletgår ud på følgende: Man stiller et Xij-skema op, magen til den første tabel, blot med lutter tomme pladser i skemaets indre, og begyndermed at udfylde det nordvestlige hjørne, pladsen for xn. Den første række i skemaet skal have summen 2, medens den første kolonne skal have summen 3; vi skriver da det mindste af disse tal, 2, på denne plads - den største værdi, xn må have, hvis disse to bibetingelser skal holde. Fabrik nr. 2 må da dække resten af forsyningen til depot nr. 1. d. v. s. vi skriver xl>i = 1; herudover skal fabrik nr. 2 levere 3 tons pr. uge, hvoraf åbenbart 1 går til depot nr. 2 og altså X22 = 1. På denne måde når vi til sidst ned til det sydøstlige hjørne, hvor vi sætter X23 = 2, jfr. nedenstående skema, hvor de blanke pladser markerer nuller (ikke-benyttederuter). Vi har hermed fundet en positiv løsning i 4 variable, der tilfredsstiller bibetingelserne. At regnestykket altid må gå op, følger af, at summen af de afsendte mængder er lig med summen af de modtagne;

---

3) Ved transportproblemer af denne type støder man ikke sjældent på „^{degenererede k} løsninger, hvor der indgår færre end m+n—l positive variable (transportruter) i den optimale kombination.

4) 1 det hele taget kan problemet vanskeligt løses ved common-sense-metoder. Det nytter f. cks. ikke at gå ud fra, at hvert depot skal forsynes fra den nærmest liggende fabrik, for man kommer da let i strid med bibetingelserne.

5) Jfr. Danø. op. cit.. p. 16.

og at en løsning fundet ved denne procedure altid vil være en basisløsning,følger af, at vejen fra det nordvestlige til det sydøstlige hjørne nødvendigvis må passere gennem (og altså udfylde) m+ n—l celler i skemaet, når man kun må bevæge sig ét skridt ad gangen og kun må gå mod syd eller øst.

Løser vi nu det ligningssystem, der udgøres af 4 uafhængige bibetingelser, m. h. t. de 4 basisvariable - hvad der er meget let, da alle koefficienter på venstre side er 1 eller 0 - har vi dermed bestemt koefficienterne i den første simplex-tavle. De videre beregninger vil som nævnt vise sig at være overordentlig simple. Yderligere kan man forkorte proceduren ved et hensigtsmæssigt valg af udgangsbasis, f. eks. ved at nummerere oprindelses- og bestemmelsesstederne således, at nordvestregelen giver en initial basisløsning, der kan formodes at ligge „i nærheden af" optimum.

b. Ved løsning af transportproblemet er det imidlertid overhovedet ikke nødvendigt at benytte simplex-metoden i dens generelle form; problemets specielle karakter gør det nemlig muligt at løse det uden brug af egentlige simplex-tavle⁶). Man kan nemlig se direkte af det ved nordvestregelen udfyldte skema, sammenholdt med omkostningskoefficienterne, hvad løsningen på det følgende beregningstrin bliver, og så fremdeles. Vi skal illustrere fremgangsmåden ved et nyt eksempel med 3 oprindelses- og 5 modtagelsessteder, jfr. følgende tabel, hvor den initiale basisløsning - fundet ved hjælp af nordvestregelen - er indsat.

---

6) Jfr. f. eks. A. Charnes & W. W. Cooper, „The Stepping Stone Method of Explaining Linear Programming Calculations in Transportation Problems", Management Science, Vol. 1, No. 1. October, 1954.

(Denne basisløsning er degenereret, idet kun 5 af tallene i tabellens indre er -fi 0; der skal 3 + 5 — 1 = 7 variable til at danne en basis, og vi skriver da 0 på de to tomme pladser, der passeres fra vejen fra nordvest til sydøst, for at markere, at vi lader de tilsvarende to variable indgå med værdien nul i basisløsningen). De tilsvarende transportomkostningskoefficienter er som følger:

Enhver af de tomme pladser i den første tabel repræsenterer en variabel, der ikke er med i basen, og som altså kan komme på tale som indgående variabel. Lad os f. eks. undersøge, hvad der sker, hvis vi med udgangspunkt i tabellen giver X2l en tilvækst x, medens de øvrige variable udenfor basen fremdeles holdes på nul. Vi skriver altså -fx på X2i's plads:

Nå vi således lægger x til xai (der før var 0), må vi til gengæld trække x fra en basisvariabel i samme række,hvis bibetingelsen i denne række skal holde. Vi sætter da den nye værdi for X23 lig 2 —x; xis må da få et tillæg på x, hvis bibetingelsen for søjle 3 skal holde, og xn må da til gengæld formindskes med x. Herefter passer samtlige bibetingelser igen, og lader vi x vokse, indtil en af de hidtidige basisvariable kommer ned

på nul, får vi dermed en ny basisløsning; det ses at ske for x = 2, og X2l har da erstattet X23 i basen. Men om det er fordelagtigt således at tage X2l ind i basen, er et andet spørgsmål; det afhænger af fortegnet for simplex-koefficienten Z2l. — C2l. Den er meget let at beregne; tabel 5 viser umiddelbart, hvilke variable der berøres af overgangen fra den ene basis til den anden - nemlig dem, på hvis pladser x optræder - og netto-meromkostningen ved at indføre X2l i basen med værdien x bliverda

Simplex-koefficienten Z2l--C2l, der angiver nettobesparelsen regnet
pr. enhed af X2l, bliver derfor

Tilsvarende kan man beregne simplex-koefficienten for hver af de
øvrige variable udenfor basen, og tallene indføres på de tomme pladser
i tabellen; resultatet fremgår af følgende tabel:

På de pladser, der svarer til basisvariable, opføres disses værdier i en cirkel - her af typografiske grunde markeret med en ( ) -. medens de øvrige pladser er udfyldt med simplex-koefficienterne for de respektivevariable. Tabellen kan altså opfattes som en simplex-tavle for det første beregningstrin i kondenseret form. Den største simplex-koefficient - der sættes i en firkant, her markeret med en [ ] -er Z3l — csi = 5, og X3l er følgelig den indgående variabel. Den udgående variabel bestemmessom den af de variable, som først bliver nul, når X3l vokser; idet vi for xsi = x har X34 = 0 — x. ses det, at xsi kommer ind i basen

med værdien nul i stedet for X34 (d. v. s. den ene degenererede basis afløser den anden), og i den nye „simplex-tavle" skal vi altså skrive 0 på X3i's plads, medens pladsen for X34 nu lades blank. Løsningen m. h. t. de øvrige basisvariable går i dette tilfælde uforandret over, idet tilvæksten resp. fradraget x er nul.

Tavle II - den, der svarer til det andet beregningstrin - får vi nu på samme måde ved at indføre den nye basisløsning i en ellers blank tavle og derpå beregne simplex-koefficienterne, og så fremdeles. Således fortsætter vi, indtil der ikke længere forekommer positive simplexkoefficienter, hvilket ses at indtræffe i tavle V⁷). Her repræsenterer de i ( ) anførte tal en optimal basisløsning (ikke degenereret), og den tilsvarende værdi af omkostningsfunktionen ses at blive c = 21:

---

7) Hvis en eller flere simplex-koefficienter i tavle V havde været nul, ville løsningen stadig have været optimal, men der ville da have eksisteret alternative optimale låsninger.

Den optimale kombination af ruter er vist grafisk på figuren nedenfor,
hvor tallene - løsninger m. h. t. Xij'erne - er ført på.

Ved den praktiske beregning af simplex-koefficienterne er det ikke nødvendigt at tilføje +xog —x i de med ( ) betegnede rubrikker, der påvirkes af en tilvækst i Xij. Med lidt øvelse kan man nemlig umiddelbartse, hvilke af basisvariablerne der vil blive påvirket. Princippet er det, at man ud fra xv's plads bevæger sig vandret ud ad den i'nde række til en cirkel, hvorfra man kan gå videre i lodret retning til en anden cirkel, og så fremdeles - skiftevis vandret og lodret - indtil man havner i en cirkel i den j'nde søjle, hvorfra man bevæger sig lodret til Xij's plads. Man skal bevæge sig ad den kortest mulige rute, og de cirkler, hvor man skifter retning, repræsenterer de basisvariable, hvis værdier bliver påvirket, og hvis c'er altså kommer til at indgå med koefficienten +1 eller —1, cl. v. s. med skiftevis positivt og negativt fortegn, ved beregningen af zu — Cij 8). (Det vil være praktisk at notere Cij'erne øverst til venstre i hver rubrik i samtlige tavler, så at man slipperfor hele tiden at skulle „slå op" i omkostningstabellen). Det er hellerikke nødvendigt at udfylde alle pladserne i hver tavle; så snart man har fundet en positiv simplex-koefficient, kan man standse udfyldningenog betragte den pågældende koefficient som den „mest positive", der bestemmer den indgående variabel. Den tidgående variabel er til enhvertid

---

8) Man kan opfatte () som „trædesten", som man benytter med udforskningen af Xjj's omegn (deraf navnet „the stepping stone method"). Eller man kan tænke sig tavlen som et skakbræt, hvor ruterne fastlægges ved operationer med et tårn, begyndende og sluttende i rubrikken Xjj.

hvertidbestemt ved det mindste af de med ( ) anførte tal i den indgåendevariabels rute, der giver et positivt bidrag til dens simplexkoefficient( det er nemlig disse tal, der får tilføjet — x), og tallet angiver tillige den værdi, hvormed den indgående variabel optræder i den næste tavle, altså korrektionsleddet x. De øvrige med ( ) anførte tal i den næste tavle findes ved at addere eller subtrahere dette x i den hidtidige basisløsning, men heller ikke hertil er det nødvendigt at skrive x'erne ned; man begynder med at indsætte tomme ( )'er på de rette pladser, udfylder så de indgående variabels ( ) med værdien for x, og kan herefter udfylde resten af pladserne under hensyn til bibetingelserne(summerne i marginen).

3. Praktiske anvendelser.

Transportplanlægning er et af de områder, hvor man har haft størst succes med praktisk anvendelse af lineær programmering. Det kan f. eks. nævnes⁹), at det amerikanske levnedsmiddelfirma H. J. Heinz Go., der fremstiller tomat-ketchup i 5-6 fabrikker og fordeler produktionen på omkring 70 hoveddepoter spredt over U. S. A., har sparet flere tusind $ i fragtomkostninger pr. halvår ved at gå over til at planlægge transporterne ved lineær programmering; metodens store simpelhed har yderligere gjort det muligt for virksomheden at planlægge på månedsbasis i stedet for kvartalsvis, således at transportplanlægningen i højere grad end hidtil har kunne baseres på de nyeste produktions- og salgsdata.

Problemstillingen dækker en lang række andre praktiske planlægningsopgave r₁₀). Under den anden verdenskrig stod man over for det problem at planlægge transporterne af givne ladninger over Atlanterhavet på en sådan måde, at tonnagen blev udnyttet bedst muligt, udtrykt ved minimal sejltid i ballast — det var denne opgave, der gav stødet til formuleringen og løsningen af det generelle transportproblem - og tilsvarende problemer må nødvendigvis forekomme inden for større transportvirksomheder, både rederier og jernbaneselskaber (dirigering af tomme godsvogne).

En nær beslægtet problemstilling har man, hvor de produktmængder, der skal fremstilles og afsendes fra hver fabrik, ikke er fastlagt på forhånd, men blot skal holdes inden for givne kapacitetsgrænser (d. v. s. den ene gruppe af bibetingelser bliver uligheder); opgaven går da ud på

---

9) Jfr. A. Henderson & R. Schlaifer, ,^Mathematical Programming: Better Information for Betler Decision Making", Harvard Business Review, May-June 1954, p. 78.

10) Se f. eks. op. cit., pp. 79 ff.

at planlægge produktion og transport onder ét på en sådan måde, at de samlede produktions- og transportomkostninger skal være mindst mindst mulige. Herved bestemmer man alts. samtidigt, hvor meget hver fabrik skal producere, og hvilke depoter der skal forsynes fra hvilke fabrikker. Det ovennævnte amerikanske firma (Heinz C0..) benytter også lineær programmering på opgaver af denne type. En lignende problemstilling har man, når en virksomhed skal planlægge indkøb og transport af råmaterialer, der købes hos forskellige leverandører i forskelligelandsdele og skal fordeles til de forskellige fabrikker, virksomhedenejer, på en sådan måde, at indkøbs- plus transportomkostningerbliver så små som muligt. Det amerikanske forsvarsministerium angives at have sparet betydeligt beløb i transportomkostninger ved at løse sådanne problemer ved hjadp af lineær programmering. Endvidere kan man komme ud for, at også de bibetingelser, der refererer sig til modtagelsesstederne, har form af uligheder, nemlig når den samlede produktion og dens fordeling på depoter (d. v. s. salget og dets geografiskefordeling) såvel som på fabrikker ikke er eksakt fastsat på forhånd; i dette tilfælde får man et maksimumsproblem, idet man skal maksimere den samlede salgsindtægt minus variable produktions- og transportomkostninger.

Det kan endelig nævnes, at ethvert programmeringsproblem, der kan stilles op i en tabel som ovenfor - med en bestemt vurderingskoefficient knyttet til enhver kombination af et „input" og et „output" (i videste forstand) - formelt kan stilles op og løses som et transportproblem¹¹). Det gælder f. eks. visse typer af blandingsproblemer, og det gælder sådanne problemer som det at beregne, hvorledes man skal fordele et givet sæt produktionsordrer på et antal fabrikker (anlæg), der alle fremstiller de pågældende produkter under givne, kapacitetsbegrænsninger, når de samlede produktionsomkostninger for fabrikkerne under ét skal være minimum, eller det at fordele (allokere) givne mængder af et antal råstoffer på et antal fabrikker, når disses samlede overskud skal maksimeres¹²).

---

11) Jfr. nærmere op. cit., pp. 98 f.

12) Et konkret eksempel (et antal olieraffinaderier, der udnytter de samme råolier) findes i G. H. Symonds, Linear Programming: The Solution of Refinery Problems, New York 1955 (udg. af Esso Standard Oil Co.), kap. 9.