At finde det løsende element i simplekstabellen. Generelle karakteristika for det opløste ligningssystem

For at tillade appletten at køre på din computer, skal du gøre følgende - klik på Start>Kontrolpanel>Programmer>Java. I Java-vinduet Kontrolpanel vælg fanen Sikkerhed, klik på knappen Rediger webstedsliste, knappen Tilføj og indsæt stien til denne side fra det frie felt adresse bar browser. Klik derefter på OK, og genstart derefter computeren.

For at starte appletten skal du klikke på knappen "Simplex". Hvis knappen "Simplex" ikke er synlig over denne linje, er Java ikke installeret på din computer.

Efter at have klikket på knappen "Simplex", vises det første vindue til indtastning af antallet af variabler og antallet af begrænsninger for problemet på simpleksmetoden.

Efter at have klikket på knappen "ok" vises et vindue til indtastning af de resterende data for problemet ved hjælp af simpleksmetoden: visningstilstand (decimalbrøker eller almindelige), type opgavekriterium min eller maks., input af koefficienter for objektivfunktionen og koefficienter for systemet af begrænsninger med tegnene "≤", " ≥ "eller "=", begrænsninger af formen x i ≥ 0 behøver ikke at indføres, tager højde for dem i sin algoritme.

Efter at have klikket på knappen "Løs" vises et vindue med resultaterne af løsningen af problemet .Vinduet består af to dele, øverst er der et tekstfelt med en beskrivelse af rollebesætningen. oprindelige problem til den kanoniske form, som bruges til at kompilere den første simplex-tabel. I bunden af vinduet, i et panel med faner, er der simplekstabeller af hver iteration med en lille tekstfelt nedenfor angiver tilladelseskolonnen, tilladelsesrækken og andre oplysninger, som gør programmet lærerigt. I fanen med den optimale (sidste) tabel vises den resulterende optimale løsning på problemet i tekstfeltet.

Send eventuelle fejl, du bemærker, og kommentarer til appletten til: [e-mail beskyttet] eller ring på 8 962 700 77 06, hvilket vi vil være dig meget taknemmelig for.

M-metode program

Program til at løse transport problem

Her er en manuel (ikke applet) løsning af to problemer ved hjælp af simplex-metoden (svarende til applet-løsningen) med detaljerede forklaringer for at forstå algoritmen til at løse problemer. Det første problem indeholder kun ulighedstegn "≤" (problem med et indledende grundlag), det andet kan indeholde tegn "≥", "≤" eller "=" (problem med kunstigt grundlag), løses de forskelligt.

Enkel metode, der løser et problem med en indledende basis

1)Enkel metode for et problem med en indledende basis (alle tegn på ulighedsbegrænsninger " ≤ ").

Lad os skrive problemet ind kanonisk form, dvs. vi omskriver ulighedsbegrænsningerne i form af ligheder, tilføjer balance variabler:

Dette system er et system med en basis (basis s 1, s 2, s 3, hver af dem er kun inkluderet i én af systemets ligning med en koefficient på 1), x 1 og x 2 er frie variable. Problemer, der skal løses ved hjælp af simplex-metoden, skal have følgende to egenskaber:
-systemet af begrænsninger skal være et ligningssystem med et grundlag;
-frie led for alle ligninger i systemet skal være ikke-negative.

Det resulterende system er et system med et grundlag, og dets frie udtryk er ikke-negative, så simplex-metoden kan anvendes. Lad os skabe den første simplex-tabel (Iteration 0), dvs. en tabel med koefficienter for objektivfunktionen og et ligningssystem for de tilsvarende variable. Her betyder "BP" kolonnen med grundlæggende variable, "Løsning" betyder kolonnen med højre side af systemligningerne. Løsningen er ikke optimal, pga der er negative koefficienter i z-rækken.

iteration 0

BP	Løsning	Holdning

For at forbedre løsningen går vi videre til næste iteration og får den følgende simplex-tabel. For at gøre dette skal du vælge aktivér kolonne, dvs. en variabel, der vil indgå i grundlaget ved næste iteration. Det vælges af den største absolutte negative koefficient i z-rækken (i det maksimale problem) - i den indledende iteration er dette x 2 kolonnen (koefficient -6).

Vælg derefter aktivere streng, dvs. en variabel, der forlader basis ved næste iteration. Det vælges af det mindste forhold mellem "Beslutning"-kolonnen og de tilsvarende positive elementer i opløsningskolonnen (kolonne "Ratio") - i den indledende iteration er dette række s 3 (koefficient 20).

Tilladende element er i skæringspunktet mellem den løsende kolonne og den løsende række, er dens celle fremhævet i farve, den er lig med 1. Derfor vil variablen x 2 ved næste iteration erstatte s 3 i basis. Bemærk, at der ikke søges efter relationen i z-strengen; en bindestreg "-" er placeret der. Hvis der er identiske minimale relationer, vælges nogen af dem. Hvis alle koefficienter i opløsningskolonnen er mindre end eller lig med 0, så er løsningen på problemet uendelig.

Lad os udfylde følgende tabel "Iteration 1". Vi får det fra "Iteration 0"-tabellen. Målet med yderligere transformationer er at omdanne x2 opløsningskolonnen til en enhedskolonne (med en i stedet for opløsningselementet og nuller i stedet for de resterende elementer).

1) Beregn række x 2 i "Iteration 1"-tabellen. Først dividerer vi alle medlemmer af den løsende række s 3 i "Iteration 0"-tabellen med det løsende element (det er lig med 1 i I dette tilfælde) i denne tabel får vi række x 2 i tabellen "Iterationer 1". Fordi det løsende element i dette tilfælde er lig med 1, så vil række s 3 i "Iteration 0"-tabellen falde sammen med række x 2 i "Iteration 1"-tabellen. Række x 2 i Iteration 1-tabellen fik vi 0 1 0 0 1 20, de resterende rækker i Iteration 1-tabellen vil blive hentet fra denne række og rækkerne i Iteration 0-tabellen som følger:

2) Beregning af z-rækken i "Iteration 1"-tabellen. I stedet for -6 i den første række (z-rækken) i x2-kolonnen i Iteration 0-tabellen, skal der være et 0 i den første række af Iteration 1-tabellen. For at gøre dette skal du gange alle elementerne i rækken x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med 6, vi får 0 6 0 0 6 120 og tilføje denne række med den første række (z - række) af tabellen "Iteration 0" -4 -6 0 0 0 0, får vi -4 0 0 0 6 120. Et nul 0 vises i x 2 kolonnen, målet er nået. Elementer i opløsningskolonnen x 2 er fremhævet med rødt.

3) Beregning af række s 1 i "Iteration 1" tabellen. I stedet for 1 i s 1 række i "Iteration 0"-tabellen skal der være et 0 i "Iteration 1"-tabellen. For at gøre dette skal du gange alle elementerne i række x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med -1, få 0 -1 0 0 -1 -20 og tilføje denne række med s 1 - række af tabel "Iteration 0" 2 1 1 0 0 64, får vi rækken 2 0 1 0 -1 44. I kolonnen x 2 får vi den nødvendige 0.

