Home   Lessen online Functies en Grafieken Onderwerpen  
kader_rand
Startpagina
Bravenet

Lineair programmeren

LP-Menu


Inleiding
Erg veel praktijkproblemen, die ontstaan bij het besturen en leiden van grote systemen van mensen, machines, materialen en geld in industrie, handel, overheid en defensie, hebben met lineair programmeren te maken. In de economie kan een groot aantal praktische beslissingsproblemen in de standaard LP-vorm worden gegoten. In verband hiermee is lineair programmeren ťťn van de bekendste en meest gebruikte wiskundige technieken. In de landbouw, de industrie, het transportwezen en bij militaire operaties vindt het lineair programmeren zijn toepassing. De Operationele Research is de wetenschap die zich hiermee bezig houdt.

Het LP-model bestaat uit een eerstegraads doelstellingsfunctie van tenminste twee beslissingsvariabelen, die gemaximaliseerd of geminimaliseerd moet worden onder een aantal beperkende voorwaarden. We noemen dit optimaliseren. De beperkende voorwaarden of restricties, waaraan moet worden voldaan, hebben de vorm van lineaire vergelijkingen of ongelijkheden. Voor het oplossen van het LP-probleem bestaat geen formule. Het probleem was tot 1947 onoplosbaar.

In 1947 kwam George B. Dantzig met een methode, de zogenaamde Simplex-methode, die het mogelijk maakte problemen met een willekeurig
aantal variabelen op te lossen. Hij ontwikkelde deze methode tijdens de
Tweede Wereldoorlog toen hij als wiskundige werkzaam was bij de Amerikaanse luchtmacht. Het Simplex-algoritme, de grootste 'bestseller" aller tijden in de Operations Research,  is een goed voorbeeld van een algoritmische oplossing van een wiskundig probleem. Het Simplex- algoritme is in een namiddag op een computer te programmeren. Dit levert echter nog geen bruikbaar LP-pakket op!


George B. Dantzig

 LP-pakketten zijn zeer grote programma's van duizenden regels die vele manjaren gekost hebben. Het Simplex-algoritme is daarin slechts een klein maar zťťr belangrijk onderdeel. Een LP-probleem met niet meer dan twee variabelen is behalve met de Simplex-methode ook makkelijk grafisch op te lossen. De grafische methode wordt in de meeste leerboeken voor wiskunde A behandeld.

In praktijkgevallen heeft een LP-probleem echter enkele tientallen tot honderden variabelen en restricties. De meeste computerfirma's hebben dan ook programma-pakketten ontwikkeld, waarmee LP-problemen kunnen worden opgelost, en die gebaseerd zijn op de Simplex-methode. Voor een uitgebreide behandeling van dit onderwerp wordt verwezen naar de diverse leerboeken. We zullen ons op deze website beperken tot een korte samenvatting van het standaard Simplex-algoritme.

Op deze website vind je het programma 'Lineair Programmeren op Internet'. Dit is een educatief programma waarmee je LP-problemen met de Simplex-methode kunt oplossen. Het programma is ook geschikt voor de zogenaamde "Big-M" methode. Het Simplex-tableau kan maximaal 10 vergelijkingen en 20 variabelen bevatten. Er kan een keuze gemaakt worden tussen:

- Basisoplossing opvragen
- Pivot-element opvragen
- Kolommen vegen
- Automatisch vegen (stap voor stap)
- Optimaliseren

Voor de matrixelementen van het Simplex-tableau mogen behalve getallen ook rekenkundige uitdrukkingen ingetypt worden. De berekende matrixelementen kunnen in de gebruikelijke computernotatie of in de vorm van breuken op het scherm afgebeeld worden. De ingevulde en berekende tableaus kunnen op schijf opgeslagen worden. In geval van twee beslissingsvariabelen kan een grafische weergave opgeroepen worden.

Het programma is ondermeer geschikt als ondersteuning bij de behandeling van het onderwerp lineair programmeren bij wiskunde A of bij economie. De opgaven uit de leerboeken voor wiskunde A en economie kunnen met dit programma gemaakt worden.


Omhoog

Wiskunde online ----- is speciaal ontworpen voor:
Microsoft  Internet Explorer 5.5 of hoger
Beeldschermresolutie minimaal 800◊600
JavaScript-Interpretatie ingeschakeld!
Bijgewerkt: