Tabulárna simplexová metóda online. Vyriešte úlohu lineárneho programovania simplexnou metódou

Tu je ručné (nie appletové) riešenie dvoch problémov pomocou simplexnej metódy (podobne ako appletové riešenie) s podrobnými vysvetleniami, aby ste pochopili algoritmus riešenia problémov simplexnou metódou. Prvá úloha obsahuje znaky nerovnosti len " ≤ " (problém s počiatočným základom), druhá môže obsahovať znaky " ≥ ", " ≤ " alebo " = " (úloha s umelým základom), riešia sa v rôznych spôsoby.

Simplexná metóda, riešenie úlohy s východiskovým základom

1)Simplexná metóda pre problém s počiatočným základom (všetky znaky obmedzujúcich nerovností sú " ≤ ").

Napíšme problém kanonický forme, t.j. obmedzenia nerovností prepíšeme na rovnosti a pridáme súvahy premenné:

Táto sústava je sústava s bázou (báza s 1, s 2, s 3, každá z nich je obsiahnutá len v jednej rovnici sústavy s koeficientom 1), x 1 a x 2 sú voľné premenné. Úlohy, na ktoré sa použije simplexová metóda, musia mať tieto dve vlastnosti: - systém obmedzení musí byť sústavou rovníc so základom; -voľné členy všetkých rovníc v systéme musia byť nezáporné.

Výsledný systém je systém so základom a jeho voľné termíny sú nezáporné, takže môžeme aplikovať simplexná metóda. Zostavte prvú simplexnú tabuľku (iterácia 0) na riešenie problému simplexná metóda, t.j. tabuľku koeficientov účelovej funkcie a sústavu rovníc pre príslušné premenné. Tu "BP" znamená stĺpec základných premenných, "Solution" - stĺpec pravých častí rovníc systému. Riešenie nie je optimálne, pretože v z-línii sú záporné koeficienty.

iterácia simplexnej metódy 0

Na zlepšenie riešenia prejdime k ďalšej iterácii simplexná metóda, dostaneme nasledujúce simplexné tablo. Na to si musíte vybrať povoliť stĺpec, t.j. premenná, ktorá vstúpi do základu pri ďalšej iterácii simplexovej metódy. Vyberá sa najväčším záporným koeficientom v z-riadku (v maximálnom probléme) - v počiatočnej iterácii simplexovej metódy je to stĺpec x 2 (koeficient -6).

Potom si vyberte reťazec povolenia, t.j. premenná, ktorá opustí základ pri ďalšej iterácii simplexovej metódy. Vyberá sa najmenším pomerom stĺpca „Rozhodnutie“ k zodpovedajúcim kladným prvkom rozlišovacieho stĺpca (stĺpec „Pomer“) – v počiatočnej iterácii je to riadok s 3 (koeficient 20).

Permisívny prvok sa nachádza na priesečníku povoľujúceho stĺpca a povoľujúceho riadku, jeho bunka je farebne zvýraznená, rovná sa 1. Preto pri ďalšej iterácii simplexnej metódy premenná x 2 nahradí s 1 v základe. Všimnite si, že vzťah sa nehľadá v reťazci z, vloží sa tam pomlčka „-“. Ak existujú rovnaké minimálne pomery, vyberie sa ktorýkoľvek z nich. Ak sú všetky koeficienty v stĺpci rozlíšenia menšie alebo rovné 0, riešenie problému je nekonečné.

Vyplňte nasledujúcu tabuľku „Iterácia 1“. Získame to z tabuľky "Iterácia 0". Účelom ďalších transformácií je zmeniť stĺpec povolenia x2 na jeden stĺpec (s jedným namiesto prvku enable a nulami namiesto ostatných prvkov).

1) Výpočet riadku x 2 tabuľky "Iterácia 1". Najprv vydelíme všetky členy rozlišovacieho riadku s 3 tabuľky "Iterácia 0" rozlišovacím prvkom (v tomto prípade sa rovná 1) tejto tabuľky, dostaneme riadok x 2 v tabuľke "Iterácia 1" . Pretože rozlišovací prvok je v tomto prípade rovný 1, potom sa riadok s 3 tabuľky "Iterácia 0" bude zhodovať s riadkom x 2 tabuľky "Iterácia 1". Riadok x 2 tabuľky „Iterácia 1“ sme dostali 0 1 0 0 1 20, zvyšné riadky tabuľky „Iterácia 1“ získame z tohto riadka a riadkov tabuľky „Iterácia 0“ takto:

2) Výpočet z-riadku tabuľky "Iterácia 1". Namiesto -6 v prvom riadku (riadok z) v stĺpci x2 tabuľky "Iterácia 0" by mala byť v prvom riadku tabuľky "Iterácia 1" 0. Aby sme to dosiahli, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 6, dostaneme 0 6 0 0 6 120 a tento riadok pridáme k prvému riadku (z - riadok) tabuľky "Iterácia 0" -4 -6 0 0 0 0, dostaneme -4 0 0 0 6 120. V stĺpci x 2 sa objavila nula 0, cieľ bol dosiahnutý. Prvky stĺpca povolenia x 2 sú zvýraznené červenou farbou.

