Ledelse og Erhvervsøkonomi/Handelsvidenskabeligt Tidsskrift/Erhvervsøkonomisk Tidsskrift, Bind 30 (1966)Optimalitetsbetingelser ved parametervariasjon i lineær programmering,.Av Jan Mossin *) InnledningEt 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. Side 34
sannsynligheten
for at ruten vil være optimal (dvs. sannsynligheten for
Vi vil forst
formulere dette problemet generelt og deretter vise
hvordan Det generelle problemDet 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
Velg så blant
disse den k = k* som gjor gk til et maksimum, dvs. velg
Side 3.5
Da er Xk*
losningen på problemet. Bruk av simplexmetoden for beregning av optimalitetsbetingelserDen »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~1B —d' og Ck'Ak"1. I den vanlige simplexrutinen er regiene for valg av basis slik at vi er garantert at vektoren Ak~1b er positiv - for en vilkårlig basis må vi sette opp denne betingelsen eksplisitt. Optimalitetsbetingelsene for basis k kan derfor formuleres slik: Side 36
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 bNå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'1!? 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
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; Side 37
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 Side 38
Variasjoner i dSom et eksempel på
beregningene når d er uspesifisert kan vi bruke Vi kan
sammenfatte de resulterende vektorer og betingelser på d
i Fra kolonnen for
Ak~xb ser at basisene 20g4 aldri kan være optimal
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. Side 39
Side 40
Som eksempel kan
vi bruke det samme problemet som ovenfor med Som et eksempel
på avhengigheten mellom b- og (i-vektorene ser vi Variasjoner i BTilslutt
illustrerer vi under hvilke betingelser en gitt basis,
f. eks. Optimalitetsbetingelsene er
derfor: |