I. Problemstilling og eksempel.

(a) Et lineært programmeringsproblem går som bekendt ud på at finde maksimum af en lineær funktion under lineære betingelser, når det tillige kræves, at de variable kun må antage ikke-negative værdier. Kvadratisk programmering er noget mere generel, idet den funktion, der skal maksimeres (præferencefunktionen), tillige indeholder led af 2. grad; bibetingelserne derimod er fremdeles lineære, og de variables variationsområde er begrænset til det ikke-negative område. Som ved lineær programmering kan bibetingelserne være enten lineære ligninger eller lineære uligheder; det spiller heller ingen rolle, om præferencefunktionen skal maksimeres eller minimeres, idet min f = max (— f).

(b) Antag som et eksempel, at 2 varer fremstilles i fælles produktion
i hver sin lineære proces (aktivitet) under 2 kapacitetsbegrænsninger

(1)

(2)

idet begge produkter fremstilles ved hjælp af de samme to maskiner. Ulighed (l) tolkes derhen, at hvert af produkterne forbruger 1 maskintimepr. enhed på maskine nr. 1; venstresiden betegner da samlet maskintimeforbrugpå denne maskine, når der fremstilles xi og x2x₂ enheder pr. periode. Højresiden angiver overgrænsen for det mulige maskintimeforbrug(disponible maskintimer pr. periode). (2) tolkes tilsvarende

*) Dr. polit., professor ved Københavns Universitet.

1) Denne artikel bringer ikke meget egentlig nyt, men er tænkt som en oversigt over problemstillingen og de vigtigste løsningsmetoder.

for maskine nr. 2, blot er produkt nr. 2 her mere tidskrævende pr. enhed
(produktionskoefficienten er =2) end det første produkt (koefficient l).

Enhver mængdekombination (x1} X2), der tilfredsstiller (l) — (2),
repræsenterer nu en mulig løsning af virksomhedens produktionstilpasningsproblem
- forudsat at den også opfylder kravet

(3 a - b)

da negative løsninger til (l) — (2) ikke har nogen mening.

Virksomhedens optimeringsproblem består da i at finde den - eller de - blandt løsningerne til (1) —(3), som er bedst i henseende til virksomhedens præferencekriterium. Går dette ud på at opnå størst mulig (korttids-) gevinst, så er problemet det at maksimere gevinstfunktionen

(4)

hvor pi og p2 er de priser, hvortil produkterne kan afsættes, medens c\ og c2c₂ er omkostningsfunktionerne. Dersom nu priserne på de variable produktionsfaktorer er konstante, og forudsætter vi som ovenfor faste produktionskoefficienter, bliver omkostningsfunktionerne lineære; lad f. eks. de variable stykomkostninger være henholdsvis 4 og 3. Hvis også salgspriserne er givne, uafhængige af produktionsomfanget — f. eks. pi = 10, p2p₂ = 9 - bliver gevinstfunktionen (4) lineær i X\ og x2x₂ med konstante dækningsbidrag pr. stk.:

(4a)

og vi har et simpelt lineært programmeringsproblem.

Hvis derimod salgspriserne afhænger af de afsatte mængder, bliver de to første led i (4) ikke længere lineære funktioner af henholdsvis xi og x₂, og dækningsbidragene bliver ikke længere konstante. Vi har da et ikke-lineært programmeringsproblem. Der findes (endnu) ikke nogen generel metode til matematisk og numerisk løsning af sådanne problemer for ikke nærmere specificerede præferencefunktioner, men for det specielle tilfælde, at præferencefunktionen er kvadratisk, er der i de senere år fremkommet en række løsningsmetoder, en naturlig videreudvikling af den lineære programmeringsteknik.

Præferencefunktionen (4) ovenfor ses at blive kvadratisk, hvis salgspriserne
afhænger lineært af de afsatte mængder. Har vi f. eks. afsætningsfunktionerne

får vi

(4b)

(Mere generelt kunne såvel som X2 afhænge lineært af både pi og p 2, således at hver af priserne kunne udtrykkes som en lineær funktion af begge mængder; dette ville give anledning til et ekstra led i (4b) indeholdende produktet xix₂). Det er klart, at forudsætningen om retlinede afsætningsfunktioner kan være problematisk, men den vil dog give en bedre approksimation til virkeligheden end forudsætningen om konstante priser, når afsætningsfunktionerne vides at være faldende.

(c) Vi skal nu til indledning give en geometrisk illustration af det
kvadratiske programmeringsproblem at finde maksimum af (4b) under
bibetingelserne (1) — (3).

Mulighedsområdet, som defineret ved (1) — (3), bliver naturligvis af samme karakter som ved lineær programmering, nemlig polygonen OGPB i fig. 1, hvor AB og CD repra^senterer de grænser, der sættes af (1) og (2), medens akserne svarer til (3). Forskellen ligger i præferencefunktionen. Medens (4a) repræsenterer en skare parallelle rette linjer med gevinsten z som parameter, bliver det geometriske billede af (4b) en skare koncentriske ellipser, hver svarende til en bestemt værdi af gevinsten z. Skriver vi nemlig (4b) som

der kan omformes til

får vi, idet k — 28,5 — z er en parameter,

der er formlen for en ellipse med centrum i Q = (4, 2i) og akserne 2-Vk og Z-VkJz = } f2k. For z=o, d.v.s. k= 28,5, fås en ellipse, der går gennem nulpunktet (ingen produktion, ingen gevinst), som vist i fig. 1; en højere værdi af z giver en mindre isogevinst-ellipse, og for den største gevinst, der kan opnås - d.v.s. z = 28,5 - skrumper ellipsen sammen til et punkt, nemlig det fælles centrum. Alle ellipserne ses at være ligedannede2).

---

2) Havde der været et led med x±x₂ i gevinstfunktionen - jfr. ovenfor - ville ellipsernes akser ikke have været parallelle med koordinatakserne.

Når der som her kun er 2 variable, kan man i princippet altid løse problemet geometrisk ved at indtegne tilstrækkeligt mange ellipser på figuren; den »højeste« af disse isogevinstkurver, som har et punkt fælles med mulighedsområdet, repræsenterer optimum - i eksemplet ellipsen svarende til z= 27, der tangerer mulighedsområdets grænse i punktet 5=(3,2), således at den optimale løsning er xi=S, x₂=2³). Denne løsningsprocedure er dog umådeligt besværlig - den er ulige simplere ved lineær programmering, hvor isogevinstkurverne er parallelle rette linjer - og giver kun en grov tilnærmelse, foruden at den er uanvendelig ved flere end 2 strukturvariable; den er kun egnet til at illustrere problemets og løsningens karakter. Hvad vi har brug for, er en generel matematisk og numerisk løsningsprocedure.

II. Kuhn-Tucker kriteriet.

(a) Dersom problemets lineære bibetingelser (1) —(2) havde været
ligninger i stedet for uligheder og der ikke havde været nogen fortegnsbegrænsninger(3),

---

3) Havde det absolutte maksimum for gevinsten - punktet Q = (4, 2J) - ligget i mulighedsområdet, ville dette punkt naturligvis have repræsenteret optimum. Begrænsningerne (1) og (2) ville da ikke have været effektive.