3) Výpočet riadku s 1 tabuľky "Iterácia 1". Namiesto 1 na s 1 riadok tabuľky "Iterácia 0" by mal byť 0 v tabuľke "Iterácia 1". Aby sme to urobili, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 -1, dostaneme 0 -1 0 0 -1 -20 a pridáme tento riadok s 1 - riadku tabuľky "Iterácia 0" 2 1 1 0 0 64 dostaneme riadok 2 0 1 0 -1 44. Požadovaná 0 sa získa v stĺpci x 2.

4) Výpočet riadku s 2 tabuľky "Iterácia 1". Namiesto 3 v s 2 riadku tabuľky "Iterácia 0" by mala byť v tabuľke "Iterácia 1" 0. Aby sme to dosiahli, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 -3, dostaneme 0 -3 0 0 -3 -60 a pridáme tento riadok s 1 - riadku tabuľky "Iterácia 0" 1 3 0 1 0 72, dostaneme riadok 1 0 0 1 -3 12. Požadovaná 0 sa získa v stĺpci x 2. Stĺpec x 2 v tabuľke "Iterácia 1" má stať single, obsahuje jednu 1 a zvyšok 0.

Riadky tabuľky "Iterácia 1" sa získajú podľa nasledujúceho pravidla:

Nový riadok = starý riadok - (faktor povolenia starého riadka)* (nový riadok).

Napríklad pre z-riadok máme:

Starý z-reťazec (-4 -6 0 0 0 0) -(-6)*Nový z-reťazec -(0 -6 0 0 -6 -120) = Nový z-reťazec (-4 0 0 0 6 120) .

Pre nasledujúce tabuľky je prepočet prvkov tabuľky urobený podobným spôsobom, preto ho vynecháme.

iterácia simplexnej metódy 1

Povolený stĺpec x 1 , povolený riadok s 2 , s 2 opustí základ, x 1 vstúpi do základu. Presne rovnakým spôsobom získame zvyšné simplexné tabuľky, kým nezískame tabuľku so všetkými kladnými koeficientmi v z-riadku. To je znak optimálneho stola.

iterácia simplexnej metódy 2

Vyriešenie stĺpca s 3 , vyriešenie riadku s 1 , s 1 opustí základ, s 3 vstúpi do základu.

iterácia simplexnej metódy 3

V z-riadku sú všetky koeficienty nezáporné, preto sa získa optimálne riešenie x 1 \u003d 24, x 2 \u003d 16, z max \u003d 192.

Na výrobu troch druhov košieľ sa používajú nite, gombíky a látky. Zásoby nití, gombíkov a látok, ich spotreba na ušitie jednej košele sú uvedené v tabuľke. Nájdite maximálny zisk a optimálny plán vydania produktu, ktorý to zabezpečuje (nájdite ).

Riešenie problému

Stavba modelu

Cez a počet košieľ 1., 2. a 3. typu, určených na uvoľnenie.

Potom budú limity zdrojov vyzerať takto:

Navyše podľa zmyslu úlohy

Cieľová funkcia vyjadrujúca získaný zisk:

Dostaneme nasledujúci problém lineárneho programovania:

Redukcia problému lineárneho programovania na kanonickú formu

Prenesme problém do kanonickej podoby. Predstavme si ďalšie premenné. Všetky dodatočné premenné zavedieme do účelovej funkcie s koeficientom rovným nule. Do ľavých častí obmedzení pridáme ďalšie premenné, ktoré nemajú preferovaný tvar, a dostaneme rovnosti.

Riešenie úlohy simplexnou metódou

Vyplňte simplexnú tabuľku:

Keďže problém riešime na maximum - prítomnosť v indexovom riadku záporné čísla pri riešení maximálneho problému naznačuje, že sme nezískali optimálne riešenie a je potrebné prejsť z tabuľky 0. iterácie na ďalšiu.

Prechod na ďalšiu iteráciu sa vykonáva takto:

zhody vedúcich stĺpcov

Kľúčový riadok je určený minimálnymi pomermi voľných členov a členov vedúceho stĺpca (simplexné pomery):

Na priesečníku kľúčového stĺpca a kľúčového radu nájdeme povoľovací prvok, t.j. 9.

Teraz začneme zostavovať 1. iteráciu: Namiesto jednotkového vektora zavedieme vektor .

V novej tabuľke napíšeme 1 na miesto povoľujúceho prvku, všetky ostatné prvky kľúčového stĺpca sú nuly. Prvky kľúčového reťazca sú rozdelené permisívnym prvkom. Všetky ostatné prvky tabuľky sa vypočítajú podľa pravidla obdĺžnika.

Kľúčový stĺpec pre zhody 1. iterácie

Rozlišovacím prvkom je číslo 4/3. Vektor odvodíme zo základu a namiesto neho zavedieme vektor. Dostaneme tabuľku 2. iterácie.

Kľúčový stĺpec pre 2. iteráciu zodpovedá

Nájdeme kľúčový riadok, na ktorý definujeme:

Rozlišovacím prvkom je číslo 10/3. Vektor odvodíme zo základu a namiesto neho zavedieme vektor. Dostaneme tabuľku 3. iterácie.

V riadku indexu sú všetky členy nezáporné, takže dostaneme nasledovné riešenie úlohy lineárneho programovania (vypíšeme ho zo stĺpca voľných členov):

Je potrebné ušiť 24 košieľ 1. druhu, 7 košieľ 2. typu a 3 košele 3. typu. V tomto prípade bude získaný zisk maximálny a bude predstavovať 95 rubľov.