4) Beregn række s 2 i "Iteration 1"-tabellen. På plads 3 i s 2 række i tabellen "Iteration 0" skal der være 0 i tabellen "Iteration 1". For at gøre dette skal du gange alle elementer i række x 2 i tabellen "Iteration 1" 0 1 0 0 1 20 med -3, få 0 -3 0 0 -3 -60 og tilføje denne række med s 2 - række i tabellen "Iteration 0" 1 3 0 1 0 72, vi får rækken 1 0 0 1 -3 12. I kolonnen x 2 opnås det påkrævede 0. Kolonnen x 2 i tabellen "Iteration 1" er blevet til en enhed , den indeholder en 1 og resten 0.

Rækkerne i tabellen "Iteration 1" opnås i henhold til følgende regel:

Ny linje= Gammel række – (Gamle rækkeopløsningskolonnekoefficient)*(Ny opløsningsrække).

For en z-streng har vi for eksempel:

Gammel z-streng (-4 -6 0 0 0 0)
-(-6)*Ny opløsningslinje -(0-6 0 0 -6 -120)
=Ny z-streng(-4 0 0 0 6 120) .

For de følgende tabeller sker genberegningen af tabelelementer på lignende måde, så vi udelader den.

iteration 1

						Løsning	Holdning

Løsning af kolonne x 1, løsning af række s 2, s 2 forlader basis, x 1 går ind i basis. På nøjagtig samme måde får vi de resterende simplex-tabeller, indtil vi får en tabel med alle positive koefficienter i z-rækken. Dette er et tegn på et optimalt bord.

Gentagelse 2

						Løsning	Holdning

Løsning af kolonne s 3, løsning af række s 1, s 1 forlader basis, s 3 går ind i basis.

Gentagelse 3

						Løsning	Holdning

I z-rækken er alle koefficienter ikke-negative, derfor opnås den optimale løsning x 1 = 24, x 2 = 16, z max = 192.

Enkel metode, der løser et problem med et kunstigt grundlag

2) Lad os løse problemet med et kunstigt grundlag (mindst ét ulighedsbegrænsningstegn "≥" eller "=").

Lad os skrive problemet i kanonisk form (i form af et ligningssystem, som kræver simpleksmetoden), for at gøre dette introducerer vi to variable x 3 ≥ 0 og x 4 ≥ 0, vi får:

Systemet af begrænsninger tilbyder kun én tilladt grundvariabel x 4, kun den er inkluderet i kun én ligning i den tredje med en koefficient på 1, så vi tilføjer kunstige variable R 1 ≥ 0 og R 2 ≥ 0 til den første og anden ligning så simplex-metoden kan anvendes skal systembegrænsningsligninger være et system med basis, dvs. i hver ligning skal der være en variabel med koefficienten 1, som kun indgår i én af systemets ligning, i vores tilfælde er disse R 1, R 2 og x 4. Vi fik den såkaldte M-opgave:

Dette system er et system med et grundlag, hvor R 1, R 2 og x 4 er grundvariable, og x 1, x 2 og x 3 er frie variable, er de frie led i alle ligninger ikke-negative. Derfor kan simpleksmetoden bruges til at løse problemet. Lad os skrive den indledende simplex-tabel ned:

iteration 0

	Løsning	Holdning
-16

Linjen "Evaluering" er tilføjet tabellen for problemer med et kunstigt grundlag. Det opnås ved at summere de tilsvarende koefficienter for rækker med kunstige variable (R) med det modsatte fortegn. Det vil være til stede i tabellen, så længe mindst én af de kunstige variable er i grundlaget. Baseret på den største modulo negative koefficient på "Evaluering"-linjen, bestemmes den løsende kolonne, mens den er i tabellen. Når rækken "Evaluering" forlader tabellen (der er ingen kunstige variable i grundlaget), vil den løsende kolonne blive bestemt af z-rækken, som i problemet med startgrundlaget. I denne tabel er den løsende kolonne x 2, den er valgt ud fra den største absolutte negative score (-7). Den løsende række R 2 er valgt baseret på det mindste forhold mellem "Løsning"-kolonnen og de tilsvarende positive elementer i den løsende kolonne, som i problemet uden kunstige variable. Det betyder, at ved næste iteration vil variablen x2 gå fra fri til basis, og variablen R2 vil gå fra basis til fri. Lad os skrive følgende simplekstabel:

Løsning af kolonne x 1, løsning af række R 1, R 1 forlader basis, x 1 går ind i basis. Herefter er der ingen kunstige variable tilbage i grundlaget, så der er ingen "Evaluering" linje i følgende tabel:

iteration 2

							Løsning	Holdning

Dernæst vælges opløsningskolonnen af z-rækken. I z-rækken er alle koefficienter ikke-negative bortset fra koefficienten for den kunstige variabel R 1, som ikke påvirker optimaliteten, når de kunstige variable forlader basis. Som følge heraf opnås den optimale opløsning x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Særlige tilfælde af brug af simpleksmetoden

1) Når den rette linie (hvis et todimensionelt lineært programmeringsproblem betragtes, og i det generelle tilfælde et hyperplan), der repræsenterer den objektive funktion, er parallel med den rette linie (hyperplan), der svarer til en af ulighedsbegrænsningerne (som ved optimalt punkt er opfyldt som en nøjagtig lighed), tager den objektive funktion en og er også en optimal værdi ved et bestemt sæt af punkter på grænsen af området for mulige løsninger. Disse løsninger kaldes alternativ optimale løsninger . Tilgængelighed alternative løsninger kan bestemmes ud fra den optimale simplex-tabel. Hvis z-rækken i den optimale tabel indeholder nulkoefficienter af ikke-grundlæggende variable, så er der alternative løsninger.

2) Hvis alle koefficienter i simplex-tabellens opløsningskolonne er mindre end eller lig med nul, så er det umuligt at vælge en opløsningsrække, i dette tilfælde er løsningen ubegrænset.

3) Hvis begrænsningerne for et lineært programmeringsproblem er inkonsistente (det vil sige, at de ikke kan opfyldes samtidigt), så har problemet ingen gennemførlige løsninger. Denne situation kan ikke opstå, hvis alle de uligheder, der udgør restriktionssystemet, er af typen "≤" med ikke-negative højresider, fordi i dette tilfælde kan yderligere variable udgøre gyldig løsning. For andre typer begrænsninger anvendes kunstige variable. Hvis problemet har en løsning, så er der i den optimale tabel ingen kunstige variable (R i) i grundlaget. Hvis de er der, så har problemet ingen løsninger.

. Simplex metode algoritme

Eksempel 5.1. Løs følgende lineære programmeringsproblem ved hjælp af simpleksmetoden:

Løsning:

jeg iteration:

x3, x4, x5, x6 x1,x2. Lad os udtrykke de grundlæggende variabler i form af frie:

Lad os reducere den objektive funktion til følgende form:

Baseret på det opnåede problem vil vi danne den indledende simplex-tabel:

Tabel 5.3

Originalt simplex bord

				Evaluerende relationer

Ifølge definitionen af den grundlæggende løsning er de frie variable lig med nul, og værdierne af de grundlæggende variable er lig med de tilsvarende værdier af de frie tal, dvs.

Trin 3: kontrol af kompatibiliteten af PAP-begrænsningssystemet.

Ved denne iteration (i tabel 5.3) er tegnet på inkonsistens af begrænsningssystemet (tegn 1) ikke identificeret (dvs. der er ingen linje med et negativt frit tal (bortset fra linjen i den objektive funktion), hvor der ikke ville være mindst ét negativt element (dvs. negativ koefficient for en fri variabel)).

Ved denne iteration (i tabel 5.3) blev tegnet på ubegrænsethed af objektivfunktionen (tegn 2) ikke identificeret (dvs. der er ingen kolonne med et negativt element i rækken af objektivfunktionen (bortset fra kolonnen med frie tal) ) hvori der ikke ville være mindst ét positivt element).

Da den fundne basisopløsning ikke indeholder negative komponenter, er den tilladt.

Trin 6: optimalitetstjek.

Den fundne basisløsning er ikke optimal, da der ifølge optimalitetskriteriet (tegn 4) ikke bør være negative elementer i linjen af den objektive funktion (den frie nummer på denne linje tages ikke i betragtning, når dette kriterium overvejes). Derfor går vi videre til trin 8 i henhold til simplex-metodens algoritme.

Da den fundne grundlæggende løsning er tilladt, vil vi søge efter den løsende kolonne i henhold til følgende skema: vi bestemmer kolonnerne med negative elementer i rækken af objektivfunktionen (undtagen kolonnen med frie tal). Ifølge tabel 5.3 er der to sådanne kolonner: kolonne " x1"og kolonne" x2" Fra sådanne kolonner vælges den, der indeholder det mindste element i rækken af målfunktionen. Hun vil være den tilladelige. kolonne" x2" indeholder det mindste element (–3) sammenlignet med kolonnen " x1

For at bestemme den løsende linje finder vi de positive estimerede forhold mellem frie tal og elementerne i den løsende kolonne; den linje, der svarer til det mindste positive evalueringsforhold, accepteres som løst.

Tabel 5.4

Originalt simplex bord

I tabel 5.4 svarer den mindste positive evaluerende sammenhæng til linjen " x5", derfor vil det være tilladeligt.

Elementet placeret ved skæringspunktet mellem aktiveringskolonnen og aktiveringsrækken accepteres som aktiverende. I vores eksempel er dette det element, der er placeret i skæringspunktet mellem linjen " x5"og kolonner" x2».

Det løsende element viser én basis og én fri variabel, der skal byttes i simplex-tabellen for at flytte til en ny "forbedret" basisløsning. I dette tilfælde er der tale om variabler x5 Og x2, i den nye simplex-tabel (tabel 5.5) bytter vi dem.

9.1. Transformation af det løsende element.

Opløsningselementet i tabel 5.4 er konverteret som følger:

Vi indtaster det resulterende resultat i en lignende celle i tabel 5.5.

9.2. Konvertering af opløsningsstreng.

Vi deler elementerne i den løsende række i tabel 5.4 med opløsningselementet i denne simplekstabel, resultaterne passer ind i lignende celler i den nye simplekstabel (tabel 5.5). Transformationer af opløsningsstrengelementer er angivet i tabel 5.5.

9.3. Konvertering af opløsningskolonnen.

Vi dividerer elementerne i opløsningskolonnen i tabel 5.4 med opløsningselementet i denne simplekstabel, og resultatet tages med det modsatte fortegn. De opnåede resultater passer ind i lignende celler i den nye simplex-tabel (tabel 5.5). Transformationer af elementerne i opløsningskolonnen er angivet i tabel 5.5.

9.4. Transformation af de resterende elementer i simplex-tabellen.

Transformationen af de resterende elementer i simplex-tabellen (dvs. elementer, der ikke er placeret i den løsende række og opløsningskolonnen) udføres i henhold til reglen om "rektangel".

Overvej for eksempel at transformere et element placeret i skæringspunktet mellem linjen " x3" og kolonner "", vil vi betinget betegne det " x3" I tabel 5.4 tegner vi mentalt et rektangel, hvoraf det ene toppunkt er placeret i cellen, hvis værdi vi transformerer (dvs. i cellen " x3"), og den anden (diagonal toppunkt) er i en celle med et opløsningselement. De to andre hjørner (af den anden diagonal) er entydigt bestemt. Derefter den transformerede værdi af cellen " x3" vil være lig med den foregående værdi af denne celle minus brøken, i hvis nævner er det opløselige element (fra tabel 5.4), og i tælleren er produktet af to andre ubrugte hjørner, dvs.

« x3»: .

Værdierne af andre celler konverteres på samme måde:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Som et resultat af disse transformationer modtog vi en ny simplex bord(Tabel 5.5).

II iteration:

Trin 1: udarbejdelse af en simplex-tabel.

Tabel 5.5

Simplex bordII iterationer

				Anslået forhold

Trin 2: Bestemmelse af den basiske opløsning.

Som et resultat af simplex-transformationerne blev der opnået en ny basisløsning (tabel 5.5):

Som du kan se, er værdien af objektivfunktionen med denne basisløsning = 15, hvilket er større end med den tidligere basisløsning.

Inkonsekvensen af begrænsningssystemet i overensstemmelse med funktion 1 i tabel 5.5 er ikke blevet identificeret.

Trin 4: kontrol af afgrænsningen af den objektive funktion.

Ubegrænsetheden af den objektive funktion i henhold til kriterium 2 i tabel 5.5 afsløres ikke.

Trin 5: kontrol af, om den fundne basisløsning er tilladt.

Den fundne basisløsning i overensstemmelse med kriterium 4 er ikke optimal, da linjen i simplex-tabellens objektivfunktion (tabel 5.5) indeholder et negativt element: –2 (den frie nummer på denne linje tages ikke i betragtning, når dette tages i betragtning. egenskab). Derfor går vi videre til etape 8.

Trin 8: bestemmelse af opløsningselementet.

8.1. Definition af opløsningskolonnen.

Den fundne grundlæggende løsning er acceptabel; vi bestemmer kolonnerne med negative elementer i rækken af objektivfunktionen (undtagen kolonnen med frie tal). Ifølge tabel 5.5 er der kun én sådan kolonne: " x1" Derfor accepterer vi det som tilladt.

8.2. Definition af en aktiveringsstreng.

Ifølge de opnåede værdier af positive evaluerende relationer i tabel 5.6 er minimum forholdet svarende til linjen " x3" Derfor accepterer vi det som tilladt.

Tabel 5.6

Simplex bordII iterationer

				Anslået forhold
				3/1=3 – min

Trin 9: transformation af simplex-tabellen.

