WisFaq!

Pivotering

Ik ben momenteel bezig met lineaire problemen en hun duale probleem. Hierin wordt gesproken over het omzetten van je probleem in een tableau en vervolgens wordt er iets gedaan met pivotering. Wat is pivotering?

mvg,

Christine

Christine
21-3-2008

Antwoord

Beste Christine,

Een LP is van de vorm:

minimize x=(x₁ x₂ ... x_i)
subject to x_i0 ("i)

Of je kunt het LP in deze vorm omzetten (max x -- min -x)

Een veelgebruikt systeem om een LP op te lossen is het tableau-systeem. Een voorbeeld van een LP in tableau vorm staat op http://nl.wikipedia.org/wiki/Simplexmethode#Het_Simplex-Tableau.

De bedoeling met zo'n tableau is dat je een startoplossing neemt voor x zodanig dat het een oplossing is voor het probleem. Dit hoeft (kan wel) niet een optimale oplossing te zijn. Vervolgens wordt d.m.v. een pivotering (1 stap in de simplex methode) een nieuwe oplossing verkregen, die al een betere x heeft dan waarmee je begonnen bent. Als je maar vaak genoeg een pivotering uitvoert (een simplex-stap), op een gegeven moment vindt je met deze pivotering geen betere x en dan weet je dat de x die je hebt, de optimale oplossing is voor je LP.

Ik hoop dat dit antwoord duidelijk genoeg is voor je.

Groetjes,

Percy Dobbelsteyn

P.S. Voor lineaire programmeringsproblemen op te lossen kun je MS Excel gebruiken. Deze doet alle pivoteringsstappen voor je en geeft je de optimale oplossing. Dan hoef je ze niet zelf te doen ;-). Als je hier meer hulp mee nodig hebt, dan kun je me emailen:
percy@dobbelsteyn.nl

Zie Simplex Tableau [http://nl.wikipedia.org/wiki/Simplexmethode#Het_Simplex-Tableau]

pd
28-3-2008