Príklad 5.1. Vyriešte nasledujúci problém lineárneho programovania pomocou simplexnej metódy:

Riešenie:

ja iterácia:

x3, x4, x5, x6 x1,x2. Základné premenné vyjadrujeme pomocou voľných:

Objektívnu funkciu privedieme do nasledujúceho tvaru:

Na základe získaného problému vytvoríme počiatočnú simplexnú tabuľku:

Tabuľka 5.3

Počiatočná simplexná tabuľka

Podľa definície základného riešenia sa voľné premenné rovnajú nule a hodnoty základných premenných sa rovnajú zodpovedajúcim hodnotám voľných čísel, t.j.:

3. fáza: kontrola zlučiteľnosti systému obmedzení programu celoživotného vzdelávania.

Pri tejto iterácii (v tabuľke 5.3) sa nezistil znak nekonzistentnosti systému obmedzení (prvok 1) (t. j. neexistuje riadok so záporným voľným číslom (okrem riadku účelovej funkcie), ktorý by neobsahoval aspoň jeden záporný prvok (t. j. záporný koeficient pre voľnú premennú)).

Pri tejto iterácii (v tabuľke 5.3) sa nezistilo znamienko neohraničenosti účelovej funkcie (znamienko 2) (t. j. v riadku účelovej funkcie nie je stĺpec so záporným prvkom (okrem stĺpca voľných čísel) v ktorom by bol aspoň jeden pozitívny prvok) .

Keďže nájdené základné riešenie neobsahuje negatívne zložky, je prípustné.

6. fáza: kontrola optimálnosti.

Nájdené základné riešenie nie je optimálne, pretože podľa kritéria optimality (znak 4) by v riadku účelovej funkcie nemali byť žiadne záporné prvky (voľné číslo tohto riadku sa pri posudzovaní tohto znamienka neberie do úvahy ). Preto podľa algoritmu simplexovej metódy prejdeme do 8. etapy.

Keďže nájdené základné riešenie je prípustné, budeme hľadať rozlišovací stĺpec podľa nasledujúcej schémy: určíme stĺpce so zápornými prvkami v riadku účelovej funkcie (okrem stĺpca voľných čísel). Podľa tabuľky 5.3 existujú dva takéto stĺpce: stĺpec " x1"a stĺpec" x2". Z takýchto stĺpcov sa vyberie ten, ktorý obsahuje najmenší prvok v riadku účelovej funkcie. Bude riešiť. stĺpec " x2' obsahuje najmenší prvok (-3) v porovnaní so stĺpcom ' x1

Na určenie permisívneho reťazca nájdeme kladné odhadované pomery voľných čísel k prvkom permisívneho stĺpca, reťazec, ktorý zodpovedá najmenšiemu kladnému odhadovanému pomeru, sa berie ako povolený.

Tabuľka 5.4

Počiatočná simplexná tabuľka

V tabuľke 5.4 najmenší kladný pomer hodnotenia zodpovedá riadku " x5“, preto sa to vyrieši.

Prvok umiestnený na priesečníku povoľovacieho stĺpca a povoľovacej čiary je akceptovaný ako povoľujúci. V našom príklade je to prvok, ktorý sa nachádza na priesečníku čiary " x5» a stĺpce « x2».

Rozlišovací prvok zobrazuje jednu základnú a jednu voľnú premennú, ktoré je potrebné prehodiť v simplexnej tabuľke, aby ste prešli na nové „vylepšené“ základné riešenie. V tomto prípade ide o premenné. x5 a x2, v novej simplexnej tabuľke (tabuľka 5.5) ich prehodíme.

9.1. Povoliť transformáciu prvkov.

Permisívny prvok tabuľky 5.4 sa transformuje takto:

Získaný výsledok zadáme do podobnej bunky v tabuľke 5.5.

9.2. Povoliť konverziu reťazca.

Prvky permisívneho riadku tabuľky 5.4 sú rozdelené permisívnym prvkom tejto simplexnej tabuľky, výsledky zapadajú do podobných buniek novej simplexnej tabuľky (tabuľka 5.5). Transformácie prvkov povoľovacieho reťazca sú uvedené v tabuľke 5.5.

9.3. Povolená transformácia stĺpca.

Prvky rozlišovacieho stĺpca tabuľky 5.4 sú rozdelené rozlišovacím prvkom tejto simplexnej tabuľky a výsledok sa berie s opačným znamienkom. Získané výsledky zapadajú do podobných buniek novej simplexnej tabuľky (tabuľky 5.5). Transformácie prvkov rozlišovacej kolóny sú uvedené v tabuľke 5.5.

9.4. Transformácia zostávajúcich prvkov simplexnej tabuľky.

Transformácia ostatných prvkov simplexnej tabuľky (t. j. prvkov nenachádzajúcich sa v rozlišovacom riadku a rozlišovacom stĺpci) sa vykonáva podľa pravidla "obdĺžnik".

