Lineær programmering 8203123724 [PDF]

Zitiervorschau

Kvantitative metoder i økonomi og administrasjon

Jan Evensmo Gro Seim

Aschehoug

Nasjonalbiblioteket Depotbiblioteket

© H. Aschehoug & Co. (W. Nygaard) 1982 Det må ikke kopieres fra denne boka utover det som er tillatt etter bestemmelsene i Lov om opphavsrett til åndsverk m.v., Lov om rett til fotografi og A vtale mellom staten og rettighetshavernes organisasjoner om kopiering av opphavsrettslig beskyttet verk i undervisningsvirksomhet. Brudd på disse bestemmelsene vil bli anmeldt.

ISBN 82-03-12372-4

Omslag: Janne-Beth Carlsen Illustrasjoner: Gerd Eng Kielland Grunnskrift: Press Roman 11/13 Trykt i offset hos AS Bryne Trykkeri, Bjørkelangen Papir: 80 g Plan

Andre bøker i samme serie: Jan Evensmo/Frode Ihlen: Lagermodeller og lagerstyring Jan Evensmo/Gro Seim: Analyse og simulering av køsystemer

L

- FC Z-,. /_

Kjennskap til og utbredelse av kvantitative metoder, operasjons­ analyse, ,,management science”, eller hva vi enn kaller det, er nært knyttet til den pedagogiske virksomheten som foregår i høg­ skoler og universiteter. Bare gjennom grundig og systematisk presentasjon av matematisk/statistiske metoders forklaringsevne i økonomisk/administrative problemstillinger er det mulig å skape det faglige miljø som er en forutsetning for praktisk anvendelse. Forfatterne har sin pedagogiske bakgrunn fra Bedriftsøkonomisk Institutt, Oslo. Spesielt Diplomøkonomstudentene har i mange år hatt matematikk, statistikk og operasjonsanalyse som en del av sitt obligatoriske pensum. Gjennom forelesninger, øvelser og annen kontakt med studentene har vi fått mange forslag og idéer til hvor­ dan undervisning og læring i metodefag kan forbedres. Mangelen på norskspråklig litteratur har vært tydelig. Selv om engelskkunnskapene generelt er gode, viser erfaring at det i seg selv er såvidt krevende å tilegne seg metodefagene at amerikanske og engelske lærebøker ikke er noen ideell løsning. BI har som andre undervisningsinstitusjoner benyttet egenproduserte kompendier til støtte eller erstatning for utenlandsk litteratur. Vi tror imidlertid at det kan være nyttig og interessant for et større antall brukergrupper i og utenfor høgskolene å få tilgang til faglig stoff som er gjennomprøvet ved lang tids bruk. Temaserien i Kvantitative metoder er ment å gi et tilbud til studenter og andre interesserte som ønsker å få kjennskap til hva de for­ skjellige problemstillinger og metoder går ut på. Tredje bind i serien. Lineær programmering, er en bearbeidelse av tidligere BI-kompendier, tilpasset en større målgruppe. Primært skal serien være studentlitteratur tenkt anvendt i et læringsmiljø. Det er lagt stor vekt på illustrerende talleksempler, ofte som gjennomgangseksempler til belysning av det teoretiske stoffet. Dessuten har vi lagt inn et større antall oppgaver, delvis med fasit, for at studenten skal kunne arbeide aktivt og selvstendig med stoffet. Boken retter seg mot studenter i økonomi/administrasjon som bare unntaksvis er interessert i matematikk. Vi har derfor valgt en fremstillingsform som matematisk sett er lite krevende. Vårt

primære mål er å utvikle evnen til modellbygging. Behovet for avansert symbolmanipulasjon er derfor beskjedent. Studentene skal analysere en gitt problembeskrivelse, trekke ut det vesent­ ligste og formulere resultatet som en matematisk modell. Det er fullt mulig å ha et høyt ambisjonsnivå i modellbygging uten å gå inn på løsningsteknikker. Mange ville imidlertid betrakte boken som ufullstendig og uegnet for deres formål hvis den ikke inne­ holdt en mer teoretisk del, og vi har imøtekommet disse. Også her har vi imidlertid valgt å fremstille Simplex-metoden og andre teknikker på en illustrerende måte ved hjelp av talleksempler, fremfor å benytte formelle fremstillinger fra lineær algebra. Et stort antall problemsituasjoner er presentert i kursiv. Vi løser noen av dem, og overlater andre til studentene. Boken starter med små problemer som bare krever 2—3 handlingsvariabler. Deretter tar den for seg flere spesielle problemer fra forskjellige funksjonsområder, slik som produksjon, transport, jobbfordeling osv. Til slutt i modellbyggingsdelen presenteres inte­ grerte problemer som inneholder komponenter fra to eller flere funksjonsområder. Det er da problemene begynner å ligne virke­ ligheten og bli interessante, og det er dit vi vil at studentene skal komme. Boken har vokst frem over et langt tidsrom, og er langt fra noe impulsivt arbeid. Vi har for en stor del bygget på kompendiene Lineær programmering, del 1 og 2, skrevet av Ragnar Andersen, Bjørn Elvestad, Jan Evensmo og Gro Seim. Disse kompendiene var sterkt edb-orienterte, og bruken av dem forutsatte tilgang til skreddersydde edb-programmer på Bis maskin. Vi har gitt denne boken er mer edb-uavhengig form, men mange av oppgavene kan ikke løses for hånd. Dette er i dag ingen begrensning på anvendelse siden alle aktuelle læringsmiljøer har tilgang på LP-programmer i en eller annen form. Boken som helhet er forhåpentlig original nok, men hva de enkelte eksempler angår, er de velprøvede og med høyst varieren­ de opphav. Noen stammer fra Norsk Regnesentrals kursvirksom­ het i sekstiårene, hvor Evensmo var ansatt og fikk sin grunn­ leggende opplæring i emnet: De er like gode den dag i dag! Noen er laget av andre lærere ved BI, spesielt Erik Engebretsen, Gerson Komissar, Fred Wenstøp og Willy Wiik. Noen er lånt fra pensum­ bøker som har vært benyttet i Bis operasjonsanalyseundervisning, spesielt Harvey Wagner: Principles of Operations Research (Prentice Hall) og R. Ackoff & M. Sasieni: Fundamentals of Operations Research. Noen er inspirert av nyere amerikansk litte­ ratur, og noen har sitt opphav i en uidentifisert operasjonsanalytisk ,,urtid”. Vi takker alle for deres bidrag og håper at våre endringer og utvidelser er i tråd med de opprinnelige hensikter. Vi takker også Frode Ihlen og Sindre Guldvog for verdifull kritikk, samt 4

deres innsats i klassesituasjoner for å utprøve eksemplene. Til slutt'takker vi alle de studenter som har slitt med LP og som har lært oss ,,pedagoger” mer om hva som er vanskelig! Vi har laget en ,,Studieplan” som viser hvordan kapitlene bygger på hverandre. Man vil se at det er mulig å benytte boken på mange måter, og det er slett ikke nødvendig å lese boken side for side fra perm til perm. Vi skulle gjerne hatt med enkelte andre emner i boken: — Lineær programmeringsmodeller med heltallskrav til handlingsvariablene — Ikke-linearitet, spesielt i forbindelse med kostnadene — Spesielle løsningsteknikker for store LP-modeller (dekompo­ nering) — Stokastisk lineær programmering, der usikkerhet inngår som en sentral del av optimeringsmodellen. Bokens omfang er imidlertid stort nok som det er, og foreløpig får interesserte derfor fremdeles nøye seg med utenlandsk litte­ ratur. Det ville være interessant å få høre synspunkter på hva som bør med i en eventuell senere utgave av boken. For øvrig håper vi at både lærere, studenter, praktikere og andre lesere vil gi oss kommentarer angående bokens sterke og svake sider, samt eventuelle trykk- og andre feil. Lykke til med studiet!

Bedriftsøkonomisk Institutt, Bekkestua, mars 1982 Jan Evensmo

Gro Seim

Studieplan

Innhold

Innledning 8 LP-modellering i det små 12 LP-modeller med to variabler 12 LP-modeller med tre variabler 40 LP-modellering for diverse anvendelsesområder 51 Kapasitetsplanlegging 51 Blanding og avbalansering 60 Trim 70 Transport 79 Jobbfordeling 90 Nettverk 98 Diverse planleggingsproblemer 115

LP — teori og teknikk 136 Simple x-metoden 136 Stepping Stone-metoden 158 Dualitet 169 Følsomhetsanalyse og parametrisering 193

Litteraturliste 207 Fasit 208

Innledning

Hva er lineær programmering? Emnet kan betraktes fra mange synsvinkler, og svaret blir preget av hvilken bakgrunn og hvilke motiver man har for å studer.e lineær programmering (LP). En del typiske, både teoretiske og mer praktiske innfallsporter til LP er vist nedenfor.

Fra matematikerens synspunkt...

8

• Lineær programmering kan betraktes som en rent matematisk disiplin. Vi skal her skissere to mulige tilnærmingsmåter: — Lineære ligningssystemer studeres under den spesielle forut­ setning at antall variabler er større enn antall ligninger. Det finnes da som kjent uendelig mange løsninger. Vi vurderer så hvor gode de forskjellige løsningene er i forhold til et felles kriterium.

Kriteriet må kunne uttrykkes som en lineær funksjon av lignings­ systemets variabler. Som regel ønsker vi å få denne funksjonen så stor eller liten som mulig. Systemets optimale løsning vil være den løsning som maksimerer eller minimerer funksjonen. — Vi kan også studere en generell klasse av matematiske modeller, kalt matematisk programmering (MP), der problemstillingen er følgende: Gitt en funksjon av flere variabler. Finn de variabelverdiene som maksimerer eller minimerer funksjonen når variabelverdiene samtidig må tilfredsstille et sett av bibetingelser. Dersom både funksjonen og samtlige bibetingelser er lineære, har vi et enkelt spesialtilfelle som kalles lineær programmering.

Fra operasjonsanalytikerens synspunkt . . .

• Lineær programmering er et sentralt metodeområde innenfor Operasjonsanalyse (OA). En definisjon av OA (Ackoff & Sasieni) er at operasjonsanalyse kan sies å være:

— Anvendelse av vitenskapelig metodikk — av tverrfaglige grupper — på problemer som medfører kontroll av organiserte menneske/ maskin-systemer — for å frembringe løsninger som best tjener organisasjonen som helhet.

Sentralt i OA er den vekt som legges på formell modellbygging. Problemløsningsprosessen kan grovt beskrives slik: — definere og avgrense problemet — konstruere en modell hvor de relevante faktorene i problemet er tatt med — finne en løsning, helst optimal, ut fra modellen — vurdere løsningen ut fra modellen og det faktiske problemet — iverksette løsningen for å redusere, eventuelt fjerne problemet. Lineær programmering omfatter en hel klasse av modeller som har vist seg å være svært anvendelige. Mange problemer innenfor den økonomisk/administrative sektor kan uttrykkes slik: Et betydelig antall mulige beslutningsvariabler (handlingsvariabler) står til disposisjon. Beslutningene, dvs. variabelverdiene, må være slik at de oppfyller gitte begrensninger mht. ressurstilgang, tekniske spe­ sifikasjoner, administrative krav etc. Blant de mulige beslutninger søkes den (eller de) som har den gunstigste konsekvens, vanligvis i økonomisk henseende, f.eks. maksimerer totalt dekningsbidrag, minimerer totale kostnader o.l. Problembeskrivelsen forutsetter lineær sammenheng mellom handlingsvariablene og deres konsekvenser for ressursforbruket. Beskrivelsen forutsetter også linearitet i den funksjon som ut­ trykker beslutningskriteriet eller målsetningen. Selv om dette

9

ofte i praksis ikke er tilfelle, kan en LP-modell likevel bidra til å finne gode om enn ikke optimale løsninger. Problemet forutsettes også å være helt eller tilnærmet av deterministisk art, dvs. at modellens parametere (f.eks. dekningsbidrag, ressursforbruk per produsert enhet, og tilgjengelige ressurser) er gitte og sikre størrelser. Beslutningstakerens problem består derfor i stor mangfoldighet snarere enn i usikkerhet. Der­ som enkelte parametre likevel er usikre, analyseres konsekvensen av dette innenfor LP-modellens egen begrepsramme, uten å trekke formell statistikk inn i bildet. LP har vist seg å være velegnet til å strukturere og optimere mange integrerte, multiprodukt-, multiperiode-problemer. Fra økonomens synspunkt . . .

• Lineær programmering er en viktig del av økonomisk teori. Nyklassisk produksjonsteori beskjeftiger seg med input-output ana­ lyser hvor beslutningene er av typen: Hvor stort beløp bør brukes på inputfaktorene, og hvordan bør beløpet fordeles på de enkelte faktorer? Hvor mye skal produseres av hvert produkt, og hvilket ressursforbruk krever dette? Foruten svar på disse spørsmål gir teorien for LP oss også sammenhengene mellom optimal output og priser på ferdigprodukter og ressurser. LP-modellenes skyggeprisbegrep er nyttig. Ved hjelp av dette kan vi finne hva marginale ressurser er verdt, og hvordan optimal produksjon og optimale priser kan beregnes samtidig, som to sider av samme sak. LP er således en del av mikroøkonomien. Det bør også nevnes at generell likevektsteori, kapitalteori og -budsjettering samt teori for strategiske spill alle er områder der LP kan bidra til å øke forståelsen for fundamentale sammenhen­ ger.

Fra planleggerens synspunkt . . .