Transformationer af simplekstabellen (tabel 5.6) udføres på samme måde som i forrige iteration. Resultaterne af transformationer af elementer i simplekstabellen er angivet i tabel 5.7.

III iteration

Baseret på resultaterne af simplex-transformationer af den tidligere iteration, sammensætter vi en ny simplex-tabel:

Tabel 5.7

Simplex bordIII iterationer

				Anslået forhold

Trin 2: Bestemmelse af den basiske opløsning.

Som et resultat af simplex-transformationerne blev der opnået en ny basisløsning (tabel 5.7):

Trin 3: kontrol af kompatibiliteten af begrænsningssystemet.

Inkonsistensen af begrænsningssystemet i overensstemmelse med funktion 1 i tabel 5.7 er ikke blevet identificeret.

Trin 4: kontrol af afgrænsningen af den objektive funktion.

Ubegrænsetheden af den objektive funktion i henhold til kriterium 2 i tabel 5.7 afsløres ikke.

Trin 5: kontrol af, om den fundne basisløsning er tilladt.

Den fundne basisløsning i overensstemmelse med kriterium 3 er acceptabel, da den ikke indeholder negative komponenter.

Trin 6: kontrol af optimaliteten af den fundne basisløsning.

Den fundne basisløsning i overensstemmelse med kriterium 4 er ikke optimal, da linjen i simplex-tabellens objektivfunktion (tabel 5.7) indeholder et negativt element: –3 (den frie nummer på denne linje tages ikke i betragtning, når dette tages i betragtning. egenskab). Derfor går vi videre til etape 8.

Trin 8: bestemmelse af opløsningselementet.

8.1. Definition af opløsningskolonnen.

Den fundne grundlæggende løsning er acceptabel; vi bestemmer kolonnerne med negative elementer i rækken af objektivfunktionen (undtagen kolonnen med frie tal). Ifølge tabel 5.7 er der kun én sådan kolonne: " x5" Derfor accepterer vi det som tilladt.

8.2. Definition af en aktiveringsstreng.

Ifølge de opnåede værdier af positive evaluerende relationer i tabel 5.8 er minimum forholdet svarende til linjen " x4" Derfor accepterer vi det som tilladt.

Tabel 5.8

Simplex bordIII iterationer

				Anslået forhold

				5/5=1 – min

Trin 9: transformation af simplex-tabellen.

Transformationer af simplekstabellen (tabel 5.8) udføres på samme måde som i forrige iteration. Resultaterne af transformationer af elementer i simplekstabellen er angivet i tabel 5.9.

IV iteration

Trin 1: konstruktion af et nyt simplex bord.

Baseret på resultaterne af simplex-transformationer af den tidligere iteration, sammensætter vi en ny simplex-tabel:

Tabel 5.9

Simplex bordIV iterationer

				Anslået forhold
			–(–3/5)=3/5

			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Trin 2: Bestemmelse af den basiske opløsning.

Som et resultat af simplex-transformationerne blev der opnået en ny basisløsning; ifølge tabel 5.9 er løsningen som følger:

Trin 3: kontrol af kompatibiliteten af begrænsningssystemet.

Inkonsekvensen af begrænsningssystemet i overensstemmelse med funktion 1 i tabel 5.9 er ikke blevet identificeret.

Trin 4: kontrol af afgrænsningen af den objektive funktion.

Ubegrænsetheden af den objektive funktion i henhold til kriterium 2 i tabel 5.9 afsløres ikke.

Trin 5: kontrol af, om den fundne basisløsning er tilladt.

Den fundne basisløsning i overensstemmelse med kriterium 3 er acceptabel, da den ikke indeholder negative komponenter.

Trin 6: kontrol af optimaliteten af den fundne basisløsning.

Den fundne basisløsning i overensstemmelse med funktion 4 er optimal, da der ikke er nogen negative elementer i linjen for den objektive funktion af simplex-tabellen (tabel 5.9) (det frie nummer af denne linje tages ikke i betragtning, når denne funktion overvejes) .

Trin 7: kontrol af løsningens alternativhed.

Den fundne løsning er unik, da der ikke er nogen nul-elementer i objektivfunktionens linie (tabel 5.9) (det frie nummer på denne linie tages ikke i betragtning, når denne funktion tages i betragtning).

Svar: den optimale værdi af den objektive funktion af det undersøgte problem =24, som opnås ved.

Eksempel 5.2. Løs ovenstående lineære programmeringsproblem forudsat at objektivfunktionen er minimeret:

Løsning:

jeg iteration:

Trin 1: Dannelse af den indledende simplex-tabel.

Det originale lineære programmeringsproblem er givet i standardform. Lad os bringe det til kanonisk form ved at indføre en yderligere ikke-negativ variabel i hver af ulighedsbegrænsningerne, dvs.

I det resulterende ligningssystem tager vi som tilladte (grundlæggende) variable x3, x4, x5, x6, så vil de frie variable være x1,x2. Lad os udtrykke de grundlæggende variabler i form af frie.

Forudsat at der ikke er nogen "0-rækker" (lighedsrestriktioner) og "frie" variabler (dvs. variable, der ikke er underlagt kravet om ikke-negativitet).

2. I tilfælde af tilstedeværelsen af lighedsbegrænsninger og "frie" variabler, fortsæt som følger.

Vælg et løsningselement i "0-rækken", og udfør et modificeret Jordan-elimineringstrin, hvorefter denne løsningskolonne overstreges. Denne rækkefølge af handlinger fortsættes indtil simplex bord der er mindst én "0-række" tilbage (i dette tilfælde er tabellen reduceret).

Hvis der også er frie variable, så er det nødvendigt at gøre disse variable grundlæggende. Og efter at den frie variabel bliver grundlæggende, i processen med at bestemme det løsende element, når du søger efter referencen og optimale planer givet linje ikke taget i betragtning (men omregnet).

Degeneration i lineære programmeringsproblemer

Når vi overvejede simpleksmetoden, antog vi, at det lineære programmeringsproblem er ikke-degenereret, dvs. hver referenceplan indeholder nøjagtigt
positive komponenter, hvor
– antallet af begrænsninger i problemet. I en degenereret støtteplan viser antallet af positive komponenter sig at være mindre end antallet af restriktioner: nogle grundlæggende variabler svarende til en given støtteplan har nul værdier. Brug af den geometriske fortolkning til det enkleste tilfælde, hvornår
(antallet af ikke-grundlæggende variable er 2), er det let at skelne et degenereret problem fra et ikke-degenereret problem. I et degenereret problem skærer mere end to linjer hinanden ved det ene toppunkt af polyederen af betingelser, beskrevet af formens ligninger
. Det betyder, at en eller flere sider af betingelsespolygonen er kontraheret til et punkt.

EN skattepligtig hvornår
i et degenereret problem skærer mere end 3 planer hinanden ved et toppunkt
.

