Document

Report
Managerial Decision
Modeling
Cliff Ragsdale
6. edition
Chapter 2
Introduction to Optimization
and Linear Programming
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
1
Innledning
Alle står overfor beslutninger om hvordan en skal
utnytte begrensede ressurser, som:
- Naturressurser, som oljereserver
- Areal
- Tid
- Penger
- Ansatte
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
2
Matematisk programmering
MP er et fag i operasjonsanalyse som finner den
optimale eller mest effektive måten å utnytte
begrensede ressurser; for å oppnå målsettingen til et
individ eller en organisasjon.
m.a.o. Optimering
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
3
Anvendelser av Matematisk Optimering
Bestemme produksjonsmiks
Produksjonsplanlegging
Ruteplanlegging og logistikk
Finansiell planlegging
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
4
Karakteristika for optimeringsproblemer
Beslutninger
- Handlingsvariabler
Restriksjoner
- Begrensninger
Målsetting
- Målfunksjon
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
5
Generell form på et optimeringsproblem
MAX (eller MIN): f0(X1, X2, …, Xn)
Slik at :
f1(X1, X2, …, Xn)<=b1
:
fk(X1, X2, …, Xn)>=bk
:
fm(X1, X2, …, Xn)=bm
Merk: Hvis alle funksjonene i et optimeringsproblem er lineære,
så er problemet et lineært programmeringsproblem (LP).
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
6
Generell form på et Lineært
Programmeringsproblem (LP)
MAX (eller MIN): c1X1 + c2X2 + … + cnXn
Slik at:
a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn >= bk
:
am1X1 + am2X2 + … + amnXn = bm
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
7
Eksempel på et LP Problem
Blue Ridge Hot Tubs produserer to typer
varmtvannsberedere : Aqua-Spas & Hydro-Luxes.
Data
Pumper
Arbeid
Rør
DB/pr. stk
Aqua-Spa
1
Hydro-Lux
1
9 timer
12 dm
$350
6 timer
16 dm
$300
Det er 200 pumper, 1566 arbeidstimer, og 2880 dm rør
tilgjengelig.
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
8
5 trinn i formulering av LP modeller:
1. Forstå problemet.
2. Identifiser beslutningsvariablene.
X1=antall Aqua-Spa produsert
X2=antall Hydro-Lux produsert
3. Angi målfunksjonen som en lineær kombinasjon av
beslutningsvariablene.
MAX: 350X1 + 300X2
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
9
5 trinn i formulering av LP modeller:
4. Angi restriksjonene som lineære kombinasjoner av
beslutningsvariablene.
1X1 + 1X2 <= 200
} pumper
9X1 + 6X2 <= 1566
} arbeid
12X1 + 16X2 <= 2880 } rør
5. Identifiser eventuelle øvre og nedre grenser på
beslutningsvariablene.
X1 >= 0
X2 >= 0
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
10
LP Modellen for Blue Ridge Hot Tubs
Max 350X1 + 300X2
S.T.:
1X1
+ 1X2 <=
9X1
+ 6X2 <= 1566
12X1
16X2 <= 2880
X1
BØK350 OPERASJONSANALYSE
200
>=
0
X2 >=
0
Rasmus Rasmussen
11
Løsning av LP problemer:En intuitiv innfallsvinkel
Idé: Hver Aqua-Spa (X1) skaper det største dekningsbidraget
($350), produser derfor så mange som mulig!
Hvor mange kan vi produsere?
La X2 = 0
1. restriksjon:
2. restriksjon:
3. restriksjon:
1X1 <= 200
9X1 <=1566 eller X1 <=174
12X1 <= 2880 eller X1 <= 240
Hvis X2=0, så er den største mulige verdien av X1 lik 174 og
totalt dekningsbidrag er $350*174 + $300*0 = $60,900
Denne løsningen er mulig, men er den optimal? NEI!
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
12
Løsning av LP problemer:En grafisk innfallsvinkel
Restriksjonene i et LP problem definerer et
mulighetsområde.
Det beste punktet i mulighetsområdet er den
optimale løsningen av problemet.
For LP problemer med 2 variabler er det lett å plotte
mulighetsområdet og finne den optimale løsningen.
En akse for hver variabel
En linje for hver restriksjon
En linje for målfunksjonen
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
13
Tegne restriksjonene
Vi må gjøre ulikhetene om til likheter for å kunne
tegne restriksjonene.
For bruk av pumper må vi gjøre om:
1·X1 + 1·X2 ≤ 200  1·X1 + 1·X2 = 200
Om vi bare har X2 på venstre side får vi:
1·X2 = 200 – 1·X1  X2 = 200/1 – 1/1·X1
Vi får dermed: X2 = 200 – 1·X1
Dette kan vi tegne inn i et diagram.
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
14
Plotte den første restriksjonen
Bruk av pumper: X2 = 200 – 1·X1
X2
X1 ≥ 0
200
X1 = 0  X2 = 200 (punkt på Y-aksen)
X2 = 0  200 – 1·X1 = 0  1·X1 = 200  X1 = 200/1 = 200 (punkt på X-aksen)
Bruk av pumper:
1·X1 + 1·X2 = 200
Bruk av pumper:
1·X1 + 1·X2 ≤ 200
200
BØK350 OPERASJONSANALYSE
X2 ≥ 0
X1
Merk ikke-negativitet:
X2 ≥ 0
Rasmus Rasmussen
15
X2
261
Plotte den andre restriksjonen
Bruk av arbeid: 9X1 + 6X2 = 1566
X1 = 0  6X2 = 1566  X2 = 1566/6 = 261 (punkt på Y-aksen)
X2 = 0  9X1 = 1566  X1 = 1566/9 = 174 (punkt på X-aksen)
Bruk av arbeid:
9X1 + 6X2 = 1566
Bruk av arbeid:
9X1 + 6X2 ≤ 1566
174
BØK350 OPERASJONSANALYSE
X1
Rasmus Rasmussen
16
X2
261
200
Felles mulighetsområde
Område som tilfredsstiller
begge restriksjonene
Bruk av arbeid:
9X1 + 6X2 = 1566
Bruk av pumper:
1·X1 + 1·X2 = 200
174 200
BØK350 OPERASJONSANALYSE
X1
Rasmus Rasmussen
17
X2
Plotte den tredje restriksjonen
Bruk av rør: 12X1 + 16X2 = 2880
X1 = 0  16X2 = 2880  X2 = 2880/16 = 180 (punkt på Y-aksen)
X2 = 0  12X1 = 2880  X1 = 2880/12 = 240 (punkt på X-aksen)
180
Bruk av rør:
12X1 + 16X2 = 2880
Bruk av rør:
12X1 + 16X2 ≤ 2880
240
BØK350 OPERASJONSANALYSE
X1
Rasmus Rasmussen
18
X2
261
Felles mulighetsområde
Bruk av arbeid: 9X1 + 6X2 = 1566
200
180
Område som tilfredsstiller
alle restriksjonene
Bruk av pumper: 1·X1 + 1·X2 = 200
Bruk av rør: 12X1 + 16X2 = 2880
174 200
BØK350 OPERASJONSANALYSE
240
X1
Rasmus Rasmussen
19
Tegne målfunksjonen
Vi ønsker å maksimere DB = 350X1 + 300X2.
Anta at vi f.eks. produserer X1 = 100 og X2 = 0.
Da blir DB = 350·100 + 300·0 = 35 000.
Om vi skal ha samme DB men lar X1 = 0, må:
DB = 350·0 + 300· X2 = 35 000  300· X2 = 35 000
 X2 = 35 000/300 ≈ 116,67.
