Domov › Sazby › Simplexní metoda pro řešení úloh lineárního programování. Vybereme prvek aij z j-tého sloupce, který obsahuje kladné prvky. Geometrická metoda řešení úloh LP

Simplexní metoda pro řešení úloh lineárního programování. Vybereme prvek aij z j-tého sloupce, který obsahuje kladné prvky. Geometrická metoda řešení úloh LP

Simplexní metoda

1. Myšlenka simplexové metody

Uvažujme univerzální metodařešení kanonického problému LP.

známá jako simplexová metoda.

Jak bylo stanoveno v kapitole 2, množina plánů pro kanonický problém je konvexní mnohostěnná množina s konečným počtem rohových bodů. A pokud má tento problém optimální řešení, pak je dosaženo alespoň v jednom rohovém bodě.

Jakýkoli rohový bod je spojen se základním plánem problému, ve kterém jsou proměnné rovny nule a zbývající proměnné odpovídají lineárně nezávislé sloupce matice podmínek. Tyto lineárně nezávislé sloupce tvoří nesingulární základní matici.

Iterace přes všechny rohové body je výpočetně nákladná, a proto neefektivní. V roce 1944 navrhl J. Dantzig uspořádaný postup výčtu rohových bodů, ve kterém se optimální řešení stačí prozkoumat jen malou část z nich. Tento postup se nazývá simplexní metoda.

J. Dantzig navrhl nahradit pouze jeden vektor v základní matici při pohybu z jednoho extrémního bodu do druhého. To znamená, že při takovém přechodu musíme vyloučit jednu ze základních proměnných - učinit ji nezákladní (rovnou se nule) a místo ní zavést novou proměnnou z nebázických (nula) - učinit ji základní (pozitivní ).

Ukazuje se, že geometricky taková náhrada vede k přechodu z jednoho rohového bodu do sousedního (sousedního) spojeného s předchozí bod společný okraj.

Ze všech sousedních bodů je vybrán ten, ve kterém se účelová funkce zvyšuje nejvíce. Protože počet rohových bodů je konečný, přes konečný počet přechodů vrchol nejvyšší hodnotu Objektivní funkce nebo bude objektivní funkce stanovena jako neomezená na neomezený soubor plánů.

Obecné schéma Simplexová metoda se skládá z následujících základních kroků.

· 0 kroku. Definice počáteční základ a odpovídající počáteční rohový bod (baseline).

· 1 krok. Kontrola optimálnosti aktuálního základního plánu. Pokud je splněno kritérium optimality, pak je plán optimální a řešení je hotové. v opačném případě přejděte ke kroku 2.

· Krok 2. Hledání proměnné zavedená do základních. (Z podmínky zvýšení účelové funkce).

· Krok 3. Nalezení proměnné vyloučené ze základních proměnných (Z podmínky zachování omezení problému).

· Krok 4. Zjištění souřadnic nové účaří (sousední rohový bod). Přejděte ke kroku 1.

Opakované kroky 1-4 tvoří jednu iteraci simplexové metody.

Z tohoto diagramu vyplývá, že za prvé, abyste mohli začít s simplexovou metodou, musíte mít nějaký rohový bod - počáteční základní plán, a za druhé musíte být schopni prozkoumat aktuální rohový bod z hlediska optimálnosti, aniž byste museli počítat všechny sousední vrcholy. Tyto problémy lze snadno vyřešit, pokud má kanonický problém LP nějakou speciální formu.

Definice. Řekneme, že kanonický problém LP má „preferovanou formu“, jestliže

1.pravé strany rovnic, .

Matice podmínek obsahuje jednotkovou podmatici velikosti

Jinými slovy, v každé rovnici je proměnná s koeficientem rovný jedné, v ostatních rovnicích chybí. Podmínka 1 není zatěžující, protože v případě záporné pravé strany nějaké rovnice ji stačí vynásobit (-1). V preferenčním typu problému je nalezení počáteční základní linie velmi jednoduché.

Příklad .

Matice podmínek a vektor pravých stran omezení mají tvar

Jedna základní matice je okamžitě zřejmá: s jednotkovými vektory

V důsledku toho jsou základní proměnné a x2, x4 jsou nezákladní. Za předpokladu x2=x4 =0 v soustavě rovnic okamžitě najdeme x1 =10, x3 =20, x5 =8. Vidíme, že hodnoty základních proměnných se rovnají pravým stranám omezení. Z toho jasně vyplývá požadavek, aby pravé strany bi byly kladné.

V budoucnu budeme základní proměnné kombinovat do vektoru XB.

V kanonickém problému upřednostňovaného tvaru je tedy jednotková podmatice AB =E brána jako počáteční základní matice a odpovídající základní proměnné se rovnají pravým stranám omezení: xB =b.

. Nejjednodušší implementace simplexní metoda

Nejjednodušší implementace simplexové metody („jednoduchá C-metoda“) je aplikována na kanonický problém LP, který má „preferovanou formu“. Bez ztráty obecnosti budeme předpokládat, že podmatice identity je obsažena v prvních m sloupcích. Potom bude kanonický problém zapsán následovně

f(x) = c 1X 1+c 2X 2+… + c m X m +c m+1 X m+1 +… + c n X n max(3,1)x 1+ a 1m+1 X m+1 + … + a 1n X n = b 1(3,2)x 2+ a 2m+1 X m+1 + … + a 2n X n = b 2………………………………………………………….X m + a mm+1 X m+1 + … + a mn X n = b m X j ³ 0, j=1,2,…, n.(3,3)

Matice stavu

obsahuje v prvních m sloupcích jednotkovou podmatici o velikosti m x m, proto AB =(A1, A2,…, Am)=E.

Základní kroky simplexové metody (teorie)

Vzhledem k tomu, že jednotková základní matice je v prvních m sloupcích matice podmínek, prvních m souřadnic počátečního základního plánu je základních a posledních n - m souřadnic je nezákladních, tedy rovných nule:

o = (x1, x2,…, xm, 0,…, 0).

Dosazením souřadnic bodu xo do omezení (3.2) a zohledněním toho, že m+1 =... = xn = 0, dostaneme: x1 = b1, x2 = b2,..., xm = bm, že je, xoB = b.

Původní základní plán tedy vypadá takto:

xo = (b1,…, bm, 0,…, 0),

kde сБ = (с1,…, сm) je vektor složený z koeficientů účelové funkce pro základní proměnné.

1 krok.

Ze systému omezení (3.2) vyjádříme základní proměnné z hlediska nezákladních:

X 1= b 1 -A 1m+1 X m+1 - ... - a 1n X n, X 2= b 2- a 2m+1 X m+1 - ... - a 2n X n, ………………………………………… X m = b m - a mm+1 X m+1 - ... - amn X n, (3.4)

Dosadíme tyto výrazy do účelové funkce (3.1).

f(x)=c 1(b 1- a 1m+1 X m+1 - ... - a 1n X n) +c 2(b 2- a 2m+1 X m+1 - ... - a2n X n ) +

………………………………………………..

C m (b m - a mm+1 X m+1 - ... - a mn X n ) + c m+1 X m+1 +… +cn X n .

Seskupme termíny se stejnými nezákladními proměnnými:

f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1).xm+1 - …-

- (c 1 A 1n +c 2 A 2n + … + c m A mn - c n). X n. (3.5)

Všimněte si, že výrazy v závorkách lze zapsat jako

C 1 A 1m+1 +c 2 A 2m+1 + … + c m A mm+1 - c m+1 = < cB , A m+1 > - c m+1 = D m+1 ,

…………………………………………………………………………………………………………………………1 A 1n +c 2 A 2n + … + c m A mn - c n= < cB , A n > - c n= D n ,

kam s B = (s 1,…, S m ) je vektor složený z koeficientů účelové funkce pro základní proměnné A m+1 ,…, A n - sloupce matice podmínek A pro nebázické proměnné x m+1,…, x n .

Výrazy

D j = < сB , A j > - cj , j = m+1,…, n,(3,6)

se nazývají simplexní rozdíly nebo simplexní základní odhady.

S přihlédnutím k (3.6) lze vzorec (3.5) pro účelovou funkci přepsat do tvaru

Tento vzorec nám umožňuje získat znamení optimálnosti základního plánu. Pokud všechny simplexní odhady s nebázickými čísly D j ³ 0, pak je aktuální základní plán optimální.

Pokud je alespoň jeden odhad, například ?k, striktně záporný, pak přidělíme-li odpovídající nebázické proměnné xk kladnou hodnotu a zbývající nebázické proměnné plánu x položíme na nulu, získáme

f(x) = f(x Ó ) - D k X k =f(x Ó ) + | D k | X k > f(x Ó ),(3.7)

tedy v tomto případě plán x Ó by se dalo zlepšit.

Je snadné zkontrolovat, že simplexní odhady odpovídající sloupcům s jednotkovou bází jsou vždy rovny 0.

Krok 2. Nalezení proměnné zavedené do základních proměnných.

Jak vyplývá ze vzorce (3.7), účelovou funkci lze zvýšit zavedením nebázické proměnné x do bázových proměnných (učinit ji kladnou) j , což odpovídá negativnímu hodnocení? j < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную хNa s největším absolutním záporným odhadem, tedy takovým, pro který

kde D j =< CБ, Aj >- cj, j = m+1,…, n (počty nezákladních proměnných).

Tímto způsobem se dostaneme nový plán

x1 = (x1,…, xm,0,…, xk,…, 0,…, 0).

Ale x1 je nezákladní plán, protože počet kladných souřadnic je roven m+1, počet nulových souřadnic je roven n - m -1.

