Samenvatting Operationele Beleidsmethoden

OPERATIONELE BELEIDSMETHODEN
CHAPTER 2: LINEAR PROGRAMMING: BASIC CONCEPTS

INTRODUCTIE

Het management van een organisatie moet regelmatig beslissingen nemen over de toewijzing van middelen aan
verschillende activiteiten om zo goed mogelijk te voldoen aan de doelstellingen van de organisatie.
 Middelen: budget, personeel, grondstoffen …
 Activiteiten: marketing, productie, kapitaalinvesteringen …
 Doelstellingen van de organisatie: winst maximaliseren en kosten minimaliseren

Lineair programmeren = een zeer krachtig hulpmiddel om dit soort problemen te optimaliseren!
 Lineair : verwijst naar het type wiskundige uitdrukkingen in het model → geen machten (alles macht 1)
 Programmeren : ≠ computerprogrammering, maar = planning → Lineair planningsprobleem
 Gebruikt een wiskundig model van het probleem
 Niet alleen bruikbaar in bedrijven, maar ook in non-profit, overheid...
o Vb. ziekenhuizen welzijn patiënten maximaliseren

Lineaire programmering = het plannen van activiteiten door middel van een lineair wiskundig model
 De beste mix van activiteiten vinden: welke activiteiten en op welk niveau?


CASE STUDY : THE WYNDOR GLASS COMPANY PRODUCT MIX PROBLEM

CASE: WGC produceert glasproducten van hoge kwaliteit, waaronder ramen en glazen deuren. Dure producten,
marktniche door het leveren van de hoogste kwaliteit in de industrie. Drie fabrieken die tegelijkertijd onderdelen van
de producten produceren. Wegens dalende verkoop voor bepaalde producten  worden onrendabele producten
stopgezet, waardoor productiecapaciteit vrijkomt om twee nieuwe producten te lanceren.


Neem Wyndor Glass Co, dat de volgende nieuwe producten heeft ontwikkeld om zijn productlijn te vernieuwen:
 Een glazen deur van 8 voet met aluminium kozijnen.
 Een raam van 2 bij 2 meter met houten kozijnen.

Het bedrijf heeft drie fabrieken:
 Fabriek 1 produceert aluminium kozijnen.
 Fabriek 2 produceert houten kozijnen.
 Fabriek 3 produceert glas en monteert de ramen en deuren.

Vraag: Wat zou de meest winstgevende mix van producten zijn om per week te produceren (d.w.z. het aantal
eenheden om van elk nieuw product te produceren), om de winst per week te maximaliseren

 Benodigde productietijd voor beide producten in
A B C D E F G
de 3 fabrieken (gebruikte uren per Wyndor Glass Co. Product-Mix Problem
1
geproduceerde eenheid) 2
o Beschikbare capaciteit in de fabrieken 3 Doors Windows
4 Unit Profit $300 $500
(beschikbare uren per week) 5 Hours
o Winst per producteenheid (winst per 6 Hours Used Per Unit Produced Available
7 Plant 1 1 0 4
eenheid) 8 Plant 2 0 2 12
9 Plant 3 3 2 18


1

,FORMULATING A BASIC MATHEMATICAL LP MODEL

Stappenplan mathematische methode:
Stap 1. De te nemen beslissingen identificeren → beslissingsvariabelen
Stap 2. Doelfunctie
Stap 3. Identificeren van beperkingen

Voorbeeld: Wyndor Glass Co. Product Mix Problem
 STAP 1: Beslissingsvariabelen
o 1 : aantal deuren per week
o 2 : aantal ramen per week
 STAP 2: Doelfuntie
o Winst = 300$D + 500$R
 STAP 3: Beperkingen
o D≤4
o 2R ≤ 12
o 3D + 2R ≤ 18
o D ≥ o en R ≥ 0
 (examen) Negativiteitsbeperkingen weergeven !! → je kan niet -1 deuren of ramen
produceren
Oplossing:
 Een oplossing is niet noodzakelijk de beste oplossing
o Elke keuze van waarden voor D en W wordt een oplossing voor het model genoemd
 Een haalbare oplossing = een oplossing die aan alle beperkingen voldoet (= toegelaten oplossing)
 Een onhaalbare = een oplossing die minstens 1 beperking schendt (= niet toegelaten oplossing)
 De BEST haalbare oplossing = de oplossing die de objectieve functie optimaliseert en wordt de optimale
oplossing genoemd. (= optimale oplossing)


Basisaannames van LP-modellering:
 Evenredigheidsveronderstelling = De bijdrage van elke beslissingsvariabele aan de objectieve functie (en/of
aan de linkerzijde van een beperking) is evenredig met de waarde van de beslissingsvariabele.
o Geen machten groter dan 1 in doelfunctie of beperkingen

 Additiviteitsaanname = De bijdrage van elke beslissingsvariabele aan de objectieve functie (en/of aan de lhs
van een beperking) is onafhankelijk van de waarden van de andere beslissingsvariabelen.
o Producten van twee of meer beslissingsvariabelen zijn niet toegelaten in de doelfunctie of
beperkingen

 Veronderstelling van deelbaarheid:
o Elke beslissingsvariabele mag fractionele waarden aannemen!!!
o Wordt in de praktijk vaak geschonden: je kunt bijvoorbeeld vaak geen fractionele hoeveelheid van
een product produceren (deuren? ramen?).
 Het kan nodig zijn om integer beperkingen op te leggen!!! Zie later
o = we mogen kommagetallen gebruiken

 Zekerheidsaanname:
o Elke parameter (coëfficiënten van de objectieve functie, rechterkanten van de beperkingen en
coëfficiënten van de beperkingen) is met zekerheid bekend.
o Niet altijd waar!
o Bijv. Wyndor Glass company: is het aantal gebruikte uren per product in elke fabriek een exact
(deterministisch) getal?

2

, o = alle informatie die we hebben, is zeker
Voorbeeld: Wyndor Glass Co. Product Mix Problem
 Controleer de evenredigheid → op orde, want zie geen machten
 Controleer de additiviteit → in orde want beslissingsvariabelen worden niet vermenigvuldigd
APPLYING THE GRAPHICAL METHOD

LP-problemen met slechts twee beslissingsvariabelen kunnen grafisch worden opgelost!

Stappenplan grafische methode:
Stap 1. Tweedimensionale grafiek → assen = beslissingsvariabelen
Stap 2. Haalbaar gebied
→ functionele beperkingen, assen ~ niet-negatieve constr. (grenslijnen van de beperking)
Stap 3. Objectieve functie → lijnen
Stap 4. Optimale oplossing
→ beweeg de lijn van de doelfunctie in de richting van verbetering tot het laatste punt in de
haalbare regio is bereikt W

8




Production rate (units per week) for windows
A product mix of
Voorbeeld: Wyndor Glass Co. Product Mix Problem 7 D = 4 and W = 6

 Een punt is een mix van deuren en ramen 6 (4, 6)
 Geen negatief aantal deuren en/of ramen dus nooit voorbij (0,0)
5
 Allen punten in het vak rechtboven → oplossing voor het probleem
 Beslissingsvariabelen mogen ook van as gewisseld worden 4 A product mix of
D = 2 and W = 3
3 (2, 3)

2

1
Origin

-2 -1 0 1 2 3 4 5 6 7 8 D
Production rate (units per week) for doors
-1
 Beperkingen tekenen : Production rate for windows
W
Production rate for windows -2 10
W W
W

8 8
8
8
D=4
2 W = 12
6 6
6
Production rate for windows




Production rate for windows




6




3D + 2W = 18
4
4 4
4




2 2 2
2