begrænsninger(3),kunne optimeringsproblemet uden besvær have væretklaret ved hjælp af de klassiske metoder til maksimering under bibetingelser:enten ved at benytte bibetingelserne til at eliminere et tilsvarendeantal variable i præferencefunktionen og da maksimere denne uden bibetingelser (d.v.s. sætte de partielle differentialkvotienter m.h.t. de uafhængige variable = O)⁴), eller - mere generelt - ved hjælp af Lagrange-metoden⁵). Skal man maksimere en funktion g (#1,3:2,_• •,#») under bibetingelserne fh(xi,X2,- ■xn)=o (h=1,2,. „m<n), fås de nødvendigebetingelser for maksimum ved partiel differentiation af Lagrange-funktionen

hvilket giver betingelserne

d.v.s. ?i-\-m ligninger (hvoraf de sidste m er identiske med bibetingelserne)
til bestemmelse af de n-\-m variable xj og Uh.

Men disse metoder bryder sammen, når bibetingelserne - eller blot nogle af dem - har form af uligheder, eller der er pålagt de variable ikke-negativitetsbetingelser. Hvis vi på forhånd vidste, hvilke af dem der er »bindende«, d.v.s. eksakt opfyldt med lighedstegn i optimum - i det foreliggende tilfælde (l), idet optimalpunktet S på fig. 1 ligger på begrænsningen (1) - kunne problemet løses ved klassiske metoder, nemlig ved at maksimere z under kun disse bibetingelser (i ligningsform); de øvrige bibetingelser kunne lades ude af betragtning som overflødige,da de ikke repræsenterer effektive begrænsninger. Punktet S kunne således findes ved maksimering af z for Xi+x₂=5, d.v.s. ved at indsætte xi =5—X2 i funktionen z og differentiere m.h.t. x₂. Men pointener, at vi netop ikke har en sådan forhåndsviden at gå ud fra ved løsningaf

---

4) I det foreliggende specielle tilfælde ville der dog kun være et enkelt punkt, der opfylder begge bibetingelser (l)- med lighedstegn, nemlig x₁ — 2, x2x₂ = 3 (punkt P i fig. 1), således at der ikke ville være noget maksimeringsproblem (intet variationsområde, indenfor hvilket man søger et maksimum).

5) Se f. eks. Sven Danø, Industrial Production Models, Wien & New York: Springer- Verlag, 1966, Appendix I, pp. 190 ff.

ningafkvadratiske programmeringsproblemer. Man kunne forsåvidt sige, at løsningsproceduren netop består i at finde ud af, hvilke begrænsningerder er eksakt bindende; når man først ved det, går resten af sig selv⁶).

(b) Det lader sig imidlertid gøre at anvende Lagrange-metoden i noget modificeret form på problemer, hvor bibetingelserne er uligheder og de variable kun må antage ikke-negative værdier. Denne metode, der skyldes Kuhn og Tucker⁷), giver ikke umiddelbart nogen numerisk procedure (algoritme) til at finde den optimale løsning til et konkret problem; den giver derimod et kriterium til at afgøre, om en løsning, som man på en eller anden måde har fundet frem til, nu også repræsenterer et optimum. Kuhn—Tucker kriteriet er desuden, som vi skal se, udgangspunktet for flere af de algoritmer, der er blevet udviklet til løsning af kvadratisk programmering.

Lad problemet være at maksimere funktionen g{x\,x₂,- -,x_n) under bibetingelserne fh(xi,X2,_■ -,xn^o (h=1,2,. „m) og Xj^O (7= 1,2,- -,n), hvor g og fh er differentiable, men i øvrigt uspecificerede funktioner. Vi kan da opskrive Lagrange-funktionen

Nødvendige betingelser for maksimum af g under de nævnte bibetingelser
er da:

(5)

(6)

(de samme betingelser som for et saddelpunkt af L: maksimum m.h.t.
Xj, minimum m.h.t. Uh, for Xj og Uh 8). Da nogle af disse betingelser

---

6) Den løsningsmetode, der er omtalt i afsnit 111 nedenfor (Theil-van de Panne's metode), er netop baseret på denne tankegang.

7) Jfr. H. W. Kuhn & A. W. Tucker, »Nonlinear Programming«, pp. 481-492 i J. Neyman (ed.), Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probalitity, Berkeley & Los Angeles: University of California Press, 1951. For en simpel fremstilling se Danø, op.cit., Appendix I, pp. 200 ff.

8) Er nogle af bibetingelserne ligninger (f/, = 0), behøver de tilsvarende %'er ikke være 0, og de tilsvarende betingelser i (6) bliver da simpelthen BL/8u;_t=f/_t =0 ligesom ved den klassiske Lagrange-metode.

er uligheder, kan man ikke -- som ved den klassiske Lagrange-metode - uden videre regne sig frem til den optimale løsning, når man kender funktionernes form; men når man Jtiar et eller andet punkt i mulighedsområdet - d.v.s. et sæt værdier af x ferne, der tilfredsstiller bibetingelserne - kan man undersøge, om der eksisterer et sæt Lagrangemultiplikatoreriih^O, der sammen med løsningen for Xj opfylder (5) — (6).

Anvendt på eksemplet ovenfor bliver Lagrange-funktionen

og Kuhn-Tucker betingelserne (5) — (6) bliver da

(sa)

og

(6a)

Lad os prøve, om punkt S =(3,2) i fig. 1 ovenfor opfylder disse betingelser.
Når x\ og x2x2 begge er positive, kan (sa) kun være tilfredsstillet
for

og

for x1 =3, x2~2 har vi da

hvoraf

De saledes bestemte vaerdier af u\ og Us sammen med de givne vaerdier
af xi og x% ses at tilfredsstille samtlige betingelser i (sa) — (6a), de nodvendige
betingelser for maksimum.

Kuhn-Tucker betingelserne (5) — (6) er også tilstrækkelige for et (globalt) maksimum af g under bibetingelserne fa^o og x^o, hvis præferencefunktionen g såvel som funktionerne fh er konkave for xy^O, d.v.s. hvis funktionerne har en sådan form, at lineær interpolation mellem to vilkårlige punkter af funktionen i området aldrig overvurderer funktionsværdien. (For minimum af g under de samme bibetingelser er betingelserne (5) — (6) nødvendige og tilstrækkelige, hvis funktionerne fh er konkave, men g konveks - d.v.s. at lineær interpolation aldrig undervurderer funktionsværdien - idet man da blot skal maksimere funktionen {—g), der er konkav).

Præferencefunktionen i vort kvadratiske programmeringsproblem,

(4b)

består dels af lineære led, dels af en kvadratisk form i xi og x2, hvor
andengradsleddene har negativt fortegn. Et udtryk af denne art kan let
vises at være konkavt.

Som det ses af fig. 2, er funktionen y^x² konveks, medens —y = —x2 er en konkav funktion. Mere præcist: for to vilkårlige værdier af x indenfor definitionsområdet, x oglx giver lineær interpolation på y=x~ værdien

medens den sande funktionsværdi for samme x = ##+(1— d) x bliver

idet vi far

ses det, at interpolationen aldrig undervurderer funktionsværdien, d.v.s. funktionen er konveks. På tilsvarende måde ses funktionen —x2 at være konkav. Det kan endvidere vises ud fra definitionen, at en linearkombination (med positive koefficienter) af konvekse, henholdsvis konkave, funktioner er konveks resp. konkav. Idet en lineær funktion er både konveks og konkav (et grænsetilfælde af begge), ses (4b) at være konkav. De lineære funktioner i bibetingelserne,

er ligeledes konkave. Heraf følger, at punktet, xi —3, x₂—2, der tilfredsstiller Kuhn-Tucker betingelserne (5) — (6), repræsenterer den største værdi af gevinsten z indenfor mulighedsområdet, z=27, og altså er den optimale løsning⁹).

---

9) Mere generelt bestir praeferencefunktionen ved kvadratisk programmering af lineaere led plus en kvadratisk form n n Q = JS 2 c_kjx_{k Xj,} der ogsa indeholder led med produkterne xx_{k Xj} (k^j). Det bliver da vanskeligere at se, om den er konveks eller konkav i hele definitionsomradet, eller ingen af delene. Det gaslder her, at hvis den kvadratiske form er positiv se?nidefinit, d.v.s. hvis (2^o for alle xx_{k ,Xj} i definitionsomradet, sa er formen -og dermed ogsa prasferencefunktionen - konveks; er den kvadratiske form negativ semidefinit, d.v.s. Q 0, er den konkav. (Hvis yderligere Q kun kan blive 0 for alle x/x_/{,Xj —0, sa at formen er positiv resp. negativ definit, er den strengt konveks resp. strengt konkav, d.v.s. lineaer interpolation vil altid overvurdere henholdsvis undcrvurdere funktionsvasrdien; dette ses at vaere tilfseldet med de to funktioner i fig. 2 ovenfor). For bevis se S. Vajda, Mathematical Programming, Reading, Mass.: Addison-Wesley Publ. Co., 1961, pp. 222 f. For at undersoge, om en given kvadratisk form erf. eks. positiv semidefinit og dermed konveks, kan man prove at omskrive den pa falgende made. Har vi f. eks. formen Q = 5x^^{l-~16l -~l6x} _ii ^x ₂+13x₂₂₂ ² (Vajda, op.cit., p. 223), kan vi forsoge at skrive den isom en sum af kvadrater af homogene linesere udtryk: Q = {ax^ + bx^ + {cx_r\-dx^. Vi kan abenbart straks sastte a = 1 og c = 2 (koefficienten til x,² s'kal jo blive 5); ved kvadrering og ordning fir vi da Q= sx^ + (2b + 4d)x_xx₂ + (b2+d^z)x₂*, hvor koefficienterne til de sidste to led skal vsere = —16 og 13, saledes at vi far 2 ligninger til bestemmelse af bog d. Der bliver 2 lasninger: (b,d) = (— 2,-3) og (b,d) = (— 6/5, —17/5); begge sact kan bruges. Med det forste saet far vi Q = (x_t-2x₂)² + (2x₁~3x₂)^a. Idet begge kvadratled har positivt fortegn, er Q >0 for alle vjerdier af x_{ og x₂, og vaerdien 0 antages kun for xx_{1 —x2=o.x 2}=0. Formen er altsa positiv definit og dermed strengt konveks. Deter dog ikke altid, at en sadan omskrivning lykkes; ikke enhver kvadratisk form er positiv eller negativ semidefinit, endsige definit.

III. Kombinatorisk løsning og Theil-van de Panne's melode.

(a) Som vi har set, giver Kuhn-Tucker betingelserne et kriterium til at afgøre, om et bestemt punkt i mulighedsområdet repræsenterer en optimal løsning eller ej, men ingen anvisning på, hvordan man skal nå frem til et sådant punkt. Dette svarer ganske til, at simplex-kriteriet i lineær programmering (der kan opfattes som et specialtilfælde af Kuhn og Tucker's kriterium) må suppleres med en numerisk algoritme (simplex-metoden), før problemet kan siges at være løst10).

Det blev nævnt ovenfor, at hvis vi blot kunne finde frem til, hvilke af bibetingelserne (l) — (3) der er bindende - d.v.s. opfyldt eksakt med lighedstegn - i optimalpunktet¹¹), er problemet i realiteten løst, idet man da kan benytte den klassiske Lagrange-metode på disse bibetingelser og ignorere de øvrige. Denne observation kan direkte udnyttes ved, at man systematisk undersøger alle tænkelige kombinationer m.h.t, hvilke betingelser der er bindende; for hver kombination beregnes løsningen m.h.t. xi og x2x₂ og den tilsvarende værdi af z, og den løsning, der giver den største værdi af z og tilfredsstiller de ikke-bindende bibetingelser (med ulighedstegn), repræsenterer da optimum.

I eksemplet ovenfor - jfr. også fig. 1 - er der følgende muligheder m.h.t. optimalpunktets beliggenhed: punktet kan enten ligge i mulighedsområdets indre, d.v.s. ingen af bibetingelserne (1) —(3) er bindende, eller det kan ligge et sted på randen af mulighedsområdet OCPB, d.v.s. i et punkt, hvor mindst 1 bibetingelse er eksakt opfyldt. Andre muligheder er der ikke.

Vi skal da systematisk undersøge følgende muligheder:

(i) Hvis ingen af bibetingelserne er bindende, bliver løsningen det
punkt, hvor z har maksimum uden begrænsninger. Dette punkt er karakteriseret
ved, at de partielle differentialkvotienter af z er = 0:

---

10) For en almindelig behandling af kvadratisk programmering og de forskelligc l«sningsmetoder se f. eks. John C. G. Boot, Quadratic Programming: Algorithms - Anomalies - Applications, Amsterdam: North-Holland Publ. Co., 1964; W. S. Dorn, »Non-Linear Programming: A Survey«, Management Science, Vol. 9, 1963; H. P. Kiinzi & W. Krelle, Nichtlineare Programmiening, Berlin: Springer- Verlag, 1962; S. Vajda, Mathematical Programming, Reading, Mass.: Addisnn- Wesley Publ. Co., 1961, Ch. 12; og S. Vajda, Readings in Mathematical Programming, Second ed., London: Pitman & Sons, 1962. - Desuden de nedenfor naevnte specialartikler om de enkelte losningsprocedurer.

11) At en bibetingelse er bindende, kan ogsa - som i lineaer programmering - udtrykkes pa den made, at dens restvariabel er = 0.

deraf fås

(7)

hvilket svarer til punkt Q på fig. 1, ellipsernes fælles centrum. Punktet ses at overtræde (l), idet xi + x2=6,57>5,x₂=6,57>5, såvel som (2) og må altså forkastes. Vi må da undersøge de løsninger, der fås ved at maksimere under 1 eksakt bibetingelse.

(ii) Hvis (l) er bindende, skal vi finde maksimum af z for #i + #2=5 (eller fi=s —#1— #2=o). Vi kan da sætte f. eks. #i=s —#2 i gevinstfunktionen og maksimere den m.h.t. den resterende frie variabel (#2), eller vi kan med samme resultat benytte Lagrange-funktionen

hvor u\ er en Lagrange-multiplikator. Det giver

hvoraf

der med (l) giver løsningen

(8)

jfr. punkt S på fig. 1, hvor ellipsen z--27 tangerer begrænsningen AB. Dette punkt ses at opfylde også den anden begrænsning, (2), idet #i + 2#2=7<B, såvel som (3); det tilhører altså mulighedsområdet og kan derfor komme i betragtning.

Med bibetingelsen (2) alene får vi Lagrange-funktionen

der på tilsvarende måde fører til løsningen

(9)

der svarer til punkt R på fig. 1. Dette punkt må forkastes, idet
xi-\-x2=35/6'>s, således at (1) er overtrådt.

Med (3a) som eneste bindende bibetingelse skal vi maksimere z for
#i = 0, hvilket giver

(10)

d.v.s. punkt T, der tilhører mulighedsområdet.

For (3b) bindende fås tilsvarende det ligeledes mulige punkt U, d.v.s.

(11)

(iii) Endelig må vi undersøge de punkter, hvor 2 bibetingelser samtidig er bindende, d.v.s. hvor 2 af mulighedsområdets grænselinjer skærer hinanden. (Der findes i eksemplet ingen punkter, hvor mere end 2 af dem skærer hinanden; ellers skulle disse muligheder også have været taget i betragtning). Hvert af disse punkter er bestemt entydigt ved løsning af de pågældende 2 ligninger, således at der ikke bliver noget maksimeringsproblem. Løsningerne bliver:

(12)

(13)

(14)

(15)

(16)

(17)

Af de 11 løsninger (7)-(l7) må de 4 kasseres som liggende udenfor rnulighedsområdet; af de resterende 7 mulige løsninger ses (8), altså punkt S, at repræsenterer den største værdi for z, således som vi også fandt ovenfor.

(b) En sådan kombinatorisk common-sense procedure bliver for besværlig,når der er flere bibetingelser end i vort eksempel, men danner udgangspunktet for en løsningsmetode, der er udviklet af Theil og van de Panne¹²). Dene metode begynder ligesom proceduren ovenfor med at undersøge det frie maksimum, hvor 0 bibetingelser er bindende opfyldtl3).Ligger det i mulighedsområdet, er problemet løst; hvis ikke,

---

12) Jfr. Henri Theil & G. van de Panne, »Quadratic Programming as an Extension of Classical Quadratic Maximization«, Management Science, Vol. 7, 1960. - Se også J. C. G. Boot, »Notes on Quadratic Programming: The Kuhn-Tucker and Theil-Van de Panne Conditions, Degeneracy, and Equality Constraints«, Management Science, Vol. 8, 1961; »On Trivial and Binding Constraints in Programming Problems«, Management Science, Vol. 8, 1962; og »Binding Constraint Procedures of Quadratic Programming«, Econometrica, Vol. 31, 1963.