Abychom získali nový rohový bod, nastavíme jednu ze základních proměnných na nulu, to znamená, že jednu proměnnou ze základních odstraníme.

Krok 3

Dosadíme souřadnice bodu x1 do podmínek (3.4) a vezmeme v úvahu, že proměnné xj musí být nezáporné

X 1= b 1- a 1k X k ³ 0 x 2= b 2- a 2k X k ³ 0 …………………………. X m = b m - a mk xk ³ 0(3.8)

Ze vzorce (3.7) je zřejmé, že co větší hodnotu X Na > 0, tím více se zvyšuje účelová funkce. Pokusíme se najít maximální hodnota X Na , aniž by došlo k porušení omezení problému a splnění podmínek nezápornosti (3.8).

Nerovnosti (3.8) lze přepsat jako

A 1k X k £ b 1 A 2k X k £ b 2 ………………A mk X k £ b m (3.9)

Při řešení soustavy nerovnic (3.9) jsou možné dva případy: mezi koeficienty pro x Na žádné pozitivní: a ik £ 0, i=1,2,…, m. Protože b i > 0, pak jsou splněny nerovnosti (3.9) pro libovolné libovolné velká důležitost X Na. To naznačuje, že účelová funkce není omezena na množinu plánů (max f(x) ® ¥ ) a proto neexistuje žádné řešení úlohy LP.) mezi koeficienty pro x Na existují pozitivní a ik > 0. Řešením soustavy nerovnic (3.9) získáme:

X Na £ b i /A ik , pro všechny i pro které aik > 0.(3.10)

Největší hodnota x Na , splňující všechna omezení (3.10), se rovná nejmenšímu z poměrů na pravé straně těchto nerovností

X Na =min(b i /A ik ) pro všechny i: aik > 0.

Nechť je dosaženo minima při i = r, tedy x Na ? b r /A rk . To znamená, že základní proměnná x r za podmínek (3.8) zmizí.

X r = b r - a rk X k = b r - a rk (b r /archa ) = 0,1 r m.

Proměnná x r vyloučeno ze základu. Následně jsme získali nové složení základních a nebázických proměnných, lišících se od původní v jedné základní a jedné nebázické souřadnici.

Krok 4

Nová základní linie bude vypadat takto

1= (x 1, X 2,…, 0,…, x m , 0,…, xk ,0,…, 0),

kde na místě x r stojí nula a x Na > 0.tento základní plán odpovídá nové základní matici:

Pro nalezení souřadnic nového rohového bodu x1 je kanonický problém LP redukován na novou preferovanou formu, tedy na takovou formu, že se matice stane identitou (= E). K tomu je třeba sloupec Ak převést na reprezentaci jednotek,

R-tý řádek,

ve kterém koeficient = 1 a všechny ostatní prvky = 0, i ?r. Toho lze dosáhnout pomocí elementárních operací na rovnicích soustavy. Řešení končí, když pro určitý bod všechny odhady Dj ³ 0.

3. Implementace simplexové metody na příkladu

Ukažme si aplikaci simplexové metody na příkladu z kapitoly 2.

Uvažujme kanonický problém LP

f(x) = x 1+ 2x 2 +0 x 3 +0x 4max(3,11)-x 1+ 2x 2+x 3= 4,(3,12)3 x 1 +2x 2+x 4= 12,(3,13)x j? 0, j = 1,2,3,4.(3,14)

Matice podmínek A = (A 1, A 2, A 3, A 4), kde

Cílový vektor c =(c1, c2, c3, c4)=(1, 2, 0, 0); vektor pravých stran b=(b1, b2) = (4, 12).

0 kroku. Nalezení počátečního rohového bodu (baseline).

Úloha má výhodnější formu, protože pravé strany rovnic jsou kladné a sloupce matice podmínek A3, A4 tvoří jednotkovou podmatici. To znamená počáteční základní matice = (A3, A4); x3 a x4 jsou základní proměnné, x1 a x2 jsou nebázické proměnné, cB = (c3, c4) = (0, 0).

Počáteční základní linie vypadá takto

x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.

1 krok. Kontrola optimálnosti základního plánu.

Vypočítejme simplexní odhady pro nezákladní proměnné pomocí vzorce (3.6)

D1 =< cБ, A1 >- c1 = 0 ·(-1) + 0 ·3 - 1 = -1.

D2 =< cБ, A2 >- c2 = 0 · 2 + 0 · 2 - 2 = -2.

Protože jsou odhady záporné, plán xo není optimální. Budeme hledat novou účaří (sousední rohový bod) s větší hodnotou účelové funkce.

Krok 2. Nalezení proměnné zavedené do základu.

Cílovou funkci lze zvýšit, pokud je jedna z nebázických proměnných x1 nebo x2 zahrnuta do základních proměnných (kladná), protože oba odhady Dj< 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.

Krok 3 Definice proměnné odvozené od základu.

Po zadání proměnné x2 do základu bude mít nový plán tvar1 = (0, x2, x3, x4).

Tento plán není základní, protože obsahuje pouze jednu nulovou souřadnici, což znamená, že je nutné jednu z proměnných x3 nebo x4 nastavit na nulu (vyloučit ze základny).

Dosadíme souřadnice půdorysu x1 = (0, x2, x3, x4) do omezení problému. Dostaneme

Vyjádřeme odtud základní proměnné x3 a x4 přes proměnnou x2 zavedenou do základu.

X 3= 4-2x 2,(3,15)x 4= 12 - 2x2 .(3.16)

Takže proměnné x 3a x 4 musí být nezáporné, získáme systém nerovností

4-2x 2 ³ 0 ,(3,17)12 - 2x 2 ³ 0 .(3.18)

Jak větší hodnotu X 2, tím více se zvyšuje účelová funkce. Najděte maximální hodnotu nové bazické proměnné, která neporušuje omezení problému, tedy splňující podmínky (3.17), (3.18).

Přepišme nerovnosti do formuláře

x2 £ 4,

x2 £ 12,

kde je maximální hodnota x 2= min (4/2, 12/2) = 2. Dosazení této hodnoty do výrazů (3.15), (3.16) pro x 3a x 4, dostaneme x 3= 0. Proto x 3 odvozené od základu .

Krok 4Určení souřadnic nové základní linie.

Nová základní linie (sousední rohový bod) je:

X 1= (0, x2, 0.x 4).

Základ tohoto bodu tvoří sloupce A2 a A4, tedy = (A2, A4). Všimněte si, že tato báze není unitární, protože vektor A2 = (2, 2), a tudíž úloha (3.11) - (3.14) nemá vzhledem k nové bázi preferovaný tvar. Transformujme podmínky úlohy (3.12), (3.13) tak, aby měla preferovaný tvar vzhledem k novým základním proměnným x2, x4, tedy aby proměnná x2 byla zahrnuta do první rovnice s koeficientem roven jedné a není přítomen ve druhé rovnici. Přepišme rovnice úlohy

x1+ 2x2+ x3 = 4, (p1)

x1 +2x2 + x4 = 12. (p2)

Vydělme první rovnici koeficientem x2. Získáme novou rovnici = p1 / 2, ekvivalentní té původní

1/2 x1+ x2+ 1/2 x3 = 2. ()

Tuto rovnici, kterou nazýváme řešení, použijeme k odstranění proměnné x2 z druhé rovnice. Chcete-li to provést, musíte rovnici vynásobit 2 a odečíst ji od p2. Dostaneme rovnici = p2 - 2 = p2 - p1.

x1 – x3 + x4 = 8. ()

V důsledku toho jsme získali novou „preferovanou“ reprezentaci původního problému (3.11) - (3.14) s ohledem na nové základní proměnné x2, x4:

f(x) = x1+ 2x2 + 0 x3 + 0 x4® max

1/2 x1+ x2+ 1/2 x3 = 2. ()

x1 – x3 + x4 = 8. ()

xj ³ 0, j = 1,2,3,4.

Když zde nahradíme reprezentaci nového základního plánu x1 = (0, x2,0, x4), okamžitě najdeme jeho souřadnice, protože hodnoty základních proměnných se rovnají pravým stranám rovnic

x1 = (0,2,0,8); f(x1)=4.

Tím je dokončena první iterace simplexové metody. Dále proces řešení problému pokračuje od kroku 1, který spočívá v kontrole optimálnosti nalezeného plánu. Řešení končí, když se všechny simplexní odhady aktuálního základního plánu ukáží jako nezáporné.

Druhou iteraci neprovedeme podle schématu první, protože je pohodlnější provádět všechny výpočty simplexové metody v tabulková forma.

simplexní proměnná kanonické programování

Literatura

1. Ekonometrie: Učebnice / Ed. I.I. Eliseeva. - M.: Finance a statistika, 2002. - 344 s.: ill.

Workshop z ekonometrie: Proc. příspěvek / I.I. Eliseeva, S.V. Kurysheva, N.M. Gordeenko a další; Ed. I.I. Eliseeva. - M.: Finance a statistika, 2002. - 192 s.: ill.

Kremer N.Sh., Putko B.A. Ekonometrie: Učebnice pro vysoké školy. - M.: UNITY-DANA, 2002. - 311 s.

Magnus Y.R., Katyshev P.K., Peresetsky A.A. Ekonometrie. Počáteční kurz: učebnice. - M.: Delo, 2001. - 400 s.

Katyshev P.K., Magnus Y.R., Peresetsky A.A. Sbírka problémů pro počáteční kurz ekonometrie. - 3. vydání, rev. - M.: Delo, 2003. - 208 s.

Dougherty K. Úvod do ekonometrie. - M.: Finance a statistika, 1999.