Begge disse punktene: (100, 0) og (0, 116,67)
gir samme DB = 35 000 .
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
20
Plotte nivåkurver for målfunksjonen
X2
261
Bruk av arbeid: 9X1 + 6X2 = 1566
200
180
DB =350X1 + 300X2
Totalt DB= 35 000
116
Bruk av pumper: 1·X1 + 1·X2 = 200
Bruk av rør: 12X1 + 16X2 = 2880
100
BØK350 OPERASJONSANALYSE
174 200
240
X1
Rasmus Rasmussen
21
X2
Ny nivåkurve for målfunksjonen
(0,175)
DB =350X1 + 300X2
Totalt DB= 52 500
175
Første nivåkurve tar utgangspunkt i
X1 = 100.
Andre nivåkurve tar utgangspunkt i
X1 = 150.
116
(150, 0)
100
BØK350 OPERASJONSANALYSE
150
X1
Rasmus Rasmussen
22
Maksimalt dekningsbidrag
I figuren har vi tegnet isobidragslinjen for totalt
dekningsbidrag lik 52 500.
Alle punkt på denne linjen har samme DB.
Om vi parallellforskyver linjen oppover (nordøst) i
diagrammet vil DB øke (jo mer vi produserer av
produktene jo større blir DB).
Når isobidragslinjen akkurat tangerer mulighetsområdet
har vi maksimalt DB, en større produksjon er ikke mulig.
Denne tangeringen vil alltid skje i ett (eller 2)
hjørnepunkt.
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
23
Parallellforskyve nivåkurver
X2
Størst mulig dekningsbidrag når
nivåkurven ligger lengst nordøst, og
samtidig tangerer mulighetsområdet.
Optimal løsning
175
DB: 350X1 + 300X2= 52 500
116
DB: 350X1 + 300X2= 35 000
100
BØK350 OPERASJONSANALYSE
150
X1
Rasmus Rasmussen
24
Optimal løsning
X2
261
Bruk av arbeid: 9X1 + 6X2 = 1566
DB =350X1 + 300X2
200
180
Optimal løsning der restriksjonene for
arbeid og pumper krysser hverandre
Bruk av pumper: 1·X1 + 1·X2 = 200
Bruk av rør: 12X1 + 16X2 = 2880
174 200
BØK350 OPERASJONSANALYSE
240
X1
Rasmus Rasmussen
25
Beregne den optimale løsningen
Den optimale løsningen inntrer der linjene for pumpe- og
arbeidstids- restriksjonene krysser.
Det skjer når de er like:
X1 + X2 = 200
(1)
9X1 + 6X2 = 1566
(2)
Fra (1) får vi,
X2 = 200 -X1
(3)
Setter vi (3) for X2 inn i (2) får vi,
9X1 + 6 (200 -X1) = 1566
Som forenkles til X1 = 122
Så den optimale løsningen er,
X1=122, X2= 200 – X1  X2 =200 – 122 = 78
Totalt DB = $350122 + $30078 = $66,100
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
26
X2
Undersøke alle hjørneløsninger
(0,180)
Målfunksjon = 54 000
(80,120)
Målfunksjon = 64 000
(122,78)
Målfunksjon = 66 100
(0,0)
Målfunksjon = 0
MERK:
Denne metoden fungerer
ikke hvis mulighetsområdet
ikke er lukket.
(174,0)
Målfunksjon = 60 900
X1
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
27
Sammendrag Grafisk løsning av LP Problemer
1. Plott grenselinjen for hver restriksjon.
2. Identifiser mulighetsområdet.
3. Finn optimal løsning enten ved:
1.
2.
Plott nivåkurver for målfunksjonen,
eller
Beregn alle hjørneløsningene.
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
28
Spesielle tilfeller av LP Modeller
Forskjellig unormale forhold kan inntreffe
i LP problemer:
Alternative optimale løsninger
Overflødige restriksjoner
Ubegrenset gode løsninger
Ingen mulige løsninger
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
29
X2
Alternative optimale løsninger
DB: 450X1 + 300X2= 78 300
Alle punktene på linjestykket har like
stort dekningsbidrag, inklusive
endepunktene, som er hvert sitt
hjørnepunkt.
I tillegg til disse to hjørnepunktene er
altså også alle punkt imellom like gode.
(122,78)
(174,0)
X1
BØK350 OPERASJONSANALYSE
MERK:
Alternative optimale løsninger er
gunstig.
En har flere valgmuligheter.
Rasmus Rasmussen
30
Overflødig restriksjon
X2
261
Bruk av arbeid: 9X1 + 6X2 = 1566
225
180
Bruk av pumper: 1·X1 + 1·X2 = 225
Pumper
påvirker
ikke lenger
mulighetsområdet
Bruk av rør: 12X1 + 16X2 = 2880
174
BØK350 OPERASJONSANALYSE
225 240
X1
MERK:
«Overflødige» restriksjoner bør
ikke fjernes. De er nødvendige når
en skal foreta sensitivitetsanalyse.
Rasmus Rasmussen
31
Ubegrenset løsning
X2
Max: X1 + X2
-1·X1 + 2·X2 ≤ 400
800
X1 + X2 ≥ 400
Kan øke verdien på målfunksjonen
i de uendelige.
Problemet har derfor en
ubegrenset god løsning.
Mulighetsområdet
er ikke lukket i alle
retninger.
400
200
400
BØK350 OPERASJONSANALYSE
600
800
X1
MERK:
Ved ubegrenset løsning vil det
ikke fungere å beregne alle
hjørnepunkter for å finne optimal
løsning.
Rasmus Rasmussen
32
Ingen mulig løsning
X2
Max: X1 + X2
200
150
Det finnes ingen områder som
tilfredsstiller alle restriksjonene
samtidig.
X1 + X2 ≥ 200
X1 + X2 ≤ 150
Mulighetsområdet
er tomt.
150
BØK350 OPERASJONSANALYSE
200
X1
MERK:
Ved ingen mulig løsning er det
ofte feil fortegn, eller feil retning
på restriksjonsgrensene, eventuelt
feil verdi på noen
restriksjonsgrenser.
Hvis alle data er riktig, må en
vurdere tiltak for å gjøre
problemet løsbart. (Øke kapasitet)
Rasmus Rasmussen
33
Slutt på kapittel 2
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
34
LP på generell form
MAX (eller MIN):
c1X1 + c2X2 + … + cnXn
Slik at:
a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn >= bk
:
am1X1 + am2X2 + … + amnXn = bm
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
35
LP på standard form
MAX (eller MIN):
c1X1 + c2X2 + … + cnXn
Slik at:
a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn <= bk
:
am1X1 + am2X2 + … + amnXn <= bm
Merk at alle restriksjonene er på formen ”<=”
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
36
Omformulering til standard form
ak1X1 + ak2X2 + … + aknXn >= bk
Multipliser gjennom med -1:
-1| ak1X1 + ak2X2 + … + aknXn >= bk
 -ak1X1 - ak2X2 - … - aknXn <= -bk
Tilsvarende erstattes en ”=” med både ”<=” og ”>=”:
am1X1 + am2X2 + … + amnXn = bm
BØK350 OPERASJONSANALYSE

am1X1 + am2X2 + … + amnXn <= bm
og
am1X1 + am2X2 + … + amnXn >= bm
dvs.
am1X1 + am2X2 + … + amnXn <= bm
og
-am1X1 - am2X2 - … - amnXn <= -bm
Rasmus Rasmussen
37
LP på kompakt form
MAX (eller MIN):
Slik at:
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
38
LP på matriseform
MAX (eller MIN):
Slik at:
Der:
BØK350 OPERASJONSANALYSE
Rasmus Rasmussen
39

similar documents