Zvážte napríklad transformáciu prvku umiestneného na priesečníku reťazca " x3“ a stĺpce „“, podmienečne ho označujú ako „ x3". V tabuľke 5.4 mentálne nakreslíme obdĺžnik, ktorého jeden vrchol sa nachádza v bunke, ktorej hodnota sa transformuje (t. j. v bunke " x3“) a druhý (diagonálny vrchol) je v bunke s rozlišovacím prvkom. Ďalšie dva vrcholy (druhej uhlopriečky) sú jednoznačne určené. Potom transformovaná hodnota bunky " x3"bude sa rovnať predchádzajúcej hodnote tejto bunky mínus zlomok, v menovateli ktorého je rozlišovací prvok (z tabuľky 5.4) a v čitateli súčin dvoch ďalších nepoužitých vrcholov, t.j.:

« x3»: .

Hodnoty ostatných buniek sa prevedú podobne:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

V dôsledku týchto transformácií bola získaná nová simplexná tabuľka (tabuľka 5.5).

II iterácia:

1. fáza: zostavenie simplexnej tabuľky.

Tabuľka 5.5

Simplexný stôlII iterácií

2. fáza: stanovenie základného roztoku.

V dôsledku simplexných transformácií sa získalo nové základné riešenie (tabuľka 5.5):

Ako vidíte, pri tomto základnom riešení je hodnota účelovej funkcie =15, čo je viac ako pri predchádzajúcom základnom riešení.

Nekonzistentnosť systému obmedzení podľa znaku 1 v tabuľke 5.5 nebola zistená.

4. fáza: kontrola ohraničenosti účelovej funkcie.

Neohraničenosť účelovej funkcie v súlade so znakom 2 v tabuľke 5.5 nebola zistená.

5. etapa: kontrola prípustnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa znaku 4 nie je optimálne, keďže riadok účelovej funkcie simplexovej tabuľky (tabuľka 5.5) obsahuje záporný prvok: -2 (voľné číslo tohto riadku sa pri uvažovaní neberie do úvahy). vlastnosť). Prejdime teda na krok 8.

Fáza 8: definícia aktivačného prvku.

8.1. Definícia rozlišovacieho stĺpca.

Nájdené základné riešenie je prípustné, v riadku účelovej funkcie určíme stĺpce so zápornými prvkami (okrem stĺpca voľných čísel). Podľa tabuľky 5.5 existuje iba jeden takýto stĺpec: " x1". Preto to akceptujeme ako povolené.

8.2. Definícia permisívneho reťazca.

Podľa získaných hodnôt kladných odhadovaných pomerov v tabuľke 5.6 je minimom pomer zodpovedajúci riadku " x3". Preto to akceptujeme ako povolené.

Tabuľka 5.6

Simplexný stôlII iterácií

Fáza 9: transformácia simplexnej tabuľky.

Transformácie simplexnej tabuľky (tabuľka 5.6) sa vykonávajú rovnakým spôsobom ako v predchádzajúcej iterácii. Výsledky transformácií prvkov simplexnej tabuľky sú uvedené v tabuľke 5.7.

III iteráciu

Na základe výsledkov simplexných transformácií predchádzajúcej iterácie zostavíme novú simplexnú tabuľku:

Tabuľka 5.7

Simplexný stôlIII iterácií

2. fáza: stanovenie základného roztoku.

Ako výsledok simplexných transformácií sa získalo nové základné riešenie (tabuľka 5.7):

3. fáza: kontrola zlučiteľnosti systému obmedzení.

Nekonzistentnosť systému obmedzení podľa znaku 1 v tabuľke 5.7 nebola zistená.

4. fáza: kontrola ohraničenosti účelovej funkcie.

Neohraničenosť účelovej funkcie v súlade so znakom 2 v tabuľke 5.7 nebola odhalená.

5. etapa: kontrola prípustnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa kritéria 3 je prípustné, pretože neobsahuje negatívne zložky.

6. fáza: kontrola optimálnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa znaku 4 nie je optimálne, keďže riadok účelovej funkcie simplexovej tabuľky (tabuľka 5.7) obsahuje záporný prvok: -3 (voľné číslo tohto riadku sa pri uvažovaní neberie do úvahy vlastnosť). Prejdime teda na krok 8.

Fáza 8: definícia aktivačného prvku.

8.1. Definícia rozlišovacieho stĺpca.

Nájdené základné riešenie je prípustné, v riadku účelovej funkcie určíme stĺpce so zápornými prvkami (okrem stĺpca voľných čísel). Podľa tabuľky 5.7 existuje iba jeden takýto stĺpec: " x5". Preto to akceptujeme ako povolené.

8.2. Definícia permisívneho reťazca.

Podľa získaných hodnôt kladných odhadovaných pomerov v tabuľke 5.8 je minimom pomer zodpovedajúci riadku " x4". Preto to akceptujeme ako povolené.

Tabuľka 5.8

Simplexný stôlIII iterácií

Fáza 9: transformácia simplexnej tabuľky.

Transformácie simplexnej tabuľky (tabuľka 5.8) sa vykonávajú rovnakým spôsobom ako v predchádzajúcej iterácii. Výsledky transformácií prvkov simplexnej tabuľky sú uvedené v tabuľke 5.9.

IV iteráciu

1. etapa: konštrukcia nového simplexného stola.

Na základe výsledkov simplexných transformácií predchádzajúcej iterácie zostavíme novú simplexnú tabuľku:

Tabuľka 5.9

Simplexný stôlIV iterácií

2. fáza: stanovenie základného roztoku.

V dôsledku simplexných transformácií sa získalo nové základné riešenie podľa tabuľky 5.9, riešenie je nasledovné:

