Parametrisk lineær programmering

I. Problemstilling.

Det generelle lineære prograrnmeringsproblem kan beskrives på formen:
find maksimum (eller minimum) af en lineær funktion

under de lineære bibetingelser

og ikke-negativitetsbetingelserne

Som bekendt eksisterer der ingen metode til analytisk løsning af sådanneproblemer; det er ikke muligt at løse problemet generelt, d.v.s. at finde hvert enkelt xj - og dermed også præferencefunktionen g - som en funktion af problemets koefficienter an, hi og Cj, således at man umiddelbart ville få løsningen til et konkret numerisk problem ved at indsætte de givne talværdier for koefficienterne i den generelle løsnin g₁) . Dette hænger, som vi skal se, sammen med, at løsningen reagerer

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

1) Smlgn. den traditionelle type af maksimeringsproblerner under bibetingelser, hvor man ved differentiation finder et sæt nødvendige maksimumsbetingelser, der sammen med bibetingelserne giver en analytisk løsning; specificerer man funktionernes form med talværdier for koefficienterne, får man den konkrete numeriske løsning.

Side 42

diskontinuert på ændringer i hver enkelt af koefficienterne, idet sættet
af positive (basis-) variable bliver et andet, når den pågældende koefficientpasserer
en bestemt kritisk værdi.

Man er derfor henvist til numeriske løsningsmetoder - i første række
simplex-metoden2) - hvor man på forhånd må specificere talværdierne
af koefficienterne i det konkrete problem, der skal løses.

Det har imidlertid - i relation til et sådant konkret problem - ofte interesse at undersøge, hvad der sker med den optimale løsning, hvis en eller flere af koefficienterne antager en anden værdi; hvis problemet f. eks.. går ud på at maksimere en virksomheds gevinst under kapacitetsbegrænsninger, vil løsningen blive påvirket af en given ændring af en af de priser, der indgår i c ferne i præferencefunktionen. Eftersom man ikke kan finde en analytisk løsning, hvori koefficientændringen umiddelbart kan indsættes, kunne det synes, som om man da var henvist til at begynde helt forfra med simplex-beregningerne. Så galt er det dog ikke. Man kan nemlig gennemføre beregningerne efter simplex-metoden med en enkelt koefficient som uspecificeret parameter og da undersøge, indenfor hvilket interval omkring den pågældende koefficients oprindelige værdi den dertil svarende løsning (eller rettere: den dertil svarende basis) stadig er optimal; en undersøgelse af denne karakter, hvor man altså bestemmer en løsnings følsomhed m.h.t. ændringer i en koefficient ud fra udgangspunktet, betegner man ofte sensitivitetsanalyse. Ved en mere omfattende undersøgelse kan man lade parameteren gennemløbe alle værdier inden for det interval, hvor den har nogen mening (f.eks. fra nul og opefter), og da bestemme den følge af optimale basisløsninger, man får, efterhånden som parameteren passerer gennem successive kritiske værdier. Man taler da om parametrisk lineær programmering^) 4).

2) For en simpel fremstilling af simplex-metoden se f. eks. Sven Dana, Linear Programming in Industry: Theory and Applications, Wien & New York: Springer- Vcrlag, 1960 el. senere.

3) Smlgn. begrebet komparativ statik i den okonomiske teori, hvor man sammenligner losningerne til en ligevaegtsmodel for alternative vaerdier af en parameter (f. eks. pengeudbudet i en rentemodel), eller - nar man er interesseret i sma marginale asndringer - differentierer modellen m. h. t. parameteren.

4) Se f. eks. S. Vajda, Mathematical Programming, Reading, Mass.: Addison-Weslcy Publ. Co., 1961 (Ch. 9); en mere detaljeret fremstilling findes i E. 0. Heady & W. Candler, Linear Programming Methods, Ames, Iowa: lowa State College Press, 1958 (Ch. 7, 8 og 16). - Se ogsa Jan Mossin, »Optimalitetsbetingelser ved paramctervariasjon i lineasr programmering«, Erhvervsokonomisk Tidsskrift, SO. arg., nr. 1, 1966.

Side 43

