Lineær programmering

 

Lineær programmering

 ​​ ​​ ​​ ​​​​ 

 

 ​​ ​​ ​​ ​​​​ 

 

 

Frederik Hovmark Pedersen

 

 

Indholdsfortegnelse

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Indledning

Lineær programmering er en matematisk metode, der kan anvendes til at finde​​ optimering og minimering.​​ Metoden​​ blev opfundet under 2. verdenskrig, og​​ emnet​​ er dermed forholdsvist nyt​​ sammenlignet med de fleste andre matematiske emner. Grunden til det så blev opfundet var, at man havde​​ behov for en hurtig metode, til​​ at beregne hvor meget man kunne laste i et fly eller​​ et​​ skib, når der var​​ et krav om maksimal vægt samt et begrænset​​ rumfang.​​ 

I virkelighedens verden kan lineær programmering​​ i dag bruges til blandt andet at beregne, hvordan en virksomhed der producerer flere produkter indenfor en række begrænsninger, såsom et maksimum antal arbejdstimer til rådighed, et maksimum antal stk. af hver produkt der skal produceres eller lignende, kan optimere produktionssammensætningen, hvilket vil sige​​ finde​​ det produktmix, der giver de mindst mulige omkostninger, og den størst mulige fortjeneste.

Jeg vil i denne emneopgave gennemgå teori samt løse opgaver samtidig, således at jeg gennemgår teorien​​ med opgaverne som eksempel.​​ Disse opgaver omhandler definition af x og y, opstilling af kriteriefunktion, opstilling af begrænsninger og niveaulinjer og indtegning af disse i et koordinatsystem. Jeg vil se på den optimale kombination, på mindsteværdi, og til sidst vil jeg udarbejde en følsomhedsanalyse.

Opgavebeskrivelse

En bygherre skal fuldføre 2 projekter A og B, hvortil der skal anvendes murere, tømrere og malere.​​ Begge projekter består af mindre selvstændige bygninger.​​ Til projekt A skal anvendes 4 tømre, 6 murere og 1 maler pr. bygning.​​ Til projekt B skal anvendes 5 tømre, 4 murere og 12 malere pr. bygning.​​ Der skal bygges højst 9 bygninger i​​ projekt B.​​ Der skal beskæftiges mindst 30 tømre og antallet af murere må ikke overstige 48.​​ Endelig skal der beskæftiges mindst 29 malere.​​ En bygning i projekt A koster 900.000 kr. pr. bygning og i projekt B koster en bygning 1.200.000 kr.

Det er nu din opgave at bestemme den optimale kombination dvs. hvor mange bygninger der skal​​ være i projekt A samt hvor mange bygninger der skal være i projekt B, således at de samlede omkostninger bliver mindst mulige.

  • Definér dine variable dvs. hvad skal x og y stå for her

Det​​ første​​ skridt på vejen til at løse en problemstilling ved hjælp at lineær programmering er, at definere hvad x og y skal stå for.​​ I dette tilfælde, hvor vi skal finde ud af hvor mange bygninger der kan være i henholdsvis projekt A og B, ​​ står x for antal bygninger i projekt A, mens y står for bygninger i projekt B.​​ Det vil sige:​​ 

x = antal bygninger i projekt A

y = antal bygninger i projekt B

  • Opstil begrænsninger og indtegn dem i et koordinatsystem

Før​​ vi​​ så er i stand til at kunne​​ indtegne det,​​ der skal blive vores polygonområde,​​ er det nødvendigt at opstille en række begrænsninger, ud fra de betingelser vi fik i opgavebeskrivelsen. Her fik vi at vide, at der skulle bygges to projekter A og B. Der skulle så bruges 4 tømre, 6 murere og 1 maler pr. bygning i projekt A, samt 5 tømre, 4 murere og 12 malere pr. bygning i projekt B. Der skulle højst være 9 bygninger i projekt B. Der skulle beskæftiges mindst 30 tømrere og 29 malere og antallet af murere måtte ikke overstige 48. Og en bygning i projekt A kostede 900.000 kr., mens en bygning i projekt B kostede 1.200.000 kr.​​ 

Disse oplysninger kan så indtegnes i et skema som det nedenstående. ​​​​ 

Projekt

A

B

Minimum

Maximum

Tømre

4

5

