Simplexná metóda na riešenie úloh lineárneho programovania. Jordan-Gaussova transformácia a simplexná metóda v Exceli

Ak problém obsahuje obmedzenia so znamienkom ≥, potom ich možno zredukovať na tvar ∑a ji b j vynásobením oboch strán nerovnosti -1. Zavedieme m prídavných premenných x n + j ≥0 (j = 1, m) a transformujeme obmedzenia do tvaru rovnosti

(2)

Predpokladajme, že všetky počiatočné premenné úlohy x 1, x 2, ..., x n sú nebázické. Potom budú dodatočné premenné základné a konkrétne riešenie systému obmedzení bude mať formu

x 1 = x 2 = ... = x n = 0, x n + j = b j, j = 1, m. (3)

Keďže v tomto prípade je hodnota cieľovej funkcie F 0 = 0, môžeme reprezentovať F (x) nasledujúcim spôsobom:

F (x) = ∑c i x i + F 0 = 0 (4)

Počiatočná simplexná tabuľka (simplexná tabuľka 1) je zostavená na základe rovníc (2) a (4). Ak pred dodatočnými premennými x n + j je znamienko "+", ako v (2), potom sa všetky koeficienty pred premennými x i a voľným členom b j zapíšu do simplexnej tabuľky nezmenené. Keď je cieľová funkcia maximalizovaná, koeficienty cieľovej funkcie sa zadávajú do spodného riadku simplexnej tabuľky s opačnými znamienkami. Voľné výrazy v simplexnej tabuľke určujú riešenie problému.

Algoritmus na vyriešenie problému je nasledujúci:

1. krok. Prvky stĺpca voľného člena sa posúvajú. Ak sú všetky kladné, potom sa našlo uskutočniteľné základné riešenie a treba prejsť na krok 5 algoritmu, ktorý zodpovedá nájdeniu optimálneho riešenia. Ak má počiatočná simplexová tabuľka záporné voľné podmienky, riešenie nie je platné a mali by ste prejsť na krok 2.

2. krok. Na nájdenie realizovateľného riešenia sa vykonáva, pričom je potrebné rozhodnúť, ktorú z nezákladných premenných zaradiť do základu a ktorú premennú zo základu odvodiť.

Stôl 1.

x n

základné premenné	Voľní členovia v obmedzeniach	Nezákladné premenné
		x 1	x 2	...	x l	...
x n + 1	b 1	11	12	...	a 1l	...	a 1n
x n + 2	b 2	21	22	...	a 2l	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + r	b2	a r1	a r2	...	a rl	...	a rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n + m	b m	m1	m2	...	ml	...	a mn
F (x) max	F 0	-c 1	-c 2	...	-c 1	...	-c n