Der er principielt intet i vejen for, at to eller flere koefficienter samtidigt kan behandles som uspecificerede parametre⁵), men jo flere sådanne parametre der optræder i problemet, des mere komplicerede bliver resultaterne m.h.t. de kombinationer af parameterintervaller, indenfor hvilke de forskellige parametriske løsninger er optimale. Vi skal derfor i det følgende begrænse os til at operere med en enkelt parameter ad gangen.

Lad os som udgangspunkt betragte følgende eksempel (der f. eks.
kan tolkes som et diætproblem): find minimum af

(1)

under bibetingelserne

(2)

(3)

og ikke-negativitetsbetingelserne

(4)

Ulighederne (2) — (3) kan omdannes til ligninger ved hjælp af ikkenegative restvariable yi og y<z, der har koefficienten —li henholdsvis (2) og (3). Den optimale basis består da cif x2x₂ og X3. Løser vi nemlig (2) - (3) for disse basisvariable, og indsætter vi løsningen i (l), får vi

(5)

For xi = yyl~l~y2 —0 giver konstantleddene en løsning, der er positiv i
basisvariablerne og opfylder simplex-kriteriet, og som derfor er optimal.
- Ligningerne (5) kunne ogsa have vaeret stillet op i en simplex-tavle.
Vi skal nu se, hvad der sker, hvis en af koefficienterne i problemet
(1) —(3) far lov at variere.

II. Ændringer i aij.

Lad os f. eks. variere på koefficienterne au (==2, koefficienten til xi i
den første bibetingelse). Det kan gøres på forskellige måder: man kan

5) Jfr. Mossin, op. cit.

Side 44

enten sætte flu = 2 + t, hvor parameteren t da er en additiv ændring i forhold til den oprindelige værdi, eller man kan lade t være en multiplikativændring (a_n = 2 • i); endelig kan man lade parameteren t repræsentere selve koefficienten (an = t). Resultatet bliver det samme.Vi vælger den første metode. Med an = 2 + t i (2) og samme basisvariable som ovenfor får vi da - opstillet i en simplextavle — basisløsningen

der for t = 0 er identisk med (5) ovenfor.

Denne løsning er ikke-negativ for alle værdier af t, jfr. PO-kolonnen,P0-kolonnen,
og simplex-kriteriet er opfyldt, så længe simplex-koefficienten i xi-kolonnen
er ikke-positiv,

For alle værdier af I op til denne kritiske værdi er den parametriske løsning i tavle I altså optimal. Dersom koefficienten an ifølge problemets natur (som f. eks. i et diætproblem) kun kan være positiv eller nul, har det kun interesse at betragte værdier af t fra —2 og opefter. I dette interval er ikke blot basisvariablerne de samme (#2, #3); deres værdier og dermed også værdien af g er også uafhængige af t, jfr. kolonne Pq. Den optimale løsning er altså helt ufølsom for ændringer i t indenfor intervallet.

Når t passerer den kritiske værdi 18 f7, bliver det fordelagtigt at trække xi ind som basisvariabel. Den erstatter da i basen den variabel, der først bliver =0, når x^ vokser; for t= 18 f7 er det x₃, der sætter denne grænse. Med den nye basis får vi da følgende løsning:

Side 45

Denne løsning, hvor t nu også optræder i kolonne Po, er positiv og opfylder simplex-kriteriet for alle i 1817. I dette åbne interval består den optimale basis af X\ og X2, men deres værdier og dermed også værdien af præferencefunktionen vil afhænge af parameteren t; g er en aftagende funktion af t (og dermed også af «n).

Vi kan da sammenfatte resultaterne i følgende tabel:

En tilsvarende undersøgelse kan foretages for hver af de andre an'er
i problemet.

Programmering med et parametrisk an vil særlig have praktisk betydning ved problemer, hvor an'erne udtrykker tekniske produktionskoefficienter (f. eks. maskintid pr. produceret enhed), som man enten har mulighed for at variere indenfor visse grænser ved at ændre lidt på produktionsteknikken, eller som p.gr.a. mere eller mindre »tilfældige« variationer ikke kan bestemmes nøjagtigt.

III. Ændringer i bi.

Lad os nu i stedet indføre parametervariation i en af højresiderne
i bibetingelserne, f. eks. sætte b] = 5 -f t. Simplex-tavle I bliver da:

Side 46

der for I = 0 giver (5). Det ses, at løsningen er ikke-negativ i basisvariablernefor —5 t 11. Simplex-kriteriet er altid opfyldt, da t ikke optræder i simplex-koefficienterne (tavlens nederste række); når bibetingelsernes højresider varierer parametrisk, er det kun Po-kolonnen - altså selve løsningen - der bliver berørt. Indenfor dette interval er den optimale basis altså den samme, men værdierne afhænger af parameteren; vi har således dg fdt —7 fl2.

For t<— 5 bliver bi<o. Det har da kun interesse at se på, hvad der sker, når t bliver større end 11. Det er da klart, at #2 må gå ud af basen, da den bliver negativ. M.h.t. valg af indgående variabel giver simplexkoefficienterne i nederste linje ingen vejledning, da de alle er negative. Vi bruger da i stedet et valgkriterium, der er kendt fra den s.k. duale simplex-metode⁶). Denne løsningsmetode for lineær programmering tager udgangspunkt i en simplex-tavle, hvor simplex-kriteriet er opfyldt, men hvor nogle af basisvariablerne er negative. Som udgående variabel vælges da en negativ basis variabel (her altså X2); den indgående variabel bestemmer man herefter som den, i hvis kolonne forholdet mellem simplex-koefficienten og tallet i den udgående variabels række (dog kun forsåvidt dette tal er negativt) er numerisk mindst - i dette tilfælde J2⁷). Overgangen fra en tavle til den næste foregår i øvrigt på sædvanlig måde, således at den nye tavle også repræsenterer en basisløsning til problemet. Man når da efterhånden frem til en optimal løsning, idet man skridt for skridt fjerner negative variable fra basisløsningen. - Idet X2 altså byttes om med y^ som basisvariabel, får vi da tavle II':

6) Se f. eks. Vajda, op. cit., pp. 99 ff.

7) Metoden ses på alle punkter at være symmetrisk med den almindelige simplexmetode, idet der blot er »byttet om på lodret og vandret«, således at det i virkeligheden er dualproblemet, man løser; jfr. specielt, at kolonnen Pq svarer til simplex-koefficienterne i dualproblemet og omvendt.

Side 47

Den hertil svarende løsning er ikke-negativ i basisvariablerne og optimal
for alle t^ll.

Vi har da:

Man ser, at præferencefunktionen i dette tilfælde vokser stykvis lineært
med t, d.v.s. med b\. Differentialkvotienten dg fdt —dg fdbi vil i
regelen have en ganske bestemt tolkning alt efter problemets natur.

Hvis (1) —(4) f. eks. er et diætproblem, vil en forøgelse af bi - der f. eks. repræsenterer en stipuleret vitaminmængde - med 1 enhed fra 5 til 6 hæve omkostningerne g med 7 fl2, som da bliver grænseomkostningerne ved at fremstille en enhed mere af det første vitamin⁸). Tallet 7 fl2 genfindes som simplex-koefficienten til den tilsvarende rest variabel yi i tavle I': øges den fra 0 til 1, svarer det til, at højresiden af (2) bliver 1 enhed mindre. Den tilsvarende variabel i dualproblemet har i optimum ligeledes værdien 7 fl2 og kan tolkes på samme måde.

Et andet eksempel har man i udledningen af omkostningsfunktionen under en lineær produktionsmodel, idet omkostningerne minimeres underhensyn til givne kapacitetsgrænser og for given parametrisk totalproduktioni de aktiviteter, der står til rådighed. En sådan undersøgelse foretages ved parametrisk programmering som vist ovenfor. Omkostningerneved den optimale produktion bliver da en stykvis lineær funktion

8) Jfr. Danø, op. cit., pp. 92 ff.

Side 48

af den højreside-parameter, der repræsenterer produktionsmængden, og
dg\dt bliver slet og ret grænseomkostningerne9).

Hvis endelig problemet går ud på gevinstmaksimering under kapacitetsgrænser, bliver dg fdbi at tolke som mer-gevinsten ved en udvidelse af kapaciteten bi med en enhed, d.v.s. som skyggeprisen på den pågældende kapacitetsfaktors tjenester (f. eks. maskintimer)¹⁰).

IV. Ændringer i cj.

Lad endelig ci, koefficienten til xi i præferencefunktionen (l), blive
erstattet med en parameter, a=4-\-t.