Under den antagelse, at problemet ikke var degenereret, var der kun én værdi
, hvorved indekset for vektoren af betingelser afledt af grundlaget (afledt af antallet af grundlæggende variabler) blev bestemt. I et degenereret problem
kan opnås på flere indekser på én gang (for flere rækker). I dette tilfælde vil flere grundvariable i den fundne referenceplan være nul.

Hvis det lineære programmeringsproblem viser sig at være degenereret, så med et dårligt valg af vektoren af betingelser afledt af basis, uendelig bevægelse langs baserne af samme referenceplan. Det såkaldte cykelfænomen. Selvom looping er et ekstremt sjældent fænomen i praktiske lineære programmeringsproblemer, kan dets mulighed ikke udelukkes.

En af metoderne til at bekæmpe degeneration er at transformere problemet ved "mindre" at ændre vektoren på højre side af systemet med begrænsninger af mængder , på en sådan måde, at problemet bliver ikke-degenereret, og på samme tid, så denne ændring ikke rigtig påvirker den optimale plan for problemet.

Mere almindeligt implementerede algoritmer inkluderer nogle simple regler, der reducerer sandsynligheden for, at en loop opstår eller bliver overvundet.

Lad variablen skal gøres grundlæggende. Overvej et sæt indekser , bestående af disse , som det er opnået for
. Masser af indekser , for hvilken denne betingelse er opfyldt, betegner vi den med . Hvis består af et element, så er vektoren af betingelser udelukket fra grundlaget (variabel er lavet ikke-grundlæggende).

Hvis består af mere end et element, så dannes et sæt , som består af
, hvorpå det opnås
. Hvis består af ét indeks , så er variablen udledt af grundlaget . Ellers dannes et sæt etc.

I praksis bør reglen bruges, hvis cykling allerede er opdaget.

Lad os overveje OPP-beslutning ved hjælp af simpleksmetoden og præsentere den i forhold til maksimeringsproblemet.

1. På baggrund af problemets betingelser sammenstilles dens matematiske model.

2. Den færdige model konverteres til den kanoniske form. I dette tilfælde kan et grundlag med en indledende referenceplan identificeres.

3. Den kanoniske model af problemet er skrevet i form af en simplekstabel, så alle frie termer er ikke-negative. Hvis den oprindelige referenceplan er valgt, skal du fortsætte til trin 5.

Simplex tabel: et system af begrænsningsligninger og en objektiv funktion indtastes i form af udtryk, der er løst i forhold til startgrundlaget. Rækken, hvori koefficienterne for objektivfunktionen F er skrevet, kaldes F-rækken eller objektivfunktionsrækken.

4. Find den indledende referenceplan ved at udføre simplekstransformationer med positive opløsningselementer svarende til minimumssimplexrelationerne og uden at tage hensyn til fortegnene for F-rækkeelementerne. Hvis der under transformationerne stødes på en 0-række, hvis elementer, bortset fra det frie led, er nuller, så er systemet af begrænsningsligninger for problemet inkonsistent. Hvis vi støder på en 0-række, hvor der udover det frie led ikke er andre positive elementer, så har systemet af restriktive ligninger ingen ikke-negative løsninger.

Reduktion af system (2.55), (2.56) til et nyt grundlag vil blive kaldt en simplekstransformation. Hvis en simplekstransformation betragtes som en formel algebraisk operation, så kan man bemærke, at som et resultat af denne operation omfordeles roller mellem to variable inkluderet i et bestemt system lineære funktioner: den ene variabel går fra afhængig til uafhængig, og den anden går tværtimod fra uafhængig til afhængig. Denne operation er kendt i algebra som Jordan-elimineringstrinnet.

5. Den fundne indledende støtteplan undersøges for optimalitet:

a) hvis der ikke er negative elementer i F-rækken (frit led ikke medregnet), så er planen optimal. Hvis der ikke er nuller, så er der kun én optimal plan; hvis der er mindst et nul, så er der et uendeligt antal optimale planer;

b) hvis der er mindst et negativt element i F-rækken, som svarer til en kolonne af ikke-positive elementer, så<

c) hvis der er mindst et negativt element i F-rækken, og der er mindst et positivt element i dens kolonne, så kan du flytte til en ny referenceplan, der er tættere på den optimale. For at gøre dette skal den angivne kolonne tildeles som en løsende kolonne, ved hjælp af minimum simplex-relationen, find den løsende række og udfør simplex transformation. Den resulterende referenceplan undersøges igen for optimalitet. Den beskrevne proces gentages, indtil der opnås en optimal plan, eller indtil problemets uløselighed er fastslået.

Kolonnen med koefficienter for en variabel, der er inkluderet i grundlaget, kaldes opløsning. Ved at vælge en variabel indført i basis (eller vælge en opløsende kolonne) baseret på det negative element i F-rækken sikrer vi således, at funktionen F øges.

Det er lidt sværere at bestemme den variabel, der skal udelukkes fra grundlaget. For at gøre dette sammensætter de forholdet mellem frie udtryk og de positive elementer i den løsende kolonne (sådanne relationer kaldes simplex) og finder den mindste blandt dem, som bestemmer rækken (opløsning), der indeholder den udelukkede variabel. Valget af en variabel, der er udelukket fra grundlaget (eller valget af en opløsende linje) i henhold til den minimale simplex-relation garanterer, som det allerede er fastslået, positiviteten af basiskomponenterne i den nye referenceplan.

I punkt 3 i algoritmen antages det, at alle elementer i kolonnen frie termer er ikke-negative. Dette krav er ikke nødvendigt, men hvis det er opfyldt, udføres alle efterfølgende simplex-transformationer kun med positive opløsningselementer, hvilket er praktisk til beregninger. Hvis der er negative tal i kolonnen med frie termer, vælges det løsende element som følger:

1) se gennem rækken, der svarer til et negativt frit led, for eksempel en t-række, og vælg et negativt element i den, og den tilsvarende kolonne tages som løsende (vi antager, at problemets begrænsninger er konsistente);

2) opgør relationerne mellem elementerne i kolonnen med frie udtryk til de tilsvarende elementer i den løsende kolonne, der har de samme tegn (simplekse relationer);

3) vælg den mindste af simpleksrelationerne. Dette vil bestemme aktiveringsstrengen. Lad det for eksempel være en p-streng;

4) i skæringspunktet mellem den løsende kolonne og rækken findes et opløsende element. Hvis et element i y-rækken viser sig at være opløselig, vil efter simplex-transformationen den frie led i denne række blive positiv. Ellers vender næste trin tilbage til t-strengen. Hvis problemet kan løses, vil der efter et vist antal trin ikke være nogen negative elementer tilbage i kolonnen med frie udtryk.

At finde den oprindelige referenceplan, kanonisk visning af ZLP

Ideen om sekventiel forbedring af løsningen dannede grundlaget for en universel metode til løsning af lineære programmeringsproblemer - simplex-metoden eller metoden til sekventiel forbedring af planen.

