Hvis du trenger å løse et lineært programmeringsproblem ved hjelp av simplekstabeller, vil vår onlinetjeneste være til stor hjelp for deg. Simplexmetoden innebærer en sekvensiell oppregning av alle toppunktene i rekkevidden av tillatte verdier for å finne toppunktet der funksjonen har en ekstrem verdi. På det første trinnet finner man en løsning, som forbedres ved hvert påfølgende trinn. Denne løsningen kalles grunnleggende. Her er en sekvens av handlinger når du løser et lineært programmeringsproblem ved hjelp av simpleksmetoden:
Første skritt. I den kompilerte tabellen må du først og fremst se på kolonnen med gratis medlemmer. Hvis det er negative elementer i det, er det nødvendig å fortsette til det andre trinnet, hvis ikke, så til det femte.
Andre trinn. På det andre trinnet er det nødvendig å bestemme hvilken variabel som skal ekskluderes fra grunnlaget, og hvilken som skal inkluderes, for å beregne simplekstabellen på nytt. For å gjøre dette, se gjennom kolonnen med gratis medlemmer og finn et negativt element i den. Linjen med et negativt element vil bli kalt ledende linje. I den finner vi det maksimale negative elementet i absolutt verdi, den tilsvarende kolonnen - følgeren. Hvis det er negative verdier blant de gratis medlemmene, men ikke i den tilsvarende raden, vil en slik tabell ikke ha noen løsninger. Ved å endre i ledende rad ekskluderes den i gratis medlemskolonnen fra grunnlaget, og variabelen som tilsvarer ledende kolonne inkluderes i grunnlaget.
Tabell 1.
| grunnleggende variabler | Gratis medlemmer i begrensninger | Ikke-basisvariabler | |||||
| x 1 | x 2 | ... | x l | ... | x n | ||
| x n + 1 | b 1 | en 11 | en 12 | ... | en 1l | ... | en 1n |
| x n + 2 | b 2 | en 21 | en 22 | ... | en 2l | ... | en 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + r | b2 | en r1 | en r2 | ... | en rl | ... | en rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + m | b m | en m1 | en m2 | ... | en ml | ... | en mn |
| F (x) maks | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Tredje trinn. På det tredje trinnet regner vi om hele simplekstabellen ved hjelp av spesielle formler, disse formlene kan sees ved hjelp av.
Fjerde trinn. Hvis negative elementer etter omberegning forblir i kolonnen med gratis medlemmer, gå til det første trinnet, hvis det ikke er slike, så til det femte.
Femte trinn. Har du kommet til det femte trinnet, så har du funnet en løsning som er akseptabel. Dette betyr imidlertid ikke at det er optimalt. Det vil bare være optimalt hvis alle elementene i F-raden er positive. Hvis dette ikke er tilfelle, er det nødvendig å forbedre løsningen, som vi finner den ledende raden og kolonnen for neste omberegning i henhold til følgende algoritme. Til å begynne med finner vi det minste negative tallet på linje F, unntatt funksjonsverdien. Kolonnen med dette nummeret vil være den ledende. For å finne den ledende raden finner vi forholdet mellom det tilsvarende frie elementet og elementet fra den ledende kolonnen, forutsatt at de er positive. Minimumsforholdet lar deg bestemme den ledende raden. Vi regner om tabellen igjen ved å bruke formlene, dvs. gå til trinn 3.
Et eksempel på å løse problemet ved simpleksmetoden vurderes, samt et eksempel på å løse det dobbelte problemet.
Oppgaven
For salg av tre varegrupper har en kommersiell virksomhet tre typer begrensede materielle og økonomiske ressurser i mengden b 1 = 240, b 2 = 200, b 3 = 160 enheter. På samme tid, for salg av 1 gruppe varer for 1 tusen rubler. omsetningen brukes på ressursen av den første typen i mengden 11 = 2 enheter, ressursen til den andre typen i mengden 21 = 4 enheter, ressursen av den tredje typen i mengden 31 = 4 enheter. For salg av 2 og 3 grupper av varer for 1 tusen rubler. omsetningen brukes, henholdsvis ressursen av den første typen i mengden a 12 = 3, a 13 = 6 enheter, ressursen av den andre typen i mengden a 22 = 2, a 23 = 4 enheter, ressursen av den tredje typen i mengden 32 = 6, en 33 = 8 enheter ... Fortjeneste fra salg av tre grupper av varer for 1 tusen rubler. omsetningen er henholdsvis c 1 = 4, c 2 = 5, c 3 = 4 (tusen rubler). Bestem det planlagte volumet og strukturen på omsetningen slik at fortjenesten til handelsbedriften er maksimal.
Til den direkte oppgaven med å planlegge omsetning, løses ved simpleksmetoden, sminke dobbel oppgave lineær programmering.
Installere konjugerte par av variabler direkte og doble oppgaver.
I henhold til konjugerte par av variabler, fra løsningen av det direkte problemet, oppnå dobbel problemløsning i hvilken ressursvurdering brukt på salg av varer.
Løse problemet ved hjelp av simpleksmetoden
La x 1, x 2, x 3 - antall solgte varer, i tusen rubler, henholdsvis 1, 2, 3 - gruppene hennes. Da har den matematiske modellen av oppgaven formen:F = 4 x 1 + 5 x 2 + 4 x 3 -> maks
0))) (~) "title =" (! LANG: delim (lbrace) (matrise (4) (1) ((2x_1 + 3x_2 + 6x_3 = 0))) (~)">!}
Vi løser simpleksmetoden.
Introduser tilleggsvariabler x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 for å konvertere ulikheter til likheter.
Ta x 4 = 240 som grunnlag; x 5 = 200; x 6 = 160.
Vi legger inn dataene simplex bord
Enkel tabell nummer 1
Objektiv funksjon:
0 240 + 0 200 + 0 160 = 0
Vi beregner poengsummene ved å bruke formelen:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Siden det er negative vurderinger, er ikke planen optimal. Laveste karakter:
Vi introduserer variabelen x 2 i grunnlaget.
Vi definerer en variabel som forlater grunnlaget. For å gjøre dette, finn det minste ikke-negative forholdet for kolonnen x 2.
= 26.667
Minste ikke-negative: Q 3 = 26,667. Vi utleder variabelen x 6 fra grunnlaget
Del 3. rad med 6.
Fra den første linjen trekker du den tredje linjen, multiplisert med 3
Fra den andre raden trekker du den tredje raden, multiplisert med 2
Vi beregner:
Vi får et nytt bord:
Enkel tabell nummer 2
Objektiv funksjon:
0 160 + 0 440/3 + 5 80/3 = 400/3
Vi beregner poengsummene ved å bruke formelen:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 = 5/6
Siden det er et negativt estimat Δ 1 = - 2/3, er ikke planen optimal.
Vi introduserer variabelen x 1 i grunnlaget.
Vi definerer en variabel som forlater grunnlaget. For å gjøre dette, finn det minste ikke-negative forholdet for kolonnen x 1.
Den minste ikke-negative: Q 3 = 40. Vi utleder variabelen x 2 fra grunnlaget
Del 3. rad med 2/3.
Fra 2. rad trekker du 3. rad, multiplisert med 8/3
Vi beregner:
Vi får et nytt bord:
Enkel tabell nummer 3
Objektiv funksjon:
0 160 + 0 40 + 4 40 = 160
Vi beregner poengsummene ved å bruke formelen:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 = 1
Siden det ikke er negative evalueringer, er planen optimal.
Løsningen på problemet:
Svar
x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F maks = 160Det vil si at det er nødvendig å selge varene av den første typen i mengden 40 tusen rubler. Det er ikke nødvendig å selge varer av 2. og 3. type. I dette tilfellet vil maksimal fortjeneste være F max = 160 tusen rubler.
Løsning på det doble problemet
Det doble problemet er:
Z = 240 y 1 + 200 y 2 + 160 y 3 -> min
Tittel = "(! LANG: delim (lbrace) (matrise (4) (1) ((2y_1 + 4y_2 + 4y_3> = 4) (3y_1 + 2y_2 + 6y_3> = 5) (6y_1 + 4y_2 + 8y_3> = 4) (y_1, y_2, y_3> = 0))) (~)">!}
Introduser tilleggsvariabler y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 for å konvertere ulikheter til likheter.
Konjugerte par av variabler av de direkte og doble problemene har formen:
Fra den siste simpleksen i tabell nr. 3 i det direkte problemet finner vi løsningen på det doble problemet:
Z min = Fmaks = 160;
y1 = A4 = 0; y2 = Δ5 = 0; y3 = A6 = 1; y4 = Δ1 = 0; y5 = A2 = 1; y6 = A3 = 4;
Likte? Bokmerke
Løse problemer ved hjelp av simpleksmetoden: netteksempler
Mål 1. Selskapet produserer baderomshyller i to størrelser - A og B. Salgsagenter anslår at det kan selges opptil 550 hyller på markedet per uke. Hver hylletype A krever 2 m2 materiell, og hylletype B krever 3 m2 materiell. Bedriften kan motta inntil 1200 m2 materiell per uke. For produksjon av en hylle av type A kreves det 12 minutters maskintid, og for produksjon av en hylle av type B - 30 minutter; maskinen kan brukes 160 timer i uken. Hvis fortjenesten fra salg av type A-hyller er 3 valutaenheter, og fra salg av type B-hyller - 4 den. enheter, hvor mange hyller av hver type skal produseres i uken?
Mål 2. Løs det lineære programmeringsproblemet ved å bruke simpleksmetoden. 
Mål 3. Bedriften produserer 3 typer produkter: A1, A2, A3, ved bruk av to typer råvarer. Kostnadene for råvarer av hver type per produksjonsenhet, lager av råvarer for den planlagte perioden, samt fortjenesten fra en produksjonsenhet av hver type er kjent.
- Hvor mange produkter av hver type må produseres for å få maksimal fortjeneste?
- Bestem status for hver type råvare og dens spesifikke verdi.
- Bestem det maksimale intervallet for endringer i lager av hver type råvare, innenfor hvilken strukturen til den optimale planen, dvs. nomenklaturen for problemet vil ikke endres.
- Bestem mengden av produkter og fortjenesten fra utgivelsen med en økning i lagerbeholdningen av en av de knappe typene råvarer til maksimal verdi (innenfor grensene for den gitte produksjonsnomenklaturen).
- Bestem intervallene for endring i profitt fra en produksjonsenhet av hver type, der den resulterende optimale planen ikke vil endres.
Oppgave 4. Løs det lineære programmeringsproblemet ved å bruke simpleksmetoden: 
Oppgave 5. Løs det lineære programmeringsproblemet ved å bruke simpleksmetoden: 
Oppgave 6. Løs problemet ved å bruke simpleksmetoden, og vurdere planen gitt i tilstanden som den første referanseplanen: 
Oppgave 7. Løs problemet ved å bruke den modifiserte simpleksmetoden.
For produksjon av to typer produkter A og B brukes tre typer teknologisk utstyr. For produksjon av en enhet av produkt A brukes utstyr av den første typen a1 = 4 timer, utstyr av den andre typen, a2 = 8 timer, og utstyr av den tredje typen, a3 = 9 timer. For produksjon av enhet B brukes utstyr av den første typen b1 = 7 timer, utstyr av den andre typen, b2 = 3 timer, og utstyr av den tredje typen, b3 = 5 timer.
For produksjon av disse produktene kan utstyr av den første typen ikke fungere mer enn t1 = 49 timer, utstyr av den andre typen ikke mer enn t2 = 51 timer, utstyr av den tredje typen ikke mer enn t3 = 45 timer.
Fortjeneste fra salg av en enhet av ferdig produkt A er ALPHA = 6 rubler, og for produkt B - BETTA = 5 rubler.
Lag en plan for produksjon av produktene A og B, for å sikre maksimal fortjeneste fra salget.
Oppgave 8. Finn den optimale løsningen ved hjelp av dual simplex-metoden 
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. medlem | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. medlem | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
... Enkel metodealgoritme
Eksempel 5.1. Løs følgende lineære programmeringsproblem ved å bruke simpleksmetoden:
Løsning:
Jeg iterasjon:
x3, x4, x5, x6 x1,x2... La oss uttrykke de grunnleggende variablene i form av frie:
La oss bringe den objektive funksjonen til følgende form:
Basert på det oppnådde problemet, vil vi danne den første simplekstabellen:
Tabell 5.3
Kilde simplekstabell
Verdsettelsesforhold |
||||
I henhold til definisjonen av den grunnleggende løsningen er de frie variablene lik null, og verdiene til de grunnleggende variablene er lik de tilsvarende verdiene til de frie tallene, dvs.:
Trinn 3: kontroll av kompatibiliteten til LPP-begrensningssystemet.
Ved denne iterasjonen (i tabell 5.3) ble tegnet på inkompatibilitet til restriksjonssystemet (tegn 1) ikke identifisert (dvs. det er ingen rad med et negativt fritt tall (bortsett fra linjen til objektivfunksjonen), som gjør ikke inneholde minst ett negativt element (dvs. negativ koeffisient ved en fri variabel)).
Ved denne iterasjonen (i tabell 5.3) ble tegnet på uavgrensetheten til den objektive funksjonen (tegnet 2) ikke identifisert (dvs. det er ingen kolonne med et negativt element i linjen til objektivfunksjonen (bortsett fra kolonnen med fri) tall), der det ikke vil være minst ett positivt element) ...
Siden den funnet basisløsningen ikke inneholder negative komponenter, er den tillatt.
Trinn 6: kontroll av optimaliteten.
Den funnet grunnleggende løsningen er ikke optimal, siden i henhold til optimalitetskriteriet (funksjon 4) skal det ikke være noen negative elementer i linjen til objektivfunksjonen (det frie nummeret til denne linjen tas ikke i betraktning når man vurderer denne funksjonen). Derfor, i henhold til algoritmen til simpleksmetoden, går vi til åttende trinn.
Siden den funnet grunnleggende løsningen er tillatt, vil søket etter den løsende kolonnen bli utført i henhold til følgende skjema: vi bestemmer kolonnene med negative elementer i linjen til objektivfunksjonen (bortsett fra kolonnen med frie tall). I følge tabell 5.3 er det to slike kolonner: kolonnen " x1"Og kolonnen" x2". Fra slike kolonner velges den som inneholder det minste elementet i linjen til målfunksjonen. Hun vil løse. høyttaler" x2"Inneholder det minste elementet (–3) sammenlignet med kolonnen" x1
For å bestemme oppløsningslinjen finner vi de positive estimerte forholdene mellom frie tall og elementene i tillatelseskolonnen, linjen, som tilsvarer det minste positive estimerte forholdet, tas som tillatt.
Tabell 5.4
Kilde simplekstabell
I tabell 5.4 tilsvarer det minste positive estimerte forholdet linjen " x5”, Derfor vil det være tillatt.
Elementet plassert i skjæringspunktet mellom tillatelsessøylen og tillatelseslinjen aksepteres som tillat. I vårt eksempel er dette et element som er plassert i skjæringspunktet mellom linjen " x5"Og kolonner" x2».
Oppløsningselementet viser én grunnleggende og én fri variabel som må byttes i simplekstabellen for å gå over til en ny «forbedret» grunnløsning. I dette tilfellet er dette variabler x5 og x2, i den nye simplekstabellen (tabell 5.5) bytter vi dem.
9.1. Transformasjon av oppløsningselementer.
Det permissive elementet i tabell 5.4 er transformert som følger:
Vi legger inn resultatet oppnådd i en lignende celle i tabell 5.5.
9.2. Konvertering av oppløsningsstrengen.
Vi deler elementene i oppløsningslinjen i tabell 5.4 med oppløsningselementet i denne simplekstabellen, resultatene passer inn i lignende celler i den nye simplekstabellen (tabell 5.5). Transformasjoner av elementene i oppløsningslinjen er gitt i tabell 5.5.
9.3. Konvertering av oppløsningskolonnen.
Elementene i oppløsningskolonnen i Tabell 5.4 er delt med oppløsningselementet i den gitte simplekstabellen, og resultatet tas med motsatt fortegn. Resultatene som ble oppnådd passer inn i lignende celler i den nye simplekstabellen (tabell 5.5). Transformasjonene av elementene i oppløsningskolonnen er vist i tabell 5.5.
9.4. Konverter resten av elementene i simplekstabellen.
Transformasjonen av de gjenværende elementene i simplekstabellen (dvs. elementer som ikke er plassert i oppløsningslinjen og oppløsningskolonnen) utføres i henhold til "rektangel"-regelen.
Vurder for eksempel å transformere et element som befinner seg i skjæringspunktet mellom strengen " x3"Og kolonnen" ", vi vil konvensjonelt betegne den som" x3". I tabell 5.4, tegn mentalt et rektangel, hvorav ett toppunkt er plassert i cellen, verdien som vi transformerer (det vil si i cellen " x3»), Og den andre (diagonal toppunkt) er i cellen med det løsende elementet. De to andre hjørnene (den andre diagonalen) er unikt bestemt. Deretter den transformerte verdien av cellen " x3"Vil være lik den forrige verdien av denne cellen minus brøken, i nevneren som det er et oppløsningselement (fra tabell 5.4), og i telleren produktet av to andre ubrukte hjørner, dvs.:
« x3»: .
Verdiene til andre celler transformeres på samme måte:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Som et resultat av disse transformasjonene ble det oppnådd en ny simplekstabell (tabell 5.5).
II iterasjon:
Trinn 1: lage en simplekstabell.
Tabell 5.5
Enkelt bordII iterasjoner
Antatt forhold |
||||
| ||||
|
|
Trinn 2: bestemmelse av basisløsningen.
Som et resultat av simplekstransformasjonene ble det oppnådd en ny basisløsning (tabell 5.5):
Som du kan se, med denne grunnleggende løsningen, er verdien av målfunksjonen = 15, som er mer enn med den forrige grunnløsningen.
Inkonsistensen i restriksjonssystemet i henhold til attributt 1 i tabell 5.5 ble ikke avdekket.
Trinn 4: kontroll av begrensetheten til objektivfunksjonen.
Uavgrensningen til objektivfunksjonen i henhold til funksjon 2 i tabell 5.5 ble ikke avdekket.
Trinn 5: kontroll av tillateligheten til den funnet grunnleggende løsningen.
Den funnet grunnleggende løsningen i samsvar med funksjon 4 er ikke optimal, siden linjen til objektivfunksjonen til simplekstabellen (tabell 5.5) inneholder et negativt element: –2 (det frie tallet til denne linjen tas ikke i betraktning når man vurderer dette trekk). Derfor går vi til trinn 8.
Trinn 8: bestemmelse av oppløsningselementet.
8.1. Definisjon av oppløsningskolonnen.
Den funnet grunnleggende løsningen er tillatt, vi definerer kolonnene med negative elementer i linjen til objektivfunksjonen (bortsett fra kolonnen med frie tall). I følge tabell 5.5 er kun én kolonne en slik kolonne: " x1". Derfor aksepterer vi det som tillatt.
8.2. Bestemmelse av tillatelsesstrengen.
I henhold til de oppnådde verdiene av positive evalueringsforhold i tabell 5.6, er minimum forholdet som tilsvarer linjen " x3". Derfor aksepterer vi det som tillatt.
Tabell 5.6
Enkelt bordII iterasjoner
Antatt forhold |
||||
3/1 = 3 - min |
||||
Trinn 9: transformasjon av simplekstabellen.
Simple tabelltransformasjoner (tabell 5.6) utføres på samme måte som i forrige iterasjon. Resultatene av transformasjoner av elementer i en simplekstabell er vist i tabell 5.7.
III iterasjon
Basert på resultatene av simplekstransformasjonene fra forrige iterasjon, komponerer vi en ny simplekstabell:
Tabell 5.7
Enkelt bordIII iterasjoner
Antatt forhold |
||||
| ||||
|
|
Trinn 2: bestemmelse av basisløsningen.
Som et resultat av simplekstransformasjonene ble det oppnådd en ny basisløsning (tabell 5.7):
Trinn 3: kontroll av konsistensen til systemet med begrensninger.
Inkonsistensen i restriksjonssystemet i henhold til attributt 1 i tabell 5.7 ble ikke avdekket.
Trinn 4: kontroll av begrensetheten til objektivfunksjonen.
Uavgrensningen til objektivfunksjonen i henhold til attributt 2 i tabell 5.7 ble ikke avdekket.
Trinn 5: kontroll av tillateligheten til den funnet grunnleggende løsningen.
Den funnet grunnleggende løsningen i samsvar med attributt 3 er tillatt, siden den ikke inneholder negative komponenter.
Trinn 6: sjekke optimaliteten til den funnet grunnleggende løsningen.
Den funnet grunnløsningen i samsvar med funksjon 4 er ikke optimal, siden linjen til objektivfunksjonen til simplekstabellen (tabell 5.7) inneholder et negativt element: –3 (det frie nummeret til denne linjen tas ikke i betraktning når man vurderer dette trekk). Derfor går vi til trinn 8.
Trinn 8: bestemmelse av oppløsningselementet.
8.1. Definisjon av oppløsningskolonnen.
Den funnet grunnleggende løsningen er tillatt, vi definerer kolonnene med negative elementer i linjen til objektivfunksjonen (bortsett fra kolonnen med frie tall). I følge tabell 5.7 er kun én kolonne en slik kolonne: " x5". Derfor aksepterer vi det som tillatt.
8.2. Bestemmelse av tillatelsesstrengen.
I henhold til de oppnådde verdiene av positive evalueringsforhold i tabell 5.8, er minimum forholdet som tilsvarer linjen " x4". Derfor aksepterer vi det som tillatt.
Tabell 5.8
Enkelt bordIII iterasjoner
Antatt forhold |
||||
5/5 = 1 - min |
||||
Trinn 9: transformasjon av simplekstabellen.
Simple tabelltransformasjoner (tabell 5.8) utføres på samme måte som i forrige iterasjon. Resultatene av transformasjoner av elementer i en simplekstabell er vist i tabell 5.9.
IV iterasjon
Trinn 1: bygge et nytt simpleksbord.
Basert på resultatene av simplekstransformasjonene fra forrige iterasjon, komponerer vi en ny simplekstabell:
Tabell 5.9
Enkelt bordIV iterasjoner
Antatt forhold |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Trinn 2: bestemmelse av basisløsningen.
Som et resultat av simplekstransformasjonene ble det oppnådd en ny basisløsning, ifølge tabell 5.9 er løsningen som følger:
Trinn 3: kontroll av konsistensen til systemet med begrensninger.
Inkonsistensen i restriksjonssystemet i henhold til attributt 1 i tabell 5.9 ble ikke avdekket.
Trinn 4: kontroll av begrensetheten til objektivfunksjonen.
Uavgrensningen til objektivfunksjonen i henhold til funksjon 2 i tabell 5.9 ble ikke avdekket.
Trinn 5: kontroll av tillateligheten til den funnet grunnleggende løsningen.
Den funnet grunnleggende løsningen i samsvar med attributt 3 er tillatt, siden den ikke inneholder negative komponenter.
Trinn 6: sjekke optimaliteten til den funnet grunnleggende løsningen.
Den funnet grunnleggende løsningen i samsvar med funksjon 4 er optimal, siden det ikke er noen negative elementer i linjen til objektivfunksjonen til simplekstabellen (tabell 5.9) (det frie nummeret til denne linjen tas ikke i betraktning når denne funksjonen vurderes) .
Trinn 7: sjekke alternativet til løsningen.
Den funnet løsningen er den eneste, siden det ikke er noen nullelementer i linjen til objektivfunksjonen (tabell 5.9) (det frie nummeret til denne linjen tas ikke i betraktning når denne funksjonen vurderes).
Svar: den optimale verdien av den objektive funksjonen til det vurderte problemet = 24, som oppnås ved.
Eksempel 5.2. Løs det lineære programmeringsproblemet ovenfor under forutsetning av at objektivfunksjonen er minimert:
Løsning:
Jeg iterasjon:
Trinn 1: dannelse av den innledende simplekstabellen.
Det opprinnelige lineære programmeringsproblemet er gitt i en standardform. La oss bringe den til sin kanoniske form ved å introdusere en ekstra ikke-negativ variabel i hver av ulikhetsbegrensningene, dvs.
I det resulterende ligningssystemet tar vi som de tillatte (grunnleggende) variablene x3, x4, x5, x6, da vil de frie variablene være x1,x2... La oss uttrykke de grunnleggende variablene i form av frie.
