Operasjonsanalyse for økonomi og samfunnsfag 8251838509 [PDF]

Zitiervorschau

0\-oc\a'-i

Modelloppførsel/ modellkonsekvens Forslag til løsning av problem

Denne figuren er egentlig generelt gyldig ut fra de innledende betraktninger rundt begrepet «vir­ keligheten». Innenfor våre fagområder bruker vi imidlertid figuren på en mer formell måte. Veien fra «problem» til «forslag til løsning av problem» har et solid fundament i vitenskapelig metode og modellbygging.

1.1.2 Modellteknikk Alt etter formålet kan modeller konstrueres på forskjellige måter; en lang rad modellverktøy står til disposisjon. En vanlig, hierarkisk inndeling av modeller ifølge modellteknikk er denne:

Verbal modell

Matematisk modell

Skjematisk modell

En kort forklaring til de forskjellige modelltypene:

•

ikoniske modeller; «avbildninger» som «ser ut som» det som modelleres (eks. statue)

•

analoge modeller; modeller som benytter egenskaper hos en lett tilgjengelig del av virkeligheten til å be­ skrive og bearbeide en mer vanskelig tilgjengelig del av virkeligheten (eks. elveløp som analogi til blodårer)

•

symbolske modeller; modeller som består av matematiske, logiske, grafiske og språklige symboler

14

MODELLER I ØKONOMI OG SAMFUNNSFAG

Vi kan igjen inndele symbolske modeller i:

•

skjematiske modeller; modeller som hovedsakelig bygges opp av grafiske symboler som bokser, piler etc. (eks. flytdiagram innenfor dataprogrammering, prosjektnettverk, organisasjonskart)

•

verbale modeller; også kalt begrepsmodeller; modeller som hovedsakelig uttrykkes gjennom ord (eks. Teori Y - en modell for individets adferd i en organisasjon)

•

matematiske modeller; også kalt formalmodeller; modeller som hovedsakelig uttrykkes gjennom funksjoner, ulikheter og ligningssystemer (eks. kostnadsfunksjon)

Det er først og fremst matematiske modeller innenfor økonomi og samfunnsfag som behandles i denne boka. Vi er særlig opptatt av modeller der variablene kan kvantifiseres, og der vi søker tallsvar. Økonomiske variabler som pris, kostnad etc. vil ut fra sin natur være kvantitative. Mo­ deller der alle attributter er beskrevet ved kvantitative variabler, kalles kvantitative modeller, i motsetning til kvalitative modeller. Vi bruker termene matematiske modeller og kvantitative modeller om hverandre. Modeller kan ikke alltid klassifiseres på en enkel måte, slik som figuren ovenfor antyder. Simuleringsmodeller, som vi skal komme tilbake til senere ved flere anled­ ninger, er en modellteknikk i grenselandet mellom analoge, matematiske og skjematiske model­ ler. Et eksempel på en analog/verbal modell har vi i Stafford Beers bok «Brain of the Firm» (1972), der menneskets hjerne og nervenettverk brukes som analogi til bedriftens ledelse og styringssystemer. Det finnes andre klassifikasjonskriterier for modeller som kan bidra til å gi oss oversikt over mangfoldehj^podellbegrepet:

« •

deterministiske modeller; modeller der variablenes virkning på hverandre er sikker, eller det antas at det aktuelle problem i liten grad inneholder usikkerhet, og at denne derfor ikke behøver å tas med i modellen,

i kontrast til

•

stokastiske modeller; modeller der variablenes virkning på hverandre er usikker og beskrevet ved sannsynlighetsfordelinger, og det antas at usikkerhet er så vidt sentralt i problemet at denne må tas med i modellen.

•

statiske modeller; «tidløse» modeller, ofte knyttet til beskrivelse av likevektsituasjoner, og hvor forbindel­ ser mellom variabelverdier på forskjellige tidspunkter ikke inngår,

i kontrast til

•

dynamiske modeller; modeller som beskriver tilstandsendringer over tid, og hvor det er funksjonelle sam­ menhenger mellom variabler på forskjellige tidspunkter.

HVA ER EN MODELL?

•

15

konsekvensmodeller, også kalt deskriptive modeller; modeller som tar sikte på å kartlegge hvordan virkeligheten oppfører seg, og som be­ regner den konkrete effekt av ulike handlingsalternativ,

i kontrast til •

preferansemodeller; også kalt normative modeller; modeller som tar sikte på å gi et underlag for beslutninger, og som beregner beslutningstakerens oppfatning av verdien/nytten av ulike, tenkte situasjoner.

Det er av og til slik at modelltypen tar navn etter løsningsteknikken. Vi benytter definisjonen:

•

analytiske modeller; matematiske modeller som kan løses ved hjelp av analytiske teknikker

Med analytiske teknikker mener vi vanlige matematiske operasjoner som addisjon, subtraksjon, multiplikasjon og divisjon, samt funksjonslære med derivasjon og integrasjon. Vi anvender tek­ nikken til å konstruere matematiske uttrykk som kan bearbeides til en hendig form mht. de vari­ abler vi er interessert i. Vi kan gjeme definere:

•

analytiske modeller; modeller der de enkelte variabler kan uttrykkes eksplisitt gjennom andre variabler og parametre (data), slik at numerisk beregning skjer ved enkel tallinnsetting i «formler»

Denne teknikken er meget slagkraftig. Derfor søker vi å bygge våre modeller slik at matematik­ ken kommer til full nytte, når det er mulig. Det å gjøre modeller analytiske er derfor ofte et mål som modellbyggeren søker å nå, slike modeller gir meget stor informasjon med et minimum av verktøy. Imidlertid lar dette seg ikke alltid gjøre, virkeligheten er ofte så komplisert at de mate­ matiske verktøy ikke strekker til. Det er nødvendig å utvikle modeller/teknikker som «leter etter» løsninger heller enn å «utlede» dem. Vi må ta i bruk det vi kaller:

•

numeriske modeller; matematiske modeller der de enkelte variabler ikke kan uttrykkes eksplisitt, men må beregnes numerisk, gjeme gjennom flere trinn (iterative teknikker), ofte med en viss unøyaktighet

Dersom numeriske modeller far stor kompleksitet, vil vi kalle dem simuleringsmodeller. Dette er et så interessant og mangfoldig tema at vi skal behandle det i et eget avsnitt:

16

MODELLER I ØKONOMI OG SAMFUNNSFAG

1.1.3 Innledning til simuleringsmetodikk Hva menes egentlig med simulering? Alle kjenner ordet «simulering» og diverse tilknyttede former som «simulator», «simulant», «simulere», men det synes ofte å dreie seg om helt forskjel­ lige meningsinnhold. Vi kjenner begrepene i anvendelser som •

«han simulerte syk», dvs. han etterlignet en syk persons adferd med det formål selv å bli oppfattet som syk,

•

«hun gjennomførte et treningsprogram i flysimulatoren», dvs. hun etterlignet en virkelig flysituasjon i et slags laboratorium,

•

«insektet simulerte et blad», dvs. det etterlignet et blad ved at huden kjemisk antok bladets grønne farge.

Uttrykk som «etterligne» eller «late som om» vil lett kunne anvendes istedenfor «simulere». Hva betyr det da å «simulere» i forbindelse med «våre» fag, økonomi og samfunnsfag?

Norsk Dataordbok definerer simulering slik: Representasjon av visse egenskaper i et reellt eller abstrakt system ved hjelp av egenskaper ved et annet system.

Begrepet «system» blir brukt løselig i mange sammenhenger, vi har selv anvendt det uten presi­ sjon tidligere i boken. Norsk Dataordbok definerer system slik:

1. Samling av komponenter som hører og virker sammen slik at de utgjør en organisert helhet. 2. Samling av mennesker og metoder som er organisert for å utøve et sett med spesifiserte funksjoner.

Med slike vide definisjoner (som likevel synes begrenset til reelle systemer) er det ikke noe rart at begrepet simulering antar mange betydninger, ikke bare i vanlig dagligtale, men også innenfor vitenskapelige områder. Mangfoldet i de problemstillinger som kan utsettes for simulering, gjør at det er umulig å bli «ekspert» på området; det finnes flere områder av simulering som har liten eller ingen innbyrdes forbindelse hva angår den detaljerte utforming av simuleringsmetodikken. Tar vi utgangspunkt i modellbegrepet og benytter følgende definisjon:

En modell er en forenklet beskrivelse av virkeligheten.

HVA ER EN MODELL?

17

vil vi kunne si at

En simuleringsmodell er en forenklet beskrivelse av virkeligheten vanligvis med det spesielle formål å etterligne virkelighetens oppførsel over tid.

Den del av virkeligheten som interesserer oss, rammer vi inn og kaller et system. Så konstruerer vi en systemmodell som vi kan eksperimentere med, til erstatning for det virkelige system. Dette gjør vi fordi •

det kan være umulig, for farlig eller for kostbart å eksperimentere med det virkelige system,

•

det virkelige system eksisterer ikke ennå; det befinner seg bare på planleggingsstadiet.

En simuleringsmodell vil alltid «ligne mer» på det virkelige system, ha en mer praktisk utforming enn de analytiske modellene som moderne økonomiske fag er så fulle av! Vi kan definere følgende:

En simulering er en anvendelse av en simuleringsmodell, et eksperiment med en forenklet versjon av et virkelig system, en etterligning av en tenkt fremtidig systemoppførsel.

Vi kan gjeme si at en vindtunnel, et bølgebasseng, en flysimulator eller et krigsspill er eksempler på simuleringsverktøy med utpreget eksperimentell orientering mot problemløsning, altså egent­ lig analoge modeller. Det er både vanskelig, kostbart og tidkrevende å konstruere simuleringsmodeller på denne måten, i form av laboratorier. Det samme gjelder selve simuleringene. Likevel lar det seg gjøre å sette en miniatyrisert fly-prototyp inn i en vindtunnel for å teste det virkelige flyets aerodynamis­ ke egenskaper. Det er imidlertid ikke så enkelt å forestille seg hvordan tilsvarende konstruksjoner skulle se ut dersom man ønsket å simulere produksjon, kapasitetsutnyttelse, lager, likviditet etc. i en bedrift. Vi må derfor studere området simulering i perspektiv av moderne informasjonsteknologi — hvordan kan vi lage en databasert simuleringsmodell? Kan vi simulere på PC’en? Svaret erja, med eksperimentaspektet klart for oss kan vi konstruere databaserte simulerings­ modeller av forskjellige systemer.

Med enkle parameterendringer kan vi etterligne eller konsekvensberegne forskjellige systemaltemativ raskt og effektivt ved simulering. En databasert simuleringsmodell kaller vi et simu­ leringsprogram. Et slikt program blir å karakterisere som en symbolsk modell. Vi har altså en symbolsk modellrepresentasjon i et språk som datamaskiner forstår. Når vi kjører dette program­ met, foretar vi altså en data-simulering. Definisjonen «simulering lik etterligning» er vid og upresis. Bruk av begrepet simulering i faglig forstand avspeiler dette. Det er et stort antall anvendelsesområder som har lite til felles med hverandre bortsett fra at «noe etterlignes». Dette gjelder også mengden av dataverktøy innenfor området simulering. Behovet er derfor stort for å klassifisere mangfoldet av simuleringsproblemer og -teknikker. En grov klassifikasjon er:

18

MODELLER I ØKONOMI OG SAMFUNNSFAG

•

Deterministisk simuleringsmetodikk, der man greier seg uten noe statistisk begrepsapparat.

•

Stokastisk simuleringsmetodikk, der et statistisk begrepsapparat er helt sentralt.

Deterministisk simuleringsmetodikk er egentlig ikke noe annet enn numerisk beregning av systemvariabler, vanligvis over tid. Fordi sammenhengen mellom variablene kan være svært komp­ lisert, vil alternative matematiske analyseverktøy ofte ikke strekke til. Det kan være umulig å løse de ligningene som beskriver systemet, og simulering må erstatte en eksakt analytisk beregning. Med utgangspunkt i variabelverdiene (systemets tilstand) på tidspunkt t beregner vi variabelverdiene på tidspunkt t + Ar, der Ar velges så liten at vi far den nøyaktighet vi har behov for i det problem vi behandler. Slike simuleringer kan være så enkle at de kan utføres for hånd, eller ved hjelp av ulike ITverktøy som regneark eller spesialprogrammer som QM eller Lindo.

Generelt er imidlertid deterministisk simuleringsmetodikk nyttig for å gi numerisk løsning av store systemer - med mange variabler og kompliserte årsakssammenhenger, der det er svært vanskelig eller umulig å ha noen intuitiv mening om systemets oppførsel. Et eget fagområde, Systemdynamikk, beskriver slike systemer og anviser løsningsmetodikk ved hjelp av simulering. En systemdynamisk modell kan defineres som «et komplisert system beskrevet av et sett (ikke-lineære) differensialligninger over tid». Vi skal studere dette området i detalj senere og vise sammenhenger og forskjeller mellom matematisk analyse på den ene side og simulering på den annen side. Store systemer krever spesielle IT-verktøy for å lette modellkonstruksjonen samt gjøre selve simuleringene hurtige og oversiktlige. Et systemdynamisk program kan nå oppfattes som en simulenngsmodell (i enklere tilfeller er det riktigere å bruke begrepet numerisk modell) av en matematisk modell av et komplisert virke­ lig system. Simuleringsmodellen må til for å finne tallsvar for den matematiske modellen. Om du synes dette høres innviklet ut, vil det forhåpentlig være oppklarende å lese kapitlet om Determi­ nistisk Simuleringsmetodikk. Stokastisk simuleringsmetodikk er et mer sammensatt emne. Ordet «stokastisk» knytter seg først og fremst til selve simuleringsmetodikken; det anvendes statistiske teknikker i selve løsningsprosessen. Det er imidlertid to hovedområder som skiller seg fundamentalt ut fra hverandre:

•

Monte Carlo simulering; simulering enten av problemstillinger som er av rent deterministisk art, eller av statis­ tiske problemstillinger som er så vidt kompliserte at det matematiske apparat ikke strek­ ker til. Tiden inngår ofte ikke i det hele tatt, eller på en forholdsvis enkel måte. Monte Carlo simulering anvender tilfeldighetsbegrepene fra statistikken til å finne tilnærmede løsninger på veldefinerte matematisk/statistiske problemer som har eksakte løsninger vi ikke greier å finne!

•

Simulering av systemer med diskrete begivenheter; ofte kø-/trafikksystemer av stor kompleksitet, der tilfeldige variasjoner i systemets pro­ sesser gjør systemets oppførsel vanskelig å forutsi (ref. køteori). For å etterligne et slikt system må simuleringsmodellen være i stand til å reprodusere eller konstruere samme form for tilfeldighet som i det virkelige system.

19

HVA ER EN MODELL?

Det første området må sies å være anvendelse av numeriske modeller, mens det andre området representerer de egentlige simuleringsmodeller. Språkbruken er imidlertid ikke entydig blant fagfolk. Begge disse simuleringsmetodikker forutsetter IT-verktøy som kan produsere «tilfeldig­ heter» etter gitte sannsynlighetsfordelinger. Mange generelle programmeringsspråk har rutiner/ funksjoner som gjør dette. Simulering av systemer med diskrete begivenheter med stokastisk avstand har imidlertid behov for et større begrepsapparat for å modellere enkeltobjekter, køer, tidsakse og hendelser. Slike systemer er nettopp karakterisert ved at enkelthendelser oppstår på uforutsigbare tidspunkter; vi har altså ikke lenger noen fast Ar mellom beregningene. Det er nødvendig med egne, spesielle simuleringsspråk for simulering av slike systemer.

1.1.4 Modellbygging Utviklingen av modellteknikk har solid forankring i naturvitenskapelig tradisjon. Den «teknis­ ke» del av modellbyggingen, dvs. konstruksjon av matematiske funksjoner, ligninger, algorit­ mer, dataverktøy, har likhet med ingeniørens arbeid med sitt byggverk. Man kunne fristes til å tro at å lære modellbygging bare er å lære å anvende et sett av sofistikerte redskaper. Dette er ikke riktig. Det skal betydelig mer til for å lage en god modell, og den tunge ballast av kvantitativ vitenskap må oppveies av kvalitative elementer som gjør en god modellbygger til noe av en kunstner. Følgende figur gir fire kompletterende innfallsvinkler til modellbygging:

Overordnede holdninger Mål, ønsker, vurderinger, fornuft

> Modellbygging
20%, = 300 => %! = 15 X, = 0 => 15%2 = 300 => X2 = 20

Maksimalt kan det altså produseres hhv. 15 og 20 stk. av de to typene.

32

LINEÆR PROGRAMMERING

En rett linje er som kjent, entydig beskrevet hvis vi kjenner to punkter på den. Vi har nettopp funnet to punkter, (15, 0)og(0, 20), og disse avmerkes med stjerner (*) i figur 2a. Deretter trekkes en rett linje mellom dem. Alle produksjonsprogrammer på venstre side, nedsiden av linjen, bru­ ker mindre enn maksimalt tilgjengelig tid og er derfor mulige. De på høyre side, oversiden av linjen, krever mer tid enn MOCO har til disposisjon, og er derfor ikke mulige. En tilsvarende beregning kan vi nå foreta for avdeling B, se figur 2b. Punktene (20, 0) og (0, 10) ligger på den linjen som deler produksjonsprogrammene i to deler, mulige og ikke mulige, i forhold til tilgjengelig tid i avdeling B (kontroller dette). Det totale mulighetsområde, når vi tenker på at produksjonsprogrammene må være mulige i hegge avdelinger, blir da det som er skravert i figur 3. (Pilene viser hvilke sider av de forskjellige linjer et mulig produksjonsprogram må befinne seg på.)

Det beste produksjonsprogram velges altså fra punkter i det skraverte området i figur 3. La oss se på fortjenesten Z = 5000Åj + 6000ÅS

Figur 3

33

LP-MODELLERING I DET SMA

Siden vi ikke vet hvor stor Z kan komme til å bli, antar vi en tilfeldig verdi, f.eks. kr 24 000. Hvilke produksjonsprogrammer vil kunne gi en fortjeneste på kr 24 000? Svaret er gitt ved de kombinasjoner av Aj og %2 som passer i ligningen L, i figur 4 (igjen en rett linje), og som ser ut som følger:

Lp 24 000 = 5000JV] + 6000Aj

„

...

«

1 1-

iz

24 000

.

„

i ,.

„

24 000

. o

Setter vi Aj1 0, blir X2 = x 6000 „

,AAA = 4.

Setter vi Aj = 0, blir Aj = ■ 5000 ■- - — 4,8.

Alle produksjonsprogrammer som representeres av linjen Lj gjennom punktene (0, 4) og (4,8, 0), og som dessuten ligger innenfor mulighetsområdet, gir altså kr 24 000 i fortjeneste.

Dersom vi i stedet velger en fortjeneste på f.eks. kr 48 000, kan dette oppnås ved de kombi­ nasjoner av Aj og Aj som oppfyller ligningen L2 nedenfor. L2: 48 000 = 5000%, + 6000Aj Setter vi Xt = 0, blir X2 = ■4^>’ = 8. Setter vi X2 = 0, blir X\ — 4^° — 9,6.

Vi tegner inn 48 000 kronerslinjen L2 gjennom punktene (0, 8) og (9,6, 0) sammen med 24 000 kronerslinjen Lj i figur 5. Vi ser at linjen L2 er parallell med linjen Lt og ligger til høyre for denne. Linjene Lt og L2 kalles for zso-fortjenestelinjer (iso er gresk og betyr «samme»). De har alle samme helning (bratthet). Dette ses på følgende måte: Hvis vi kaller en valgt fortjeneste for K, har vi at

K = 5000%, + 6000Aj.

Herav finner vi y _ _ 5000 y — 6000 A1

k _ _ _5_ „ 6000 — 6 A1

K 6000

hvor koeffisienten foran X] er den samme for alle valg av K.

34

LINEÆR PROGRAMMERING