Johnston J. Ekonometrické metody. - M.: Statistika, 1980.

Kane E. Ekonomická statistika a ekonometrie. Úvod do kvantitativní ekonomické analýzy. sv. 1. - M.: Statistika, 1977.

Lange O. Úvod do ekonometrie / Přel. z polštiny - M.: Pokrok, 1964.

Lizer S. Ekonometrické metody a problémy. - M.: Statistika, 1971.

Malenvo E. statistické metody ekonometrie. - M.: Statistika, 1976.

Tintner G. Úvod do ekonometrie. - M.: Finance a statistika, 1965.

Ayvazyan S.A., Mkhitaryan V.S. Aplikovaná statistika a základy ekonometrie: učebnice pro vysoké školy. - M.: UNITY, 1998.

Ventzel E.S. Teorie pravděpodobnosti: Učebnice pro vysoké školy. - 6. vyd. - M.: Vyšší. škola, 1999.

Simplexová metoda spočívá v nalezení a testování vrcholu (úhlu), který je řešením problému LP. V každé fázi metoda vybírá vrchol a jemu odpovídající proměnné, které zajišťují pohyb na minimum (maximum) s nejvyšší rychlost. Vybraná proměnná nahradí druhou, nejvíce omezující. Simplexová metoda také umožňuje určit, zda existuje řešení. Algoritmus implementující simplexovou metodu lze napsat jako:

Krok 1. Určí se určitý vrchol v ODR, odpovídající základním přípustným řešením (proměnným) nalezeným extrakcí z matice T- lineárně nezávislé sloupce a rovnající se nule všechny ostatní proměnné odpovídající ostatním sloupcům matice.

Krok 2. Vybráno ze všech zbývajících možných p - t hrany odpovídající nebázickým proměnným hrana (proměnná), která při pohybu po ní vede k nejrychlejšímu poklesu účelové funkce.

Krok 3 Je to, jako by byl proveden pohyb z počátečního vrcholu podél vybrané hrany do jiného vrcholu, což dává nové řešení, které má nižší hodnotu CF. Nový vrchol vzniká nahrazením základní proměnné (hrana) novou základní proměnnou (hrana).

Sloupce a prvky vektorů jsou obvykle uspořádány a zapsány ve formě simplexní tabulky, jejíž vytvoření bude ukázáno níže.

Simplexová metoda řeší problém LP v standardní forma.

Minimalizovat (maximalizovat) funkci za podmínek x > 0; Sekera = b.

Matrix A je skutečný a má rozměr T x "a pořadí T.

Formulovaný problém LP lze zapsat i ve formě

Na základě záznamu úlohy LP ve tvaru (8Л) můžeme říci, že rozšířená matice

rozměry (t + 1) (n + 2) odpovídá řešení[x/] t.

Představme si matici A jako množinu sloupců

Protože matice A má hodnost T, pak tam bude T lineárně nezávislé sloupce matice A, například (a V1 ,...,a V/i Uvažujme vektor x° > 0, takový, že všechny p - t prvky jsou 0 a Ax° = b. Nechť to jsou prvky s čísly..., i n _ m . Předpokládejme také, že umístění aw lineárně nezávislých sloupců matice A odpovídá umístění nenulových prvků ve vektorech 0. Geometricky to podle výroku 3 § 7.6 znamená, že x° je vrchol (úhel) ODR a navíc splňuje dané podmínky. Toto řešení se nazývá přípustné základní řešení.Úhly přípustné sady jsou přípustná základní řešení.

Připomeňme, že sada základních řešení obsahuje všechny informace potřebné pro optimální řešení úlohy LP. Pro dvourozměrný případ uvažovaný v § 7.6 jsou základními řešeními všech 6 bodů a přípustnými základními řešeními jsou body L, V, Si 0.

Jakýkoli vektor x podobný x° lze tedy zapsat jako

Kde x v- vektor, jehož prvky odpovídají lineárně nezávislým sloupcům matice A; xF - vektor s nulovými prvky.

Podobně definujme vektory

Proměnné, které jsou prvky vektoru x v, jsou nazývány základní proměnné a proměnné, které jsou prvky vektoru x F jsou nazývány volný, uvolnit (nezákladní) proměnné.

Protože x° F=0, pak bude hodnota účelové funkce pro počáteční vektor x° rovna

kde /° je hodnota / v bodě x°.

Zavolá se řešení (8.1) tvaru [x°/°]t pro x > 0 zřejmé (explicitní) řešení. Pokud tedy nastavíme nezákladní proměnné na nulu, dostaneme zřejmé řešení.

Pro pohodlí to přeuspořádejme T lineárně nezávislé sloupce matice A in levá strana a zapište matici do formuláře

Zde matice B odpovídá T lineárně nezávislé sloupce má rozměr tx t a hodnosti T, a matice F

je TX (p - t) matice. Protože se matice B skládá z lineárně nezávislých sloupců, má inverzní B -1 a detB φ 0. Všimněte si, že pro vytvoření matice B si můžete vybrat libovolnou T lineárně nezávislé sloupce matice A.

Představme si problém (8.1) s přihlédnutím k zavedenému zápisu

Tato reprezentace odpovídá rozšířené matici

odkud následuje

Pokud vektor x PROTI bude řešením soustavy Bx d = b, pak to bude základní řešení. Pokud nerovnost platí PROTI= B-1b > O, tedy x v bude přijatelné řešení.

Současné řešení tedy splňuje následující rovnici:

Uvažujme matici (8.4). Základní proměnné budou prezentovány v výslovně, nahradíme-li matici B identitní maticí I. Vynásobením prvního řádku matice (8.4) zleva B~ 1 dostaneme

kde B_1 b > O, tj. T horní prvky v pravém sloupci jsou nezáporné a představují aktuální hodnotu proměnných.

Na levé straně horního řádku se ukázalo matice identity: V -1 V = I. Tato prezentace velmi pohodlné, protože při násobení vektorem x v každá proměnná bude na samostatném řádku.

Základní řešení, které budeme považovat za přípustné a odpovídající bázi B, je tedy x m = [x v 0], kde x v == B_1 b. Základní řešení vyplývá z předpokladu, že x F = 0. Pokud však xF* 0, pak x^ lze vypočítat jako x 5 = = B~"b - B^"Fx/r. Dosazením tohoto výrazu do účelové funkce (nákladové funkce) získáme

Protože je nutné určit závislost nákladů na nezákladních proměnných, z nichž jedna je pak zahrnuta do základních, měl by být spodní řádek pod maticí I nulový. Za tímto účelem v (8.7) vynásobíme první řádek (matice) číslem od Pro a přidejte jej s druhým

kde je hodnota účelové funkce pro počáteční století

torus x 0 od (8.3).

Matice (8.8) se nazývá simplexní stůl. Přivést ji k tento druh je počáteční fáze simplexní algoritmus. Během provádění algoritmu se provádí přechod z jedné tabulky do druhé, dokud se pravý dolní prvek tabulky nestane maximem nebo minimem.

Pomocí simplexní tabulky je snadné vidět proveditelné řešení. Proměnné X F odpovídají nulové podmatici, proměnným x v- matice jednotek:

Předpokládejme, že úloha LP byla zredukována na standardní formu, byla vypočtena simplexová tabulka a bylo vybráno výchozí základní řešení odpovídající vrcholu mnohostěnu řešení.

Pak - řešení problému (8.1). Tak

jako b > Oh, to je základní přípustné řešení.

Představme si matici (8.9) více pohodlná forma při zachování základní notace:

Podívejme se samostatně na problémy maximalizace a minimalizace.

Přednáška 3. Simplexní stoly. Algoritmus simplexové metody.

§ 3 JEDNODUCHÁ METODA

3.1. Hlavní myšlenka simplexní metoda. Geometrická interpretace

Grafická metoda je použitelná pro velmi úzkou třídu problémů lineární programování: dokáže efektivně řešit problémy obsahující maximálně dvě proměnné. Byly uvažovány základní věty lineárního programování, z nichž vyplývá, že má-li úloha lineárního programování optimální řešení, pak odpovídá alespoň jednomu rohovému bodu mnohostěnu řešení a shoduje se s alespoň jedním z přípustných základních řešení řešení. systém omezení. Byl naznačen způsob, jak vyřešit jakýkoli problém lineárního programování: vyjmenujte konečný počet proveditelných základních řešení systému omezení a vyberte z nich to, na kterém účelová funkce vytváří optimální řešení. Geometricky to odpovídá výčtu všech rohových bodů mnohostěnu řešení. Takové vyčerpávající hledání nakonec povede k optimálnímu řešení (pokud existuje), ale jeho praktická realizace je spojena s obrovskými obtížemi, protože u skutečných problémů může být počet proveditelných základních řešení, byť konečných, extrémně velký.

Počet přípustných základních řešení, která mají být prohledávána, lze snížit, pokud hledání není prováděno náhodně, ale s přihlédnutím ke změnám lineární funkce, tj. zajistit, aby všichni další řešení byl „lepší“ (nebo alespoň „ne horší“) než předchozí, podle hodnot lineární funkce (zvýšení při nalezení maxima, snížení při nalezení minima
). Toto vyhledávání umožňuje snížit počet kroků při hledání optima. Vysvětlíme si to na grafickém příkladu.

Nechť je oblast možných řešení reprezentována mnohoúhelníkem ABCDE. Předpokládejme, že jeho rohový bod A odpovídá původnímu proveditelnému základnímu řešení. Náhodné hledání by vyžadovalo testování pěti proveditelných základních řešení odpovídajících pěti rohovým bodům polygonu. Z nákresu je však zřejmé, že po vr A je výhodné přesunout se do sousedního vrcholu V, a pak do optimálního bodu S. Místo pěti jsme prošli pouze třemi vrcholy, čímž jsme lineární funkci neustále zlepšovali.

Myšlenka postupného zlepšování řešení tvořila základ univerzální metody pro řešení problémů lineárního programování - simplexová metoda nebo metoda postupného zlepšování plánu.

Geometrický význam simplexové metody spočívá v sekvenčním přechodu z jednoho vrcholu omezujícího mnohostěnu (tzv. počátečního) do sousedního, ve kterém lineární funkce nabývá nejlepší (alespoň ne nejhorší) hodnotu ve vztahu k cíl problému; dokud není nalezeno optimální řešení - vrchol, kde je dosaženo optimální hodnoty cílové funkce (pokud má problém konečné optimum).

Simplexovou metodu poprvé navrhl americký vědec J. Danzig v roce 1949, ale již v roce 1939 myšlenky metody rozvinul ruský vědec L.V. Kantorovič.

Simplexní metoda, který vám umožní vyřešit jakýkoli problém lineárního programování, je univerzální. V současné době se používá pro počítačové výpočty, ale jednoduché příklady pomocí simplexové metody lze řešit ručně.

Pro implementaci simplexové metody - sekvenčního zlepšování řešení - je nutné zvládnout tři hlavní prvky:

způsob pro stanovení jakéhokoli počátečního proveditelného základního řešení problému;

pravidlo přechodu k nejlepšímu (přesněji ne horšímu) řešení;

kritérium pro kontrolu optimálnosti nalezeného řešení.

Chcete-li použít simplexovou metodu, je třeba problém lineárního programování zredukovat na kanonická forma, tj. systém omezení musí být prezentován ve formě rovnic.

Literatura dostatečně podrobně popisuje: nalezení výchozího plánu podpory (počáteční přípustné základní řešení), také pomocí metody umělého základu, nalezení optimálního plánu podpory, řešení úloh pomocí simplexních tabulek.

3.2. Algoritmus simplexové metody.

Uvažujme řešení ZLP simplexovou metodou a uveďme jej ve vztahu k maximalizačnímu problému.

1. Na základě podmínek úlohy je sestaven její matematický model.

2. Kompilovaný model je převeden na kanonická forma. V tomto případě lze identifikovat základnu s počátečním referenčním plánem.

3. Kanonický model úlohy je zapsán ve formě simplexní tabulky tak, aby všechny volné členy byly nezáporné. Pokud je vybrán počáteční referenční plán, pokračujte krokem 5.

Simplexní tabulka: systém omezujících rovnic a účelová funkce se zadávají ve formě výrazů vyřešených vzhledem k výchozí bázi. Řádek obsahující koeficienty účelové funkce
, volal
– řetězec nebo řetězec cílové funkce.

4. Najděte počáteční referenční plán provedením simplexních transformací s pozitivními rozlišovacími prvky odpovídajícími minimálním simplexním vztahům a bez zohlednění znamének prvků
– čáry. Pokud se během transformací setkáme s řádkem 0, jehož všechny prvky, kromě volného členu, jsou nuly, pak je systém omezujících rovnic pro problém nekonzistentní. Pokud se setkáme s nulovou řadou, ve které kromě volného členu nejsou žádné další kladné prvky, pak systém omezujících rovnic nemá nezáporná řešení.

Zavoláme redukci soustavy (2.55), (2.56) na nový základ simplexní transformace . Pokud je simplexová transformace považována za formální algebraickou operaci, pak si můžeme všimnout, že v důsledku této operace jsou role přerozděleny mezi dvě proměnné zahrnuté v určitém systému lineárních funkcí: jedna proměnná přechází ze závislé na nezávislou a druhá , naopak z nezávislých na závislé. Tato operace je v algebře známá jako Krok eliminace Jordan.

5. Nalezený počáteční plán podpory je zkoumán z hlediska optimálnosti:

a) pokud v
– v řadě nejsou žádné negativní prvky (nepočítáme-li volný termín), pak je plán optimální. Pokud tam nejsou nuly, tak optimální plán jediný; pokud existuje alespoň jedna nula, pak existuje nekonečný počet optimálních plánů;