• Lineær programmering er en praktisk anvendbar planleggingsmetode der større mengder data kan behandles i standardiserte edb-programmer. De store planleggingsproblemer innenfor produksjon, distribu­ sjon, raffinering og økonomistyring må formuleres og behandles på en slik måte at det er mulig å holde oversikt over de betydelige datamengdene. Beregningene må foretas kontrollert og automa­ tisert under klare, veldefinerte forutsetninger. Resultatene må bli presentert i en oversiktlig form. LP må sammen med modeller for nettverksplanlegging, prognostisering og lagerstyring, sies å være sentrale, nyttige teknikker som kombinerer praktisk plan­ legging med moderne edb-teknologi. Et LP-program utfører både en — konsekvensanalyse der konsekvensene av ulike ,,tenkte” planer mht. ressursforbruk o.l. bli beregnet, og en — preferanseanalyse der de forskjellige realiserbare planer

10

sammenlignes ut fra økonomiske eller andre kriterier, og hvor programmet finner frem til den beste plan i forhold til krite­ riene.

Alle større edb-installasjoner har i dag standard kommersielle LPprogramsystemer beregnet for praktisk planlegging innen ulike områder. Ordet ,,programmering” er avledet av det engelske ,,programming” som betyr planlegging, og ikke koding av edb-programmer, som er en hyppig forekommende og forståelig misforståelse. Fra pedagogens synspunkt . . .

• Lineær programmering har vist seg å være et effektivt hjelpe­ middel når det gjelder å utvikle studentenes evne til å betrakte problemstillinger som samtidig berører flere av organisasjonens tradisjonelle funksjonsområder i en større sammenheng. På mange måter er OA en „avansert form for praktisk regning med et visst økonomisk tilsnitt” (jfr. Jan Mossin: Operasjonsanalytiske emner). Det er en av de økonomiske høyskolers opp­ gaver å trene studentene opp i praktisk regning fra relativt enkle problemer med få variabler innen et avgrenset område, til det praktiske livs mer komplekse problemer der produksjon, finansiering, markedsføring, distribusjon, likviditetsstyring, personaladministrasjon etc. griper inn i hverandre. LP er velegnet i denne prosess. Mange tilsynelatende forskjel­ lige problemer kan formuleres som optimeringsproblemer under gitte praktiske begrensninger. Studentene kan selv formulere LP-modeller og bearbeide dem ved hjelp av standardprogrammer fra en dataterminal. På denne måten får de anledning til å se kon­ sekvensen av den modell de formulerer, noe som skaper mulighet for en mer konkret diskusjon av modellens og løsningenes bruk­ barhet enn det som ellers er tilfelle.

Fra forfatterens synspunkt . . .

• Ut fra det som er nevnt foran, har vi tro på LP som et nyttig fag i økonomisk/administrative studier, spesielt når det gjelder

— — — —

kjennskap til matematisk modellbygging praktisk problemløsning innsikt i moderne økonomisk teori „sektor”-løsninger kontra ,,total”-løsninger.

11

LP-modellering i det små

En grunnleggende innføring i lineær programmering konsen­ treres om problemets dimensjon. For å øve opp evnen til modell­ bygging gir vi eksempler og oppgaver fra et større antall anvend­ elsesområder, men med ett fellestrekk: Det er bare to eller tre handlingsvariabler i modellen. Dette gjør det mulig å gi grafiske illustrasjoner til modellformulering, løsning og tolkning.

LP-modeller med to variabler Introduksjonsog gjennomgangseksempel 1 Dreiebenk

Fabrikken MOCO A/S produserer dreiebenker av to typer, type M—101 og type M—102. Det skal legges opp et produksjonsprogram for neste måned. Hvor mange dreiebenker skal produseres av hver av de to typer7 Problemstillingen er foreløpig ufullstendig. Det vil sikkert kunne tenkes flere produksjonsprogrammer, og vi har ikke sagt noe om hvordan vi skal vurdere dem i forhold til hverandre. Vi mangler et mål. Dette må vi fastlegge før problemet, slik det er skissert ovenfor, har noen mening. Anta at MOCO har følgende mål med sitt produksjonsprogram: Størst mulig salgsinntekt av dreiebenkene. Målet er nå klart, men det mangler en tallmessig uttrykks­ form. Vi må sette oss i stand til å regne ut salgsinntekten av et produksjonsprogram, og det innebærer at vi må vite salgsprisen for den enkelte dreiebenk. MOCO vet at salgsprisen per dreiebenk av type M—101 er kr 5000 og av type M—102 kr 6000. Målet kan nå uttrykkes tallmessig på følgende måte:

Salgsinntekten ved et gitt produksjonsprogram er

Figur 1

12

kr 5000 • produsert antall type M—101 + kr 6000 • produsert antall type M—102 Produsér det antall dreiebenker av type M—101 og type M—102 som fører til at salgsinntekten blir størst mulig. ---------- T----------------------------------------Z------------------------

l

Overfladisk kan dette se ut som en tilfredsstillende beskrivelse av problemet, men det er lett å se at det mangler noe. Det er ikke sagt noe om hvilke produksjonsprogrammer som er mulige. En produksjon av 100 millioner dreiebenker i måneden vil gi en enorm salgsinntekt. Det er nødvendig å fortelle hvorfor dette ikke er mulig. Vi mangler altså de begrensninger som en prak­ tisk gjennomførlig løsning må ta hensyn til. Disse må nå fast­ legges: Anta at MOCO er i den situasjon at alt som produseres kan selges, og at produksjonen bare begrenses av produksjons­ kapasiteten i de forskjellige avdelingene i fabrikken. Det er to avdelinger, A og B, og begge dreiebenktyper må gjennom begge avdelinger.

Det er således to kapasitetsbegrensninger, én for hver avde­ ling. Begrensningene uttrykkes ved at den tid som forbrukes i avdelingene, ikke må overskride den tid som er tilgjengelig. Det er nødvendig å uttrykke dette i tall. Vi må vite hvor mye tid som er tilgjengelig, samt hvor mye tid den enkelte dreiebenk forbruker i hver avdeling. MOCOs avdeling A har tilgjengelig inntil 300 arbeidstimer i måneden for produksjon av dreiebenker. Det tilsvarende tall for avdeling B er 200 arbeidstimer. Produksjonen av én dreie­ benk av type M—101 tar 20 arbeidstimer i avdeling A og 10 arbeidstimer i avdeling B. De tilsvarende tall for type M—102 er 15 og 20 arbeidstimer. Kapasitetsbegrensningene kan nå uttrykkes tallmessig på følgende måte: Avdeling A: (20 timer • produsert antall type M—101) + (15 timer • produsert antall type M-102) må ikke overskride 300 timer.

Avdeling B: (10 timer • produsert antall type M—101) + (20 timer • produsert antall type M-102)

Figur 2

må ikke overskride 200 timer.

Figur 1 og 2 inneholder nå det fullstendige problem uttrykt tallmessig. Sagt på en annen måte: Figur 1 og 2 representerer en

13

modell av problemet. Figur 1 representerer målet, og figur 2 representerer begrensningene. Vi kan klargjøre dette ytterligere: Gitt to ukjente størrelser (variabler):

Modell av MOCOs produksjonsproblem

— Det produserte antall dreiebenker av type M—101 — Det produserte antall dreiebenker av type M—102 Salgsinntekten, som kan uttrykkes ved:

kr 5000 • det produserte antall dreiebenker av type M—101 + kr 6000 • det produserte antall dreiebenker av type M—102

ønskes gjort størst mulig, samtidig som følgende to begrensninger gjelder:

(20 timer • produsert antall type M—101) + (15 timer • produsert antall type M—102) må ikke overskride 300 timer. (10 timer • produsert antall type M—101) + (20 timer • produsert antall type M—102) må ikke overskride 200 timer. Figur 3

Selv om modellen i figur 3 gir en presis beskrivelse av proble­ met, er selve formen ikke særlig oversiktlig. Det er hensikts­ messig å velge en annen form som er mer kortfattet, men som inneholder nøyaktig den samme beskrivelse. Modellen er ut­ trykt i symbolsk form i figur 4. Slik er det lettere både å få et inntrykk av modellens innhold, samt å arbeide videre med den: Definisjon av variablene:

En mer hensiktsmessig modellformulering

Vj = det produserte antall dreiebenker av type M—101 X2 = det produserte antall dreiebenker av type M—102 Z = salgsinntekt i kroner

Formulering av problemet i en matematisk modell: Finn de verdier av Xx og X2 som maksimerer mål­ funksjonen Z = 5000X1 + 6000Z2

med begrensningene

Figur 4

14

20 Xj + 15 X2 < 300 (timer) 10 Xt + 20 X2 < 200 (timer) ______.

—

Vi kaller denne modellen for en lineær programmeringsmodell, og selve fagområdet som behandler denne form for modell­ bygging for lineær programmering, forkortet til LP. Begrepet programmering er avledet fra engelsk, hvor det har betydningen planlegging eller handlingsprogram?.

Kort definisjon av lineær programmering

Maksimering/minimering av en lineær målfunksjon under lineære beskrankninger

Vi skal senere se nærmere på en LP-modells egenskaper, hva begreper som lineær/linearitet egentlig innebærer, og eksempler på ikke-lineære modeller/ulinearitet. (Vi vil i det følgende bruke ordet beskrankning som navn på en begrensning uttrykt i mate­ matisk form, slik som i figur 4, nederst.) Planleggingsproblemet til MOCO er nå beskrevet i form av en matematisk modell, men det er ikke løst. Vi trenger en teknikk/ løsningsmetode som kan gi oss de produksjonsmengder vi søker. Siden problemet til MOCO er lite av dimensjon, det inneholder bare to ukjente størrelser, kan vi løse det ganske enkelt ved å benytte en grafisk fremstilling, bygget på nedenstående aksekors: x2-

— *1

Figur 5

Aksen Xx representerer produksjonsvolum av type M—101, mens aksen X2 representerer produksjonsvolum av type M—102. La oss sette verdier på de to aksene Xr og X2 og avmerke et punkt P i figuren: *211

Figur 6 15

Hva er tolkningen av punktet P?

Som i figur 4 representerer Xx det produserte antall dreie­ benker av type M-101, og X2 det produserte antall dreiebenker av type M—102. Det tilfeldig valgte punkt P representerer nå et produksjonsprogram som består av fem type M—101 og seks type M—102dreiebenker. Vi vet imidlertid ikke om P representerer det beste produksjonsprogram, ikke engang om P er mulig. Vi må benytte de begrensninger vi har beskrevet tidligere til å tegne opp et mulighetsområde (også kalt løsningsrom), dvs. det område som inneholder de produksjonsprogrammer som er mulige å realisere, og som vi skal velge blant. La oss se på beskrankningen angående tid i avdeling A (husk at enheten er timer): 20Jfj + 15%2 0, X2 > 0. Glem aldri å drøfte om modellens variabler har slike beskrankninger. Vi har heller ikke tatt hensyn til at vi har en minsteenhet på 1 dreiebenk. Et brukbart produksjonsprogram må nød­ vendigvis bestå av hele dreiebenker, det er vanskelig å tenke seg at 3/4 dreiebenk har noen særlig salgsverdi. Dette medfører at mulighetsområdet strengt tatt ikke er hele det skraverte området i figur 8, men bare de heltallige punkter i området. Dette er illustrert i figur 13. Her er de mulige produksjonsprogrammer avmerket som små ringer:

W

io 0. Merkat alle beskrankningene i dette tilfellet opptrer som likheter. Det skyldes at summen av de tilgjengelige kvanta hos avsenderne er 12 + 10 +11 = 33, det samme som summen av behovene hos mottagerne som er 13 + 5 + 15. Det kan derfor ikke bh slakk eller overskudd noe sted. Merk også at vi har satt opp beskrankningene på en særlig oversiktlig måte som viser at modellen har en ganske spesiell struktur: Hver variabel forekommer i bare to beskrankninger, en for avsender og en for mottaker. Dessuten er summen av avsenderbeskrankningene lik summen av mottagerbeskrankningene. Alle venstresidekoeffisientene er enten 1 eller 0. Det skal senere vise seg at vi kan utnytte denne strukturen til å løse slike tran­ sportproblemer på en langt lettere måte enn å benytte LPprogrammer som er laget for å løse det generelle lineære programmeringsproblem, og som ikke tar spesielle hensyn til modellens detaljerte form.

★ 4 Følgende utskriftssekvens fra et generelt LP-program viser mellomregninger, fra en første, brukbar ikke-optimal løsning frem til optimal løsning. Sekvensen er supplert med tabeller som lettere viser hvordan transporten skjer (Xy er skrevet ut som XIJ): STARTBASIS: Z = 1150 XCL XAN XBN XBL XBM

= = = = =

11 12 3 2 5

L

A B C

M

2 11

5

L 2

M

N 12 3

ETTER ITERASJON 1 Z= 1050 XCL XAN XBN XAL XBM

= = = = =

11 10 5 2 5

A B C

5

N 10 5

11

ETTER ITERASJON 2 Z = 900 XCL XAN XBN XAL XCM

6. Lineær programmering

= = = = =

6 5 10 7 5

A B C

L 7

M

6

5

N 5 10

81

ETTER ITERASJON 3 Z = 850

xcl xcn

=

=

XBN = XAL = XCM =

i 5 10 12 5

A B C

L 12

M

1

5

N

10 5

SOM ER OPTIMAL LØSNING.

★ 5 Vi ser at av 9 mulige transportveier, blir bare 5 benyttet i den optimale løsning. Legg videre merke til at dette også gjelder samtlige transportplaner i mellomregningene. Dette er ingen til­ feldighet og kan forklares ut fra teorien for lineær programmering. Det skal vi komme tilbake til senere. Alle transportkvanta er blitt heltallige, selv om det i dette eksemplet ikke er påkrevet. Dette kan også forklares ut fra teorien: Dersom avsenderkvanta og behov er heltallige, vil løsningsverdiene også bli det. Oppgave 35a

Finn optimal transportplan når: — Kostnaden for A — L økes til 30. — Kostnaden for B — N økes til 55. — Det ikke er anledning til å sende noe fra A til L. — A har ytterligere 2 tonn tilgjengelig, samtidig som behovet hos L og M økes med 1 tonn. Ta først hver endring isolert i forhold til de opprinnelige data og foreta deretter alle endringene samtidig.

Generell formulering av transportmodellen

Det kan være på tide å vise hvordan TP-modellen kan formuleres generelt: — Gitt m avsendere, hver med en tilgjengelig varemengde på st enheter, i = 1, . . . , m. — Gitt n mottagere, hver med et behov på d, enheter, j ... ,n. — Gitt kostnader for forsendelse av en enhet fra i til j, ialt m • n tall. — Finn den transportplan som minimerer de totale transport­ kostnader. m n — Forutsetning: S sf = S dj i= i j= i

altså alt sendes og alle behov dekkes fullt ut.

Vi definerer følgende variabler:

= antall enheter som sendes fra i til j i = 1, . . . ,m j = 1, ... ,n ialt m • n variabler

82

Z = totale transportkostnader

Da får vi følgende TP-modell: m

n

(min) Z = S S c^X» i= i j= i

gitt

n

i = 1, . . . , m

S Xjj = Si i= i m

S Xij = dj

j = 1, ... ,n

i=i

og

X^ >0

for alle i og /

Modellen har som vi ser m + n beskrankninger i form av ligninger. Av disse er bare m + n — 1 uavhengige, kjenner vi så mange lig­ ninger, er den siste gitt av seg selv, gjennom forutsetningen om at _ totalt tilbud er lik totalt behov. Det kan vises at maksimalt m + n - 1 ruter/transportveier vil bli benyttet i den optimale transportplan. Hva om Ss; > 'Edj‘1 Det er da klart at beskrankningene ikke uten videre kan skrives som ligninger. Det er mer tilgjengelig enn det totale behov. Beskrankningene må derfor formuleres som følger: n

Xij< Si

i= 1, ... ,m

S Xjj = dj

i = 1, ... n

/=i

m i=i

Alternativt kan vi definere en ny mottager, ,,restlageret”, med m

n

behov dn+i = Z ’ ,si — S dj. Derved har vi gjenopprettet i= i /= i balansen mellom tilbud og etterspørsel og kan skrive n+ 1

Xjj = sf

i = \, . . . ,m

m

S Xy - d j

j = 1, . . . , n + 1

i=i

Kostnadene knyttet til denne ,,mottageren” er naturligvis 0 siden det ikke forekommer noen fysisk transport.

Anta at A, B og C har henholdsvis 13, 11 og 12 tonn til disposisjon, altså 1 tonn mer for alle. Hva blir nå optimal transportplan?

J

83

Vi går frem på tilsvarende måte dersom Ss, < Sd/. Ikke alle mottagerbehov kan nå dekkes, og vi må formulere beskranknin­ gene slik: n

i m S Xij

< dj

= 1, . . .

,m

j =1, ... ,n

Definerer vi en ny avsender, „totalt udekket behov”, med et n

tilgjengelig kvantum

sm

formulere ligningene: n s Xij i=i

= Si

m + 1 S Xij = dj 1=1

+ i = S dj j- 1

m

—

S sh kan vi alternativt i

i-

i = 1, . . . , m + 1 / = 1, . . . ,

77

Variablene Xm + / forteller derved hvor mye som mangler for å dekke behovet til /.

Oppgave 35c

Anta at L, M og N i eksemplet foran har et behov på hen­ holdsvis 15, 7 og 17 tonn, altså 2 tonn mer for alle. Hva blir nå optimal transportplan?

Eksempel 36 Mek A/S

Firmaet Mek A/S produserer blant annet en type deler til olje­ plattformer og ønsker å minimere de totale kostnader (produk­ sjonskostnader + lagringskostnader) over de tre månedene januar, februar og mars. Etterspørselen er beregnet til å bli hen­ holdsvis 12, 8 og 11 stk. deler for de tre månedene og forut­ settes dekket. Dessuten ønsker firmaet å ha 2 stk. deler på lager ved periodens slutt. På grunn av stigende kostnader for rå­ materialer og lønninger regner man med følgende produksjons­ kostnader per stk. (i tusen kr): Normalproduksjon Overtidsproduksjon

Januar 18 25

Februar Mars 24 26 30 32

Lagringskostnaden-e per stk. er kr 2000 i forbindelse med å få varene inn og ut av lager samt kr 1000 per måned varen ligger på lager. Deler som blir solgt i samme måried som de produ84

seres, blir ikke belastet med lagringskostnader. Maksimal produk­ sjon i hver måned er 10 stk. dersom det bare benyttes normal arbeidstid og 14 stk. hvis det benyttes overtid.

Problemet synes ikke å ha noe med transport å gjøre. Imidlertid kan vi betrakte de forskjellige måneder som henholdsvis avsendermåned og mottager-måned for produserte kvanta. ★ 1

Vi definerer

Xijk = antall enheter som produseres i måned i på måte j for forbruk i måned k, i = 1, 2, 3, j = 1, 2, k = 1, 2, 3, 4 (/ = 1 representerer normal tid, j = 2 representerer overtid)

cijk = tilsvarende kostnader per enhet

Z Oppgave 36a

= totale kostnader ved produksjon og lagring

Vis at kostnadene per enhet må bh som følger: Jan

Feb

Mars

April

Jan N

18

21

22

23

Jan 0

25

28

29

30

Feb N

24

27

28

Feb 0

30

33

34

26

29

Mars O ■ ■ 32

35

Mars N

De skraverte ruter representerer ,,forbudte forsendelser”.

Oppgave 36b

Formulér en LP-modell for problemet og forklar hvorfor den er av TP-typen.

Oppgave 36c

Kjør modellen. Velg en høy kostnad (f.eks. 999), for de for­ sendelsene” som ikke er tillatte. Påvis at overtid bare benyttes i januar. Hvor mye lagres, når er disse lagrede enhetene produsert og i hvilke måneder skal de benyttes? Er det mulig å finne løs­ ningen på systematisk måte uten bruk av edb, eventuelt på hvilken måte?

Vi ser at det maksimalt lagres 3 enheter fra en periode til neste. Hva om det hadde vært en begrensning på lagerplass til 2 enheter? Vi må da bygge opp modellen på en annen måte:

Gjøvik

imgekiøshøgskole Fi

,

_________

85

Vi definerer følgende avsendere:

1. 2. 3. 4. 5. 6. 7. 8.

Produksjon på normaltid i januar Produksjon på overtid i januar Produksjon til lager i januar Produksjon på normaltid i februar Produksjon på overtid i februar Produksjon til lager i februar Produksjon på normaltid i mars Produksjon på overtid i mars

NJ OJ LJ NF OF LF NM OM

og følgende mottagere:

1. 2. 3. 4. 5. 6. 7.

EJ LJ EF LF EM LM UK

Etterspørsel i januar Lager ved utgangen av januar Etterspørsel i februar Lager ved utgangen av februar Etterspørsel i mars Lager ved utgangen av mars Ubrukt kapasitet

Merk at lager i januar og lager i februar forekommer både som avsendere og som mottagere. Vi kan nå sette opp følgende matrise: 1 2 3 4 5 6 7 8

Etterspørsel

Tilbud

1

2

3

4

5

6

7

18 25 999 999 999 999 999 999

21 28 0 999 999 999 999 999

999 999 0 24 30 999 999 999

999 999 1 27 33 0’ 999 999

999 999 999 999 999 0 26 32

999 999 999 999 999 1 29 35

0 0 999 0 0 999 0 0

10 4 3 10 4 3 10 4

12

3

8

3

11

2

9

48

I første omgang har vi beholdt lagringskapasiteten lik 3 enheter for å vise at vi får samme løsning som tidligere. Fra inputmatrisen ser vi at i januar er kostnadene per stk. for normal produksjon til salg 18, og for produksjon til lager 21 (18 + 3 i lagerkostnader). De tilsvarende kostnader for overtidsproduksjon er 25 og 28. Alle umulige „transportveier”, som for eksempel de som representerer bruk av produksjon i februar til å dekke etterspørsel i januar, er gitt en så høy kostnad (999) at de helt sikkert ikke vil være representert i den optimale løsningen. De tidsavhengige lagringskostnadene (1 per måned) blir lagt til varer som blir liggende på lager i februar. Disse variablene er bundet sammen ved at ubrukt lagerkapasitet for januar er gitt en kostnad på 999 (vilkårlig høy kostnad for å hindre

86

variablene i å få verdi i den optimale løsning), og forsendelsesveien fra lager i januar til lager i januar er gitt 0 i kostnad. Variabelen (LJ -> LJ), kalt X32 etter plasseringen i inputmatrisen, vil nå ha en dobbeltfunksjon. Den vil være bindeleddet mellom antall produsert til lager i januar og antall av disse som blir solgt i februar eller fortsatt blir liggende på lager, og den vil represen­ tere ubrukt lagerkapasitet i januar. For eksempel, hvis det ikke blir produsert til lager i januar, vil X32 bli satt lik 3, da dette tilfredsstiller beskrankningene og gir 0 i kostnad. Hvis det i januar er blitt produsert 1 enhet til lager (X12 eller X22 lik 1) blir X32 tvunget til å ta verdien 2, og enheten må enten selges i februar eller bli Eggende på lager til mars (X32 eller X34 må ta verdien 1). Forbindelsen mellom produksjon/lagerbeholdning i februar og salg/lagerbeholdning i mars fungerer etter det samme prinsippet. Oppgave 36d

Kontrollér at minimal kostnad er 767 for følgende beslutninger: - Januar: Inngangslager: 0. Produsér 10 på normaltid og 3 på 4 overtid hvorav 1 til lager. Utgangslager: 1. - Februar: Inngangslager: 1. Produsér 10 på normaltid hvorav 2 til lager. Utgangslager: 3. - Mars: Inngangslager: 3. Produsér 10 på normaltid og ta 1 fra lager. Utgangslager: 2.

Oppgave 36e

Vi minsker nå lagringskapasiteten til 2 enheter. Det medfører endringer i modellen for avsender 3 og 6 samt mottager 2 og 4. Vis at ny optimal løsning blir 3 dårligere enn den forrige. Hvilke endringer er skjedd i produksjon og lagring?

Oppgave 36f

Siste dag i februar mottar Mek A/S en ordre på 12 stk. deler som skal leveres i april og 12 stk. som skal leveres i mai. Pro­ duksjonskostnadene i april og mai er beregnet til å bli henholds­ vis 27 og 30 ved normalproduksjon og 32 og 35 ved overtidsproduksjon. Ved utgangen av mai ønsker firmaet å ha 3 deler på lager. Andre beskrankninger og kostnader er som tidligere. Finn den produksjonsplan som minimerer totale kostnader over de tre månedene mars, april og mai.

Eksempel 37 Produksjon og distribusjon

A/S Unicum har sin produksjon av varen Nix fordelt på de tre bedriftene A, B og C, med kapasitet på henholdsvis 18, 10 og 11 enheter per dag. På grunn av forskjellig utstyr og effektivi­ tet har de tre bedriftene ikke samme kostnader ved frem­ stilling av Nix: A produserer for kr 90 per stk., B for kr 95 per stk. og C for kr 80 per stk. Nix har en fast markedspris på kr 120, frakt inkludert. A/S Unicum har oppnådd kontrakt om faste daglige leveringer av Nix med fire forbrukere, R, S,

87

T-og U, på henholdsvis 9, 5, 7 og 6 enheter. Transportkost­ nadene i kroner per enhet er gitt som følger:

Oppgave 37a

Hvilke forbrukere må de forskjellige bedriftene levere til for at A/S Unicum skal oppnå størst mulig fortjeneste? Vis at maksimalfortjenesten blir 785. Hvilke av fabrikkene får ikke utnyttet sin kapasitet?

Oppgave 37b

Hva om produksjonskostnaden ved bedrift B reduseres med kr 10?

Oppgave 37c

Hva om behovet hos U øker til 10 enheter?

Eksempel 38 Fire avsendere, seks mottagere

Gitt et vanlig TP-problem med balansert tilbud og etterspørsel: Tilgjengelige kvanta hos 4 avsendere er henholdsvis 50, 40, 60 og 31 enheter. Behovene er henholdsvis 30, 50, 20, 40, 30 og 11 enheter hos de 6 mottagerne. Kostnadene ved å sende en enhet fra avsender i til mottager j er gitt ved følgende tabell:

Til 1 Fra 2 3 4

1

2

3

4

5

6

2 3 3 4

1 2 5 2

3 2 4 2

3 4 2 1

2 3 4 2

5 4 1 2

Oppgave 38a

Formulér en LP-modell for dette problemet.

Oppgave 38b

Finn den optimale distribusjonsplan og vis at den har en minimal kostnad lik 330.

Oppgave 38c

Det finnes forøvrig flere optimale løsninger på dette problemet. Forsøk å finne flere.

Eksempel 39 Tre lagre, syv mottagere

