Lineær Programmering (danish)

Lineær programmering 

Hvad handler lineær programmering overordnet om? 
En virksomhed producerer og sælger eksempelvis to forskellige varer.
Virksomheden vil gerne maksimere sit samlede dækningsbidrag og skal i den forbindelse beslutte, hvor mange af hver vare, for virksomhedens produktion resurser er nemlig begrænsede.
Eksempelvis kan virksomhedens produktion være begrænset af, at dens maskiner kun kan køre et vidst antal timer hver uge, eller af, at medarbejderne kun arbejder et vist antal timer hver uge.

Virksomheden skal optimere sin produktion af sine to varer, dvs. Vælge den kombination af de to varer der maksimerer det samlede dækningsbidrag under hensyntagen til den intensitet hvormed produktionen af de de to varer forbruger de begrænsede resurser.

Vi løser opgaver i lineær programmering i 7 trin:

1) definer variablene x og y

2) Opstil uligheder og omskriv til eksplicit form
3) Indtegn begrænsningslinjer og skraver
4) Opstil kriteriefunktion
5) Opstil niveaulinjer
6) Forskyd niveaulinjerne i ønsket retning indtil sidste røringspunkt med kapacitetsområdet
7) Konklusion

Eksempel  

En virksomhed producerer to varer: Borde og stole.
De to varer skal begge gennem to processer/afdelinger, nemlig produktion og samling.
Et bord bruger 3 timer i produktionen og 10 minutter i samlingen.
Et bord bruger 1 time i produktionen og 10 minutetter i samlingen.
I produktionsafdelingen har man maksimalt 50 timer til rådighed på en uge, og i samlingen 5 timer, dvs. 300 minutter (5*60).

Dækningsbidraget pr. bord: 400 kr.  
Dækningsbidraget pr. stol: 200 kr.

1. Definer variable x og y
   
   x = antal borde
   y= antal stole

1. Opstil uligheder og omskriv til eksplicit form
   

Vi bruger nu skemaet til at opstille to uligheder – en for hver afdeling:

Afdeling 1: 3x+1y ≤ 50

3x er lig med at et bord tager 3 timer og +1y betyder, at 1 stol tager 1 time. ≤ 50 betyder større eller mindre end 50. Hvis man fx siger 10 * borde og 10 * stole = 30 timer + 10 timer = 40 timer og derfor kan det godt produceres fordi vi maksimalt har 50 timer til rådighed.

Peders formulering: Hvorfor ser uligheden sådan ud? Husk, at x er antal bordeog y er antal stole. Hver gang vi lader et bord gennemgå produktionen, bruger den 3 timer. Hver gang en stol gennemgår produktionen bruger vi 1 time. Vi har maksimalt 50 timer til rådighed. Derfor kan vi ikke producere flere borde og stole, end at 3x+1y samlet set højst giver 50.

Vi omskriver nu begrænsningen/uligheden til eksplicit form, dvs. Så y står alene på venstre side.