Innledning

Et problem i forbindelse med anvendelsen av lineær programmering er å bestemme under hvilke betingelser på problemets parametre en viss losning eller et visst sett av basisvektorer er optimal. Problemet kan oppstå i tilfeller der parametrene er fastlagt og en optimal losning beregnetmen hvor vi onsker å undersoke hvordan unoyaktigheter eller andre avvik i de gitte parametre vil endre ved den optimale losning. I andre tilfeller er vi interessert i å angi det fullstendige sett av verdier for hvilke hver av alle de mulige basiser er optimal. I én slik type vet programmerenbare sannsynlighetsfordelingen for parameterverdiene, og er interessert i å finne forventningsverdien av maksimanden under den forutsetning av at den optimale beslutning vil bli tatt når parameterverdienepå et senere tidspunkt blir kjent med sikkerhet. For å lose dette problemet er det tydeligvis påkrevd å spesifisere de områder i parameterrummet hvor hver mulig basis vil være optimal. I et transportproblemkan f. eks. forsyningene på hvert tilforselssted være stokastiskevariable, og vil vil være interessert i å beregne forventet transportkostnadunder forutsetning av at de forsyninger som senere inntreffer vil bli transportert på optimalt vis. Hvis vi kjenner de områder i parameterrummet(dvs. i rummet av forsyningsvektorer) hvor hvert sett av transportruter vil bli brukt er det prinsipielt mulig å beregne forventettransportkostnad ved forst å beregne forventet transportkostnadfor hver rute og så ta et gjennomsnitt over alle ruter veid med

*) Norges Handelshoyskole.

sannsynligheten for at ruten vil være optimal (dvs. sannsynligheten for
at tilforslene vil være slik at rutene blir optimale).

Vi vil forst formulere dette problemet generelt og deretter vise hvordan
simplexmetoden kan brukes som hjelpemiddel for beregningen av
parameterbetingelsene.

Det generelle problem

Det generelle problem kan angripes ved å betrakte det lineære programmeringsproblemet:

under bibetingelsene:

der B er (mxn), z er (nxl), d er (nxl) og b er (mx\)

Ved å innfore »slack«-variable y (mxl) har vi den ekvivalente formuleringen:

under bibetingelsene:

der

Vi antar i det folgende at rangen af A er m.

En metode for losning av dette problemet er folgende: Velg et subsett kalt k bestående av m kolonner fra A og de tilsvarende elementer fra a og c. k loper derved over tallene fra 1 til (*"+"). Betegn den resulterende matrise bestående av de valte vektorer for Ak og vektorene med elementer fra x og c for Xk og Ck. Los deretter likningssystemet:

ved hjelp av

Dersom Ak 1b 0 er losningen tillatelig, dvs. den tilfredsstiller de gitte
sidebetingelser. For alle tillatelige losninger Xk beregn så:

Velg så blant disse den k = k* som gjor gk til et maksimum, dvs. velg
k* slik at

Da er Xk* losningen på problemet.

Bruk av simplexmetoden for beregning av optimalitetsbetingelser