3. fáza: kontrola zlučiteľnosti systému obmedzení.

Nekonzistentnosť systému obmedzení podľa znaku 1 v tabuľke 5.9 nebola zistená.

4. fáza: kontrola ohraničenosti účelovej funkcie.

Neohraničenosť účelovej funkcie v súlade so znakom 2 v tabuľke 5.9 nebola zistená.

5. etapa: kontrola prípustnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa kritéria 3 je prípustné, pretože neobsahuje negatívne zložky.

6. fáza: kontrola optimálnosti nájdeného základného riešenia.

Základné riešenie nájdené podľa znaku 4 je optimálne, keďže v riadku účelovej funkcie simplexnej tabuľky (tabuľka 5.9) nie sú žiadne záporné prvky (voľné číslo tohto riadka sa pri posudzovaní tohto znaku neberie do úvahy) .

7. fáza: kontrola alternatívneho riešenia.

Nájdené riešenie je jediné, keďže v riadku účelovej funkcie (tabuľka 5.9) nie sú žiadne nulové prvky (pri posudzovaní tejto vlastnosti sa neberie do úvahy voľné číslo tohto riadku).

odpoveď: optimálna hodnota objektívnej funkcie uvažovaného problému =24, ktorá sa dosiahne pri.

Príklad 5.2. Vyriešte vyššie uvedený problém lineárneho programovania za predpokladu, že cieľová funkcia je minimalizovaná:

Riešenie:

ja iterácia:

Fáza 1: vytvorenie počiatočnej simplexnej tabuľky.

Pôvodný problém lineárneho programovania je uvedený v štandardnej forme. Dostaňme to do kanonickej podoby zavedením ďalšej nezápornej premennej do každého z obmedzení nerovnosti, t.j.

Vo výslednej sústave rovníc berieme ako povolené (základné) premenné x3, x4, x5, x6, potom sú voľné premenné x1,x2. Základné premenné vyjadrujeme v termínoch voľných.

Pridelenie služby. Služba je určená pre online riešeniaúlohy lineárneho programovania (LPP) pomocou simplexnej metódy v nasledujúcich formách:

• vo forme simplexnej tabuľky (metóda Jordanových transformácií); základná forma záznamu;
• modifikovaná simplexová metóda; vo forme stĺpca; v riadkovej forme.

Inštrukcia. Vyberte počet premenných a počet riadkov (počet obmedzení). Výsledné riešenie sa uloží do súboru Word a Excel. Zároveň neberte do úvahy obmedzenia typu x i ≥0. Ak nie sú v úlohe žiadne obmedzenia pre niektoré x i, tak treba LLP zredukovať na KZLP, alebo využiť túto službu. Riešenie automaticky určuje použitie M-metóda(jednoduchá metóda s umelým základom) a dvojstupňová simplexná metóda.

S touto kalkulačkou sa používajú aj nasledujúce položky:
Grafická metóda riešenia LLP
Riešenie dopravného problému
Riešenie maticovej hry
Pomocou služby online môžete určiť cenu maticovej hry (dolná a horná hranica), skontrolovať sedlový bod, nájsť riešenie zmiešanej stratégie pomocou nasledujúcich metód: minimax, simplexová metóda, grafická (geometrická) metóda, Brownova metóda.
Extrém funkcie dvoch premenných
Problémy dynamického programovania
Rozdeľte 5 homogénnych dávok tovaru medzi tri trhy tak, aby ste z ich predaja získali maximálny príjem. Príjem z predaja na každom trhu G(X) závisí od počtu predaných šarží tovaru X a je uvedený v tabuľke.

Algoritmus simplexnej metódy zahŕňa nasledujúce kroky:

1. Zostavenie prvého základného plánu. Prechod na kanonickú formu problému lineárneho programovania zavedením nezáporných dodatočných bilančných premenných.
2. Kontrola optimálneho plánu. Ak existuje aspoň jeden koeficient riadka indexu menej ako nula, potom plán nie je optimálny a treba ho zlepšiť.
3. Definovanie úvodných stĺpcov a riadkov. Zo záporných koeficientov indexovej čiary sa vyberie najväčší v absolútnej hodnote. Potom rozdelí prvky stĺpca voľných členov simplexnej tabuľky na prvky rovnakého znamienka vedúceho stĺpca.
4. Budovanie novej základnej línie. Prechod na nový plán sa uskutočňuje v dôsledku prepočtu simplexnej tabuľky Jordan-Gaussovou metódou.

Extrémne riešenie sa dosiahne na hranici oblasti realizovateľných riešení v jednom z vrcholov rohových bodov mnohouholníka alebo na úseku medzi dvoma susednými rohovými bodmi.

Základná veta lineárneho programovania. Ak cieľová funkcia LLP dosiahne v určitom bode v oblasti realizovateľných riešení extrémnu hodnotu, nadobudne túto hodnotu v rohovom bode. Ak cieľová funkcia LLP dosiahne extrémnu hodnotu vo viac ako jednom rohovom bode, potom nadobudne rovnakú hodnotu v ktorejkoľvek z konvexných lineárnych kombinácií týchto bodov.