30

 

Murer

6

4

 

48

Maler

1

12

29

 

Max antal bygninger

 

9

 

 

Dækningsbidrag

900.000

1.200.000

 

 

 

Og det er så ud fra dette skema,​​ samt vores tidligere definition af hvad x og y står for,​​ at​​ vi​​ kan finde frem til vores begrænsninger, som ses herunder:

4x+5y ≥ 30

6x + 4y ≤ 48

1x + 12y ≥ 29

x ≥ 0​​ 

y ≤ 9

Begrænsningerne kan så indtegnes på flere forskellige måder. Man kan vælge at gøre det i hånden, eller vælge at gøre det i Maple.​​ 

Gøres det i hånden skal man ved hver begrænsning isolere y (på nær​​ y ≤ 9​​ og​​ x ≥ 0, det siger jo sig selv). Jeg starter derfor med den første begrænsning,​​ 4x+5y ≥ 30, og isolerer y således:

4x+5y ≥ 30

5y ≥ -4x + 30

y​​  ​​​​ -45x + 6

Det samme gøres så ved de andre begrænsninger, således at man nu har nogle begrænsninger der ser således ud:

y ≥ ​​ -45x + 6

y ≤ -112x + 12​​ 

y​​ ​​ -112x + 2512​​ 

​​ x ≥ 0​​ 

y ≤ 9

Disse skal jo så indtegnes ”manuelt” i et koordinatsystem, hvor man ved fx​​ y ≥ ​​ -45x + 6, starter i punktet +6 på y-aksen, og derfra går 1 ud af x-aksen og 0,8 ned ad y-aksen, hvor man finder et punkt, og derfra kan indtegne en linje. Dette gøres ligeledes ved de andre, og de linjer man nu har indtegnet, danner så et begrænsningsområde(også kaldet et polygonområde).​​ Herunder har jeg sat dem ind i GeoGebra, i stedet for at tegne dem i hånden.​​ Polygonområdet ses her som det område i den mørkeste blå farve. Og det er dermed i punkterne inden for dette område, at de givne betingelser er opfyldt. ​​ ​​  ​​​​ 

 ​​​​ 

Det kan naturligvis også laves i Maple, hvilket er noget hurtigere.​​ Gør man det i Maple, som jeg her i opgaven har valgt at gøre, ser det​​ ud som på billedet herunder.​​ Det første man gør er, at skrive begrænsningerne​​ ind. Derefter indskrives den kriteriefunktion, som jeg finder i næste opgave. Det jeg så gør efterfølgende er, at lave en BL(BL​​ står for begrænsningslinjer), hvor jeg​​ ”samler” alle begrænsningslinjerne.​​ De informationer der skal bruges er nu skrevet ind, og efter at have skrevet display(p1) og trykket enter, ses grafen så.​​ 

 

​​ 

  • Opstil kriteriefunktion

For at finde kriteriefunktionen skal vi bruge vores oplysninger om, at en bygning i projekt A koster 900.000 kr. pr. bygning,​​ mens en bygning i projekt B koster 1.200.000 kr. pr. bygning. Samt at x er lig antal bygninger i projekt A,​​ og at y er lig antal bygninger i projekt B. Kriteriefunktionen bliver så:

f(x,y) = 900.000x​​ + 1.200.000y

  • Opstil og indtegn ​​ 2 niveaulinjer i koordinatsystemet

Hele idéen med lineær programmering er jo som sagt, at finde største- og mindsteværdien​​ indenfor et begrænsningsområde​​ (altså vores polygonområde),​​ og til at gøre dette​​ benyttes niveaulinjer.​​  ​​​​ 

Et eksempel på en niveaulinje er, at vi har​​ en niveaulinje til niveauet t. Denne er en ret linje, og betegnes​​ som N(t).​​ t kunne jo så naturligvis​​ være et hvilket som helst tal.​​ Niveaulinjen t viser så​​ alle de punkter, hvor der opnås et dækningsbidrag på t.​​ ​​ 

Måden hvorpå du beregner forskriften for din niveaulinje er meget simpelt, at sætte t lig kriteriefunktionen, for derefter at isolere y. Kriteriefunktionen var jo i dette tilfælde f(x,y) = 900.000x + 1.200.000y, og da jeg så vælger at jeg vil indtegne niveaulinjerne​​ N(0) og N(4000.000), gør jeg således:​​ 

N(0): f(x,y) = 900.000x + 1.200.000y = 0

900.000x + 1.200.000y = 0

1.200.000y = -900.000x

y = -0,75x

N(4.000.000): f(x,y) = 900.000x + 1.200.000y = 4.000.000

900.000x + 1.200.000y = 4.000.000

1.200.000y = -900.000x + 4.000.000

y = -0,75x + 3,33

Det vil sige at jeg nu har de to niveaulinjer:

N(0):​​ y = -0,75x

N(4.000.000):​​ y = -0,75x + 3,33

Niveaulinjer kan naturligvis også laves i Maple.​​ Og gør man dette, er der to muligheder. Man enten vælge at lave en helt masse niveaulinjer,​​ hvilket gøres ved at skrive således:

​​ ​​ 

Eller​​ man​​ vælge blot at indtegne​​ netop de to niveaulinjer N(0) og N(4.000.000),​​ hvilket​​ gøres ved at skrive således:

De to niveaulinjer bliver så vist som de røde linjer i grafen herunder.​​ De to sorte pile er til brug i næste opgave.​​ 

  • Bestem den optimale kombination

Nu skal​​ vi så​​ finde den optimale kombination,​​ altså den kombination af antal bygninger af henholdsvis typen A og B​​ hvor omkostningerne er billigst, indenfor de givne betingelser. Til dette skal de​​ ovenstående niveaulinjer benyttes.​​ Af de to niveaulinjer fremgår det, at niveauet stiger til​​ højre, illustreret med de to pile.​​ At niveauet stiger til højre ses af, at N(4.000.000) ligger til​​ højre for N(0).​​ 

Og da dette er en minimeringsopgave​​ betyder​​ det​​ så, at​​ man skal finde det første punkt man rammer,​​ som vel og mærket ligger indenfor polygonområdet,​​ når​​ en af niveaulinjerne​​ rykkes​​ til højre, og​​ det​​ er så dette​​ punkt​​ hvori den optimale kombination ligger. Dette punkt er​​ i dette tilfælde (5,2).​​ Punktet er vist med den røde pil herunder.

Kan​​ man​​ ikke umiddelbart​​ aflæse punktet, kan man også finde det, ved at sætte de to linjer sammen, der danner punktet. Her kan jeg så, af de begrænsninger hvor jeg tidligere har isoleret y, at det er​​ y ≥ ​​ -0,8x + 6​​ og​​ y​​ ​​ -0,083x + 2,417​​ der danner punktet. Beregningen ser således ud:

y ≥ ​​ -0,8x + 6​​ ^​​ y​​ ​​ -0,083x + 2,417

Jeg fjerner y og sætter dem lig med hinanden:

-0,8x + 6​​ =​​ -0,083x + 2,417​​ 

Jeg isolerer nu x:

-0,717x = -3,583

x = 5

Jeg sætter så 5 ind på x plads i​​ y ≥​​ -0,8x + 6(jeg kunne også have sat den ind på x plads i​​ y​​ ​​ -0,083x + 2,417):

y ≥ ​​ -0,8*5​​ + 6​​ = 2

Altså har jeg nu fundet ud af,​​ at punktet​​ hedder (5,2).

Da x derfor er lig 5, mens y er lig 2, betyder dette, at der skal bygges henholdsvis 5 bygninger af typen A, mens der skal bygges 2 bygninger af typen B.​​ 

Maple kan​​ naturligvis også beregne​​ punktet​​ for os,​​ hvilket gøres ved at skrive følgende efter grafen​​ i Maple:

Resultatet ses så som den blå skrift, hvor det fremgår at x er lig 5, mens y er lig 2. Tallet der står lige før det, omtales i næste opgave.​​ 

Havde dette i stedet for en minimeringsopgave været en maksimeringsopgave,​​ hvor man skulle maksimere dækningsbidrag, nettofortjeneste eller lignende, så ville det punkt man skulle finde, være det sidste punkt man ramte indenfor polygonområdet, når man rykkede en niveaulinje til højre. I dette tilfælde ville det så være punktet (2,9), hvilket​​ man også kunne beregne, ved at sætte to linjer lig med hinanden, ligesom at​​ Maple naturligvis også​​ kunne​​ beregne​​ det, ved at skrive maximize = true, i stedet for maximize = false som ved minimeringen. Det ser i Maple således ud:

 ​​​​ 

  • Hvad bliver mindsteværdien og hvad fortæller den?