Fremgangsmåten for å finne den beste produksjonsplan blir da følgende: Fortjenestelinjen L] parallellforskyves mot høyre så langt som mulig, dvs. så lenge som linjen fremdeles skjærer mulighetsområdet. Til slutt går linjen bare gjennom ett av hjørnene i mulighetsområdet. Dette hjørnet representerer da den beste produksjonsplan. Bruker vi denne frem­ gangsmåte på MOCOs problem, får vi figur 6:

Den beste løsning blir punktet Q med

= 12, X2 = 4, som gir

Z = 5000 • 12 + 6000 • 4 = 84 000. Det beste eller optimale produksjonsprogram for MOCO er da følgende: Produksjon av 12 type 1 Produksjon av 4 type 2 Dette gir en maksimal total fortjeneste på kr 84 000.

Legg merke til at L] skyves mot høyre fordi vi ønsker størst mulig fortjeneste. Ofte er vårt mål slik at vi søker en tallmessig minst mulig løsning, f.eks. kostnadsminimering. L] måtte da skyves mot venstre. Legg merke til at Zmax og Zmin nødvendigvis må være i ett av hjørnene i mulighetsom­ rådet. Dette er grunnlaget for Simplexmetoden som er beskrevet i Apppendix, der hjørnene sjek­ kes på en systematisk måte. Det er en vesentlig form for begrensning på produksjonsprogrammene som vi har tatt med i figur 6 uten nærmere kommentar. Det er begrensningen at produksjonsstørrelsene ikke kan være negative tall (f.eks. —10 stk.). Dette kan synes selvfølgelig for MOCOs problem, men er likevel et matematisk vesentlig moment som i enkelte sammenhenger kan føre til ubrukbare løsninger. Det vanligste er at variablene må anta positive verdier eller eventuelt null, men ikke negative verdier. Dette uttrykker vi formelt gjennom ikke-negativitetsbibetingelser, f.eks. X\ > 0, X2 0. Glem aldri å drøfte om modellens variabler har slike bibetingelser. Vi har heller ikke tatt hensyn til at vi har en minsteenhct på ett stk. Et brukbart produksjonspro­ gram må nødvendigvis bestå av hele stk., det er vanskelig å tenke seg at 14 stk. har noen særlig markedsverdi. Dette medfører at mulighetsområdet strengt tatt ikke er hele det skraverte området i figur 6, men bare heltallige punkter i området. Dette er illustrert i figur 7. Her er de mulige produksjonsprogrammer avmerket med sine fortjenester.

35

LP-MODELLERING I DET SMA

d\

2

Z = 5000 Xt+ 6000 X2 gitt 20^+15^2^300

10

lOXj + 2027 2 < 200

60

64

9

54 59

8

48 53 58 63 68

7

42 47

52 57 62 67 72

6

36 41

46 51

5

30 35 40 45 50 55

4

24 29

34 39 44 49 54 59 64 69 74 79 84

3

18 23

28 33 38 43

48 53 58 63 68 73 78

2

12 17

22 27 32 37

42 47 52 57 62 67 72 77

16 21

36 41

11

1

6

0

0

5 10

0

1

2

56 61

26 31

66 71

76

60 65 70 75 80

46 51

56 61

15 20 25 30 35 40 45 50 3

4

5

6

7

8

9 10

66 71

76

55 60 65 70 75 11

12

13

14

15

Figur 7 En helt korrekt fremstilling av MOCOs modell blir da den matematiske modellen (s. 30) med tillegg av presiseringene X, > 0 X2 > 0

X\ må være et helt tall X2 må være et helt tall

eller X} = 0, 1,2,... X2 = 0, 1,2,...

I mange situasjoner av denne type representerer heltallighet ikke noe problem. MOCO fikk en heltallig optimalløsning uten å forlange det spesielt. Andre ganger kan man ganske enkelt, hvis det er nødvendig, avrunde nedover til nærmeste heltall. Vi skal imidlertid være klar over at dette kan lede til løsninger som er langt fra optimale. Vi skal drøfte dette senere i boken. Det er vanlig å sløyfe benevninger i den endelige matematiske modell. Ved formuleringen av modellen, samt ved vurdering av resultatene, er det imidlertid meget viktig å passe på at alle ledd innenfor samme bibetingelse får samme benevning, og at vi husker hva denne er. I MOCOs tilfelle dreier det seg om timer.

La oss nå tenke oss at vi i tillegg til begrensningene med hensyn på tilgjengelig tid i avdelingene også har en salgsbegrensning, nemlig at det ikke er mulig å selge mer enn høyst 7 stykker av type 2. Modellen må da utvides med bibetingelsen X2 < 7

Figur 6 som representerer mulighetsområdet, må da endres ved å føye til en linje parallell med V]-aksen gjennom X2 — 7. Legg merke til at den nye bibetegnelsen ikke er kritisk, dvs. den har ingen effekt på det opti­ male produksjonsprogram. Vi fant at dette hadde X2 — 4. Det er altså ikke «behov» for et så stort maksimalsalg som 7. (Hva blir effekten av et maksimalsalg på bare tre stykker av type 2?)

36

LINEÆR PROGRAMMERING

I dette eksemplet er det altså tilgjengelig tid i avdelingene som begrenser produksjonen. Men dette skyldes igjen de fortjenester som er gitt. Hva ville skje dersom fortjenesten på type 1 var kr 10 000 og ikke kr 5000? Jo: (15, 0) ville gi 15 • kr 10 000 = kr 150 000, mens (12, 4) ville gi 12 • kr 10 000 + 4 • kr 6000 = kr 144 000, altså lavere. Endringer av forholdet mellom for­ tjenestene gir altså mulighet for at det optimale produksjonsprogram blir et annet enn før. Dette fører igjen til at andre ressurser kan bli kritiske. F.eks. vil (15, 0) medføre at det blir tid til overs i avdeling B, denne ressursen er ikke lenger kritisk.

Iso-fortjenestelinjene vil med kr 10 000 for type 1 fa helningen - 10000 = - —, altså brattere 6000

3

enn før. Ved tilsvarende parallellforskyvning som tidligere ser vi lett at punktet (15, 0) faktisk blir optimalt. Se figur 8 som viser to typer isofortjenestelinjer, L for det tidligere fortjenesteforhold og M for det nye:

La oss nå tenke oss at MOCO ikke produserer to, men tre typer, og at problemstillingen for øvrig er den samme. Det beste produksjonsprogram kan finnes på en tilsvarende måte som for to typer, men siden vi nå har tre variabler, må en grafisk fremstilling være i tre dimensjoner, altså i rommet. Bibetingelsene vil bh flater og ikke linjer, og mulighetsområdet vil være et uregelmessig mangekantet legeme. Det beste produksjonsprogram vil være ett av hjørnene i legemet.

Figur 8

Utvider vi MOCOs situasjon ytterligere til fire eller flere typer dreiebenker, er det ikke lenger mulig å tegne grafiske fremstillinger (prøv!). Imidlertid kan prinsippene bak løsningsmetoden foran beskrives på en slik måte at det lar seg gjøre å finne optimalløsningen bare ved hjelp av regning, dvs. uten bruk av figur. Denne beskrivelse lar seg lett generalisere fra to til et vilkårlig antall produkttyper. Selve regnearbeidet vokser med antallet, men prinsippene, og dermed regnereglene, er de samme. Det finnes eksempler fra praktisk produksjonsplanlegging med flere tusen variabler og bibe­ tingelser. Disse skiller seg imidlertid ikke fra MOCOs problem i form, bare i størrelse. Behovet for et dataprogram som kan finne den optimale løsning på en LP-modell, melder seg allerede når antall variabler er lik tre, og det eneste praktiske hjelpemiddel når variablenes antall blir tosifret eller mer. Programmene bygger vanligvis på den såkalte Simplexmetoden (se Appendix 1).

37

LP-MODELLERING I DET SMA

Vi -

vil presentere tre programmer som behandler LP-modeller: Lindo QM Solver i EXCEL

De to første finnes på Internett eller på bokens hjemmeside. Løsningen på MOCOs problem i Lindo ser slik ut:

LP OPTIMUM FOUND AT STEP

2

OBJECTIUE FUNCTION UALUE

84000.00

1)

UALUE 12.000000 4.000000

UARIABLE X1 X2

MAX 5000 SUBJECT TO 2) 3) 4) 5) END

X1 + 6000 X2 20 10 X1 X2

X1 + 15 X2 10

*as+Abs

(3) (4) (5)

Xat + Xbt>15

3. Blandingsforholdene: Det er viktig at man har helt klart for seg hva restriksjonene innebærer. Noen ganger uttrykkes blandingsforholdene komponent mot komponent, andre ganger som komponent mot total mengde, dvs. summen av komponentene. Her får vi: R: minst halvparten må være A, dvs. A må minst være halvparten av totalen, dvs.

2C\r 25 0,5 (JfAR + VBR) som kan skrives

0,5XAR - 0,5XBR

0

eller

-0,5Aar + 0,5ABR

*5 0

(6)

eller

0,65Xas - 0,35%bs

=5 0

(7)

eller

2Aat — AfBT

=5 0

(8)

eller

-0,05Aar + 0,05Xbr

=5 0

(9)

eller

0,02Xas - 0,08AbS

=5 0

(10)

S: høyst 35 % må være A, dvs.

Xas^0,35(Aas+Abs) T: minst dobbelt så mye B som A, dvs. A BT 2= 2Aai R igjen: høyst 15 % må være C, dvs.

0,10XAR + 0,20Abr *5 0,15 (XAR + VBR) S igjen: minst 12 % må være C, dvs.

0,10VAS + 0,20Xbs 2= 0,12 (XAS + Abs)

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

67

I alt får vi altså 10 bibetingelser, hvorav 5 har med selve blandingsforholdene å gjøre. (Merk at (6) og (9) er like, den ene kan derfor sløyfes). Optimal løsning blir: Note ' .... Multiple optimal Solutions exist

r Objective (• Maximize

C Minimize

!

Oppgave 2.14 Ta utgangspunkt i Kjemico ovenfor. Denne modellen har flere optimale løsninger. Prøv å finne andre enn den som er gitt ovenfor.

Oppgave 2.15 Fraktbåt En fraktbåt har tre lasterom: 1 (foran), 2 (senter), 3 (akter). Lasterommene har følgende kapasi­ tetsbegrensninger: Rom

Vekt (tonn)

Volum (m3)

1 2 3

1000 1500 1000

2500 3500 1000

Rederiet blir tilbudt frakt av 3 varer, L, M, N, henholdsvis 1000, 4000 og 2000 tonn, og for­ tjenesten er 70, 60 og 70 kr per tonn. Varevolumet er henholdsvis 1,5, 1,2 og 0,6 m3 per tonn. Rederiet kan akseptere hele eller en del av frakttilbudet for hver av de tre varene. Vektene i hvert fraktrom må være proporsjonal med vektkapasiteten av hensyn til båtens stabilitet. Lasten skal fordeles slik at rederiets fortjeneste blir størst mulig. a) Lag en LP-modell, og finn optimal løsning. Drøft løsningen med hensyn på eventuell over­ kapasitet i de enkelte lasterom hva angår både vekt og volum.

b) Vare M kan demonteres slik at den bare opptar fjerdeparten av det opprinnelige volum. Vis at man far frem en løsning som er en alternativ optimal løsning til den opprinnelige modell. c) Tilbudt mengde av vare L synker med 50 %. Hva skjer?

68

LINEÆR PROGRAMMERING

d) Som uttrykk for et praktisk problem er de stabilitetsbibetingelseene vi har formulert, altfor strenge. En viss slakk vil man kunne ha. Utvid modellen til å tillate en avvikelse fra det ideelle forholdstall på inntil 5 % opp eller ned. Hvorfor øker likevel ikke fortjenesten? e) Anta at volumkapasiteten i fraktrom 3 reduseres fra 1000 til 500 m3. Vis at det nå er av be­ tydning å ha slingringsmonn i stabiliteten.

I dette kapitlet har vi trukket inn en type begrensning, knyttet til kravet om at variablene skal stå i et spesifisert, innbyrdes forhold til hverandre. Dette skjer særlig i problemer med blanding av forskjellige komponenter eller balansering/stabilisering av vektforhold. Bibetingelsene kan da uttrykkes på formen (etter eventuell mellomregning): m




2 0 2

1 3 0

1 2 1

1 1 2

6

2

8

14

10 11 X\x *t0

12

7

8

9

^7

x8

^9

1 0 4

0 4 0

0 3 1

0 2 3

0 1 4

0 0 5

1

10

16

3

9

15

^12

70

LINEÆR PROGRAMMERING

145 cm

1 Yy

k2

3 Yi

4 Y
ii

>12

13 ii3

14 Yt4

1 2 3

1 1 4

1 0 5

0 5 1

0 4 2

5

11

17

1

7

y7

8 Y*

9 Yg

>10

2 1 2

2 0 4

1 4 0

1 3 1

16

3

12

18

15

16

>15

>16

17 Y\i

0 3 3

0 2 5

0 1 6

0 0 7

13

0

6

12

18 >18

Dessuten definerer vi målvariabelen:

Z = totale materialkostnader Materialkostnadene er henholdsvis kr 900 og kr 1200 per stang, dvs. brutto kostnad er lik:

900 (Aj + X2 + ...+V12) + 1200(1) + r2+ ...+^8)

Til fradrag kommer så kr 100 per stang for de stenger som har kapp mellom 14 og 18 cm. Det gjelder variablene X6, X9, X]2, >6, Y9 og fj2 (sjekk med tabellen). Vi får derfor

(min.)

Z = 900 (A, + X2 + ...+Åj2) + 1200(7) + Y2 + ...+7)8) - 100 (%6 + X9 + Zl2 + Y6 + Y) + 7)2)

Dette må naturligvis trekkes sammen før dataverktøy kan benyttes. Bibetingelsene faller i to typer. Den ene typen er knyttet til behovet for deler på 33, 25 og 19 cm, og vi får én bibetingelse for hver lengde. Tar vi lengder på 33 cm først, ser vi at behovet for disse er 160 stk. fordi hvert stk. av produkt P2 trenger ett stk. 33 cm. Vi ser av tabellen hvilke kombi­ nasjoner som gir 33 cm, og vi får dermed følgende bibetingelse:

3Åj + 2X2 + 2X3 + X4 + X5 + X6 + X2 + 4Y} + 3T2 + 37) + 2 7j + 2T5 + 2T6 + 2T7 + y8 + y9 + 7)0+ 7), + t)2 160

(i)

Av lengder på 25 cm er det et behov på 280 • 2 = 560 stk., dvs.:

X2 + 3X4 + 2Z5 + X6 + 4AX + 3V9 + 2A10 + + y2 + 3y4 + 2y5 + y6 + 4y8 + 3y9 + 2 y,0 + + 5^3 + 47)4 + 3 P)5 + 27)6 + yj7 > 560

(2)

Av lengder på 19 cm er det et behov på 160 • 1 + 120 • 2 = 400 stk., dvs.:

X2 + 2%3 + X5 + 2X6 + 4A7 + X9 + 3Aj0 + 4X}, + 5X12 + y2 + 2Y3 + y5 + 2Y6 + 4Y-J + y9 + 37)O + 4YU + 57)2 + y13 + 27)4 + 3y15 + 5y16 + 6y17 + ?y18 2= 400

(3)

Den andre typen bibetingelse er knyttet til forbruk av eget lager. Alt må brukes opp, dvs. summen av alle 110 cm stenger som benyttes, må minst være 25. Det er 12 variabler som tar utgangspunkt i 110 cm, dvs.: Xy+X2+ ...+Xn > 25

(4)

71

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

Kjører vi denne modellen, som altså har 30 variabler og 4 bibetingelser, får vi: XI

X2

X3

X4 Y11 Yl 2

Y13 Y14 Y15

RHS

Y16 Yl 7 Y18

1 200. 200. 200. 900. 900. 900. 900. 200. 100. 1 200. 200. 200. Minimize 0. 0. 0. 0. 0. 1. 0. 1, 1, 2. Likning 1 3. 2. 0. 2. 5. 4. 3. 0. 1. 0. 0. Likning 2 0. 1. 1. 7. 5, 6. 1. 2. 3. 4. 5. 2. 0. Likning 3 0. 1. 0. 0, 0. 0. 0. 0. 1. 0. Likning 4 0. 1. L 1. 0. 0. 0. 76.5217 0. 48.6957 0, 0. 0. 0. Solution-» 0. 80.

>=

>» >«

>=

Dual

160. -267.3913 560. -208.6956 400. -156.5217 25. 0. $222 260.9

Det lønner seg altså å kjøpe inn 55 stenger å 110 cm og la disse, sammen med de 25 på lager, bli kappet opp etter mønsteret 2 • 33 cm, 1 • 25 cm, 1 • 19 cm med null trimtap. Dessuten kjøpes inn 125,218 stenger å 145 cm. Av disse kappes 76,522 etter mønsteret 5 -25 cm, 1 • 19cm med trimtap 1 cm, og 48,696 etter mønsteret 2 • 25 cm, 5 • 19 cm med null trimtap.

Oppgave 2.16 Ta utgangspunkt i Kapping av stenger ovenfor. a) I praksis må vi ha et helt antall stenger. Undersøk hvordan 126 stenger å 145 cm skal kappes opp for å dekke behovet. Blir delingen 77-49 eller ikke? Hvor mange lengder får vi til overs?

b) Får vi samme optimale løsning dersom prisen på 110 cm stenger går ned til kr 800? c) Hva skjer dersom prisen på 145 cm stenger går ned til kr 1100? d) Dersom ordren for produkt P2 blir endret til 200, hvordan påvirkes løsningen?

e) Vi ser at det ikke er interessant å benytte kappkombinasjoner som gir trimtap på 14-18 cm. Hva om prisen på trimtapene blir satt opp fra kr 100 til kr 300? Oppgave 2.17 Kapping av stoffruller En tekstilfabrikk har to maskiner, A og B, som kutter opp store stoffruller (omtrent som å skjære skiver av en pølse). Det er to typer standard stoffruller, en av bredde 250 cm som kuttes av maskin A, og en av bredde 200 cm som kuttes av maskin B. Fabrikken har bestillinger på stoff i bredde 110 cm, 90 cm, 75 cm og 35 cm i et antall på henholdsvis 862, 341, 87 og 216. Stoffbredder på mindre enn 35 cm betraktes som verdiløse.

a) Finn optimal løsning når målet er å minimere antall ruller. b) Finn optimal løsning når målet er å minimere trimtapet.

Eksempel 9 Kapping av stenger 2 (fortsettelse av eksempel 8) Vi vil nå utvide problemet i eksempel 8 i mer realistisk retning. Firmaets mål er ikke lenger å minimere materialkostnadene, men å maksimere det totale dekningsbidrag. Etterspørselen for de tre produktene Pl, P2 og P3 er som før henholdsvis 280, 160 og 120 stk., og salgsprisen er hen­ holdsvis kr 2000, kr 2100 og kr 1800 per stk. Som tidligere kan man selge kapp i 14 -18 cm lengde for kr 100 per stk. Vi antar nå at firmaet ikke har noen stenger på lager. Innkjøpsprisen er som før henholdsvis kr 900 og kr 1200 for stenger av henholdsvis 110 cm og 145 cm lengde, men firmaet har bare kr 100 000 til disposisjon for innkjøp. Dessuten er bearbeidingstiden en knapphetsfaktor, spesielt uttrykt ved den tid det tar å spenne fast og kappe opp stengene. Det tar 10 minutter å spenne fast en stang, uansett hvor mange kapp som skal foretas. I tillegg til dette kommer 3 minutter for hver gang det foretas et kapp. Totalt har

72

LINEÆR PROGRAMMERING

man tilgjengelig 40 timer til kappingen og fastspenningen. Dessuten er det bearbeidingskostnader knyttet til selve kappingen, for hvert kapp er det en slitasje på kappemaskinen samt forbruk av smøreolje som er kalkulert til kr 5 for hver gang det kappes. Dersom det ikke lar seg gjøre å produsere så mye som det er etterspurt, antar vi at det likevel ikke fører til kostnader i form av tapt goodwill etc. 1 tillegg til de 30 variabler vi definerte tidligere, må vi nå innføre 3 nye:

Pi - antall enheter produsert av produktet Pj

i =1,2,3

Dessuten må vi omdefinere målfunksjonen:

Z = totalt dekningsbidrag Målfunksjonen blir sammensatt av fem hovedkomponenter:

- Totale salgsinntekter fra produktene Pl, P2 og P3: 2000P, + 2100P2 + 1800P3

- Totale salgsinntekter fra lange kapp (brukbare trimtap):

ioo(z6 + Å9 + z12 + y6 + r9 + }j2) - Innkjøpskostnader for korte stenger: 12

900 £ Å7-1

- Innkjøpskostnader for lange stenger: 18

1200 V yr j= 1

- Totale bearbeidingskostnader:

5 (3X, + 3Åj> + 4Å3 + 4%4 + ... +6 fj6 + 7fi7 + 7 Yx 8) Merk at antall kappinger er lik antall kapp i alle tilfeller unntatt der hvor det ikke er noe trimtap, da er antall kappinger 1 mindre.

Etterspørselsbibetingelser: Pi

280

P2

160

P3

120

(1),(2),(3)

Pengebibetingelse: 12

18

900 V Åj + 1200 Jj lj =£ 100 000 7=1

7=1

(4)

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

73

Tidsbibetingelse: 10

/ 12 18 1^+ Z

\

>=’

/

V=1

+ 3-(3X1 + 3X2 + ...+7Yi7 + 7E18) « 2400

(5)

Bibetingelser som binder sammen produktene med kappene:

3X} + 2X2 + 2V3 + X4 + X5 + X6 + V7 + 4YX + 3 Y2 + 3r3 + 2T4 + 2E5 + 2Y6 + 2F7 + }g + Y9 + Fj0 + y, J + >12 = P2 (33 cm lengder)

(6)

Sett opp de tilsvarende sammenhenger for 25 cm og 19 cm lengder. I alt har vi nå fått en LP-modell med 33 variabler og 8 bibetingelser, hvorav 5=s og 3 = . Optimal løsning: Maksimal verdi = 418 455

Variabel

Verdi

Variabel

Verdi

x2 x2

32,033 32,683 34,797

P\ Pi Pi

50,813 96,748 120,000

*16

Firmaet produserer altså samtlige tre produkter, men bare for produkt 3’s vedkommende blir etterspørselen dekket. Begge typer stenger blir innkjøpt, og den korteste typen blir kappet opp på to måter, den lengste typen bare på én måte.

Oppgave 2.18 Ta utgangspunkt i Kapping av stenger 2 ovenfor. a) Hva hender dersom salgsprisene for produktene Pl og P2 økes til kr 2200 for begge?

b) Hvor mange timer kan firmaet ha tilgjengelig for produksjon før timetallet ikke lenger blir en knapphetsfaktor? c) Hva hender dersom tiden det tar å spenne fast en stang, reduseres til 5 minutter?

Kapitlet har vist hvordan trimproblemer av forskjellig type i én eller to dimensjoner kan for­ muleres som LP-modeller. Det viste seg at de største vanskeligheter i modellkonstruksjonen ligger i å fastlegge antall kappkombinasjoner, dvs. antall variabler, samt deres trimtap. De forskjellige kombinasjoner kan lett genereres automatisk for trimproblemer i én dimensjon, men dette blir betydelig vanskeligere i to dimensjoner. Dessuten leder denne problemtypen van­ ligvis til et meget stort antall variabler, og praktiske problemer må benytte seg av forenklinger for å redusere antallet. Den enkleste versjon av trimproblemet består i å minimere trimtapet, men som vi har sett, kan trimproblemet inngå som én blant flere komponenter i en større problemstilling.

74

LINEÆR PROGRAMMERING

2.3.4 Transport Kapitlet tar for seg problemer vedrørende transport/distribusjon av en vare fra en gruppe avsendere/varelagre til en gruppe mottagere/kunder. Med utgangspunkt i gitte kvanta på lager og gitte behov, samt gitte enhetskostnader for transport langs de forskjellige transportruter, søker man å finne en optimal transportplan. Problemer av denne typen kan formuleres som LP-modeller, og kapitlet illustrerer dette. Imid­ lertid har transport-modellene (TP-modellene) en spesielt enkel struktur som gjør at de kan be­ handles mer effektivt enn de generelle modeller. Følsomhetsanalyse er imidlertid ikke da så enkelt. Eksempel 10 Tre varelagre, tre kunder En bedrift har tre varelagre A, B og C som inneholder henholdsvis 12, 10 og 11 tonn av en vare. Denne varen er etterspurt av tre kunder L, M og N med henholdsvis 13, 5 og 15 tonn. Kostnadene ved å sende ett tonn fra lager til kunde er gitt ved følgende tabell:

Varelager

A B C

L

Kunde M

N

10 60 30

30 20 10

40 40 50

Bedriften er interessert i å finne den transport-distribusjons-forsendelsesplan som minimerer de totale transportkostnader. Det er naturlig å definere handlingsvariabler med to indekser, en som beskriver avsender, og en som beskriver mottager:

Åjj - antall tonn som sendes fra avsender/lager i til mottager/kunde j i = A, B, C j = L, M, N i alt 9 handlingsvariabler Z — totale transportkostnader

Målfunksjonen blir (min.)

Z= 10Aal + 30Aam+40%an + 60Ab1+20%bm+4()Abn+30%Cl+10%cm + 50Xcn

Hver avsender gir opphav til én bibetingelse. Den skal sikre at summen av det som sendes til de respektive mottagere, er lik det tilgjengelige kvantum. Likeledes gir hver mottager opphav til én bibetingelse. Den skal sikre at summen av det som mottas fra de respektive avsendere, er lik behovet. I alt får man derfor 6 ligninger: A: Aal + Aam + XAN B: -I- XBL + XBM + XBN C. + XCL + XCM + %CN = 11 L: XAL + XBL + ^cl M: + XAM + Abm + XCM N: + A\n + XBN + %cn

Dessuten må naturligvis alle X^

0.

= 12 = 10 - 13 = 5 = 15

75

LP-M0DELLER1NG FOR DIVERSE ANVENDELSESOMRÅDER

Merk at alle bibetingelsene 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 be­ hovene hos mottagerne som er 13 + 5 + 15. Det kan derfor ikke bli slakk eller overskudd noe sted. Merk også at vi har satt opp bibetingelsene på en særlig oversiktlig måte som viser at modellen har en ganske spesiell struktur: Hver variabel forekommer i bare to bibetingelser, én for avsender og én for mottager. Dessuten er summen av avsenderbibetingelsene lik summen av mottagerbibetingelsene. Alle venstresidekoeffisientene er enten 1 eller 0. Denne strukturen kan utnyttes til å løse slike transportproblemer på en langt lettere måte enn å benytte LP-programmer som er laget for å løse det generelle lineære programmeringsproblem, og som ikke tar spesielle hensyn til modellens detaljerte form. Optimal løsning blir: EEÉj Linear Programming R esults

Minimize .Betingelse •“•w• —- Betingelse Betingelse Betingelse Betingelse Betingelse Solution->

1 2 3 4 5 6

Xal

Xam

Xan

Xbl

Xbm

10, 1, 0, 0, 1, 0, 0, 12,

30, 1, 0, 0, 0, 1, 0, 0

40, 1, 0, 0, 0, 0, 1, 0.

60, 0, 1, 0, 1, 0, o. 0,

20, 0, 1, 0, 0, 1, 0, 0,

Xbn

—

—

40J 0, 1, 0, 0, 0, 1. 10,

Xcl

30,

~Tl

l-IDI*l _______ T re varelagre, tre kunder solution RHS Dual Xcm Xcn 10, 0, 0, 1, 0, 1, 0-

0, 1. 1. 0, 01- ___ L

50, 0, 0, 1, 0, 0, 1, 5,

= = = = = =

12, 10, 11, 13, 5, 15, $850,

-30, 40, -50, 20, 40, 0,

——

Vi ser at av 9 mulige transportveier blir bare 5 benyttet i den optimale løsning. Dette er ingen tilfeldighet og kan forklares ut fra teorien for lineær programmering. 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.

Generell TP-modell - Gitt m avsendere, hver med en tilgjengelig varemengde på enheter, i = 1,... , m. - Gitt n mottagere, hver med et behov på d} enheter, j = 1,..., n. - Gitt kostnader ctJ for forsendelse av en enhet fra i til j, i alt m ■ n tall. - Finn den transportplan som minimerer de totale transportkostnader. m

n

- Forutsetning: y s, — V dj j=i

j=i

altså alt sendes og alle behov dekkes fullt ut.

_

76

LINEÆR PROGRAMMERING

Vi definerer følgende variabler:

Ajj = antall enheter som sendes fra i til j i= ,m j = 1, ..., n i alt m • n variabler Z = totale transportkostnader Da får vi følgende:

Generell TP-modell •

m

Z =

(min.)

n

y

Cjj^j

i=\j= i

gitt n

m

'y'.

1 — 1, ••• , ™

-^ij

j= 1

S

~ dj

j ~ 1» ••• > n

i= 1

Og

Ajj > 0

for alle i og j

Modellen har som vi ser m + n bibetingelser i form av ligninger. Av disse er bare m + n — 1 uavhengige. Kjenner vi så mange ligninger, 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 Ssj > Sdj? Det er da klart at bibetingelsene ikke uten videre kan skrives som lig­ ninger. Det er mer tilgjengelig enn det totale behov. Bibetingelsene må derfor formuleres som følger: n V Ajj

nt

5j

z = 1, ... , m

7=1

X Ajj = dj

j = 1, - ,n

i= I

Alternativt kan vi definere en ny mottager, «restlageret», med behov m

dn +

n

. Derved har vi gjenopprettet balansen mellom tilbud og etterspørsel, og

i = X Sj - y

z= 1

7=1

kan skrive n+ 1

y. Ajj

5i

i

1, ... , m

m y Ajj = d}

j = 1,...,/?+ 1

z= 1

7=1

Kostnadene knyttet til denne «mottageren» er naturligvis 0 siden det ikke forekommer noen fysisk transport.Vi Vi går frem på tilsvarende måte dersom Ss, < St/j. Ikke alle mottagerbehov kan nå dekkes, og vi må formulere bibetingelsene slik: n Z v, = * 7=1

m

i — 1, ... , m

y -^ij — dj i= 1

j — 1,..., n

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

77

Definerer vi en ny avsender, «totalt udekket behov», med et tilgjengelig kvantum in

n

d} - y Sj, kan vi altså alternativt formulere ligningene:

Sm + | = j=\

n y Ajj = Si

i=\

z = l, ...

m+ 1 y ^ij =

,m+\

j=\

d}

xn — *11 ~ X112

*21 — ■X2i - ^212

=> => => => =>

x21 x12 x22 x13 x23

*12 “ ■Xi2

+ z112 — z123

*22 = ■x22 ~ ^212 “ ^223 *13 = •Xi3 ~ Zi23

*23 ~ ■x23 — Z223

— — -

*21 ~ X212 *12 + Z112 — Z123 *22 ~ ^212 ~ ^223

*13 ~ Z\23 ¥23 ~ X223

Totalt gir denne modellen altså 16 variabler og 14 bibetingelser.

= = = = =

0 0 0 0 0 0

(9) (10) (11) (12) (13) (14)

84

LINEÆR PROGRAMMERING

Oppgave 2.24 Ta utgangspunkt i Produksjon/lagring/salg ovenfor.

a) Vis at modellen gir optimal løsning Zopt = 2115,67. Drøft løsningen. Hva produseres når? Hvordan skjer eventuell lagring?

b) Foreta følgende endringer av data/parameterverdier, og kjør modellen på nytt: - Antall produksjonstimer tilgjengelig øker med 10 % i periode 2. - Maskin A forbedres slik at fremstillingstiden reduseres med 15 %. — Lagringskostnadene fra periode 1 til 2 reduseres til 0,50. - Produkt 1 pakkes bedre slik at det bare opptar 4 m2 lagerplass. - Fortjenesten på produkt 2 i periode 3 reduseres til 3,50. - Kombiner endringene ovenfor. c) Beregn konsekvensen av følgende tilleggskrav: - Det kan maksimalt selges 100 av hvert produkt i hver periode. - Det skal være 25 av hvert produkt på lager ved slutten av periode 3. Planleggingsperioden utvides til fire perioder. Det er 400 timer tilgjengelig i periode 4 i begge avdelinger. Fortjenesten er 5,00 for begge produkter, og lagringskostnadene til pe­ riode 4 er som til periode 3. - Kombiner endringene ovenfor. Still gjeme noen egne krav i tillegg.

Merk at vi kan forenkle modellen betraktelig ved å erstatte samtlige salgsvariabler med produk­ sjons- og lagringsvariabler. Dette gjør vi ved å benytte ligningene (9)—(14). Setter vi disse inn i målfunksjonen, får vi (maks.)

Z = 3,00 (Ah-Z112) +3,75 (A12 + Z112-Z123) + 6,50 (X13 + Zl23) + 2,25 (X21 - Z212) + 3,00 (X22 + Z2]2 — Z223) + 4,00 (A23 + Z223) - l,00Zll2 - 2,00Z|23 - l,00Z212 - 0,50Z223 = 3,00A,, + 3,75X12 + 6,50X13 + 2,25%2I + 3,00X22 + 4,00%23 0,25Z] i2 + 0,75Z|23 0,25Z212 -I- 0,50Z223

Dermed har vi redusert modellen til å bestå av bare 10 variabler og 8=s bibetingelser, alle =S. Vi ser at vi ved å innføre denne form for substitusjon, nemlig ved å la én eller flere av vari­ ablene bli uttrykt ved en eller flere andre variabler, vil de substituerte variablene ikke ha inne­ bygde ikke-negativitetsbibetingelser. Dersom man ikke ønsker å uttrykke disse bibetingelsene eksplisitt ved hjelp av substitusjonsvariablene, må man kontrollere svaret for å se at de likevel er oppfylt. I dette tilfellet har vi valgt å utelate ikke-negativitetsbibetingelsene for salget, og vi må derfor, når vi finner optimalløsningen, finne verdiene for salget ved hjelp av verdiene på produk­ sjonen og lageret. Blir noen av disse verdiene negative, kan vi slutte at modellen ikke har vært fullstendig, og at vi må legge inn ikke-negativitetsbibetingelser for salgsverdiene. I vårt eksem­ pel oppstår ikke disse problemene.

Oppgave 2.25 a) Kjør modellen ovenfor, og kontroller at den gir samme maksimalverdi som tidligere. Salgstal­ lene gis nå ikke i utskriften, beregn derfor disse selv. Studer verdiene på lagringsvariablene, og forsøk å forklare dem.

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

85

b) En tredje modellformulering får vi ved å definere Ajjk = produksjon av produktet i i periode j som skal selges i periode k z=l,2 #= 11,12,13,22,23,33

Hvert produkt gir 6 variabler (produksjon i periode 1, salg i henholdsvis periode 1, 2 og 3, produksjon i periode 2, salg i henholdsvis periode 2 og 3, produksjon i periode 3 og salg i periode 3). I alt får vi 12 variabler mot før 16 eller 10. Kjør denne modellen, og kontroller at den gir samme maksimalverdi som tidligere. Hvor­ dan beregnes nå produksjon og salg i hver periode, og lagringskostnadene fra periode til periode? Oppgave 2.26 MOCO flerperiode Fabrikken MOCO, som vi kjenner fra tidligere, ønsker å se sine produksjonsproblemer innenfor en større ramme. Mens fabrikken tidligere konsentrerte seg om den førstkommende måned, vil den nå se fire påfølgende måneder i sammenheng. Målet er fremdeles det samme, nemlig maksi­ mering av fortjenesten. Kapasiteten i avdeling A, som var 300 timer i første måned, antas å stige til 330 de neste to måneder, men falle tilbake til 300 timer i fjerde måned. Kapasiteten i avdeling B, som var 200 timer i første måned, antas å være uforandret bortsett fra i tredje måned, hvor den bare er 150 timer. Produksjonsbetingelsene er de samme i de tre første måneder, henholdsvis 20 og 15 timer per produsert enhet av type 1 og type 2 i avdeling A, og henholdsvis 10 og 20 timer per produsert enhet i avdeling B. Installasjon av nytt utstyr i avdeling A gjør imidlertid at man i fjerde måned bare benytter henholdsvis 15 og 10 timer per enhet. MOCO A/S regner med at prisene ikke vil være stabile, men at de vil øke med kr 100 per måned for type 1 og med kr 150 per måned for type 2. Det koster å ha produktene liggende på lager. Lagringskostnadene er for enkelhets skyld knyttet til det antall som ligger over fra en periode til neste. Denne kostnaden er kr 120 for begge typer fra periode 1 til periode 2 og fra periode 2 til periode 3. Fra periode 3 til periode 4 er lagringsfor­ holdene av forskjellige grunner gunstigere, og kostnaden per stk., uansett type, er kr 100. Det er ikke plass til å lagre mer enn 4 enheter fra periode til periode. Etterspørselen antas å være som følger: Av type 1 kan det totalt selges inntil 40 enheter. MOCO kan selv velge i hvilken måned leveransen skal foretas ut fra egne fortjenestevurderinger. Av type 2 kan det hver måned selges inntil 7 enheter. MOCOs problem er nå å bestemme hvor mange enheter som skal produseres og selges av hver type i hver av de fire periodene, og dermed hvor mange som eventuelt skal lagres etter hver periode.

a) Finn optimal løsning.

b) Forsøk å øke lagerkapasiteten med 1 enhet for hver periode, dvs. lagerkapasitet etter periode 1 lik 4, etter periode 2 lik 5 og etter periode 3 lik 6. Vil dette influere på den optimale produk­ sjonsplanen? c) Anta at planleggingen bare går over to måneder, og at resultatene for den første måned be­ nyttes. Det blir derfor tre forskjellige kjøringer over en firemånedersperiode. Vi forutsetter at ingen av problemets data endrer seg, men at begrensning vedrørende maksimal etterspørsel av type 1 settes til 20 over tomånedersperioden mot før 40 over firemånedersperioden. Husk at utgangslager fra første måned for en kjøring vil være inngangslager for neste kjøring. Regn ut den økonomiske effekt av denne planleggingsprosedyren over hele firemånedersperioden, og sammenlign med opprinnelig optimal løsning. Forklar.

86

LINEÆR PROGRAMMERING

Oppgave 2.27 Konsern 2 Et konsern fremstiller aluminium av råstoffet bauxitt. Produksjonen kan kort karakteriseres ved at bauxitten først omdannes til mellomproduktet aluminiumoksyd (Å12O3). Aluminiumoksydet smeltes, og ferdigproduktet aluminium blir dannet gjennom en elektrolyseprosess. Bauxitt kan leveres fra tre gruver, beliggende i A, B og C, med følgende data:

Gruve

Leveringspris kr per tonn bauxitt

A B C

30 25 38

Årlig bauxittkapasitet (tonn)

Utbytte av A12O3

36 000 52 000 28 000

6% 8% 6,2 %

(Vi ser altså at 1 tonn bauxitt fra gruve A gir 60 kg A12O3.)

Foredlingen av bauxitt til A12O3 kan foregå i fire fabrikker, beliggende i henholdsvis B, C, D og E. Fabrikkenes produksjonskostnader, uttrykt per tonn A12O3, og produksjonskapasitet, uttrykt som den mengde bauxitt som årlig kan behandles, er som følger: o

Fabrikk

Variable produksjons­ kostnader (kr/tonn A12O3)

B C D E

23 22 27 17

Årlig bauxittkapasitet (tonn) 40 20 30 80

000 000 000 000

Smeltingen og elektrolysen av aluminiumoksyd til aluminium, samt salget av aluminium, foregår i to bedrifter som ligger i D og E. Tabellen nedenfor gir de nødvendige opplysningene om disse bedriftene. Produksjonskost­ nadene er uttrykt per tonn smeltet aluminiumoksyd. Kapasiteten er uttrykt i det antall tonn alumi­ niumoksyd som kan behandles på ett år. Videre viser tabellen hvor mange tonn aluminium det selges hvert år. Merk at produksjonsprosessen medfører et betydelig svinn. Kolonnen aluminiumsutbytte i tabellen viser at 1 tonn aluminiumoksyd bare gir 0,4 tonn aluminium. o

Sted

Variable kostnader ved foredling av A12O3 (kr per tonn)

Årlig kapasitet for A12O3 (tonn)

Aluminiumsutbytte (prosent)

Årlig salg av aluminium (tonn)

D E

600 370

4000 7000

40 40

1000 1200

87

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

Til slutt har vi disse data for transportkostnadene:

Variable kostnader ved transport av A12O3 (kr per tonn)

Variable kostnader ved transport av bauxitt (kr per tonn)

Til

Til

Fra

A B C

B

C

D

E

28 1 115

140 115 1

35 15 43

155 105 66

_ Fra

B c D

E

D

E

15 43 0 100

105 66 113 0

Det foregår ingen transport av ferdigproduktet aluminium mellom bedriftene i D og E. Anta at salget av aluminium skal tilfredsstilles, og at de samlede årlige råmateriale-, produk­ sjons- og transportkostnadene skal minimeres.

a) Sett opp en LP-modell, og finn optimal løsning. b) Hva vil det koste dersom man forlanger minst 10 % kapasitetsutnyttelse i hver fabrikk? c) Det er nokså dårlig kapasitetsutnyttelse i gruve A. Hva vil det koste å legge ned denne gruven?

d) Det er full kapasitetsutnyttelse i gruve B, noe som bl.a. skyldes det høye utbyttet av alumi­ niumoksyd. Hvor lavt må utbyttet være før det ikke lenger lønner seg med full kapasitetsut­ nyttelse i gruve B? e) Anta at man forventer en salgsøkning av aluminium på 20 % per år på hvert sted i årene som kommer. Hvordan påvirker dette de forskjellige handlingsvariablene i modellen? Oppgave 2.28 Bondens problem En bonde har 700 tonn fullgjødsel, 1500 traktortimer og 18 000 m3 vann som kapasitetsgrenser for neste sesong. Han har erfaring med dyrking av korn, poteter, blomkål og frilandstomater, og har bestemt seg for å dyrke henholdsvis 40,18, 60 og 10 mål med disse vekstene. Som grunnlag for sin beslutning har han nedenstående tabell over ressursforbruk og dekningsbidrag per mål:

Gjødsel (tonn) Traktor (timer) Vann (m3) Dekningsbidrag

Kom

Poteter

Blomkål

Tomater

4 15 125 200

5 18 90 170

6 7 150 210

9 5 200 240

Bonden har egentlig 135 mål til disposisjon, men greier ikke å få tak i mer gjødsel og må derfor la 7 mål stå brakk. Naboen er kjent med disse planene og foreslår: «Siden du ikke benytter ditt dyrkbare areal, er jeg interessert i å leie dette. Dessuten har du til overs 106 traktortimer og 380 m3 vann. Egentlig kunne du vel la meg disponere dette gratis for godt vennskaps skyld, siden du ikke selv har bruk for dem, men jeg vil likevel gi deg en god pris. Du skal få 100 per mål, 1 per traktortime og 0,2 per m3 vann. Da får du et tilskudd på 882 uten å røre en finger.» Bonden syntes naturligvis at dette var et godt tilbud, og slo til. a) Formuler bondens problem som LP-modell. Vis at tilbudet kanskje ikke er så godt likevel.

88

LINEÆR PROGRAMMERING

b) Anta at naboens tilbud ikke bare gjelder de ressurser som er til overs, men alt som bonden disponerer av land, traktortimer og vann. Lag en utvidet modell, og bruk den til å finne ut hva bonden da bør gjøre. c) Forsøk å finne ut hva naboen eventuelt må tilby for gjødsel for at bonden kan være interessert i å selge fremfor å bruke den selv.

Eksempel 13 Kapitalbudsjettering Et firma vurderer å investere i fem forskjellige prosjekter. Over de neste tre årene har firmaet henholdsvis kr 1 000 000, kr 400 000 og kr 400 000 til disposisjon. Firmaet har en låneramme på kr 300 000 til en rente av 8 % p.a. Alternativet til å investere i noen av prosjektene er å sette pengene i bank til en rente av 6 % p.a. Kapitalstrømmene som oppstår ved å investere i de for­ skjellige prosjektene, er gitt i følgende tabell, hvor investeringer er representert ved positive tall og inntekter ved negative tall (i 1000 kr):

1

Ar Diskontert netto inntekt fra og med år

2

Prosjekt 3

4

5

1 2 3

300 150 - 30

280 168 252

240 240 192

590 118 - 59

540 54 108

4

- 525

- 798

- 780

- 767

- 837

Delinvesteringer i de enkelte prosjekter er tillatt. Det innebærer f.eks. at dersom firmaet inves­ terer x % av kr 300 000 i prosjekt 1 i det første året, må denne investeringen følges opp med x % av kr 150 000 i år 2, og i år 3 vil prosjektet i så fall gi en avkastning på x % av kr 30 000. De forskjellige prosjektene vil generere kapitalstrømmer av forskjellig lengde og med for­ skjellig struktur i årene etter planleggingsperioden. Derfor er det nødvendig å diskontere disse kapitalstrømmene tilbake til begynnelsen av år 4 for å finne verdien av de enkelte prosjektene på dette horisonttidspunktet, som for prosjekt 1 da vil være x % av kr 525 000. Alle inn- og ut­ betalinger forutsettes å skje ved begynnelsen av hvert år. Målet for firmaet er å maksimere netto verdi av investeringene ved begynnelsen av år 4, dvs. å maksimere diskonterte fremtidige inn­ tekter + bankinnskudd — gjeld.

Vi definerer følgende variabler:

Xj Bx Lx Z

— = =

Deltagelse i prosjekt j Bankinnskudd i år t Lån i år t Verdien av diskonterte fremtidige inntekter fra prosjektene pluss netto egenkapital per 1. januar år 4.

Videre benytter vi følgende symboler for gitte konstanter:

= Investering/inntekt i år t for prosjekt j = Summen av inntektene generert av prosjekt j fra og med år 4, diskontert tilbake til begynnelsen av år 4 kx = Kapital til disposisjon for investeringer i år t mx — Maksimalt lånebeløp i år t 7=1,2,... ,5 t= 1,2,3 atj Cj

LP-MODELLERING FOR DIVERSE ANVENDELSESOMRÅDER

89

Lån og bankinnskudd kan betraktes som ettårige fornybare kontrakter. Hvis firmaet låner y kroner ved begynnelsen av år 1, må det betale tilbake 1,08y kroner ved begynnelsen av år 2. Setter firmaet y kroner i banken, mottar det l,06y kroner ett år etter.

Målfunksjonen kan nå formuleres slik: 5

(maks.)

Z = Y CjAj + 1,0653 — 1,O8L3 j= i

Vi maksimerer de diskonterte netto inntektene fra de delprosjektene firmaet deltar i, pluss det som er innestående i banken, minus gjeld ved begynnelsen av år 4. Bankinnskuddet ved be­ gynnelsen av år 4 er lik bankinnskuddet ved begynnelsen av år 3 pluss 6 % rente, og gjeld per 1. januar år 4 er lik gjeld per 1. januar år 3 pluss 8 % rente. Summen av investeringer og bankinnskudd minus lån i det første året må være mindre eller lik disponibel egenkapital i år 1, dvs.: 5

F. «ij-Aj +

- L, =s k}

7=1

For år 2 og 3 far vi tilsvarende bibetingelser: 5

Y atjX}- l,065t_! +Bt+ l,08Lt_! - Lt

kt

t = 2,3

7=1

Firmaet kan ikke delta med mer enn 100 % i et prosjekt:

X.J « 1

7J = 1,..., 5

Firmaet kan bare låne inntil et gitt beløp per år:

L{

mt

t = 1, 2, 3

Oppgave 2.29 Ta utgangspunkt i Kapitalbudsjettering ovenfor. a) Finn optimal løsning. Den innebærer at det investeres fullt ut i to prosjekter og delvis i ett prosjekt. Hvilke? Forklar løsningen i detalj. b) Skyggeprisene for de tre kapitalbibetingelsene blir henholdsvis 1,224, 1,145 og 1,060. Bruk dette til å finne marginal gjennomsnittlig årlig forrentning for de tre årene og for hvert enkelt ar. o

c) Definer fem variabler }■= kronebeløp investert i prosjekt j i år 1. Formuler problemet oven­ for slik at }■ blir brukt istedenfor Åj, og kontroller at modellen gir samme svar som tidligere.

d) Hvis man enten må investere 100 % eller la være å investere i det enkelte prosjekt, er løs­ ningen ovenfor ikke brukbar. Forsøk å finne den nye optimale løsning. e) Hva skjer dersom lånerenten senkes til 6,5 %? f) Det viser seg at kr 600 000 av det beløp man regnet med var tilgjengelig i år 1, ikke blir tilgjengelig før i år 2. Hvordan påvirker dette investeringer, lån og forrentning?

Matematisk Programmering

92

MATEMATISK PROGRAMMERING

Del 2 introduserte emnet Lineær Programmering, dvs optimeringsmodeller der både målfunk­ sjon og bibetingelser er lineære, og der det ikke stilles krav om heltallige handlingsvariabler. Den virkelige verden er imidlertid svært ofte ikke lineær, og mange interessante problemstil­ linger kan bare behandles gjennom mer avanserte modeller, der det ikke stilles så strenge krav til linearitet. Generelt kan vi introdusere begrepet Matematisk Programmering som kan defineres som føl­ ger: Matematisk Programmering

Optimering av en vilkårlig målfunksjon under et vilkårlig sett av bibetingelser

Lineær Programmering er således bare et enkelt spesialtilfelle av et stort og komplisert område innenfor matematikken. Vi kan ikke gå i dybden i denne boken, men vi skal ta for oss enkelte interessante og ikke altfor kompliserte spesialtilfeller.

3.1 Lineær Programmering med heltallskrav

Dette spesialtilfellet, også kalt Integer Linear Programming (ILP), tar utgangspunkt i vanlige LP-modeller men pålegger variablene å være hele tall større eller lik 0. Vi illustrerer problemstillingen med følgende «klassiker» - «ryggsekkproblemet» eller «the knapsack problem»: Du skal på fottur og kan bære med deg 11 kilo. Du må velge mellom fire ting som foreligger i pakninger. En pakke med ting A veier 1 kg, en pakke med ting B veier 2 kg, en pakke med ting C veier 3 kg, og en pakke med ting D veier 4 kg. Du har vurdert nytten av en pakke med ting A til 2 nytteenheter, av en pakke med ting B til 5 nytteenheter, av en pakke med ting C til 6 nytteenheter og av en pakke med ting D til 12 nytteen­ heter.

Pakke

Vekt (kg)

Nytte (enh)

Nytte/vekt

A B C D

1 2 3 4

2 5 6 12

2 2,5 2 3

Du ønsker å pakke sekken din slik at du maksimerer total nytte.

Anta først at du ikke er begrenset til å ta med deg et helt antall pakker av hver ting. Vi kan da lett formulere en LP-modell av problemet:

Aj = antall pakker av ting i Z = total nytte (maks.) gitt

i — A,B,C,D

Z = 2Aa + 5XB + 6AC + 12AD VA + 2Xb + 3XC + 4XD < 11

Det er ikke nødvendig å benytte noe dataverktøy for å finne optimal løsning her. Vi beregner nytte per vektenhet for de fire tingene A, B, C, D og får y = 2, — = 2,5, — = 2, — = 3. Ting D har størst nytte per vektenhet, og du tar derfor med deg så mye som mulig av denne, nemlig

XD = -y = 2,75 pakker.

Dette gir deg en optimal nytte Zmax = 12 • -y = 33.

94

MATEMATISK PROGRAMMERING

Slik ser løsningen i QM ut.

XA

XB

XD

XC

RHS Dua

-- ...... . Maximize A Solution->

Anta deretter at du er begrenset til å ta med deg et helt antall pakker av hver ting. Da kan løsningen ovenfor ikke brukes. Avrunding nedover til Xo = 2 tar 8 kilo med nytte 24, og de gjenstående 3 kilo kan være enten 3 pakker A, eller 1 pakke A og 1 pakke B, eller 1 pakke C. Det midterste alternativ er best med nytte 2 + 5. Total nytte blir således 31. Dette viser seg å være optimal heltallsløsning, altså Zopt = 31

XA=1

%B-1

%c = 0

XD = 2

Nå er det vanligvis tidkrevende å finne og analysere slike løsninger ved avrunding når modellen er stor. Enda verre er det faktum at den optimale ILP-løsning ofte kan ligge så langt fra den optimale LP-løsning at den ikke kan finnes ved avrunding. Studer f.eks. følgende eksempel:

(maks.)

Z = 2Xx + X2

gitt

og

-6Åj +'1X2 I B

U |

95

gt gg

= ; =2*B6-i5*B7-t6*B8+12*B9

L8

A 1 Ryggsekkproblemet 2

3 Total nytte

sH

4 5 Variable: 6 Xa

1

7 Xb 8 Xc

0

9 Xd 10 11 Betingelser 12 13 14 15

1 2 11 1

1 0

2

Her har vi satt de fire variablene i rutene b6 til b9 (Changing cells). Disse skal være heltallige (int) og > 0. Hovedbetingelsen finner du i bil, og funksjonen Z som skal maksimeres er i b3 (Target cell).

Oppgave 3.1 Gitt følgende modell av «ryggsekk-typen»: 5+ (maks.) Z = 55X[ + 75X2 + 40X3 +-^X4 + 70X5 + 10X6 + 30X7 gitt 3,5Xj + 5X2 + 4X3+ 4,5X5 + 3X6 + 2X7 15 min) = e

-io — 60 « 0,08

Tallmaterialet ga 2 av 51 tidsintervaller større enn 15 minutter. Dvs. at: P(T> 15) « — « 0,04 51

Hovedpoenget i fremstillingen ovenfor er at vi forsøker å lage en matematisk/statistisk modell av en kundestrøm. Vi tar utgangspunkt i den virkelige verden, kanskje har vi foretatt en del observa­ sjoner, og vi vil forsøke å finne et «mønster», altså en sannsynlighetsfordeling som best mulig beskriver de variasjonene vi har observert. Variasjoner kan være så mangt, kanskje det ikke engang er noen variasjoner i kundestrømmen, dvs. kundene kommer med fast mellomrom? Vi vil imidlertid svært ofte finne et ankomstmønster slik som i gatekjøkkenet. Det kan nemlig vises teoretisk at dersom en større mengde potensielle kunder foretar sine kjøpsbeslutninger uavhengig av hverandre og uavhengig av køsystemets ak­ tuelle tilstand, så vil variasjonen i ankomsttidspunkt være negativt eksponensialfordelt. For nybegynnere med ikke altfor god matematisk bakgrunn er det nettopp starten på køteorien som representerer den største utfordringen. Det er viktig å forstå at vi trenger kontinuerlige sannsynlighetsfordelinger for å beskrive variasjoner i tider, siden ethvert tidsintervall jo er mulig. Dette verktøyet bygger på integralregning, og du må nødvendigvis beherske de grunnleggende deler av dette. La oss gå videre i teoriforklaringen. Vi har også at: P (tidsintervall mellom to påfølgende kunder F(f) = P(T^t) = 1 - e~Ål

t) =

211

ANKOMSTPROSESSEN

Senere får vi bruk for sannsynligheten for at det kommer en ny kunde innen et meget kort tidsrom At:

^(tidsintervall mellom to påfølgende kunder < Ar) — 1 - e~K^‘ Fra matematikken vet vi (Taylors formel) at funksjonen ex kan uttrykkes som et polynom med uendelig antall ledd på denne måte: r2

xn

ex = 1 + x +---2!

n\

og anvendervi dette,får vi:

1 - e-AA/

+ 8

m

Qn

m = antall kvarters-intervaller der det kommer n kunder

20

0,082 0,205 0,257 0,214 0,134 0,067 0,028 0,010 0,003

2 3 5 4 4 2 0 0 0

0,10 0,15 0,25 0,20 0,20 0,10 0,00 0,00 0,00

ANKOMSTPROSESSEN

213

Eksempelvis kommer det ingen kunder i intervallet 15-30 minutter og 90-105 minutter, dvs. at for n = 0 blir m — 2. Uoverensstemmelsene skyldes at antall observasjoner er lite. Med et større antall observasjoner kan vi regne med å fa bedre tilpasning, vel å merke dersom ankomstene virkelig er Poissonfordelt. Kundestrømmen til gatekjøkkenet skulle nå være klarlagt.

Oppgave 6.2 Ta for deg en Markov-ankomstprosess med A = 7 kunder per time. Beregn: a) Sannsynligheten for at det går mer enn ett kvarter mellom to kunder.

b) Sannsynligheten for at det går mellom 6 og 10 minutter mellom to kunder. c) Sannsynligheten for at det kommer 7 kunder i løpet av en time.

d) Sannsynligheten for at det ikke kommer noen i løpet av ett kvarter.

Oppgave 6.3 Ta for deg en Markov-ankomstprosess der det kommer gjennomsnittlig én kunde hvert 5. minutt. Hva er sannsynligheten for at det kommer minst 3 kunder i løpet av 20 minutter?

6.4 Betjeningsprosessen

I dette avsnittet skal vi se på betjeningen/ekspedisjonen i gatekjøkkenet, eller det vi formelt kaller betjeningsprosessen. Betjeningshastigheten er avhengig av to faktorer. Den ene er kundenes be­ hov for ekspedisjon, uttrykt ved om de bare skal kjøpe en sjokolade, eller om de skal utstyre seg for et helt selskap, eller skal spise middag ved gatekjøkkenet. Denne faktoren er ikke avhengig av ekspeditøren. Den andre faktoren representerer selve arbeidstempoet til gatekjøkkenets ekspedi­ tør. Vi antar at vi kan uttrykke begge disse faktorene samtidig ved det gjennomsnittlige antall kunder som kan betjenes per time, her 15 for Hansens vedkommende. Vi generaliserer dette på tilsvarende måte som for ankomstprosessen ved å innføre den greske bokstaven p (my) som symbol for følgende størrelse:

Betjeningsintensitet p Det forventede antall kunder som kan betjenes per tidsenhet

Herav følger:

Betjeningstid — Den forventede betjeningstid for en kunde

Problemstillingen er nå helt analog med den vi hadde vedrørende kundestrømmen. Vi er interes­ sert i å finne den sannsynlighetsfordeling som karakteriserer betjeningsprosessen. Vi vil definere en funksjon:

Sannsynlighetstetthet g (t) T Betjeningstiden har sannsynlighetstettheten g(t) g (t) Beskrivelse av usikkerheten i T

Eieren vil derfor analysere betjeningstidene for kundene over en lengre periode. For Hansens vedkommende ble disse registrert ved at han prøvebetjente gatekjøkkenet samme kveld som man også registrerte kundeankomstene, som presentert foran. Betjeningen forløp som følger:

215

BETJENINGSPROSESSEN

Kunde nr.

Betjeningstid

Kunde nr.

Betjeningstid

Kunde nr.

Betjeningstid

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

14,63 0,39 3,45 1,37 5,56 2,58 12,42 3,42 2,24 1,28 4,42 4,91 2,04 1,08 5,41 0,83 0,15

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

8,71 2,53 0,92 0,72 1,13 0,20 1,63 9,99 0,93 3,08 6,84 0,75 8,23 4,94 1,22 7,12 9,18

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

8,07 4,28 9,84 1,72 3,21 0,31 8,87 7,05 2,59 0,63 3,63 2,21 1,93 1,43 5,39 0,29 0,08

På samme måte som tidligere teller vi opp hvor mange ganger betjeningstiden var hhv. 0-1 minutt, 1-2 minutter osv., og får følgende tabelloppstilling, også fremstilt grafisk:

Oppgave 6.4 På tilsvarende måte som for ankomstprosessen, lag histogrammer der tidsintervallet er hhv.: a) 0,5 minutt

b) 2 minutter

c) 5 minutter

216

KØTEORI

Det viser seg altså at ganske mange ekspederinger tar forholdsvis kort tid. Til gjengjeld kommer det av og til kunder som trenger lang betjeningstid. Gjennomsnittlig betjeningstid for 51 kunder er 3,84 minutter (kontroller dette selv). Når dette tallet avviker fra 4 minutter, som vi påsto var Hansens gjennomsnittlige arbeidstempo, skyldes det igjen at observasjonsmaterialet egentlig er betydelig større enn fem timer. Histogrammet synes å ha samme form som histogrammet over ankomstintervallene, jevnt over forekommer lengre betjeningstider sjeldnere enn kortere betjeningstider. Ut fra tilsvarende vur­ deringer som tidligere synes det hensiktsmessig å beskrive betjeningsprosessen som en Markovprosess. Dette betyr altså at:

g(r) =

jjue

dvs. at betjeningstiden beskrives av den negative eksponensialfordelingen med parameter /jl. Analogt med tidligere er sannsynligheten for at en kunde som holder på å bli ekspedert på et gitt tidspunkt, skal bli ferdigekspedert i løpet av de nærmeste A/ tidsenheter, lik /xAr (A/ må være liten). En annen analog sammenheng har vi i: P (en ekspedisjon varer mer enn b tidsenheter) = P(T>b) = J /uce Md/

h

= e~*b Også Poissonfordelingen kommer til anvendelse, dog med en liten nyanseforskjell fra tidligere definisjon:

Pn (t) = P(n kunder blir ferdigbetjent i et tidsintervall av lengde t, under forutsetning av at betjening/ekspedisjon pågår hele tiden)

og vi har at: PM = JÆL

n = 0, 1,..., oc

n'.

Oppgave 6.5 Det kan være interessant å studere de forskjellige søkernes arbeidstempo i forhold til hverandre. Det er rimelig å anta at samtlige ekspeditørers betjening kan karakteriseres ved en negativ eksponensialfordeling, den eneste forskjell består i verdien på betjeningsintensiteten /jl. Hva er sannsynligheten for at en ekspedisjon tar mer enn 5 minutter for hver av de 4 søkerne (også Pettersen som ikke strakk til under noen omstendighet)?

Legg merke til at tallmaterialet er valgt slik at det følger samme mønster som for ankomstpro­ sessen. Dermed kan vi også benytte den negative eksponensialfordelingen som modell, og de to prosessene blir av samme type. Dette viser seg senere å lette arbeidet med å lage en modell for hele køsystemet. Imidlertid er det ikke så selvfølgelig i praksis at du observerer variasjoner i betjeningstider av denne type. Vi skal senere se hvordan vi modellere andre typer betjeningsvariasjoner.

6.5 Køsystemet MIMI\

Vi er nå kommet så vidt langt i vår analyse at vi vet hva som karakteriserer vårt køsystem. Det er den simultane, gjensidige påvirkning av to Markovprosesser, en som representerer kundestrøm (ankomst), og en som representerer betjening, som er årsak til at det oppstår kø. Vi kan fremstille køsystemet ved hjelp av en figur:

Kunder i kø

Kunde som betjenes

Symbolet M står for Markov-prosess. Vi karakteriserer vårt køsystem som et M/M/X system, i overensstemmelse med vanlig forekommende terminologi:

alblc køsystem: Et køsystem der - ankomstprosessen er av type a - betjeningsprosessen er av type b - antall ekspeditører er lik c

Vi har her et system med bare én ekspeditør og to Markov-prosesser, herav et M/M/X system. Vi skal nå søke å finne frem til størrelser som karakteriserer køsystemets oppførsel, altså sam­ virkningen av de to Markov-prosessene. Vi definerer: N(i) = antall kunder i køsystemet ved tidspunktet t Pn(t) = P(N(t) = n) = P(det er n kunder i køsystemet ved tidspunktet t)

218

KØTEORI

Sannsynlighetene Pn (t) vil naturligvis avhenge av køsystemets starttilstand. f.eks. dersom 4 kun­ der står i kø utenfor en butikk når den åpner, er (0) = 1, P„(0) = 0 n A 4. Vi vil imidlertid her beskjeftige oss med køsystemets stasjonære tilstand, altså når virkningen av startti 1 standen antas å være forsvunnet. Da er t uinteressant, og Pn (t) skrives som Pn. Utledningen av formelen for Pn er relativt komplisert og presenteres ikke her. Vi får:

Tilstandssannsynligheten for et M/M/1-system Å \ / Å \n

(

1------- || ----- ) M/ \ M/

H=0,l,...,OO

Det er satt et eget navn på forholdet mellom ankomstintensitet og betjeningsintensitet, nemlig trafikkintensiteten p (ro), altså:

Dette gir Pn = pi' (1 - p) Navnet trafikkintensitet skyldes at sannsynligheten for at det er trafikk i systemet, er 1 — P{} som

nettopp er lik y. Vi er nå i stand til å finne P(det er n kunder i køsystemet ved et vilkårlig tidspunkt) for

samtlige av søkerne unntatt Pettersen (hvorfor)? Vi har Å = 10 per time, eller y per minutt. Vi setter forskjellige verdier av betjeningsintensiteten p inn i formelen for

Andersen: p = 20 per time

Hansen: p = 15 per time / _ 10 \ / 10 \” _ II I \ 15 / \ 15 J I 1

Olsen: p = 12 per time

1 /2_Y I I 3 \ 3 /

og får:

219

KØSYSTEMET M/M/\

Med forskjellige verdier av /z får vi følgende tabell og figur:

n

/z = 20 Andersen

/z,= 15 Hansen

/z=12 Olsen

0 1 2 3 4 5 6 7 8 9 10

0,5000 0,2500 0,1250 0,0625 0,0313 0,0156 0,0078 0,0039 0,0020 0,0010 0,0005

0,3333 0,2222 0,1481 0,0988 0,0658 0,0439 0,0293 0,0195 0,0130 0,0087 0,0058

0,1667 0,1389 0,1157 0,0965 0,0804 0,0670 0,0558 0,0465 0,0388 0,0323 0,0269

Vi ser at mens det er meget liten sannsynlighet for å finne mer enn ni kunder i køsystemet med Andersen, så er sannsynligheten for dette ca. 2- med Olsen. Nå er ikke tilstandssannsynlighetene Pn noe særskilt godt beslutningsgrunnlag, det blir sim­ pelthen for mange tall å holde styr på. Et bedre beslutningsgrunnlag finner vi i forventnings­ verdien, dvs. det forventede antall kunder i køsystemet, kalt E (N) (eller Ls som er vanlig i engelskspråklig litteratur). Vi har at:

EW =

f iP, = f l(l - —) (—

i=0

i=0

\

M/VM.

220

KØTEORI

Det kan vises at dette uttrykket kan utvikles videre til:

£(7V) =

A /i — Å

Vi ser at differansen mellom de to karakteristiske størrelsene A og /jl forekommer i nevneren i formelen. Dette betyr at dersom A og /jl er nær hverandre og det dermed bare så vidt er kapasitet til å betjene kundestrømmen, vil det i gjennomsnitt være svært mange kunder i køsystemet. La nå Nq være antall kunder i kø (eller Lq i engelskspråklig litteratur). Hva er nå det for­ ventede antall kunder i kø, E (AQ? Merk at E (Nq) A E(N) - 1. Disse to uttrykkene er bare like dersom det alltid er en kunde under betjening, noe som ikke er tilfelle, køsystemet kan være tomt. Den korrekte sammenheng, uten at den skal bevises, er: A2

E(Nq) = E(N)~— = —------ jj /L ~ A /JL

- A)

En tredje forventningsverdi av interesse er detforventede antall kunder i kø, gitt at det virkelig er kø, kalt E (Nq | N > 1). Vi ser her altså bort fra de tidsperioder hvor det ikke er noen i køsyste­ met, eller hvor det bare er én kunde som dermed blir betjent. Vi har at:

E(Nq\N> 1) =

£(MZ)

/jl

1 - P> - Pi

/i — A

_

/jl — A + A _ - + A /jl — A /i — A

= 1 + £(V) Disse formlene anvender eieren nå på sitt gatekjøkken-system. Ved utregning (kontroller selv) fås følgende:

Andersen Hansen Olsen Pettersen

20 15 12 9

£(7V)

E(Nq)

E(Nq\N>>1)

1 2 5 —

0,5 1,333 4,167 —

2 3 6 —

Vi ser at det forventede antall kunder i kø blir stort når /x er nær A. Selv om Andersen bare arbeider 1,67 ganger hurtigere enn Olsen, vil i køen foran Olsen i gjennomsnitt være, 8,33 ganger større! Vi har nå et ganske godt beslutningsunderlag, men vi vil likevel vente litt med den endelige beslutning. Vi har utledet flere forventningsverdier som angår antall kunder. Like interessant er det imidlertid å betrakte tider tilknyttet kunde og køsystem. Kaller vi ventetiden for Wq, har vi forventet ventetid E(lVq). Med ventetid mener vi da den tid som kunden tilbringer i køen og ikke i selve betjeningssituasjonen. Det kan vises at følgende sammenheng gjelder (resultatet er meget generelt og krever beskjedne forutsetninger som vi ikke skal komme inn på her):

E(Wq) =

E(Nf A

eller

TL\

KØSYSTEMET MIMI\

K = ~7------ K

Kaller vi kundens totaltid i køsystemet, dvs. ventetid + betjeningstid, for W, har vi at (hvorfor?): £W = W) + —

eller

1__

E(1F) = ------ ------- + —

/x(ai-å)

/x — A

il

Dessuten har vi den forventede ventetid for de som virkelig må vente, kalt E (| Wq > 0):

A e(^|

^>o) =

E(PF)

~ A)

E(lF>0)

A

=

1 gc — A

Anvender vi disse formlene på gatekjøkken-systemet, får vi følgende:

E (Mf (minutter) E(W) - E(Wq\ M^> 0) (minutter)

Andersen Hansen Olsen Pettersen

20 15 12 9

3 8 25 —

6 12 30 —

Vi ser at også tidene blir svært store når A og g er nær hverandre. Før vi vurderer søkernes kvalifikasjoner, skal vi avrunde formelverket med enda et par viktige momenter. Det kan tenkes at vi ikke er fornøyd med å finne bare forventet ventetid eller totaltid, og gjeme vil finne sannsynligheten for at ventetid eller totaltid overskrider en gitt tid.

Det kan vises at for ventetid er:

A e(Å -

Tilsvarende formel for totaltid er: P(W>t) =

fjåt

Tn

KØTEORI

Oppgave 6.6 Finn for samtlige søkere til gatekjøkkenet: a) P(en kunde må vente mer enn 10 minutter) b) P(en kunde må vente mellom 2 og 4 minutter)

Ser vi på ekspeditørens arbeidssituasjon, vet vi at han er beskjeftiget en brøkdel — av tiden.

Kaller vi varighet av en sammenhengende periode med betjening for E, har vi at:

E® = ------- g—Å

Kaller vi antall adskilte ekspedisjonsperioder i løpet av tiden t for A, har vi at:

E(A) = å(1 - — M /

\

I løpet av en femtimers arbeidsdag i gatekjøkkenet kan ekspeditøren «forvente» følgende arbeidssituasjon:

Andersen Hansen Olsen Pettersen

20 15 12 9

Beskjeftigelsesgrad i %

Forventet lengde av sammenhengende arbeid (min.)

Antall adskilte arbeidsperioder

50 66,67 83,33 —

6 12 30 —

25 16,67 8,33 —

Vi har nå presentert det sentrale formelverk for et MIMI1 køsystem og har dermed et godt kjenn­ skap til systemets operative egenskaper.

223

KØSYSTEMET M/M/\

I programsystemet QM finnes det en modul for forskjellige køsystemer. Vår modell MIMI\ med Andersen som ekspeditør kan presenteres på denne måten:

Cost analysis (• No costs O Use Costs

Model

Time unit (arrival, service rate) _^J

M/M/s

hours

v|

IjffiWaiting Lines Results Andersen Solution

Parameter

Value

M/M/s Arrival rate(lambda) Service rate(mu) Number of servers

10. 20, 1.

Parameter Average Average Average Average Average

Value Value * 60

server utilization number in the queue(Lg) number in the system(Ls) time in the gueue(Wq) time in the system(Ws)

If^Table of Probabilities

k 0 1 2 3 4 5 6 7 8 9 10 11

Prob (num in sys = k)

0.5 0.25 0.125 0.0625 0.0313 0.0156 0.0078 0.0039 0.002 0.001 0.0005 n nnn?

Prob (num in sys k) 0.5 0.25 0.125 0.0625 0.0313 0.0156 0.0078 0.0039 0.002 0.001 0.0005 n nnns>

Andersen Probabilities P(N = k)

0.5 0.5 1, 0.05

Value * 60*60 _________

3. 6.

180. 360.

224

KØTEORI

Oppgave 6.7 Utfør tilsvarende beregninger som foran for tre nye aktuelle søkere: a) «Snegla» med /jl = 10,5 kunder per time

b) Jonsen med /jl = 16 kunder per time c) «Speedy Gonzales» med /jl = 30 kunder per time

Oppgave 6.8 Det forventes å komme 8 kunder per time, og forventet betjeningstid er 5 minutter. Hva er: a) Sannsynligheten for at det ikke er noen kunder i køsystemet?

b) Forventet kølengde? c) Forventet ventetid?

d) Sannsynligheten for at ventetiden er større enn 3 minutter?

e) Sannsynligheten for at totaltiden er større enn 8 minutter? Oppgave 6.9 Det forventes 3 minutter mellom hver kundeankomst, og forventet ventetid er 4,5 minutter. Hva er:

a) Forventet betjeningstid? b) Forventet antall kunder i køsystemet?

c) Sannsynligheten for at ventetiden er mellom 3 og 6 minutter?

d) Forventet bcskjcftigclsesgrad for ekspeditøren?

e) Forventet kølengde når det er kø?

6.6 Økonomisk vurdering av køsystemet

Hvilken av de tre beste søkerne bør ansettes? Naturligvis kunne eieren resonnere som følger: Anta at kundene aldri blir utålmodige, at de finner seg i å stå i en kø uansett lengde og varighet, og dessuten at en slik kundebehandling ikke får varig effekt på gatekjøkkenets rykte. Da er saken opplagt, eieren bør ansette den søker som er billigst av dem som greier å holde kundestrømmen unna, nemlig Olsen! Disse forutsetningene må i beste fall sies å være tvilsomme! Hva bør vi gjøre? Dersom vi forutsetter at kundene blir utålmodige, har vi en helt ny situasjon som gjør at formelverket foran ikke lenger kan anvendes. Utålmodigheten kan gi seg utslag på to hovedmåter: • Kundene vurderer situasjonen når de ser køen utenfor gatekjøkkenet. Jo lengre køen er, desto mindre tilbøyelige er de til å stille seg i den. • Kundene stiller seg alltid i kø, men blir utålmodige etter hvert og blir dermed tilbøyelige til å forlate køen uten å ha fatt betjening.

Formelverket vårt forutsetter at alle kunder som ankommer, før eller senere får betjening. Derfor kan ikke formelverket behandle utålmodighetssituasjonen direkte. Istedenfor å forsøke å utvikle et formelverk som direkte tar hensyn til utålmodighet, skal vi behandle utålmodighet indirekte på følgende to måter: • Vi knytter kostnader til kundenes forventede ventetid og/eller totaltid i køsystemet. Disse kostnadene kommer altså i tillegg til ekspeditørkostnadene. • Vi stiller servicekrav til køsystemet, uttrykt ved at forventede ventetider/totaltider/kølengder etc. skal holdes innenfor visse på forhånd fastsatte grenser.

Vi skal først ta utgangspunkt i kostnader. Kaller vi køsystemets totalkostnad per time for TK, er denne i utgangspunktet en funksjon av to variabler, som karakteriserer hhv. ankomstprosessen og betjeningsprosessen, altså TK(X, /jl). Her er imidlertid kundestrømmen gitt, og det er bare som kan oppfattes som en variabel. Altså har vi kostnadsfunksjonen TKft | A = konstant). Hva slags form har denne funksjonen? Det kan synes naturlig å modellere TK som

TKig | A = konstant) = f (/z) +f2 (A, /z) +f (A, /z) der

• • •

f representerer konkrete lønnskostnader til ekspeditøren, avhengig av betjeningskapasiteten. J2 representerer subjektive kostnader knyttet til selve ekspederingen. Sen ekspedering irri­ terer og ødelegger gatekjøkkenets gode rykte. f representerer subjektive kostnader knyttet til selve ventingen i kø. Lang ventetid er også irriterende.

(Merk at f2 og f i mange køsystemer kan være høyst objektive kostnader, f.eks. benyttet til bundet kapital i et produksjonssystem der «kundene» representerer «varer i arbeid».)

226

KØTEORI

Vi skal konkretisere dette nærmere og må derfor gjøre forutsetninger om formen til funksjonene f, fi og/3Vi erstatter f (/jl) med Cj • /jl, dvs. vi antar at lønnskostnaden er proporsjonal med yteevnen, dvs. betjeningskapasiteten. Dette synes i hvert fall å være tilfelle for søkerne til gatekjøkkenet, der Cj — kr 10 per kunde. (Av situasjonsbeskrivelsen for gatekjøkkenet går det frem at for­ holdet mellom krav til timelønn og betjeningskapasitet er lik 2 for alle søkerne.)

Videre erstatter vi f2 (A, /jl) med C2 • A • —, dvs. vi antar at den subjektive kostnad ved eks-

pedering er proporsjonal med betjeningens varighet. C2 uttrykkes i kr per time når ekspedisjon pågår.

Tilsvarende erstatter vi /j (A, /jl) med C3 • A • ———, dvs. vi antar at også ventetidskostnadene er lineært avhengig av ventetiden. C3 uttrykkes i kr per time når venting finner sted. Herav får vi:

TK(/jl) = Q/jl +

A

A2

M

/1(/L~Å)

C2— + C3 —------ —

Det kan vises at dette gir en ijerdegradsligning til bestemmelse av optimal /jl. Vi kan forenkle situasjonen ved å anta at irritasjon ved sen ekspedering er den samme som irritasjon ved venting i kø hva kr per time angår. Vi kan da sette C2 = C3. Dermed får vi (for­ klar):

TK(/jl) = Cj/z + C2A--------/jl — A

Hvordan bør gatekjøkkeneieren nå vurdere de subjektive kostnader? Det er i hvert fall innlysende at dersom dårlig service ikke tillegges noen som helst vekt slik at C2 = 0, blir p,opt = A, eller egentlig «så vidt» større siden forutsetningen er at — < 1. Det spiller da ingen rolle hvor lang

køen er. Under disse omstendigheter er selv Olsen for rask! La oss forsøksvis sette C2 = kr 25 per time. Hvilken ekspeditør bør ansettes? Vi får, idet vi husker at A = 10 kunder/time:

Andersen

/jl (kunder/time) Forventet totaltid E(W) — /z A (minutter) «Dødtid» per time XE(W) (minutter) Kostnader ved dødtid C2KE(W) (kr/time) Timelønn C\/jl (kr/time) Totale kostnader (kr/time)

Hansen

Olsen

20

15

12

6

12

30

60 25 200 225

120 50 150 200

300 125 120 245

Hansen blir altså den ekspeditøren som minimerer de totale kostnadene og derfor bør velges. Vi kan også finne den optimale ekspeditør med betjeningskapasitet /zopt. Vis selv at vi ved derivasjon og ved å sette den deriverte lik 0 får den optimale ekspeditør:

227

ØKONOMISK VURDERING AV KØSYSTEMET

Mopt - A +

Da får vi

Mopt = 10 + u ~— 10= 15

(kunder per time)

Med dette valg av C2 blir altså Hansen ikke bare den beste av de fire søkerne, men den «opti­ male» søker!

Oppgave 6.10 Hva må C2 være for at Olsen er bedre enn Hansen?

Vår vurdering står og faller med størrelsen på kundekostnadene, som altså i dette køsystemet overveiende må antas å være av subjektiv art. Det er vanskelig å bestemme disse nøyaktig. Hvis gatekjøkkenet ikke har konkurrenter og kundene gjeme benytter ventetiden til å slå av en prat med medkundene som er venner fra nabolaget, må kundekostnadene kunne antas å være små. Ligger det derimot en pølsebod med rask betjening på neste hjørne, vil kundene trolig forsvinne lynraskt for senere å bli stamgjester hos konkurrenten. Kundekostnadene blir dermed store og knyttet til tap av fremtidig fortjeneste. En annen sak er at selve forutsetningen for vår analyse ikke helt gjelder lenger i sistnevnte tilfelle. Vi har nemlig gått ut fra en konstant gjennomsnittlig kundestrøm over tid, karakterisert ved parameteren A. Et systematisk kundefrafall skaper en ny situasjon. Ut fra disse betraktningene kan det synes fornuftig å velge en mer indirekte vurderingsmåte, som nevnt foran, der det stilles servicekrav til køsystemet. Vi lar da de konkrete økonomiske betalbare faktorer inngå i en målfunksjon som skal minimeres. Servicekravene uttrykkes som beskrankninger. Vi kan eksempelvis anta at eieren mener at det må være et ufravikelig krav at den gjennomsnitt­ lige ventetid ikke må overskride 5 minutter, og at det i gjennomsnitt ikke må være mer enn 3 kunder i kø når det først er kødannelse. Dette fører til følgende optimeringsproblem:

Minimaliser Cj/x (kr per time) gi«

A —-------— /z(/x — A) xt

samt --------/x — A

1 zX —- (timer) 12 „

< 3

Siden A = 10 kunder per time og C] = kr 10 per kunde, får vi: Minimaliser 10/x (kr per time) => /x > 1 7,04 (kunder per time) ~ 10)

xt samt ----------/x- 10

=> /x s 15

(kunder per time)

228

KØTEORI

Mens både Hansen og Andersen oppfyller kravet til kødannelse, er det bare Andersen som opp­ fyller kravet til ventetid, og som derfor bør få stillingen. Imidlertid, hadde det kommet en søker som hadde kapasitet /jl = 18 kunder per time, ville han ha blitt tilbudt stillingen, idet han ville vært billigere og likevel oppfylt de totale servicekrav. Vi har med dette forsøkt å illustrere at selv om beslutningsunderlag foreligger i form av en komplett spesifikasjon av hvordan køsystemet vil oppføre seg, så er den konkrete beslutning avhengig av en avveining av denne oppførselen mot økonomiske faktorer som delvis er av sub­ jektiv art.

Oppgave 6.11 Hvilken søker bør få jobben dersom den gjennomsnittlige totaltid i systemet for en kunde ikke må overskride 10 minutter? Hvor hurtig bør den «optimale» ekspeditør arbeide? Oppgave 6.12

a) Verdsett kundekostnadene til kr 0,25 per time. Det er da grunn til å tro at det er optimalt å arbeide langsomt, selv om ventetidene skulle bli relativt store. Vis at selv Olsen nå er for rask, og at det optimale arbeidstempo er 10 -7 kunde per time.

b) Verdsett kundekostnadene til kr 250 per time. Vis at selv Andersen nå er for sen, og at det optimale arbeidstempo blir så høyt som 25,8 kunder per time. Oppgave 6.13 For en produksjonsprosess er to maskiner aktuelle, A og B. Maskin A koster 1 mill., maskin B koster bare 600 000. Til gjengjeld har maskin B bare 75 % av kapasiteten til A. Produksjonspro­ sessen kan betraktes som et MIMI\-system, og kapasitetsutnyttelsen til maskin A vil eventuelt bli på bare 50 %. Kapitalbinding antas å koste 25 % per år. Begge maskinene antas å ha en levetid på 1 år (ingen skrapverdi). En beregning av de totale kostnader knyttet til både maskinene og til kapitalbinding leder til at A og B vurderes likt. Hva er verdien av en «kunde», altså ett stk. «varer i arbeid»?

6.7 Køsystem med plassbegrensning

Vi har hittil forutsatt at køen i prinsippet kan bli uendelig lang. Det betyr at vi alltid far den samme bruttoinntekt per time, siden frafall ikke kan tenkes forekomme. La oss nå endre litt på denne forutsetningen. Plassen som er disponibel for kundene og kødannelsen, er begrenset. Vi kan forutsette at det maksimalt kan være 3 kunder foran gatekjøkkenet, iberegnet den kunden som ekspederes. Hvilken innflytelse far dette kravet på køsystemets oppførsel og økonomi? Det er klart at dersom køsystemet maksimalt kan ha R kunder totalt, og en kunde ankommer når det allerede er R, så blir denne kunden avvist og må kjøpe pølser et annet sted. Dette inne­ bærer tapt inntekt, og verdien på R er derfor av betydning. La oss først analysere køsystemets operative egenskaper når det er begrenset til R kunder. Vi kaller et slikt system foret A//Af/l/7?-system, i motsetning til det tidligere MIMI\- eller egentlig A//Å//l/°°-system siden vi ikke hadde begrensninger på kundetallet. Utledning av formelen følger samme fremgangsmåte som for MlM/\-systemet, men alle de­ taljer blir mer intrikate og overlates til spesielt interesserte. Det kan vises at sannsynligheten for at det er /jl kunder i dette systemet, er:

n = 0,1,...,/?

Legg merke til at utledningen ikke krever at — < 1. I dette tilfellet er det køsystemets kapasitet R som begrenser køen. Det forventede antall kunder i køsystemet blir nå: R

E(N) = X iPi = 1=0

Det kan vises at E (V) kan utvikles til:

A EW =

!-(/?+!)

A

R

+R

A R + lq

R + l-i

230

KØTEORI

Dersom — < 1 og 7? —> fJL

får vi E(N) = —som tidligere utledet for M/M/\-systemet /JL

Å

(kontroller). Det er nå spesielt interessant å studere hvor mange kunder gatekjøkkenet mister på grunn av plassmangel. Sannsynligheten for å miste en kunde er PR, fordi køsystemet er fullt en brøkdel PR av tiden. Vi har:

Vi må nå skille mellom ankomstintensiteten Å som representerer strømmen av kunder frem til køsystemet, og Acf-f som representerer den virkelige, effektive ankomstintensiteten, altså strøm­ men av kunder som virkelig får plass i køsystemet. Vi har:

Aeff — A Acff = 0

n=R

Skriver vi Acff = A(1 — PR), kan vi tolke den som den gjennnomsnittlige effektive ankomst­ intensiteten. Det kan vises at vi får disse uttrykkene for forventet antall kunder i kø E (Nq), for­ ventet ventetid E(JVq) og forventet totaltid E(W): Aeff E(Nq) = E(N) - — M

E(Wq) =

E (AJ

Acff

1 E(W) = E(Wq) + — /l

Oppgave 6.14 Kontroller følgende resultater (A =10 og R = 3) gjeme ved hjelp av regneark: Betjeningsintensitet /jl P0 P\ Pi Pi

n

Andersen 20

Hansen 15

Olsen 12

Pettersen 9

0 1 2 3

0,533 0,267 0,133 0,067

0,415 0,277 0,185 0,123

0,322 0,268 0,224 0,186

0,212 0,236 0,262 0,291

Vi ser at sannsynligheten for å finne køsystemet fullt er over fire ganger så stor for Pettersen enn for Andersen, enda sistnevnte arbeider bare litt over dobbelt så fort. Kontroller at vi også far

Andersen Hansen Olsen Pettersen

20 15 12 9

E(A) (kunder)

E(Nq) (kunder)

E(Wq) (min.)

E(W) (min.)

Aeff (kunder per time)

0,73 1,02 1,27 1,63

0,27 0,43 0,60 0,84

1,71 2,95 4,40 7,13

4,71 6,95 9,40 13,80

9,33 8,77 8,14 7,09

KØSYSTEM MED PLASSBEGRENSNING

231

Vi ser f.eks. at Andersen mister 6,4 % av kundene, til gjengjeld reduseres ventetiden fra 3 til 1,71 minutter. Pettersen mister 29,2 % av kundene, men er da i det minste i stand til å arbeide i gate­ kjøkkenet, noe han ikke var før. Oppgave 6.15 I et A//Å//l/6-køsystem forventes det å komme 8 kunder per time, og forventet betjeningstid er 5 minutter. Hva er

a) sannsynligheten for at det ikke er noen kunder i køsystemet? b) forventet kølengde? c) forventet ventetid?

Sammenlign med tilsvarende system uten plassbegrensning.

d) Hvor stor prosentdel av kundene blir avvist på grunn av plassmangel? Gjenta beregningene for et A//A//l/3-køsystem.

6.8 Køsystem med flere ekspeditører

Etter en omfattende analyse av gatekjøkkensystemet og de operasjonelle og økonomiske konse­ kvenser ved å ansette de forskjellige søkerne, faller valget på Hansen. Gatekjøkkenet kan altså karakteriseres som et MIMI\-system med Å = y kunde per minutt og fi = y kunde per mi­

nutt. Vi antar også at det ikke var aktuelt med plassbegrensning, og at kundene ikke kjenner begrepet utålmodighet. Hansen viser seg å leve opp til forventningene (!), det er gjennomsnittlig 2 kunder foran gate­ kjøkkenet, og de venter gjennomsnittlig 8 minutter. Kundene er fornøyd med Hansen, og rykter om gode pølser sprer seg. Resultatet er at kundestrømmen øker. Dette er vel og bra for den totale bruttoinntekten. Imidlertid øker også ventetiden kraftig, og det er klart at en uholdbar situasjon er i ferd med å oppstå. En økning av kundestrømmen på 50 % vil f.eks. medføre at køen vokser over alle grenser. I første omgang ønsker eieren derfor å finne hvor sterk kundestrømmen kan bli før den totale nettoinntekt begynner å synke pga. ventekostnader. Vi vet fra tidligere at nettoinntek­ ten er NI (/jl | A = konstant) = BX — TK (/jl | A = konstant)

= BX- Cxtx-C2--- -— /z - A der B — bruttoinntekt per kunde. (Vi forutsetter at ekspedisjonskostnader og ventekostnader per time er like store.) Vi kan nå oppfatte som gitt og finne optimal A. Altså blir inntektsfunksjonen NI(X | /jl = konstant). Det kan vises ved derivasjon at optimal kundestrøm blir:

•opt

M

C2 ---- M B

Benytter vi denne formelen, med B - kr 50 per kunde og C2 = kr 25 per time, finner vi Aopt =» 12,26 kunder per time. En økning av kundestrømmen utover ca. 22,6 % fra det nåværende nivå er altså ikke ønskelig.

Oppgave 6.16 Med A = 10 kunder per time ga Hansen en nettoinntekt på kr 300. Hva blir tilsvarende nettoinn­ tekt for A lik hhv. 12, 13 og 14 kunder per time? Hva blir optimal nettoinntekt?

Eieren overveier å erstatte Hansen med en raskere ekspeditør, men finner dette uriktig, det er Hansens personlige dyktighet som har økt kundestrømmen, og han bør ikke straffes for det. Dessuten kan tilsvarende problemer oppstå med en ny ekspeditør. Han far imidlertid en idé som

233

KØSYSTEM MED FLERE EKSPEDITØRER

synes lovende: Hvorfor ikke ansette en ekspeditør i tillegg til Hansen? Riktignok går da lønns­ kostnadene opp, men kapasitetsøkningen vil helt sikkert redusere ventekostnadene betydelig. Det forutsettes altså at flere ekspeditører arbeider med en felles kø, og at vi har det som kalles et AY/AZ/S-system, der S er antall ekspeditører. Vi kan fremstille systemet ved hjelp av en figur:

Kunder som er ferdigbetjent

betjenes

På samme måte som for MIMI\-systemet må vi nå analysere Af/Af/S-systemets operasjonelle egenskaper. Vi vil utvikle formler for tilstandssannsynligheter og forventninger som inneholder S i tillegg til A og /jl. Vi forutsetter at de 5 ekspeditørene er like raske, altså at: /JL, = M

i=

,S

Det kan vises følgende:

Tilstandssannsynligheter for et M/M/S-system:

234

KØTEORI

Forutsetningen for utledningen har vært at

Det må altså totalt hos S ekspeditører være kapasitet til å ta seg av kundestrømmen. Vi skal først vise at dette formelverket med S= 1 ekspeditør gir samme resultat som tidligere utviklet fra Å//Å//l-systemet. Vi far

= _______________ 1______________ /

1

. J____ Å

0! \ /z / =

1!

M ~ A

/z

m /i — A

= i _ A

/z — A + A

/z

som tidligere. Videre far vi for n > 1

som tidligere.

La oss benytte formelverket med 5 = 2 ekspeditører:

1 A2 /z

\ M 7

2ju — A

________ g(2g ~ A)________ /jl (2/i — A) + A (2/i — A) + A2 /i(2/i — A) /i(2/i + A)

_

/i(2/i - A) _______ - A)_____________ 2/i2 — Å/i + 2Å/i — A2 + A2

2/i — A 2/i + A

Videre får vi:

1 2"“ 1

n

1

n

2

235

KØSYSTEM MED FLERE EKSPEDITØRER

Oppgave 6.17 Sett opp de generelle formler for P„ som funksjon av A og /z dersom 5=3. La oss studere hva tilstandssannsynlighetene blir dersom kundestrømmen øker til A = 14 kunderpertime, /z= 15 kunder per time som før, og dersom 5 antar følgende forskjellige verdier 1, 2 og 3. Da far vi:

n

0 1 2 3 4 5 >6

Tilstandssannsynligheter Pn 5=2 5=3 S= 1

0,067 0,062 0,058 0,054 0,051 0,047 0,661

0,364 0,339 0,158 0,074 0,034 0,016 0,014

0,390 0,364 0,170 0,053 0,016 0,005 0,002

Tilstandssannsynligheter Pn for 1, 2 og 3 ekspeditører Vi ser at sannsynligheten for å finne køsystemet tomt eller sparsomt besøkt øker kraftig når systemets kapasitet to- eller flerdobles. Motsatt, det er bare med 1 ekspeditør at det er betydelig sannsynlighet for å finne mange kunder i systemet. Merk spesielt sannsynligheten for at en kunde må vente, dvs. P (V > 5). Disse er hhv. 0,933,0,297,0,077 og kan også regnes ut fra formelen:

P(N>S)

(5 - 1)! (5/z - A)

Også for MlMl5-systemet er det mulig å utlede formler for forventningsverdiene. Vi skal la detaljene ligge og bare presentere de viktigste formler:

Forventet antall kunder i kø, E (Nq):

E(Nq) =

(S-1)!(Sm-A)2

Forventet antall kunder i køsystemet, E (AO :

E(N) = E(Nq) + —

236

KØTEORI

Forventet ventetid, £(^):

£(^) =

W,,)

A

(S-1)!(SM-A)2

Forventet totaltid, E(IF):

= £(^) + —

Oppgave 6.18 a) Vis at S = 1 innsatt i formlene ovenfor gir de formler vi kjenner fra før i MIMI\-systemet.

b) Sett 5 = 2, og utled formlene. c) Finn E(Wq) for S = 2.

Anvender vi formlene på gatekjøkkensystemet, får vi følgende (A og /jc er hhv. 14ogl5kunder per time): Forventet antall kunder i køsystemet £(7V)

Forventet ventetid

Forventet ventetid

5

Forventet antall kunder i kø E(Nq)

E(Vty (min.)

E(IE) (min.)

1 2 3

13,067 0,260 0,035

14,000 1,193 0,968

56,000 1,114 0,148

60,000 5,114 4,148

Vi ser at de betydelige kø- og venteproblemene i M/M/\-systemet tilnærmet forsvinner allerede med 2 ekspeditører. En fordobling av køsystemets kapasitet fører til en ventetidsreduksjon på 98 %. Vi kan nå regne ut nettoinntekt som funksjon av antall ekspeditører:

S

Bruttosalg (kr)

Ekspeditørlønn (kr)

Eksp.- og vente­ kostnader (kr)

Netto­ inntekt (kr)

1 2 3

700,00 700,00 700,00

150,00 300,00 450,00

14-1 • 25 = 350,00 14 • 5,11/60 • 25 = 29,80 14-4,15/60-25 = 24,20

200,00 370,20 225,80

KØSYSTEM MED FLERE EKSPEDITØRER

237

Det optimale antall ekspeditører er 2. Med 1 ekspeditør er ventekostnadene svært store. En ut­ videlse fra 2 til 3 ekspeditører er imidlertid ikke lønnsomt, ventekostnadene som allerede er små, blir bare ubetydelig lavere, mens lønnskostnadene øker med 50 %. Vi kan fremstille nettoinntekten grafisk som funksjon av A for hhv. 1 og 2 ekspeditører. Nettoinntekt 500 t

-400 T

Oppgave 6.20 Forsøk å finne analytisk ved hvilken kundestrøm det er likegyldig om gatekjøkkenet benytter en eller to ekspeditører av Hansens kvalitet. Bruk figuren ovenfor til å kontrollere resultatet.

Dersom A øker gradvis, vil altså nettoinntekten synke fra og med A = 12,26 kunder per time inntil A - svaret på oppgave 20, da det lønner seg å ansette noen i tillegg til Hansen. Finnes det noen mulighet for å unngå dette? Av analysene ovenfor ser vi at køsystemet forbedrer sin operasjonelle oppførsel i oppsiktsvek­ kende grad ved innføring av en ekspeditør nr. 2. Dette skyldes egentlig to ting. For det første fordobler vi systemets kapasitet, og for det andre skaper vi større fleksibilitet ved at det er mulig for en kunde å få betjening umiddelbart, selv om det allerede foregår betjening i systemet (en ekspeditør ledig/en ekspeditør opptatt). Det kan være interessant å studere hva som skjer dersom vi bare skaffer oss fleksibilitet, men opprettholder den opprinnelige kapasitet og ekspeditørkostnad. La oss anta at det er mulig å erstatte Hansen midlertidig (han kan ha behov for ferie!) med to vikarer. De forlanger hver bare kr 75 per time, til gjengjeld er ikke deres arbeidstempo særlig høyt, de greier bare 7,5 kunder per time hver. Til sammen har disse to nå samme lønnskrav og samme totalkapasitet som Hansen. Systemet er imidlertid blitt mer fleksibelt, det må derfor bli mindre venting enn før.

Oppgave 6.21 Vis at forventet ventetid nå bare blir 16,1 minutter mot før 17,9 minutter, men at nettoinntekten blir kr 339,90, som fremdeles er lavere enn for Hansen.

6.9 Ikke-Markov ankomstog betjeningsprosesser

I det foregående har vi konsentrert oss om Markov-prosesser og utviklet et formelverk for køsys­ temer der både ankomst og betjening er av denne typen. Hva om forutsetningene for Markovprosesser ikke er til stede? Enten kan vi på teoretisk grunnlag betvile forutsetningene, eller vi kan ha et observasjonsmateriale over ankomster og betjeningstider som i histogramform ikke har noen særlig likhet med negative eksponensialfordelinger. Hvordan vil køsystemer med ikkeMarkov-prosesser oppføre seg? La oss f.eks. anta at en fem timers observasjonsperiode foran gatekjøkkenet ga dette tallmateri­ alet: Kunde nr.

Ankomst­ tidspunkt

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

0,50 34,89 69,23 78,61 82,14 82,19 84,02 85,70 88,31 90,44 92,19 107,77 133,94 139,44 140,34 144,12 145,41 157,12 163,94 169,17 172,78 175,25 175,68

Ankomstintervall

0,50 34,39 34,34 9,38 3,53 0,05 1,83 • 1,68 2,61 2,13 1,75 15,58 26,17 5,50 0,90 3,78 1,29 11,71 6,82 5,23 3,61 2,47 0,43

Betjeningstid

Kunde nr.

Ankomst­ tidspunkt

Ankomstintervall

Betjenings tid

5,09 2,56 2,85 2,79 0,60 2,14 5,54 2,39 4,48 3,11 5,72 2,74 1,31 8,37 2,58 6,72 9,45 4,55 6,26 5,47 4,30 6,71 4,13

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

176,32 177,79 179,25 180,51 180,58 183,26 189,88 199,03 206,59 209,83 211,05 215,45 229,85 231,71 245,58 252,84 270,21 272,13 277,37 284,85 296,02 296,20 299,91

0,64 1,47 1,46 1,26 0,07 2,68 6,62 9,15 7,56 3,24 1,22 4,40 14,40 1,86 13,87 7,26 17,37 1,92 5,24 7,48 11,17 0,18 3,71

4,94 5,67 2,14 4,43 2,86 4,48 4,55 5,58 1,63 0,81 5,85 1,93 6,30 4,04 3,91 2,05 7,52 5,02 2,49 3,36 1,29 2,40 3,17

IKKE-MARKOV ANKOMST- OG BETJENINGSPROSESSER

239

På samme måte som tidligere teller vi opp hvor ofte ankomstintervallet og betjeningstiden er 0-1 minutt, 1-2 minutter osv., og får følgende tabelloppstillinger og histogrammer:

Betjeningstid min.

Antall ganger

0- 1 1- 2 2- 3 3- 4 4- 5 5- 6 6- 7 7- 8 8- 9 9-10

2 4 12 4 9 8 4 1 1 1

Ankomstintervall min.

Antall ganger

Ankomstintervall min.

Antall ganger

0- 1 1- 2 2- 3 3- 4 4- 5 5- 6 6- 7 7- 8 8- 9 9-10 10-11 11-12 12-13 13-14 14-15 15-16 16-17 17-18

7 10 4 5 1 3 2 3 0 2 0 2 0 1 1 1 0 1

18-19 19-20 20-21 21-22 22-23 23-24 24-25 25-26 26-27 27-28 28-29 29-30 30-31 31-32 32-33 33-34 34-35

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2

240

KØTEORI

Minutter

Ingen av histogrammene støtter en antagelse om at vi har Markov-prosesser, dvs. negative eksponensialfordelinger. Ankomstintervallene synes å vise enda større spredning enn tidligere, med en større prosentvis forekomst av svært korte intervaller, men fordelingens hale er blitt lengre. Betjeningstidene derimot synes å vise mindre spredning enn tidligere, de minste tidene er for­ svunnet, samtidig som fordelingens hale er blitt kortere. Det synes som kundenes betjeningsbehov er mer homogent enn tidligere. Hvordan vil et system med samvirkning av to slike prosesser oppføre seg? Det er variasjonene i ankomstintervall og betjeningstid som skaper kø, jo større variasjoner, desto større køproblemer. De jevnere betjeningstidene reduserer problemene, mens de mer varierte ankomstintervallene øker dem. Hva blir den samlede virkning? Vi kan ikke besvare dette uten å gå nærmere inn på de enkelte prosesser som har generert tallmaterialet. I dette tilfellet kan det opplyses at ankomstintervallene følger en hypereksponensiell fordeling av grad 2, mens betjeningstidene følger en Erlangfordeling av grad 3 (£3). Dersom vi ikke på forhånd vet hva slags sannsynlighetsfordeling vi har med å gjøre, må vi forsøke å finne en fordeling som «passer best» med de observerte data. Vi må altså selv danne oss en modell av ankomstprosessen og betjeningsprosessen. La oss se på betjeningsprosessen foran. Det er teoretisk ingenting i veien for at den egentlig kan modelleres med en negativ eksponensialfordeling, men det er lite sannsynlig ut fra de få korte betjeningstider vi har observert. Bare en skikkelig hypoteseprøving kan hjelpe oss til å velge modell på en vitenskapelig måte. Det kan godt tenkes at både en E2- og en ^-fordeling som hypotese ville blitt beholdt ut fra de gitte data ovenfor. Det fører for langt å forfølge dette videre. Det kan imidlertid være interessant å drøfte når vi kan regne med å finne Erlang-fordelt be­ tjening. La oss anta at betjeningen egentlig består av to operasjoner i serie, med samme eks­

peditør. Anta at hver av operasjonene er Markov-fordelt med forventet betjeningstid —. Der­ med blir

1 ,

1

_ 1

—- H----- - — — fi fi p.

.dvs.

, 0

/z = 2p.

Det kan da vises (for komplisert å gjøre her!) at den samlede betjeningstid er Erlang-fordelt av grad 2.

241

IKKE-MARKOV ANKOMST- OG BETJENINGSPROSESSER

La oss anta at en fem timers observasjonsperiode foran gatekjøkkenet isteden ga følgende tallmateriale: Kunde nr.

Ankomsttidspunkt

Ankomst­ intervall

Betjenings­ tid

Kunde nr.

Ankomsttidspunkt

Ankomst­ intervall

Betjenings­ tid

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

6,47 12,40 19,08 25,05 31,96 37,25 40,70 46,22 52,41 56,03 59,80 66,41 71,94 79,86 85,76 89,57 94,84 100,66 106,42 110,42 114,71 121,94 127,02 131,54 136,12 141,92

6,47 5,93 6,69 5,97 6,90 5,29 3,45 5,52 6,19 3,62 3,77 6,61 5,53 7,93 5,89 3,81 5,27 5,83 5,76 4,01 4,29 7,23 5,08 4,53 4,58 5,80

7,99 0,01 1,42 0,49 6,06 1,71 7,29 0,91 7,89 0,62 0,95 2,00 6,15 0,05 1,46 0,54 6,38 6,77 1,15 1,66 1,51 0,12 0,82 7,50 7,41 1,60

27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

147,38 153,13 158,06 163,47 169,34 175,24 180,51 186,02 191,08 195,17 202,01 205,89 213,40 220,08 227,66 234,85 240,14 247,33 254,38 261,65 268,32 274,30 279,26 286,27 291,96 298,55

5,46 5,75 4,93 5,41 5,87 5,90 5,27 5,51 5,06 4,08 6,85 3,87 7,51 6,68 7,58 7,18 5,30 7,18 7,06 7,27 6,67 5,98 4,96 7,01 5,68 6,59

1,22 1,92 6,59 0,08 7,53 6,43 1,88 1,20 6,80 1,79 6,31 6,02 1,15 7,44 7,85 7,39 7,68 0,69 6,09 7,64 0,54 0,34 6,48 6,08 7,95 0,61

Tabelloppstilling og histogrammer over ankomstintervaller og betjeningstider blir som følger:

Ankomstintervall min.

Antall ganger

0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8

0 0 0 6 6 22 9 9

242

KØTEORI

Heller ikke disse histogrammene gir noe overbevisende forsvar for antagelse om Markov-pro­ sesser. Histogrammet for ankomstintervallene synes å ligne på en Erlangfordeling, men mer symmetrisk rundt en middelverdi, uten den skjevhet vi fant der. Histogrammet for betjenings­ tidene tyder på at vi ikke kan ha en én-toppet fordeling i det hele tatt, men en to-toppet fordeling. Hva slags hypotese ville du selv ha tatt utgangspunkt i for å modellere de to prosessene oven­ for? De faktiske forhold er at de to prosessene er som følger: Ankomstprosessen er her slik at det i utgangspunkt er et konstant tidsintervall lik 6 minutter mellom hver kunde. I tillegg er det et normalfordelt avvik med forventning 0 minutter og stan­ dardavvik a = 1 minutt. Alternativt kan vi oppfatte ankomstintervallet som normalfordelt med forventning -7 og standardavvik a, altså: A

/'(/; /z,

a) =

Normalfordelingen er egentlig definert for alle t, mens vi her nødvendigvis må ha t > 0. Vi har derfor, for å være presise, en venstreavkuttet normalfordeling. Dersom 2- > 3cr, er forskjellen imidlertid liten. Dersom vi finner at verken normalfordeling, negativ eksponensialfordeling, hypereksponensiell fordeling eller Erlangfordeling synes å beskrive prosessen, kan vi beskrive fordelingen em­ pirisk. Betjeningsprosessen er her følgende: Kundene består av to typer. Den ene typen har en uniformfordelt betjeningstid som er kort­ varig, mellom 0 og 2 minutter. Den andre typen har en uniformfordelt betjeningstid som er lang­ varig, mellom 6 og 8 minutter. Det er 50 % av hver kundetype. Forventningen er hhv. 1 og 7 minutter for hver type, og dermed 4 minutter totalt som før. Vi kan uttrykke dette som: /W =

00 At

som

eller

J(t) =

Dødsraten d (t) er altså befolkningsendringen i et meget lite tidsrom t, eller det vi kaller den deriverte av befolkningsfunksj onen N(f), på fortegnet nær. Når vi studerer endringer over tid, altså lar tiden t være den uavhengige variable, er det vanlig å erstatte skriveformen V'(t) med TV(t). Vi har gjort dette i den følgende fremstilling. Vi må nå beskrive den aktuelle dødsprosessen. Den vil naturligvis være situasjonsavhengig. La oss imidlertid gjøre en antagelse som synes fornuftig og anvendbar i mange situasjoner, nem­ lig at: Forholdet mellom dødsfall og befolkning er til enhver tid konstant, eller antall dødsfall er proporsjonal med befolkningen til enhver tid. Det betyr altså mer presist:

- Forholdet mellom dødsrate på et gitt tidspunkt, slik det er definert ovenfor, og befolkning på samme tidspunkt er en konstant d, dvs.: i/(t) , ,, N(t) ------ - = d eller N(t)--------------------- N(t)

, = k

ZJ -1 , Z. (der vi har satt k = — d)

eller:

N(t) = k • N(f)

der

kQ

Altså samme ligning som for fødselsprosessen, men med motsatt fortegn for k. Dermed blir løsningen på denne differensialligningen en eksponensialfunksjon med positiv eksponent:

N(t) = N(0) • e*

k>Q

H------------------------------------------- 1----------------------------------------

►

t

Konstanten k har som før benevning «per tidsenhet» og uttrykker nå befolkningens «forplantningstilbøyelighet». La oss beregne V(r) for forskjellige verdier av k>Q. Z(år)

£ = 0,1

£ = 0,2

£ = 0,5

0 1 2 3 4 5 6 7 8 9 10

1000 1105 1221 1350 1492 1649 1822 2014 2226 2460 2718

1000 1221 1492 1822 2226 2718 3320 4055 4953 6050 7389

1000 1649 2718 4482 7389 12182 20086 33115 54598 90017 148413

304

DETERMINISTISK SIMULERINGSMETODIKK

Vi får da følgende grafiske fremstilling, idet vi også har avmerket når befolkningen er fordoblet, hhv. etter t\ = ca. 1,5 år, t2 = ca. 3,5 år og t3 = ca. 7 år:

Analytisk løser vi dette på følgende måte:

A(0) • é’ = 2 - V(0) eller

= 2 In 2

kt = In 2

k Sammenligner vi med resultatene for dødsprosessen, ser vi at fordobling av befolkningen tar like lang tid som halvering for samme k verdi med motsatt fortegn.

Oppgave 8.3 Ta utgangspunkt i talleksemplene ovenfor, og finn når befolkningen er 25 % større enn og tre ganger så stor som den opprinnelige. Oppgave 8.4 Beregn N(t) for k - 0,05, 0,3 og 1,0 per år, og kontroller når befolkningen er fordoblet.

La oss lage et kausaldiagram for den befolkningsvekst vi har påvist ovenfor. Da får vi: 1) Befolkning påvirker fødselsrate i den forstand at jo større befolkningen blir, desto flere individer fødes, dvs. økning av befolkning medfører økning av fødselsrate. Dette kan uttrykkes grafisk som følger: Befolkning

Fødselsrate

305

BEFOLKNINGSMODELLER

2) Fødselsrate påvirker befolkning i den forstand at jo større fødselsraten blir, desto flere individer blir det, dvs. økning i fødselsrate medfører økning av befolkning:

Fødselsrate

Befolkning

Til sammen får vi følgende kausaldiagram:

।

Fødselsrate

W Befolkning

+

Symbolet + angir at vi har en positiv, lukket kausalløkke som gir akselererende vekst. Vi kan nå betrakte fødsels- og dødsprosessen i sammenheng gjennom det omforente kausaldia­ gram: Fødselsrate

C 1 < ) Befolkning

+

Dødsrate

+

Hvordan vil befolkningen nå utvikle seg over tid? Fremdeles har vi en differensialligning av fonnen: V(t) = k • N(t) Nå er k — «ettoendringsrate per tidsenhet og kan være negativ, null eller positiv. Løsningen blir analogt med tidligere:

V(t) = V(0) • e* Vi ser da at befolkningen vil være stabil lik 7V(0) bare når k = 0, dvs. fødselsrate og dødsrate er like. Hvis f> d, dvs. k > 0, blir det eksponensiell vekst, hvis f 0, d > 0

kan vi oppfatte konstantene f og d slik: f er «fødselstilbøyeligheten» (eg. forplantning) d er «dødstilbøyeligheten» (som en konsekvens av levealder)

Enheten er «antall fødte/døde per individ per tidsenhet», men det er vanlig i praksis å bruke formuleringer av type «antall fødte per år per 10 000 innbyggere» o.l. Nå er eksponensiell vekst i det lange løp umulig. Det er innlysende at en fødselsprosess som løper løpsk, før eller senere blir begrenset av forskjellige faktorer, f.eks. matmangel, plassbegrensning, forurensning o.l. Den modellen for befolkningsvekst vi har diskutert foran, kan såle­ des bare være en tilnærmelse til virkelige vekstprosesser.

Oppgave 8.5 a) Lag et tilsvarende kausaldiagram for sammenhengen mellom lager, produksjon og salg. b) Innfør en fjerde variabel, pris, og lag nytt kausaldiagram.

Oppgave 8.6 Utvid kausaldiagrammet for befolkningen ovenfor til å inneholde relevante eksogene konstanter (som altså ikke selv påvirkes av systemets oppførsel). Oppgave 8.7 Lag et tilsvarende kausaldiagram for realverdi av kapital, renter og verdiforringelse, med rente­ sats og inflasjonssats som eksogene konstanter.

8.1.2 Befolkningsmodell med veksthindring Den befolkningsmodellen vi har studert i forrige avsnitt, lider av en vesentlig svakhet: Dersom f> d, vil befolkningen vokse, og det er intet som stopper veksten; befolkningen går mot «uendelig». Dette kan naturligvis aldri inntreffe for virkelige befolkninger, det vil være forskjellige mekanismer som hindrer ukontrollert vekst. Verken f eller d vil være konstanter, men tvert imot funksjoner av systemets tilstand. Vi kan gi et enkelt eksempel på dette: Vi antar at fødselstilbøyeligheten er konstant som tidligere, men at dødstilbøyeligheten vokser proporsjonalt med befolkningens størrelse, altså at:

d = m •N Det er altså uforholdsmessig flere som dør når befolkningen er stor, enn når den er liten. Eksem­ pelvis, når befolkningen blir dobbelt så stor, blir dødsraten fire ganger så stor! Vi kan tenke oss at

DETERMINISTISK SIMULERINGSMETODIKK

307

levevilkårene for individene blir dårligere når det blir mange av dem, og at levealderen derfor synker. Det er klart at en slik forutsetning vil være veksthindrende, men hvordan? Denne modellen av befolkningsvekst får differensialligningen: = (f-

■ N(i)

f> 0, m> 0

Kan vi si noe om V(t) på grunnlag av ligningens form? Når befolkningen er liten, dvs. N(t) ~ 0, blir ligningen tilnærmet lik

N(f) = N(t) = V(0) •

som har løsningen altså eksponensiell vekst.

Når befolkningen er nær forholdet

, medfører dette at N(f) ~ 0, dvs. veksten har stoppet!

Funksjonen N(t) må følgelig se omtrent slik ut:

Det er mulig å løse denne differensialligningen analytisk, og resultatet blir:

N(t) =

f- W) • f+ m • Af(O) • (/' - 1)

Dette kalles også for logistisk vekst, og modellen kan også benyttes til å beskrive epidemier, spred­ ning av et rykte, salg av nye produkter mv. La oss ta et talleksempel der vi velger V(0) = 1000. Vi setter f= 0,12 per år og m = 0,000006 per år. Det betyr altså at dødsraten d initielt er 0,006 per år, altså liten i forhold til fødselsraten f Da skal befolkningen stabilisere seg på nivået fim =

308

DETERMINISTISK SIMULERINGSMETODIKK

0,12/0,000006 = 20 000. La oss kontrollere dette, idet vi for sammenligningens skyld også har presentert ren eksponensiell vekst (m = 0); og vi har rundet av til hele tall: (år)

N(t), (m > 0)

0 1 2 3 4 5 6 7 8 9

1000 1120 1254 1403 1568 1750 1952 2173 2417 2684

1000 1127 1271 1433 1616 1822 2054 2316 2612 2945

10 20 30 40 50 60 70 80 90 100

2975 7343 13165 17296 19100 19720 19915 19974 19992 19998

3320 11023 36598 121510 403429 1339431 4447067 14764782 49020801 162754791

N(i), (m = 0)

Dette gir følgende graf:

Befolkn

Logistisk vekst

Tid i år

309

BEFOLKNINGSMODELLER

Vi kan også sammenligne hvordan forskjellige verdier av m influerer på befolkningsveksten. La oss f.eks. sette V(0) = 1000, f = 0,48 og la m ha verdiene: 0,000016, 0,000024, 0,000048 og 0,000096. Da får vi følgende grafer:

Oppgave 8.8 Kontroller at formelen for logistisk vekst er riktig ved derivasjon, samt utregning av differensial­ ligningens høyre side, og vis at uttrykkene blir identiske.

La oss studere hvordan et slikt system kan simuleres. La oss velge 7V(0) = 1000, f= 0,12 per år, m = 0,000006 per år. Altså skal N gå mot 20 000 når t går mot uendelig. Vi husker den grunnleggende tilnærmelsen som simulerer systemets oppførsel over tid: N(t + At) « V(t) + At -Å(t)

La oss velge f.eks. At = 1 år. Vi må da beregne N(t + 1) « N(t) +N(t) der

Å(t) = (f-

■ N(f)

t = 1, 2, 3,...

310

DETERMINISTISK SIMULERINGSMETODIKK

Vi starter med å beregne V(0). Deretter beregner vi V(l) som gir oss mulighet til å beregne V(l) osv. Vi beregner altså vekselvis N(t) og N(t + 1). Vi får: t

N(t + 1)

7V(t)

(0,12 (0,12 (0,12 (0,12

0 1 2 3 osv.

-

0,000006 0,000006 0,000006 0,000006

■ • • ■

1000) • 1000 = 114 1114) • 1114 = 126,234 1240,234) ■ 1240,234= 139,599 1379,833) • 1379,833) = 154,156

1000 + 114 = 1114 1114 + 126,234 = 1240,234 1240,234 + 139,599 = 1379,833 1376,833 + 153,846 = 1533,989

Det kan være interessant å studere hvordan verdien til At påvirker nøyaktigheten av simuleringsresultatene. Vi har valgt At så lav som 0,1 måned og så høy som 20 år, i tillegg til At = hhv. 1 måned, 1 år (som presentert ovenfor) og 10 år. Resultatene er sammenlignet med de eksakte verdier beregnet ut fra formelen for V(t). Vi har rundet av alle resultater til nærmeste hele tall.

Vi får: Eksakt formel

t

*'=77

At= 1

At= 10

At = 20

1000

0 1 2 3 4 5

1000 1120 1254 1403 1568 1750

1000 1120 1254 1403 1567 1750

1000 1120 1253 1401 1565 1746

1000 1114 1240 1380 1534 1704

1000

10 20 30 40 50 60 70 80 90 100

2975 7343 13165 17296 19100 19720 19915 19974 19992 19998

2974 7339 13162 17295 19100 19720 19915 19974 19992 19998

2963 7306 13130 17285 19101 19722 19916 19975 19992 19998

2837 6916 12732 17160 19107 19742 19927 19980 19994 19998

2140 4433 8573 14451 19262 20114 19976 20004 19999 20000

3280 9861 21859

16983 23131

Vi ser at verdien til At har stor betydning. Prinsipielt skulle vi naturligvis hatt At «uendelig liten», men i praksis er det vårt behov for nøyaktighet som setter krav til At. Vi må f.eks. være klar over at beregningene for At1 =-7 — tar 120 ganger så lang tid som for At = 1. Er dette verdt 120 । bryderiet? Vi ser at for At = er maksimal feil (for t = 20) bare ca. 0,05 %, for At = — ca. 0,5 %, for At =1 ca. 6 %. Det er helt klart at At — 1 er for mye, N varierer da altfor mye i intervallet V(t) til N(t + At) til å gi gode resultater. Legg også merke til at simuleringsmetodikken i dette eksemplet får komplett sammenbrudd for store At verdier. For At = 10 blir ikke resultatene bare svært dårlige, vi ser dessuten at det for store t inntreffer tendenser til svingninger rundt 20 000. Når At = 20 blir dette helt tydelig; det er åpenbart at vi ikke lenger «etterligner» befolkningsvekstsystemet slik som hensikten var.

311

BEFOLKNINGSMODELLER

Vi har nå fatt en grunnleggende innsikt i hvordan simulering av denne type systemer foregår. Vi ser hvordan vi i prinsippet kan foreta håndregning av simuleringen (håndsimuleringer), men at dette er meget tidkrevende. Det er derfor i praksis nødvendig med dataverktøy.

Oppgave 8.9 a) Beregn 7V(z) for funksjonen foran med følgende verdier:

V(0) = 1500 V(0) = 1500 V(0) = 1500 V(0)=1000

/=0,15 f= 0,30 f= 0,30 /= 0,30

m m m m

= = = =

0,0000048 0,0000048 0,000006 0,000006

Tegn løsningene inn i samme graf. b) Velg det første alternativet ovenfor. Simuler løsningen av differensialligningen for forskjel­ lige verdier av Az, og studer nøyaktigheten.

Vi skal nå studere noen befolkningsmodeller under mer kompliserte forutsetninger for å bedre bakgrunnen både i modellutvikling og i selve simuleringsteknikken.

8.1.3 Konkurransemodellen La oss nå anta at vi har to befolkninger, f.eks. to dyrearter som lever i det samme miljø. Dersom artene ikke har noen påvirkning på hverandre, vil deres utvikling kunne beskrives av to uavhen­ gige differensialligninger. Det kan f.eks. tenkes at veksthindringsmodellen i foregående avsnitt. Å(z) = (f-

■ N(f)

er relevant for begge artene. Vi kan da sette opp ligningene M(z) = (/i-m^JzB-Vjz) Å2W = {fl ~ m2N2 (z)) • N2 (z)

som kan løses eller simuleres hver for seg. Anta imidlertid at artene påvirker hverandre, og slik at jo flere det blir av den ene arten, desto større dødelighet blir det hos den andre. Vi kan da modifisere ligningene ovenfor med hvert sitt tilleggsledd M (0 = (/i -

(0 - «1^2 (0) • M (z)

N2 (z) = (f2 - m2N2 (z) - n2N} (z)) • N2 (z)

og n2 er konstanter som angir hvor sterk påvirkningen er. Dersom ii\ = n2 = 0, er det f fi ingen gjensidig påvirkning, og hver av artene når sitt eget stabile nivå gitt ved hhv. —— og----- . Wi rn2

der

312

DETERMINISTISK SIMULERINGSMETODIKK

Vi har da to simultane differensialligninger som må løses samtidig. Som talleksempel, la oss som befolkning 1 velge eksemplet foran med: ni\ = 0,000006

N] (0) = 1000 f = 0,12 per år

La oss som befolkning 2 velge jV2(0)

= 1500 f2 = 0,15 per år m2 = 0,0000048

(I en virkelig analyse må disse parametrene bestemmes ut fra de faktiske forhold vedrørende reproduksjon og dødelighet. Det fører for langt å forsøke dette her.) La oss nå velge n} 0 og n2 =# 0, slik at artene påvirker hverandre. Med n । = 0,0000096 per

II

II II

a S

II

S

år og n2 = 0,000009 per år far vi følgende resultater (simulert med Ar = 0,1 mnd = -pp- år):

Befolkning 1 1000 0,12 0,0000060 0,0000096 Ar =

i

Befolkning 2 1500 0,15 0,0000048 0,0000090

, ar

/ (år)

MW

MW

0 1 2 3 4 5 10 20 30 40 50 60 70 80 90 100

1000 1103 1214 1331 1455 1583 2262 2893 1796 593 129 23 4 1 0 0

1500 1713 1952 2220 2518 2846 5035 11900 19921 26293 29610 30795 31135 31222 31243 31248

Vi ser altså at den første arten dør ut!

313

BEFOLKNINGSMODELLER

Hva om koblingen mellom artene blir mindre sterk, f.eks. n\ = 0,0000024 per år og «2 = 0,000003 per år? Da får vi følgende:

II

a

II

II

=

II

Befolkning 2 1500 0,15 0,0000048 0,0000030

Befolkning 1 1000 0,12 0,0000060 0,0000024 St =

/(år)

MW

MW

0 1 2 3 4 5 10 20 30 40 50 60 70 80 90 100

1000 1116 1245 1384 1538 1706 2769 5706 8095 9165 9565 9737 9828 9884 9921 9946

1500 1724 1978 2266 2590 2955 5482 13803 21241 24251 25017 25146 25133 25100 25070 25049

I dette tilfellet blir det altså fredelig sameksistens mellom de to artene!

314

DETERMINISTISK SIMULERINGSMETODIKK

Simuleringen foregår på følgende måte: Vi skriver analogt med tidligere:

Ni (z + Az) « V, (z) + Az - TV] (z) V2(z + Az) « V2(z) + Az-V2(z)

Dermed kan vi begynne beregningene, idet vi f.eks. setter Az = 1 år:

Z = 0:

V,(0)=1000

N2(O)=15OO

315

BEFOLKNINGSMODELLER

Dermed blir:

TV, (0) = = = N2 (0) = = =

(/i - m.N. (0) - n}N2 (0)) • TV, (0) (0,12 - 0,000006 • 1000 - 0,0000024 • 1500) • 1000 (0,12 - 0,006 - 0,0036) • 1000 = 110,4 (f2 - m2N2 (0) - n2Nx (0)) • N2 (0) (0,15 - 0,0000048 • 1500 - 0,000003 • 1000) • 1500 (0,15 - 0,0072 - 0,003) -1500 = 209,7

Herav:

/ = 1:

TV,(1) « 1000 + 110,4 = 1110,4 TV2(1) « 1500 + 209,7 = 1709,7

TV, (1) = = TV2(1) = =

(0,12 (0,12 (0,15 (0,15

-

0,000006 • 0,0066624 0,0000048 0,0082065

1110,4 - 0,0000024 • 1709,7) • 1110,4 - 0,0041032) • 1110,4 « 121,3 • 1709,7 - 0,000003 • 1110,4) • 1709,7 - 0,0033312) • 1709,7 « 236,7

Herav:

t = 2:

TV, (2) « 1110,4 + 121,3 = 1231,7 N2(2) « 1709,7 + 236,7 = 1946,4

Sammenlignet med resultatene for At = 0,1 mnd., altså 120 ganger flere beregninger per år, ser vi at resultatene våre har en riktig tendens, men er for unøyaktige. Annet var vel ikke å vente. Prinsippet i beregningene er imidlertid greit nok. Et lite moment i forbindelse med selve modellen: Vi har konstatert to helt forskjellige typer oppførsel av systemet ut fra forskjellige valg av h, og n2. Noe mer vet vi imidlertid ikke, og det ville være en tidkrevende oppgave å variere parametrene med sikte på en dypere innsikt. Dette kan bare matematisk analyse gi, og dette systemet kan faktisk langt på vei analyseres. Det viser seg at dersom

n, n2 < m, m2 nxn2 > mxm2

kan artene leve sammen vil den ene arten knekke den andre.

Dette motsies ikke av simuleringene ovenfor.

Oppgave 8.10 Tegn et kausaldiagram for samlivet mellom disse to dyreartene.

316

DETERMINISTISK SIMULERINGSMETODIKK

8.1.4 Rovdyr-byttedyrmodellen En annen interessant befolkningsmodell er følgende: Vi antar at vi har et system med to arter, rovdyr og byttedyr, og at - dersom det ikke er noen rovdyr, vil byttedyrbefolkningen vokse ubegrenset - dersom det ikke er noen byttedyr, finnes det ikke mat til rovdyrbefolkningen som dermed vil dø ut

Vi setter: V] (z) = befolkning av byttedyr V2 (z) = befolkning av rovdyr Da vil hhv. den første og den andre av følgende to differensialligninger beskrive hva som skjer:

y (z) = n • y(z)

v2(z) = -r2-v2(z)

der f| og r2 er positive konstanter. Dersom begge befolkninger er i systemet samtidig, antar vi at

- beskatningen (dødsprosessen) av byttedyrene er proporsjonal med antall rovdyr tilveksten (fødselsprosessen) av rovdyrene er proporsjonal med antall byttedyr (mattilførselen)

Dermed kan vi sette opp de simultanc differensialligningene M(Z) = M (/) = («2^1 (6 ~ Z2) •

N2 (t)

der n} og n2 er positive konstanter. Hva slags oppførsel har nå dette systemet? La oss f.eks. velge n = 0,012 per mnd., r2 = 0,008 per mnd., h, = 0,000005 per mnd. og n2 = 0,000004 per mnd. La oss først velge y (0) = 2000, N2 (0) = 3000, deretter V, (0) = 5000, N2 (0) = 500 og

foreta simuleringer med T = 0,1 mnd=

for hvert femte år):

år. Da får vi følgende tabeller (utskrift av resultater

317

BEFOLKNINGSMODELLER

r= n=

Byttedyr 2000 0,1440000 0,0000600

Rovdyr 3000 0,0960000 0,0000480

Byttedyr 5000 0,1440000 0,0000600

Rovdyr 500 0,0960000 0,0000480

'(år)

MW

^2 W

mw

Aa2(0

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135 140 145 150

2000 1691 1519 1490 1589 1800 2095 2407 2607 2564 2276 1911 1632 1497 1502 1631 1867 2176 2475 2625 2512 2185 1829 1583 1484 1522 1680 1940 2257 2534 2625

3000 2884 2616 2316 2068 1918 1892 2010 2279 2638 2928 2994 2827 2539 2246 2019 1897 1906 2063 2365 2725 2971 2972 2762 2463 2180 1976 1885 1929 2126 2456

5000 7957 6038 1273 328 164 136 156 220 354 616 1124 2096 3893 6768 8096 2646 536 203 138 140 183 281 476 854 1582 2958 5379 8253 5252 1029

500 1472 5903 7939 5757 3760 2408 1542 997 659 457 346 311 387 842 3466 8068 6790 4541 2921 1867 1200 784 530 382 314 329 541 1754 6626 7787

W) =

318

DETERMINISTISK SIMULERINGSMETODIKK

Vi får følgende grafer:

år

Grafene er bemerkelsesverdig forskjellige. I begge tilfeller oppstår det svingninger i befolk­ ningene, men mens det ene tilfellet har rolige, symmetriske svingninger av den typen vi kjenner som sinus/cosinus funksjoner, har det andre tilfellet symmetriske svingninger karakterisert ved en voldsom vekst og tilsvarende kollaps, og et lengre tidsrom der befolkningene ligger på et lavt nivå. Periodelengden ser heller ikke ut til å være den samme; ca. 55 år i det første tilfellet, ca. 70 år i det andre tilfellet.

319

BEFOLKNINGSMODELLER

La oss ta en tredje simulering med Vj (0) = 2000, N2 (0) = 2400. Da far vi: t år

MW

0 1 5 25 100

2000 2000 2000 2000 2000 osv.

2400 2400 2400 2400 2400

Befolkningen er altså i dette tilfellet i stabil likevekt! Vi kan illustrere befolkningsendringene i en ny graf, der vi setter N} langs den horisontale akse og N2 langs den vertikale akse. Vi kan da tegne systemets oppførsel som en lukket kurve i -A^-planet, også kalt fasediagranv.

Selv relativt enkle modeller av typene illustrert ovenfor, gir altså opphav til meget komplisert oppførsel. Vi ser klart behovet for simuleringsteknikk for å kunne studere slike systemers opp­ førsel.

320

c DETERMINISTISK SIMULERINGSMETOD1KK

Oppgave 8.11 Ta utgangspunkt i rovdyr-byttedyr-modellen foran. Anta samme verdier for f , f2, , r2, som før. Anta også at A(0) = 5000 og TV (0) = 500 som ved en av de analyser som ble presentert. Vi innfører nå en jeger i systemet! Simuler hva som hender dersom jegeren skyter rovdyr i et antall av x dyr per måned. Start med x = 5, studer hva som hender, og velg deretter selv for­ skjellige x-verdier. Det er ønskelig at du bruker dataverktøy til å løse denne oppgaven, f.eks. regneark. Da velger du selv simuleringenes lengde og nøyaktighet. For dem som likevel måtte foretrekke håndregning, foreslås simulering over 25 år med et tidsintervall på 1 år. Dette blir ganske unøyaktig, noe du selv bør påvise. Det er viktig med gode grafiske fremstillinger av hvordan de to befolkningene utvikler seg over tid. Vurder når modellen er brukbar.

8.2 Økonomiske modeller

Innenfor økonomisk teori finner man mange modeller som uttrykkes ved differensligninger. Mo­ dellene beskriver hvordan tilstanden i et økonomisk system på tidspunkt t kan uttrykkes ut fra kjennskap til tilstanden på tidspunkt t - 1. Disse modellene er beskrivelser av en forenklet øko­ nomisk virkelighet. Beslutninger av et stort antall aktører blir beskrevet som kontinuerlige pro­ sesser ved hjelp av differensialligninger. Disse blir gjort diskrete for å lette den matematiske analyse og de numeriske beregninger. Modellene kan også ta direkte utgangspunkt i at beslut­ ningene ofte faktisk tas på utvalgte tidspunkter, og at det «ikke hender noe av betydning» mellom t - 1 og t. Vi skal i denne boken bare gi et par illustrasjoner av hvordan slike økonomiske modeller kan se ut, og hva slags løsninger vi kan vente å få. Noen diskusjon om hvor realistiske disse modellene er, vil ikke finne sted.

8.2.1 En enkel markedsmodell Vi antar at vi har et marked der det til ethvert tidspunkt er balanse mellom tilbud L og etter­ spørsel E av en vare, dvs.:

Lt = Et Etterspørselen vil være avhengig av varens pris P, og slik at etterspørselen synker når prisen øker. Vi kan modellere en enkel lineær sammenheng:

Et - a — bPt der a og b er positive konstanter. a sier hvor stor etterspørselen vil være når prisen er null, og b sier hvor mye etterspørselen synker når prisen økes med én enhet. Tilbudet L vil også være avhengig av varens pris P, og slik at tilbudet øker når prisen øker, motivert av at de som tilbyr varen, ser større fortjenestemuligheter. Vi kan modellere dette enkelt slik:

Lt = c + dPt der d er en positiv konstant, mens c både kan være positiv og negativ, c sier hvor stort tilbudet vil være når prisen er null, og d sier hvor mye tilbudet øker når prisen øker med én enhet. (Normalt antas ligningen ovenfor å være interessant bare over en minstepris større enn null, c får derfor bare en geometrisk betydning for å fastslå hvor tilbudsligningen ligger.)

322

DETERMINISTISK SIMULERINGSMETODIKK

Siden det er balanse i markedet vil a — bPt = c + dPt

ci — c eller Pt — ■■ som vi kaller likevektsprisen.

La oss f.eks. velge konstantene a = 500

c = -200

b = 2000

d = 1500

Dermed får vi p = 500 -(-200) ' 2000 + 1500

=

7 35

= Q2 —

som gir likevekten

E, = 500 - 2000 • 0,2 = 100 Lt = -200 + 1500 • 0,2 = 100 Nå vil imidlertid tilbudet ofte være knyttet til prisen på et tidligere tidspunkt, idet det tar tid å produsere varen. Dette kan vi uttrykke slik:

Lt = c + dPt _ ]

Dermed får vi av ligningen Lt = Et at a-bPt = c + dPt _ ]

Dette er en differensligning for prisen:

b

b

I talleksemplet ovenfor får vi

p =

1500 p 2000

!

500 ~ (-200) 2000

eller

3 7 Pt =------ Pt-i +----- = -0,75Pz_ ! + 0,35 4 20

Anta nå at Po, altså prisen på tidspunkt null, er den likevektsprisen vi fant tidligere, altså Po = 0,2. Da får vi:

Pi = -0,75P0 + 0,35 = -0,15 + 0,35 = 0,2 P2 = -0,75^ + 0,35 = -0,15 + 0,35 = 0,2 osv.

323

ØKONOMISKE MODELLER

Hvis markedet opprinnelig er i likevekt, blir altså denne likevekten opprettholdt. Men hva om Po * 0,2? Anta f.eks. Po - 0,3. Da får vi:

Tid

Pris

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0,3000 0,1250 0,2563 0,1578 0,2316 0,1763 0,2178 0,1867 0,2100 0,1925 0,2056 0,1958 0,2032 0,1976 0,2018 0,1987 0,2010 0,1992 0,2006 0,1996 0,2003

°’30

Pris

0,05

0,00 ------------ 1------------ 1------- —।------------- 1------------ 1----------- ’------------ ’------------ '----------- '------- —1 0 2 4 6 8 10 12 14 16 18 20

t

Vi ser at prisen svinger rundt likevektsprisen, men at utslagene blir mindre etter hvert som tiden går; vi har dempede svingninger. La oss velge et annet talleksempel. Vi setter a = 500, b - 2000, c = —200 og d = 2200, altså som i det forrige eksemplet, men med større verdi på d. Da blir

p _ '

2200 p 2000

!

500 -(-200) 2000

11 p 10 ’

1

+ _7_ 20

324

DETERMINISTISK SIMULERINGSMETODIKK

Med Po — 0,3 far vi; Tid

Pris

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0,3000 0,0200 0,3280 -0,0108 0,3619 -0,0481 0,4029 -0,0932 0,4525 -0,1477 0,5125 -0,2137 0,5851 -0,2936 0,6730 -0,3903 0,7793 -0,5073 0,9080 -0,6488 1,0637

I dette tilfellet får vi også svingninger, men utslagene blir større etter hvert som tiden går; vi har eksplosive svingninger. Hvorfor oppfører disse to systemene seg så vidt forskjellig? Vi ser her ulempene med en simu­ lering; vi finner oppførselen til akkurat dette systemet, men det er ikke så lett å fa større innsikt i slike systemer generelt. A forutsi effekten av en parameterendring på systemet ut fra tidligere simuleringer er slett ikke alltid enkelt: En teoretisk utledning derimot gir generelle formler, hvor det er mye lettere å se effekten av parameterendringer. I vårt tilfelle kan vi løse differensligningen eksplisitt, og det kan vises at vi far:

P, =

\

b ) \

b+d)

+

b+d

Vi kan kontrollere dette ved å se om uttrykket for Pt passer i ligningen

325

ØKONOMISKE MODELLER

Høyresiden blir da:

/ d\ \ -----b• /

/ a—c \ a — c "I \Pb---------b + d )+--------b+dJ

F/ d

I------[\ b /I

( \

d \z / p a — c\ b / \ ° b+d)

d(a~c)^a — c b(b + d) b

-( \

d \‘ ( p a~c\ b / \ ° b+d)

a—c / b \

1 c) et = 6 t>1 d) = 4, e2 = 5, e3 = 6, et — 3 t >4 e) et = 3 + t r>I

Oppgave 8.14 Analyser fem uavhengige problemstillinger tilknyttet systemet ovenfor:

a) Det er mulig at en annen handlingsregel kan gi systemet en annen oppførsel. Man kan f.eks. forsøke å jevne ut virkningen av etterspørselsendringer ved å benytte gt = y (G + G - i) - (4~0)

Simuler dette lenge nok til å kunne konstatere at resultatet i hvert fall ikke blir bedre. b) Simuler hva som hender dersom etterspørselen plutselig antar periodiske variasjoner, f.eks. slik at:

e2

~ e5 = e9 = G3 = e6 = eI0 =

£3

=