Et firma har tre lagre, LI, L2 og L3 som har henholdsvis 10 000, 5000 og 16 000 enheter av et mindre produkt. I neste måned skal det sendes henholdsvis 2000, 1000, 3000, 4500, 500, 600 og 950 enheter til 7 mottagere, Dl, D2, D3, D4, D5, D6 og D7. Kostnadene per enhet for transport er som følger:

88

Dl D2 D3 D4 D5 D6 D7 LI L2 L3

10 19 20

8 25 17

16 18 20

2 7 5

10 12 14

25 18 16

18 19 17

Oppgave 39a

Formulér en LP-modell for dette problemet.

Oppgave 39b □

Finn den (de) optimale transportplan(er).

Oppgave 39c □

Foreta en økning på 50 % i kostnadene ved forsendelse fra LI til D1, D2 og D3 og vis hva optimal løsning da blir.

Eksempel 40 Fem fabrikker, fire grossister

Konsernet Grisk har 5 fabrikker, Ql, Q2, Q3, Q4 og Q5 som kan produsere henholdsvis 400, 350, 200, 900 og 600 enheter av produktet ,,Julemoro”. Produktet skal selges til 4 grossister, NI, N2, N3 ogN4, som etterspør henholdsvis 350, 300, 600 og 250 enheter. Konsernet vil at kundenes behov skal dekkes uan.sett hvilke kostnader dette medfører, forøvrig er målet å oppnå størst mulig fortjeneste. Hver enhet av ,,Julemoro ” har en salgs­ pris på kr 32. Produksjonskostnadene ved de 5 fabrikkene er henholdsvis kr 11, kr 11, kr 12, kr 10 og kr 11. Transportkost­ nadene fra fabrikk til grossist er gitt i tabellen under, alle tall i kroner per enhet. NI N2 N3 N4 Ql Q2 Q3 Q4 Q5

8 6 4 8 9 2 5 6 13

9 7 13 4 9

2 11 2 6 9

Oppgave 40a □

Finn konsernet Grisks maksimale fortjeneste og den tilhørende produksjons- og transportplan.

Oppgave 40b

Hva må transportkostnadene fra Q2 til N3 være for at denne forsendelsesruten blir aktuell?

Eksempel 41 Østlandsdistribusjon

Firmaet Østlandsdistribusjon A/S arbeider for et konsern som har tre fabrikker, en i Gjøvik, en i Hamar og en i Moss. Disse fabrikkene produserer i et gitt tidsrom henholdsvis 300, 300 og 100 enheter av en vare. Østlandsdistribusjon A/S frakter disse varene til syv store lagre, i Fredrikstad, Halden, Kongsvinger, Magnor, Oslo, Sarpsborg og Ørje. Utfra etterspørsel og lagerplass er behovet for varen over en tilsvarende periode satt til henholds89

vis 150, 100, 80, 10, 250, 150 og 10 enheter. Det antas at trans­ portkostnadene er proporsjonale med veiavstanden mellom av­ sender og mottager, og følgende veiavstander gjelder: Gjøvik Halden Hamar Kongsvinger Magnor Moss Oslo Sarpsborg Ørje

Fredrikstad 214 Gjøvik 37 243 Halden 211 37 240 Hamar 179 139 179 102 Kongsvinger 197 176 160 139 37 Magnor 33 181 62 1 78 146 218 Moss 88 126 117 123 91 128 55 15 216 27 213 164 187 35 93 205 59 191 126 98 89

Oslo 90 94

Sarpsborg 78

Oppgave 41a

Hva blir den optimale transportplan? Hvilke behov kan ikke dekkes med den nåværende produksjonskapasitet?

Oppgave 41b

Hvordan endrer planen seg når behovet i Fredrikstad reduseres til 50 enheter?

Oppgave 41c

Hva om bedriften i Gjøvik flyttes til Moss? Hvor mye mindre vil antall stykk-kilometre bli?

Oppgave 4Id

Hva skjer dersom det opprettes et nytt lager i Askim med et behov på 100 enheter, samtidig som behovet i Oslo og i Sarpsborg reduseres med 50 enheter hver? Bruk NAFs veibok.

Jobbfordeling

Kapitlet tar utgangspunkt i et problem der det gjelder å fordele et gitt antall søkere på et tilsvarende antall jobber, slik at total nytte maksimeres. Problemer av denne typen kan formuleres som LP-modeller, og kapitlet illustrerer dette. Videre vises at modellene får samme struktur som en TP-modeli. Imidlertid er jobbfordelingsmodellen (eng. job assignment) egentlig et spesialtilfelle av TP-modellen.

Eksempel 42 Fire søkere, fire jobber

90

Et firma har 4 jobber som skal besettes ved intern rekruttering. Det viser seg å være 4 søkere til jobbene, og firmaet står overfor spørsmålet: Hvilken søker skal få hvilken jobb? For å avgjøre dette har firmaet vurdert hver enkelt søkers kvalifikasjoner i forhold til hver enkelt jobb. Man har søkt å uttrykke kvalifika­ sjonene tallmessig gjennom et poengsystem fra 0 til 10. Poeng­ tallet 10 betyr at firmaet vil ha maksimal nytte av personen i

den aktuelle jobb, poengtallet 0 betyr at personen er fullstendig ukvalifisert. Nedenstående representerer de vurderte kvalifika­ sjoner:

Søker

7 2 3 4

1

Jobb 2

3

4

7 3 2 2

9 6 2 2

5 8 5 5

0 7 8 8

Firmaet ønsker å finne den jobbfordeling som maksimerer total nytte. ★ 1 Det er naturlig å definere handlingsvariabler med to indekser, en som beskriver søker og en som beskriver jobb. Vi kan gjøre det slik:

"Xij = „den brøkdel av søker i som får jobb /” i= 1,2, 3,4 7=1,2, 3,4 ialt 16 variabler

Denne definisjonen kan virke noe merkelig, hva om modellen f.eks. gir verdien 1/2 på en eller flere av variablene? Det viser seg imidlertid at de modeller vi får av denne type problemer alltid gir løsningsverdier som begrenser seg til de akseptable 0 og 1. Vi kan derfor definere mer lettforståelig på følgende måte: % ’’

11 dersom søker i får jobb j |0 dersom søker i ikke får jobb j.

Denne modellen kan sies å ligge på grensen til en heltalls lineær programmeringsmodell, idet vi må ha heltallige løsningsverdier, men vi får disse automatisk selv om vi bare betrakter modellen som en helt ordinær LP-modell. Dessuten definerer vi Z = samlet nytte ★ 2

(max) Z = 7Xn + 9JT12 + 5JT13 + 0X14 + 3V21 + 6X22 + 8X23 + 7X24 + 2X31 + 2X32 + 5JL33 + 8X34 + 2V41 + 2V42 + 5JL43 + 8V44 ★ 3 Hver søker gir opphav til en beskrankning som sikrer at han/hun får en jobb. Likeledes gir hver jobb opphav til en be­ skrankning som sikrer at den blir besatt med en søker. Ialt får man derfor 8 ligninger:

91

★ 4 Følgende utskriftssekvens fra et generelt LP-program viser mellomregning frem til optimal løsning, illustrert ved tabeller som lettere viser hvordan jobbfordelingen skjer:

★ 5 Vi ser at samtlige variabler får verdien 0 eller 1 som nevnt tidligere. Maksimal nytte/verdi blir 27 ved at søker 1 får jobb 2, søker 2 får jobb 3, søker 3 får jobb 4 og søker 4 får jobb 1. Merk også at søker 3 og søker 4 har nøyaktig de samme kvalifika­ sjoner og like gjeme kunne byttet jobber. Det finnes altså to optimale løsninger (ihvertfall). Vi konstaterer at å kjøre denne modellen på et generelt LPprogram krever mye arbeid ved punching av O’er og 1 ’ere. Vi kan få frem optimal løsning på en enklere måte ved å kjøre modellen

92

på et TP-program. Modellen er nemlig en transportmodell av en forenklet form. Studerer vi beskrankningene og sammenligner med transport-modellene, ser vi at sokerligningene har samme form som avsenderligningene og at jobbligningene har samme form som mottagerligningene. Vi har imidlertid at alle tilgjenge­ lige mengder” og alle ,,behov” er hk 1. Altså s, = dj = 1 for alle i og j. Målfunksjonen skal maksimeres siden vi har uttrykt den som samlet nytte i stedet for kostnader.

Oppgave 42a

Generell formulering av jobbfordelingsmodellen

Hvor lavt poengtall må søker 2 ha på jobb 3 for at han/hun ikke skal få denne jobben? Selv et TP-program representerer en tungvint måte å behandle denne typen modell. For det første er alle høyresidekoeffisientene gitt hk 1 og skulle derfor kunne behandles uten spesiell datainnlesning. For det andre er det grunn til å tro at modellens helt spesielle struktur burde gjøre det mulig med skreddersydde beregnings­ metoder. Dette viser seg å være tilfelle. Vi skal vise hvordan jobbfordehngsmodellen kan formuleres generelt: — Gitt r søkere på r jobber. — Gitt nytten Cy ved at søker i får jobb j, i alt r • r tall. — Finn den jobbfordehng som maksimerer total nytte. Vi definerer følgende variabler:

x„ =

! dersom søker i får jobb / . r 0 dersom søker i ikke får jobb j Z = samlet nytte. Da får vi følgende jobbfordehngsmodell: r

r

(max) Z = S S c^Xy i= 1 j= 1 2 Xij = 1 /=i

i = 1, . . . , r

2 xa =1

j = l, ... ,r

gitt

Modellen har som vi ser 2r beskrankninger i form av ligninger. Bare r av de r2 variablene kan få verdien 1 (hvorfor?). Dersom antall søkere er større eller mindre enn antall jobber, kan dette behandles på samme måte som i den tilsvarende TPmodehen.

Eksempel 43 Mannskapsstasjonering

Et flyselskap har daglige ruter i begge retninger mellom byene Oslo og Helsinki. Rutetabellen er som følger (alle klokkeslett er i lokal tid): 93

Ankomst Oslo 0900 0945 1530 1915 2030

Avgang Helsinki 0730 0815 1400 1745 1900

Rute 1 3 5 7 9

Rute 2 4 6 8 10

Avgang Oslo 0700 0745 1100 1800 1930

Ankomst Helsinki 1000 1045 1400 2100 2230

Dette betyr at flyet går direkte fra Oslo til Helsinki, en tur på 2 timer. I motsatt retning er det mellomlanding i Stockholm, slik at turen Helsinki—Oslo tar 2^ timer. Tidsforskjellen mellom Oslo og Helsinki er 1 time. Selskapet har fem flymannskap, og hvert av dem kan være stasjonert enten i Oslo eller i Helsinki. Hvert mannskap flyr fra sitt stasjoneringssted til den andre byen, og må der ha en hvilepause på minst 1 time før det flyr tilbake. Dette kan gjerne skje neste dag, dvs. mannskapet overnatter. Problemet er følgende: Hvilke ruter skal kobles sammen (to og to)? (Når to ruter er koblet, flyr altså mannskapet østover på den ene og vestover på den andre.) Dessuten: For en gitt sam­ menkobling av to ruter: Hvor skal flymannskapet stasjoneres?

Løsning

Denne problemsituasjonen (som er lånt fra Ackoff & Sasieni: Fundamentals of Operations Research) skal illustrere at jobbfordelingsmodellen også kan benyttes i andre og mer subtile situasjoner enn de som er beskrevet foran i dette kapitlet. Først legger vi merke til at dersom rute i skal kobles med rute j, så kan vi på forhånd, før oppsetting av en LP-modell, regne ut hvor mannskapet skal stasjoneres. Eksempelvis: Dersom rute 1 kobles med rute 10 og basen er Helsinki, må man vente i Oslo fra 0900 til 1930 — ialt 10,5 timer. Hvis basen er Oslo, må man derimot vente i Helsinki fra 2230 til 0730 neste dag — i alt 9 timer. Det lønner seg altså å ha base i Oslo for denne koblingen. Vi kan sette opp tabeller over ventetider for alle sammenkoblin­ ger for begge basealtemativ (tallene er i hele kvarter):

Ventetid 2

1 3 5 7 9

94

88 85 62 47 42

Base i Helsinki 4 6 8

10

36 33 10 91 86

42 39 16 97 92

91 88 65 50 45

8 5 78 63 58

1 3 5 7 9

2

4

86 89 16 31 36

83 86 13 28 33

Base i Oslo 6 8

10

42 45 68 83 88

36 39 62 77 82

70 73 96 15 20

For hver kombinasjon plukker vi ut det minste tall, merker de som har base i Helsinki med ★, og merker de som har samme ventetid uansett base med Da får vi følgende tabell: Minimum ventetid

1 3 5 7 9

2

4

6

8

10

86 * 85 16 31 36

83 86 13 28 33

8 * * 5 * 78 15 20

36 * * 33 * 10 83 * 86

36 ** 39 16 77 82

1

Vi kan nå definere følgende variabler:

1 dersom rute i kobles med mte / 0 dersom rute i ikke kobles med rute / Z = samlet ventetid

* ★ 2

Med Cij for ventetid i koblingen rute i — rute / får vi 5

5

(min) Z = S S i=\i=\

zy^ ij

5

/=!

z = l,2, 3,4, 5

(Hver rute fra Helsinki må kobles med en av rutene fra Oslo.) 5

S Xif

i =1,2, 3, 4, 5

