Lineær programmering: maksimering, minimering og hjørneinspektion

Emneopgave 4 - Lineær Programmering (kapitel 7 i c-bogen)

Svar på følgende spørgsmål:

Hvordan løses et maksimeringsproblem?

Et maksimeringsproblem kan løses trin for trin. Hvis en opgave fx lyder: Bestem det maksimale dækningsbidrag når DB for et bord er 200kr. og 100kr. for en stol. Derudover er der maks 50 m^3 plads. Et bord fylder 3m^3 og en stol 1m^3. Klargøring tager 10 min for et bord eller en stol. Der er maksimalt 5 T til klargøring (300 min.)

Trin 1: Definer x og y:

X= antal bord

Y= antal stole

Trin 2: Opstil begrænsninger.

X

Y

Maks

Lagerplads

3m^3

1m^3

50m^3

Klargøring

10 min

10 min

300 min

Lagerplads: 3x+1y<50 y<-3x+50

Klargøring: 10x+10y<30 y<-x+30

x>0 og y>0

Trin 3 Indtegn polygonområdet:

Trin 4 kriteriefunktion:

400*x+200*y=samlet DB

Trin 5 Indtegn niveaulinje:

N (6000): Y=-400200x+6000200 y=-2x+30 reducer

Trin 6 konklusion:

Rykker niveaulinjen ud til det maksimale punkt som er (10.14,20.07)

Så der skal produceres 10 borde og 20 stole for at opnå maksimalt dækningsbidrag.

Hvordan løses et minimeringsproblem?

Et Minimeringsproblem kan løses trin for trin. Hvis en opgave fx lyder: At der skal indrettes et lager med 2 typer skabe, Skab 1 og Skab 2, i alt mindst 99 stk. hvoraf mindst 10 af dem skal være Skab 2-skabe.