Podstata simplexovej metódy. Pohyb do optimálneho bodu sa vykonáva pohybom od jedného rohového bodu k ďalšiemu, čím sa priblíži a urýchli X opt. Takáto schéma sčítania bodov, nazývaná simplexná metóda, navrhol R. Danzig.
Rohové body sú charakterizované m základnými premennými, takže prechod z jedného rohového bodu do susedného je možné vykonať zmenou len jednej základnej premennej v báze na premennú z nezákladnej.
Implementácia simplexovej metódy v praxi rôzne funkcie a problémové vyhlásenia LP má rôzne modifikácie.

Konštrukcia simplexových stolov pokračuje, kým sa nedosiahne optimálne riešenie.

Ako pomocou simplexnej tabuľky určiť, že riešenie úlohy lineárneho programovania je optimálne?
Ak posledný riadok (hodnoty objektívnej funkcie) neobsahuje záporné prvky, nájde optimálny plán.

Poznámka 1. Ak sa jedna zo základných premenných rovná nule, potom krajný bod zodpovedajúci takémuto základnému riešeniu je degenerovaný. Degenerácia nastáva, keď existuje nejednoznačnosť vo výbere vedúceho radu. Degeneráciu problému si vôbec nemusíte všimnúť, ak si ako návod zvolíte inú líniu. V prípade nejednoznačnosti by sa mal vybrať riadok s najnižším indexom, aby sa predišlo zacykleniu.

Poznámka 2. Nech sú v nejakom extrémnom bode všetky simplexné rozdiely nezáporné D k ³ 0 (k = 1..n+m), t.j. získa sa optimálne riešenie a existuje taký А k - nebázický vektor, pre ktorý D k = 0. Vtedy sa maximum dosiahne aspoň v dvoch bodoch, t.j. existuje alternatívne optimum. Ak túto premennú x k zavedieme do bázy, hodnota účelovej funkcie sa nezmení.

Poznámka 3. Riešenie duálneho problému je v poslednom simplexnom tablo. Posledných m komponentov vektora simplexných rozdielov (v stĺpcoch bilančných premenných) je optimálnym riešením duálnej úlohy. Hodnota objektívnych funkcií priamej a duálnej úlohy v optimálnych bodoch je rovnaká.

Poznámka 4. Pri riešení úlohy minimalizácie sa do základu zavedie vektor s najväčším kladným simplexovým rozdielom. Ďalej sa použije rovnaký algoritmus ako pre problém maximalizácie.

Ak je nastavená podmienka "Je potrebné, aby suroviny III. typu boli úplne spotrebované", potom zodpovedajúca podmienka je rovnosť.

Analytický úvod do simplexovej metódy

Ak teda riešime LLP v kanonickej forme, potom je systém obmedzení obvyklým systémom lineárne rovnice. Pri riešení úloh LP sa získajú sústavy lineárnych rovníc, ktoré majú spravidla nekonečne veľa riešení.

Napríklad daný systém

Tu je počet rovníc 2 a počet neznámych 3, rovníc je menej. Vyjadrite x 1 a x 2 v zmysle x 3:

to spoločné rozhodnutie systémov. ak má premenná x 3 ľubovoľné číselné hodnoty, potom nájdeme konkrétne riešenia systému. Napríklad, X 3 =1 → X 1 =1 → X 2 = 6. Máme (1, 6, 1) - konkrétne riešenie. Nechaj X 3 =2 → X 1 =-3, X 2 = 1, (-3, 1, 2) je ďalšie konkrétne riešenie. Takýchto konkrétnych riešení je nekonečne veľa.

Premenné X 1 a X 2 sa nazývajú základné a premenná X 3 - nie základné, zadarmo.

Sada premenných X 1 a X 2 tvorí základ: B (X 1 , X 2). Ak X 3 = 0, potom sa výsledné partikulárne riešenie (5, 11, 0) nazýva základné riešenie zodpovedajúce zákl. B (X 1 , X 2).

Základným riešením je riešenie zodpovedajúce nulovým hodnotám voľných premenných.
Ostatné premenné možno považovať za základné: ( X 1 , X 3) alebo ( X 2 , X 3).
Ako prejsť z jedného základu B(X 1 , X 2) na iný základ B(X 1 , X 3)?
Na to potrebujete premennú X 3 previesť na základné a X 2 - v nezákladných, t.j. v rovniciach je potrebné X 3 expresné cez X 2 a nahradiť v 1.:

B(X 1 , x 3), je: (-19/5; 0; 11/5).

Ak teraz od základu B(X 1 , X 3) chceme ísť na základ B(X 2 , X 3), potom

Základné riešenie zodpovedajúce základu B (X 2 , X 3): (0;19/4; 7/8).
Z troch nájdených základných riešení riešenie zodpovedajúce zákl B (X 1 , X 3) - negatívny X 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.

Ak má úloha LP riešenie, potom sa dosiahne na množine základných nezáporných riešení systému obmedzení kanonického tvaru.

Preto myšlienka simplexovej metódy spočíva v postupnom prechode z jedného základu na druhý, najlepšie z hľadiska hodnoty účelovej funkcie.

Príklad. Vyriešte problém s LP.

Funkcia F= X 2 - X 1 → min sa musí minimalizovať pre daný systém obmedzení:
-2X 1 + X 2 + X 3 = 2
X 1 + X 2 + X 5 = 5
X 1 - 2X 2 + X 4 = 12
X i ≥ 0, i = 1, 5