(Hver rute fra Oslo må kobles med en av rutene fra Helsinki.) Vi ser at modellen er nøyaktig på samme form som en generell jobbfordelingsmodell. Antall „søkere” = antall Jobber” = 5. (Vi har omnummerert rutene: i = 1, 2, 3, 4, 5 tilsvarer henholds­ vis 1,3, 5, 7, 9 og / = 1, 2, 3, 4, 5 tilsvarer henholdsvis 2, 4, 6, 8, 10.)

Oppgave 43a

Vis at optimal løsning innebærer at minimal ventetid er ter lik 28^- timer for følgende ruteopplegg: Rute 1 kobles med rute 10, flymannskapet stasjoneres i Rute 3 kobles med rute 6, flymannskapet stasjoneres i Rute 5 kobles med rute 8, flymannskapet stasjoneres i Rute 7 kobles med rute 4, flymannskapet stasjoneres i ute 9 kobles med rute 2, flymannskapet stasjoneres i

115 kvar-

Oslo Helsinki Helsinki Oslo Oslo

95

Oppgave 43b

Ser vi nærmere på problemet, finner vi snart ut at rute 1 ikke kan kobles sammen med rute 2. Flyr mannskapet fra Oslo 0700 en morgen, vil de ikke kunne rekke tilbake til flyturen 0700 neste morgen. Dette vil også være tilfelle for flere andre kombinasjoner av ruter, finn disse. (For å være sikker på at disse ikke kommer med i den endelige løsningen, kunne vi ha satt „uendelig” stor ventetid for disse kombinasjonene.)

Oppgave 43c □

Hva hender dersom rute 5 fra Helsinki fremskyndes to timer slik at avgang blir kl. 1200?

Oppgave 43d □

Hva skjer dersom det opprettes en ny rute 11 fra Helsinki med avgang kl. 2100 og ankomst kl. 2230, samtidig som det opp­ rettes en ny rute 12 fra Oslo med avgang kl. 1300 og ankomst kl. 1600?

Eksempel 44 Fem søkere, seks jobber

Gitt et jobbfordelingsproblem med 6 jobber, men bare 5 søkere. Poengsystemet er det samme som i eksempel 42 og nedenstående tabell gir verdiene:

Søker

1 2 3 4 5

1

2

10 10 6 5 2

0 9 7 4 1

Jobb 3 3

7 7 7 5

4

5

6

3 1 7 6 6

3 4 8 0 2

10 9 7 4 8

Oppgave 44a

Formulér en LP-modell for dette problemet.

Oppgave 44b □

Finn optimal jobbfordeling.

Oppgave 44c □

Det dukker opp en søker 6 med følgende nyttetall: 4, 10, 8, 5, 8, 3. Hvordan ser modell og optimal løsning nå ut?

Oppgave 44d

Vi tenker oss at jobbene 1 og 2 blir rasjonalisert vekk. Hva blir nå den optimale jobbfordeling, med og uten søker 6?

Eksempel 45 Seks laboranter, seks jobber

Dr. Smart har nylig ansatt seks nye laboranter som skal settes til å utføre seks kompliserte biokjemiske analyser. Hver av disse ana­ lysene krever på hver sin måte stor nøyaktighet og ferdighet. Smart har derfor bestemt at hver enkelt laborant skal spesialisere seg på en bestemt av disse analysene. På bakgrunn av tidligere ut­ dannelse, praksis og ferdighetsprøver har Smart kartlagt de enkelte laboranters ferdigheter, og resultatene er gitt i tabellen neden­ under (høye tall viser stor ferdighet).

96

j

st

Laborant

1 2 3 4 5 6

1

2

15 21 19 13 18 4

6 19 15 12 15 14

Analyse 3 16 12 8 13 15 15

4

5

6

10 7 11 11 10 8

20 3 14 16 18 10

11 12 14 14 17 18

Oppgave 45

Hvilken analyse vil de enkelte laboranter bli satt til å utføre når Smart ønsker maksimal utnyttelse av ferdighetene?

Eksempel 46 Svømmelandslag

Det skal tas ut et landslag på 4 x 100 meter medley til EM i svømming. (Medley er en konkurranseform hvor 4 svømmere svømmer hver sin stil: rygg, bryst, butterfly og fri. Ingen kan svømme mer enn 1 etappe.) Landslags-stallen består av 5 svøm­ mere, og for å få et beslutningsgrunnlag har det vært arrangert prøvesvømming i alle 4 stilarter. Denne ga følgende resultater:

Svømmer A Svømmer B Svømmer C Svømmer D Svømmer E

Rygg

Bryst

Butterfly

Fri

1.03,2 1.02,5 1.08,3 1.04,2 1.06,0

1.10,5 1.05,6 1.10,8 1.12,5 1.11,4

58,8 1.04,5 1.01,9 59,4 1.02,7

54,6 52,5 53,7 58,2 53,0

Oppgave 46a

Formulér en jobbfordelingsmodell for dette problemet.

Oppgave 46 b

Finn det optimale svømmelandslag utfra to beslutningskriteria: — Oppnådd tid i prøvesvømmingen — Oppnådd plassering i prøvesvømmingen Diskutér!

Vi har vist hvordan jobbfordelingsproblemet, der m søkere på m jobber skal fordeles med hensyn på maksimal nytte eventuelt minimal kostnad, kan formuleres som en LP-modell. Videre har vi vist at modellen har samme struktur som TP-modellen. Dermed kan denne type modeller behandles både ved hjelp av LP- og TPprogrammer. I eksempel 43 vises at det finnes problemer som i utgangspunk­ tet ikke synes å ha noe med jobbfordeling å gjøre, men som like­ vel leder til en modell med struktur som en vanlig jobbfordelings­ modell. Dette er analogt med at jobbfordelingsproblemet selv ikke synes å ha noe med varetransport å gjøre, men at modellen likevel får TP-modellens struktur. 7. Lineær programmering

97

Nettverk Kapitlet introduserer en gruppe av problemer som lett kan be­ skrives ved hjelp av nettverk. Typiske slike problemer har man i korteste/billigste rute, „Transshipment”, „Travelling Salesman” der nettverket representerer transportruter, og i Kritisk linje der nettverket representerer prosjektavhengighet. Modeller av disse problemene blir formulert både som generelle LP-modeller og som TP-modeller. Kapitlet introduserer også TP-modeller med kapasitetsbegrensninger.

Eksempel 47 Korteste reiserute

Firmaet Slips og Sløyfe A/S skal sende et parti slips fra fabrikken i byen U til en kunde i byen R. Forsendelsen må gå gjennom en eller flere av byene A — I, og de mulige ruter er som følger:

Figur 30 Til hver direkte forbindelse mellom to byer er det angitt et tall som vi for enkelhets skyld kan tolke som antall mil. Eksempel­ vis er det fire mil mellom byene E og H. Alternativt kan vi tolke tallene som kostnader ved forsendelse mellom de respektive byer, det har ingen betydning for den videre fremstilling og forståelse. Firmaet ønsker å finne den korteste (alternativt billigste) rute mellom byene U og R.

Løsning

Dette er et typisk nettverksproblem og kan formuleres på for­ skjellige måter ved hjelp av LP-modeller. Vi skal her demonstrere to måter:

I. Bruk av vanlig LP-modell 98

LP-modell av korteste rute problemet

★ 1

Vi definerer 1 dersom veien mellom byene S og T ligger på den _ korteste rute 0 dersom veien mellom byene S og T ikke ligger på den korteste rute

(Denne definisjonen er analog med den vi benyttet i forbindelse med jobbfordeling. Det viser seg at VST alltid blir lik 1 eller 0, det er ingen fare for at vi får f.eks. 1/2!) Ved å studere nettverket ser vi at det er 20 direkte veier mellom to byer. Vi får altså 20 variabler. Videre definerer vi Z = antall mil (kostnad) for ruten mellom U og R. ★ 2

Målfunksjonen blir

(min) Z — SScgT-VgT

der summasjonen går over alle eksisterende kombinasjoner av S og T, ialt 20 ledd. cST er antall mil (kostnad) fra S til T. ★ 3 Beskrankning for byen U (som vi kaller kilden (eng. source), i overensstemmelse med vanlig nettverkterminologi): Vi vet at én og bare én av veiene ut fra U ligger på den korteste rute, dvs. ^UA

^ub

3" ^uc = 1

Beskrankninger for byene A - I: Vi vet ikke om den enkelte by ligger på den korteste rute eller ikke. Imidlertid vet vi at dersom en by ligger på den korteste rute, så må det benyttes en vei inn i byen og en vei ut av byen. Summen av variabelverdiene for alle veier som går inn i en by må derfor være lik summen av variabelverdiene for alle veier som går ut av en by. Eksempelvis for byen E: Det er to veier inn, fra A og fra B. Det er to veier ut, til H og til I. Dermed må vi ha

^eh + ^ei

^ae "f T be

eller

~^ae — 2fBE + XEH + XEI = 0

Tilsvarende får vi åtte likheter i tillegg for de åtte resterende byene. Oppgave 47a

Formulér det komplette sett av beskrankninger for byene A, B, C, D,F,G, H, I.

Beskrankning for byen R (som vi kaller sluket (eng. sink), også dette i overensstemmelse med vanlig nettverk-terminologi): En av veiene inn til R må benyttes, dvs. 99

^HR + ^IR ~ 1

Ialt får vi altså 11 beskrankninger i form av likheter. Høyresideverdiene er lik 0, bortsett fra for første og siste likhet som repre­ senterer henholdsvis kilde og sluk, der er høyresideverdiene lik 1. ★ 4

Ved edb-kjøring får vi

^ub =^bg =^gi =^ir = 1, alle andre variabler Hk 0, eller ^ua = ^af = ^fh = ^hr = 1, alle andre variabler lik 0. Hvilken løsning vi får er avhengig av rekkefølgen av Hgningene. Den korteste rute er således 20 mil og er

U-B-G-I-R

eller

U-A-F-H-R

Det er altså to optimale løsninger.

Oppgave 47b

Ta utgangspunkt i den optimale løsning du selv fant. Øk vei­ lengden for en av veiene med 1 mil og vis at du da får frem den alternative optimale løsning. ★ 5 Å benytte generell LP som ovenfor, er en metode som ofte fungerer dårlig i praksis. Årsaken er naturligvis at selv små nettverk leder til meget store modeller. Vi får én variabel for hver vei mellom to byer samt én likhet for hver by. I eksemplet ovenfor hadde vi altså 20 variabler og 11 likheter, noe som med­ førte et ikke ubetydelig regnearbeid, mens de optimale løsninger lett kunne finnes ved å se på nettverket samt foreta noen enkle summasjoner. Når vi likevel velger å illustrere nettverksproble­ mets løsning innenfor rammen av generell LP, er det fordi det gir både en god trening i modellformulering, samt en innsikt i hva nettverksproblemer egentlig består av.

II: TP-modell av korteste rute problemet

100

Bruk av transportmodell (TP-modell)

Problemet representerer egentlig et transportproblem av en helt spesiell type. Dersom vi ser det i lys av avsnittet om transport­ problemer, ser vi at vi egenthg har et transportproblem med bare 1 avsender (U) og 1 mottager (R). Til gjengjeld har vi en rekke transportpunkter som selv hverken har noe tilgjengehg eller har noe behov, men som fungerer som mellomstasjoner, f.eks. med sikte på omlasting av varene. Denne typen problem kalles for et Tmnsshipment-problem, og en modell med den struktur som er beskrevet foran kalles for en Transshipment-modell (TSP-modell). Det viser seg at en Transshipment-modell ved enkle midler kan modifiseres til en

vanlig transport-modell og dermed løses ved de metoder/edbprogrammer som er utviklet for denne. Modifikasjonen skjer på følgende måte: • Alle transportpunkter, enten det dreier seg om kilde, sluk eller mellomstasjoner, oppfattes både som avsendere og som mottagere. Transportskjemaet blir derfor kvadratisk, med antall rader lik antall kolonner lik antall transportpunkter. • Kostnadene/milene i transportskjemaet fastsettes på følgende måte: - De kostnader som er gitt for nettverket, føres inn direkte. - Kostnadene langs hoveddiagonalen, dvs. for „forsendelse fra byen S til seg selv”, settes overalt lik 0. - Alle andre kostnader settes lik store tall (f.eks. 999) for å umuliggjøre transport langs veier som ikke eksisterer. (Merk at det er mulig å ha en vei mellom byene S og T hvor transport kan foregå begge veier, med forskjellig kostnad. Vi skal vise eksempel på dette senere.) I dette eksemplet får vi altså en transport-modell med 11 „avsendere” og 11 ,,mottagere”. De tilgjengelige mengder og behov i transportskjemaet fast­ settes på følgende måte. Kall den totale tilgjengelige mengde for X. X adderes så til samtlige transportpunkters virkelige tilgjen­ gelige mengde og behov. Alle mellomstasjoner får dermed en til­ gjengelig mengde lik behov, lik X. Kilden får en tilgjengelig mengde lik virkelig tilgjengelig mengde pluss X og et behov lik X. Sluket får en tilgjengelig mengde lik X og et behov lik virke­ lig behov pluss X. I dette eksemplet er X lik 1 (det er 1 parti slips som skal sendes). Alle tilgjengelige mengder og behov i transportskjemaet blir derfor 1, bortsett fra tilgjengelig mengde hos U samt behov hos R, som begge blir 1 + 1=2. Begrunnelsen for denne fremgangsmåten er litt for omfattende til at vi vil presentere den her, og den er heller ikke nødvendig for å benytte metoden. Interesserte henvises derfor til annen litteratur. Kostnadsmatrisen blir da

101

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5

6

7

8

9

10

11

0 999 999 999 999 999 999 999 999 999 999

5 0 999 999 999 999 999 999 999 999 999

4 999 0 999 999 999 999 999 999 999 999

9 999 999 0 999 999 999 999 999 999 999

999 3 6 999 0 999 999 999 999 999 999

999 6 7 999 999 0 999 999 999 999 999

999 3 999 12 999 999 0 999 999 999 999

999 999 5 8 999 999 999 0 999 999 999

999 999 999 999 7 4 6 8 0 999 999

999 999 999 999 999 9 8 4 999 0 999

999 999 999 999 999 999 999 999 6 7 0

Vi får følgende transportplan:

1 2 3 4 5 6 7 8 9 10 11

1

2

3

4

5

6

7

8

9

10

11

1 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 1 0 1

med minimal verdi 20. Vi må nå tolke resultatene: Ett-tallene langs hoveddiagonalen kan overses, og vi står igjen med følgende ett-tall av interesse: 1-2, 2—7, 7-9, 9-11. Da 1,2, 7, 9 og 11 representerer hen­ holdsvis byene U, A, F, H og R, ser vi at vi får en av de optimale løsningene for korteste rute: U — A — F — H — R Det er utviklet egne edb-programmer for TSP-modellene, men den ovenfor beskrevne fremgangsmåte for bruk av TP-modell er tilstrekkelig for vårt bruk. Det er utviklet egne edb-programmer for TSP-modellene, men den ovenfor beskrevne fremgangsmåte for bruk av TP-modell er tilstrekkelig for oss.

Oppgave 47c

102

Benytt både fremgangsmåte I og II på følgende endringer i nett­ verket til Slips og Sløyfe: — Veilengdene for UA og UB settes lik 9, og for UC lik 5

— Veiene AF og BG ,,nedlegges” — Det opprettes en „ny” vei CE på 1 mil — Det opprettes en direkte forbindelse BI på 8 mil Endringene utføres først hver for seg og bør deretter kombineres.

Vi kan omgjøre problemet i Slips og Sløyfe til et mer avansert TSP-problem ved å anta at R har behov for hele 7 slipspartier. Av disse kan U bare levere 3. Imidlertid har firmaet tidligere opprettet slipslagre i mellomstasjonene B, D og I, nok til hhv. 1, 2 og 1 parti. Nå har vi et TSP-problem med 4 avsendere og 1 mottager. Det er enkelt å benytte et LP-program på dette. Vi kan bare skifte ut høyresidene, som i den opprinnelige modell var 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 3,0, 1,0, 2, 0, 0, 0, 0, 1,7

Oppgave 47d

med og kjøre programmet på nytt.

Vis at 2 og 5 av slipspartiene vil komme til R gjennom/fra hen­ holdsvis H og I. Slipspartiene vil da samlet ha blitt forflyttet . 109 mil.

Oppgave 47e

Lag alternativt en TP-modell etter anvisningene under II og kjør den på et TP-program.

Eksempel 48 Tre varelagre, tre kunder (fortsettelse av eksempel 35)

Tre varelagre A, B, C skulle sende totalt 33 tonn av en vare til tre kunder L, M og N. Alle kombinasjoner av varelager/kunder var i prinsippet mulig, og vi kan uttrykke problemstillingen ved hjelp av et nettverk i figur 31.

Figur 31

Figur 32

Den optimale løsning ble funnet å være %al = 12, %bn ~ 10, %CL = 1, Xcm = 5, XCN = 5.

De faktisk benyttede transportruter er angitt i figur 32, med mengde påført. 103

Vi antar nå at antall transportruter blir utvidet, slik at et hvilket som helst transportpunkt kan sende varer til et hvilket som helst annet transportpunkt, altså fungere både som av­ sender og mottager. Vi antar følgende kostnadssammenhenger: — Kostnaden ved å sende en enhet mellom to av de opprinnelige avsendere A, B, C settes lik 5. — Kostnaden ved å sende en enhet mellom to av de opprinnelige mottagere L, M, N settes lik 10. — Kostnaden ved å sende en enhet fra en av de opprinnelige mot­ tagere L,M,N tilbake til A, B, C settes lik 100. Hva blir nå den optimale transportplan?

Den nye problemstillingen er avgjort realistisk. I mange praktiske tilfeller er det f.eks. langt dyrere å sende en pakke mellom to geografisk nære punkter med dårlig forbindelse enn via omveier med rask og effektiv ekspedisjon. Vi har et typisk Transshipment-problem med 6 avsendere og 6 mottagere. Kostnadsmatrisen blir:

A B C L M N

ETTERSPØRSEL

A

B

c

L

M

N

0 5 5 100 100 100

5 0 5 100 100 100

5 5 0 100 100 100

10 60 30 0 10 10

30 20 10 10 0 10

40 40 50 10 10 0

33

33

33

46

38

48

TILBUD

45 43 44 33 33 33

Forklaring på matrisen: Summen av tilgjengelig mengde = Summen av behov = X - 33. Dette tallet er lagt til alle virkelige tilgjengelige mengder og behov. Eksempelvis blir As „tilbud” 12 + 33 = 45, mens Ls tilbud blir 0 + 33 = 33. Tilsvarende blir Bs ,,etterspørsel” 0 + 33 = 33, mens Ms blir 5 + 33 = 38. Vi får følgende transportplan: c

L

M

N

22 o o ooo o 11 o 24 0 9 0 27 6 0 0 33

med minimal verdi 530. Forklaring på resultater: Vi ser bort fra tallene på hoveddiagonalen og får *al = 22, XBA = 10, VCM =11, XLN = 9, 104

=6

Det opprinnelige transshipment-nettverk, som tillot alle ruter, uansett type transportpunkt, så ut som i figur 33 (pilene går nå begge veier i nettverket). Den optimale løsning kan representeres som i figur 34.

Figur 33

Figur 34

Det er lett å se hva forskjellen fra den forrige optimale løsning består i: - Det er blitt billigere å sende varer fra C til N via M enn direkte, nemlig 10 + 10 = 20 mot før 50. - Det er blitt billigere å sende varer fra B til N via A og L enn direkte, nemlig 5 + 10 + 10 = 25 mot før 40.

Oppgave 48a

Vis at dersom ruten fra B til A nedlegges, finnes det en ny optimal løsning som bare er 5 dårligere enn den gamle.

Oppgave 48b

Hva blir optimal løsning dersom kostnaden per enhet for ruten A — L økes til 20?

Oppgave 48c

Opprett en mellomstasjon H. Varene kan sendes fra A, B, C til H for henholdsvis 4 per enhet. Fra H sendes de videre til L, M, N for henholdsvis 12 per enhet. Hva blir optimal løsning nå?

Oppgave 48d

Dersom de seks kostnadene i oppgave 48c var like store.' Hva er den laveste verdi som fører til at H ikke benyttes? — Hva er den høyeste verdi som fører til at alle varene sendes gjennom H?

Eksempel 49 Rundtur

Disponenten på Slips og Sløyfes hovedkontor (se eksempel 47) i byen U vil gjerne besøke de forskjellige transportpunkter for å sikre at slipstransportene også i fremtiden vil foregå effektivt. Dessuten vil han besøke kunden i byen R. Disponenten ønsker å legge opp reiseruten sin slik at den blir så kort som mulig (even­ tuelt så billig som mulig hvis tallene representerer kostnader). Han sta/ ter altså i U, vil besøke de 10 andre byene og deretter vende tilbake til U. Hva blir den optimale reiserute?

105

Løsning

Denne problemstillingen har mye til felles med eksempel 42 der vi hadde et antall søkere på et tilsvarende antall jobber, med poengtall for nytte, og vi forsøker å sette opp en tilsvarende modell:

★ 1

Vi definerer

1 dersom reiseruten inkluderer veien fra by i til by / 0 dersom reiseruten ikke inkluderer veien fra by i til by j Antall variabler blir da lik 40, dobbelt så mange som antall veier, fordi disponenten ikke vet om by i skal besøkes før eller etter by 7. ★ 2

(min) Z = ZZCijXij over alle tillatte kombinasjoner av i og j. I nettverket tegnet i eksempel 49, har vi bare gitt c,y, knyttet til reiser fra „vest” mot „øst”. Det er ikke noe i veien for å sette Cji = cif slik at reiselengden (kostnaden) er uavhengig av retningen. Vi forutsetter imidlertid at c/7 * Cy på følgende måte: — rutene gjennom A og H er 1 lengre (dyrere) vestover — rutene gjennom C og I er 1 kortere (billigere) vestover. ★ 3

Beskrankningene

ZXif = 1 i

i = U, A,. . . , I, R

sikrer at når man er i by i så reiser man til en annen by. Beskrankningene ZXti = 1 i

f = U, A,. . . , I, R

sikrer at når man er i by j så er man kommet fra en annen by. På denne måten sikrer vi sammenheng i reiseruten, slik at det ikke er mulig å forlate en by uten å ha kommet til den og vice versa. ★ 4 Hvis ovenstående er en korrekt modell av problemet, er dette et jobbfordelingsproblem. Vi kan da kjøre modellen med 11 ,,søkere” og 11 Jobber”:

Oppgave 49a

106

Sett opp modellen, kjør den, og vis at minimal verdi = 1049 for følgende løsning: JfUB =^af =^bd =^cu ~^"dr =^eh = Afa = ^GC = ^HE = ^IG = = 1, alle andre variabler = 0.

★ 5 Denne løsningen må være gal utfra det opprinnelige problem! Minimalverdien er blitt altfor høy, det skyldes at dis­ ponenten ikke har funnet noen brukbar reiserute der hver by besøkes en gang. Edb-programmet plukker inn en av de veiene som ikke eksisterer og som vi trodde vi kunne unngå ved å gi den en høy kunstig verdi, nemlig „veien” D — R! Årsaken til dette er egentlig, med litt etterpåklokskap, helt innlysende: Hvis disponenten f.eks. besøker A på utreise og C på hjemreise, hvordan skal han da kunne besøke B? Husk at han skulle besøke hver by bare én gang. Problemet er derfor uløselig slik det er beskrevet. Vi kan naturligvis avstå fra ett-besøkskravet. Problemet blir imidlertid da langt større av dimensjon, og jobbfordelingsmodellen kan ikke hjelpe oss. Vi skal derfor ikke forfølge denne tanken. Derimot kunne det være interessant å opprette en del nye direkte veier i nettverket, slik at det blir mulig å besøke hver by en og bare en gang. Vi oppretter tverrgående forbindelse mellom A — B, B — C, D — E, E — F, F — G og H — I. (Kontrollér at det da blir mulig å foreta en slik rundtur som disponenten ønsker på et stort antall måter.) La de seks nye veiene kunne reises begge retninger, og la veistrekningene være henholdsvis 6, 4, 7, 8, 9 og 5.

Oppgave 49b

Sett opp modellen, kjør den, og vis at minimal verdi = 57 for følgende løsning: VUB = VAF - VBC = XCU = VDE = Åfa = *gi = VHR = VIG = = 1, alle andre variabler = 0.

Men dette resultatet, selv om den minimale verdien er liten og det dermed bare benyttes eksisterende veier, viser seg å være meningsløst! Vi kan tegne opp disponentens reiserute og får følgende:

Figur 35

Hver by besøkes riktignok én og bare én gang, og man forlater ikke en by som man ikke er kommet til. Løsningen er således korrekt utfra modellen. Men modellen er ikke korrekt! Det er nemlig ikke nok å innføre de beskrankninger vi har gjort, det sikrer ikke at turen blir sammenhengende. Vi får en løsning som består av en rekke „underturer” (eng. subtours), her fire i tallet. En korrekt modell av dette problem som kalles Den handels­ reisendes problem (eng. The Travelling Salesman Problem) må derfor ha zv/Zeggsbeskrankninger som utelukker underturer. Det viser seg imidlertid at det ikke er mulig å lage en slik modell innenfor området lineær programmering! Når vi har presentert problemet her, uten å kunne løse det, er det for å vise at et problem som overfladisk ser ut som et enkelt nettverksproblem, kan vise seg å ha skjulte og ubehagelige egenskaper.

Oppgave 49c

Finn den beste reiserute ved å studere nettverket, uten å benytte noen edb-programmer.

Eksempel 50 Prosjektnettverk

Firmaet Slips og Sløyfe skal utvide produksjonen og skal til dette formål bygge ut firmaets nåværende produksjonslokaler. Utbyggingsprosjektet kan inndeles i 20 mindre delprosjekter. Tre av disse, Pl, P2 ogP3 kan igangsettes uavhengig av hver­ andre og utgjør starten på utbyggingsprosjektet. De resterende delprosjekter kan imidlertid ikke igangsettes før ett eller flere andre delprosjekter er fullført. Denne avhengigheten er tildels ganske komplisert og kan lettest beskrives ved hjelp av et nett­ verk:

Figur 36 Grenene i nettverket representerer de enkelte delprosjekter, og tallene i parentes representerer varigheten av det enkelte del-

108

prosjekt i antall uker. Sirklene markerer hvilke delprosjekter som direkte påvirker andre. F. eks. kan ikke P4 igangsettes før Pl er fullført. Pl3 kan ikke igangsettes før P6 ogP7 er full­ ført. P20 kan ikke igangsettes før Pl 6, Pl 7 og P18 er fullført. Firmaet ønsker å få best mulig kontroll over totalprosjektet ved blant annet å få rede på hvilke delprosjekter som er kritiske, dvs. hvilke delprosjekter som ved forsinkelse vil forsinke selve totalprosjektet. Firmaets mål er å fullføre totalprosjektet så hurtig som mulig.

Dette problemet er meget nær beslektet med eksempel 47. Vi skal vise to måter å løse det på:

I. Vi ser lett at totalprosjektet minst må ta 5 + 3 + 7 + 6 = 21 uker, som er summen av prosjekttidene for Pl, P4, Pl2 og Pl9. Problemet består i å finne den lengste (i tid) sammenhengende sekvens av delprosjekter, også kalt totalprosjektets kritiske linje. ★ 1

Vi kan da definere

1 dersom delprosjekt P/ ligger på den kritiske linje 0 dersom delprosjekt P/ ikke ligger på den kritiske linje

Z = total prosjekttid ★ 2

Målfunksjonen blir 20

(max) Z = S CjXj i=i

der Cj representerer beregnet varighet av delprosjekt P/. ★ 3 Beskrankningene har til hensikt å binde delprosjektene på den kritiske linje sammen. Dette har vi imidlertid gjort tidli­ gere i eksempel 47. Prosjektnettverket er laget slik at det er nøyaktig likt det tidligere korteste rute problem, det er bare tolkningen/betydningen av grenene som er forskjellige. Vi har dermed her et lengste rute problem og kan benytte den tidli­ gere modell i eksempel 47 med én forandring (bortsett fra eventuelt bytte av variabelnavn): Vi maksimerer målfunksjonen istedenfor å minimere den!

Kjører vi modellen får vi at 17 ~ X2o ~ 1,

109

dvs. at den kritiske linje består av prosjektene P3 - P9 - Pl7 - P20. Summen av prosjekttidene for disse er 9 + 12 + 8 + 7 = 36 (uker). Oppgave 50a

På tilsvarende måte som tidligere kan vi også betrakte dette pro­ blemet som et Transshipment-problem med maksimering isteden­ for minimering. Gjør dette.

★ 5 Vi ser altså at en forsinkelse i delprosjektene P3, P9, Pl7 og P20 forsinker totalprosjektet og derfor bør styres særlig nøye. Til gjengjeld kan f.eks. P2 forsinkes med inntil fem uker før det får noen betydning. Delprosjektene P14 og Pl9 kan sammenlagt forsinkes tre uker (hvorfor?).

Oppgave 50b

Finn den kritiske linje dersom delprosjekt P9, som har den lengste individuelle prosjekttid lik 12, antas å kunne sløyfes, f.eks. ved å kjøpe ferdig utstyr istedenfor å lage det selv. Vis at total prosjekttid da kan kortes ned med fem uker.

II. En alternativ måte å formulere en modell for dette proble­ met er å ta utgangspunkt i starttidspunktene for delprosjektene. Starttidspunktet for et delprosjekt må minst være så langt ut i tid at det overskrider starttidspunktet pluss prosjekttiden for foregående delprosjekt. ★ 1 Det enkleste er å gjeninnføre bokstavene U, A, . . . , I, R, nå som identifikasjon på sirklene mot før navn på byene. Da kan vi definere

f, = tidligste starttidspunkt for start på de delprosjekter som forutsetter at delprosjektene umiddelbart før i er ferdige. i = A, . . . , I, R, ialt 10 variabler. Det er altså ikke nødvendig med en variabel for hvert delpro­ sjekt. Heller ikke er det nødvendig å definere variabelen , vi forutsetter at totalprosjektet starter på et vilkårlig tids­ punkt 0.

★ 2

Målfunksjonen kan uttrykkes på følgende enkle måte:

(min) Z = tR Vi ønsker altså å gjøre avslutningstidspunktet Z for totalpro­ sjektet så lavt som mulig, og dette er identisk med starttids­ punktet for et eventuelt delprosjekt etter R. ★ 3

110

Vi får en beskrankning for hvert delprosjekt. Eksempler:

Pl: fA>5

fordi intet delprosjekt kan igangsettes etter A før det er gått minst fem uker som er varigheten av Pl.

P4: tD P5:

3 + tA 6+

fordi intet delprosjekt kan igangsettes etter D før det både er gått minst tre uker etter A og minst seks uker etter B.

Oppgave 50c

P19: P20:

tR > 6 + tH fR > 7 + ti

★ 4

Modellen får 10 variabler og 20 > beskrankninger.

Formulér de resterende beskrankninger, kjør modellen og vis at man får minimal verdi = 36, og Variabel ★★★★★★★★

Verdi ***** 14 13 9 23 20

Verdi ***** 21 22 30 29 36

Variabel ********

fF tø

tø

og Beskrankning Overskudd Skyggepris Beskrankning Overskudd Skyggepris 1 2 3 4 5 6 7 8 9 10

9 9 0 6 4 0 0 4 0 4

0 0 1 0 0 0 0 0 1 0

11 12 13 14 15 16 17 18 19 20

5 0 6 3 0 0 0 3 0 0

0 0 0 0 0 0 1 0 0 1

★ 5 Totalprosjektet tar altså i beste fall 36 uker, i overens­ stemmelse med hva vi fant tidligere. Dette kan vi se både ut fra optimal/minimal verdi og ut fra verdien på variabelen rR som er to sider av samme sak. Tidligere fant vi den kritiske linje direkte fra variabelverdiene. I denne modellen ser man ikke dette av variabelverdiene, men av beskrankningenes skyggepriser. Hvis skyggeprisen er forskjellig fra null, må dette bety at en reduk111

.

sjon av delprosjekttiden har en økonomisk verdi. Dette gjelder bare de delprosjekter som ligger på den kritiske linje. Vi ser at skyggeprisene er forskjellig fra null for beskrankningene 3, 9, 17 og 20, dvs. delprosjektene P3, P9, Pl7 og P20, i overensstemmel­ se med tidligere.

Oppgave 5 Od

Hvorfor blir de positive skyggepriser alltid lik 1 ?

Eksempel 51 Tre varelagre, tre kunder (fortsettelse av eksempel 35 og 48)

Hittil har vi forutsatt at det bare er transportkostnadene som har influert valg av transportplan. I praksis er det imidlertid ofte slik at det er kapasitetsbegrensninger på de enkelte ruter, altså at det bare er mulig å sende inntil en viss mengde. Dette kan naturligvis gi optimale løsninger som er dårligere enn de vi får uten slike begrensninger. Dette skyldes at man blir nødt til å benytte ruter med høye enhetskostnader.

Det er prinsipielt enkelt å innføre slike transportbegrensninger i modellen. Vi kan bare utvide den tidligere modell med de be­ grensninger vi ønsker. La oss innføre som begrensning på transportmengde fra i til j. Da får vi et sett av beskrank­ ninger: Xij < Kif

I dette konkrete tilfelle får vi altså ni beskrankninger i tillegg. Vi får imidlertid problemer med å finne løsningen på slike modeller, ikke fordi de representerer noen prinsipielle vanske­ ligheter, men fordi modellene lett blir svært store. Vi kan ikke lenger bruke et TP-program, fordi slike bare kan behandle „rene transport-modeller/problemer. Vi har da bare generell lineær programmering til disposisjon, som vi vet ikke utnytter spesielle forhold/strukturer i modellen. Det finnes på større datamaskiner spesielle programmer/algoritmer for beregninger av denne type. Det vil føre for langt å gå inn på nettverkspro­ blemer og deres løsningsmetoder i sin fulle bredde, og vi vil derfor bare henvise interesserte til annen litteratur. For at vi skal få litt mer kjennskap til problemtypen, skal vi likevel kjøre noen varianter. Vi har ni variabler, ni < beskrankninger og seks likheter. Optimalløsningen uten kapa­ sitetsbegrensninger var MINIMAL VERDI = 850

112

VARIABEL ★★★★★★★★★★

VERDI ★★★★★★

XAL XBN XCL

12 10 1

VARIABEL

VERDI

★★★★★★★★★★

★★★★★★

XCM XCN

5 5

Hvis vi nå innfører kapasitetsbegrensninger med alle ruter, vil vi få en ny og dårligere løsning:

= 11 for

MINIMAL VERDI = 860

VARIABEL ★★★★★★★★★★

VERDI ★★★★★★

VARIABEL ★★★★★★★★★★

VERDI ★★★★★★

XAL XAN XBN

11 1 10

XCL XCM XCN

2 5 4

Transportruten A — N blir nå benyttet. Dermed kan ikke N få så mye fra C som før, som må sende det overskytende til L, som dermed får erstattet den manglende enhet som ikke kunne leveres fra A.

Oppgave 51a

Sett alle Ky = 10, deretter 9, 8 osv. og studér hvordan den optimale transportplan endrer seg og hvordan kostnadene øker. Hva er den laveste verdi av Kif som kan benyttes?

Oppgave 51b

Legg på kapasitetsbeskrankninger der ikke alle Kif har samme verdi og drøft løsningen.

Eksempel 52 To varer (fortsettelse av eksempel 35,48 og 51)

Vi utvider nå problemstillingen til å omfatte to forskjellige varer. Vi kaller den første, som vi er kjent med, for vare X, og den nye for vare Y. Både A, B og C har vare Y på lager, henholdsvis 4, 4 og 5 enheter. Behovene for vare Y hos L, M ogN er henholdsvis 2, 8 og 3 enheter. Vi antar at enhets­ kostnadene ved transport av vare Y er den samme som for vare X.

Hvis vi ikke hadde kapasitetsbegrensninger, kunne vi naturlig­ vis løse transportproblemet for vare Y uavhengig av vare X. Hvis vi lager en totalmodell for dette problemet, og setter kapasitetsgrensene tilstrekkelig høyt til at de ikke er bindende, vil denne gi transportplaner for X og Y med samme verdier som om vi kjørte to mindre modeller. En totalmodell vil ha 9 * 2 = 18 variabler, 2 6 * = 12 likheter, samt 9 < beskrank­ ninger. De siste vil ha en litt annen form enn tidligere, nemlig Xtj + Yif < Kif

Med alle de, får vi

o. Lineær programmering

valgt tilstrekkelig høyt til at de ikke blir binden­

MINIMAL VERDI = 1100 VARIABEL

VERDI

VARIABEL

VERDI

★★★★★★★★★★

★★★★★★

★★★★★★★★★★

★★★★★★

XAL XBN XCL XCM XCN

12 10 1 5 5

YAL YAN YBM YBN YCM

2 2 3 1 5

Vi kjenner igjen X-verdiene fra tidligere, og vi kan gjeme kontrollere Y-verdiene ved å kjøre Y-modellen. Bare to av de ni mulige transportrutene blir ubenyttet, B - L og A - M. Hvis vi nå innfører kapasitetsbegrensninger lik 10 på alle ruter, ser vi at rutene A - L og B - N er overbelastet. Oppgave 52a

Foreta de nødvendige endringene i modellen og vis at B — L og A — M fremdeles blir ubenyttet, men at transportkost­ nadene går opp til 1160.

Oppgave 52b

Hvor lavt kan den felles kapasitetsbegrensning settes før det ikke lenger er mulig å finne noen transportplan?

Eksempel 53 Tre lagre, fem kunder

Tre lagre A, B, C har til disposisjon henholdsvis 5, 10 og 10 enheter av en vare. Dette dekker behovet hos fem kunder a, b, c, d, e, med henholdsvis 3, 3, 10, 5 og 4 enheter. Enhetskost­ nadene for transport er gitt som følger:

A B C a b c d e

A

B

C

a

0 2 3 5 7 10 5 3

3 0 1 8 6 9 12 4

1 2 0 10 9 8 10 15

5 8 10 0 1 2 2 4

bede

7 6 9 2 0 4 3 1

10 9 8 1 3 0 1 2

5 12 10 3 4 1 0 3

3 4 15 4 2 2 3 0

Oppgave 53a

Finn den optimale transportplan — som et vanlig transport-problem — som et Transshipment-problem Sammenlign løsningene og klargjør årsakene til forskjellen.

Oppgave 53b

Anta at A har 10 enheter til disposisjon i stedet for 5. Besvar spørsmålene under 53a.

Oppgave 53c

Anta at a har et behov på 8 enheter i stedet for 3. Besvar spørsmålene under 53a.

114

I dette kapitlet har vi vist eksempler på problemstillinger som er beskrevet ved hjelp av nettverk. Det har vært vist at modell­ enes størrelse i antall variabler og beskrankninger blir betydelig selv for små nettverk, og til tross for at LP-formulering av denne type problemer er relativt enkelt og gir god innsikt i nett­ verksproblemenes struktur, er de løsningsmetoder/edb-program ­ mer som er utviklet for LP-modeller mindre hensiktsmessige. Kapitlet motiverer derfor til å studere nettverksproblemer utfra andre synsvinkler. Vi kan nevne stikkord som nettverks­ teori og dynamisk programmering. Dette ligger imidlertid uten­ for denne bokens ramme.

Diverse planleggingsproblemer Dette kapitlet knytter sammen ulike momenter fra tidligere kapitler og innfører planleggingsproblemer som er større og mer realistiske enn tidligere. Sammenhengen mellom produk­ sjon, lagring og salg i samme periode og fra periode til periode blir drøftet, og vi viser at modellene kan utformes på forskjel­ lige måter. Vi introduserer også situasjoner der noen av pro­ duktene både kan benyttes som komponenter i egen produk­ sjon, og selges direkte. Produksjonsplanleggingen gis en ekstra dimensjon ved at det er mulig å produsere produktene på forskjellige steder. Dermed knyttes distribusjonsplanleggingen til. Tilslutt viser vi hvordan investeringsanalysen også kan behandles ved hjelp av LP-modeller. Eksempel 54 Produksjon/ lagring/salg Planlegging for tre perioder

