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. |