Simplexmetodens geometriske betydning består i en sekventiel overgang fra et toppunkt af begrænsningspolyederet (kaldet det indledende) til det naboliggende, hvor den lineære funktion tager den bedste (i hvert fald ikke den dårligste) værdi i forhold til målet med problemet; indtil den optimale løsning er fundet - det toppunkt, hvor den optimale værdi af målfunktionen er opnået (hvis problemet har et endeligt optimum).

Først simpleks metode blev foreslået af den amerikanske videnskabsmand J. Dantzig i 1949, men tilbage i 1939 blev ideerne til metoden udviklet af den russiske videnskabsmand L.V. Kantorovich.

Simplex-metoden, som gør det muligt at løse ethvert lineært programmeringsproblem, er universel. I øjeblikket bruges det til computerberegninger, men simple eksempler ved hjælp af simpleksmetoden kan løses manuelt.

For at implementere simplex-metoden - konsekvent forbedring af løsningen - er det nødvendigt at mestre tre hovedelementer:

En metode til at bestemme enhver indledende gennemførlig grundlæggende løsning på et problem;

Reglen om overgang til den bedste (mere præcist, ikke værre) løsning;

Kriterium for kontrol af optimaliteten af den fundne løsning.

For at bruge simpleksmetoden skal det lineære programmeringsproblem reduceres til kanonisk form, dvs. systemet af begrænsninger skal præsenteres i form af ligninger.

Litteraturen beskriver tilstrækkeligt detaljeret: at finde den oprindelige referenceplan (indledende tilladte basisløsning), også at bruge den kunstige basismetode, at finde den optimale referenceplan, at løse problemer ved hjælp af simplekstabeller.

58. Simplexmetodens hovedsætning.

???????????????????????????????????????????????????????????????????????

59. Alternativt optimum i ZLP, degeneration i ZLP.

Degeneration i lineære programmeringsproblemer

Når vi overvejede simpleksmetoden, antog vi, at det lineære programmeringsproblem er ikke-degenereret, dvs. hver støtteplan indeholder præcis m positive komponenter, hvor m er antallet af begrænsninger i problemet. I en degenereret støtteplan viser antallet af positive komponenter sig at være mindre end antallet af restriktioner: nogle grundlæggende variabler svarende til en given støtteplan har nul værdier. Ved at bruge den geometriske fortolkning til det enkleste tilfælde, når n - m = 2 (antallet af ikke-grundlæggende variable er 2), er det let at skelne et degenereret problem fra et ikke-degenereret problem. I en degenereret opgave skærer mere end to rette linjer i det ene toppunkt af betingelsespolyederet, beskrevet ved ligninger på formen xi = 0. Det betyder, at en eller flere sider af betingelsespolygonen er kontraheret til et punkt. På samme måde, for n - m = 3 i et degenereret problem, skærer mere end 3 planer hinanden ved et toppunkt xi = 0. Under den antagelse, at problemet er ikke-degenereret

der var kun én værdi, ved hvilken indekset for vektoren af betingelser afledt af basis (variablen afledt af basis) blev bestemt. I

Det degenererede problem kan opnås på flere indekser på én gang (for flere rækker). I dette tilfælde vil flere grundvariable i den fundne referenceplan være nul. Hvis det lineære programmeringsproblem viser sig at være degenereret, kan der med et dårligt valg af vektoren af betingelser afledt af grundlaget forekomme uendelig bevægelse langs baserne af den samme referenceplan. Dette er det såkaldte looping-fænomen. Selvom looping er ret sjælden i praktiske lineære programmeringsproblemer, er dens mulighed ikke udelukket. En af metoderne til at håndtere degeneration er at transformere problemet ved "mindre" at ændre vektoren på højre side af systemet af begrænsninger på mængder på en sådan måde, at problemet bliver ikke-degenereret, og samtidig tid, så denne ændring ikke rigtig påvirker den optimale plan for problemet. Mere almindeligt implementerede algoritmer inkluderer nogle simple regler, der reducerer sandsynligheden for, at en loop opstår eller bliver overvundet. Lad variablen xj gøres grundlæggende. Lad os overveje

sættet af indekser E0 bestående af de i, som er opnået. Vi betegner det sæt af indekser i, for hvilket denne betingelse er opfyldt af E0,. Hvis E0 består af et element, så er vektoren af betingelser Ai udelukket fra basis (variablen xi gøres ikke-grundlæggende). Hvis E0 består af mere end et element, så dannes mængden E1, som består af , hvorpå . Hvis E1 består af et indeks k, så udledes variablen xk fra basis. Ellers dannes sættet E2 mv. I praksis bør reglen bruges, hvis cykling allerede er opdaget.

Alternativt optimum i ZLP????????????????????????????

60. Kunstig basismetode. M-opgave. Sætning om sammenhængen mellem løsningerne af det oprindelige problem og M-problemet.

Kunstig basismetode.

Den kunstige basismetode bruges til at finde en acceptabel basisløsning på et lineært programmeringsproblem, når betingelsen indeholder begrænsninger af lighedstypen. Lad os overveje problemet:

max(F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0).

De såkaldte "kunstige variable" Rj indføres i begrænsningerne og i målfunktionen som følger:

∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj

Ved indføring af kunstige variable i den kunstige basismetode i objektivfunktionen tildeles de en tilstrækkelig stor koefficient M, hvilket har betydningen af en straf for at indføre kunstige variable. I tilfælde af minimering tilføjes kunstige variable til målfunktionen med en koefficient M. Indførelse af kunstige variable er tilladt, hvis de i processen med at løse problemet successivt forsvinder.

En simplex-tabel, som udarbejdes under løsningsprocessen ved hjælp af den kunstige basismetode, kaldes udvidet. Den adskiller sig fra den sædvanlige ved, at den indeholder to linjer for målfunktionen: en for komponenten F = ∑cixi, og den anden for komponenten M ∑Rj. Overvej proceduren for løsning af problemet på konkret eksempel.

Eksempel 1. Find maksimum af funktionen F(x) = -x1 + 2x2 - x3 under begrænsningerne:

x1≥0, x2≥0, x3≥0.

Lad os bruge den kunstige basismetode. Lad os introducere kunstige variable i problembegrænsningerne

2x1 + 3x2 + x3 + R1 = 3;

x1 + 3x3 + R2 = 2;

Objektiv funktion F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).

Lad os udtrykke summen R1 + R2 fra systemet af begrænsninger: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, derefter F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .

Når vi kompilerer den første simplekstabel (tabel 1), vil vi antage, at de oprindelige variable x1, x2, x3 er ikke-basiske, og de introducerede kunstige variable er grundlæggende. I maksimeringsproblemer vendes fortegnet af koefficienterne for ikke-grundlæggende variable i F- og M-rækkerne. Tegnet for den konstante værdi i M-linjen ændres ikke. Optimering udføres først langs M-linjen. Udvælgelsen af ledende kolonner og rækker, alle simplex-transformationer ved brug af den kunstige basismetode udføres som i den sædvanlige simpleksmetode.

