Lineair programmeren > De simplexmethodeUitleg
Gegeven is de doelfunctie `W = 100x + 300y + 20z` onder de randvoorwaarden:
-
`0 le x le 100`
-
`y ge 0`
-
`0 le z le 50`
-
`10x + 20y + 2z le 2020`
-
`25x + 100y + 3z le 7750`
Je wilt `W` maximaliseren. De randvoorwaarden `x ge 0` , `y ge 0` en `z ge 0` worden als standaard beschouwd en daar let je verder niet meer op. De overige ongelijkheden noteer je onder elkaar in de vorm `ax + by + cz le d` :
|
`10x+20y+2z` |
`le` |
`2020` |
|
|
`25x+100y+3z` |
`le` |
`7750` |
|
|
`x` |
`le` |
`100` |
|
|
`z` |
`le` |
`50` |
Van deze ongelijkheden kun je vergelijkingen maken door zogenaamde "spelingsvariabelen" `s_1` , `s_2` , enzovoort in te voeren. Deze spelingsvariabelen zijn positief of `0` . Bijvoorbeeld de ongelijkheid `10x + 20y + 2z le 2020` wordt dan `10x + 20y + 2z + s_1 = 2020` .
Als je ook de doelfunctie toevoegt, geeft dit:
| `10x+20y+2z+s_1` | `=` | `2020` | |
| `25x+100y+3z+s_2` | `=` | `7750` | |
| `x+s_3` | `=` | `100` | |
| `z+s_4` | `=` | `50` | |
| `100x+300y+20z` | `=` | `W` |
Het gaat hierbij om het bepalen van het maximum van `W` . Dat doe je door in het gevonden stelsel van vijf vergelijkingen met zeven variabelen bij de onderste vergelijking (altijd de doelfunctie) de variabelen `x` , `y` en `z` weg te werken met behulp van de vergelijkingen erboven.
Werk daarbij toe naar een uitdrukking als `W_max -as_1 -bs_2 - cs_3 - ds_4 = W` voor de laatste vergelijking. Je ziet dan meteen welke spelingsvariabelen je `0` moet maken om `W = W_max` over te houden.
Bekijk de vijf vergelijkingen met zeven variabelen in
Schrijf de eerste twee vergelijkingen in de vorm `y = ...`
Je gaat één van beide vergelijkingen bij a vervolgens in de andere voorwaarden substitueren. Omdat je binnen het toegestane gebied moet blijven, neem je daarvoor de vergelijking met het kleinste positieve constante getal.
Vervang in elk van de andere vergelijkingen `y` door de uitdrukking `77,5 - 0,25x - 0,03z - 0,01s_2` . Schrijf het nieuwe stelsel van vijf vergelijkingen op.
Als het goed is wordt je doelfunctie
`23250 + 25x + 11z - 3s_2 = W`
.
Omdat nu de grootste positieve coëfficiënt die van
`x`
is, ga je vervolgens de
`x`
wegwerken.
Schrijf de eerste vier vergelijkingen in de vorm `x = ...` als dat mogelijk is. Welke heeft de kleinste positieve constante?
Gebruik de vergelijking met de kleinste positieve constante die je bij c hebt gevonden.
Vervang nu in elke vergelijking `x` door de gevonden uitdrukking. Schrijf het nieuwe stelsel van vijf vergelijkingen op.
De doelfunctie (onderste vergelijking) heeft nu nog alleen maar de `z` om weg te werken. Ook nu moet je de eerste vier vergelijkingen allemaal in de vorm `z = ...` schrijven en de vergelijking met de kleinste positieve constante gebruiken. Dat is `z = 50 - s_4` .
Vul in elke vergelijking voor `z` deze uitdrukking in. Schrijf het nieuwe stelsel van vijf vergelijkingen op.
Bekijk nu de doelfunctie. Daarin komen alleen de spelingsvariabelen voor.
Welke spelingsvariabelen moet je gelijk stellen aan `0` om `W` maximaal te krijgen? Hoeveel bedraagt die maximale waarde van `W` en bij welke waarden van `x` , `y` en `z` treedt hij op?