En fabrikk produserer to forskjellige produkter. Produktene bearbeides i to maskiner A og B. Fabrikken ønsker å bestemme et optimalt produksjonsprogram for tre perioder. I de tre periodene er følgende antall produksjonstimer tilgjengelig på de to maskinene:

Maskin A Maskin B

Periode 12 450 340 320 400

3 450 380

Antall timer som kreves for å fremstille en enhet av hvert av de to produktene: Produkt 1 Produkt 2

Maskin A 3 1,5

Maskin B 1 3

115

Prognosene for fortjenesten på de to produktene varierer fra periode til periode. Fortjenesten før lagringskostnader blir trukket fra, er:

Produkt 1 Produkt 2

Periode 1 2 3,00 3,75 2,25 3,00

3 6,50 4,00

Man antar at alt som kan produseres kan selges i samme eller senere perioder. Det er mulig å lagre produktene fra periode til periode. Lagringskostnaden per enhet er:

Produkt 1 Produkt 2

Lagring fra Periode 1 til 2 1,00 1,00

Lagring fra Periode 2 til 3 2,00 0,50

Fabrikken har imidlertid begrenset lagringsplass, tilsammen 100 m2. En enhet av produkt 1 krever 5 m2 lagringsplass, det tilsvarende tall for produkt 2 er 3 m2. Det er ikke noe på lager ved begynnelsen av periode 1.

Løsning

★ 1 Situasjonen er her slik at problemet refererer både til produksjon, lagring og salg. Det kan derfor synes naturlig at man definerer følgende sett av variabler:

- produksjon av produkt i i periode j (i = 1, 2 j = 1, 2, 3) Yij = salg av produkt i i periode j

(z = 1, 2 j = 1, 2, 3)

Zijk = lager av produkt i fra periode j til periode k (z = l,2 jk= 12,23) Z = total fortjeneste for de tre periodene.

Merk følgende: — Lagerproblematikken er forenklet dithen at lagringskostnadene er knyttet til et tidspunkt, nemlig overgangen fra en periode til neste. I praksis vil kostnadene blant annet være knyttet til kapitalbinding og dermed påløpe kontinuerlig. Den gitte problemformulering er derfor en tilnærmelse. Problemet er formulert dynamisk i den forstand at vi studerer sammen­ hengen mellom handlingsvariabler i forskjellige perioder. Innenfor den enkelte periode sees imidlertid problemene statisk, det har f.eks. ingen betydning når i perioden produksjon og salg foregår. — Planleggingshorisonten, dvs. det antall perioder fremover som er med i analysen, er satt lik tre. Dette innebærer at vi ikke tar i betraktning eventuell nytte ved å lagre varer utover

116

periode 3. Det er derfor ikke nødvendig å definere variablene Z134 og Z234, slik lagring vil bare medføre kostnader innenfor den ramme som er valgt. Salget ville jo skje i periode 4 og senere, og dette har vi sett bort fra. Vi skal imidlertid være klar over at denne tilsynelatende grove utelatelse ikke er så farlig, fordi den form for problem­ stilling vi har skissert hører inn under begrepet rullerende plan­ legging, som nevnt tidligere. Det er egentlig bare resultatene fra periode 1 som blir satt ut i livet direkte. En periode senere vil en ny analyse utføres, med reviderte tall for periodene 2 og 3, og med en periode 4 hektet på. Tilbake til variabeldefmisjonene: Dette sett på 6 + 6 + 4 = 16 variabler er ikke særlig godt som utgangspunkt fordi det er unød­ vendig stort. Vi søker nemlig primært et sett av uavhengige hand­ lingsvariabler, hvilket ikke er tilfelle her. Dersom f.eks. produk­ sjon og lager er gitt, følger salg automatisk. Vi kan faktisk velge to av de tre størrelsene produksjon, salg og lager for en gitt periode og den tredje følger automatisk. Imidlertid vil vi likevel gjennomføre analysen først med disse 16 variabler for å illustrere avhengigheten mellom variablene. ★ 2 Vi får en målfunksjon som består av positive ledd, for­ tjenesten ved salg, og negative ledd, lagringskostnadene:

(max) Z = 3,00yn + 3,75r12 + 6,50r13 + 2,25721 + 3,oor22 + 4,ooy23 — l,00Z112 —2,00Z123 — l,00Z212 — 0,50Z223 Produksjonsvariablene Xi;- inngår altså ikke i målfunksjonen.

★ 3

Tilgjengelig tid på maskinene:

3X„ + 1,5J¥21 3V12 + l,5Jf22

Xn +

3%21 *12 +

3X22

C 450 S 340 * 13 + 1,5X23«C 450 3 S 320 ; 4oo *13 + 3X23< 380

(1) (2) (3) (4) (5) (6)

Lagringsplass:

5Z112+3Z212

3Z^i23

istedenfor en maksimering av den opprinnelige funksjon. Dette gjør vi for å kunne greie oss med én metode for beregningene. Hvis ikke måtte vi ha hatt ett program for maksimeringsproblemer og ett for minimeringsproblemer. Programmet tester da koeffisientene i Z-raden og plukker ut den kolonne som har den minste, dvs. den mest negative fortjeneste/kostnad, altså her —6000. Vi setter en ring rundt denne kolonnen og kaller den Å?kolonnen. Deretter regner programmet ut, for hver rad (unntatt Z-raden naturligvis), forholdet mellom 2?’en og tallet i den innringede kolonne. Vi får, som forklart tidligere, forholdene qy, og p. Det minste forholdet er 7 som fremkommer for 53-raden. Vi kaller denne for r-raden og ringer den inn: (Se tabellen ovenfor.) Variabelen i ^-kolonnen skal da erstatte variabelen i r-raden. Etter at de nødvendige regneoperasjoner er foretatt, skal vi kunne lese ut variabelverdiene i den nye løsning, samt målfunk­ sjonens verdi fra et nytt tallskjema. Hvilke regneregler gjelder? Vi har i det opprinnelige skjemaet skrevet ligningssystemet på en form hvor én variabel fremtrer separat i hver ligning, og bare der. I det første skjemaet er og X2 forutsatt lik 0, og vi kan derfor lese av verdiene på , S2 og S3 direkte fra 2?kolonnen. I det neste tallskjemaet er det nå Sj, S2 og X2 som er basisvariabler og som skal kunne avleses direkte. Imidlertid er ikke ligningssettet på en slik form at dette lenger lar seg gjøre, og vi må derfor foreta noen enkle omforminger først: For r-raden kan vi umiddelbart finne verdien på den nye basisvariabelen ved å dividere ligningen med det dobbelte innringede element. Hele ligningen skaleres altså. For de andre radene er regneoperasjonene noe mer om­ fattende. Vi må fjerne alle koeffisienter som er knyttet til den nye basisvariabelen, fordi denne må forekomme bare i r-raden. For å gjøre dette kan vi trekke fra r-raden multiplisert med en passe konstant, og denne konstanten vil være forholdet mellom de respektive tall i Å>kolonnen og den felles nevner representert ved det dobbelt innringede element.

Presisering av regnereglene

10. Lineær programmering

For å få oversikt over regnereglene innfører vi symboler: La oss kalle et element/tall i rad i og kolonne j fory/;-, Siden vi lager et nytt skjema/ligningssett ut fra et gammelt, må vi angi hvilket skjema variablene refererer seg til. Vi sier at — fij refererer seg til nytt skjema (uttales „y hatt”) ytj refererer seg til gammelt skjema

145

Vi lar Æ-kolonnen ha kolonnenummer 0, slik at den kan be­ handles likt med de andre kolonnene. Regnereglene blir da som følger:

|

'

Trinn 1:

Undersøk om noen av de relative kostnader/fortjenester er nega­ tive. (Husk at disse er 0 for alle basisvariabler, det er derfor vi bruker uttrykket „relative” for å angi at det er snakk om verdi i forhold til den løsningen vi allerede har.) Hvis ingen er negative, har vi funnet den optimale løsning på vårt problem. Hvis en eller flere er negative: Gå til trinn 2. Trinn 2:

Sett en ring rundt den kolonne (j = k) som har mest negativ relativ vi kostnad. Variabelen i denne kolonnen går inn i basis. Gå til trinn 3. .£ Trinn 3: Beregnfor i = 1, ... ,n for alleyik > 0. Sett en ring rundt den raden (z = r) der dette forholdet er minst. Variabelen i denne raden går ut av basis. Gå til trinn 4. Hvis alle yik < 0, er det ingen endelig løsning på problemet.

Trinn 4: Beregn nytt skjema således: For rad r: y ■ =

j = 0,1, . . . ,m y rk (divisjon med den dobbelte innringede koeffisient). For alle andre rader: — Bestem først = y-^~ Trk - Daerj>z>. _ t.yr.

z = 1+ 1

i* r

j=

Gå tilbake til trinn 1. Simplexmetoden

Metoden som er beskrevet i trinnene ovenfor kalles altså Simplex-metoden. Vårt neste tallskjema ser slik ut, etter å ha benyttet reglene oven­ for, dvs. utført én iterasjon: ETTER 1 ITERASJON

B

S3

S1

195

20

0

1

0

-15

S2

60

10

0

0

1

-20

X2

7

0

1

0

0

1

M2000 -5000

0

0

0 6000

Z

146

X2 S1 S2

X1

For å illustrere beregningene kan vi ta y15 = y15 — ti_y3s (siden r = 3), der - — (siden k = 2). Vi får 71 = ^- = 15, dvs. yl5 =0- 15 • 1 =-15. Eller: j>20 = 72o - ^73o> der r2 = ~- Vi får t2 = = 20 og 720 = 200 — 20 • 7 = 60. Kontrollér at dette stemmer, og kontrollér også resten av tallene i skjemaet. Deretter gjentas alle beregningene (trinn 1 — 4), på det nye tallskjemaet:X} vil erstatte S2 (hvorfor?), slik at k - 1 og r = 2. Vi får to iterasjoner til, som følger: ETTER 3 ITERASJONER

ETTER 2 ITERASJONER B

X1 X2 S1

S2 -2

S1

75

0

0

1

X1

6

1

0

0

0.1

X2

7

0

1

0

72000

0

0

Z

B

S3

X1 X2

S1

S2

S3

25

S3

3

0

0

0.04

-0.08

1

-2

X1

12

1

0

0.08

-0.06

0

0

1

X2

4

0

1

-0.04

0.08

0

0 500

-4000

84000

0

0 160

z

180

0

Kontrollér selv at tallene i skjemaene stemmer.

Etter tre iterasjoner ser vi at alle relative fortjenester er blitt positive for de variabler som ikke er i basis. Det er således ingen mulighet for ytterligere forbedringer, og vi konstaterer at dette skjemaet representerer den optimale løsning. Hvorfor utføres beregningene i trinn 3 bare i de tilfeller der yik > 0? Fordi dersom yik < 0, så gir ikke ligning i noen restriksjon på verdien av den nye variabel. Dette kan vi lett illustrere: I talleksemplet foran hadde vi som første ligning i startbasis følgende: 300 = 20Vj + 15V2 +51!

Siden X2 skulle bli ny basisvariabel, uttrykte vi den gamle basisvariabelen Sj ved hjelp av X2:

S1! = 300 - 20%! - 15%2

og siden Xr har, og foreløpig vil fortsette å ha, verdien 0, får vi S1! =300 - 15X2 Når X2 øker, avtar Si. Maksimal verdi på X2 må bli yy = 20, for da får Sj sin lavest mulige verdi som er 0. Dermed blir 20 en øvre grense, et tak på X2 . Hver ny ligning lager et nytt tak, og det vil være det laveste som blir utslagsgivende. Her får vi at %2s maksimale verdi = minimum (2æ, ?-) = minimum (20, 10, 7) = 7.

147

Anta imidlertid at første ligning ovenfor var

300 = 20^ - 15V2 +51! Altså en negativ koeffisient foran den nye basisvariabelen. Da får vi

Si =300 + 15X2 Det innebærer at når X2 øker, øker også Sx \ X2 kan bli uendelig stor, det samme blir i så fall også Sj. Det blir altså ingen øvre grense på X2 ut fra denne ligningen. Dette er årsaken til at vi ikke behøver å behandle ligninger med negativ yik. (Dersom yik = 0, er det ingen kobling mellom den gamle og den nye basisvariabelen, den gamle endrer ikke verdi når den nye øker, og heller ikke da blir det noe tak.) Vi kan nå betrakte påstanden i trinn 3: Dersom alle yik < 0 så er det ingen endelig løsning på modellen. Som en meget enkel illustrasjon kan vi benytte Dreiebenk men ,,glemme” avdelingsbeskrankningene, og dermed bare ha X2 < 7 SOOOVj + 6000V2 = Z (max) Det er klart at her kan XY bli uendelig stor og gi uendelig salgsinntekt. Løsningsrommet er åpent og ser slik ut:

Figur 39 Benytter vi Simplex-metoden på denne modellen får vi STARTBASIS

B S1 7

Z

ETTER 1 ITERASJON

S1

X2

X1

0

11

0 -5000 -6000

0

B X2 Z

X2

X1

7

0

42000 -5000

1

S1 1

0 6000

Vi ser at i det siste Simplex-skjemaet (etter 1 iterasjon) blir Æ-kolonnen som før lik X{ -kolonnen. Imidlertid er =0, og siden vi bare har en eneste ligning, er alle yik < 0. Vi har nå sett hvordan Simplex-metoden fungerer så lenge alle beskrankningene er av typen