Den maksimale negative koefficient i absolut værdi (-4) bestemmer den førende søjle og variablen x3, som vil gå ind i grundlaget. Det minimale simpleksforhold (2/3) svarer til den anden række i tabellen, derfor skal variablen R2 udelukkes fra grundlaget. Det ledende element er skitseret.

I den kunstige basismetode returneres kunstige variable, der er udelukket fra grundlaget, ikke længere til den, så kolonnerne med elementer i sådanne variable udelades. Bord 2. nedsat med 1 kolonne. Ved at foretage en genberegning af denne tabel går vi videre til tabellen. 3., hvor linjen M er blevet nulstillet, kan den fjernes. Efter at have fjernet alle kunstige variable fra grundlaget, opnår vi en acceptabel basisløsning på det oprindelige problem, som i det betragtede eksempel er optimal:

x1=0; x2=7/9; Fmax=8/9.

Hvis løsningen ikke er optimal ved eliminering af M-strengen, så fortsætter optimeringsproceduren og udføres ved hjælp af den sædvanlige simpleksmetode. Lad os overveje et eksempel, hvor der er begrænsninger af alle typer: ≤,=,≥

Opgaven

Find de optimale produktionsværdier for produkter af type A, B og C. Råvareomkostninger pr. produktionsenhed: A – 5, B – 2, C – 4. Råvaremængde – 2000 enheder. Udstyrsomkostninger pr. produktionsenhed: A – 4, B – 5, C – 4. Udstyrsvolumen – 1000 enheder. Fortjeneste ved salg af en produktionsenhed: A – 10, B – 8, C – 12. Kriteriet er virksomhedens maksimale fortjeneste. Produktionen af produkt A skal være på mindst 100 enheder. Produktionen af produkt B skal være på mindst 50 enheder.

Løsning af simplex-problemet ved hjælp af M-metoden

1) Fastlæggelse af den optimale produktionsplan

Lad x1, x2, x3 være mængden af producerede produkter af henholdsvis type A, B, C. Så har den matematiske model af problemet formen:

F = 10 x1 + 8 x2 + 12 x3 –>maks

Vi introducerer yderligere variable x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0 for at transformere ulighederne til ligheder.

For at vælge et indledende grundlag introducerer vi kunstige variable x8 ≥ 0, x9 ≥ 0 og meget stort antal M (M –> ∞). Vi løser ved hjælp af M-metoden.

F = 10 x1 + 8 x2 + 12 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7– M x8– M x9 –>max

Lad os tage x4 = 2000 som grundlag; x5 = 1000; x8 = 100; x9 = 50.

Vi indtaster dataene i en simplekstabel

Simplex bord nr. 1

Objektiv funktion:

0 2000 + 0 1000 + (– M) 100 + (– M) 50 = – 150 mio.

Vi beregner estimater ved hjælp af formlen:

Δ1 = 0 5 + 0 4 + (– M) 1 + (– M) 0 – 10 = – M – 10

Δ2 = 0 2 + 0 5 + (– M) 0 + (– M) 1 – 8 = – M – 8

Δ3 = 0 4 + 0 4 + (– M) 0 + (– M) 0 – 12 = – 12

Δ4 = 0 1 + 0 0 + (– M) 0 + (– M) 0 – 0 = 0

Δ5 = 0 0 + 0 1 + (– M) 0 + (– M) 0 – 0 = 0

Δ6 = 0 0 + 0 0 + (– M) (–1) + (– M) 0 – 0 = M

Δ7 = 0 0 + 0 0 + (– M) 0 + (– M) (–1) – 0 = M

Δ2 = 0 0 + 12 0 + 10 0 + 8 1 – 8 = 0

Δ3 = 0 0 + 12 1 + 10 0 + 8 0 – 12 = 0

Δ4 = 0 1 + 12 0 + 10 0 + 8 0 – 0 = 0

Δ5 = 0 (–1) + 12 1/4 + 10 0 + 8 0 – 0 = 3

Δ6 = 0 1 + 12 1 + 10 (–1) + 8 0 – 0 = 2

Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7

Da der ikke er nogen negative vurderinger, er planen optimal.

Løsning på problemet: x1 = 100; x2 = 50; x3 = 175/2 = 87,5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450

Svar: x1 = 100; x2 = 50; x3 = 175/2 = 87,5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450 Det vil sige, at det er nødvendigt at producere x1 = 100 enheder af type A-produkter, x2 = 50 enheder af type B-produkter og x3 = 87,5 enheder af type C-produkter. Maksimal fortjeneste i dette tilfælde vil det være Fmax = 2450 enheder.

Sætning om sammenhængen mellem løsningerne af det oprindelige problem og M-problemet.

???????????????????????

På grafisk metode til løsning af LP-problemer valgte vi faktisk fra mængden af toppunkter, der hører til grænsen for mængden af løsninger til systemet af uligheder, et toppunkt, hvor værdien af den objektive funktion nåede et maksimum (minimum). I tilfælde af to variable er denne metode fuldstændig intuitiv og giver dig mulighed for hurtigt at finde en løsning på problemet.

Hvis et problem har tre eller flere variabler, og i reelle økonomiske problemer er dette præcis situationen, er det vanskeligt at visualisere løsningsområdet for systemet af begrænsninger. Sådanne problemer løses vha simpleks metode eller metode konsekvente forbedringer. Ideen med metoden er enkel og er som følger.

Ifølge en bestemt regel findes den oprindelige referenceplan (noget toppunkt af begrænsningsområdet). Den tjekker om planen er optimal. Hvis ja, så er problemet løst. Hvis ikke, så går vi videre til en anden forbedret plan – til en anden top. værdien af den objektive funktion på dette plan (ved dette toppunkt) er åbenbart bedre end i det foregående. Overgangsalgoritmen udføres ved hjælp af et bestemt beregningstrin, som bekvemt er skrevet i form af tabeller kaldet simplex tabeller . Siden toppen endeligt nummer, så når vi i et begrænset antal trin frem til den optimale løsning.

Lad os overveje simpleksmetoden ved hjælp af et specifikt eksempel på problemet med at udarbejde en plan.

Lad os endnu en gang bemærke, at simpleksmetoden er anvendelig til at løse kanoniske problemer LP'er reduceret til en speciel form, dvs. at have et grundlag, positive højresider og en objektiv funktion udtrykt i form af ikke-grundlæggende variable. Hvis opgaven ikke er reduceret til en speciel form, er der behov for yderligere trin, som vi vil tale om senere.

Lad os overveje problemet med en produktionsplan, efter at vi tidligere har konstrueret en model og bragt den til en speciel form.

Opgave.

Til fremstilling af produkter EN Og I Lageret kan højst frigive 80 enheder råvarer. Desuden til fremstilling af produktet EN to enheder forbruges, og produkterne I- en enhed råvarer. Det er nødvendigt at planlægge produktionen, så den største fortjeneste sikres, hvis produkterne EN det er påkrævet at producere ikke mere end 50 stykker og produkter I- højst 40 stk. Desuden fortjeneste fra salg af ét produkt EN- 5 rubler, og fra I- 3 gnidninger.