13) Heri adskiller metoden sig fra den lineære simplex-metode og fra de nedenfor omtalte algoritmer for kvadratisk programmering, der alle starter i et punkt i mulighedsområdet (et »feasible point«), sædvanligvis nulpunktet.

undersøger man maksimumspunkterne for 1 eksakt bibetingelse, og så fremdeles. Det er ikke nødvendigt at undersøge samtlige kombinationer; dels angiver metoden et kriterium for, om en mulig løsning, man er nået frem til, er optimal - i så fald behøver man ikke at gå videre og indføre flere bibetingelser i beregningerne - og dels anviser den genveje til at styre uden om en del af kombinationerne undervejs14, 15).

Theil-van de Panne metoden forudsætter, at præferencefunktionen er strengt konkav (ved minimering, strengt konveks), d.v.s. at dens kvadratiske form er negativ (resp. positiv) definit; eksemplet ovenfor opfylder som nævnt dette krav. Metoden er åbenbart bedst egnet for problemer, hvor optimum ligger »i nærheden af« det frie maksimum, d.v.s. hvor kun få bibetingelser er eksakt opfyldt i optimum. Kan dette ikke på forhånd formodes at være tilfældet, er man bedre tjent med andre

IV. Houthakker's kapacitetsmetode.

(a) En løsningsmetode, der er noget beslægtet med Theil-van de Panne algoritmen, forsåvidt som den benytter sig af klassisk Lagrangemaksimering under bindende bibetingelser, er den såkaldte kapacitetsmetode, der skyldes Houthakker¹⁶).

I modsætning til Theil og van de Panne's metode starter Houthakker's
procedure altid i nulpunktet. I omegnen heraf er der ingen bindende

---

14) Smlgn. linear programmering, hvor problemet ogsa kan loses ved en systematisk gennemgang af samtiige kombinationer (her samtlige hjorner af mulighedsomradet), men hvor simplex-kriteriet og simplex-metoden giver henholdsvis et kriterium for optimalitet og en algoritme til at skyde genvej til det optimale punkt.

15) Boot (op.cit., 1961) har vist, at disse regneregler i Theil og van de Panne's raetode kan udledes direkte af Kuhn-Tucker betingelserne. Specielt kan optimalitetskriteriet formuleres derhen, at en lssning svarende til et givet sset bindende bibetingelser er opumal, dersom den tilhorer mulighedsomrddet (d.v.s. ikke strider mod de ovrige bibetingelser) og Lagrange-multiplikatorcrne for de bindende bibetingelser er positive. Dette er netop tilfseldet med lasning (8) ovenfor (wj = 2>o), der umiddelbart ses at tilfredsstille Kuhn-Tucker betingelserne (sa)— (6a), nar u2u₂ - d.v.s. Lagrange-multiplikatoren for den ikkebindende bibetingelse (2) - saettes == 0; der eksisterer altsa et sset u'er, der sammen med losningen opfylder (sa) — (6a). Vi kunne saledes have standset beregningerne pa dette trin og dermed have sparet det meste af regnearbejdet.

16) Jfr. H. S. Houthakker, »The Capacity Method of Quadratic Programming«, Econometrica, Vol. 29, 1961. - Se ogsa Boot (op.cit., 1963); Kunzi & Krelle, op.cit., Kap. 15; og Vajda (op.cit., 1961), pp. 230 f. Houthakker's metode kan formuleres i et simplex-skema, se C. van de Panne & Andrew Whinston, »A Parametric Simplicial Formulation of Houthakker's Capacity Method«, Econometrica, Vol. 34, 1966.

bibetingelser, men der indføres da en kunstig, bindende »kapacitetsbetingelse«af

hvor f er en parameter. Proceduren går da ud på at bestemme de successive optimale løsninger, der fremkommer, når t vokser fra nul og opefter. Dersom problemet i forvejen indeholder en bibetingelse, hvor alle x'erne har koefficienten 1, kan den bruges som kapacitetsbetingelse, idet højresiden da blot erstattes med parameteren t, der er begrænset opadtil. (Ellers må problemet omformes ved en passende transformation)

