Halfvlakken, lineair programmeren

Een halfvlak is een term die we gebruiken bij het praten over vlakken in een assestelsel. Je kan je voorstellen dat het totale vlak, uitgaande van de x- en y-as, oneindig groot is. Als je nu een lijn in dit vlak trekt, verdeel je dit oneindige vlak in twee helften. Dit noemen we de halfvlakken. Afhankelijk van waar de lijn heen gaat, heb je halfvlakken aan weerskanten van de lijn.

Herkenning van halfvlakken

De formule 2x + 6y = 18 geeft een lineair verband aan dat een lijn op de grafiek zal vormen. Maar we willen hier niet over vergelijkingen praten, we willen over ongelijkheden praten. Deze vormen de basis voor de halfvlakken. In plaats van te bepalen wat de waarde van x en y zijn, willen we weten waar ze groter of kleiner zijn. De ongelijkheden 2x + 6y < 18 en 2x + 6y > 18 geven respectievelijk de halfvlakken onder en boven de lijn aan.

Lineair programmeren

Bij lineair programmeren onderzoeken we een situatie waar er meerdere beperkende voorwaarden zijn. Deze voorwaarden bepalen het gebied waarin we kunnen werken, ook wel het "ingeschreven gebied".

Laten we dit illustreren met een voorbeeld van een fabriek die koekjes (k) en chocolaatjes (c) produceert. Er zijn minimale productie-eisen voor beide (k > 200 en c > 100). Daarnaast is er een maximale opslagmogelijkheid van 600 kilo chocola (c < 600) en zijn er beperkingen qua beschikbare mankracht (10k + 10c < 12000 en 0.6k + 0.3c < 570). Deze voorwaarden kunnen allemaal in een assenstelsel geschetst worden, zie de afbeelding hieronder. Het gebied dat ingesloten wordt door de lijnen is het ingeschreven gebied.

Maximalisering van winst

Het laatste aspect van lineair programmeren dat we willen verkennen is het optimaliseren, in dit geval het maximaliseren van winst. De winst uit het koekje en de chocolade kan worden uitgedrukt als 2,3k + 6,9c. Het doel is om nu het ingeschreven gebied te onderzoeken en de productiekosten (k en c) te vinden die deze winst maximaliseren.

We doen dit door een lijn te trekken, de "winstlijn", en deze lijn omhoog te verplaatsen tot het snijpunt met de grenslijn van het ingeschreven gebied. De winst bij dit snijpunt is de maximale winst. De winstlijn kan worden geschetst door één variabele vast te zetten. Hiervoor kan je bijvoorbeeld het punt op de y-as (c) op 200 nemen. Dit is dus het coördinaat (0,200). Als we dit in de formule voor de winst invullen, krijgen we W = 1380. Met deze gegevens kunnen we ook een bijbehorende waarde voor k vinden. We hebben nu namelijk 1380 = 2,3k + 6,9 · 200. Als we dit oplossen naar k krijgen we k = 600. Door de punten (0,200) en (600,0) kan een lijn geschetst worden. Deze lijn is de winstlijn. Om deze winstlijn te optimaliseren, moeten we de winstlijn evenwijdig doortrekken. De optimale winstlijn gaat in dit geval door het coördinaat (600,600). Dit is weergegeven in onderstaande afbeelding.