Lineær programmering uden computer
Det er nemt at lave lineær programmering vha. Geogebra, men som altid får man en bedre forståelse når man regner i hånden. Dette afsnit kan springes over hvis man ikke går efter topkarakter.
Vi tager udgangspunkt i det samme eksempel som vi lige har været i gennem med Geogebra. Problemstillingen var:
En tøjproducent producerer bukser og jakker.
Producenten har $$750 m^2$$ bomuld og $$1000 m^2$$ polyester.
Til et par bukser skal bruges $$1 m^2$$ bomuld og $$2 m^2$$ polyester, og til en jakke skal der bruges $$1{,}5m^2$$ bomuld og $$1 m^2$$ polyester.
Dækningsbidraget er $$500 kr.$$ pr. par bukser og $$400 kr.$$ pr. jakke.
Hvor mange bukser og hvor mange jakker skal der produceres for at få det størst mulige dækningsbidrag?
Hvad er det maksimale dækningsbidrag?
Kriteriefunktionen
Vi vil gerne optimere dækningsbidraget, og det afhænger af antal solgte bukser og antal solgte jakker. Derfor definerer vi:
$$x$$ er antallet af bukser. $$y$$ er antallet af jakker.
Kriteriefunktionen beskriver det vi vil optimere (dækningsbidraget), og har derfor forskriften:
$$$f(x,y)=500x+400y$$$
Polygonområdet
Vi har $$750 m^2$$ bolmuld og $$1000 m^2$$ polyester og til et par bukser skal bruges $$1 m^2$$ bomuld og $$2 m^2$$ polyester.
Til en jakke skal der bruges $$1{,}5m^2$$ bomuld og $$1 m^2$$ polyester.
Som før skriver vi det op i et skema:
| Bukser ($$x$$) | Jakker ($$y$$) | Maks | |
| Bomuld | 1 | 1,5 | 750 |
| Polyester | 2 | 1 | 1000 |
Ud fra skemaet kan vi opstille følgende ligninger.
$$1x+1{,}5y\leq 750$$ og $$2x+1y\leq 1000$$.
Udover dette er det oplagt at vi selvfølgelig ikke kan producere et negativt antal varer, så:
$$x\geq 0$$ og $$y\geq 0$$
I stedet for at skrive begrænsningerne ind i Geogebra omformer vi dem nu, så de kommer til at ligne lineære funktioner.
Den første ulighed er:
$$$1x+1{,}5y\leq 750.$$$
Vi trækker $$x$$ fra på begge sider:
$$$1{,}5y\leq -x+750$$$
og dividerer med $$1{,}5$$:
$$$\mathbf{y\leq -\frac{2}{3}x+500}.$$$
Den næste ulighed er:
$$$2x+1y\leq 1000.$$$
Vi trækker $$2x$$ fra på begge sider:
$$$\mathbf{y\leq -2x+1000}.$$$
Vi tegner de to uligheder som er markeret med fed ind i et koordinatsystem som om det var lineære funktioner:
Men fordi der står $$y\leq\ldots$$, så er det faktisk ikke linjer, og vi skal have fat i alt det der ligger under linjerne. De to uligheder $$x\geq 0$$ og $$y\geq 0$$ betyder at vi skal ligge over $$x$$-aksen og til højre for $$y$$-aksen, så vi må få et polygonområde der ser således ud:
Nu skal vi tegne niveaulinjer. Vi benytter følgende sætning:
Sætning 1
For $$f(x,y)=ax+by+c$$ og for $$t\in\mathbb{R}$$ er niveaukurven $$N(t)$$ en linje bestemt ved følgende ligning:
$$$y=-\frac{a}{b}x+\frac{t-c}{b}.$$$
Vha. sætning 1, finder vi $$N(0)$$ for vores kriteriefunktion. Forskriften var $$f(x,y)=500x+400y$$, så $$a=500$$ og $$b=400$$, og vi indsætter i ligningen:
$$$y=-\frac{a}{b}x+\frac{t-c}{b}=-\frac{500}{400}x+\frac{0-0}{400}=-1{,}25x$$$
Øvelse 1
Bestem niveaulinjen $$N(200000)$$ for $$f(x,y)=500x+400y$$ vha. sætning 1.
$$y=-1{,}25x+500$$
Vi tegner de to fundne niveaulinjer ind i vores koordinatsystem, og vi kan se hvilken vej niveauerne vokser:
Så jo længere vi går skråt op til højre i retning af den røde pil, jo højere bliver niveauerne. Det største niveau indenfor polygonområdet må derfor være i skæringspunktet mellem de to blå linjer.
De to blå linjer havde forskriften $$y= -\frac{2}{3}x+500$$ og $$y= -2x+1000$$, og vi finder skæringspunktet ved at sætte højresiderne lig hinanden:
$$$-\frac{2}{3}x+500=-2x+1000.$$$
Vi ganger med 3 på begge sider:
$$$-2x+1500=-6x+3000.$$$
Vi lægger $$6x$$ til og trækker $$1500$$ fra på begge sider:
$$$4x=1500.$$$
Vi deler med $$4$$ og får
$$$x=375$$$
Vi finder $$y$$-koordinaten ved at sætte $$375$$ ind i en af begrænsningerne:
$$$y=-2\cdot 375+1000=250.$$$
Producenten skal altså producerer 375 bukser og 250 jakker, for at få det største dækningsbidrag.
Dækningsbidraget finder vi ved at sætte ind i kriteriefunktion:
$$$f(375,250)=500\cdot 375 + 400\cdot 250=287500.$$$
Altså er det optimale dækningsbidrag 287500 kr.
Vi slutter dette kapitel med en dejlig øvelse:
Øvelse 2
Regn de to sidste opgaver i det forgående afsnit med eksamensopgaver uden at bruge andre hjælpemidler end mathhx.
...