Lineær programmering

OBS: bloggen er flyttet til http://www.studienoter.com

 

Benyt venligst denne

Indledning:

Lineær programmering blev opfundet i 1947 efter anden verdenskrig og bliver brugt til at udregne hvordan man kan anvende begrænsede ressourcer bedst muligt.

Hvis man tager udgangspunkt i 2 produkter vil det svare til 2 akser.

x= antal produkter af produkt 1.

y= antal produkter af produkt 2.

Begrænsninger, skema og uligheder:

Begrænsninger kan være:

–      Kapital

–      Ansatte

–      Tid

–      Råstoffer

–      Maskiner

Det skal siges at når vi snakker begrænsninger gælder reglerne: x≥0 og y≥0 altid.

For at få et overblik over begrænsningerne laver man et ”begrænsningsskema” hvor x (produkt 1) og y (produkt 2) hver har en kolonne og begrænsningerne hver har en række. Derudover er der en kolonne til fx hvor mange minutter der max må bruges på at forme et glas eller pakke det i en kasse.

X   = antal produkt 1 Y   = antal produkt 2 Max
Pustes 3 3 30
Formes 2 1 20
Pakkes 1 2 40

Så skal man sammensætte nogle uligheder som man senere kan tegne ind for at finde sit polygonområde. Ulighedernes formel ser sådan ud: ax+by≤c. Hvor man derefter isolerer y.

Fx

3x+3y≤30
3y≤-3x+30
y≤-x+15

2x+y≤20
y≤-2x+20

x+2y≤20
2y≤-x+40
y≤-0,5x+20

Polygonområde:

Når man har sammensat sine uligheder og har isoleret y skal man tegne dem ind i et koordinatsystem. Når de krydser hinanden dannes der et område som hedder polygon området, og det er indenfor det man må producere.

Max punktet viser den optimale løsning i forhold til de begrænsninger vi har. Minimum viser hvad vi mindst kan afsætte/omsætte/købe/bruge. Fx skal vi som mennesker mindst bruge en hvis mængde vitaminer i vores kost.

Man finder sit max eller minimumspunkt ved enten at lave en niveaulinje eller en hjørnepunktsløsning. Det kommer jeg tilbage til.

poly1

Kriteriefunktion og optimering:

Kriteriefunktionen (f(x,y)=ax+by=t) viser hvor meget man fx omsætter. Hvis vi forestiller os at produkt 1 sælges for 15 kr. og produkt 2 for 20 kr., vil t være et udtryk for omsætningen hvis der sælges x antal til 15kr. og y antal til 20 kr. kriteriefunktionen vil altså se således ud: f(x,y)=15x+20y=t

Man bruger kriteriefunktionen når man skal maximere eller minimere, hvis man bruger hjørnepunktsløsning. Det gør man ved at tegne ulighederne ind i et koordinatsystem, og der hvor de krydses får vi nogle skæringspunkter.

I vores eksempel er de (0,15) (5,10) og (10,0).

For at finde den optimale løsning kan man benytte hjørnepunktsløsning. Dvs. at man sætter skæringspunkterne ind i kriteriefunktionen for at finde den optimale omsætning.

Hvis det ikke er direkte til at se hvor skæringspunktet er, kan sætte forskrifterne lig med hinanden og derefter sætte den x værdi man finder ind på x’s plads.

-x+15=2x+20
-x+2x=20-15
x=5

-5+15=10

(5,10)

Fx:

F(0,15)=0*15+15*20= 300
F(5,10)=5*15+10*20= 275
F(10,0)=10*15+0*20= 150

Der kan man så se at for at få den størst mulige omsætning skal man sælge 0 af produkt 1 og 15 af produkt 2.

Man kan også lave en niveaulinje, hvor man sætter kriteriefunktionen lig med 0 og isolerer y.

15x+20y=0

20y=-15x

y= -0,75x

så indtegner man det i sit koordinatsystem, og derefter kan man parallelforskyde den, og det sidste skæringspunkt linjen rammer, er den optimale løsning.

Følsomhedsanalyse:

Man bruger følsomhedsanalyse til at finde ud af hvor meget fx prisen på produkt A skal ændres for at det ville være mere optimalt at ændre produktionen.

Opgave:

En virksomhed kan sælge sin produktion af varerne A og B med et dækningsbidrag på henholdsvis 5 kr. og 8 kr. pr. stk.

Begge produkter skal først opskæres, herefter slibes og til sidst samles. Til skæring kan anvendes 7 timer (420 min.) pr. dag, til slibning 10 timer (600 min.) pr. dag og til samling 8 timer (480 min.) pr. dag.

Til produktion af 1 stk af vare A lægges der beslag på skæremaskinen i 8 min., på slibemaskinen 6 min, og på samlemaskinen 4 min. de tilsvarende tal for varer B er henholdsvis 6 min., 2 min., og 8 min.

Bestem den produktionssammensætning af varer A og B der giver virksomheden det størst mulige dækningsbidrag.

Kriteriefunktionen vil hedde: f(x,y)=5x+8y=t

Begrænsningsskema:

X   antal vare A Y   antal vare B Max
Skære 8 6 420
Slibe 6 2 600
Samle 4 8 480

 

Uligheder og graf:

8x+6y≤420
6y≤-8x+420
y≤-1,33x+70

6x+2y≤600
2y≤-6x+600
y≤-3x+300

4x+8y≤480
8y≤-4x+480
y≤-0,5x+60

 poly2

Skæringspunkter:

(0,60) (aflæst)

-4/3x+70=-1/2+60

-4/3x+1/2x=60-70

-8/6x+3/6x=-10                                            y=-0,5*12+60

-5/6x=-10                                                     y=-6+60

x=12                                                             y=54

(12,54)

(52,2;0) (aflæst)

Hjørnepunktsløsning :

F(0,60)      =5*0+8*60=              480

F(12,54)    =5*12+8*54=            492

F(52,5;0)  =5*52,5+8*0=           262,5

Det størst mulige dækningsbidrag vil fremkomme af 12 af produkt A og 54 af produkt B.

Reklamer