(b) Dette er netop tilfældet i vort eksempel. Vi erstatter da (1) med

(la)

For £=0 er der kun 1 bindende bibetingelse, nemlig (la), og kun
»løsningen« Xj.— x2=o.x2=0.

For små positive værdier af t er optimeringsproblemet tilnærmet
lineært, idet de partielle differentialkvotienter

er domineret af konstantleddene (d.v.s. koefficienterne til de lineære led i præferencefunktionen (4b); andengradsleddene er af lavere størrelsesorden). Maksimum under betingelsen (la) bliver da øjensynlig tilnærmet bestemt ved xi =0, x2x₂ =t, idet 10>8. Idet dz/åx₂ betegnes X, har vi da

(18)

Vi skal da undersøge, indenfor hvilket (18) repræsenterer
en (tilnærmet) optimal løsning.

For det første må t og dermed x2x₂ ikke blive så stor, at I bliver negativ, da zer maksimal m.h.t. x2x₂ for åz/åx₂=l =0. Det giver overgrænsen t = 5 f2. For det andet må løsningen xi = 0, xz — t respektere bibetingelserne (1) — (2), d.v.s. vi må kræve

hvilket giver grænserne t=s og t=4, hvor (l) og (2) bliver bindende. (3a-b) er opfyldt for positiv t. Endelig - og her opgiver vi den lineære tilnærmelse - lønner det sig ikke at lade x2x₂ være eneste positive (»effektive«)variabel længere end til det punkt, hvor åz/åx2 - der jo aftager

for voksende X2 - bliver lig med åz/åxx (~S for #i = 0); dette giver en
grænse for x% og dermed for t, bestemt ved

d.v.s. t=\ f2. For L>l f 2 vil den optimale løsning også indeholde et
positivt xi17).

Af de fire grænser, vi således bar bestemt for parameteren t, er den sidste den laveste; allerede for t—l f 2, d.v.s. #i —0, #2=l f 2, har vi et kritisk punkt, hvor den parametriske løsning (18) ophører med at være optimal og må erstattes med en løsning indeholdende 2 effektive variable. Den nye parametriske løsning bestemmes ved maksimering af z under den bindende bibetingelse (la); Lagrange-funktionen

giver da

De første to ligninger giver

d.v.s. vi bevæger os ud ad den rette linje, der er det geometriske sted
for lige stor marginalgevinst m.h.t. xi og x2; den tredje ligning er den
bindende bibetingelse (la) for parametrisk t,

og vi har da 2 lineaere ligninger, der kan loses for xi og x2x2 som lineaere
funktioner af parameteren t, hvorefter vi finder I som en ligeledes
lineaer funktion aft:ft:

(19)

(19) er da den nye parametriske lesning - nu med 2 positive variable
- der har aflest (18) for C>l/2. Vi skal da, som for, bestemme de

---

17) z har maksimum under bibetingelsen (la) i et punkt bestemt ved Sz/8x₁ = dz/dxg =X, *i+*₂ =t (jfr. nedenfor), hvor Lagrange-multiplikatoren X kan identificeres med vort X = sz/8x₂ ovenfor. For K.l/2 ville denne lesning give et »I<o,»₁<0, saledes at den forste af ligevasgtsbetingelserne (Bz/dx₁ = X) ma erstatles med x_l = 0; dette er lesningen (18).

overgrænser for t, indenfor hvilke (19) er optimal. Vi ser, at a^O for
2^13 f2. Endvidere får vi ved indsætning af (19) i bibetingelserne
(l)-

Ikke-negativitetsbetingelserne (3) er her begge opfyldt for C>l f 2. Endelig skulle det undersøges, ved hvilken værdi af t det lønner sig at indføre yderligere positive variable, men dette er ikke aktuelt, da vi kun har 2 strukturvariable, der allerede begge er »i brug«.

Det næste kritiske punkt bliver da bestemt ved den laveste af grænserne, her t—s, hvor #i =3, #2—2. Fra dette punkt at bliver (l) bindende, og den kunstige kapacitetsbetingelse (la) bliver overflødig. Vi skal da finde maksimum af z under den bindende bibetingelse (l); Lagrange-funktionen bliver L=z+«i•(s—xi— x₂), d.v.s. den samme som ovenfor med t sat =5, og løsningen er da givet med (19) for t=s; vi får xi =3, #2 =2, hvilket er løsningen til vort problem (punkt S på fig. I)¹⁸). (Dette punkt ses umiddelbart at opfylde Kuhn-Tucker betingelserne (sa) — (6a) med multiplikatorerne Wi =fl= 2X) og w2=o).w₂=0). Den vej, vi har bevæget os frem til optimalpunktet, er vist på fig. 3.

Princippet i metoden er altså det, at man for voksende t regner sig frem gennem en serie løsninger, der hver for sig er optimal for et bestemtFor enhver sådan løsning vil den laveste overgrænse for t bestemme et kritisk punkt, hvor man »skifter retning«, d.v.s. hvor man ændrer på sættet af bindende bibetingelser og effektive variable

---

18) Havde hojresiden af (1) va;ret 6 i stedet for 5, havde den kritiske vaerdi for I vaerct 23/4, hvor (2) var blevet bindende i stedet for (1); lasningen (19) ville da have vseret optimal indtil denne vsrdi aft,f_t, hvor *j = 7/2, x₂=9/4. Vi matte da ior £>23/4 have beregnet en ny parametrisk lasning med (2) som bindende bibetingelse ved siden af (la), svarende til en bevasgelse nedacl langs begranisningslinjen CD for voksende t; de lineaere maksimumsbetingelser ville have givct x₁ = 2t-8, x2x₂ ■■=-- -t +8, u2u₂ — Bt—46, I= -12< + 70, hvor den nye effektive variabel u2u₂ er Lagrange-multiplikatoren svarende til (2). Den effektive grsense saettes her af 2=o, d.v.s. = 35/6. For denne vserdi aftf_t er (2) opfyldt eksakt og (1) med ulighedstegn; lesningen bliver da = 11/3, x2=l3/6,x₂=13/6, d.v.s. punkt R pa fig. 1, der ses at blive optimalt, hvis begrsensningen AB - altsa (1) - parallelforskydes til at ga igennem punkterne (0,6) og (6,0).

(derunder Lagrange-multiplikatorer). Den næste parametriske løsning beregnes da ved klassisk Lagrange-ma'ksimering, hvor de nødvendige optimumsbetingelser udgør et lineært ligningssystem, der kan løses for de effektive variable som lineære funktioner af t. Problemet er løst, når I bliver = 0,¹⁹) eller når - som ovenfor - alle grænserne er større end højresiden af (1).

Metoden har (ligesom Theil-van de Panne metoden) den svaghed, at den kvadratiske form i præferencefunktionen må forudsættes at være positiv eller negativ definit, ligesom Houthakker forudsætter, at alle koefficienter i de lineære bibetingelser er ikke-negative (og højresiderne positive).

V. Beale's metode.

(a) Eftersom kvadratisk programmering kan opfattes som en generaliseringaf
den lineære programmering, ville det være naturligt, om
man søgte at udnytte de grundlæggende træk i den lineære simplexmetodetil

---

19) Dette sker i vort eksempel, hvis højresiden i (1) sættes til 6 i stedet for 5, jfr. fodnoten ovenfor.

metodetilløsning af kvadratiske problemer20). Dette er udgangspunktet
for en metode, der er udviklet af Beale21).

Princippet i Beale's algoritme er det, at man ligesom ved lineær
programmering skriver bibetingelserne om til ligninger, idet man indfører
ikke-negative restvariable, i vort eksempel y\ og y%:

(i')

(2')

hvor

(3')

og dernæst vælger 2 afhængige variable (basisvariable), svarende til antallet lineære bibetingelser; løser man nu (1')- for disse variable og indsætter i præferencefunktionen, får man basisvariablerne og z udtrykt som funktioner af de øvrige variable. Sætter man disse =0, har man en basisløsning (der skal tilfredsstille (3') for at være feasible), svarende til et hjørne af mulighedsområdet (et af punkterne O, C, P eller B på fig. l). På samme måde som ved simplex-metoden undersøger man nu, om løsningen kan forbedres ved, at man indfører en af ikke-basisvariablerne i basen, d.v.s. gør den positiv i stedet for nul - dette vil være tilfældet, hvis z i basispunktet er en voksende funktion af den pågældende variabel - og man bevæger sig da hen til en ny basis, indtil løsningen ikke længere kan forbedres. Begrebet basis må dog modificeres undervejs, idet vi ikke som ved lineær programmering kan nøjes med at betragte mulighedsområdets hjørner, men også må afsøge dets sider; vi så jo ovenfor, at den optimale løsning - punkt S på fig. 1 - ligger på begrænsningen PB. Denne modifikation finder, som vi skal se, udtryk i, at man under proceduren indfører ekstra variable og tilsvarende ekstra bibetingelser.

(b) Vi skal nu løse det numeriske problem ovenfor ved hjælp af Beale's
metode. En initialbasis giver sig selv med y\ og y2y2 som afhængige variable:

---

20) For en enkel fremstilling af simplex-metoden se f. eks. Sven Danø, Linear Programming in Industry: Theory and Applications, Wien: Springer-Verlag, 1960, Ch. 11, VI og Appendix B-C.

21) JJr. E. M. L. Beale, »On Optimizing a Convex Function Subject to Linear Inequalities«, Journal of the Royal Statistical Society (B), Vol. 17, 1955, og »On Quadratic Programming«, Naval Research Logistics Quarterly, Vol. 6, 1959. - Se også f. eks. Kiinzi & Krelle, op.cit., Kap. 7, og Vajda (op.cit., 1961), pp. 224-230.

(20)

hvor konstantleddene svarer til basisløsningen (for *i = *2=o). Svarende
til simplexkoefficienterne i den lineære simplex-metode22) har
vi da

begge positive i basispunktet (0,0), hvor kun konstantleddene tæller med, så at z er en voksende funktion af både xi og x2x₂ i omegnen af punktet. Idet åz/dx2 er størst (10!>8), vælger vi da at øge xz fra nul til positive værdier, medens xi holdes fast på vserdien nul - ganske som hvis der ikke havde været nogen kvadratiske led i præferencefunktionen. Der er 3 overgrænser for, hvor langt vi må gå med x₂: dels må åz/åx₂ — der aftager for voksende x<> — ikke blive negativ, da z så ville begynde at falde igen, og dels må ligesom ved den lineære simplex-metode basisvariablerne y\ og y2y₂ - der ligeledes er aftagende funktioner af x₂, jfr. (20) - ikke blive negative i strid med (3')- Grænserne bestemmes (for xi =0) ved

Den første grænse er den laveste og dermed den effektive grænse, så
at x2x2 kun må vokse indtil værdien 5 f2, hvilket iflg. (20) reducerer
J\ og y2y2 til henholdsvis 5 f2 og 3.

Vi har nu 3 positive variable med kun 2 lineære bibetingelser, så det punkt, vi er nået frem til, er ikke nogen ny i sædvanlig forstand - jfr. at punktet (*i,*l>) = (0,5 f2) ikke er et hjørne af mulighedsområdet OCPB på fig. I, men ligger på en af områdets sider (her aksen xi = 0). Vi indfører da en ny (kunst-)variabel zi, defineret som —dz/åx₂:

(21)

betragter vi denne ligning som en ekstra bibetingelse i (20), indført
så at sige med tilbagevirkende kraft, kan initialløsningen i nulpunktet
opfattes som en basisløsning i det således udvidede problem, med Z\

---

22) Se Danø (op.rit., 1960), pp. 12 og 66.

som en tredje basisvariabel, og hvad mere er: den nye løsning, hvor x2x₂ ( = 5 f2) har reduceret Z\ til nul og således har erstattet denne som positiv variabel, bliver ligeledes at betragte som en basisløsning (et hjørne) til det udvidede problem. Ved at løse (21) for den nye basisvariabelx2 x₂ og indsætte i (20) - en substitution, der ganske svarer til overgangen fra én basis til den næste i lineær programmering, bortset fra at omregningen af den kvadratiske præferencefunktion er lidt mere besværlig - får vi den nye basisløsning bestemt ved

(22)

Vi er da i stand til at fortsætte til den næste basisløsning. Blot må det erindres, at kunstvariablen Z\ nu er en fri variabel, der herefter gerne må antage negative værdier²³); det var kun ud fra punktet (0,0), at det lineære udtryk Z\ repræsenterede dz/dx₂, der ikke måtte blive negativ. Og skulle Zi på et senere beregningstrin atter blive basisvariabel, kan den tilsvarende basisligning for Z\ droppes som overflødig.

I løsningen (22) har vi for xxi=z 1z1 =0

således at kun X\ kommer på tale som indgående variabel. Grænserne
er (for zx stadig =0) bestemt ved

(x2 0 sætter ikke her nogen grænse for xi). Den effektive grænse
sættes af y\ 0, d.v.s x± erstatter y± som basisvariabel, og den nye basisløsningfindes

---

23) Heraf følger, at dersom dz/dz^ skulle være negativ på et senere beregningstrin, kan præferencefunktionen øges ved, at z± reduceres fra nul til en negativ basisværdi.

løsningfindesved en almindelig simplex-substitution uden indførelse af
nogen ny kunstvariabel. Den bliver:

(23)

hvor cSz/dy^ —3, <sz/dzi=3/4 for ji =Zi=o, d.v.s. zi bliver den næste
indgående variabel.

Det ses af (23), at kun aføs^O og dz/fø^O sætter overgrænser, og
den sidstnævnte grænse bliver den effektive. Vi sætter da åz/åz1 —Z2 og
får svarende til denne nye kunstvariabel den ekstra bibetingelse

(24)

og med Zi i stedet for z2z2 som basisvariabel giver (23) — (24) da den
fjerde basisløsning

(25)

(hvor den første ligning kan udelades, da det herefter ikke tjener
noget formål at beholde zx blandt de variable). For yyl=z2=oz2=0 giver
(25) en løsning, i hvilken vi har

heraf følger, at z bliver mindre, hvis den fortegnsbegrænsede ikke-basisvariabel y-i gøres positiv i stedet for at være nul (og negativ kan den ikke blive), og z er maksimum m.h.t. den frie ikke-basis-variabel z₂. Dette kombinerede kriterium24) garanterer, at den til (25) svarende basisløsning - jfr. punkt S i fig. 1 - er optimal.

Den optimale løsning er således nået gennem 4 beregningstrin, svarende til de 4 basispunkter på fig. 3. Ud fra (0,0) bevæger man sig op ad x>-aksen indtil punktet (0,22), hvor åz/3x2 =0; her er åz/éx_{X), og X\ øges da, indtil man i punktet (2^,21) støder på begrænsningen (1), som da bliver effektiv, og herefter bevæger man sig langs denne grænselinje indtil det optimale punkt (3,2).

Beale's metode er lidt mere generel end de algoritmer, der er demonstreret ovenfor, iden den kun forudsætter, at den kvadratiske form i præferencefunktionen er semidefinit. Den er velegnet til manuel beregning, særlig når beregningerne foregår i et regneskema, der meget ligner simplex-tavlerne ved lineær programmering₂₅), men kan også anvendes ved løsning på elektronregnemaskiner.

VI. Wolfe's metode.

(a) De sidste to metoder, der skal omtales, bygger direkte på Kuhn- Tucker kriteriet (sa) —(6a), idet man benytter sig af, at ulighederne i Kuhn-Tucker betingelserne vil være lineære i xer og w'er, når præfercncefunktionen er kvadratisk og bibetingelserne lineære. Det at finde en optimal løsning til det kvadratiske problem bliver da det samme som at finde en mulig (feasible) løsning til de lineære Kuhn-Tucker betingelser, hvorved man kan benytte sig af den lineære simplex-teknik.

---

24) Smlgn. simplex-kriteriet, der ses at fremkomme som et specialtilfaslde, nar der ikke er nogen 2. grads led. - Ligesom ved lineasr programmering efter simplexmetoden foregar losningen uden bi-ug af Lagrange-multiplikatorer, idet bibetingclserne er elimineret, saledes at man finder et frit maksimum af pra?ferencefunktionen, der fremtrasder som en funktion af de uafheengige (ikke-basis-) variable. Blot skal de variable vecre ikke-negative. Kuhn-Tucker betingelserne for et frit maksimum af en funktion af ikke-negative variable (d.v.s. med Lagrangefunktionen L — z) reducerer sig da til dz/dxj 0, Xj 0, Xj • (<)z/dxj) =0 for fortegnsbegrsensedc variable eg dz/8z_k ~ 0 for frie variable, jfr. henholdsvis y^ og z_o i losningcn ovenfor.

25) Se Kunzi & Krelle, Kap. 7.

Den første ulighed i (sa) omdannes da til ligningsform ved hjælp
af en ikke-negativ restvariabel V\\

hvor betingelsen xj^O da må suppleres med v^O (da uligheden ellers
kommer til at vende den gale vej). Ligningen

kan da - jfr. definitionen af v*t ovenfor - skrives

Gør man tilsvarende med de øvrige betingelser - med restvariablerne
y\ og y2y2 i bibetingelserne, jfr. (6a) - kan (sa) — (6a) skrives

(26)

(27)

(28)

(29)

hvor

(30)

og hvor desuden

(31)

Problemet er da blot at finde en ikke-negativ lesning til (26) — (29) - svarende til en mulig basislesning ved lineaer programmering - der samtidig tilfredsstiller (31). Ligningerne (31) cr ikke-lineaere, men kan i relation til en basislosning opfattes kombinatorisk: for ethvert par (vj,xj) eller {ui,yO ma det kraeves, at hvis den ene variabel er i basen (d.v.s. er positiv), ma den anden ikke samtidig vaere det. Respekterer vi denne restriktion pa basisvalget for hvert af de 4 par, er (31) opfyldt og indgar ikke pa anden made i beregningerne. Den fundne losning er da optimal, idet den tilfredsstiller Kuhn-Tucker kriteriet.

(b) Wolfe's algoritme26) bygger på denne tankegang. En løsning til
(26) —(31) finder man frem til på følgende måde:

Først finder man en mulig løsning til (28) —(29). En sådan giver
sig her umiddelbart med restvariablerne som basis:

---

26) Jfr. Philip Wolfe, »The Simplex Method for Quadratic Programming«, Econometrica, Vol. 27, 1959. - Se ogsa Dorn, op.cil., pp. 183-188; Kiinzi & Krelle, op.cit., Kap. $; Vajda (op.cit., 1961), pp. 239-241; og Vajda {op.cit., 1962), pp. 108 f.

(d.v.s. nulpunktet). Udvider vi den med

er også (30) — (31) opfyldt. Det er (26) - (27) derimod ikke; indsætter vi løsningen, bliver venstresiderne henholdsvis 8 og 10. Vi kan imidlertid få det til at stemme ved at indføre ekstra restvariable z\ og z2z₂ (begge som vi trækker fra på venstre side i henholdsvis (26) og (27) for at få »opsuget« differencen²⁷); i den således løsnede form bliver (26)-(27) da

(26a)

(27a)

og losningcn ovenfor supplerct med

er da en basisløsning (4 positive variable) til det reviderede system (26a) - (27a), (28) —(31) ovenfor. Problemet består herefter blot i at finde frem til en anden basisløsning, hvor z_x og z2z₂ er udgået af basen og derfor er =0, således at (26) — (27) er tilfredsstillet i deres oprindelige form.

En sådan basis finder man frem til ved at finde minimum af den
lineære præferencefunktion

under de lineære bibetingelser (26a) —(27a), (28) - (29) og ikkenegativitetsbetingelserne (30) suppleret med z\,z->^o'²⁸). Dette er et almindeligt lineært programmeringsproblem, der kan løses ved den almindelige simplex-metode - blot må man huske, hver gang man skifter basis, at overholde den restriktion på basisvariabel-kombinationerne, der er indeholdt i (31). Man når da efter et endeligt antal iterationer frem til den tilladelige mindsteværdi af g, nemlig g=o, hvor zi =Z2=o, og problemet er dermed løst.

Beregningerne foregår lettest indenfor det velkendte regneskema
(simplextavler) og ses her at føre til målet i 4 trin29):

---

27) liavile konstantleddet i (26) eller (27) været negativt, skulle den tilsvarende kunstvariabel (2) eller z 9)z₉) have haft koefficienten -{-1 i stedet for —1 for at få det til at stemme.

28) Pointen med denne præferencefunktion er, at kun de variable, man unsker kastet ud af basen, har positive koefficienter; de øvrige har koefficienten 0 og er derfor »billigere«, således at de kommer til at dominere, efterhånden som man arbejder yig frem mod g's minimum. Princippet er forsåvidt det samme som ved elimination af kunstvariable i lineær programmering, hvor de tildeles en vilkårligt stor koefficient i den funktion, der skal minimeres.

