Den Simplex algoritmen är en metod för att lösa linjära programmeringsproblem. På ren svenska är det som används för att nå ett mål och samtidigt ha begränsningar. Eftersom detta är matte, vi har att göra med siffror och formler bara använda addera, subtrahera och multiplicera (det är därför det kallas linjär programmering).
Typiska användningsområden för simplex-algoritmen är att hitta den rätta blandningen av ingredienser till lägsta kostnad (målet). Om ingredienserna är mat, skulle de begränsningar ska ha minst så många kalorier, Simplex algoritmen är tillämpliga på mycket mer än mat så mycket protein, fett, kolhydrater, vitaminer, mineraler, etc. Naturligtvis.
Steg
- 1Först måste du titta på vad du försöker att träna. Har du redan begränsningen du maximerar / minimera och ojämlikhet?
- 2När du har dessa måste du införa slackvariabler till olikheterna. Slackvariabler vänder ojämlikheter i ekvationer och oftast använda bokstäverna S och framåt (även om du kan använda vilken bokstav du vill), till exempel:
- 2y +4 x <= 8 blir 2y +4 x + s = 8
- 6år +2 x <= 28 blir 6år +2 x + t = 28
- 3Begränsningen bör vara i form p = x + y (+ z) som du behöver för att ordna att bli 0 = PXY (-z). till exempel:
- P = 2x +2 y blir 0 = P-2x-2y
- 4När du har dina data som du behöver för att bygga tablån. Detta är konstruerat enligt följande:
| P | x | y | (Etc) | s | t | (Etc) | l | ekvation |
|---|
- 1Därefter måste du lägga dina data i tablån. Din första raden blir vad du maximera, raderna under restriktioner. Om du har den bokstaven wat går i den raden numret går in i den kolumnen. Om brevet inte det sätta en 0.
| P | x | y | s | t | l | ekvation |
|---|---|---|---|---|---|---|
| 1 | -2 | -2 | 0 | 0 | 0 | (1) |
| 0 | 4 | 2 | 1 | 0 | 8 | (2) |
| 0 | 2 | 6 | 0 | 1 | 28 | (3) |
- 1Nu det roliga biten. Välj en kolumn, varje kolumn, så länge som det översta numret är negativ (observera att du inte kan använda l) Av hänsyn till det exempel jag kommer att använda x, men om du är uttråkad kan du använda y bara för att vara annorlunda (om du har en hel del kolumner att välja mellan skulle jag rekommendera att börja till vänster, gör livet enklare).
- För varje rad (som numret i din valda kolumnen är positivt) dividera antalet i L kolumnen med antalet i din valda kolumnen.
- För den rad som gav minsta värdet, ring numret i din valda kolumnen. (I mitt exempel skulle det vara 4) Detta nummer kallas pivot.
- 2På denna punkt måste du dra en linje i din tablå så att du kan skriva in den första iteration. Lämna en rad för ekvation 4 och dividera (2) genom svängtappen (i detta fall fyra) sedan skriva att in i utrymmet för (5)
- 3Du måste nu göra alla värden i x kolumnen (bortsett från din pivot linje) är lika med 0. Du gör detta genom att kombinera lämpliga multiplar av leden med den ursprungliga ekvationen för varje linje. Till exempel (4) = (1) 0,5 (2) När du har gjort detta din tablå bör se ut så här:
| P | x | y | s | t | l | ekvation |
|---|---|---|---|---|---|---|
| 1 | -2 | -2 | 0 | 0 | 0 | (1) |
| 0 | 4 | 2 | 1 | 0 | 8 | (2) |
| 0 | 2 | 6 | 0 | 1 | 28 | (3) |
| 1 | 0 | -1 | 0,5 | 0 | 4 | (4) = (1) 0,5 (2) |
| 0 | 1 | 0,5 | 0,25 | 0 | 2 | (5) = (2) / 4 |
| 0 | 0 | 5 | -0,5 | 1 | 24 | (6) = (3) -0,5 (2) |
- 1Om du fortfarande har negativa tal på din översta raden (inte inklusive kolumn l) Upprepa steg 6-8 tills alla dina översta raden är positivt. När detta är fallet att du har avslutat din simplex problem.
- 2Du läser lösningen på ditt simplex problemet mycket enkelt. Ignorera slackvariabler. Den sista (l)-kolonn (av den slutliga iterationen) innehåller värdena för funktionen (P) och icke-noll-variabler.
Tips
- När du kan använda Simplex bara vara glad att du kan använda det och gå skryta till alla dina vänner som inte kan. Aldrig under några omständigheter försöka skriva en Google om det.
Varningar
- Endast gälla situationer där decimala mängder vettigt. En tredjedel av en volleyboll eller halv häst är inte vettigt.
- Namnet är vilseledande. Simplex är inte enkelt. Normalt är det en avancerad nivå ämne inom Operations Research, även om vissa tenta styrelser även inkludera det i A-nivå Maths modulen D2.
- Det är väldigt lätt att göra misstag och mycket svårt att hitta dem. Stressa inte Simplex!
- Kan resultera i stora mängder av stress. I forskarskolan i simplex-algoritmen görs manuellt av eleverna bara en gång. Från och med då är det gjort på datorer.
- Verkliga livet använder för simplex-algoritmen är mycket viktiga för verksamheten (deras svar kan spara miljoner), men de är också enorma och endast görs på datorer.
- Den "svaret" bör ibland avvisas den politiska, sociala eller psykologiska skäl. Linjär programmering appliceras på utvecklingsländerna i utformningen av "mix" av branscher i ekonomin. Ett "svar" av en enskild bransch eller jordbruksgrödor för ett land är bristfällig på stabilitet grunder.
Saker du behöver
- En penna / penna
- Papper
- Ruler
- Calculator (om du inte är väldigt bra med siffror)