Mindsteværdien​​ beregnes ud fra det punkt vi fandt i forrige opgave, nemlig punktet​​ (5,2).​​ Dette sættes så ind i kriteriefunktionen​​ f(x,y) = 900.000x​​ + 1.200.000y.

f(5,2) = 900.000*5 + 1.200.000*2 = 6.900.000.​​ 

Altså er 6.900.000 kr. det mindst mulige beløb de kan forvente at skulle af med, når alle kriterierne skal opfyldes.​​ 

Men også her kan Maple selvfølgelig løse problemet,​​ hvilket ses herunder, hvor resultatet ses som det blå tal til venstre.​​ 

​​ 

Også her kunne opgaven, hvis det havde været en maksimeringsopgave, selvfølgelig have været at udregne størsteværdien. Dette ville man så skulle gøre på samme måde, ved at sætte det punkt man nu har fundet ind i kriteriefunktionen.​​ 

  • Udarbejd en følsomhedsanalyse for en bygning​​ både i projekt A og i projekt B.

Ved en følsomhedsanalyse undersøges det,​​ hvor meget henholdsvis dækningsbidraget eller omkostningerne kan ændres, uden at der ændres på produktmixet, hvilket vil sige uden,​​ at den optimale løsning skal ændres.​​ Dette sker da oplysningerne om dækningsbidrag​​ og omkostninger ofte i praksis​​ er svære at fastlægge helt nøjagtigt, grundet risikoen for ændringer over tid.​​ ​​ ​​ 

For at finde ud af dette, må man først og fremmest finde optimeringspunktet, som i dette tilfælde er (5,2).​​ Herefter finder jeg de to linjer som krydsede hindanden i optimeringspunktet, disse var:

y ≥ ​​ -0,8x + 6​​ ^​​ y​​ ​​ -0,083x + 2,417

Jeg skal så bruge de to stigningstal, -0,8x​​ og -0,083x, samt kriteriefunktionen som jo var f(x,y) = 900.000x + 1.200.000y.​​ ​​ 

Det man så tager udgangspunkt i, i en følsomhedsanalyse, er​​ -ab.

Når jeg så har disse oplysninger, vil jeg starte med at udarbejde en følsomhedsanalyse for en bygning i projekt A. Det betyder så, at jeg skal sætte det der svarer til b i kriteriefunktionen(altså 1.200.000) ind på b’s plads i​​ -ab.​​ Samt sætte det lig med stigningstallet i første den første af de to linjer. Således:

​​ -a1.200.000​​ = -0,8

Herefter isolerer jeg så a

-a = -960.000

a = 960.000

Nu sætter jeg det så lig stigningstallet i den anden linje i stedet.

​​ -a1.200.000​​ = -0,083

-a =​​ 100.000

a = 100.000

Det vil sige​​ at a, som er​​ 900.000, kan stige til 960.000​​ mens den kan falde til​​ 100.000, uden at man skal ændre den optimale løsning.​​ Dermed er følsomheden høj, når det handler om hvor meget den kan stige, eftersom at den kun kan stige med 60.000, mens følsomheden er lav, hvis man kigger på hvor meget den kan falde, da den kan falde med hele 800.000.

Skal jeg udarbejde en følsomhedsanalyse for en bygning i projekt B, gør jeg det samme, bortset fra at jeg sætter a i kriteriefunktionen ind på a’s plads, og isolerer b.​​ 

-900.000b​​ = -0,8

-900.000 = -0,8*b

1.125.000 = b

b = 1.125.000

 

-900.000b​​ = -0,083

-900.000 = -0,083*b

10.800.000= b

b =​​ 10.800.000

Altså kan b, som er 1.200.000,​​ stige til​​ 10.800.000​​ og falde til 1.125.000,​​ uden at der skal ændres på den optimale løsning.​​ Det betyder så, at følsomheden er lav, når man ser på hvor meget den kan stige, da den kan stige med hele 9.600.000, mens følsomheden er høj, når det handler om hvor meget den kan falde, da den kun kan falde med 75.000.​​