b) pokud c
– v řádku je alespoň jeden záporný prvek, který odpovídá sloupci nekladných prvků
;

c) pokud v
– řádek má alespoň jeden záporný prvek a jeho sloupec má alespoň jeden kladný prvek, pak se můžete přesunout na nový referenční plán, blíže k optimálnímu. K tomu musí být určený sloupec označen jako rozlišovací sloupec s použitím minimálního simplexního poměru, najít rozlišovací řádek a provést simplexní transformaci. Výsledný referenční plán je opět zkoumán z hlediska optimálnosti. Popsaný proces se opakuje, dokud není získán optimální plán nebo dokud není zjištěna neřešitelnost problému.

Sloupec koeficientů pro proměnnou zahrnutou do základu se nazývá rozlišení. Tedy výběr proměnné zadané do základu (nebo výběr rozlišovacího sloupce) záporným prvkem
-struny, zajišťujeme zvyšující se funkci
.

Trochu obtížnější je určit proměnnou, která má být vyloučena ze základu. K tomu sestaví poměry volných členů ke kladným prvkům rozlišovacího sloupce (takové vztahy se nazývají simplexní) a najdou z nich nejmenší, který určuje řádek (rozlišovací) obsahující vyloučenou proměnnou. Volba proměnné vyloučené z báze (nebo volba rozlišovací linie) podle minimálního simplexního vztahu zaručuje, jak již bylo stanoveno, pozitivitu složek báze v novém referenčním plánu.

V bodě 3 algoritmu se předpokládá, že všechny prvky sloupce volných členů jsou nezáporné. Tento požadavek není nutný, ale pokud je splněn, pak se všechny následné simplexní transformace provádějí pouze s kladně rozlišovacími prvky, což je výhodné pro výpočty. Pokud jsou ve sloupci volných výrazů záporná čísla, je rozlišovací prvek vybrán následovně:

1) podívejte se například na řádek odpovídající nějakému zápornému volnému termínu – řádek a vyberte v něm libovolný záporný prvek a odpovídající sloupec se považuje za řešení (předpokládáme, že omezení problému jsou konzistentní);

2) sestavit vztahy prvků sloupce volných členů k odpovídajícím prvkům rozlišovacího sloupce, které mají stejná znaménka (simplexní vztahy);

3) vyberte nejmenší z simplexních vztahů. Tím určíte aktivační řetězec. Ať je to např. R-čára;

4) v průsečíku rozlišovacího sloupce a řádku se nachází rozlišovací prvek. Pokud je prvek permisivní –řetězce, pak se po simplexní transformaci volný člen tohoto řetězce stane kladným. Jinak se v dalším kroku obracíme znovu na -čára. Pokud je problém řešitelný, pak po určitém počtu kroků nezůstanou ve sloupci volných termínů žádné záporné prvky.

Pokud je určitá skutečná produkční situace vložena do formy PLP, pak další proměnné, které je třeba do modelu zavést v procesu jeho převodu na kanonickou formu, mají vždy určitý ekonomický význam.

Uvažujme o univerzální metodě řešení problému kanonického lineárního programování

S n proměnné a m omezení rovnosti, známé jako simplexová metoda.

Množina plánů pro kanonický problém je konvexní mnohostěnná množina s konečným počtem rohových bodů. A pokud má tento problém optimální řešení, pak je dosaženo alespoň v jednom rohovém bodě.

Jakýkoli rohový bod je spojen se základním plánem problému, ve kterém jsou proměnné rovny nule a zbývající proměnné odpovídají lineárně nezávislým sloupcům matice podmínek. Tyto lineárně nezávislé sloupce tvoří nesingulární základní matici.

Iterace přes všechny rohové body je výpočetně nákladná, a proto neefektivní. V roce 1947 navrhl J. Danzig řádný postup výčtu rohových bodů, kdy k nalezení optimálního řešení stačí prozkoumat jen malou část z nich. Tento postup se nazývá simplexní metoda.

Ukazuje se, že geometricky taková náhrada vede k přechodu z jednoho rohového bodu do sousedního, spojeného s předchozím bodem společnou hranou.

Ze všech sousedních bodů je vybrán ten, ve kterém se účelová funkce zvyšuje nejvíce. Protože počet rohových bodů je konečný, konečným počtem přechodů se najde vrchol s největší hodnotou účelové funkce nebo se na neomezené množině plánů ustaví neohraničenost účelové funkce.

Obecné schéma simplexové metody se skládá z následujících hlavních kroků.

· krok 0. Určení počáteční základny a odpovídajícího počátečního rohového bodu (základny).

· krok 1. Kontrola optimálnosti aktuální základní linie . Pokud je splněno kritérium optimality, Že plán je optimální a řešení hotové. v opačném případě přejděte ke kroku 2.

· krok 2. Hledání proměnné zavedená do základních. (Z podmínky zvýšení účelové funkce).

· krok 3. Nalezení proměnné vyloučené ze základních proměnných (Z podmínky zachování omezení problému).

· krok 4 . Zjištění souřadnic nové účaří (sousední rohový bod). Přejděte ke kroku 1.

Opakované kroky 1-4 tvoří jednu iteraci simplexové metody.

Definice. Řekneme, že kanonický problém LP má „preferovanou formu“, jestliže

1. pravé strany rovnic, .

2. matice podmínek obsahuje jednotkovou podmatici velikosti