Den »losningsmetoden« som er skissert ovenfor er selvsagt ikke særlig effektiv fra et praktisk synspunkt forsåvidt som vi ville måtte lose (T(^{TO + n}) lineære likningssystemer. Simplexmetoden er imidlertid basert på det samme prinsippet, nemlig å velge en basis og lose det tilsvarende likningssystem. Forskj ellen er at istedet for å finne alle ekstremalpunkter går vi fra én basis til en annen ifolge en systematisk regel som er slik at den nye basis alltid gir en hoyere verdi til g enn den tidligere, og slik at vi alltid vet når vi har nådd fram til en optimal basis. Trinnene i regnearbeidet ved simplexmetoden kan imidlertid brukes også når vi onsker å gå gjennom alle mulige bcisiser. I så fall setter vi bare tilside de regiene som bestemmer valget av ny basis inntil samtlige kombinasjoner bestående av m vektorer fra A har vært basis. Men optimalitetsbetingelsene er selvsagt ikke influert av den rekkefolgen vi innforer nye basiser i.

I vår tidligere symbolikk er den forste simplextabellen:

I denne tabellen har vi valt som forste basis de m enhetsvektorene (dvs. de siste m kolonnene fra A). Ved. hjelp av en serie rekkeoperas joner skifter vi så ut en og en vektor ad gangen. Når basisen består av de vektorene som utgjor matrisen Ak vil tabellen være som følger:

Optimalitetsbetingelsene for denne basisen er nå at alle »indikatorene« er positive: indikatorene er elementene i vektorene Ck'Ak~¹B —d' og Ck'Ak"¹. I den vanlige simplexrutinen er regiene for valg av basis slik at vi er garantert at vektoren Ak~¹b er positiv - for en vilkårlig basis må vi sette opp denne betingelsen eksplisitt. Optimalitetsbetingelsene for basis k kan derfor formuleres slik:

Det kan vaere verdier av parametrene for hvilke to eller flere basiser tilfredsstiller optimalitetsbetingelsene. Men fra dualitetsteoremet folger det at i dette tilfelle er verdien av malsetningsfunksjonen den samme, dvs. hvis optimalitetsbetingelsene er tilfredsstilt for basiser ; og k, da er

Optimalitetsbetingelsene er derfor både nodvendige og tilstrekkelige. Når et slikt tilfelle inntreffer betyr det at linjen gjennom ekstremalpunktene tilsvarende de to basiser er parallell med målsetningsfunks jonens hyperplan. At en optimal basis ikke er entydig bestemt vil i nærværende sammenheng være av liten eller ingen betydning.

Selv om optimalitetsbetingelsene er fullstendig generelle er de penbart begrenset vcrdi hvis samtlige parametre i c, B og d får lov å variere samtidig. De enkleste tilfellene har vi når enten matrisen B er fastlagt og bare vektorene b eller d (eller muligens begge) varierer, eller omvendt.

Variasjoner i b

Når bare b er uspesifisert vil indikatorene ha gitte numeriske verdier slik at de basiser som ikke kan være optimale kan sjaltes ut med det samme. Når bare d er uspesifisert vil på tilsvarende mate vektorene Ak'¹!? ha gitte numeriske verdier som tillater oss å skille ut de basiser som kan være optimale.

Som et eksempel kan vi studere et enkelt problem der bare b-vektoren
er uspesifisert. I ulikhetsform er problemet som folger:

under bibetingelsene:

Her er m = n = 2 slik at det er (|) = 6 mulige basiser. I nedenstående tabell 1 er satt opp en simplextabell som inneholder alle disse basisene. Kolonnen som er merket 0 behover selvsagt ikke fores med gjennom alle beregningene ettersom dens elementer lett kan finnes etterpå som Ak~^xb. Vi har tatt den med for oversiktens skyld.

Av tabellen ser vi straks at basisene merket 1, 3 og 5 ikke kan kvalifisere som optimale for noen verdi for b, ettersom en eller flere indikatorer er negative. Vi kan derfor skrive ned optimalitetsbetingelsene for b for hver av de ovrige basiser;

Nr. 2 (vektorene 2 og 4):

Nr. 4 (vektorene 1 og 3):

Nr. 6 (vektorene 1 og 2):

I figur 1 som framstiller (&i,&2)-planet har vi tegnet opp de tilsvarende
regioner og merket dem ©, © og ©.

Variasjoner i d

Som et eksempel på beregningene når d er uspesifisert kan vi bruke
den samme matrisen B som for og fastlegge vektoren b som f. eks. (**).
Vektorene Ck er da folgende (k i samme rekkefolge som ovenfor):

Vi kan sammenfatte de resulterende vektorer og betingelser på d i
tabell 2.

Fra kolonnen for Ak~xb ser at basisene 20g4 aldri kan være optimal
for den gitte b. Hvilke verdier av d som gjor hver av de ovrige basiser
optimale er angitt i figur 2,

Tilfellet hvor både b og d er uspesifisert er ikke vesentlig mer komplisert, idet som tidligere nevnt ingen av optimalitetsbetingelsene angår både b og d samtidig. Men det er nå ikke mulig å sjalte ut enkelte basiser med samme letthet som tidligere, og hvorvidt en bestemt basis er optimal for et visst område i ett av rummene vil avhenge av verdien av den andre vektoren.

Som eksempel kan vi bruke det samme problemet som ovenfor med
både b og d uspesifisert, og kan sette opp resultatet i tabell 3 (s. 41).

Som et eksempel på avhengigheten mellom b- og (i-vektorene ser vi
at regionen di 3<&, di fik f 2 gir 2 som optimal basis hvis bi 0,
bi fø f 2; 4 dersom bi 0, bi 362; og 6 dersom bi >62 f 2, bi 362.

Variasjoner i B

Tilslutt illustrerer vi under hvilke betingelser en gitt basis, f. eks.
nr. 4, er optimal når B er uspesifisert, mens b og d er fastlagt som (^)
og (i). Basis 4 består av vektorene 1 og 3 og vi har således:

Optimalitetsbetingelsene er derfor: