Om numerisk løsning af "degenererede" lineære programmeringsproblemer.¹)

1. Ved løsning af lineære programmeringsproblemer støder man undertiden på det s. k. de generations fænomen. Ifølge fundamentalteoremet for lineær programmering vil der - forudsat at optimale løsninger overhovedet findes — altid eksistere en optimal basisløsning, d.v.s. en løsning i m variable, hvor m er antallet af bibetingelser, og ved den praktiske procedure (simplex-metoden) kan man derfor nøjes med at undersøge basisløsninger.

I de fleste tilfælde vil samtlige m variable i en basisløsning være i= o, men det sker dog af og til, at der på et eller andet trin optræder et eller flere nuller i løsningen under kolonnen P_o i simplex-tavlen, og den pågældende basisløsning siges da at være degenereret³). Det kan forekomme allerede på første trin, nemlig hvis der optræder nuller på højre side af bibetingelserne i deres oprindelige form (de tilsvarende rest- eller hjælpevariable i den første basis vil da blive nul), eller det kan indtræffe senere i beregningerne; hvis det nemlig på et eller andet trin sker, at to (eller flere) basisvariable sætter den samme laveste overgrænse for den indgående variabel, vil de begge (resp. alle) blive nul i den følgende basisløsning, uanset hvilken af dem man formelt betragter som udgående variabel.

---

1) Om løsningsproceduren i almindelighed 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, hvilken sidste også giver en mere udførlig fremstilling af degenerationsproblemet.

2) Cand. polit., p.t. Associate Professor, University of Illinois.

3) Degeneration forekommer sjældent i konkrete praktiske problemer, undtagen ved transportproblemet.

2. Antag f. eks., at vi har følgende problem4):

Simplex-tavlerne for de tre første beregningstrin ser ud som følger:

I tavle II er der frit valg mellem X4 og xs som udgaende variabel, idet de begge ssetter greensen 1 for den indgaende variabel X2. Lad os f. eks. vaslge x->.; resultatet bliver da som vist i tavle 111. I denne basislosning er der kun 1 variabel, der er ¥= 0, saledes at losningen er degenereret; ikke blot den udgaende variabel xa, men ogsa X4 er blevet nul. Men vi beholder formelt X4 i basen, blot altsa med vaerdien nul, da vi ellers ville afskaere os fra at fortsaette beregningerne. Simplex-kriteriet er jo ikke tilfredsstillet i tavle 111, og vi skulle derfor gerne kunne arbejde os videre skridt for skridt gennem nye basislesninger, indtil vi stoder pa en, der er optimal.

Vi regner da videre fra tavle 111. Med xi som indgående variabel bliver
det nu X4, der skal ud. Ganske vist udelukker dette, at xi kommer ind med

---

4) Læseren bør selv regne eksemplet igennem.

nogen positiv værdi; X4 er nul i forvejen og sætter derfor grænsen nul for xi - positiv xi ville gøre X4 negativ i den næste basisløsning - men dette betyder blot, at vi indfører xi som nulvariabel i basen i stedet for den hidtidige nulvariabel X4. Vi kommer da til en ny degenereret basisløsning,jfr. tavle IV.

Simplex-kriteriet er nu tilfredsstillet, og løsningen i tavle IV er altså
optimal.

Vi bemærker, at basisløsningerne i de to sidste tavler i virkeligheden
er identiske, idet de begge er ensbetydende med den degenererede løsning
i 1 positiv variabel5)

alle andre variable er lig med nul, og det gør ingen reel forskel, om man formelt betragter en hvilken som helst af dem som en basisvariabel, der indgår i basisløsningen med værdien 0. Heraf følger, at allerede løsningen i tavle 111 var optimal til trods for, at simplex-kriteriet ikke var tilfredsstillet; eksemplet illustrerer således, at kriteriet ikke er en nødvendig betingelse for optimum, når basisløsningen er degenereret⁶). Dette voldte imidlertid ingen vanskeligheder i beregningerne, idet vi blot fortsatte til en ny basis (tavle IV), hvor alle simplex-koeffienter viste sig at være positive, og som derfor med sikkerhed var optimal, idet simplex-kriteriet altid er en tilstrækkelig betingelse for optimum.

3. Den omstændighed, at der på et vist trin optrådte degeneration, hindrede os altså ikke i at nå frem til en optimal løsning ved den normalesimplex-procedure, og tilsyneladende skulle degeneration således ikke byde på nogensomhelst beregningsmæssige vanskeligheder. Imidlertider der ved degeneration - men også kun da - altid en teoretisk mulighedfor,

---

5) At der må eksistere degenererede løsninger, ses umiddelbart af, at Pq er proportional med P' 2 i tavle I; dette viser jo, at det er muligt at tilfredsstille bibetingelserne ved at tage kun 1 variabel „i brug", nemlig X2.

6) Jfr. Sven Danø, „Lineær programmering", Nordisk Matematisk Tidsskrift, 1956, p. 130 n. - Pointen er, at selv om simplex-koefficienten Zj-cj i tavle 111 viser, at løsningen kunne forbedres, hvis xj kunne „tages i brug", så er dette ikke muligt, fordi det ville gøre X4 negativ.

hedfor,at proceduren ikke fører frem, selv om det i de allerfleste tilfælde vil gå godt. Når man arbejder sig igennem en serie degenererede basisløsninger,der er identiske på nær den variabel, der formelt indgår i basisløsningenmed værdien nul (jfr. tavle 111 og IV ovenfor), kan det nemlig ske, at en af disse baser vender tilbage, før man er nået frem til en løsning med lutter positive simplex-koefficienter, hvorefter den samme serie gentages i det. uendelige. Proceduren kører da i ring og fører ikke til målet i løbet af et endeligt antal trin.

Man kan imidlertid vise, at risikoen for dette cirkulationsfænomen („cycling") kan udelukkes ved et hensigtsmæssigt valg af udgående variabel i de tavler, hvor der er flere at vælge imellem som følge af, at flere variable sætter den samme laveste overgrænse for den indgående variabel (jfr. ettallerne i marginen ud for tavle II). Hvor det således „står lige" mellem to eller flere kandidater, vælger man den, der giver den laveste værdi for kvotienten xn/xik, d.v.s. forholdet mellem tallet under kolonne Pi og det tilsvarende tal i den indgående variabels kolonne, Pk.⁷) Er der herefter stadig flere kandidater går man videre til kolonne P2 og beregner for hver af dem kvotienten Xi2 fxik, etc. etc., indtil alle kandidater er blevet elimineret på nær én, som da bliver den udgående variabel. Den bliver normalt bestemt allerede i kolonne Pi eller P2.

Anvendt på tavle II ovenfor indebærer denne regel følgende: Idet X2 er den indgående variabel, er der 2 muligheder m. h. t. valget af den udgående, idet xi fx^ — X3 fX32 = 1. Vi erstatter da tællerne (fra Po) med de tilsvarende elementer fra Pi og får: X4l fX42 = 71'2,7₁'2, X3l fX32 =1 f_2, som noteres i marginen; det sidste tal er lavest, altså skal X3 være udgående variabel.

Følger man denne simple tommelfingerregel⁸), er man altid på den sikre side. Som regel vil simplex-proceduren også føre frem, selv om man vælger den udgående variabel på anden måde blandt de mulige kandidater, f. eks. tilfældigt; man skal være meget uheldig, for at der indtræder cirkulation (i eksemplet ovenfor vil det således ikke kunne ske, selv om man vælger X4 i tavle II). Men man kan lige så godt anvende regelen, når den jo dog uden mindste besvær giver et kriterium, der så at sige gratis sikrer mod enhver risiko for, at simplex-proceduren ikke skulle være konvergent.

---

7) Den laveste kvotient kan godt være negativ.

I Sven Danøs artikel i E.T. nr. 2, 1958: Om transportplanlægning ved hjælp af lineær
programmering har der grundet på forf. bortrejse indsneget sig et par misforståelser:

1. Tegningerne på side 74 og side 81 er ombyttede.

2. Overskrifterne over de pa side 77-80 opstillede tabeller er trykt som M^Tavle 1" o.s.v. Denne overskrift skulle have va:ret stroget, idet man i givet fald kan forveksle de tre forste med „tavle" betegnede tabelopstillinger med simplextavlerne pa side 79 og 80, der lober fra I til V.

Red.

---

8) Regelen, der skyldes A. Charnes, er udledt af en modificeret simplex-procedure, der gar ud pa at „vride" problemstillingen ganske lidt, idet Pq erstattes med P(j£ + Pi£² + + Pn£ⁿ _' hvor ceret meget lille: posiiivt (men uspecificeret) tal. Loser man dette udvidede problem - hvoraf det oprindelige problem er specialtilfaeldet e = 0 - vil man se, hvorledes degeneration og dermed risikoen for cirkulation er elimineret pa ethvert trin; graenserne i marginen ud for tavlerne kan aldrig falde sammen, da de kommer til at indeholde hvert sit forskellige polynomium i £. (I tavle II bliver graenserne henholdsvis 1 + 7lz £ -f- ... og 1 + %£ + ...; deter koeffecienterne i disse polynomier, der noteres i marginen til hojre). Polynomierne domineres af de led, der er af lavest grad; som regel er allerede 1. - eller 2. grads leddenes koefficienter - der viser sig at vasre x^/x^ resp. x^/xj^, jfr. ovenfor - tilstraekkelige til at bestemme den laveste graense. Den optimale tasning til det udvidede problem svarer, med e sat == 0, til den optimale lesning til det oprindelige problem. Det anbefales laeseren at bse det saledes udvidede problem; det vil da blive klart, hvorfor det ikke er nedvendigt at skrive £*erne op.