Jinými slovy, v každé rovnici je proměnná s koeficientem rovným jedné, který v ostatních rovnicích chybí. První podmínka není zatěžující, protože v případě záporné pravé strany nějaké rovnice ji stačí vynásobit (-1). V preferenčním typu problému je nalezení počáteční základní linie velmi jednoduché.

Příklad 2.1.

Matice stavu A a vektor pravých stran vazeb b vypadat jako

a cílový vektor c = (1, -3, 0, 4, 2).

Jedna základní matice je okamžitě zřejmá: s jednotkovými vektory podmínek.

Proto volíme jako základní proměnné X 1 , X 3 ,X 5 , a vkládání do soustavy rovnic X 2 = x 4 = 0 (nezákladní proměnné) , najdeme okamžitě X 1 = 10,X 3 = 20,X 5 = 8, tedy počáteční základní čára X 0 = (10, 0, 20, 0, 8). Vidíme, že hodnoty základních proměnných se rovnají pravým stranám omezení. Z toho je zřejmé, že pravé strany musí být kladné b i .

V budoucnu budeme základní proměnné kombinovat do vektoru X B.

V kanonickém problému preferované formy je tedy podmatice identity brána jako výchozí základní matice A B = E a odpovídající základní proměnné se rovnají pravým stranám omezení:

X B = b.

Pro základní plán tohoto typu lze formulovat kritérium optimality, které je dostatečně jednoduché na testování. Představíme si množství

? j = < с B , A j > - c j , j = 1,...,n,(2.1)

Kde S B- vektor koeficientů účelové funkce pro základní proměnné X B , A j -j-čt sloupec matice podmínek, C j -j- koeficient účelové funkce. Rozdíly ? j se nazývají simplexní rozdíly nebo simplexní odhady.

Kritérium optimálnosti pro základní plán. Pokud jsou pro základní plán s jednotkovou bázovou maticí všechny simplexní odhady nezáporné, pak je tento plán optimální.

Použitelný toto kritérium pro kontrolu optimálnosti základního plánu X 0 = (10, 0, 20, 0, 8) z příkladu 2.1.

Protože v tomto ohledu vektor základních proměnných X B =(X 1 , X 3 ,X 5 ), Že S B = (C 1 , C 3 ,C 5 ) = (1, 0, 2).

Proto,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Od posouzení ? 4 < 0, то базисный план X 0 není optimální. Všimněte si, že simplexní odhady odpovídající základním proměnným se vždy rovnají nule, takže stačí zkontrolovat pouze nezákladné odhady.

ÚVOD

Téma mé práce se týká řešení problémů vznikajících v ekonomii. To vyvolává otázku výběru nejlepší, v jistém smyslu, možnosti řešení. A hledat možná variantaČasto ovlivněn různými faktory, které zužují rozsah výběru. Jinými slovy, je nutné vyřešit optimalizační problém, který spočívá v nutnosti výběru nejlepší možnost rozhodnutí mezi určitým, obvykle omezeným souborem možných možností.

Optimalizační problém lze formulovat v matematickém jazyce, pokud je množina Dostupné možnosti lze popsat pomocí matematických vztahů (rovnice, nerovnice, rovnice) a každé řešení lze kvantitativně posoudit pomocí nějakého ukazatele zvaného kritérium optimality nebo účelová funkce. Pak nejlepší řešení bude ta, která do účelové funkce dodá maximum resp nejmenší hodnotu, v závislosti na věcném smyslu úkolu. Například při investování omezeného množství finančních prostředků do více projektů je přirozeným úkolem vybrat ty projekty, které mohou v budoucnu přinést největší zisk. Při dodávání produktů od různých dodavatelů do prodejen vyvstává úkol minimalizovat náklady na dopravu.

Proces formalizace problému se nazývá konstrukce jeho matematického modelu. Skládá se ze tří etap.

1. Výběr parametrů problému, na kterém závisí řešení. Tyto parametry se nazývají řídicí proměnné a označují se tak, že se z nich vytvoří vektor . Rozhodnout se znamená nastavit konkrétní hodnoty proměnných.

2. Konstrukce číselného kritéria, podle kterého můžete porovnávat různé možnosti rozhodnutí. Takové kritérium se obvykle nazývá účelová funkce a označuje se .

3. Popis celé sestavy X přípustné hodnoty proměnných - omezení spojená s přítomností materiální zdroje, finanční zdroje, technologické schopnosti a tak dále..

Problém matematické optimalizace je takový najít proveditelné řešení , který dává účelové funkci největší nebo nejmenší hodnotu ze všech možných řešení.

1. Geometrická metodařešení problémů s LP

Tato metoda se často používá k řešení problémů, ve kterých existují pouze dvě neznámé veličiny. Podívejme se na to pomocí následujících příkladů:

Příklad 1.1. (Problém s výrobou barev).

Malá továrna vyrábí dva typy barev: INT- Pro interiérové práce A EXT- pro venkovní práce. Při výrobě barev se používají dva typy barev: originální produkt A A V. Vzhledem k malé skladové ploše jsou maximální možné denní zásoby těchto produktů 6 tun, respektive 8 tun. Na výrobu 1 tuny barvy INT Spotřebuje se 1 tuna produktu A a 2 tuny produktu V a na výrobu 1 tuny barvy EXT jsou 2 tuny produktu A a 1 tuna produktu V. Továrna prodává barvy za cenu 3 tis. dolarů za tunu barvy INT a 2 tisíce dolarů za tunu barvy EXT. Počáteční údaje je vhodné shrnout do tabulky:

Studie prodejního trhu ukázala, že denní poptávka po barvě EXT nikdy nepřekročí poptávku po nátěru INT, více než 1 tuna. Kolik barvy každého typu by měla továrna vyrobit za den, aby maximalizoval příjem z prodeje produktů?

Sestavme matematický model problému. K tomu je nutné určit problémové proměnné, účelovou funkci a omezení, která proměnné splňují. Označme podle x 1- plánovaný denní objem výroby barvy INT a poté x 2- denní objem výroby barvy EXT. Objektivní funkce f(x) bude vyjadřovat denní příjem z prodeje barvy rovnající se 3x 1 + 2x 2(tisíc dolarů). Tento příjem musí být maximalizován

F( x) = 3 x 1 + 2 x 2 ® max.

Pojďme sestavit omezení problému spojeného s omezenými dodávkami produktů A A V. Pro výrobu barev INT v množství x 1 t) se použije 1x 1 t) produktu A a na výrobu barev EXT v objemu x 2(t) budou vynaloženy 2x2 t) produktu A. Od denní dodávky produktu A je 6 tun, pak spotřeba produktu A na výrobu dvou druhů barev nesmí toto množství překročit za den: 1x 1 + 2x 2 6 liber. Podobně získáme omezení spojené se zásobou produktu V : 2x 1+1x 2 8 £. Omezení poměru poptávky po barvách lze popsat nerovností: x 2 - x 1 1 £. Vezmeme-li v úvahu přirozené podmínky pro nezápornost objemů výroby, dostáváme nakonec následující problém lineárního programování

f(x) = 3 x 1 + 2 x 2 ® max (1.1)

1 x 1 + 2 x 2 £ 6 , (1.2)

2 x 1 + 1 x 2 £ 8 , (1.3)

- x 1 + x 2 1 £ , (1.4)

x 1 ³ 0, x 2 ³ 0 . (1.5)

Sestavme množinu problémových plánů popsaných omezeními (1.2)-(1.5). Podívejme se na první nerovnost. Určuje určitou polorovinu umístěnou na jedné straně hraniční čáry

p 1 : 1x 1 + 2x 2 = 6

Sestrojme tuto přímku na rovině se souřadnicovými osami x 1 A x 2. K nakreslení čáry stačí znát její dva body. Nejjednodušší způsob je najít průsečíky přímky se souřadnicovými osami. Věřící x 1 = 0, z rovnice přímky dostaneme x 2 = 3, a kdy x 2 = 0 najdeme x 1 = 6. Takto rovně p 1 projde body (0,3) A ( 6,0) . K určení, na které straně přímky leží požadovaná polorovina, stačí dosadit souřadnice libovolného bodu roviny do nerovnice (1.2). Pokud přímka neprochází počátkem, pak je nejvhodnější vzít bod (0, 0) . Je zřejmé, že v tomto bodě je zcela splněna nerovnost (1.2). (1* 0 + 2* 0 < 6) , což znamená, že polorovina definovaná touto nerovností leží pod přímkou p1, včetně původu. Požadovanou polorovinu označíme stínováním ( Obr.1.1).

Podobně sestrojme polorovinu definovanou nerovností (1.3) . Chcete-li to provést, nakreslete hraniční čáru na rovině souřadnic

p2 : 2x 1 +x 2 = 8 ,

nalezení jeho průsečíků se souřadnicovými osami: (0,8) A (4,0) .

Nahrazení souřadnic bodu (0,0) do nerovnosti (2.3), vidíme, že počátek souřadnic leží v požadované polorovině (2* 0 + 1* 0 < 8) , což znamená, že všechny body vyhovující nerovnosti (2.3) jsou umístěny vlevo od přímky p2. Označme tuto oblast stínováním ( Obr.1.1).

Body definované omezením ( 4 ), jsou pod přímou čarou

p 3 : -x 1 +x 2 = 1,

procházející body (0, 1) A (-1, 0) .

Nakonec podmínky nezápornosti: x 1 ³ 0, x 2³0 nastaví všechny body prvního čtvrtletí, které také označíme stínováním.

Nyní výběrem bodů roviny, které splňují všechna omezení problému (1.1)-(1.5), to znamená, že se nacházejí současně ve všech stínovaných polorovinách, získáme sadu plánů X. Je to mnohoúhelník (v tomto problému pětiúhelník). Jeho strany leží na přímkách, jejichž rovnice jsou získány z původní systém nerovnosti (1.2)-(1.5) nahrazením znaků nerovnosti přísnými rovnostmi.

Pro grafické znázorněníúčelové funkce zavádíme pojem úrovňová čára (funkční izočára).

Definice.Čára funkční úrovně (izolovaná) f(x) se nazývá množina bodů x = (x 1, x2), ve kterém nabývá stejné konstantní hodnoty f(x) = h, Kde h- nějaké číslo. Pro lineární funkci dvou proměnných f(x) = c 1 x 1 + c 2 x 2úrovňová čára odpovídající číslu h, bude představovat přímku s rovnicí

c 1 x 1 + c 2 x 2 = h (1.6)

Když se číslo změní h získáme rodinu úrovňových čar (paralelních přímek) se stejným směrovým vektorem c = =(c 1, c 2), kolmo ke všem čarám. Je známo, že vektor c = (c 1, c 2) pro lineární funkci f(x) = c 1 x 1 + c 2 x 2 udává směr jejího nárůstu. Geometricky to znamená, že při paralelním pohybu přímky (1.6) ve směru cílového vektoru C hodnota účelové funkce roste.

Sestrojme úrovňové čáry účelové funkce f(x) = 3x 1 + 2 x 2 v našem úkolu. Jejich rovnice budou vypadat 3x 1 + 2 x 2 = h. Definují rodinu rovnoběžných čar v závislosti na parametru h. Všechny čáry jsou kolmé k cílovému vektoru c = (3, 2), složený z koeficientů účelové funkce, proto ke konstrukci rodiny čar úrovně účelové funkce stačí sestrojit její cílový vektor a nakreslit několik přímek kolmých na tento vektor. Na mnoha plánech nakreslíme úrovňové čáry X, pamatovat si, že při pohybu rovnoběžných čar ve směru cílového vektoru c = (3, 2) funkční hodnotu f(x)= 3x 1 + 2x 2 se zvýší. Protože v problému by měl optimální plán poskytnout maximální hodnotu cílové funkci možný význam, pak k vyřešení problému graficky je nutné mezi všemi body x = (x 1, x2) mnoho plánů X najít takový bod x* = (x 1 *, x 2 *), kterou bude procházet poslední čára úrovně ve směru cílového vektoru c = (3,2). Z obrázku 1.2 je zřejmé, že požadovaným bodem bude bod ležící v horní části množiny X, tvořený průsečíkem čar p 1 A p2. Řešením soustavy rovnic popisujících tyto přímky najdeme optimální plán x 1 * = 3 1/3, x 2 * = 1 1/3. V tomto případě bude maximální hodnota účelové funkce rovna f(x*) = 12 2/3. Továrna tedy musí vyrábět každý den 3 1 / 3 tuny barvy INT A 1 1 / 3 tuny barvy EXT při pobírání příjmu 12 2 / 3 tisíc dolarů.

x 1 + 2 x 2 = 6,

2 x 1 + x 2 = 8,

Příklad 1.2. Zdravotnický podnik nakupuje dva typy multivitaminových komplexů „Zdraví“ a „Dlouhověkost“ obsahující tři druhy vitamínů. Počet jednotek těchto vitamínů v jednom gramu multikomplexů, jejich požadovaná norma pro preventivní použití a náklady na jeden gram komplexů „Zdraví“ a „Dlouhověkost“ jsou uvedeny v tabulce.

Kolik gramů multivitaminových komplexů jednotlivých typů je potřeba na jednu preventivní dávku, aby všechny vitaminy byly přijímány alespoň tak, jak je požadováno, a zároveň jejich celková cena byla minimální.

Vytvořme matematický model problému. K tomu zavádíme proměnné: x 1– množství komplexu „Zdraví“. (GR.) , x 2– množství komplexu „dlouhověkosti“. (GR.) nezbytné pro profylaktické použití. Objektivní funkce vyjadřuje celkovou cenu vitaminových komplexů, která by měla být co nejnižší

F( x) = 5 x 1 + 4 x 2 ® min (1.7)

Omezení popisující splnění vitaminových norem jsou následující:

Podle vitaminu V 1 : 3x 1 + x 2 ³ 9 , (1.8)

Podle vitaminu V 2 : x 1 + 2 x 2 ³ 8, (1.9)

Podle vitaminu V 3 : x 1 + 6 x 2 ³ 12 . (1.10)

V tomto případě musí být proměnné nezáporné: x j ³ 0, j = 1, 2.

Začněme řešení znovu konstrukcí mnoha plánů X, pro které nakreslíme hraniční přímky, jejichž rovnice získáme nahrazením znamének nerovností v omezeních rovností

p 1 : 3 x 1 + x 2 = 9,

p2 : x 1 + 2 x 2 = 8,

p 3 : x 1 + 6 x 2 = 12.

Nahrazení souřadnic bodu (0,0) u nerovností (1.8)-(1.10) vidíme, že počátek souřadnic je nesplňuje, a proto není zahrnut do množiny plánů X. Proto jsou šrafy nasměrovány nad a vpravo od hraničních čar. Identifikací bodů, které splňují všechny nerovnosti a podmínky nezápornosti, získáme sadu plánů znázorněnou na Obr. 1.2. V v tomto příkladu není omezená.

Znázorněme účelovou funkci (1.7) pomocí úrovňových čar. K tomu stačí sestrojit cílový vektor c = (5, 4) a nakreslete několik čar kolmých k němu na sadě X. Protože cílový vektor udává směr nárůstu cílové funkce a v dietním problému je potřeba najít jeho minimum, pak pro nalezení optimálního řešení posuneme linii hladiny rovnoběžně s ní podél množiny X ve směru opačném k cílovému vektoru.

Posledním bodem množiny plánů, kterým ještě prochází úrovňová linie, bude průsečík linií p 1 A p2. Řešení uranového systému (obr. 1.3).

3 x 1 + x 2 = 9

x 1 + 2 x 2 = 8

dostaneme optimální plán x 1 * = 2, x 2 * = 3. Minimální hodnota účelové funkce bude rovna

f(x*) = 5∙2 + 4∙3 = 22.

Proto se nejlevnější profylaktická sada skládá z 2 g. komplex A a 3 g. komplex V a jeho cena je 22 třít.

Nyní je snadné formulovat geometrické řešení standardní úkoly LP se dvěma proměnnými:

· je znázorněn přípustný mnohoúhelník - průsečík polorovin, které jsou řešením odpovídajících nerovností;

· je zobrazen cílový vektor;

· přípustnou množinou je vykreslena kolmice k cílovému vektoru - jedná se o linii úrovně cílové funkce;

· posunutím úrovňové čáry rovnoběžně se sebou ve směru cílového vektoru, dokud není na jedné straně posunuté přímky, je vizuálně určen maximální bod (nebo body);

· jsou vypočteny souřadnice maximálního bodu (řešením příslušné soustavy rovnic definujících přímky, jejichž průsečíkem je požadovaný bod) a maximální hodnota účelové funkce.

Komentář. Chcete-li určit minimální bod, posuňte izočáru proti směru cílového vektoru.

V analyzovaných příkladech byl optimální plán umístěn v jediném vrcholu polygonu proveditelných plánů. Při řešení problémů LP však mohou nastat i další případy.

Nekonečné množství optimálních plánů. Na Obr.1.4účelová funkce má stejnou maximální hodnotu v libovolném bodě segmentu AB spojující dva vrcholy množiny plánů X. Tato situace nastane, pokud jsou čáry úrovně rovnoběžné s hraniční čárou.

Absence omezené řešení . Na Obr.1.5 Je znázorněn případ, kdy účelová funkce není shora ohraničena na množině plánů a řešení maximálního problému neexistuje. V tomto případě může existovat řešení minimálního problému (jako v problému vitamínů).

Nedostatek platných plánů. Na Obr.1.6 Oblasti povolené v rámci každého z omezení nemají společné body. V tomto případě říkají, že omezení jsou nekonzistentní, sada plánů je prázdná a problém LP nemá řešení.

Rýže. 1.4 Obr. 1.5 Obr. 1.6

2. Simplexní metoda

2.1 Myšlenka simplexové metody

Uvažujme o univerzální metodě řešení problému kanonického lineárního programování

, , ,

S n proměnné a m omezení rovnosti, známé jako simplexová metoda.

Ukazuje se, že geometricky taková náhrada vede k přechodu z jednoho rohového bodu do sousedního, spojeného s předchozím bodem společnou hranou.

Obecné schéma simplexové metody se skládá z následujících hlavních kroků.

· krok 0. Určení počáteční základny a odpovídajícího počátečního rohového bodu (základny).

· krok 1. Kontrola optimálnosti aktuální základní linie . Pokud je splněno kritérium optimality, je plán optimální a řešení je hotové. v opačném případě přejděte ke kroku 2.

· krok 2. Hledání proměnné zavedená do základních. (Z podmínky zvýšení účelové funkce).

· krok 3. Nalezení proměnné vyloučené ze základních proměnných (Z podmínky zachování omezení problému).

· krok 4 . Zjištění souřadnic nové účaří (sousední rohový bod). Přejděte ke kroku 1.

Opakované kroky 1–4 tvoří jednu iteraci simplexové metody.

Definice. Řekneme, že kanonický problém LP má „preferovanou formu“, jestliže

1. pravé strany rovnic , .

2. matice podmínek obsahuje jednotkovou podmatici velikosti

Jinými slovy, v každé rovnici je proměnná s koeficientem rovným jedné, který v ostatních rovnicích chybí. První podmínka není zatěžující, protože v případě záporné pravé strany nějaké rovnice ji stačí vynásobit (–1). V preferenčním typu problému je nalezení počáteční základní linie velmi jednoduché.

Příklad 2.1.

Matice stavu A a vektor pravých stran vazeb b vypadat jako

, ,

a cílový vektor c = (1, -3, 0, 4, 2).

Jedna základní matice je okamžitě zřejmá: s jednotkovými vektory podmínek.

Proto volíme jako základní proměnné x 1 , x 3 ,x 5 a vkládání do soustavy rovnic x 2 = x 4 = 0 (nezákladní proměnné) , najdeme okamžitě x 1 = 10,x 3 = 20,x 5 = 8, tedy počáteční základní čára x 0= (10, 0, 20, 0, 8) Vidíme, že hodnoty základních proměnných se rovnají pravým stranám omezení. Z toho je zřejmé, že pravé strany musí být kladné b i.

V budoucnu budeme základní proměnné kombinovat do vektoru x B.

V kanonickém problému preferované formy je tedy podmatice identity brána jako výchozí základní matice A B = E a odpovídající základní proměnné se rovnají pravým stranám omezení:

x B = b .

Pro základní plán tohoto typu lze formulovat kritérium optimality, které je dostatečně jednoduché na testování. Představíme si množství

∆ j =< с Б, A j >– c j , j = 1,...,n, (2.1)

Kde s B– vektor koeficientů účelové funkce pro základní proměnné x B , Aj - j- sloupec matice podmínek, c j – j- koeficient účelové funkce. Rozdíly ∆ j se nazývají simplexní rozdíly nebo simplexní odhady.

Kritérium optimálnosti pro základní plán. Pokud jsou pro základní plán s jednotkovou bázovou maticí všechny simplexní odhady nezáporné, pak je tento plán optimální.

Použijme toto kritérium pro kontrolu optimálnosti základního plánu x 0= (10, 0, 20, 0, 8) z příkladu 2.1.

Protože v tomto ohledu vektor základních proměnných x B =(x 1 , x 3 ,x 5), Že s B = (c 1 , c 3 ,c 5) = (1, 0, 2).

Proto,

∆ 1 = < с Б, A 1 >– od 1 =1∙1 + 0∙0 + 2∙0 – 1= 0,

∆ 2 = < с Б, A 2 >– c 2 =1∙3 + 0∙1 + 2∙2 – (-3) = 10,

∆ 3 = < с Б, A 3 >– c 3 =1∙0 + 0∙1 + 2∙0 – 0= 0,

∆ 4 = < с Б, A 4 >– c 4 =1∙(-1) + 0∙5 + 2∙1 – 4= -3,

∆ 5 = < с Б, A 5 >– od 5 =1∙0 + 0∙0 + 2∙1 – 2= 0.

Od posouzení ∆ 4 < 0, то базисный план x 0 není optimální. Všimněte si, že simplexní odhady odpovídající základním proměnným se vždy rovnají nule, takže stačí zkontrolovat pouze nezákladné odhady.

2.2 Implementace simplexové metody na příkladu

Ukažme si použití simplexové metody na příkladu. Zvažte kanonický problém LP

f(x) = X 1 + 2X 2 + 0X 3 + 0X 4 →max	(2.2)
–X 1 + 2X 2 +x 3 = 4,	(2.3)
3X 1 + 2X 2 +x 4 = 12,	(2.4)
x j ≥ 0, j = 1,2,3,4.	(2.5)

Matice stavu A = (A 1 , A 2 , A 3 , A 4), kde

Cílový vektor C =(c 1, c2, c 3, c 4 a) = (1, 2, 0, 0); vektor pravých částí b =(b 1 , b 2) = (4, 12).

Krok 0. Nalezení počátečního rohového bodu (baseline).

Úloha má výhodnější formu, protože pravé strany rovnic jsou kladné a sloupce matice podmínek A 3, A 4 tvoří jednotkovou submatici. To znamená počáteční základní matici = (A 3 ,A 4); X 3 a X 4 – základní proměnné X 1 a X 2 - nezákladní proměnné, c B = (C 3, C 4) = = (0, 0).

Počáteční základní linie vypadá takto x 0 = (0, 0, X 3 , X 4) = (0, 0, 4, 12); F( x o)= 0.

Krok 1. Kontrola optimálnosti základního plánu.

Vypočítejme simplexní odhady pro nezákladní proměnné pomocí vzorce (5.1)

 1 = < c B, A 1 > – C 1 = 0 · (–1) + 0 ·3 – 1 = –1 .

 2 = < c B, A 2 > – C 2 = 0 2 + 0 2 – 2 = –2 .

Vzhledem k tomu, že odhady jsou negativní, plán X - není optimální. Budeme hledat novou účaří (sousední rohový bod) s větší hodnotou účelové funkce.

Krok 2. Nalezení proměnné zavedené do základu.

Cílovou funkci lze zvýšit zavedením jedné z nebázických proměnných do základních proměnných (učinit ji kladnou) X 1 nebo X 2, protože oba odhady  j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную X 2.

Krok 3 Definice proměnné odvozené od základu.

Po zadání proměnné do základu x 2 nový plán bude vypadat

x" = (0, X 2, X 3 , X 4).

Tento plán není základní, protože obsahuje pouze jednu nulovou souřadnici, což znamená, že je nutné jednu z proměnných nastavit na nulu (vyloučit ze základny) X 3 nebo X 4. Dosadíme souřadnice plánu x" = (0, X 2, X 3 ,X 4) v omezeních problému. Dostaneme

2X 2 + X 3 = 4,

2X 2 + X 4 = 12.

Vyjádřeme odtud základní proměnné X 3 a X 4 přes proměnnou X 2 , vstoupil do základu.

Čím vyšší je hodnota X 2 , tím více se zvyšuje účelová funkce. Najděte maximální hodnotu nové bazické proměnné, která neporušuje omezení problému, tedy splňující podmínky (2.8), (2.9).

Přepišme poslední nerovnosti ve formuláři

2X 2 ≤ 4,

2X 2 ≤ 12,

odkud pochází maximální hodnota? X 2 = min ( 4/2, 12/2 ) = 2. Dosazení této hodnoty do výrazů (2.6), (2.7) pro X 3 a X 4, dostáváme X 3 = 0. Proto x 3 odvozené od základu .

Krok 4. Určení souřadnic nové základní linie.

Nová základní linie (sousední rohový bod) je:

X" = (0, X 2, 0, X 4)

Základ tohoto bodu tvoří sloupce A 2 a A 4 , takže =( A 2, A 4). Tento základ není jednotný, protože vektor A 2 = (2,2), a proto problém (2.2)–(2.5) nemá vzhledem k novému základu preferovanou formu. Transformujme podmínky problému (2.3), (2.4) tak, aby nabyl preferované podoby vzhledem k novým základním proměnným X 2, X 4, to znamená, že proměnná X 2 byl zahrnut do první rovnice s koeficientem rovným jedné a nebyl přítomen ve druhé rovnici. Přepišme rovnice úlohy

– X 1 + 2 X 2 + X 3 = 4, (p 1)

3X 1 +2 X 2 + X 4 = 12. (p 2)

Vydělme první rovnici koeficientem at X 2. Dostaneme novou rovnici = p 1/2 ekvivalent originálu

– 1/2 X 1 + X 2 + 1/2 X 3 = 2. ( )

Tuto rovnici, kterou nazýváme řešení, používáme k eliminaci proměnné X 2 z druhé rovnice. K tomu potřebujeme rovnici vynásobte 2 a odečtěte od p 2 . Dostaneme = p 2 – 2= p 2 -p 1:

4 X 1 – X 3 + X 4 = 8. ( )

V důsledku toho jsme získali novou „preferovanou“ reprezentaci původního problému s ohledem na nové základní proměnné X 2 , X 4:

F (X) = X 1 + 2 X 2 + 0 X 3 + 0 X 4  max

– 1/2 X 1 + x 2 + 1/2 X 3 = 2 ( )

4 X 1 – X 3 + X 4 = 8 ( )

x j 0, j = 1,2,3,4

Zde se nahradí reprezentace nové základní linie X 1 = (0, X 2, 0, X 4), okamžitě najdeme jeho souřadnice, protože hodnoty základních proměnných se rovnají pravým stranám rovnic

X" = (0, 2, 0, 8); F (X 1)=4.

Druhou iteraci neprovedeme podle schématu první, protože je pohodlnější provádět všechny výpočty simplexové metody v tabulkové formě.

2.3 Tabulková implementace jednoduché simplexové metody

Tabulkovou implementaci předvedeme na stejném příkladu (2.2)–(2.5).

Krok 0. Řešení začíná konstrukcí počáteční simplexní tabulky. Vyplněno jako první pravá část tabulky ze třetího sloupce. Ve dvě horní řádky jména jsou zaznamenána problémové proměnné (X 1, ...,X 4) a koeficienty účelové funkce pro tyto proměnné. Níže jsou uvedeny koeficienty rovnic - prvky matice podmínek A, tedy pod proměnnou X 1 je umístěn sloupec A 1, pod proměnnou X 2 – sloupec A 2 atd. Pravé strany omezení (čísla) se zadávají do pravého sloupce b i > 0).

Poté najdeme sloupce matice podmínek, které tvoří základ jednotky – v našem příkladu to tak je A 3 a A 4 a odpovídající základní proměnné X 3, X 4 se píše ve druhém sloupci. Nakonec do prvního sloupce zapíšeme koeficienty účelové funkce pro základní proměnné.

