Upravená simplexní metoda. Cvičení: Simplexní metoda v prezentační formě. Multiplikativní reprezentace inverzní matice

1.5.1. Výpočtové schéma založené na transformaci inverzních matic. Při analýze výpočetního postupu simplexové metody z hlediska odhadu pracnosti je snadné vidět, že nejkritičtější je v tomto ohledu fáze přepočítávání hodnot A A b při přechodu z jednoho základního plánu do druhého (kapitola 3 algoritmu). Nicméně v případě, kdy počet omezení problému m jednoznačně méně proměnných n, můžete dosáhnout významných „úspor“ provedením v další iteraci q Jordan-Gaussova transformace ne přes matrici A(β ( q)) a přes matici Δ -1 (β ( q)). To také bere v úvahu skutečnost, že v případě potřeby lze pomocí vzorce (1.26) vždy získat A(β ( q)) o Δ -1 (β ( q)). Navíc, abychom mohli provádět akce výše popsaného simplexního postupu, ve skutečnosti jsme matici nepotřebovali A(β ( q)) úplně. Ve skutečnosti v něm byla použita pouze ratingová linie A 0 (β ( q)) a úvodní sloupec a l(β ( q)). Tyto úvahy tvoří základ výpočtového schématu simplexové metody, založené na transformaci inverzních matic, které se také říká modifikovaná simplexová metoda. Poprvé tento algoritmus byl navržen v roce 1951 v dílech L. V. Kantoroviče.

Výpočtové schéma modifikované simplexové metody odpovídá soustavě tabulek T 1 a T 2 (q). Tabulka T 1 (rýže. 1.7) je společný pro všechny iterace a slouží k získání řady odhadů pro aktuální základní linii A 0 (β ( q)). Označíme-li δ i(β ( q)) (iÎ 0: m) řádky matice Δ -1 (β ( q)), pak zejména z (1.26) vyplývá, že

Jak je vidět z rýže. 1.7, T 1 se skládá ze tří bloků:

Ø Ø střed obsahuje matici A;

Ø Ø v levém bloku tabulky se při každé iteraci přidávají nulové řádky maticeΔ -1 (β ( q))pro aktuální základ;

Ø Ø spodní blok umístěný pod maticí A, při každé iteraci je doplněna o řádek odhadů aktuálního plánu, vypočítaný podle vzorce (1.42).

Simplexní stůl T 2 (q) zobrazeno v rýže. 1.8, odpovídá přípustnému základu KZLP β ( q) přijato v q iteraci. Sloupec N(β ( q)) obsahuje čísla sloupců základu (v pořadí výskytu v základu); sloupec b(β ( q)) - složky vektoru omezení vzhledem k aktuální bázi β ( q); Δ -1 (β ( q)) - matice inverzní k matici rozšířených sloupců aktuální báze β ( q); graf a l obsahuje rozšířený vektor podmínek zavedených do základu v aktuální iteraci a další graf obsahuje souřadnice a l(β ( q)) stejného sloupce v aktuálním základu β ( q) .

Analogicky k odstavci 1.4.1 popíšeme formální schéma algoritmu modifikovaná simplexová metoda.

0-stupeň. Nalezení proveditelné základní linie.

1. K nalezení přípustného základu lze použít metodu minimalizace zbytků popsanou v odstavci 1.4.5. V tomto případě se pro řešení pomocné úlohy používá postup modifikované simplexové metody. V důsledku nulové fáze získáme proveditelnou základní linii x(β (1)) a odpovídající matici Δ -1 (β (1)) a vektor b(p(1)).

2. Vyplňte střední část tabulky T 1 obsahující matrici A.

3. Obsah matice Δ -1 (β (1)) a vektoru b(β (1)), získaný ve fázi hledání přípustného základního plánu, se přenese do tabulky T 2 (1) .

4. Nastavte číslo aktuální iterace q rovno 1 a přejděte do fáze I.

Fáze 1. Standardní iterace algoritmu- proveden pro další základní plán x(β ( q)).

1°. Kontrola optimálnosti aktuálního základního plánu. Obsah nultého řádku tabulky T 2 (q) - δ 0 (β ( q)) se přepíše do odpovídajícího sloupce tabulky T 1. Pomocí vzorce (1.42) vypočítáme a vyplníme řádek A 0 (β ( q)). Podíváme se na linii hodnocení A 0 (β ( q)). Jsou dvě možnosti:

1΄. A 0 (β ( q))≥0 -plán odpovídající aktuálnímu základu problému, optimální. Proces výpočtu je dokončen. Podle vzorců (1.33) a (1.32) je sepsán optimální plán úlohy X* = x(β ( q)) A optimální hodnotu objektivní funkce F(X*) = F(x(β ( q))).

1". V řádku hodnocení A 0 (β ( q)) existuje alespoň jeden prvek A 0, j(β ( q))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x(β ( q)) - suboptimální. Číslo je vybráno l, odpovídající prvku, který má minimální (maximální v absolutní hodnotě) záporné skóre:

l sloupec matice A se stává vedoucí a musí být zapsána do dalšího základu. Přejděme k bodu 2° algoritmu.

2°. Definování sloupce odvozeného od základu. Přepsání úvodního sloupce a l od stolu T 1 k aktuální tabulce T 2 (q). Podle vzorce a l(β ( q)) = Δ -1 (β ( q))a l vyplňte odpovídající sloupec v tabulce T 2 (q). Jsou dvě možnosti:

2". Pro všechny iО 1: m a i, l(β ( q))≤0. Dochází k závěru, že neomezený objektivní funkce a výpočetní proces končí.

2". Existuje alespoň jeden index iО 1: m, pro které a i, l(β ( q))>0. Podle pravidla (1.27) se určí umístění r a číslo N r(β ( q)) pro sloupec odvozený od základu. Přejděme k bodu 3° algoritmu.

3°. Přepočet vzhledem k novému základu prvků sloupce b A matrice A-1. Přechod na nový základ β ( q+1), který se získá zavedením β ( q) sloupec a l a výstup sloupce z něj a r se provádí podle vzorců podobných vzorcům (1.28)-(1.31). Vypadají jako:

Nastavíme číslo aktuální iterace q: =q+l a přejděte k prvnímu bodu algoritmu.

Závěrem zdůrazňujeme, že vzhledem k výše uvedeným výhodám se ve skutečnosti používá právě modifikovaná simplexová metoda software, určený k řešení kanonické problémy lineární programování.

1.5.2. Příklad řešení ZLP modifikovanou simplexovou metodou. Uveďme řešení dříve uvažované úlohy (1.34)-(1.35), založené na použití postupu modifikované simplexové metody. Analogicky s oddílem 1.4.3 se začíná výběrem zřejmého výchozího základu tvořeného sloupci (5,2,3). Pro to platí Δ -1 (β ( q)) A b(β ( q)), tedy vyplnění úvodních tabulek T 1 a T 2(1) není obtížné.

V první iteraci přepíšeme nulový řádek

z T 2 (1) palce T 1 a vynásobením maticí A, dostaneme řadu hodnocení

Protože A 0 (β (1)) obsahuje záporné prvky, pak docházíme k závěru, že plán odpovídající základně β (1) není optimální a výběrem nejmenšího záporného odhadu (-88) získáme číslo zadaného sloupce. základ, l= 4.

Přepisování sloupce

od stolu T 1 palec T 2 (1) a přepočítejte její souřadnice vzhledem k aktuální bázi, tj. vynásobte matici Δ -1 (β ( q)), který se nachází v tabulce T 2 (1) vlevo, na A 4 .

Po vyplnění tabulky T 2 (1) S údaji o sloupci zapsanými do nového základu můžete přistoupit k určení čísla výstupního sloupce. Tento postup se provádí zcela analogicky s konvenční simplexovou metodou. Po zvážení vztahů prvků b i(p(1)) a a i, l(β (1)) pro ( iО1: m| a i, l(β (1))>0) a po určení jejich minima zjistíme, že r= 2. Proto sloupec s číslem N 2 (β ( q)) = 2 musí být odvozeno od základu. Získáme tak další přípustný základ pro problém s N(p (2)) = (5, 4, 3). Živel A 2.3(β(1)) je proklad (zakroužkovaný). Použitím vzorců (1.43)-(1.46) přejdeme k simplexní tabulce odpovídající druhé iteraci T 2 (2) a nastavte index aktuální iterace q = 2.

Opakováním stejných kroků (lze je snadno sledovat ze zde uvedených tabulek) T 2 (2) a T 2 (3), při třetí iteraci získáme optimální plán problému a optimální hodnotu účelové funkce, které jsou extrahovány z druhého sloupce tabulky T 2 (3). Je snadné si všimnout, že v procesu řešení jsme „prošli“ stejnou sekvencí přípustných základních plánů, na kterou jsme narazili v části 1.4.3.

Federální agentura pro vzdělávání

Stát vzdělávací instituce vyšší odborné vzdělání

Státní technická univerzita v Permu

Lysvensky obor

Katedra ekonomie

Práce v kurzu

v oboru "Systémová analýza a operační výzkum"

na téma: „Simplexní metoda v prezentační formě“

Vyplněno studentem skupiny VIVT-06-1:

Startseva N.S.

Kontrolováno učitelem:

Mukhametyanov I.T.

Lysva 2010

Zavedení. 3

Matematické programování. 5

Grafická metoda. 6

Tabulková simplexová metoda. 6

Metoda umělý základ. 7

Upravená simplexní metoda. 7

Dual simplex - metoda. 7

Obecný pohled na problém lineárního programování. 9

Řešení úlohy lineárního programování simplexovou metodou. 11

Výpočetní postupy simplexové metody. 11

Věta 1: 13

Věta 2: 14

Věta 3: 15

Věta 4: 15

Věta 5: 15

Přechod do nového referenční plán. 15

Dvojitý úkol. 17

Věta 1 (první věta o dualitě) 18

Věta 2 (druhá věta o dualitě) 18

Závěr. 20

Optimální řešení problému lineárního programování patří mezi referenční řešení. Myšlenka simplexové metody spočívá v tom, že se podle určitého pravidla třídí referenční řešení, dokud se mezi nimi nenajde to optimální. Protříděním referenčních řešení v podstatě třídíme různé základní proměnné , v dalším kroku se ze základních přenese nějaká proměnná a místo ní nějaká proměnná z počtu volných do počtu základních.

7x 1 +5x 2 →max

x 3 = 19-2x 1-3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 původní referenční plán

x 6 = 18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

Na intuitivní úrovni je jasné, že bude přirozené zvýšit x 1, protože koeficient pro něj je větší než pro x 2. Ponecháme-li x 2 = 0, můžeme zvyšovat, dokud x 3 , x 4 , x 5 , x 6 nezůstanou nezáporné.

x 1 = min(19/2;13/2;∞;18/3)=6

To znamená, že když x 1 =6, x 6 =0, tedy x 1 jde do počtu základních a x 6 jde do počtu volných.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 = 13-2 (6-1/3 x 6)- x 2 = 1+2/3 x 6 - x 2

F(x2; x 6) = 42-7/3 x 6 + 5 x 2

S daným referenčním plánem (6;0;7;1;15;0) x 2 převod z volných na základní proměnné:

x 2 = min (∞; 7/3; 1/11; 15/3) = 1

Express x 2 až x 4

x 2 = 1 + 2/3 x 6 - x 4

Neznámé proměnné a účelovou funkci vyjadřujeme pomocí volných proměnných:

x 3 = 7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5 (1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 je kladné, proto jej lze zvýšit

x 6 = min(18;∞;3;6)=1

x 4 = 4/3-4/9 x 6 - 1/3 x 3

F=47+x 6-5(4/3-4/9-1/3x 3)

V účelové funkci jsou všechny koeficienty proměnných záporné, hodnotu funkce nelze zvýšit obdobně zbylé proměnné, najdeme referenční plán, ze kterého určíme x 1, x 2.

1. Průnik uzavřených množin, množina netriviálních omezení.

2. Množina řešení soustavy lineárních nestriktních nerovnic a rovnic je uzavřena.

αX=(αx 1 ,x 2 ,…, αx n)

X+Y=(x 1 + y 1, x 2 + y 2,… x n + y n)

Lineární souřadnice X 1 ,X 2 ,…X n se nazývají bod P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Sada P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 pro i= 1,…k n åR i =1, 1≤ i ≤k konvexní lineární kombinace bodů x 1 ,x 2,…x n. Pokud k=2, pak se tato množina nazývá segment. X 1,X 2 – konce segmentu. Rohový bod uzavřené množiny je bod, který není netriviální lineární kombinací bodů v množině (rohový bod).

Netriviálnost znamená, že alespoň jedno z λ se liší od 0 nebo 1.

Jakékoli referenční řešení problému lineárního programování je rohovým bodem oblasti možných řešení.

Pokud má problém lineárního programování jedinečné řešení, pak leží mezi rohovými body ODP. A pokud existuje více než jedno řešení, pak mezi řešeními je několik úhlových, takže množina všech řešení je jejich konvexní lineární kombinací.

Simplexová metoda spočívá v tom, že se nejprve najde určité referenční řešení problému (počáteční referenční plán) a poté se cíleně přechází od jednoho referenčního plánu k druhému a hledá se optimální plán. Pokud je jich několik, najdou se všechna rohová a množina řešení je reprezentována jako jejich lineární kombinace.

Přechod na nový referenční plán

F1 = F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 lze prokázat, kde υ k je výše uvažované minimum, které se určí zavedením k-té proměnné do základu, a Δ k =åс j x j ( 1) -С k, kde n ≤ j ≤ 1, X 1 = (x 1 (1) ;x 2 (1) ;…x n (1)) je odhad k-té proměnné , takže pokud je vyřešen maximální problém, pak hodnota ΔF 2 musí být kladná, Δk musí být záporná. Při řešení minimálních úloh je ΔF 2 záporné, Δ k kladné. Tyto hodnoty jsou vypočteny a pokud mezi ΔF 2 nejsou všechny hodnoty kladné, pak při řešení problémů na minimu je opak pravdou. Pokud je při řešení pro maximum mezi ΔF 2 několik kladných, pak do báze zavedeme vektor, při kterém tato hodnota dosáhne maxima, a pokud je problém vyřešen pro minimum a mezi ΔF 2 je několik záporných jedničky, pak vektor s nejnižší hodnotaΔF 2, tedy s největší absolutní hodnotou. Při splnění těchto podmínek je zaručena největší možná změna hodnoty funkce.

Řešení problému bude jedinečné, pokud pro libovolné vektory x k nezahrnuté v bázi odhadne Δ k ≠0, pokud alespoň jeden z těchto Δ k = 0, pak řešení není jedinečné, pro nalezení jiného řešení přejdeme k jiný referenční plán, včetně základu x k, kde Δ k =0. Prohledáním všech takových podpůrných řešení se z nich vytvoří lineární kombinace, která bude řešením problému.

Pokud pro nějaké nějaké Δ k koeficienty pro proměnnou x k ≤ 0 odporují podmínce optimality, pak systém omezení není omezen, tzn. optimální plán neexistuje.

Duální problém

Duální problém (DP) je pomocný problém lineárního programování formulovaný pomocí určitých pravidel přímo z podmínek přímé úlohy. Zájem o určení optimálního řešení přímého problému řešením jeho duálního problému je způsoben tím, že výpočty při řešení DP se mohou ukázat jako méně složité než při řešení přímého problému (DP). Složitost výpočtů, kdy rozhodnutí PPP závisí spíše na počtu omezení než na počtu proměnných. Chcete-li přejít na dálkové ovládání, je nutné, aby technické znalosti byly napsány standardně kanonická forma. Při prezentaci PP ve standardní podobě zahrnují proměnné x j také redundantní a reziduální proměnné.

Duální problém má:

1. m proměnných odpovídajících počtu omezení přímého problému;

2. n omezení odpovídajících počtu proměnných přímé úlohy.

Duální problém se získá symetrickou strukturální transformací podmínek přímé úlohy podle následujících pravidel:

· Každé omezení b i PD odpovídá proměnné y i PD;

· Každá proměnná x j PD odpovídá omezení C j PD;

· Koeficienty pro x j v omezeních PD se stanou koeficienty levé strany příslušného omezení PD;

· Koeficienty Cj pro xj v cílové funkci PD se stanou konstantními na pravé straně omezení PD;

· Omezující konstanty b i PD se stávají koeficienty cílové funkce PD.

Zvažte následující dva problémy:

F = С 1 x 1 +С 2 x 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 x 1 + b 2 x 2 +... +b n x n →min

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

. . . . . . . . . . . . . . . . . . . . . . .

a 1 n y n + a 2 m y n + ... + a nm y n ≤ C n

V tomhle práce v kurzu byly položeny základy matematické metodyřešení problémů lineárního programování. Proto více pozornosti byla věnována následujícím sekcím:

1. Základy matematických metod a jejich aplikace;

2. Řešení úloh simplexovou metodou.

MODIFIKOVANÁ SIMPLEXNÍ METODA Simplexová metoda není nejúčinnější
počítačový postup, protože počítá a
ukládá informace, které nejsou potřebné pro aktuální
iteraci a nelze je vůbec použít
rozhodování během následujících iterací. Pro
koeficienty nehlavních proměnných v rovnici
(0), koeficienty zavedených hlavních proměnných
v jiných rovnicích a pravé strany rovnic at
Každá iterace používá pouze tu relevantní
informace. Proto je potřeba takový postup
mohou tyto informace získat efektivně, bez
výpočty a uložení všech ostatních koeficientů
(toto je modifikovaná simplexová metoda).

Vypočítává a ukládá pouze informace
nutné pro momentálně a důležitá data
přenáší v kompaktnější podobě.
Používá maticové operace, takže
je nutné problém popsat pomocí matic.
VELKÁ písmena, zvýrazněná tučně
představují matice, velká písmena,
tučně vytištěné představují
vektory.
Kurzíva jsou skalární veličiny, zvýrazněné nulou
(0) označuje nulový vektor (jeho prvky jsou stejné
nula, řádky i sloupce, nula (0)
představuje normální číslo 0. Pomocí
matrice standardní formulář lineární modely
programování má podobu:

Maximalizovat Z = c x,
podle
A x ≤ b a x ≥ 0,
kde c je řádkový vektor
x, b a 0 sloupcové vektory

A - matice
U rozšířeného formuláře sloupcový vektor
fiktivní proměnné:
Omezení:
I = (m × m matice identity)
0 = (n + m prvků nulového vektoru)

Hledání základny proveditelné řešení
Obecným přístupem simplexové metody je získat
sled zlepšování OA řešení až
dokud se nenajde ten optimální
řešení. Jedna z klíčových vlastností
modifikovaná simplexová metoda - jak na to
najde nové řešení OD po jeho definování
hlavní (základní) a nezákladní (nezákladní)
proměnné. Vzhledem k těmto proměnným je výsledná
hlavní řešení – řešení m rovnic
Ve kterých n nebázických proměnných z n + m
prvky
jsou nastaveny na nulu.

Odstranění těchto n proměnných jejich nastavením na nulu,
získáme soustavu rovnic m s m proměnnými
(hlavní (základní) proměnné):
kde je vektor základních proměnných:
získané vyloučením nezákladního (nezákladního)
proměnné:

A základní matice
Výsledek získaný vyloučením odpovídajících sloupců
koeficienty nezákladních proměnných z .
(Kromě toho jsou prvky xB a sloupce B odlišné
Dobře). Simplexová metoda zavádí pouze základní
proměnné takové, že B je nedegenerované, tak
inverzní matice B-1 bude vždy existovat.
K vyřešení B x B = b se obě strany vynásobí B-1:
B-1 B x B = B-1 b.

cB je vektor, jehož prvky jsou koeficienty
objektivní funkce (včetně nul pro figurínu
proměnné) pro odpovídající prvky xB.
Cílová funkce pro toto základní řešení je:

Příklad:
- Iterace 0
tak
tak

10.

- Iterace 1
tak
tak

11.

- Iterace 2
tak
tak

12. Maticový tvar pro aktuální soustavu rovnic

Maticový tvar pro sadu rovnic,
objevující se v simplexní tabulce pro jakoukoli iteraci
původní simplexová metoda. Pro zdrojový systém
rovnice, tvar matice je:
Algebraické operace prováděné simplexovou metodou (rovnici vynásobte konstantou a přidejte
součin jedné rovnice druhou) jsou vyjádřeny v
maticová forma, po vynásobení obou částí
původní soustavu rovnic na odpovídající
matrice

13.

14.

Tato matice bude mít stejné prvky jako matice identity
matice, kromě toho, že každý produkt
pro určitou algebraickou operaci to bude trvat
prostor potřebný k provedení této operace,
pomocí maticového násobení. I po sérii
algebraické operace v několika iteracích,
stále můžeme dojít k závěru, že tato matice
by mělo být pro celou sérii s využitím toho, o čem víme
pravá strana nový systém rovnic. Po nějakém
iterací, xB = B-1b a Z = cB B-1b, tedy pravé strany
nový systém rovnic dostal podobu

15.

Protože provádíme stejnou sérii
algebraické operace s oběma stranami
originální sada, pro znásobení pravého a
na levé straně používáme stejnou matici.
Proto,
Požadovaný maticový tvar soustavy rovnic
po jakékoli iteraci:

16.

Příklad: maticová forma získaná po iteraci 2
pro problém sklárny pomocí B-1 a cB:

17.

Pomocí veličin xB = B-1 b a Z = cB B-1 b:

18.

Pro výpočet je třeba obdržet pouze B-1
všechna čísla simplexní tabulky z originálu
parametry úlohy (A, b, cB). Kterékoli z těchto čísel
lze získat jednotlivě jako
Zpravidla se provádí pouze vektorové násobení
(jeden řádek na sloupec) místo plné
násobení matice. Požadovaná čísla pro
provádění iterací simplexové metody může být
přijímat podle potřeby bez utrácení
zbytečné výpočty, abyste získali všechna čísla.

19. Stručný přehled modifikované simplexové metody

1. Inicializace: Stejně jako v původní simplex metoda.
2. Iterace: Krok 1 Určete zadaný základní (hlavní)
proměnné: Stejně jako v původní simplexové metodě.
Krok 2 Určete odchozí základní proměnné: Stejně jako v originále
simplexovou metodou, s výjimkou počítání pouze těch nezbytných pro
těchto čísel [koeficienty zavedených základních proměnných v
každá rovnice kromě rov. (0) a poté pro každou přísně
kladný koeficient pravá strana tato rovnice].
Krok 3 Určete nové řešení OD: Získejte B-1 a nastavte xB=B-1b.
3. Analýza optimality: Stejně jako v původní simplexové metodě, pro
kromě počítání pouze čísel nezbytných pro tuto analýzu,
tj. koeficienty nezákladních (nezákladních) proměnných v
Rovnice (0).
V kroku 3 iterace lze B-1 získat pokaždé pomocí
norma počítačový program pro obrácení (inverzi)
matrice. Protože B (pak B-1) se z jedné iterace do změní jen málo
jiný je efektivnější získat nový B-1 (označený B-1 nový).
B-1 v předchozí iteraci (B-1 starý). (Pro původní řešení OA).

Základní myšlenkou modifikované simplexové metody je použít aktuální inverzní matici (a původní data problému) k provedení výpočtů nezbytných k určení proměnných, které mají být zahrnuty a vyloučeny. Reprezentace inverzní matice v multiplikativní formě vám umožňuje vypočítat sekvenci inverzních matic přímo ze zdrojových dat bez použití vícenásobných inverzních operací pro každý základ. Stejně jako v obvyklé simplexové metodě je v tomto případě výchozím základem vždy matice identity I, jejíž inverzní je tato matice samotná. Proto pokud
- posloupnost inverzních matic odpovídajících iteracím 1, 2,…,i, a
je posloupnost jim odpovídajících matic

Posloupnost substitucí vede k následujícímu vzorci:

(2.23)

Je třeba zdůraznit, že multiplikativní reprezentace inverzní matice není nezbytný postup implementovat výpočetní schéma modifikované simplexové metody a při každé iteraci můžete použít kteroukoli z metod pro invertování aktuální báze. Při použití modifikované simplexové metody je důležité, aby byly inverzní matice počítány způsobem, který snižuje dopad chyb strojového zaokrouhlování.

Kroky algoritmu modifikované simplexové metody jsou v podstatě stejné jako kroky konvenčního algoritmu simplexové metody. Po nalezení počáteční základ I, je určen odpovídající vektor koeficientů účelové funkce , jehož prvky se tvoří v závislosti na tom, zda jsou výchozí základní proměnné reziduální (nadbytečné) nebo umělé.

1. 2.7.2. Multiplikativní reprezentace inverzní matice

V multiplikativní reprezentaci inverzní matice se operace maticové algebry používá k výpočtu prvků matice inverzních k nové matici bázových vektorů ze známé inverzní matice předchozí báze za předpokladu, že se obě uvažované báze liší pouze jeden sloupcový vektor. Tato metoda reprezentace inverzní matice je vhodná pro použití ve výpočetním schématu simplexové metody, protože báze odpovídající každé dvěma po sobě jdoucím iteracím se liší pouze v jednom sloupci (v důsledku nahrazení eliminovaného sloupcového vektoru aktuální báze s novým sloupcovým vektorem). Jinými slovy, aktuální základní matice a novou základní matici
, odpovídající další iteraci, se liší pouze v jednom sloupci. S multiplikativní reprezentací inverzní matice
odpovídající novému základu, vypočítá se vynásobením převrácené hodnoty aktuální matice vlevo
do matice vytvořené podle určitých pravidel .

Pojďme definovat matici identity následovně:

(2.24)

Kde - jednotkový sloupcový vektor s i-tým prvkem, rovný jedné a zbývající prvky se rovnají nule. Předpokládejme, že matice jsou známé A
a vektor matrice je nahrazen novým vektorem ; jak je zvykem při popisu simplexové metody, vektor je definován jako zahrnutý v základu a vektoru - jako vyloučené ze základu. Pro zjednodušení zápisu matematických vztahů použijeme následující definici
,ve stejnou dobu bude představovat k-tý prvek
. Pak nový inverzní matice
lze vypočítat pomocí následujícího vzorce:

(2.25)

pokud
. Li
, matrice
neexistuje. Všimněte si, že matice získané z matrice nahrazením jeho r-tého sloupcového vektoru sloupec .

Pojďme si vysvětlit výpočty a i, j¢ pomocí „pravidla obdélníku“. Je nutné vzít povolovací prvek ak, s a mentálně jej spojte s koeficientem, jehož novou hodnotu chcete najít. Tento řádek je třeba vzít v úvahu hlavní úhlopříčka, je na něm postaven obdélník, jehož strany jsou řádky a sloupce. Do obdélníku je potřeba nakreslit sekundární úhlopříčku, pak bude hodnota nového koeficientu rovna jeho původní hodnotě, od které se odečte součin prvků umístěných na vedlejší diagonále dělený rozlišovacím prvkem. Vysvětleme tyto akce na diagramu (obr. 1.9). Před vyplněním simplexové tabulky by měly být původní rovnice uvedeny ve tvaru (1.21).

	a k,j
			a i,j

Podívejme se na podstatu transformací simplexové metody pomocí příkladu 1.4. Připomeňme si omezující nerovnosti a účelovou funkci z tohoto příkladu a najdeme max objektivní funkce pomocí výše uvedené metody:

F = 908 x 1 + 676 x 2 ® max.

X 1 + X 2 14,

X 2 10,

10 x 1 + 8 x 2 120,

7 x 1 + 5 x 2 70,

4X 1 + 2X 2 28,

.

Pojďme to transformovat do kanonické podoby zavedením dalších proměnných Xj 0 a přeměnu nerovností na rovnost. Je třeba poznamenat, že pokud je v nerovnosti znaménko „“, pak s volnou proměnnou píší „-“, jinak - „+“:

X 1 + X 2 = 14 - X 3,

X 2 = 10 - X 4,

10 x 1 + 8 x 2 = 120 - x 5,

7X 1 + 5 X 2 = 70 - X 6,

4X 1 + 2X 2 = 28 - X 7.

Chcete-li zahájit postup simplexové metody, musíte nejprve najít referenční řešení z množiny základních řešení výsledné soustavy rovnic. Když to vezmeme v úvahu, existují tři fáze řešení problémů pomocí simplexové metody:

Nalezení počátečního základního řešení a sestavení počáteční simplexní tabulky;

Stanovení přijatelného řešení;

Stanovení optimálního řešení.

1. etapa

Počáteční základní řešení systémy, které najdeme za předpokladu volných proměnných X 1 A X 2 .

Pak X 3 = 14 - X 1 - X 2,

X 4 = 10 - X 2,

X 5 = 120 – 10 X 1 – 8 X 2,

X 6 = 70 – 10 X 1 – 5 X 2,

X 7 = 28 - 4X 1 - 2X 2,

F = 908 x 1 + 676 x 2 = 0.

Převedeme tyto rovnice na normálně vypadající:

X 3 = 14 - (X 1 + X 2),

X 4 = 10 - (0 X 1 + X 2),

X 5 = 120 - (10X 1 + 8X 2),

X 6 = 70 - (7X 1 + 5X 2),

X 7 = 10 - (4X 1 + 2X 2),

F = 0 + 908 x 1 + 676 x 2.

Výslednou soustavu rovnic zapíšeme do tvaru původní simplexové tabulky (tab. 1.9). V tabulce 1.9 neexistují žádné negativní volné podmínky. V důsledku toho jsme získali podpůrné (přípustné) řešení, protože přípustným řešením je jakékoli nezáporné řešení (pro které > 0 ), ale není to optimální.

Je zřejmé, že pokud pro všechny neznámé v účelové funkci F Pokud by byly kladné koeficienty, pak by toho bylo dosaženo maximální hodnota F. Z toho vyplývá znak optimálnosti přípustného řešení: PROTI F- řádek simplexní tabulky by neměl mít záporné koeficienty.

Tabulka 1.9

Základní proměnné X b	Volný člen	Volné proměnné
X 1	X 2
X 3
X 4
X 5
X 6
X 7
F		- 908	- 676

2. etapa

Připomeňme, že hlavní operací simplexové metody je v podstatě to, že některá základní proměnná je nahrazena volnou proměnnou . V tomto případě se operace výměny provádí za následujících podmínek:

Hodnota objektivní funkce F nové referenční (přípustné) řešení musí být větší než předchozí;

Nové řešení systému musí být rovněž referenční (přípustné).

V našem příkladu je první podmínka splněna, pokud je aktivační prvek kladný a je vybrán ve sloupci záporný koeficient F-čáry.

Druhá podmínka je splněna, pokud je rozlišovací prvek nalezen jako minimální kladný poměr prvků sloupce volných členů k odpovídajícím prvkům rozlišovacího sloupce.

Podle výše uvedeného pravidla se pro nalezení přípustného řešení prohodí základní a volné proměnné. Chcete-li to provést, najděte rozlišovací prvek (je zarámován v tabulce 1.9). V našem případě by měl být permisivní sloupec X 1 , takže X 2. Dělení volných proměnných jejich odpovídajícími hodnotami X 1 A X 2 (kromě linky F), najdeme nejmenší kladnou hodnotu. Je důležité poznamenat, že pro sloupec X 1 :

Je důležité poznamenat, že pro sloupec X 2:

Nejnižší poměr 28/4 definuje povolovací řádek a povolovací sloupec a průsečík povolovacího sloupce a povolovacího řádku je povolovacím prvkem a ks= 4. V tabulce. 1.9 označíme povolovací sloupec a povolovací řádek šipkami (®). Po určení a ks sestavte následující tabulku, ve které jsou proměnné zahrnuté v řádku a sloupci rozlišovacího prvku prohozeny ᴛ.ᴇ. převést základní proměnné na volné a volné na základní.

V našem příkladu vyměníme proměnné X 7 A X 1 , uvedeno v tabulce. 1,9 šipky. Koeficienty nové tabulky. 1,10 se zjistí z koeficientů staré tabulky. 1.9 za použití výrazů uvedených v tabulce. 1.8 a „pravidlo obdélníku“. V tabulce 1.10 opět nemáme optimální řešení.

Tabulka 1.10

Základní proměnné X b

Volný člen B

Volné proměnné

X 7

X 2

X 3

- 1/4

1/2

X 4

X 5

-5/2

X 6

-7/4

3/2

X 1

1/4

1/2

F

-222

Podle pravidel popsaných výše v tabulce. 1.10 najdeme rozlišovací prvek 1 a sestavíme novou tabulku. 1.11 nahrazením základny ( X 4 A X 2). Zvláště zdůrazňujeme, že pro nalezení rozlišovacího prvku musíme zvolit nejmenší kladnou hodnotu, ᴛ.ᴇ. Negativní vztahy volných členů ke koeficientům sloupce rozlišení neuvažujeme.

3. etapa

Pojďme zkontrolovat, zda je nalezené řešení optimální a pro náš příklad maximální. K tomu budeme analyzovat účelovou funkci F: F = 8576 + 227 X 7 + 222 X 4.

Účelová funkce neobsahuje záporné koeficienty a má nejvyšší hodnotu V poslední tabulce jsme získali optimální řešení:

X3 = 2; X2 = 10; X5 = 20; X6 = 6; Xi = 2; X7 = X4 = 0;

Fmax = 8576.

Upozorňujeme, že výsledky řešení simplexové metody a grafické metody jsou stejné.

V souladu s uvažovanou posloupností musí mít algoritmus simplexové metody další bloky:

1. Nalezení výchozího základního (referenčního) řešení a sestavení výchozí tabulky.

2. Nalezení rozlišovacího prvku a ks(nalezení záporného volného termínu - b i < 0 и минимального отношенияb i / a ij; Pokud v řádku záporného volného členu nejsou žádné záporné koeficienty, pak je problém neřešitelný).

3. Přepočet nový stůl podle vzorců v tabulce. 1.8.

4. Kontrola přítomnosti negativního volného termínu. Pokud existuje, pokračujte krokem 2. Nepřítomnost záporného volného členu znamená, že bylo získáno podpůrné (přípustné) řešení.

5. Podobně jako v krocích 2 - 4 se tabulka přepočítává při hledání optimálního řešení.

Řešení úlohy LP simplexovou metodou v maticovém tvaru

Nutné minimalizovat ,

pod omezeními

v " x³ 0.

Pojďme si představit vektory:

C= (C1, ..., Cn) - stupeň vektor,

X= (X 1 , ... , X n) - vektor proměnných,

b= (B 1 , ... , B m) - vektor omezení

a matrice

A=

velikost (mn) - matice omezujících koeficientů.

Pak bude mít problém LP následující výklad:

minimalizovat F=CX

za podmínek AX = b, X 0.

Tento problém lze zapsat v maticovém tvaru:

Představme si notaci:

A * = - tady je matrice A* velikost (m+1) (n+1).

Podle výše uvedeného způsobu je nalezen rozlišovací prvek a ks.

Dalším krokem simplexové metody je Gaussova eliminační procedura, která umožňuje zadávat všechny koeficienty s- m sloupec, kromě a ks, nula, a ks- rovná se jedné.

Je důležité poznamenat, že pro simplexovou metodu v maticovém tvaru je iterace simplexové metody ekvivalentní vynásobení maticové rovnice vlevo následujícím čtvercová matice:

(1.23)

, Kde k 0; s 0.

Pokud všechny sloupce matice A rozdělit na základní B a nezákladní N, pak lze problém LP zapsat následovně:

,

Kde Cb A C N- odpovídající vektorové složky C, Xb, X N- základní a nezákladní proměnné.

Chcete-li vybrat počáteční základní proměnné x b měli byste vynásobit rovnici vlevo maticí:

Kde R= CbB-1.

V důsledku toho dostáváme

,

Kde já- matice identity.

Z toho vyplývá, že relativní odhady pro nezákladní proměnné

c j = c j - C b B - 1 a j = c j - Ra j.

Báze bude přípustná, pokud volné členy základních proměnných jsou nezáporné, ᴛ.ᴇ. B -1 b ³ 0.

V případě c j³ 0 pro , pak základem je optimální řešení problému. Vektor se nazývá vektor aktuální ceny. Každý řádek je vynásoben vektorem R a je odečtena od linie nákladových koeficientů, aby se eliminovaly nákladové koeficienty pro základní proměnné.

Pokud problém LP není uveden v kanonické formě, ᴛ.ᴇ.

minimalizovat F=CX

za podmínek AX b , X 0,

poté, po zavedení slabých proměnných, mohou být zapsány ve tvaru

Metoda eliminace řádků pro matici je ekvivalentní vynásobení této matice zleva B-1, Kde B- podmaticový základ A, Pak

,

ᴛ.ᴇ. matice získaná místo matice identity já, bude inverzní matice pro aktuální základ. Relativní hodnocení uvedená výše matice identity, vůle

,

protože jsou jednotkové vektory.

Protože F= CbB-1b = Rb, aktuální hodnota účelové funkce je rovna součinu vektoru běžných cen matice A na původní vektor b.

Příklad.
Publikováno na ref.rf
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5® min

pod omezeními

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10 ,

3X 2 + 3X 4 + 6X 5 = 9,

.

Pro tento příklad matice A* bude vypadat

.

Nechat X 1 A X 2- základní proměnné.

Matice B vypadá jako

.

Pak inverzní matice B-1 má další pohled

.

Připomeňme vám to , kde adjungovaná matice složená z algebraických doplňků prvků b ik determinant matice B.

Determinant se rovná:

= .

Proto matrice B není zvláštní.

Algebraické sčítání prvky determinantu mají následující význam:

b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2; těch . .

Vynásobením číslem najdeme inverzní matici:

.

Vektor aktuálních cen bude

R = CbB-1 = = .

Připomeňme vám to Cb- základní vektorové složky C:

Pak = .

K výběru počátečního základu potřebujete matici A* vlevo násobit maticí

=

.

Rozlišovací prvek je ve čtverci.

Iterace simplexové metody je ekvivalentní výsledné tabulce vynásobené zleva následující matrice:

.

Tato matice je získána z matice (1.23)

Zde aks = 2;

a11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;

a13 = 0; a21 = 0; a 22 = 1/ a ks = 1/2; a23 = 0;

a31 = 0; a32 = - a ms/aks = -1/2; a 33 = 1.

Pak máme

=

(1.24)

Rozlišovací prvek je umístěn ve čtverci.

Další iterace simplexové metody je ekvivalentní levému násobení maticí

.

=

.

Proto, Fmin =11; X 4=7/3; X 5=1/3; X 1 = X 2 = X 3=0.

Upravená simplexní metoda (MSM) odlišná od běžné simplexové metody (CM) protože v CM Všechny prvky simplexních tabulek se při každé iteraci přepočítávají a při získání další tabulky se všechny předchozí tabulky, včetně té původní, neuloží. V MSM původní tabulka se uloží a při každé iteraci se určí následující: řádek relativních odhadů C zadané do základu a aktuální hodnotu vektoru pravých stran vazeb. Aby bylo možné určit všechny prvky tabulky po j- iteraci CM, stačí znát matici B-1, odpovídající této tabulce, původní matice a indexy aktuálních základních proměnných. Potom aktuální vektor R = CbB-1(indexy aktuálních základních proměnných určují, které prvky vektoru odhadů ze zdrojové tabulky jsou do vektoru zahrnuty C b); =B-1 b, Kde b je převzat z původní tabulky a libovolný sloupec nové tabulky = B-1A j , Kde A j - sloupec zdrojové tabulky.

Nechť je nyní uvedena zdrojová tabulka B-1, odpovídající tabulce i iteraci. Za účelem získání matrice B-1, odpovídající (i+1)- iteraci, musíte definovat nezákladní sloupec i tabulky, která by měla být vložena do základu. Z CM z toho vyplývá, že musí být zapsáno do základu pokud Cj<0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить C j Pro i th tabulky, vyberte si z nich<0, а затем вычислить

A S = B-1 a = B-1 b (= Cj - Ra j ).

Po nalezení rozlišovacího prvku a pomocí prvků vektorů a najdeme matici B-1 pro následující tabulku.

Příklad. Použití modifikované simplexové metody k minimalizaci

F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min

s omezeními:

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

Výběr jako základní proměnné X 1 A X 2, dostali jsme následující úkol: F = 43 - 9/2X 3 - 12X 4 - 12X 5