Ak to chcete urobiť, vyberte ľubovoľný zo záporných prvkov stĺpca voľného člena (nech je to b 2 vedúce alebo rozlišovacie. Ak v rade so záporným voľným členom nie sú žiadne záporné prvky, potom je systém obmedzení nekompatibilný a problém nemá riešenie.

Zároveň sa z BP vylúči premenná, ktorá ako prvá zmení znamienko so zvýšením zvoleného NP x l. Bude to x n + r, ktorého index r je určený z podmienky

tie. premenná zodpovedajúca najmenšiemu pomeru voľného člena k členovi zvoleného otočného stĺpca. Tento vzťah sa nazýva simplexný vzťah. Mali by sa brať do úvahy iba pozitívne simplexné vzťahy.

Zavolá sa reťazec zodpovedajúci premennej x n + r vedúci, alebo povoľujúci. Prvok simplexnej tabuľky a rl, ktorý stojí na priesečníku vodiaceho riadku a vodiaceho stĺpca, sa nazýva vodiaci alebo rozlišovací prvok. Nájdenie prvku pivot končí prácou s každou následnou simplexnou tabuľkou.

3. krok. Vypočíta sa nová simplexová tabuľka, ktorej prvky sa prepočítajú z prvkov simplexovej tabuľky predchádzajúceho kroku a označia sa prvočíslom, t.j. b "j, a" ji, c "i, F" 0. Prvky sa prepočítavajú podľa nasledujúcich vzorcov:

Najprv nová simplexná tabuľka vyplní riadok a stĺpec, ktoré viedli v predchádzajúcej simplexnej tabuľke. Výraz (5) znamená, že prvok a "rl na mieste vedúceho prvku sa rovná recipročnej hodnote prvku predchádzajúcej simplexovej tabuľky. Prvky riadku a ri sú delené vodiacim prvkom a prvky stĺpec a jl je tiež delený vodiacim prvkom, ale s opačným znamienkom Prvky b "r a c" l sa vypočítajú rovnakým spôsobom.

Ostatné vzorce sa dajú ľahko napísať.

Obdĺžnik je zostrojený podľa starej simplexovej tabuľky tak, že jednu z jeho uhlopriečok tvoria prepočítaný (a ji) a vodiaci (a rl) prvok (obr. 1). Druhá uhlopriečka je jednoznačne určená. Ak chcete nájsť nový prvok a "ji, súčin prvkov opačnej uhlopriečky delený vodiacim prvkom sa odpočíta od prvku a ji (ako je označené znamienkom" - "v blízkosti bunky). Prvky b" j, (j ≠ r) a c"i, (i ≠ l).

4. krok. Analýza novej simplexovej tabuľky začína 1. krokom algoritmu. Akcia pokračuje dovtedy, kým sa nenájde uskutočniteľné základné riešenie, t.j. všetci členovia stĺpca voľných členov musia byť kladní.

5. krok. Veríme, že sa našlo uskutočniteľné základné riešenie. Pozeráme sa na koeficienty priamky cieľovej funkcie F (x). Kritériom optimálnosti simplexnej tabuľky je nezápornosť koeficientov pre nebázické premenné v F-riadku.

Ryža. 1. Pravidlo obdĺžnika

Ak sú medzi koeficientmi radu F záporné (s výnimkou priesečníka), musíte prejsť na iné základné riešenie. Pri maximalizácii cieľovej funkcie je základom jedna z nebázických premenných (napríklad x l), ktorej stĺpec zodpovedá maximálnej absolútnej hodnote záporného koeficientu c l v spodná čiara simplexné stoly. To vám umožní vybrať premennú, ktorej zvýšenie vedie k zlepšeniu cieľovej funkcie. Stĺpec zodpovedajúci premennej x l sa nazýva vedúci stĺpec. Zároveň je zo základu vylúčená premenná x n + r, ktorej index r je určený minimálnym simplexným vzťahom:

Riadok zodpovedajúci x n + r sa nazýva vodiaci prvok a prvok simplexnej tabuľky a rl, ktorý stojí na priesečníku vodiaceho riadku a vodiaceho stĺpca, sa nazýva vedúci prvok.

6. krok. podľa pravidiel uvedených v kroku 3. Postup pokračuje, kým sa nenájde optimálne riešenie alebo sa dospelo k záveru, že neexistuje.

Ak sú počas optimalizácie riešenia vo vodiacom stĺpci všetky prvky nekladné, potom nie je možné vybrať vodiaci riadok. V tomto prípade funkcia v obore realizovateľných riešení úlohy nie je ohraničená vyššie a F max -> & ∞.

Ak sa v ďalšom kroku pri hľadaní extrému jedna zo základných premenných rovná nule, potom sa zodpovedajúce základné riešenie nazýva degenerované. V tomto prípade dochádza k tzv. loopingu, ktorý sa vyznačuje tým, že s určitou frekvenciou sa začne opakovať rovnaká kombinácia BP (hodnota funkcie F je zachovaná) a nie je možné prejsť na nové prípustné základné riešenie. Looping je jednou z hlavných nevýhod simplexovej metódy, ale je pomerne zriedkavý. V praxi v takýchto prípadoch zvyčajne odmietajú zadať do základu premennú, ktorej stĺpec zodpovedá maximálnej absolútnej hodnote záporného koeficientu v cieľovej funkcii a vytvoriť náhodný výber nové základné riešenie.

Príklad 1. Vyriešte úlohu

max (F (x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simplexová metóda a poskytnúť geometrickú interpretáciu procesu riešenia.

Grafická interpretácia riešenia úlohy je na obr. 2. Maximálna hodnota cieľovej funkcie sa dosiahne v hornej časti ODZP so súradnicami. Vyriešme problém pomocou simplexných tabuliek. Druhé obmedzenie vynásobíme (-1) a zavedieme ďalšie premenné, aby sa nerovnosti dostali do formy rovnosti, potom

Počiatočné premenné x 1 a x 2 sú brané ako nezákladné a dodatočné x 3, x 4 a x 5 sú považované za základné a zostavujeme simplexnú tabuľku (simplexnú tabuľku 2). Riešenie zodpovedajúce simplexnej tabuľke. 2 neplatí; otočný prvok je načrtnutý a vybraný podľa kroku 2 predchádzajúceho algoritmu. Ďalšia simplexná tabuľka. 3 určuje prípustné základné riešenie, ktoré zodpovedá vrcholu ODZP na obr. 2 Prvok pivot je načrtnutý a vybraný v súlade s 5. krokom algoritmu na riešenie problému. Tab. 4 zodpovedá optimálnemu riešeniu úlohy, preto: x 1 = x 5 = 0; x2 = 4; x 3 = 3; x4 = 8; Fmax = 20.

Ryža. 2. Grafické riešenieúlohy

Gauss-Jordanova metóda je určená na riešenie lineárnych systémov algebraické rovnice(POMALY). Ide o modifikáciu Gaussovej metódy. Ak sa Gaussova metóda vykonáva v dvoch fázach (dopredu a dozadu), potom metóda Gauss-Jordan umožňuje riešenie systému v jednej fáze. Podrobnosti a priama schéma aplikácie Gauss-Jordanovej metódy sú opísané v príkladoch.

Vo všetkých príkladoch $ A $ znamená systémovú maticu, $ \ widetilde (A) $ znamená rozšírenú systémovú maticu. Môžete si prečítať o matricovej forme notácie SLAE.

Príklad #1

Vyriešte SLAE $ \ vľavo \ (\ začiatok (zarovnané) & 4x_1-7x_2 + 8x_3 = -23; \\ & 2x_1-4x_2 + 5x_3 = -13; \\ & -3x_1 + 11x_2 + x_3 = 16. \ Koniec (zarovnané ) \ vpravo $ pomocou Gaussovej-Jordanovej metódy.

Prejdime od poslednej matice, ktorú sme dostali, k systému:

$$ \ vľavo \ (\ začiatok (zarovnané) & 0 \ cdot x_1 + 1 \ cdot x_2 + 0 \ cdot x_3 = 1; \\ & 1 \ cdot x_1 + 0 \ cdot x_2 + 0 \ cdot x_3 = -2; \\ & 0 \ cdot x_1 + 0 \ cdot x_2 + 1 \ cdot x_3 = -1. \ Koniec (zarovnaný) \ vpravo. $$

Pre zjednodušenie výsledného systému máme:

$$ \ vľavo \ (\ začiatok (zarovnané) & x_2 = 1; \\ & x_1 = -2; \\ & x_3 = -1. \ koniec (zarovnané) \ vpravo. $$

Kompletné riešenie vyzerá bez vysvetlenia takto:

Aj keď je tento spôsob výberu rozlišovacích prvkov celkom prijateľný, je vhodnejšie zvoliť ako rozlišovacie prvky diagonálne prvky matice systému. Na túto metódu sa pozrieme nižšie.

Voľba rozlišovacích prvkov na hlavnej diagonále matice systému.

Keďže toto riešenie je úplne podobné predchádzajúcemu (s výnimkou voľby prvkov rozlíšenia), podrobné vysvetlenia preskočíme. Princíp výberu permisívnych prvkov je jednoduchý: v prvom stĺpci vyberieme prvok prvého riadku, v druhom stĺpci vyberieme prvok druhého riadku, v treťom stĺpci vyberieme prvok tretieho riadku atď. na.

Prvý krok

V prvom stĺpci vyberieme prvok prvého riadku, t.j. ako rozlišovací prvok máme 4. Rozumiem, že je vhodnejší výber čísla 2, keďže toto číslo je stále menšie ako 4. Aby sa číslo 2 v prvom stĺpci posunulo na prvé miesto, vymeníme prvý a druhý riadok:

$$ \ vľavo (\ začiatok (pole) (ccc | c) 4 & -7 & 8 & -23 \\ 2 & -4 & 5 & -13 \\ -3 & 11 & 1 & 16 \ koniec (pole) \ vpravo) \ šípka vpravo \ vľavo (\ začiatok (pole) (ccc | c) 2 & -4 & 5 & -13 \\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \ koniec (pole ) \ vpravo) $$

Rozlišovací prvok je teda reprezentovaný číslom 2. Rovnakým spôsobom ako predtým vydeľte prvý riadok 2 a potom vynulujte prvky prvého stĺpca:

$$ \ vľavo (\ začiatok (pole) (ccc | c) 2 & -4 & 5 & -13 \\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I: 2 \\\ fantóm (0) \\ \ fantóm (0) \ koniec (pole) \ šípka doprava \ vľavo (\ začiatok (pole) (ccc | c) 1 & - 2 & 5/2 & -13/2 \\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ II-4 \ cbodka I \\ III + 3 \ cbodka I \ koniec (pole) \ šípka doprava \ vľavo (\ začiatok (pole) (ccc | c) 1 & -2 & 5/2 & -13 /2 \ \ 0 & 1 & -2 & 3 \\ 0 & 5 & 17/2 & -7/2 \ koniec (pole) \ vpravo). $$

Druhý krok

Druhým krokom je vynulovanie prvkov druhého stĺpca. Ako rozlišovací prvok vyberieme prvok druhého radu, t.j. 1. Povoľujúci prvok už je sa rovná jednej, takže nebudeme prehadzovať žiadne linky. Mimochodom, ak by sme si chceli vymeniť riadky, nedotkli by sme sa prvého riadku, keďže už bol použitý v prvom kroku. Ale druhý a tretí riadok sa dá jednoducho prehodiť. Opakujem však, že v tejto situácii nie je potrebné prehadzovať riadky, pretože rozlišovací prvok je už optimálny - rovná sa jednej.

$$ \ vľavo (\ začiatok (pole) (ccc | c) 1 & -2 & 5/2 & -13/2 \\ 0 & 1 & -2 & 3 \\ 0 & 5 & 17/2 & -7 / 2 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I + 2 \ cdot II \\ \ fantóm (0) \\ III-5 \ cdot II \ koniec (pole) \ šípka vpravo \ vľavo (\ begin (pole) (ccc | c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 37/2 & -37/2 \ end (pole ) \vpravo). $$

Druhý krok je za nami. Prejdime k tretiemu kroku.

Tretí krok

Tretím krokom je vynulovanie prvkov tretieho stĺpca. Ako rozlišovací prvok vyberieme prvok tretieho radu, t.j. 37/2. Prvky tretieho riadku vydelíme 37/2 (tak, aby sa rozlišovací prvok rovnal 1) a potom vynulujeme zodpovedajúce prvky tretieho stĺpca:

$$ \ vľavo (\ begin (pole) (ccc | c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 37/2 & -37 / 2 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ \ fantóm (0) \\ III: \ frac (37) (2) \ koniec (pole) \ šípka doprava \ vľavo (\ začiatok (pole) (ccc | c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 1 & -1 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I + 2 \ cdot III \\ II + 3/2 \ cdot III \\ \ fantóm (0) \ koniec (pole) \ šípka vpravo \ vľavo (\ začiatok (pole) ( ccc | c) 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -1 \ koniec (pole) \ vpravo). $$

Prijme sa odpoveď: $ x_1 = -2 $, $ x_2 = 1 $, $ x_3 = -1 $. Kompletné riešenie vyzerá bez vysvetlenia takto:

Všetky ostatné príklady na tejto stránke budú riešené presne druhým spôsobom: ako rozlišovacie zvolíme diagonálne prvky matice systému.

Odpoveď: $ x_1 = -2 $, $ x_2 = 1 $, $ x_3 = -1 $.

Príklad č.2

Vyriešte SLAE $ \ vľavo \ (\ začiatok (zarovnané) & 3x_1 + x_2 + 2x_3 + 5x_4 = -6; \\ & 3x_1 + x_2 + 2x_4 = -10; \\ & 6x_1 + 4x_2 + 11x_3 + 11x_4 = -27; \\ & -3x_1-2x_2-2x_3-10x_4 = 1. \ Koniec (zarovnaný) \ vpravo $ Gaussovou-Jordanovou metódou.

Napíšme rozšírenú maticu daného systému: $ \ widetilde (A) = \ left (\ begin (pole) (cccc | c) 3 & 1 & 2 & 5 & -6 \\ 3 & 1 & 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \ koniec (pole) \ vpravo) $.

Ako rozlišovacie prvky zvolíme diagonálne prvky matice systému: v prvom kroku vezmeme prvok prvého riadku, v druhom kroku prvok druhého radu atď.

Prvý krok

Musíme vynulovať zodpovedajúce prvky v prvom stĺpci. Zoberme si prvok prvého riadku ako rozlišovací prvok, t.j. 3. Podľa toho bude potrebné prvý riadok vydeliť 3, aby sa rozlišovací prvok rovnal jednej. A potom vynulujte všetky prvky prvého stĺpca, okrem toho, ktorý má vyriešiť:

$$ \ vľavo (\ začiatok (pole) (cccc | c) 3 & 1 & 2 & 5 & -6 \\ 3 & 1 & 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \ \ -3 & -2 & -2 & -10 & 1 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I: 3 \\ \ fantóm (0) \\\ fantóm (0) \\\ fantóm (0) \ koniec (pole) \ šípka doprava \ doľava (\ začiatok (pole) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 3 & 1 & 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ II-3 \ cdot I \\ III-6 \ cdot I \\ IV + 3 \ cdot I \ koniec (pole) \ šípka doprava \\ \ šípka doprava \ doľava (\ begin (pole) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 0 & -2 & -3 & -4 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & -1 & 0 & - 5 & ​​​​-5 \ koniec (pole) \ vpravo). $$

Druhý krok

Pokračujeme k vynulovaniu zodpovedajúcich prvkov druhého stĺpca. Dohodli sme sa, že prvok druhého riadku vezmeme ako prvok rozlíšenia, ale odvtedy to nemôžeme urobiť požadovaný prvok je nula. Záver: vymeníme riadky. Prvý riadok sa nedá dotknúť, pretože už bol použitý v prvom kroku. Výber nie je bohatý: buď vymeníme druhý a tretí riadok, alebo prehodíme štvrtý a druhý. Keďže štvrtý riadok obsahuje (-1), nech sa „výmeny“ zúčastní štvrtý riadok. Takže vymeňme druhý a štvrtý riadok:

$$ \ vľavo (\ begin (pole) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 0 & -2 & -3 & -4 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & -1 & 0 & -5 & -5 \ koniec (pole) \ doprava) \ šípka doprava \ doľava (\ začiatok (pole) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & -1 & 0 & -5 & -5 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & 0 & -2 & -3 & -4 \ koniec (pole) \ vpravo) $$

Teraz je všetko normálne: rozlišovací prvok sa rovná (-1). Stáva sa mimochodom, že zmena miesta čiar je nemožná, ale o tom budeme diskutovať v nasledujúcom príklade №3. Zatiaľ vydeľte druhý riadok (-1) a potom vynulujte prvky v druhom stĺpci. Upozorňujeme, že v druhom stĺpci je prvok umiestnený vo štvrtom riadku už rovný nule, takže sa nedotkneme štvrtého riadku.

$$ \ vľavo (\ begin (pole) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & -1 & 0 & -5 & -5 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & 0 & -2 & -3 & -4 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ II: (- 1) \\\ fantóm (0) \\\ fantóm (0) \ koniec (pole) \ šípka doprava \ vľavo (\ začiatok (pole) (cccc | c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 2 & 7 & 1 & -15 \\ 0 & 0 & -2 & -3 & -4 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I-1/3 \ cdot II \\ \ fantóm (0) \\ III-2 \ cdot II \\\ fantóm (0) \ koniec (pole) \ šípka vpravo \\ \ šípka vpravo \ vľavo (\ začiatok ( pole) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 7 & -9 & -25 \\ 0 & 0 & -2 & -3 & -4 \ koniec (pole) \ vpravo). $$

Tretí krok

Začnime spracovávať tretí stĺpec. Dohodli sme sa, že ako rozlišovací prvok použijeme diagonálne prvky matice systému. Pre tretí krok to znamená výber položky umiestnenej v treťom riadku. Ak však ako riešiteľ vezmeme len prvok 7, potom bude musieť byť celý tretí riadok vydelený číslom 7. Zdá sa mi, že je jednoduchšie deliť číslom (-2). Preto si vymeníme pozície tretieho a štvrtého riadku a potom sa rozlišovacím prvkom stane (-2):

$$ \ vľavo (\ begin (pole) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 7 & -9 & -25 \\ 0 & 0 & -2 & -3 & -4 \ koniec (pole) \ doprava) \ šípka doprava \ doľava (\ začiatok (pole) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & -2 & -3 & -4 \\ 0 & 0 & 7 & -9 & -25 \ koniec (pole) \ vpravo) $$

Permisívny prvok - (-2). Vydeľte tretí riadok (-2) a vynulujte zodpovedajúce prvky tretieho stĺpca:

$$ \ vľavo (\ begin (pole) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & -2 & - 3 & -4 \\ 0 & 0 & 7 & -9 & -25 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ \ fantóm (0) \\ III :( -2) \\\ fantóm (0) \ koniec (pole) \ šípka doprava \ doľava (\ začiatok (pole) (cccc | c) 1 & 0 & 2/3 & 0 & -11/3 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 7 & -9 & -25 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I-2 / 3 \ cdot III \\ \ phantom (0) \\ \ phantom (0) \\ IV-7 \ cdot III \ end (pole) \ rightarrow \\ \ rightarrow \ left (\ begin (pole) (cccc | c ) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & - 39 \ koniec (pole) \ vpravo). $$

Štvrtý krok

Prejdime k vynulovaniu štvrtého stĺpca. Rozlišovací prvok sa nachádza v štvrtom riadku a rovná sa číslu $ - \ frac (39) (2) $.

$$ \ vľavo (\ begin (pole) (cccc | c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & -39 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ \ fantóm (0) \\ \ fantóm (0) \\ IV: \ vľavo (- \ frac (39) (2) \ vpravo) \ koniec (pole) \ šípka vpravo \ vľavo (\ začiatok (pole) (cccc | c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5 \\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & 1 & 2 \ koniec (pole) \ vpravo) \ začiatok (pole) (l ) I + IV \\ II-5 \ cdot IV \\ III-3/2 \ cdot IV \\ \ fantóm (0) \ koniec (pole) \ šípka doprava \\ \ šípka doprava \ doľava (\ začiatok (pole) (cccc | c) 1 & 0 & 0 & 0 & -3 \\ 0 & 1 & 0 & 0 & -5 \\ 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 2 \ koniec (pole) \ vpravo). $$

Rozhodnutie sa skončilo. Odpoveď je: $ x_1 = -3 $, $ x_2 = -5 $, $ x_3 = -1 $, $ x_4 = 2 $. Kompletné riešenie bez vysvetlenia:

Odpoveď: $ x_1 = -3 $, $ x_2 = -5 $, $ x_3 = -1 $, $ x_4 = 2 $.

Príklad č.3

Vyriešte SLAE $ \ vľavo \ (\ začiatok (zarovnané) & x_1-2x_2 + 3x_3 + 4x_5 = -5; \\ & 2x_1 + x_2 + 5x_3 + 2x_4 + 9x_5 = -3; \\ & 3x_1 + 4x_2 + 4x_43 + + 14x_5 = -1; \\ & 2x_1-4x_2 + 6x_3 + 11x_5 = 2; \\ & -2x_1 + 14x_2-8x_3 + 4x_4-7x_5 = 20; \\ & -4x_1-7x_2-9x_2-6 =x_2-9x_3 -6 9. \ koniec (zarovnaný) \ vpravo $ Gauss-Jordanovou metódou Ak systém nie je definovaný, uveďte základné riešenie.

Podobnými príkladmi sa zaoberá téma „Všeobecné a základné riešenia SLAE“. V druhej časti spomínanej témy uvedený príklad riešené pomocou Gaussovej metódy. Budeme to riešiť pomocou Gauss-Jordanovej metódy. Riešenie nebudeme rozoberať postupne, ako to už bolo urobené v predchádzajúcich príkladoch.

$$ \ vľavo (\ začiatok (pole) (ccccc | c) 1 & -2 & 3 & 0 & 4 & -5 \\ 2 & 1 & 5 & 2 & 9 & -3 \\ 3 & 4 & 7 & 4 & 14 & -1 \\ 2 & -4 & 6 & 0 & 11 & 2 \\ -2 & 14 & -8 & 4 & -7 & 20 \\ -4 & -7 & -9 & -6 & -21 & -9 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ II-2 \ cdot I \\ III-3 \ cdot I \\ IV-2 \ cdot I \\ V + 2 \ cdot I \\ VI + 4 \ cdot I \ koniec (pole) \ šípka doprava \ doľava (\ začiatok (pole) (ccccc | c) 1 & -2 & 3 & 0 & 4 & -5 \ \ 0 & 5 & -1 & 2 & 1 & 7 \\ 0 & 10 & -2 & 4 & 2 & 14 \\ 0 & 0 & 0 & 0 & 3 & 12 \\ 0 & 10 & -2 & 4 & 1 & 10 \\ 0 & -15 & 3 & -6 & -5 & -29 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) \ fantóm (0) \\ II: 5 \\ \ fantóm (0) \\ \ fantóm (0) \\ \ fantóm (0) \\ \ fantóm (0) \ koniec (pole) \ šípka doprava \\ \ doľava (\ začiatok (pole) (ccccc | c) 1 & - 2 & 3 & 0 & 4 & -5 \\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\ 0 & 10 & -2 & 4 & 2 & 14 \\ 0 & 0 & 0 & 0 & 3 & 12 \\ 0 & 10 & -2 & 4 & 1 & 10 \\ 0 & -15 & 3 & -6 & -5 & -29 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I + 2 \ cdot II \\ \ fantóm (0) \\ III-10 \ cdot II \\ IV: 3 \\ V-10 \ cdot II \\ VI + 15 \ cdot II \ koniec (pole) \ šípka doprava \ vľavo (\ begin (pole) (ccccc | c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\ 0 & 1 & -1/5 & 2/5 & 1 / 5 & ​​​​7/5 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & -1 & -4 \\ 0 & 0 & 0 & 0 & -2 & -8 \ koniec (pole) \ vpravo). $$

Domnievam sa, že jedna z vykonaných transformácií ešte potrebuje nejaké vysvetlenie: $ IV: 3 $. Všetky prvky štvrtého riadku boli úplne deliteľné tromi, preto sme čisto z dôvodu jednoduchosti rozdelili všetky prvky tohto riadku na tri. Tretí riadok v transformovanej matici sa stal nulou. Prečiarknite nulový riadok:

$$ \ vľavo (\ začiatok (pole) (ccccc | c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & -1 & -4 \\ 0 & 0 & 0 & 0 & -2 & -8 \ koniec (pole) \ vpravo) $$

Je čas, aby sme prešli k tretiemu kroku, v ktorom by sa prvky tretieho stĺpca mali vynulovať. Diagonálny prvok (tretí riadok) je však nulový. A zmena miesta liniek nič neurobí. Prvý a druhý riadok sme už použili, takže sa ich nemôžeme dotknúť. A nemá zmysel dotýkať sa štvrtého a piateho riadku, pretože problém rovnosti nuly rozlišovacieho prvku nikam nevedie.

V tejto situácii je problém vyriešený mimoriadne jednoduchým spôsobom. Nezvládneme tretiu kolónu? Dobre, prejdime k štvrtému. Možno vo štvrtom stĺpci bude prvok v treťom riadku nenulový. Štvrtá kolóna však trpí rovnakým problémom ako tretia. Prvok tretieho riadku vo štvrtom stĺpci je nula. A zmena miesta čiar opäť nič neurobí. Nezvládate aj štvrtú kolónu? Dobre, prejdime k piatemu. Ale v piatom stĺpci nie je prvok tretieho riadku ani nula. Rovná sa jednej, čo je celkom dobré. Čiže rozlišovací prvok v piatom stĺpci je 1. Rozlišovací prvok je vybraný, takže vykonáme ďalšie transformácie Gaussovej-Jordanovej metódy:

$$ \ vľavo (\ začiatok (pole) (ccccc | c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5 \\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & -1 & -4 \\ 0 & 0 & 0 & 0 & -2 & -8 \ koniec (pole) \ vpravo) \ začiatok (pole) (l) I-22/5 \ cdot III \\ II-1/5 \ cdot III \\ \ fantóm (0) \\ IV + III \\ V + 2 \ cdot III \ koniec (pole) \ šípka doprava \ doľava (\ začiatok (pole) (ccccc | c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5 \\ 0 & 1 & -1 / 5 & 2/5 & 0 & 3/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \ koniec (pole) \ doprava) \ šípka doprava \\ \ šípka doprava \ doľava | \ text (Odstrániť nulové riadky) \ doprava | \ šípka doprava \ doľava (\ začiatok (pole) (ccccc | c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5 \\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \ koniec (pole) \ vpravo) $$

Systémovú maticu a rozšírenú systémovú maticu sme priviedli do stupňovitej formy. Hodnoty oboch matíc sa rovnajú $ r = 3 $, t.j. treba si vybrať 3 základné premenné. Počet neznámych je $ n = 5 $, takže musíte vybrať voľné premenné $ n-r = 2 $. Od $ r< n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":

Na "stupňoch" sú prvky zo stĺpcov č.1, č.2, č.5. Preto základné premenné budú $ x_1 $, $ x_2 $, $ x_5 $. Voľné premenné budú $ x_3 $, $ x_4 $. Stĺpce č. 3 a č. 4, zodpovedajúce voľným premenným, sa presunú nad riadok, pričom sa samozrejme nezabudne zmeniť ich znamienka.

$$ \ vľavo (\ začiatok (pole) (ccccc | c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5 \\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5 \\ 0 & 0 & 0 & 0 & 1 & 4 \ koniec (pole) \ doprava) \ šípka doprava \ doľava (\ začiatok (pole) (ccc | ccc) 1 & 0 & 0 & -99/5 & -13/5 & -4/5 \\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5 \\ 0 & 0 & 1 & 4 & 0 & 0 \ koniec (pole) \ vpravo) ... $$

Z poslednej matice dostaneme všeobecné riešenie: $ \ left \ (\ begin (zarovnané) & x_1 = - \ frac (99) (5) - \ frac (13) (5) x_3- \ frac (4) (5 ) x_4; \\ & x_2 = \ frac (3) (5) + \ frac (1) (5) x_3- \ frac (2) (5) x_4; \\ & x_3 \ v R; \\ & x_4 \ v R; \\ & x_5 = 4. \ koniec (zarovnaný) \ vpravo $. Základné riešenie sa nájde tak, že sa voľné premenné rovnajú nule, t. j. $ x_3 = 0 $, $ x_4 = 0 $:

$$ \ vľavo \ (\ začiatok (zarovnané) & x_1 = - \ frac (99) (5); \\ & x_2 = \ frac (3) (5); \\ & x_3 = 0; \\ & x_4 = 0; \\ & x_5 = 4. \ Koniec (zarovnaný) \ vpravo. $$

Problém je vyriešený, zostáva len zapísať odpoveď.

Odpoveď: Spoločné rozhodnutie: $ \ left \ (\ begin (zarovnané) & x_1 = - \ frac (99) (5) - \ frac (13) (5) x_3- \ frac (4) (5) x_4; \\ & x_2 = \ frac (3) (5) + \ frac (1) (5) x_3- \ frac (2) (5) x_4; \\ & x_3 \ v R; \\ & x_4 \ v R; \\ & x_5 = 4 . \ end (zarovnané) \ right. $, základné riešenie: $ \ left \ (\ begin (zarovnané) & x_1 = - \ frac (99) (5); \\ & x_2 = \ frac (3) (5) ; \\ & x_3 = 0; \\ & x_4 = 0; \\ & x_5 = 4. \ koniec (zarovnaný) \ vpravo. $.

Ak chcete povoliť spustenie apletu na vašom počítači, musíte urobiť nasledovné - kliknite na Štart> Ovládací panel> Programy> Java. V Okno Java Ovládací panel vyberte kartu Zabezpečenie, kliknite na tlačidlo Upraviť zoznam lokalít, pridajte tlačidlo Pridať a vložte cestu k tejto stránke z adresný riadok prehliadač. Potom stlačíme tlačidlá OK, potom reštartujeme počítač.

Pre spustenie apletu kliknite na tlačidlo "Simplex". Ak tlačidlo "Simplex" nie je viditeľné nad týmto riadkom, potom Java nie je v počítači nainštalovaná.

Po kliknutí na tlačidlo "Simplex" sa zobrazí prvé okno pre zadanie počtu premenných a počtu obmedzení úloh pre simplexnú metódu.

Po kliknutí na tlačidlo „ok“ sa zobrazí okno na zadanie zvyšku údajov o úlohe pre simplexnú metódu: režim zobrazenia (desatinné zlomky alebo obyčajné zlomky), typ kritéria úlohy min alebo max, zadanie koeficientov cieľovej funkcie a koeficienty obmedzovacieho systému so znamienkami „≤“, „ ≥ „alebo“ = „, obmedzenia v tvare х i ≥ 0 nie je potrebné zadávať, ich zohľadňuje vo svojom algoritme.

Po kliknutí na tlačidlo "Vyriešiť" sa zobrazí okno s výsledkami riešenia problému .Okno pozostáva z dvoch častí, v hornej časti je textové pole s popisom prevodu pôvodného problému na kanonická forma ktorý sa používa na zostavenie prvej simplexnej tabuľky. V spodnej časti okna na paneli s kartami sú simplexné tabuľky každej iterácie s malým Textové pole v spodnej časti so stĺpcom rozlíšenia, riadkom rozlíšenia a ďalšími informáciami, ktoré z programu robia návod. V záložke s optimálnou (poslednou) tabuľkou je v textovom poli zobrazené získané optimálne riešenie úlohy.

Všetky zaznamenané chyby a komentáre k apletu pošlite na adresu [e-mail chránený] alebo volajte 8 962 700 77 06, za čo Vám budeme veľmi vďační.

Program M-metódy

Program riešenia dopravný problém

Tu je ručné (nie applet) riešenie dvoch problémov simplexovou metódou (podobne ako apletové riešenie) s podrobné vysvetlenia aby sme pochopili algoritmus riešenia problémov. Prvý problém obsahuje znaky nerovnosti iba "≤" (problém s počiatočným základom), druhý môže obsahovať znaky "≥", "≤" alebo "=" (problém s umelý základ), riešia sa rôznymi spôsobmi.

Simplexná metóda, riešenie problému s počiatočným základom

1)Simplexná metóda pre problém s počiatočným základom (všetky znaky nerovnosti-obmedzenia "≤").

Zapíšme si úlohu kanonický forme, t.j. obmedzenia nerovností možno prepísať ako rovnosti pridaním súvaha 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é. Problémy, ktoré sa riešia simplexnou metódou, musia mať tieto dve vlastnosti:
- systém obmedzení musí byť systémom 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é členy sú nezáporné, preto je možné použiť simplexnú metódu. Zostavme si prvú simplexnú tabuľku (Iterácia 0), t.j. tabuľku koeficientov objektívnych funkcií a sústavu rovníc pre zodpovedajúce premenné. Tu „BP“ znamená stĺpec základných premenných, „Solution“ – stĺpec pravých strán rovníc systému. Riešenie nie je optimálne, pretože v z - riadku sú záporné koeficienty.

iterácia 0

BP						Riešenie	Postoj

Ak chcete zlepšiť riešenie, prejdite na ďalšiu iteráciu, dostaneme nasledujúcu simplexnú tabuľku. Ak to chcete urobiť, musíte si vybrať permisívny stĺpec, t.j. premenná, ktorá bude zahrnutá do základu pri ďalšej iterácii. Vyberá sa najväčším záporným koeficientom v absolútnej hodnote v z-riadku (v maximálnom probléme) - v počiatočnej iterácii je to stĺpec x 2 (koeficient -6).

Potom sa vyberie permisívny reťazec, t.j. premenná, ktorá opustí základ pri ďalšej iterácii. 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 je na priesečníku rozlišovacieho stĺpca a rozlišovacieho riadku, jeho bunka je zvýraznená, rovná sa 1. Preto pri ďalšej iterácii premenná x 2 nahradí s 3 v základe. Všimnite si, že vzťah sa nehľadá v z-riadku, je tam vložená pomlčka „-“. Ak existujú rovnaké minimálne vzťahy, vyberie sa ktorýkoľvek z nich. Ak sú všetky koeficienty v rozlišovacom stĺpci menšie alebo rovné 0, potom je riešenie problému nekonečné.

Vyplňte nasledujúcu tabuľku „Iterácia 1“. Získame to z tabuľky "Iterácia 0". Cieľom ďalších transformácií je zmeniť rozlišovací stĺpec x 2 na jeden (s jednotkou namiesto rozlišovacieho prvku 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 (rovná sa 1 v v tomto prípade) tejto tabuľky dostaneme riadok x 2 v tabuľke "Iterácie 1". Pretože rozlišovací prvok je v tomto prípade rovný 1, potom sa riadok s 3 tabuľky "Iterácia 0" zhoduje s riadkom x 2 tabuľky "Iterácia 1". Dostali sme riadok x 2 tabuľky „Iterácia 1“ 0 1 0 0 1 20, ostatné 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 (z-riadok) v stĺpci x 2 tabuľky Iterácia 0 by mala byť 0 v prvom riadku tabuľky Iterácia 1. Aby sme to dosiahli, vynásobíme všetky prvky riadku x 2 tabuľky "Iterácia 1" 0 1 0 0 1 20 číslom 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 objaví nula 0, cieľ je dosiahnutý. Prvky stĺpca rozlíšenia x 2 sú zvýraznené červenou farbou.

3) Výpočet riadku s 1 tabuľky "Iterácia 1". Na mieste 1 v 1 riadku tabuľky "Iterácia 0" musí 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 -1, dostaneme 0 -1 0 0 -1 -20 a pridáme tento riadok s 1 - riadok tabuľky "Iterácia 0" 2 1 1 0 0 64, dostaneme riadok 2 0 1 0 -1 44. V stĺpci x 2 dostaneme požadovanú 0.

4) Výpočet riadku s 2 tabuľky "Iterácia 1". Na mieste 3 v s 2 riadku tabuľky "Iterácia 0" musí byť 0 v tabuľke "Iterácia 1". 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 2 - riadok tabuľky "Iterácia 0" 1 3 0 1 0 72, dostaneme riadok 1 0 0 1 -3 12. V stĺpci x 2 dostaneme požadovanú 0. Stĺpec x 2 v tabuľke "Iterácia 1" sa stal jedným , 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 stĺpca rozlíšenia starého riadka) * (nový riadok rozlíšenia).

Napríklad pre z -string máme:

Stará reťazec z (-4 -6 0 0 0 0)
- (- 6) * Nový reťazec rozlíšenia - (0-6 0 0 -6 -120)
= Nová čiara z(-4 0 0 0 6 120) .

Pre nasledujúce tabuľky sa prepočítavanie prvkov tabuľky robí rovnakým spôsobom, preto ho vynecháme.

iterácia 1

						Riešenie	Postoj

Povolenie stĺpca x 1, vyriešenie riadku s 2, s 2 opustí základ, x 1 vstúpi do základu. Presne rovnakým spôsobom dostaneme zvyšok simplexných tabuliek, až kým nedostaneme tabuľku so všetkými kladnými koeficientmi v z-riadku. To je znak optimálneho stola.

Iterácia 2

						Riešenie	Postoj

Rozlišovací stĺpec s 3, rozlišovací riadok s 1, s 1 opúšťa základ, s 3 vstupuje do základu.

Iterácia 3

						Riešenie	Postoj

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

Simplexná metóda, riešenie problému s umelým základom

2) Vyriešme problém s umelým základom (aspoň jeden znak nerovnosti-obmedzenia "≥" alebo "=").

Úlohu napíšme v kanonickom tvare (vo forme sústavy rovníc, ktorá vyžaduje simplexnú metódu), na to zavedieme dve premenné x 3 ≥ 0 a x 4 ≥ 0 dostaneme:

Systém obmedzení ponúka iba jednu prípustnú základnú premennú x 4, len je zahrnutá len v jednej rovnici v tretej s koeficientom 1, preto do prvej a druhej rovnice pridáme umelé premenné R 1 ≥ 0 a R 2 ≥ 0 rovnice-obmedzenia musia byť systémom so základom, t.j. v každej rovnici musí byť premenná s koeficientom 1, ktorá je obsiahnutá len v jednej rovnici systému, v našom prípade je to R 1, R 2 a x 4. Máme takzvaný M-problém:

Tento systém je systém so základom, v ktorom R 1, R 2 a x 4 sú základné premenné a x 1, x 2 a x 3 sú voľné premenné, voľné členy všetkých rovníc sú nezáporné. Preto je možné na vyriešenie problému použiť simplexnú metódu. Zapíšme si počiatočnú simplexnú tabuľku:

iterácia 0

							Riešenie	Postoj
		-16

Do tabuľky pridaný riadok „Hodnotenie“ pre úlohy s umelým základom. Získa sa sčítaním zodpovedajúcich koeficientov riadkov s umelými premennými (R) s opačným znamienkom. V tabuľke bude prítomná, pokiaľ bude v základe aspoň jedna z umelých premenných. Podľa najväčšieho modulo záporného koeficientu v riadku "Skóre" sa určuje rozlišovací stĺpec, kým je v tabuľke. Keď riadok "Skóre" opustí tabuľku (v základe nie sú žiadne fiktívne premenné), rozlišovací stĺpec bude určený riadkom Z, ako v prípade problému s počiatočným základom. V tejto tabuľke je rozlišovací stĺpec x 2, je vybraný podľa najväčšieho modulo záporného odhadu (-7). Rozlišovací riadok R 2 je vybraný podľa najmenšieho pomeru stĺpca "Rozhodnutie" k zodpovedajúcim kladným prvkom rozlišovacieho stĺpca, ako v úlohe bez umelých premenných. To znamená, že pri ďalšej iterácii premenná x 2 prejde z voľnej do základnej a premenná R 2 zo základnej do voľnej. Napíšme si nasledujúcu simplexnú tabuľku:

Prípustný stĺpec x 1, prípustný riadok R 1, R 1 je mimo základu, x 1 je zaradený do základu. Potom v základe nezostanú žiadne umelé premenné, takže v nasledujúcej tabuľke nie je riadok „Vyhodnotenie“:

iterácia 2

							Riešenie	Postoj

Ďalej sa rozlišovací stĺpec vyberie podľa z-riadku. V z-riadku sú všetky koeficienty nezáporné okrem koeficientu figuríny R 1, ktorý nemá vplyv na optimálnosť, keď je figurína mimo základu. Preto sa získa optimálne riešenie x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Špeciálne prípady simplexovej metódy

1) Keď je priamka (ak sa berie do úvahy dvojrozmerný problém lineárne programovanie a v všeobecný prípad nadrovina) reprezentujúca účelovú funkciu je rovnobežná s priamkou (nadrovinou) zodpovedajúcou jednej z nerovníc-obmedzení (ktorá je v optimálnom bode splnená ako presná rovnosť) objektívna funkcia berie to isté optimálna hodnota na nejakom súbore bodov hranice regiónu realizovateľných riešení. Tieto riešenia sú tzv alternatívne optimálne riešenia... Dostupnosť alternatívne riešenia možno určiť z optimálnej simplexovej tabuľky. Ak z-riadok optimálnej tabuľky obsahuje nulové koeficienty nezákladných premenných, potom existujú alternatívne riešenia.

2) Ak sú v rozlišovacom stĺpci simplexnej tabuľky všetky koeficienty menšie alebo rovné nule, potom sa rozlišovací riadok nedá vybrať, v tomto prípade je riešenie neohraničené.

3) Ak sú obmedzenia problému lineárneho programovania nekonzistentné (t. j. nemožno ich vykonať súčasne), potom problém nemá žiadne realizovateľné riešenie. Táto situácia nemôže nastať, ak všetky nerovnosti, ktoré tvoria systém obmedzení, sú typu „≤“ s nezápornými pravými stranami, pretože v tomto prípade môžu ďalšie premenné predstavovať možné riešenie. Pre iné typy obmedzení sa používajú umelé premenné. Ak má úloha riešenie, potom v optimálnej tabuľke v základe nie sú žiadne umelé premenné (R i). Ak tam sú, potom problém nemá riešenia.

Ako viete, Jordan-Gaussova metóda, známa aj ako metóda postupného odstraňovania neznámych, je modifikáciou Gaussovej metódy na riešenie systémov lineárnych algebraických rovníc (SLAE).

Metóda je založená na elementárne transformácie(preklad systému na ekvivalent), ktoré zahŕňajú:

• pridanie na obe strany rovnice sústavy ďalšej rovnice tej istej sústavy vynásobenej číslom iným ako nula;
• preskupenie rovníc v systéme;
• odstránenie zo sústavy rovníc v tvare 0 = 0.

Na rozdiel od Gaussovej metódy je v každom kroku zo všetkých rovníc okrem jednej eliminovaná jedna premenná.

Krok metódy je nasledujúci:

• vyberte v ďalšej rovnici neznámu s nenulovým koeficientom (rozlišovací prvok);
• vydeliť vybranú rovnicu rozlišovacím prvkom;
• použitie vybranej rovnice na vylúčenie neznámej v rozlišovacom prvku zo všetkých ostatných rovníc;
• na ďalši krok podobne je zo všetkých rovníc okrem jednej vylúčená ďalšia neznáma;
• proces pokračuje, kým sa nepoužijú všetky rovnice.

Dá sa to algoritmizovať takto:

Pre SLAE v tvare matice A * x = b (matica A rozmeru m * n, nemusí byť nevyhnutne štvorcová) je zostavená nasledujúca tabuľka:

V tabuľke je vybraný rozlišovací prvok a r, s ≠ 0, potom r je rozlišovací riadok, s je rozlišovací stĺpec.

Prechod na ďalšiu tabuľku sa vykonáva podľa pravidiel:

1. prvky rozlišovacej čiary sa vypočítajú: a "r, j = a r, j / a r, s - to znamená, že r-riadok tabuľky je rozdelený rozlišovacím prvkom;

2.všetky prvky rozlišovacej kolóny okrem a r, s, rovný jednej, rovná sa nule;

3. Prvky mimo rozlišovacieho riadka a stĺpca sa vypočítajú pomocou vzorca uvedeného nižšie:

Je ľahké nenechať sa zmiasť, keď uvidíte, že čitateľ tohto vzorca je podobný výpočtu determinantu matice 2 x 2.

4. Pri manuálnom výpočte sa hodnota v poslednom kontrolnom stĺpci porovnáva so súčtom prvkov predchádzajúceho riadku. Ak sa hodnoty nezhodujú, mali by ste hľadať chyby v tomto riadku. Riadiaci stĺpec môže byť pre automatizovaný výpočet vynechaný.

Možné sú tieto prípady:

1. V procese výnimiek ľavá strana rovnice sústavy zaniknú a pravá b ≠ 0, potom sústava nemá riešenie.

2. Ukáže sa identita 0 = 0 - rovnica je lineárnou kombináciou ostatných a reťazec núl možno zo systému vymazať.

3. Po použití všetkých rovníc na odstránenie neznámych tabuľka buď obsahuje požadované riešenie, alebo ukazuje nekonzistentnosť systému obmedzení.

Naprogramujme metódu v Exceli s jedným vzorcom, ktorého zmena by nemala byť príliš časovo náročná. Napríklad vyriešiť SLAE

vyplňte koeficienty buniek listu od A1 do D4 vrátane, vyberte rozlišovací prvok a 1,1 = 1 a prvý krok metódy urobte v bunke A6, kde nastavíme "univerzálny" vzorec pre Jordan- Gaussova transformácia:

IF (LINE ($ A $ 1) = LINE (A1); A1 / $ A $ 1;
IF (STĺpec ($ A $ 1) = STĹPEC (A1); 0; (A1 * $ A $ 1-
NEPRIAME (ADRESA (RIADOK (A1), STĹPEC ($ A $ 1))) *
NEPRIAME (ADRESA (RIADOK ($ A $ 1; STĹPEC (A1)))) / $ A $ 1))

V ďalšom kroku môže byť rozlišovacím prvkom napríklad a 2,2 = 1 (bunka B7). Zostáva nám skopírovať vzorec z A6 do A11 (podľa prázdny riadok ponechajte na vizuálne oddelenie krokov metódy), vstúpte do režimu úpravy vzorca ( dvojité kliknutie na bunku alebo ju vyberte a stlačte kláves F2) a opravte (jemne potiahnite myšou cez okraj) všetky ukotvené prepojenia z bunky A1 do B7.

Pevný odkaz $ A $ 1 môžete samozrejme nahradiť všade vo vzorci konštrukciou v tvare NEPRIAME (BUŇKA) dynamická adresa odkazy. Povedzme, NEPRIAME (F8) a v bunke F8 sa adresa bunky rozlišovacieho prvku automaticky vygeneruje daným používateľomčísla riadkov a stĺpcov. Potom pre tieto čísla riadkov a stĺpcov budete musieť poskytnúť samostatné bunky, napríklad takto:

Bohužiaľ, toto všetko nedá nič - namiesto $ A $ 1 budeme musieť vo vzorci jednoducho opraviť NEPRIAME ($ F $ 8) a pri kopírovaní vzorca pretiahnuť a pustiť rovnaký počet odkazov. Navyše „ručne“ zadané čísla riadkov a stĺpcov bude treba kontrolovať aj z hľadiska platnosti (aspoň ako na obrázku), takže entity nebudeme množiť.

Prevádzku metódy môžete vidieť na prvých dvoch hárkoch prílohy Excel súbor(2 rôzne príklady).

Nasledujúce je založené na Jordan-Gaussovej transformácii univerzálna metóda riešenie úloh lineárnej optimalizácie ako simplexná metóda... Jeho opisy sú zvyčajne strašidelné, dlhé a preplnené teorémami. Pokúsme sa urobiť jednoduchý popis a vytvoriť algoritmus vhodný na výpočet v Exceli. V skutočnosti je simplexná metóda už zabudovaná do štandardného doplnku Analysis Package a nie je potrebné ju programovať „ručne“, takže náš kód má skôr vzdelávaciu hodnotu.

Po prvé, minimum teórie.

Ak sú stĺpcové vektory SLAE lineárne nezávislé, zodpovedajúce premenné sú základné a zvyšok - zadarmo... Napríklad v SLAE

premenné x 2 a x 4 sú základné a x 1 a x 3 sú voľné. Základné premenné sú medzi sebou nezávislé a z voľných premenných je možné vytvoriť napríklad nuly a získať (x 2 = 2, x 4 = 1) - základné riešenie systémov.

Výberom rôznych rozlišovacích prvkov je možné získať riešenia SLAE s rôznymi bázami. Volá sa akékoľvek nezáporné zásadité riešenie SLAE podporujúce.

Simplexová metóda poskytuje prechod z jednej referenčný roztok inému, kým sa nedosiahne optimálne riešenie, ktoré dáva minimum účelovej funkcie.

Algoritmus simplexovej metódy je nasledujúci:

1. Problém LP sa transformuje do kanonickej podoby:

Vždy to možno urobiť nasledovne: k problému napísanému v štandardnom nastavení

dodatočné súvahové premenné, ktorých počet zodpovedá počtu obmedzení nerovnosti m (obmedzenia na nezápornosť hodnôt neznámych sa neberú do úvahy). Potom sa nerovnosti so znamienkom "≤" zmenia na rovnosti, napríklad systém obmedzení tvaru

2 * x 1 + 3 * x 2 ≤ 20
3 * x 1 + x 2 ≤ 15
4 * x 1 ≤ 16
3 * x 2 ≤ 12
x 1, x 2 ≥0

bude mať formu

2 * x 1 + 3 * x 2 + x 3 = 20
3 * x 1 + x 2 + x 4 = 15
4* x 1 + x 5 = 16
3 * x 2 + x 6 = 12
x 1, x 2, ..., x 6 ≥0

To znamená, že „ekonomický“ význam bilančných premenných je veľmi jednoduchý – ide o „zvyšky“ nevyužitých zdrojov každého typu.

Ak v pôvodný problém nehľadalo sa minimum, ale maximum, účelová funkcia Z bude nahradená Z 1 = -Z. Riešenia problémov sa zhodujú, pričom min Z = - max Z 1. Napríklad cieľ

Z (x 1, x 2) = 2 * x 1 + 5 * x 2 (max.)

prepísané ako

Z 1 (x 1, x 2) = - 2 * x 1 - 5 * x 2 (min)

Ak v pôvodnej úlohe boli rovnice nerovnosti so znamienkami "≥" namiesto "≤", obe strany každej takejto nerovnosti sa vynásobia -1 a znamienko nerovnosti sa obráti, napr.

3 * x 1 + x 2 + x 4 ≥15

mení sa v

3 * x 1 - x 2 - x 4 ≤ 15

Získa sa kanonická forma modelu, pretože je napísaná simplexný stôl:

Základné premenné (BP) sa zapisujú do ľavého stĺpca, ak ešte nie sú vybraté - prázdne.

2. Pomocou krokov Jordan – Gauss sa zistí počiatočný referenčný plán, t.j. SLAE sa redukuje na základnú formu s nezápornými voľnými členmi b i> 0. V tomto prípade by účelová funkcia Z mala byť vyjadrená len v podmienkach voľných neznámych (nulové koeficienty v Z-riadku sa vyskytujú len pod premennými x i, ktoré sú v báze). Pri výbere rozlišovacieho prvku a r, s vypíšeme premennú x s do riadku r stĺpca BP, ak tam už premenná bola, vymažeme ju (odvodíme zo základu).

3. Pod stĺpce x i zapíšte referenčný plán X *: pod voľné premenné - nuly, pod základné - koeficienty zo stĺpca b zodpovedajúce základnej premennej.

Dole zapíšeme vektor R podľa pravidla: pod základné premenné - nuly, pod voľné R i = Z i.

Ak sú všetky R i ≥0 nájdené optimálne riešenie X * a hodnota cieľa Z min = -q, v opačnom prípade potrebujete nový plán, máš to, súdruh Žjukov? (str. 4).

4. Pre výber rozlišovacieho stĺpca s vyberieme maximálnu modulo zápornú zložku vektora R, vyberieme rozlišovací stĺpec s. Potom analyzujeme koeficienty s-tého stĺpca matice systému obmedzení. Ak všetky a i, s ≤ 0, neexistuje žiadne riešenie a Z min má tendenciu k mínus nekonečnu, inak prejdite na krok 5.

5. Ak chcete vybrať rozlišovaciu čiaru r, zostavte nezáporné pomery b i / A i, s ≥ 0, i = 1,2, ..., m a vyberte z nich najmenší. Ak je dosiahnuté minimum pre niekoľko riadkov, ktorýkoľvek z nich môže byť považovaný za rozlišovací, pričom v novom referenčnom dizajne sa hodnoty niektorých základných premenných stanú rovnými 0, t.j. dostaneme degenerovaný referenčný dizajn.

6. Vykonajte Jordanovu-Gaussovu transformáciu s rozlišovacím prvkom a r, s a prejdite na krok 3

Geometricky simplexná metóda zodpovedá najkratšiemu prechodu vrcholov n-rozmerného konvexného mnohostenu, ktorý tvorí doménu realizovateľných riešení problému:

Tu sme prešli od základného plánu C, ktorý je jedným z vrcholov viacrozmerného mnohouholníka, k optimálnemu plánu E = X *.

Naprogramovať to všetko v Exceli nie je jednoduché, ale dá sa to. Priložený dokument obsahuje 3 príklady, ktoré realizujú riešenie úloh simplexovou metódou. Je pravda, že pri vykonávaní kroku budete musieť zmeniť 3 vzorce, ktoré sú zvýraznené na hárku prvého príkladu pre simplexnú metódu žltá: výpočet pomerov pre výber riadku rozlíšenia v bunke I2, vyplnenie stĺpca BP v bunke A12, krok Jordan-Gaussovej transformácie v bunke B12. Rovnako ako v príklade Jordan-Gaussovej transformácie je zmena vzorcov spojená iba s potrebou odkazovať na Nový riadok obsahujúci adresu bunky s povoľujúcim prvkom (pre prvý krok - bunka C9).

Za predpokladu, že neexistujú žiadne „0-riadky“ (obmedzenia rovnosti) a „voľné“ premenné (t. j. premenné, ktoré nepodliehajú požiadavke na nezápornosť).

2. V prípade prítomnosti obmedzení rovnosti a „voľných“ premenných postupujte nasledovne.

Vyberie sa prvok povolenia v „riadku 0“ a vykoná sa upravený krok Jordanovej výnimky, po ktorom sa tento stĺpec povolenia vymaže. Táto postupnosť akcií pokračuje až do simplexný stôl zostane aspoň jeden „0-riadok“ (tabuľka sa teda skráti).

Ak existujú aj voľné premenné, potom tieto premenné musia byť základné. A potom, čo sa voľná premenná stane základnou, v procese určovania rozlišovacieho prvku pri hľadaní referenčných a optimálnych plánov daný reťazec nepočítané (ale prevedené).

Degenerácia v problémoch lineárneho programovania

Vzhľadom na simplexnú metódu sme predpokladali, že problém lineárneho programovania je nedegenerovaný, t.j. každý referenčný plán obsahuje presne
pozitívne zložky, kde
- počet obmedzení v úlohe. V degenerovanom referenčnom dizajne je počet kladných komponentov menší ako počet obmedzení: niektoré základné premenné zodpovedajúce danému referenčnému dizajnu nadobúdajú nulové hodnoty. Použitie geometrickej interpretácie pre najjednoduchší prípad, keď
(počet nezákladných premenných je 2), je ľahké rozlíšiť degenerovaný problém od nedegenerovaného. V degenerovanom probléme sa v jednom vrchole mnohostenu podmienok pretínajú viac ako dve priame čiary opísané rovnicami tvaru
... To znamená, že jedna alebo viac strán polygónu podmienky je zbalených do bodu.

A zdaniteľné pri
v degenerovanom probléme sa v jednom vrchole pretínajú viac ako 3 roviny
.

Za predpokladu, že problém bol nedegenerovaný, existovala iba jedna hodnota
, pomocou ktorej sa určoval index vektora podmienok odvodeného od bázy (odvodeného od počtu základných premenných). V degenerovanom probléme
možno dosiahnuť pri niekoľkých indexoch naraz (pre niekoľko riadkov). V tomto prípade bude v nájdenom referenčnom pláne niekoľko základných premenných nulových.

Ak sa ukáže, že problém lineárneho programovania je degenerovaný, potom pri zlej voľbe vektora podmienok odvodených zo základu môže nastať nekonečný pohyb pozdĺž základne rovnakého referenčného plánu. Takzvaný slučkový fenomén. Aj keď v praktických problémoch lineárneho programovania je zacyklenie extrémne zriedkavým javom, jeho možnosť nie je vylúčená.

Jednou z metód riešenia degenerácie je transformácia problému „nepodstatnou“ zmenou vektora pravých strán systému obmedzení hodnôt. , aby sa problém nedegeneroval a zároveň aby ​​táto zmena reálne neovplyvnila optimálny plán problému.

Bežnejšie implementované algoritmy zahŕňajú niekoľko jednoduchých pravidiel na zníženie pravdepodobnosti výskytu slučiek alebo na ich prekonanie.

Nechajte premennú musí byť urobený základný. Zvážte súbor indexov pozostávajúce z tých pre ktoré
... Veľa indexov , pre ktoré je táto podmienka splnená, označujeme ako ... Ak pozostáva z jedného prvku, potom je zo základu vylúčený vektor podmienok (premenná sa stane nezákladným).

Ak pozostáva z viac ako jedného prvku, potom zo súboru ktorý pozostáva z
na ktorom
... Ak pozostáva z jedného indexu , potom je premenná odvodená od základu ... V opačnom prípade sa zostava skladá atď.

V praxi by sa pravidlo malo použiť, ak už bola slučka zistená.