Lineær programmering

Lineær programmering

med Derive

!

!

!

Børge Jørgensen

1

Indholdsfortegnelse.

Forord ---------------------------------------------------------------------------------Introduktion til lineær programmering -------------------------------------Simplexmetoden -------------------------------------------------------------------Simplexmetoden med Derive --------------------------------------------------Skyggepriser og følsomhedsanalyse ---------------------------------------Appendiks ----------------------------------------------------------------------------2 3 10 18 22 29

2

Forord.

Dette undervisningsmateriale er udviklet i forbindelse med projektet ?Matematik og naturfag i 1 verdensklasse? , som Københavns Kommune, Frederiksberg Kommune, Københavns Amt, Frederiksborg Amt, Roskilde Amt og Hovedstadens Udviklingsråd står bag. ?Lineær programmering med Derive? er, som titlen antyder, et undervisningsforløb, der i høj grad udnytter mulighederne i et CAS-program. I fremstillingen introduceres begrebet Lineær programmering (LP) samt den mest anvendte metode til løsning af LP-problemer, Simplexmetoden. Desuden behandles begreberne skyggepriser og følsomhedsanalyse, herunder hvordan slutsimplextabellens værdier kan anvendes i beskrivelsen af disse begreber. Derive?s faciliteter til grafisk fremstilling, til matrixmanipulation samt til bestemmelse af simplextabellerne mindsker i væsentlig grad de beregningsmæssige sider i løsningen af LPproblemer, hvorved der i højere grad kan fokuseres på det indholdsmæssige i begreberne. (De Derivefunktioner, der er benyttet, er forklaret i appendiks).

Børge Jørgensen Helsingør Gymnasium, maj 2004

1

www.matnatverdensklasse.dk

3

1. Introduktion til lineær programmering.

Betragt følgende problemstilling: Et lille tekstilforetagende i provinsen syr skjorter og bukser. Arbejdsgangen er fordelt på 3 områder: Tilskæring, syning og pakning. Der er ingen problemer med at skaffe de nødvendige materialer til produktionen, men på grund af lokalernes størrelse er der kun plads til et begrænset antal medarbejdere på de 3 områder; dette kan udtrykkes ved det antal timer, der er til rådighed i hver afdeling pr. uge. I dette tilfælde gælder følgende timetal: I tilskæringsafdelingen er der 110 timer, i syafdelingen 650 timer og i pakkeafdelingen 40 timer. Man regner med, at det tager 0.15 timer at tilskære en skjorte og 0.10 timer for bukser, syningen tager 0.60 timer for en skjorte og 0.90 timer for et par bukser, medens pakningen tager 0.05 timer for hver. Fortjenesten ved salget af disse beklædningsgenstande er 80 kr. pr. skjorte og 65 kr. pr. buksepar. Hvordan skal produktionen sammensættes for at maksimere fortjenesten? For at gøre problemet lidt mere overskueligt opstiller vi tallene i tabelform: ! !!!!!!"!!!!!!!!!!!!!!#$%&'()'!*+,!!-.$#)'!*/,!!!!!(01)'!!!2! !!!!!!3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!3! !!!!!!3!(04#$5'067!!!!!!!89:;!!!!!!!!!!89:!!!!!!!!!::8!!!!3! !!!!!!3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!3! <:=!!!3!!!#/6067!!!!!!!!!!89>!!!!!!!!!!89?!!!!!!!!!>;8!!!!3! !!!!!!3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!3! !!!!!!3!!!@A$6067!!!!!!!!898;!!!!!!!!!898;!!!!!!!!!B8!!!!!3! !!!!!!3!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!3! !!!!!!C!D&'(%)6)#()!!!!!!!E8!!!!!!!!!!!>;!!!!!!1A$#01)')#!F Herudover er det klart, at antal producerede skjorter (x) og bukser (y) er ikke-negative. Vi kan nu opstille problemet i matematisk form: ! <G=!!!89:;H+!I!89:H/!J!::8! ! <K=!!!89>H+!I!89?H/!J!>;8! ! <B=!!!898;H+!I!898;H/!J!B8! ! <;=!!!E8H+!I!>;H/!L!1A+! ! <>=!!!+!M!8!N!/!M!8! Dette er et typisk problem inden for lineær programmering (et LP-problem). De første tre uligheder kaldes normalt for bibetingelser, de sidste uligheder (af gode grunde) for positivitetsbetingelser, medens den størrelse, der skal maksimeres kaldes kriteriefunktionen. Det givne LP-problem kan derfor udtrykkes ved: Maksimér kriteriefunktionen under bibetingelserne og positivitetsbetingelserne.