Lad os bygge matematisk model, betegner som x 1 mængde produkter A i plan, for x 2 - antal produkter I. så vil begrænsningssystemet se sådan ud:

Lad os bringe problemet til kanonisk form ved at introducere yderligere variabler:

(3.10)

F = -5x 1 - 3x 2 → min.

Denne opgave har speciel type(med basis er højre sider ikke-negative). Det kan løses ved hjælp af simpleksmetoden.

jegscene. Registrering af et problem i en simplekstabel. Der er en en-til-en overensstemmelse mellem systemet af begrænsninger af problemet (3.10) og simplekstabellen. Der er lige så mange rækker i tabellen, som der er ligheder i systemet af begrænsninger, og der er lige så mange kolonner, som der er frie variable. Grundlæggende variabler fylder den første kolonne, frie - øverste linje borde. Bundlinjen kaldes indekslinjen; koefficienterne for variablerne i objektivfunktionen er skrevet i den. I nederste højre hjørne skrives 0 i første omgang, hvis der ikke er et ledigt medlem i funktionen; hvis der er, så skriv det med modsat fortegn. På dette sted (i nederste højre hjørne) vil der være en værdi af objektivfunktionen, som bør stige i absolut værdi, når du flytter fra en tabel til en anden. Så Tabel 3.4 svarer til vores system af restriktioner, og vi kan gå videre til fase II af løsningen.

Tabel 3.4

grundlæggende			gratis

IIscene. Kontrol af referenceplanen for optimalitet.

Denne tabel 3.4 svarer til følgende referenceplan:

(x 1 , x 2 , x 3 , x 4 , x 5) = (0, 0, 50, 40, 80).

Gratis variabler x 1 , x 2 er lig med 0; x 1 = 0, x 2 = 0. Og de grundlæggende variable x 3 , x 4 , x 5 tage værdier x 3 = 50, x 4 = 40, x 5 = 80 - fra kolonnen frie vilkår. Objektiv funktionsværdi:

-F = - 5x 1 - 3x 2 = -5 0 - 3 0 = 0.

Vores opgave er at tjekke, om en given referenceplan er optimal. For at gøre dette skal du se på indekslinjen - målfunktionslinjen F.

Forskellige situationer er mulige.

1. I indekset F- der er ingen negative elementer i strengen. Det betyder, at planen er optimal, og en løsning på problemet kan skrives ned. Den objektive funktion har nået sit mål optimal værdi, lig med tallet i nederste højre hjørne, taget med det modsatte fortegn. Lad os gå videre til fase IV.

2. Indeksrækken har mindst ét negativt element, hvis kolonne ikke har positive elementer. Så konkluderer vi, at den objektive funktion F→∞ falder uden grænse.

3. Indeksrækken har et negativt element, der har mindst ét positivt element i sin kolonne. Så går vi videre til næste fase III. Vi genberegner tabellen og forbedrer referenceplanen.

IIIscene. Forbedring af referenceplanen.

Fra de negative elementer i indekset F-rækker, vælg den med det største modul, kald den tilsvarende kolonneopløsning og marker den med "".

For at vælge en løsende række er det nødvendigt at beregne forholdet mellem elementerne i kolonnen frie termer kun Til positiv elementer i opløsningskolonnen. Vælg den mindste fra de opnåede relationer. Det tilsvarende element, hvor minimum er nået, kaldes opløsning. Vi vil fremhæve det med en firkant.

I vores eksempel, , element 2 er tilladt. Linjen, der svarer til dette element, kaldes også opløsning (tabel 3.5).

Tabel 3.5

Efter at have valgt det tilladte element, genberegner vi tabellen i henhold til reglerne:

1. I en ny tabel af samme størrelse som før ombyttes variablerne i den løsende række og kolonne, hvilket svarer til overgangen til et nyt grundlag. I vores eksempel: x 1 indgår i grundlaget i stedet for x 5, som forlader grundlaget og nu er gratis (tabel 3.6).

Tabel 3.6

grundlæggende			gratis

2. Skriv dets omvendte tal i stedet for det løsende element 2.

3. Vi deler opløsningslinjens elementer med opløsningselementet.

4. Vi deler opløsningskolonnens elementer med opløsningselementet og skriver dem med modsat fortegn.

5. For at udfylde de resterende elementer i tabel 3.6 omregner vi ved hjælp af rektangelreglen. Lad os sige, at vi vil tælle elementet ved position 50.

Vi forbinder mentalt dette element med det løsende, find produktet, fratræk produktet af elementerne placeret på den anden diagonal af det resulterende rektangel. Vi dividerer forskellen med det løsende element.

Så, . Vi skriver 10 på det sted, hvor der var 50. Tilsvarende :

, , , .

Tabel 3.7

Vi har nyt bord 3.7, er de grundlæggende variable nu variablerne (x 3,x 4,x 1). Værdien af den objektive funktion blev lig med -200, dvs. faldt. For at kontrollere denne grundlæggende løsning for optimalitet, skal vi gå igen til fase II. Processen er åbenlyst begrænset; stopkriteriet er punkt 1 og 2 i trin II.

Lad os færdiggøre løsningen af problemet. For at gøre dette, lad os kontrollere indekslinjen og, når vi ser et negativt element i den, kalder den tilsvarende kolonneopløsning og genberegner tabellen i henhold til trin III. Efter at have kompileret relationerne og valgt minimum = 40 blandt dem, bestemte vi det løsende element 1. Nu udfører vi genberegningen i henhold til reglerne 2-5.

Tabel 3.8

grundlæggende

gratis

x 3 = 30, x 2 = 40, x 1 = 20. Frie variabler er 0, x 5 = 0, x 4 = 0. Objektivfunktionen tager værdien sidste element kolonne med frie udtryk med det modsatte fortegn: - F = -220 F = 220, i vores eksempel blev funktionen undersøgt ved min, og indledningsvis F max, så skiltet skiftede faktisk to gange. Så, x* = (20, 40, 30, 0, 0), F* = 220. Svar på problemet:

Det er nødvendigt at medtage 20 produkter af typen i produktionsplanen EN, 40 produkter af type B, mens fortjenesten vil være maksimal og vil være lig med 220 rubler.

I slutningen af dette afsnit præsenterer vi et flowchart af simplex-metodealgoritmen, som nøjagtigt gentager trinene, men måske for nogle læsere vil det være mere praktisk at bruge, da pilene angiver en klar retning af handlinger.

Linkene over boksene i rutediagrammet angiver, hvilket trin eller underpunkt den tilsvarende gruppe af transformationer tilhører. reglen for at finde den oprindelige referenceplan vil blive formuleret i afsnit 3.7.

Spørgsmål til selvkontrol

1. Hvordan er et simpleksbord opbygget?

2. Hvordan afspejles en ændring i grundlaget i tabellen?

3. Formuler stopkriteriet for simpleksmetoden.

4. Hvordan organiserer man tabelgenberegning?

5. Fra hvilken linje er det praktisk at begynde at genberegne tabellen?