Tabulka 1 - Počáteční simplexní tabulka

S B	Základní proměnné	s 1 = 1	s 2 = 2	s 3 = 0	se 4 = 0	Základní proměnné hodnoty ( X B = b)
S B	Základní proměnné	*x 1*	*x 2*	*x 3*	*x 4*	Základní proměnné hodnoty ( X B = b)
c3=0	*x 3*	a 11 = -1	a 12 = 2	a 13 = 1	a 14 = 0	b1=4
c4=0	*x 4*	a 21 = 3	a 22 = 2	a 23 = 0	a 24 = 1	b2=12
Hodnotící linie  j		 1 = -1	 2 = -2	 3 = 0	 4 = 0	f(x)= 0

Protože problém má preferovanou formu, hodnoty základních proměnných se rovnají pravým stranám rovnic umístěných v posledním sloupci. Vzhledem k tomu, že nebázové proměnné jsou nulové, je počáteční základní čára

X o = (0, 0, X 3 , X 4) = (0, 0, 4, 12).

Krok 1. Pro kontrolu plánu X o pro optimalitu počítáme simplexní odhady pro nebázické proměnné X 1 a X 2 podle vzorce

 j =< c Б , A j > – c j .

 1 = < c Б , A 1 > – c 1 = 0 · (–1) + 0 ·3 – 1 = –1 .

S tabulkovou implementací pro výpočet skóre  1 musíme najít součet součinů prvků prvního sloupce ( c B) k odpovídajícím sloupovým prvkům A 1 pro nezákladní proměnnou X 1. Skóre se počítá stejným způsobem  2 , Jak skalární součin první sloupec ( c B) na sloupec v proměnné x 2 .

 2 = < c B, A 2 > – C 2 = 0 2 + 0 2 – 2 = –2 .

Simplexní odhady se zapisují do posledního řádku simplexní tabulky, který se nazývá delta řádek. V tomto případě se vyplňují nejen buňky pro nezákladní proměnné, ale i buňky základní. Je snadné zkontrolovat, že pro sloupce základních jednotek matice podmínek jsou simplexní odhady rovny nule. Do poslední buňky vyhodnocovacího řádku zapíšeme hodnotu účelové funkce v bodě xo. Všimněte si, že protože nezákladní souřadnice základního plánu jsou rovné nule, je vhodné vypočítat účelovou funkci pomocí vzorce

F (X)= < c B ,x B >,

skalárním vynásobením prvního a posledního sloupce tabulky.

Od mezi odhady  j existují negativní , pak plán X o není optimální a je nutné najít nový základní plán nahrazením jedné ze základních proměnných novou z těch nezákladních.

Krok 2. Od obou odhadů  1 a  2 < 0,то в базис можно включить любую из переменных X 1, X 2 . Zaveďme do báze proměnnou s největším absolutním záporným odhadem, tzn X 2 .

Sloupec simplexní tabulky, ve kterém se nachází proměnná zadaná do základu, se nazývá úvodní sloupec .

V příkladu bude úvodní sloupec at x 2.

Krok 3 Pokud jsou všechny prvky v úvodním sloupci záporné, pak problém neexistuje a max F (X) . V příkladu jsou všechny prvky úvodního sloupce kladné, proto můžeme najít maximální hodnotu X 2 , při kterém jedna ze starých základních proměnných klesne na nulu. Připomeňme, že maximální hodnota x 2 = min(4/2, 12/2)=2.

Podle tabulky se tato hodnota vypočítá jako nejmenší z poměrů složek základní linie (z posledního sloupce) k odpovídající pozitivní prvky vedoucího sloupce.

Nejmenší poměr je v řádku se základní proměnnou x 3. Takže proměnná x 3 vyloučeno ze základních proměnných ( X 3 = 0).

Řádek obsahující proměnnou, která má být vyloučena ze základu, se nazývá úvodní čára.

V tomto příkladu bude úvodní čára první čára.

Prvek umístěný na průsečíku úvodního řádku a úvodního sloupce se nazývá úvodní prvek.

V našem případě vůdčí prvek A 12 = 2.

Stůl 2 - Počáteční simplexní tabulka s úvodním řádkem a sloupcem

c B	Základní změny.	s 1 = 1	s 2 = 2	s 3 = 0	C4=0	Základní proměnné hodnoty	Rovnice
c B	Základní změny.	x 1	*x 2*	x 3	x 4	Základní proměnné hodnoty	Rovnice
*c3=0*	X 3	–1	2	1	0	4	p 1
c4=0	x 4	3	2	0	1	12	p2
Hodnotící linie  j		 1 = –1	 2 = –2	 3 = 0	 4 = 0	f(x)= 0

Krok 4. Pro získání nového základního plánu redukujeme problém na novou preferovanou formu s ohledem na nové základní proměnné.

K tomu sestavíme novou simplexní tabulku, v jejímž druhém sloupci místo vyloučené proměnné x 3 napíšeme novou základní proměnnou x 2 a v prvním sloupci ( s B) namísto od 3 Zapišme si koeficient účelové funkce at x 2 : c2=2. V nové simplexní tabulce je sloupec at x 2 musí být jedna (hlavní prvek musí být roven jedné a všechny ostatní prvky musí být nula). Toho je dosaženo následující transformací řádků tabulky.

A. Všechny prvky úvodního řádku vydělíme úvodním prvkem a zapíšeme je do stejného řádku nové simplexní tabulky.

Výsledný řetězec p 1"Říkejme tomu permisivní.

b. Ke zbývajícímu druhému řádku přidáme rozlišovací řádek, vynásobený takovým číslem, aby se prvek v úvodním sloupci stal nulou.

p 2 "= p 2 + (- 2) p 1 "= p 2 - p 1.

C. Poslední řádek vyplníme výpočtem odhadů  j " =< c Б ", A j " >-- c j,Kde c B", A j" - odpovídající sloupce nové simplexní tabulky a hodnotu účelové funkce f(x)=< c Б ", x Б " >.

Získáme druhou simplexovou tabulku s novým základem.

Tabulka 3 - Výsledek první iterace

c B"	Základní změny.	s 1 = 1	s 2 = 2	s 3 = 0	se 4 = 0	Základní proměnné hodnoty	Rovnice
c B"	Základní změny.	x 1	x 2	x 3	x 4	Základní proměnné hodnoty	Rovnice
c2=2	X 2	*–1/2*	1	1/2	0	2	p 1 " = p 1 /2
c4=0	*x 4*	4	0	-1	1	8	p 2 " = p 2 - p 1
hodnocení  j"		–2	0	1	0	f(x")=4

Nová základní linie X " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ).

Od posouzení  1 = -2 < 0, pak plán X " není optimální. Pro přechod na nový základní plán (sousedního rohového bodu) provedeme další iteraci simplexové metody.

Protože  1 < 0, pak se do základu zavede proměnná x 1 . První sloupec obsahující x 1 - vedoucí.

Najdeme vztahy mezi složkami základního plánu a odpovídajícími pozitivní prvky vedoucího sloupce a převezměte řádek s nejnižší poměr. V tabulce 2 je tedy v úvodním sloupci pouze druhý prvek větší než nula (= 4). druhý řádek bude vedoucí a základ v něm umístěný variabilní x 4 předmětem vyloučení ze základu .

Vybereme úvodní sloupec a úvodní řádek a najdeme jejich průsečík úvodní prvek (= 4) .

Sestavíme novou (třetí) simplexovou tabulku a nahradíme v ní základní proměnnou x 4 na x 1 a opět transformace řádků tabulky tak, aby se úvodní prvek rovnal jedné a zbývající prvky úvodního sloupce se staly nulou. Chcete-li to provést, vydělte úvodní (druhý) řádek 4 a k prvnímu řádku přidejte výsledný druhý řádek dělený 2. Poslední řádek vypočítáme pomocí vzorců pro simplexní odhady  j "" = < c Б "", Aj ""> - c j,Kde c B "", Aj "" - odpovídající sloupce nové simplexní tabulky. Hodnota účelové funkce na nové základní linii se zjistí pomocí vzorce f(x "")= < c Б "", x B "" >.

Tabulka 4 - Výsledek druhé iterace

c B ""	Základní změna.	s 1 = 1	s 2 = 2	s 3 = 0	se 4 = 0	Základní proměnné hodnoty	rovnic
c B ""	Základní změna.	x 1	x 2	x 3	x 4	Základní proměnné hodnoty	rovnic
c2=2	x 2	0	1	3/8	1/8	3	p 1 "" = p 1 "+p 2 ""/2
c 1 = 1	x 1	1	0	-1/4	1/4	2	p 2 "" = p 2 "/4
hodnocení  j ""		0	0	1/2	1/2	f(x "")= 8

Nová základní linie X "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Protože všechny odhady jsou nezáporné, pak plán X ""- optimální plán.

Tím pádem, X* = (2, 3, 0, 0 ), f(x*) = 8.

ZÁVĚR

Uvažované metody řešení úloh lineárního programování jsou v praxi široce používány. Je však třeba poznamenat, že matematický model vždy chudší než skutečný ekonomický systém. Popisuje tento systém pouze přibližně, některé vlastnosti zdůrazňuje a jiné opomíjí. Pro kompenzaci tohoto nedostatku v matematické ekonomii se vyvíjí několik typů modelů, z nichž každý je navržen tak, aby odrážel jeden konkrétní aspekt ekonomické reality, takže při řešení konkrétního ekonomický problém bylo možné vybrat model, který se k tomu nejlépe hodí.