Lineair programmeren

Waar gaat het over?

Bij lineair programmeren gaat het om het optimaliseren van een lineaire doelfunctie waarbij alle voorwaarden lineaire ongelijkheden zijn. Deze problemen zijn grafisch op te lossen of met een algoritme: de simplexmethode.

Hoe werkt het?

Een school wil met een bepaalde jaargroep naar een voorstelling. Er zijn maximaal `150` plaatsen: een leerling kost 3 euro en een docent 5 euro. Er moet minstens per `15` leerlingen een docent aanwezig zijn, er zijn maximaal `15` docenten beschikbaar.
Noem je het aantal leerlingen $x$ en het aantal docenten $y$ dan kun je met lineair programmeren van de opbrengst $R\left(x,y\right)=3x+5y$ het maximum bepalen op het toegelaten gebied dat wordt bepaald door de randvoorwaarden $x+y\le 150$, $y\le 15$ en $x\le 15y$.
Beweeg daartoe de niveaulijn $3x+5y=R$ over het toegelaten gebied (domein) van $R\left(x,y\right)$.

Wie en wanneer?

Lineair programmeren werd voor het eerst besproken in het boek "Wiskundige methoden in de organisatie en planning van productie", door de Russische wiskundige Leonid Kantorovitsj.
Later kwamen Frank L. Hitchcock (na 1975) en met name George Dantzig (jaren '40 van de vorige eeuw) met een duidelijke aanpak van o.a. het transportprobleem.

Nog later ontwikkelden John von Neumann, Oscar Morgenstern en Tjalling Koopmans de theorie verder en legden ze verbanden met de speltheorie.