Zvážte simplexná metóda na riešenie problémov lineárne programovanie(LP). Je založená na prechode od jedného referenčného plánu k druhému, v ktorom sa zvyšuje hodnota účelovej funkcie.
Algoritmus simplexovej metódy je nasledujúci:
- Pôvodný problém prevedieme do kanonickej podoby zavedením ďalších premenných. Pre nerovnosť tvaru ≤ sa ďalšie premenné zavádzajú so znamienkom (+), ale ak majú tvar ≥, potom so znamienkom (-). Do účelovej funkcie sa zavádzajú ďalšie premenné so zodpovedajúcimi znamienkami s koeficientom rovným 0 , pretože účelová funkcia by nemala meniť svoj ekonomický význam.
- Vydávajú sa vektory Pi z koeficientov premenných a stĺpca voľných členov. Táto akcia určuje počet jednotkových vektorov. Platí pravidlo, že jednotkových vektorov by malo byť toľko, koľko je nerovností v systéme obmedzení.
- Potom sa počiatočné údaje zadajú do simplexnej tabuľky. Do základu sa zavedú jednotkové vektory a po ich vylúčení zo základu sa nájde optimálne riešenie. Koeficienty účelovej funkcie sa píšu s opačným znamienkom.
- Kritérium optimality pre problém LP je, že riešenie je optimálne, ak je v f– riadok všetky koeficienty sú kladné. Pravidlo hľadania stĺpca povolení – zobrazené f je struna a spomedzi jej negatívnych prvkov sa vyberá ten najmenší. Vektor Pi jeho obsah sa stáva permisívnym. Pravidlo pre výber rozlišovacieho prvku - zostavia sa pomery kladných prvkov rozlišovacieho stĺpca k prvkom vektora P 0 a číslo, ktoré dáva najmenší pomer, sa stáva rozlišovacím prvkom, vzhľadom na ktorý sa bude simplexná tabuľka prepočítavať. Reťazec obsahujúci tento prvok sa nazýva aktivačný reťazec. Ak v stĺpci rozlíšenia nie sú žiadne kladné prvky, problém nemá riešenie. Po určení rozlišovacieho prvku pristúpia k prepočítaniu novej simplexnej tabuľky.
- Pravidlá pre vyplnenie novej simplexnej tabuľky. Namiesto rozlišovacieho prvku sa jeden položí a ostatné prvky sa považujú za rovnaké 0 . Rozlišovací vektor sa pridá k báze, z ktorej sa vylúči zodpovedajúci nulový vektor a zostávajúce bázové vektory sa zapíšu nezmenené. Prvky permisívnej čiary sú rozdelené permisívnym prvkom a zostávajúce prvky sú prepočítané podľa pravidla obdĺžnikov.
- Toto sa robí až do f– všetky prvky struny sa nestanú pozitívnymi.
Zvážte riešenie problému pomocou vyššie uvedeného algoritmu.
Vzhľadom na to:
Zavedenie problému do kanonická forma:
Skladáme vektory:
Vyplňte simplexnú tabuľku:
:
Prepočítajte prvý prvok vektora P 0, pre ktorý urobíme obdĺžnik s číslami: a dostaneme: 
.
Podobné výpočty vykonávame pre všetky ostatné prvky simplexnej tabuľky:
V prijatom pláne f– reťazec obsahuje jeden záporný prvok – (-5/3), vektory P1. Vo svojom stĺpci obsahuje jediný kladný prvok, ktorý bude rozlišovacím prvkom. Prepočítajme tabuľku vzhľadom na tento prvok:
Absencia negatívnych prvkov v f- reťazec znamená nájdený optimálny plán:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Lineárne programovanie, M: Nauka, 1998,
- Wentzel E.S. Operačný výskum, M: Sovietsky rozhlas, 2001,
- Kuznecov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematické programovanie, M: Vyššia škola, 1986
Vlastné riešenie lineárneho programovania
Akékoľvek zadania v tejto disciplíne si môžete objednať na našej stránke. Môžete pripojiť súbory a určiť termíny na
Problémy lineárneho programovania. Je to v sekvenčnej konštrukcii, ktorá charakterizuje uvažovaný proces. Riešenie je rozdelené do troch hlavných etáp: výber premenných, konštrukcia systému obmedzení a hľadanie objektívnej funkcie.
Na základe tohto rozdelenia možno preformulovať stav problému nasledujúcim spôsobom: extrém účelovej funkcie Z(X) = f(x1, x2, … ,xn) → max (min) a príslušné premenné, ak je známe, že spĺňajú systém obmedzení: Φ_i (x1, x2, … ,xn) = 0 pre i = 1, 2, …, k;Φ_i (x1, x2, …,xn)) 0 pre i = k+1, k+2, …, m.
Systém obmedzení je potrebné zredukovať na kanonickú formu, t.j. do systému lineárne rovnice, kde počet premenných je väčší ako počet rovníc (m > k). V tomto systéme určite budú existovať premenné, ktoré sa dajú vyjadriť inými premennými, a ak to tak nie je, potom ich možno zaviesť umelo. V tomto prípade sa prvé nazývajú základ alebo umelý základ a posledné sú zadarmo.
Je pohodlnejšie zvážiť simplexnú metódu konkrétny príklad. Nech je to dané lineárna funkcia f(x) = 6x1 + 5x2 + 9x3 maximálna hodnota funkcie f(x).
Riešenie V prvej fáze zadajte úplne ľubovoľným spôsobom počiatočné (referenčné) riešenie sústavy rovníc, ktoré musí spĺňať daný systém obmedzení. AT tento prípad je potrebné umelé zavedenie, t.j. základné premenné x4, x5 a x6 takto: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.
Ako vidíte, nerovnosti sa pretransformovali na rovnosť vďaka pridaným premenným x4, x5, x6, čo sú nezáporné hodnoty. Takto ste systém priviedli do kanonickej podoby. Premenná x4 vstupuje do prvej rovnice s koeficientom 1 a do dvoch - s koeficientom 0 to isté platí pre premenné x5, x6 a zodpovedajúce rovnice, čo zodpovedá definícii základu.
Pripravili ste systém a našli iniciály referenčný roztok– X0 = (0, 0, 0, 25, 20, 18). Teraz prezentujte koeficienty premenných a konštantné členy rovníc (čísla napravo od znamienka „=“) vo forme tabuľky na optimalizáciu ďalších výpočtov (pozri obrázok).
Podstatou simplexovej metódy je priviesť túto tabuľku do formy, v ktorej budú všetky číslice v reťazci L nezáporné hodnoty. Ak sa ukáže, že to nie je možné, potom systém žiadne nemá optimálne riešenie. Ak chcete začať, vyberte čo najviac minimálny prvok tento riadok je -9. Číslo je v treťom stĺpci. Preveďte zodpovedajúcu premennú x3 na základnú premennú. Ak to chcete urobiť, vydeľte reťazec 3, aby ste dostali 1 v bunke.
Teraz potrebujete bunky a otočte na 0. Ak to chcete urobiť, odpočítajte od zodpovedajúcich čísel tretieho radu o 3. Od prvkov druhého radu - prvky tretieho, vynásobte 2. A nakoniec od prvky čiary L - vynásobené (-9). Získali ste druhé kľúčové riešenie: f(x) = L = 54 pre x1 = (0, 0, 6, 7, 8, 0).
. Algoritmus simplexnej metódy
Príklad 5.1. Vyriešte nasledujúci problém lineárneho programovania pomocou simplexnej metódy:
rozhodnutie:
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
Odhadované vzťahy |
||||
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, keďž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 týchto stĺpcov vyberte ten, ktorý obsahuje najmenší prvok v riadku účelovej funkcie. Ona bude riešiť. reproduktor" 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, je akceptovaný 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 zapíšeme 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 premien vzniká nový simplexný stôl(tabuľka 5.5).
II iterácia:
1. fáza: zostavenie simplexnej tabuľky.
Tabuľka 5.5
Simplexný stôlII iterácií
Odhadovaný vzťahy |
||||
| ||||
|
|
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.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 odhalená.
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 stĺpca rozlíšenia.
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í
Odhadovaný vzťahy |
||||
3/1 = 3 – min |
||||
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ácia
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í
Odhadovaný vzťahy |
||||
| ||||
|
|
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 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.
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 stĺpca rozlíšenia.
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í
Odhadovaný vzťahy |
||||
5/5 = 1 – min |
||||
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ácia
1. fáza: 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í
Odhadovaný vzťahy |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
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 negatívne prvky (voľné číslo tohto riadku 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 (voľné číslo tohto riadku sa pri zvažovaní tejto vlastnosti neberie do úvahy).
odpoveď: optimálna hodnota objektívna funkcia 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á:
rozhodnutie:
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.
Uvažuje sa o príklade riešenia úlohy simplexovou metódou, ako aj o príklade riešenia duálny problém.
Úloha
Na realizáciu troch skupín tovarov má obchodný podnik tri druhy obmedzených vecných a peňažných zdrojov vo výške b 1 = 240, b 2 = 200, b 3 = 160 jednotiek. Zároveň na predaj 1 skupiny tovaru za 1 000 rubľov. obrat, zdroj prvého druhu sa spotrebuje vo výške a 11 = 2 jednotky, zdroj druhého typu vo výške 21 = 4 jednotky, zdroj tretieho typu v množstve 31 = 4 Jednotky. Na predaj 2 a 3 skupín tovaru za 1 000 rubľov. obrat sa minie, resp. zdroj prvého typu vo výške a 12 = 3, a 13 = 6 jednotiek, zdroj druhého typu vo výške a 22 = 2, a 23 = 4 jednotky, zdroj tretieho typu v množstve a 32 = 6, a 33 = 8 jednotiek . Zisk z predaja troch skupín tovaru za 1 000 rubľov. obrat je c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4 (tisíc rubľov). Stanovte plánovaný objem a štruktúru obratu tak, aby zisk obchodného podniku bola maximálna.
K priamemu problému plánovania obehu komodít, riešiteľná simplexná metóda, komponovať duálny problém lineárne programovanie.
Inštalácia konjugované páry premenných priame a dvojité problémy.
Podľa konjugovaných párov premenných z riešenia priamej úlohy získajte duálne riešenie problému, v ktorom odhad zdrojov vynaložené na predaj tovaru.
Riešenie simplexnej úlohy metódou
Nech x 1, x 2, x 3 - počet predaných tovarov v tisícoch rubľov, 1, 2, 3 skupiny, resp. Potom matematický modelúloha vyzerá takto:F = 4 x 1 + 5 x 2 + 4 x 3 ->max
0)))(~)" title="(!LANG:delim(lbrace)(matica(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
Simplex riešime metódou.
Zavádzame ďalšie premenné x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, aby sme previedli nerovnosti na rovnosti.
Ako základ berieme x 4 \u003d 240; x5 = 200; x6 = 160.
Údaje sa zadávajú simplexný stôl
Simplexný stôl číslo 1
0 240 + 0 200 + 0 160 = 0
Skóre vypočítame podľa vzorca:
Δ 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
Δ 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
Δ 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
Δ 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
Δ 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0
Keďže existujú negatívne odhady, plán nie je optimálny. Najnižšie hodnotenie:
Do základu zavedieme premennú x 2.
Definujeme premennú opúšťajúcu základ. Aby sme to dosiahli, nájdeme najmenší nezáporný pomer pre stĺpec x 2 .
= 26.667
Najmenšia nezáporná hodnota: Q 3 = 26,667. Premennú x 6 odvodíme zo základu
Rozdeľte riadok 3 na 6.
Od 1. riadku odpočítajte 3. riadok vynásobený 3
Od 2. riadku odpočítajte 3. riadok vynásobený 2
Vypočítame:
Dostaneme nový stôl:
Simplexný stôl číslo 2
Cieľová funkcia:
0 160 + 0 440/3 + 5 80/3 = 400/3
Skóre vypočítame podľa vzorca:
Δ 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
Δ 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 5/6
Keďže existuje negatívny odhad Δ 1 = - 2/3, plán nie je optimálny.
Do základu zavedieme premennú x 1.
Definujeme premennú opúšťajúcu základ. Aby sme to dosiahli, nájdeme najmenší nezáporný pomer pre stĺpec x 1 .
Najmenší nezáporný: Q 3 \u003d 40. Premennú x 2 odvodíme zo zákl.
3. riadok rozdelíme na 2/3.
Od 2. riadku odpočítajte 3. riadok vynásobený 8/3
Vypočítame:
Dostávame novú tabuľku:
Simplexný stôl číslo 3
Cieľová funkcia:
0 160 + 0 40 + 4 40 = 160
Skóre vypočítame podľa vzorca:
Δ 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
Δ 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
Δ 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
Δ 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1
Keďže neexistujú žiadne negatívne odhady, plán je optimálny.
Riešenie problému:
Odpoveď
x 1 = 40; x2 = 0; x 3 \u003d 0; x 4 = 160; x5 = 40; x6 = 0; Fmax = 160To znamená, že je potrebné predať tovar prvého typu vo výške 40 000 rubľov. Tovar 2. a 3. druhu nie je potrebné predávať. V tomto prípade bude maximálny zisk F max = 160 tisíc rubľov.
Riešenie duálneho problému
Dvojitý problém vyzerá takto:
Z = 240 r 1 + 200 r 2 + 160 r 3 ->min
Title="(!LANG:delim(lbrace)(matrix(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)))(~)">!}
Zavádzame ďalšie premenné y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, aby sme previedli nerovnosti na rovnosti.
Konjugované páry premenných priamych a duálnych problémov majú tvar:
Z poslednej simplexnej tabuľky č. 3 priamej úlohy nájdeme riešenie duálnej úlohy:
Zmin = Fmax = 160;
y 1 \u003d Δ 4 \u003d 0; y 2 \u003d Δ 5 \u003d 0; y 3 \u003d Δ 6 \u003d 1; y 4 \u003d Δ 1 \u003d 0; y 5 \u003d Δ 2 \u003d 1; y 6 \u003d Δ 3 \u003d 4;
| - | x 1 | + | x2 | - | S1 | = | 1 | ||||||||||
| x 1 | +3 | x2 | + | S2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x2 | + | S3 | = | 4 |
| - | x 1 | + | x2 | - | S1 | + | R1 | = | 1 | |||||||||||
| x 1 | +3 | x2 | + | S2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x2 | + | S3 | = | 4 |
| x 1 = 0 x 2 = 0 S1 = 0 S2 = 15 S3 = 4 R1 = 1 |
=>W=1 |
| x 1 | x2 | S1 | S2 | S3 | R1 | St. členom | Θ |
| -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 | + | x2 | - | S1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S1 | + | S2 | = | 12 | |||||||||
| - | x 1 | + | S1 | + | S3 | = | 3 |
| x 1 | x2 | S1 | S2 | S3 | St. členom | Θ |
| -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 |
| S1 = 0 S2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Zlaté čísla Ako predať krásne telefónne číslo
Ťažba kryptomeny: čo to je jednoduchými slovami
Najlepší operačný systém pre laptop: Kompletná recenzia
Programy na sťahovanie hudby od spolužiakov Stiahnite si smutnú pesničku od spolužiakov zo sociálnej siete
Mobilná verzia prehliadača Yandex