Tieto obmedzenia možno považovať za odvodené z nerovností a premenných X 3 , X 5 , X 4 - ako doplnkové.
Obmedzenia zapíšeme výberom základu z premenných B{ X 3 , X 4 , X 5 }:

Tento základ zodpovedá základnému nezápornému riešeniu
X 1 = 0, X 2 = 0, X 3 = 2, X 4 = 2, X 5 = 5 alebo (0, 0, 2, 2, 5).
Teraz sa musíme vyjadriť F prostredníctvom nezákladných premenných, v našom prípade to už bolo urobené: F= X 2 - X 1 .
Skontrolujte, či funkcia dosiahla F jeho minimálna hodnota. Pre toto základné riešenie F= 0 - 0 = 0 - hodnota funkcie je 0. Ale dá sa znížiť, ak X 1 sa zvýši, keďže koeficient vo funkcii at X 1 je záporný. Avšak s nárastom X 1 hodnoty premennej X 4 , X 5 znížiť (pozri druhú a tretiu rovnosť systému obmedzení). Variabilné X 1 nemožno zvýšiť na viac ako 2, inak X 4 bude záporné (v dôsledku rovnosti 2) a nie viac ako 5, inak X 5 - negatívny. Z analýzy rovnosti teda vyplýva, že premenná X 1 možno zvýšiť na 2, v takom prípade sa hodnota funkcie zníži.
Prejdime k novému základu B 2 zavedením premennej X 1 k základu X 4 .
B 2 {X 1 , X 3 , X 5 }.
Vyjadrime tieto základné premenné z hľadiska nezákladných. Aby sme to dosiahli, najprv sa vyjadríme X 1 z druhej rovnice a dosaďte do zvyšku vrátane funkcie.

Základné riešenie zodpovedajúce základu B 3 {X 1 , X 2 , X 3 ), sa vypíše (4, 1, 9, 0, 0) a funkcia nadobudne hodnotu F= -3. Všimnite si, že hodnota F znížil, t.j. zlepšil sa v porovnaní s predchádzajúcim základom.
Pohľad na formu účelovej funkcie , všimnite si, že zlepšiť, t.j. znížiť hodnotu F nie je možné a len X 4 = 0, X 5 = 0 hodnota F= -3. raz X 4 , X 5 sa stávajú pozitívnymi, hodnotnými F sa bude len zvyšovať, keďže koeficienty pri X 4 , X 5 sú pozitívne. Takže funkcia F dosiahol svoje optimum F* = -3. takže, najmenšia hodnota F, rovný -3, sa dosiahne pri X 1 * = 4, X 2 * = 1, X 3 * = 9, X 4 * = 0, X 5 * = 0.

Tento príklad veľmi jasne demonštruje myšlienku metódy: postupným prechodom od základu k základu, pričom vždy venujeme pozornosť hodnotám objektívnej funkcie, ktoré by sa mali zlepšiť, prichádzame k základu, v ktorom je hodnota objektívnej funkcie nemožno zlepšiť, je to optimálne. Všimnite si, že existuje konečný počet základov, takže počet krokov, ktoré urobíme, aby sme sa dostali k požadovanému základu, je konečný.

Tu je ručné (nie appletové) riešenie dvoch problémov pomocou simplexnej metódy (podobne ako appletové riešenie) s podrobnými vysvetleniami, aby ste pochopili algoritmus riešenia problémov simplexnou metódou. Prvá úloha obsahuje znaky nerovnosti len " ≤ " (problém s počiatočným základom), druhá môže obsahovať znaky " ≥ ", " ≤ " alebo " = " (úloha s umelým základom), riešia sa v rôznych spôsoby.

Simplexná metóda, riešenie úlohy s východiskovým základom

1)Simplexná metóda pre problém s počiatočným základom (všetky znaky obmedzujúcich nerovností sú " ≤ ").

Napíšme problém kanonický forme, t.j. obmedzenia nerovností prepíšeme na rovnosti a pridáme súvahy premenné:

Táto sústava je sústava s bázou (báza s 1, s 2, s 3, každá z nich je obsiahnutá len v jednej rovnici sústavy s koeficientom 1), x 1 a x 2 sú voľné premenné. Úlohy, na ktoré sa použije simplexová metóda, musia mať tieto dve vlastnosti: - systém obmedzení musí byť sústavou rovníc so základom; -voľné členy všetkých rovníc v systéme musia byť nezáporné.

Výsledný systém je systém so základom a jeho voľné termíny sú nezáporné, takže môžeme aplikovať simplexná metóda. Zostavte prvú simplexnú tabuľku (iterácia 0) na riešenie problému simplexná metóda, t.j. tabuľku koeficientov účelovej funkcie a sústavu rovníc pre príslušné premenné. Tu "BP" znamená stĺpec základných premenných, "Solution" - stĺpec pravých častí rovníc systému. Riešenie nie je optimálne, pretože v z-línii sú záporné koeficienty.

iterácia simplexnej metódy 0

Na zlepšenie riešenia prejdime k ďalšej iterácii simplexná metóda, dostaneme nasledujúce simplexné tablo. Na to si musíte vybrať povoliť stĺpec, t.j. premenná, ktorá vstúpi do základu pri ďalšej iterácii simplexovej metódy. Vyberá sa najväčším záporným koeficientom v z-riadku (v maximálnom probléme) - v počiatočnej iterácii simplexovej metódy je to stĺpec x 2 (koeficient -6).

