Om erachter te komen de grootste hoeveelheid geld die kon je met enkele beperkingen, kunt u de simplexmethode. In 1947, oorspronkelijk ontdekt door de luchtmacht ingenieur George B. Dantzig, is de simplexmethode een lineaire programmering methode die gemaximaliseerd (of minimaliseert) een functie in de vorm van lineaire gelijkheden beperkingen. Geometrisch, formuliergebied de ongelijkheden een polygonal. De simplexmethode probeert alle de hoekpunten van deze regio totdat het vindt enerzijds dat de functie maakt de grootste waarde aannemen.
Bepalen of het probleem een standaard maximalisatie probleem is. In dit soort problemen, moet de volgende voorwaarden worden voldaan: de functie moet worden gemaximaliseerd, de constanten in de ongelijkheden moeten alle niet-negatieve, de variabelen moeten alle niet-negatieve en de ongelijkheden moeten kleiner dan of gelijk aan. Bijvoorbeeld, is de volgende een standaard maximalisatie probleem:
Maximaliseren van F = 5 x + 6j restricties
4 x + 2y<=>=>
3 x + y<=>=>
x + 2y<=>=>
waarbij x en y zijn beide niet-negatief.
Omzetten elke ongelijkheid in een gelijkheid door een slappe variabele toe te voegen aan elke ongelijkheid. Bijvoorbeeld na het toevoegen van toegestane variabelen, de ongelijkheden worden:
4 x + 2y + u = 10
3 x + y + v = 5
x + 2y + w = 8
Zorgen ervoor dat alle van de vergelijkingen, met inbegrip van de functie, hebben de variabelen aan de linker kant en de constanten aan de rechterkant. Bijvoorbeeld, in het voorbeeld allemaal de vergelijkingen al de juiste vorm met uitzondering van de functie. Herschrijven de functie zoals aangegeven:
-5 x - 6j + F = 0
Het stelsel van vergelijkingen converteren naar een matrix die de eerste enkelzijdige tableau genoemd. Elke rij van de matrix komt overeen met de coëfficiënten van de vergelijkingen. Zet de getallen van de functie in de onderste rij. Bijvoorbeeld, is de eerste enkelzijdige tableau van het voorbeeld:
x y u v w F
4 2 1 0 0 0 10
3 1 0 1 0 0 5
1 2 0 0 1 0 8
-5 -6 0 0 0 -1 0
In de eerste enkelzijdige tableau vindt u de meest negatieve indicator. De "indicatoren" zijn de getallen in de bodem (met uitzondering van het onderste getal). In het voorbeeld is de meest negatieve indicator -6 in de tweede kolom. Deze kolom heet de draaikolom.
Het vinden van de kleinste verhouding in de draaikolom. De verhoudingen van de vorm door het nemen van het meest rechtse getal in elke rij en onder te verdelen door een overeenkomstige waarde in de draaikolom. Doe dit voor elke rij met uitzondering van de rij van de indicator. Bijvoorbeeld, zijn de verhoudingen in het voorbeeld:
10/2 = 5
5/1 = 5
8/2 = 4
De kleinste verhouding in de draaikolom is 4, die correspondeert met de derde rij.
Gebruik rij matrixoperaties alle andere getallen in de kolom van de draaitabel wijzigen in 0. Bijvoorbeeld, de eerste rij van de pivot-rij te vormen van een 0 in de eerste rij af te trekken. Aftrekken tweemaal de tweede rij door de pivot-rij te vormen van een 0 in de tweede rij. Het resultaat is hieronder weergegeven:
x y u v w F
3 0 1 0-1 0 2
5 0 0 2-1 0 2
1 2 0 0 1 0 8
-8 0 0 0 -3-1-24
Controleer of alle indicatoren niet-negatief zijn. Zo ja, dan wordt u gedaan. Ga anders door naar stap 5.
De oplossing van de uiteindelijke matrix afgelezen. Bijvoorbeeld, als de uiteindelijke matrix is
x y u v w F
1 0 0 3 4 0 4
0 3 0 4 4 0 6
0 0 2 4 3 0 4
0 0 0 3 3 1 5
Kijk voor de kolommen met een enkele ander getal dan nul. Deze kolom geeft u de waarde van die variabele in de oplossing. Om te zoeken naar de waarde, het meest rechtse getal delen door het aantal niet-nulzijnde. In deze laatste matrix is de oplossing:
x = 4/1 of 4
y = 6/3 of 2
u = 4/2 of 2
en de maximale waarde van de functie F is 5.
- Een slappe variabele per ongelijkheid toe te voegen.
- In stap 3, houden de functie variabele positief.
- In stap 4, elke rij van de matrix komt overeen met de coëfficiënten van de vergelijkingen. Bijvoorbeeld, sinds 4 x + 2y + u = 0 kan worden geschreven als 4 x + 2y 1u + 0v + 0w + 0F = 10, deze vergelijking wordt 4 2 1 0 0 0 10.
- In stap 5, in het geval van een gelijkspel, de meest linkse indicator gebruikt.
- In stap 6, het negeren van ratio's, die niet-gedefinieerde (deling door 0) of negatief. Als alle ratio's worden genegeerd, heeft het probleem geen maximale oplossing.
- Kies in stap 6, als twee ratio's beide de kleinste zijn, de verhouding in de hoogste rij.
- In stap 7, Voeg nooit een negatieve veelvoud van de pivot-rij.