29) 1 hver af tavlerne er det element, der ligger i den indgående variabels kolonne og den udgående variabels række, angivet med kursiv.

Løsningen i tavle IV, hvor basisvariablernes værdier er som angive_L i Po-kolonnen og de øvrige variable - deriblandt z\ og z2z₂ - er lig med nul, tilfredsstiller de fuldstændige Kuhn-Tucker betingelser (26) —(31) og repræsenterer derfor den optimale løsning til vort kvadratiske programmeringsproble m³⁰). De successive basisløsninger I-IV og dermed den vej, der beskrives under iterationen, ses i dette tilfælde at være de samme som efter Beale's metode, jfr. fig. 3. Dette vil dog ikke altid være tilfældet, men er specielt for det valgte eksempel.

Wolfe's metode er umiddelbart anvendelig, når den kvadratiske
form er definit; er formen kun semidefinit, må beregningerne gennemføres
i to etaper ved en modificeret udgave af metoden.

VII. Den kvadratiske simplex-metode.

Den sidste algoritme, vi skal omtale — kendt som si??iplex-meLoden for kvadratisk programmering - er nært beslægtet med Wolfe's metode, forsåvidt som den tager udgangspunkt i Kuhn-Tucker betingelserne (26) —(31), men den løser problemet på en mere elegant måde, idet den ikke gør brug af kunstvariable (zi og z₂). Metoden er opdaget først af Dantzig — der også er ophavsmanden til den lineære simplexmetode - og senere, uafhængigt deraf, af van de Panne³¹). Den forudsætter ikke, at præferencefunktionen er strengt konkav; det er tilstrækkeligt, at den kvadratiske form er negativ semidefinit.

Ligesom Wolfe's algoritme begynder den kvadratiske simplex-metode
i nulpunktet; for at få en initial basisløsning til (26) — (29) sættes

---

30) Man bemærker, at ved overgangen fra tavle 111 til tavle IV vælger man ikke u., - der har den mest positive simplex-koefficient - som indgående variabel, da dens tilsvarende variabel y^ allerede er i basen, jfr. den i (31) indeholdte regel for valg af basisvariable. Det ses også, at den optimale løsning i tavle IV ikke er entydig, idet en del af de variable, der ikke er med i basen, har simplex-koefficienten 0; men det er netop de variable, der i henhold til (31) ikke må indføres som nye basisvariable. Løsningen i tavle IV er derfor entydig, når (31) også kræves respekteret.

31) Jfr. G. B. Dantzig, Linear Programming and Extensions, Princeton: Princeton University Press, 1963, Ch. 24, Section 4. (Genoptryk af Quadratic Programming, A Variant of the Wolfe-Markowitz Algorithms, Research Report 2 of the Operations Research Center, University of California, Berkeley, 1961). Endvidere: C. van de Panne, A Non-artificial Simplex Method for Quadratic Programming, Report 22 of the International Centre for Management Science, Rotterdam, 1962. - Se ogsa C. van de Panne & Andrew Whinston, »The Simplex and the Dual Method for Quadratic Programming«, Operational Research Quarterly, Vol. 15, 1964, og Boot (op.cit., 1964), pp. 187-196.

x₁ = xx_{2—2 —u 1} = U2~O, og yi —5, 3>2=B bliver da basisvariable. De manglendeto basisvariable bliver efter Wolfe's metode kimstvariablerne z₁ =8 og 22=10, idet (26)^— (27) erstattes af de svagere betingelser (26a) — (27a), hvor v± og v2v₂ da bliver ikke-basisvariable (= 0). I Dantzig-vande Panne algoritmen derimod bliver (26) — (27) bibeholdt i deres oprindelige form uden kunstvariable, og restvariablerne V\ og v2v₂ træder da ind som basisvariable med negative værdier. Ved en noget modificeret simplex-procedure itererer man sig da frem til en basisløsning,hvor Vi og v2v₂ ligesom de øvrige variable har antaget ikkenegativeværdier, og hvor (31) også er opfyldt. Beregningerne foregår i det almindelige simplex-regneskema; overgangen fra én basisløsning (simplex-tavle) til den næste foregår ved den sædvanlige simplextransformation,blot gælder der - da der nu forekommer negative værdieri Po-kolonnen - lidt andre regler for valg af ind- og udgående basisvariable, ligesom (31) må iagttages. Disse regler går ud på, at man efterhånden skaffer sig af med de negative basisvariable og erstatter dem med positive; da valget af indgående variabel ikke bliver bestemt ved præferencefunktionens koefficienter, får man ikke som ved Wolfe's metode brug for nogen præferencefunktion under iterationen³²). Kun zj'er og ver må optræde med negative værdier i baserne.

Reglerne for overgang fra en basisløsning til den næste går nærmere ud på følgende: Hvis simplex-tavlen for det pågældende beregningstrin har en sådan basis, at der ikke findes noget par af tilsvarende variable (vj,Xj) eller (ui,yi) i basen - (31) er da opfyldt og tavlen siges at være på standardform - vælges som indgående variabel den »primalvariabel« (xj eller yi), hvis tilsvarende »dualvariabel« {vj eller w) er mest negativ i basisløsningen. Den udgående variabel vælges på samme måde som ved den almindelige simplex-metode, idet dog kun grænserne i rækkerne for de primale basisvariable, og rækken for den nye basisvariabels tilsvarende dualvariabel kommer i betragtning. Dersom tavlen ikke er på standardform - der vil da være ét »basispar« af tilsvarende variable i basen og ét »ikke-basispar« uden for basen - vælges dualvariablen fra ikke-basisparret som indgående variabel; den udgående vælges efter det sædvanlige kriterium, dog kun anvendt på rækkerne for de primale basisvariable og for dualvariablen fra basisparret.

Med disse regler kan vort problem løses i følgende 4 beregningstrin,
hvor tavle I blot udtrykker de lineære ligninger (26) — (29) med den
ovenfor angivne initialbasis:

---

32) Man kan udmasrket indfoje den oprindelige pneferencefunktion (4b) i regneskemaet, men deter ikke nadvendigt.

Tavle IV repræsenterer en ikke-negativ basisløsning til (26) —(29), og da den - ligesom I og II - er på standardform, så at også (31) er tilfredsstillet, er de fuldstændige Kuhn-Tucker betingelser opfyldt og det kvadratiske programmeringsproblem dermed løst.

Det vil ses, at ikke blot er iterationsvejen her den samrae som efter Wolfe's metode; en sammenligning af de to sset simplex-tavler viser ogsa en vidtgaende overensstemmelse mellem koefficienterne i sejlerne i tilsvarende tavler, idet positive lesninger for Z\_ og z2z₂ blot er erstattet af tilsvarende negative Lasninger for V\ og v₂, der jo har samrae koefficient med modsat fortegn i (26a) —(27a). Den kvadratiske simplex - metode kan opfattes som en forenklet variant af Wolfe's metode, hvor man har sparet det overfledige regnearbejde, der folger af at benytte to s;et restvariable i (26) — (27) og to tilsvarende ekstra kolonner i simplex- tavlerne.