Potom si vyberte reťazec povolenia, t.j. premenná, ktorá opustí základ pri ďalšej iterácii simplexovej metódy. Vyberá sa najmenším pomerom stĺpca „Rozhodnutie“ k zodpovedajúcim kladným prvkom rozlišovacieho stĺpca (stĺpec „Pomer“) – v počiatočnej iterácii je to riadok s 3 (koeficient 20).

Permisívny prvok sa nachádza na priesečníku povoľujúceho stĺpca a povoľujúceho riadku, jeho bunka je farebne zvýraznená, rovná sa 1. Preto pri ďalšej iterácii simplexnej metódy premenná x 2 nahradí s 1 v základe. Všimnite si, že vzťah sa nehľadá v reťazci z, vloží sa tam pomlčka „-“. Ak existujú rovnaké minimálne pomery, vyberie sa ktorýkoľvek z nich. Ak sú všetky koeficienty v stĺpci rozlíšenia menšie alebo rovné 0, riešenie problému je nekonečné.

Vyplňte nasledujúcu tabuľku „Iterácia 1“. Získame to z tabuľky "Iterácia 0". Účelom ďalších transformácií je zmeniť stĺpec povolenia x2 na jeden stĺpec (s jedným namiesto prvku enable a nulami namiesto ostatných prvkov).

1) Výpočet riadku x 2 tabuľky "Iterácia 1". Najprv vydelíme všetky členy rozlišovacieho riadku s 3 tabuľky "Iterácia 0" rozlišovacím prvkom (v tomto prípade sa rovná 1) tejto tabuľky, dostaneme riadok x 2 v tabuľke "Iterácia 1" . Pretože rozlišovací prvok je v tomto prípade rovný 1, potom sa riadok s 3 tabuľky "Iterácia 0" bude zhodovať s riadkom x 2 tabuľky "Iterácia 1". Riadok x 2 tabuľky „Iterácia 1“ sme dostali 0 1 0 0 1 20, zvyšné riadky tabuľky „Iterácia 1“ získame z tohto riadka a riadkov tabuľky „Iterácia 0“ takto:

2) Výpočet z-riadku tabuľky "Iterácia 1". Namiesto -6 v prvom riadku (riadok z) v stĺpci x2 tabuľky "Iterácia 0" by mala byť v prvom riadku tabuľky "Iterácia 1" 0. Aby sme to dosiahli, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 6, dostaneme 0 6 0 0 6 120 a tento riadok pridáme k prvému riadku (z - riadok) tabuľky "Iterácia 0" -4 -6 0 0 0 0, dostaneme -4 0 0 0 6 120. V stĺpci x 2 sa objavila nula 0, cieľ bol dosiahnutý. Prvky stĺpca povolenia x 2 sú zvýraznené červenou farbou.

3) Výpočet riadku s 1 tabuľky "Iterácia 1". Namiesto 1 na s 1 riadok tabuľky "Iterácia 0" by mal byť 0 v tabuľke "Iterácia 1". Aby sme to urobili, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 -1, dostaneme 0 -1 0 0 -1 -20 a pridáme tento riadok s 1 - riadku tabuľky "Iterácia 0" 2 1 1 0 0 64 dostaneme riadok 2 0 1 0 -1 44. Požadovaná 0 sa získa v stĺpci x 2.

4) Výpočet riadku s 2 tabuľky "Iterácia 1". Namiesto 3 v s 2 riadku tabuľky "Iterácia 0" by mala byť v tabuľke "Iterácia 1" 0. Aby sme to dosiahli, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 -3, dostaneme 0 -3 0 0 -3 -60 a pridáme tento riadok s 1 - riadku tabuľky "Iterácia 0" 1 3 0 1 0 72, dostaneme riadok 1 0 0 1 -3 12. Požadovaná 0 sa získa v stĺpci x 2. Stĺpec x 2 v tabuľke "Iterácia 1" má stať single, obsahuje jednu 1 a zvyšok 0.

Riadky tabuľky "Iterácia 1" sa získajú podľa nasledujúceho pravidla:

Nový riadok = starý riadok - (faktor povolenia starého riadka)* (nový riadok).

Napríklad pre z-riadok máme:

Starý z-reťazec (-4 -6 0 0 0 0) -(-6)*Nový z-reťazec -(0 -6 0 0 -6 -120) = Nový z-reťazec (-4 0 0 0 6 120) .

Pre nasledujúce tabuľky je prepočet prvkov tabuľky urobený podobným spôsobom, preto ho vynecháme.

iterácia simplexnej metódy 1

Povolený stĺpec x 1 , povolený riadok s 2 , s 2 opustí základ, x 1 vstúpi do základu. Presne rovnakým spôsobom získame zvyšné simplexné tabuľky, kým nezískame tabuľku so všetkými kladnými koeficientmi v z-riadku. To je znak optimálneho stola.

iterácia simplexnej metódy 2

Vyriešenie stĺpca s 3 , vyriešenie riadku s 1 , s 1 opustí základ, s 3 vstúpi do základu.

iterácia simplexnej metódy 3

V z-riadku sú všetky koeficienty nezáporné, preto dostaneme optimálne riešenie x 1 = 24, x 2 = 16, z max = 192.