0 2 4 6 8 D 0 2 4 6 8 D 0 2 4 6 8 D 0 2 4 6 8 D
Production rate for doors Production rate for doors Production rate for doors Production rate for doors




TIP: ≥ of ≤ vervangen door = en zo de
rechte tekenen → kijken naar rechts of links inkleuren
TIP: focus op de snijpunten van met de x-as en y-as voor het tekenen van een schuine rechte
 Kijken groter of kleiner : het punt(0,0) invullen, wanneer de beperking klopt dan ligt dit punt in
het ‘goede’ gebied en dit dus inkleuren Production rate for windows



W
10




Het toegelaten gebied is alle beperkingen te samen , dit aanduiden op je grafiek → doel
3 D + 2 W = 18
8

D=4

tweede stap : het toegelaten gebied vinden Production rate
W 6 2 W =12

for windows
8


Stap 3 : doelfunctie tekenen 4


6 Feasible

 Random een gokje wagen zodat je de functie 2
region



kan tekenen
Feasible
4
region
P = 1500 = 300D + 500W


 Vb. 1500 = 300D + 500W, twee punten: D = 0 2
0 2 4
Production rate for doors
6 8 D




W=3&W=0D=5
0 2 4 6 8 D


3
Production rate for doors

, Stap 4 : optimale oplossing
 We moeten de doelfunctie rechte bewegen in de richting van de verbetering!
Production rate W
o Maximaliseren is dus omhoog,
for windows
minimaliseren omlaag in dit geval. 8

o Want meer D en W betekent meer winst P = 3600 = 300D + 500W
Optimal solution
 Nu zie je dat de optimale oplossing 2 deuren en 6
(2, 6)
ramen produceren is → hoogste mogelijke winst P = 3000 = 300D + 500W 6


 TIP: optimale oplossing gaat altijd op een grens
vallen, gaat nooit in het midden van het gebied Feasible
4
liggen, maar altijd ergens op de grens P = 1500 = 300D + 500W
region



2

!! Wat zouden we gaan doen als we willen minimaliseren
→ dan doelfunctie naar onder moeten verschuiven → dan 2
0 4 6 8 10 D
kwamen we in 0 deuren en 0 ramen → dan winst 0, is het Production rate for doors


minimaalste

INTERPRETING THE SOLUTION

De optimale oplossing is dus om 2 deuren en 6 ramen per week te produceren. Dit levert een maximale winst op van
3600$ per week.

Opmerking:
 Er is altijd een extreem punt dat optimaal is
 om een optimum te vinden, volstaat het om de extreme punten te zoeken, niet het hele haalbare gebied
 De grafische oplossing laat ook meteen zien welke beperkingen bindend zijn in het optimum
Een beperking = bindend in het optimum als ze met gelijkheid geldt in het optimum → =

Voorbeeld: oplossing ligt op het snijpunt van 2 rechten = 2 beperkingen → dus deze twee beperkingen zijn bindend
→ dit betekent dat we alle capaciteit gaan gebruiken die we hebben

Betekenis:
 De capaciteit van fabriek 2 en 3 gaat volledig opgebruikt zijn.
 Fabriek 1 wordt maar 2 van de 4 gebruikt.
 Belangrijk om weten voor bedrijven als de vraag komt waar ze hun productiecapaciteit zouden moeten
opschalen
!! Het is mogelijk om meer dan 1 optimale oplossing te bekomen. Het is
ook mogelijk om geen optimale oplossing te bekomen

Wanneer de doelfunctie niet overeen komt met één punt, maar met een
hele rechte → al deze punten zijn een optimale oplossing
 Eender welk punt je invult, je bekomt altijd dezelfde winst




Er is geen gemeenschappelijk
haalbaar gebied dat wordt gegenereerd door twee beperkingen samen
 We kunnen zelfs geen enkel punt identificeren dat aan de
beperkingen voldoet.
 Geen overlap tussen de toegelaten gebieden → dus geen
optimale oplossing.
4