Lineair programmeren > De simplexmethode
12345De simplexmethode

Uitleg

Gegeven is de doelfunctie `W = 100x + 300y + 20z` met dezelfde randvoorwaarden als in Uitleg 1. De randvoorwaarden kun je met behulp van spelingsvariabelen vertalen naar een stelsel vergelijkingen. Toevoegen van de doelfunctie geeft:

`10x+20y+2z+s_1` `=` `2020`
`25x+100y+3z+s_2` `=` `7750`
`x+s_3` `=` `100`
`z+s_4` `=` `50`
`100x+300y+20z` `=` `W`

Werk vervolgens toe naar een uitdrukking als `W_(text(max)) - as_1 - bs_2 - cs_3 - ds_4 = W` voor de laatste vergelijking. Dan wordt meteen duidelijk welke spelingsvariabelen je `0` moet maken om `W = W_(text(max))` over te houden. Deze methode heet de simplexmethode. De Excel Oplosser maakt gebruik van deze methode.

Zet voor deze methode eerst het stelsel vergelijkingen om naar een zogenaamd simplextableau:

`x` `y` `z` `s_1` `s_2` `s_3` `s_4`
`10` `20` `2` `1` `0` `0` `0` `2020`
`25` `100` `3` `0` `1` `0` `0` `7750`
`1` `0` `0` `0` `0` `1` `0` `100`
`0` `0` `1` `0` `0` `0` `1` `50`
`100` `300` `20` `0` `0` `0` `0` `0`

In de eerste rij staan de variabelen en in de laatste rij staat
`100x+300y+20z-W = 0` . De `W` is niet in de tabel opgenomen. De bedoeling is om de `0` rechtsonder in de tabel zo groot mogelijk negatief te krijgen. In dat geval is `text(-)W` zo groot mogelijk negatief en is `W` maximaal.

In de onderste rij is `300` het grootste getal, begin daarom met het op `0` krijgen van dit getal. Bepaal in elke rij in de kolom met het getal `300` de verhouding tussen de coëfficiënten en de getallen in de laatste kolom. Neem de rij waarbij je de kleinste (niet negatieve) verhouding hebt. Dit geeft `2020/20 = 101` en `7750/100 = 77,5` (bij de andere deel je door `0` ). Bij de derde rij krijg je de kleinste verhouding.
De cel met het getal `100` heeft daarom een afwijkende kleur.

Deel nu deze hele rij door `100` , dit geeft `0,25x+y+0,03z+0,01s_2 = 77,50` . Trek deze rij zo vaak als nodig is van de andere rijen af, zodat overal in de andere rijen nullen staan op de plaats waar in de tweede rij de `1` staat. Dit geeft:

`x` `y` `z` `s_1` `s_2` `s_3` `s_4`
`5` `0` `1,4` `1` `text(-)0,2` `0` `0` `470`
`0,25` `1` `0,03` `0` `0,01` `0` `0` `77,50`
`1` `0` `0` `0` `0` `1` `0` `100`
`0` `0` `1` `0` `0` `0` `1` `50`
`25` `0` `11` `0` `text(-)3` `0` `0` `text(-)23250`

Voer nu weer hetzelfde uit met de grootste coëfficiënt op de onderste rij van dit simplextableau. Ga net zolang door, totdat de onderste rij alleen maar getallen bevat die negatief zijn.

Het derde en laatste tableau wordt:

`x` `y` `z` `s_1` `s_2` `s_3` `s_4`
`1` `0` `0` `0,2` `text(-)0,04` `0` `text(-)0,28` `80`
`0` `1` `0` `text(-)0,05` `0,02` `0` `0,04` `56`
`0` `0` `0` `text(-)0,2` `text(-)0,04` `1` `0,28` `20`
`0` `0` `1` `0` `0` `0` `1` `50`
`0` `0` `0` `text(-)5` `text(-)2` `0` `text(-)4` `text(-)25800`

In de laatste rij staat `text(-)5s_1-2s_2-4s_4-W = text(-)25800` . Kies nu `s_1 = s_2 = s_4 = 0` , dan staat de rest van de variabelen vast: `x = 80, y = 56, z = 50, s_3 = 20` en `W = 25800` .

Opmerking: je kunt in de situatie komen dat alle getallen in de onderste rij niet positief zijn, maar dat je toch geen optimale oplossing hebt gevonden. Het probleem is dan dat nog niet alle variabelen vaststaan.

Opgave 2

Bekijk de simplextableaus in Uitleg 2.

a

Geef het tweede simplextableau.

b

Reken na dat het derde simplextableau de laatste is.

Opgave 3

Stel je voor dat je `W = 25000 - x - y - z` wilt minimaliseren onder dezelfde randvoorwaarden als in Uitleg 2.

a

Wat moet er dan in je werkwijze veranderen?

b

Bereken het minimum van deze doelfunctie met behulp van de simplexmethode. Geef ook de bijbehorende waarden van `x, y` en `z` .

verder | terug