xA 0 xB 0 xc 0
dan heeft een lineaire waardefunctie
F xA 2xb 3xc
in de zo begrensde oplossingsruimte een maximum,
en wel F =33 voor (xA, xB, xc(0, 0, 11Zie afb.
4. De optimale oplossing ligt in dit geval op de
rand, zelfs op een hoekpunt van de oplossings
ruimte. We voegen nog twee voorwaarden toe:
xA 8
xfl 2xc^13 (2)
en zoeken weer het maximum voor de waarde
functie. Onderzoek van afb. 5 leidt tot de conclusie,
dat nu alle oplossingen op de snijlijn van (1) en (2)
optimaal zijn, met een maximale F 24. Een lineaire
waardefunctie leidt kennelijk niet altijd tot één
enkele optimale oplossing, wat een kwadratische
waardefunctie met gelijkheden als voorwaarden,
zoals we gezien hebben, wel doet.
Hoe los je nu een probleem met een lineaire waarde
functie numeriek op? Differentiëren helpt niet, om
dat de waardefunctie geen vrij extreem heeft.
Noodzakelijk is daarom een stapsgewijze oplossings
methode. Voor verschillende soorten problemen
bestaan er verschillende soorten rekenmethoden,
die alle berusten op de veronderstelling, dat vanuit
een min of meer willekeurige beginoplossing de
optimale oplossing kan worden gevonden door een
eindig aantal stappen te doen waarin de waarde
functie steeds toeneemt (of afneemt wanneer in het
optimum de waardefunctie een minimale waarde
moet aannemen).
Ik zal in het volgende proberen een oplossings
methode te schetsen, uitgaande van de in afb. 5
weergegeven situatie. Voor uitvoeriger gegevens
over de rekentechniek verwijs ik graag naar de
literatuur.
4.2 Lineair programmeren - de simplexmethode
Gegeven zijn de voorwaarden
xA x„+ xc 11
xA B
xB 2xc 13
met alle xt niet-negatief
en de waardefunctie
F xA 2xb 3xc
die onder de gegeven voorwaarden moet worden
gemaximeerd.
De eerste handeling is van de ongelijkheden gelijk
heden te maken door aan de tweede en derde voor
waarde de grootheden xK en xL (beide 0) toe te
voegen. Deze zouden kunnen worden geïnterpre
teerd als onderbezetting of iets dergelijks. De xK en
xL leveren voor de waardefunctie F niets op maar
kosten ook niets, en worden daarom met een co-
efficiënt 0 geplaatst bij de componenten van F. Zie
tableau I.
We zouden nu kunnen gaan rekenen, ware het niet
dat in de rekentechniek (de zgn. simplexmethode)
de eis wordt gesteld dat de oplossing (xA, xB, xc)
(0, 0, 0) tot de oplossingsruimte behoort. Door de
eerste voorwaarde kan hier niet aan worden vol
daan, maar het probleem kan worden opgelost met
de invoering van een grootheid xM (ook 0),
waarmee een zekere afwijking van de eerste voor
waarde wordt aangegeven. Het is natuurlijk niet de
bedoeling dat deze afwijking in de eindoplossing
komt en daarom wordt xM met een zeer grote co-
efficiënt M in de waardefunctie geplaatst. In
tableau I e.v. heb ik dit deel van de waardefunctie
even apart gezet onder de naam S, van „straf-
punten". S heet dan ook boetefunctie.
Bij de verdere berekeningen moet op een gegeven
moment xM 0 wordenwe zijn dan in de oorspronke
lijke oplossingsruimte aangekomen en kunnen de
xM verder gevoeglijk weglaten.
In het nu volledig verklaarde tableau I is de begin
oplossing direct af te lezen als we nog weten dat
(behoudens vele uitzonderingen) alle variabelen met
een coëfficiënt 0 in de waardefunctie de waarde 0
moeten aannemen en alle variabelen met een co-
efficiënt 0 een positieve waarde. De beginoplos
sing is (xA, xB, xc, xK, xL, xM) (0, 0, 0, 8, 13, 11).
Deze ligt buiten de bedoelde oplossingsruimte en
we krijgen dan ook 11M strafpunten. F heeft in
de beginoplossing de waarde 0. Merk op, dat er in
de beginoplossing 3 variabelen met waarden 0
zijn, evenveel als er voorwaarden zijn (de niet-
6
ngt 73