På tilsvarende måde som ovenfor får vi da følgende basisløsninger
for aftagende værdier af parameteren t, idet den basis (I"), der svarer
til (5), nu kun er optimal for værdier af t over en vis grænse:

9) Jfr. Sven Dano, Industrial Production Models: A Theoretical Study, Wien & New York: Springer-Verlag, 1966, pp. 35 ff. (jfr. ogsa p. 198).

10) Jfr. Dana (op. cit., 1960), pp. 92 ff., og Dane (op. cit., 1966), pp. 39 ff.

Side 49

De kritiske værdier for t er — 3 f2 i tavle I" og —5 f2 i tavle II", og
vi får da:

Dersom problemet tolkes som et dia^tproblem, vil omkostningerne ved den optimale diæt altså vokse stykvis lineært med ci - d.v.s. prisen på den første ingrediens, der indgår i blandingen - indtil ci når den kritiske værdi 5 f2, hvor xi går ud som basisvariabel, således at dens pris ikke længere influerer på omkostningerne.

En tilsvarende procedure kan anvendes til at udlede en virksomheds udbudskurve, når en vare fremstilles i et antal lineære aktiviteter under en kapacitetsbegrænsning; man maksimerer da gevinsten under denne begrænsning med salgsprisen som parameter. Prisen kommer her til at indgå i samtlige o'er, der jo repræsenterer dækningsbidragene (pris minus variable stykomkostninger) i de enkelte aktiviteter. De skiftende basisløsninger m.h.t. produktmængden for voksende salgspris giver da umiddelbart udbudskurven¹¹).,

Eftersom priserne (produkt- og faktorpriserne) og dermed c ferne vel er de koefficienter, der er mindst stabile over tiden i et produktionsplanlægningsproblem, er parametrlsk programmering af størst praktisk betydning ved prisvariationer, d.v.s. når parameteren optræder i præferencefunktionens koefficienter. Simplex-beregningerne er her særlig enkle, idet — som vi har set i tavle I"—III" — parameteren kun vil forekomme i simplex-tavlernes nederste linje. Som følge heraf bliver det ikke væsentligt mere besværligt at operere med flere prisparametre på samme tid for at bestemme, hvor sensitiv en given optimal løsning er m.h.t. ændringer i de pågældende priser₁₂).

11) Jfr. Danø (op. cil., 1966), pp. 38 f.

12) En empirisk sensitivitetsanalyse pa et programmeringsproblem af diast-typen er foretaget i Sven Dane, »Linear Programming in Ice Cream Making*, Nordisk Tidsskrift for Teknisk Okonomi, 1955, pp. 1(38- (Se ogsa Dane {op. cit., 1960), pp. 97-99). Samtlige Cj'ev i dette omkostningsminimeringsproblem er her behandlet som uspecificerede parametre, og simplex-kriteriet (ud fra den basislosning, der cr optimal ved de gceldende priser) giver da umiddelbart et antal lineaere ulighedcr i prisparametrene, som ma vasre respekteret, hvis lesningen skal vedblive at vatrc optimal.

Side 50

Et specielt eksempel på parametrisk programmering har man i den velkendte »M-metode« ved lineære minimeringsproblemer, hvor man for at få en ikke-negativ initial basisløsning indfører kunstvariable (»artificial variables«, kunstige restvariable); disse variable har ingen meningsfuld tolkning i relation til det konkrete problem, og for at sikre, at de bliver kastet ud af basen under beregningerne, tildeler man dem da en meget stor positiv, men iøvrigt uspecificeret koefficient M i den funktion, der skal minimeres. Parameteren M kommer da til at optræde i simplex-koefficienterne, og man når til sidst frem til en basisløsning, der tilfredsstiller simplex-kriteriet, når M tillægges en tilstrækkelig stor værdi¹³).

13) Se f. eks. Dano {op. cit., 1960), pp. 71 ff.

Ledelse og Erhvervsøkonomi/Handelsvidenskabeligt Tidsskrift/Erhvervsøkonomisk Tidsskrift, Bind 31 (1967)

Parametrisk lineær programmering

I. Problemstilling.

II. Ændringer i aij.

III. Ændringer i bi.

IV. Ændringer i cj.