4. Matematické programování.

Problematika matematického programování je velice široká a zahrnuje oblasti lineárního programování. Základní úlohu lineárního programování zformuloval Dantzig již v roce 1947 a současně později vypracoval i metodu řešení této úlohy (simplexovou metodu), která je dodnes nejpoužívanější.

Úloha parametrického programování byla zformulována v roce 1955 a úloha celočíselného programování byla řešena v roce 1958. Dále následují již v různém pořadí kvadratické, lineárně lomené, geometrické ,konvexní a nekonvexní programování. Z objemových důvodů budeme nuceni se omezit pouze na některé oblasti matematického programování, především na lineární programování a simplexovou metodu. Obecně konvexní programování je podrobně rozebráno v další kapitole.

4.1. Lineární programování.

V první kapitole jsme se seznámili s některými základními modely lineárního programování, jako byla úloha o dietě, stanovení optimálního výrobního programu, dopravní úloha apod.

Obecná úloha lineárního programování (dále pouze úloha LP) může být vyjádřena následujícím způsobem:

m a x (nebo m i n ) ( c , x )

při podmínkách

( ai , x ) nebo >= nebo = bi , i=1,2,...,m

xj >= 0 , j=1,2,...,n

Je vidět, že omezující podmínky v tomto matematickém modelu mohou být vyjádřeny v maticové a vektorové formě. Výraz (c,x) je skalárním součinem vektoru c a vektoru x.

Cílem operace v tomto modelu je najít takovou strategii x (budeme jí v tomto případě říkat plán), aby při zadaných podmínkách byla hodnota cílové funkce maximální ( minimální ). V dalším textu předpokládáme dostatečnou znalost maticového a vektorového počtu na úrovni vysokoškolského kurzu analytické geometrie a algebry.

Různé formy úloh lineárního programování a jejich ekvivalence.

Nehledě na různorodost a obsah situací, kterými jsme se zabývali při vytváření matematických modelů v první kapitole, ukazuje se, že všechny lineární modely mají hodně společného. Této vlastnosti je možné využít pro řešení i značně různorodých úloh. Pro naše další záměry bude výhodné, naučíme-li se řešit pouze jeden typ úlohy lineárního programování a všechny ostatní budeme umět k němu nějakým způsobem svést. Bude to daleko jednodušší, než kdybychom se pro každý typ úlohy učili jiný způsob řešení.

Téměř všechny úlohy lineárního programování můžeme rozdělit zhruba do tří kategorií podle omezujících podmínek:

Standardní_úlohy_lineárního_programování.

m a x ( c , x )

A.x <=b a x >= 0

Kanonické_úlohy_lineárního_programování.

m a x ( c , x )

A.x = b a x >= 0

Smíšené_úlohy_lineárního_programování.

Úloha obsahuje jak omezující podmínky typu rovnost, tak omezující podmínky typu nerovnosti. Pokud jsou nerovnosti různého typu není to na závadu, protože znak nerovnosti můžeme změnit vynásobením nerovnosti číslem -1.

Věta 4.1.

Všechny tři výše uvedené úlohy jsou ekvivalentní v tom smyslu, že jednoduchými úpravami lze jednu převést na druhou a optimální řešení těchto úloh se nezmění.

Důkaz.

Převeďme nejprve standardní úlohu LP na úlohu kanonickou.Zaveďme pro tento účel nové proměnné (budeme je označovat jako "přídatné", protože jsme je přidali) z = (z1 ,z2 ,...,zm). Těchto proměnných nechť je právě tolik, kolik omezujících podmínek standardní úlohy. Vytvořme nyní novou úlohu lineárního programování:

m a x {( c , x ) + ( 0 , z ) }

A .x + I .z = b , x,z >= 0,

kde I je jednotková matice typu (m,m). Je třeba dokázat, že vektor x* je optimálním řešením původní úlohy, právě když vektor ( x*; z* ) je řešením nové úlohy lineárního programování. Předpokládejme nejprve, že se najde vektor ( x0;z0) takový, že je optimálním řešením nové úlohy a vektor x0 není řešením nové úlohy. Jelikož

b = A .x0 + I .z0 >= A .x 0 , pak

A .x0 <=b

To znamená, že podmínky původní úlohy musí být splněny a x0 je přípustným řešením původní úlohy. Dále pro cílovou funkci platí pro libovolná x,z

( c , x0 ) + ( 0 , z0 ) = ( c , x0) >= ( c , x ) + ( 0 , z ),

což je v rozporu s předpokladem ,že x0 není optimálním řešením původní úlohy. Pokud by existoval jiný vektor xa, který by byl optimálním řešením, muselo by pro něj platit

( c , xa ) >= ( c , x0 ).

Předpokládejme nyní, že x0 je optimálním řešením původní úlohy a dokažme, že je řešením i úlohy nové pro nějaký nezáporný vektor z0.

A .x0 <=b položme z0 = b - A .x0 >= 0

v takovém případě

b = A .x0 + I .z0

a současně

( c , x0 ) + ( 0 , z0 ) = ( c , x0) >= ( c , x ) + ( 0 , z ),

pro každý vektor x a vektor z. Věta je dokázána pro převod na kanonickou úlohu. Důkaz o převodu kanonické na standardní úlohu ponechávám čtenáři. Každou omezující podmínku typu rovnost je možné přepsat jako dvě opačné nerovnosti a druhou po vynásobení číslem mínus jedna převedeme na nerovnost se stejným znakem jako má první nerovnost. Pak je možné zopakovat postup důkazu.

Cvičení.

Převeďte následující úlohy ke kanonickému tvaru.

m a x ( c,x ) 2 0 1 1 c=(2,-1,3)

A.x<b , x>=0

Matice A a vektor b

2 0 1 1
1 2 3 2

m i n ( c,x ) 2 1 1 c=(1,1)

A.x>=b

Matice A a vektor b

2 4 1
4 2 2
1 2 1


4.1.1 Úloha o nalezení číselného řešení základního problému LP.

První snahou, celkem přirozenou, je snaha využít známých metod klasické matematické analýzy a algebry. Představme si, že řešíme úlohu nalezení minima diferencovatelné funkce na segmentu. Nechť je tedy dána funkce f(x) jedné proměnné na uzavřeném intervalu [a,b]. Algoritmus pro nalezení minima této funkce by byl asi následující:

KROK 1. Vypočteme derivaci f'x(x).

KROK 2. Vyšetříme rovnici f'x(x) = 0 a najdeme všechny její kořeny, nechť to jsou čísla x1,x2,...,xn.

KROK 3. Vypočteme funkční hodnoty f(a),f(b),f(x1),...,f(xn).

KROK 4. Najdeme nejmenší z hodnot vypočítaných v kroku 3.

Je zřejmé, že i v tak jednoduché úloze mohou vznikat dosti velké problémy:

1. Funkce nemusí mít vůbec derivace?

2. Není obtížnější najít řešení rovnice v kroku 2, než řešit samotnou původní úlohu?

3. Pokud vyřešíme rovnici v kroku 2 může existovat nekonečně mnoho jejích řešení a jak potom organizovat jejich výběr v kroku 3 a 4?

Je pochopitelné, že pro funkce mnoha proměnných je situace ještě nepoměrně složitější. Důležitou roli zde sehrává pojem gradientu funkce, což je vektor sestavený z parciálních derivací funkce v zadaném bodě. Z tohoto hlediska pro lineární cílovou funkci plyne, jelikož její gradient je konstantní a tedy nezávisí na konkrétním bodě, že maximum nebo minimum nemůže existovat ve vnitřním bodě množiny přípustných řešení (t.j. takových řešení, která vyhovují omezujícím podmínkám úlohy). Později se k této problematice ještě vrátíme při definici množiny přípustných řešení a zformulujeme základní větu lineárního programování, která nám umožní přejít z nekonečné množiny přípustných řešení k analýze konečné množiny plánů (bazických řešení) dané úlohy.

4.1.2. Geometrická interpretace úlohy LP a geometrická metoda řešení.

Rozeberme si nyní jednoduchou úlohu LP pro dvě proměnné a snažme se pochopit její geometrický smysl. Analogicky tak můžeme snadno získat představu i o tom, co se děje v případě úloh s více proměnnými.

m a x {x1 + x2 )

3*x1 + 5*x2 <=15 , x >= 0

-x1 + x2 <=2

10*x1 + 7*x2 <=35

-x1 - x2 <=-1

Jak víme z kursu analytické geometrie, jednotlivé rovnice v omezujících podmínkách vyjadřují přímky v rovině X1X2, nerovnice pak poloroviny. Více omezujícím podmínkám pak odpovídá průnik jednotlivých polorovin a ten (pokud není prázdnou množinou) tvoří mnohoúhelník. Kterou z polorovin nerovnice vyjadřuje zjistíme tak, že do nerovnice dosadíme libovolný bod, který neleží na sledované hranici poloroviny, t.j. nesplňuje podmínku rovnosti. Pokud se nejedná o poloroviny, jejichž hraniční přímka prochází počátkem, je vhodné dosazovat počátek souřadnic. Množina přípustných řešení je znázorněna na obrázku č.32.

Analogická situace nastane v případě n proměnných. Přípustnou množinou řešení bude mnohostěn neboli polyedr.

Obraťme nyní pozornost na výzkum cílové funkce. Označme její hodnotu v některém bodě jako d, pak

(4.1.2.1) x1 + x2 = d

je vlastně vyjádřením třídy vzájemně rovnoběžných přímek v rovině - vrstevnic plochy, která je určena rovnicí

x0 = x1 + x2

Řešení úlohy LP nyní můžeme zformulovat takto - "Nalezněte maximální hodnotu d, pro kterou má přímka, určená rovnicí 4.1.2.1 neprázdný průnik s polyedrem, určeným omezujícími podmínkami úlohy."

V našem příkladě můžeme sestrojit nějakou přímku z dané třídy přímek a konstruovat rovnoběžky tak, aby s množinou přípustných řešení měly ještě neprázdný průnik. Je vidět, že tímto bodem na obrázku č.32 je bod A. Tento bod je průnikem přímek

3*x1 + 5*x2 = 15 10*x1 + 7*x2 = 35

Nyní, můžeme vyřešit soustavu dvou rovnic pro proměnné x1 a x2 a získame souřadnice optimálního řešení A(70/29;45/29) nebo (2.4137931034;1.5517241379). Z těchto hodnot vypočteme i hodnotu cílové funkce na optimálním řešeni jako 115/29 nebo číselně 3.9655172414.

Obr. 32

Samotný postup a výpočet pro nás nebyly ani tak důležité jako některá fakta, kterých jsme si museli všimnout a které mají platnost i u úloh s více než dvěma proměnnými:

1. Množinou přípustných řešení je polyedr.

2. Extrém cílové funkce se dosahuje ve vrcholu.

Na základě těchto znalostí není problém vytvořit celou řadu metod a procedur, které nám umožní číselně vyřešit úlohu LP. Obecnými vlastnostmi těchto metod jsou:

1. Popsat vrcholy polyedru.

2. Algoritmizovat jejich srovnání z hlediska hodnoty cílové funkce.

I když se tato úloha jeví na první pohled velmi jednoduchá, problémy, do kterých se budeme dostávat, porostou s počtem proměnných a omezujících podmínek exponenciálně. Nejjednodušší je prostý výpočet a srovnání všech hodnot funkce ve vrcholech polyedru. Bohužel, již při řádově stovkách omezujících podmínek a tisících proměnných se dostaneme do časových problémů i na dobré výpočetní technice. Reálné úlohy mnohdy obsahují i desetitisíce a statisice proměnných a omezujících podmínek.

Další alternativou je metoda lokálního výběru a zlepšení, v podstatě se jedná o to, najít nějaké řešení a pak se jej pokusit v některém okolí zlepšit, toto zlepšené vzít za původní a tak pokračovat do té doby, dokud je to možné.

V našem výkladu se omezíme na dvě metody, které jsou navíc konečné (je možné použít i metody z oblasti konvexního programování - ty budou ovšem iterační)

- simplexová metoda - je nejpoužívanější metodou, je velmi jednoduchá, dobře se

programuje, někdy špatně konverguje

- metoda elipsoidů - je nejmodernější, má zaručenu nejvyšší rychlost konvergence v

nejhorším případě

V dalším textu dáme do značné míry přednost simplexové metodě, protože pravděpodobně ještě dlouhou dobu zůstane nejpoužívanější metodou pro řešení lineárních a linearizaci nelineárních úloh. V metodě elipsoidů se omezíme pouze na výklad některých základních myšlenek a na uvedení vzorců. Než se bezprostředně dostaneme k jednotlivým metodám, budeme se muset seznámit s některými pojmy, které budeme v budoucnu používat. Tomuto cíli slouží následující odstavec.

4.1.3. Konvexní polyedry a soustavy lineárních nerovnic.

Nechť Rn je n - rozměrným Euklidovským prostorem

Definice 4.1.3.1

Množina X ( Rn se nazývá konvexní, jestliže spolu s libovolnými svými dvěma body x1, x2 X obsahuje i jejich lineární kombinaci

x = ß.x1 + (1 - ß).x2 , kde 0 <=ß <=1

Definici je možné formulovat i geometricky a to tak, že množina je konvexní, pokud se svými dvěma body obsahuje i segment, který je spojuje.

Věta 4.1.3.1

Konečný průnik konvexních množin je opět konvexní množina.

Důkaz

Předpokládejme nejprve, že se jedná o průnik pouze dvou množin X = X1 n X2. Podle definice průniku množin množina X obsahuje body x1 a x2, které patří jak množině X1 tak i množině X2. Jelikož množiny jsou konvexní, pak i libovolná lineární kombinace těchto bodů patří současně oběma množinám a tedy i průniku těchto množin. Pokud je množin N můžeme jejich průnik vyjádřit jako průnik (N-1) množin s množinou N (tedy opět dvou množin) a důkaz je možné provést matematickou indukcí (pro dvě množiny je tvrzení dokázáno).

Tím je věta zcela dokázána.

Definice 4.1.3.2

Nadrovinou v prostoru Rn budeme nazývat množinu všech bodů x z Rn, která vyhovuje rovnici:

( p , x ) = c , kde p,c Rn.

Vektor p obyčejně nazýváme normálou nebo normálovým vektorem nadroviny.

Věta 4.1.3.2

Nechť A , B Rn jsou neprázdné,uzavřené,konvexní množiny, A n B = a množina A je navíc ohraničená. Pak existuje nadrovina s normálovým vektorem p # 0, taková, že pro libovolné vektory xA a yB platí následující vztahy:

( p , x ) <=c a ( p , y ) >= c

Důkaz

Definujme množinu M = {zRn: z = x - y , xA a yB }.Tato množina je neprázdná a konvexní. Z ohraničenosti množiny A pak plyne i uzavřenost množiny M. Navíc 0 nepatří množině M. Dále pro všechna bRn ,všechna zM a taková c, pro která platí, že b + c = se splňují následující vztahy:

( z - c , b ) >= 0

0 <=( z - c , - c ) = ( z , - c ) + c2 = ( x - y , - c )

a tedy

( x , c ) <=( y , c )

Tímto je tvrzení věty dokázáno.

Definice 4.1.3.3

Hraničním bodem množiny X nazýváme takový bod množiny, v jehož libovolném okolí leží jak body patřící množině X, tak body, které množině X nepatří. Body, které patří množině a nejsou hraniční, nazýváme vnitřními body množiny.

Poznámka

Je-li množinou kruh, pak hraničními body jsou všechny body kružnice, která jej ohraničuje. Je-li množinou čtverec, pak hraniční množinu tvoří všechny body obvodu čtverce. Hraničními body segmentu jsou izolované body, které jej ohraničují, otevřený interval nemá hraniční body.

Definice 4.1.3.4

Bod nazýváme krajním bodem množiny, pokud jej nelze vyjádřit jako lineární kombinaci jiných dvou bodů dané množiny.

Poznámka

Je-li množinou kruh, pak každý hraniční bod je i krajním bodem. Čtverec má pouze čtyři krajní body, zatímco hraničních bodů má nekonečně mnoho. Krajními body čtverce jsou jeho vrcholy.

Věta 4.1.3.3

Každá neprázdná, uzavřená, konvexní množina má alespoň dva krajní body.

Definice 4.1.3.5

Ohraničená konvexní množina, která má konečný počet krajních bodů, se nazývá konvexním polyedrem.

Věta 4.1.3.4

Množina všech přípustných řešení úlohy lineárního programování je konvexní a uzavřená.

Důkaz

Omezující podmínky úlohy lineárního programování jsou lineární rovnice a nerovnice. Ty jako takové určují konvexní množiny a jejich průnik je také konvexní množinou. Jelokož každá nadrovina je současně i opěrnou nadrovinou je množina přípustných řešení i uzavřená.

Definice 4.1.3.6

Nositelem hraničního bodu se nazývá množina všech omezujících podmínek, kterým tento bod vyhovuje ve formě rovnosti.

Jedná-li se o řádky matice A , které patří množině indexů S pak odpovídající submatici z těchto řádků budeme označovat jako AS a analogicky odpovídající část vektoru b označíme jako bS.

Definice 4.1.3.7

Hodností (rankem) matice A budeme nazývat číslo, které udává maximální počet lineárně nezávislých řádků nebo sloupců matice A a budeme pro tento fakt používat zápisu Rank A .

Věta 4.1.3.6

Bod x0 je krajním bodem množiny přípustných řešení úlohy lineárního programování právě když Rank A = n a přitom An.x0 = bn

Věta 4.1.3.7

Je-li množina přípustných řešení úlohy LP omezená, pak je konvexním polyedrem.

Věta 4.1.3.8

Má-li úloha lineárního programování optimální řešení, pak existuje i optimální řešení, které je krajním bodem množiny přípustných řešení.

Poznámka

Poslední věta je základní větou lineárního programování a na ni se opírá veškerá metodika řešení těchto úloh. Poslední věta nahrazuje problém řešení úloh lineárního programování na nekonečné množině problémem nalezení maxima nebo minima lineární cílové funkce na konečné množině krajních bodů konvexního polyedru.

4.1.4. Teorie duality a duální úlohy v lineárním programování.

Ukazuje se,že v lineárním programování existují celé řady úloh, které i když jsou svým způsobem jiné, mají hodně společných vlastností a umožňují obecně nahradit řešení jedné úlohy řešením úlohy jiné. Tyto úlohy se nazývají pak duálními úlohami.

Přímá úloha LP.

m a x ( c , x )

A .x <=b

Duální úloha LP.

m i n ( b , y )

AT .y = c , y >= 0

Jelikož nyní již umíme převíst úlohu lineárního programování na jakýkoliv tvar, pak pro nás nemůže být problémem vytvořit duální úlohu k jakékoliv úloze lineárního programování. Zásady jejich tvorby jsou asi tyto:

Je-li přímá úloha maximalizační je duální úloha minimalizační, Počet proměnných jedné úlohy je stejný jako počet omezujících podmínek druhé úlohy a naopak, pokud chybí omezující podmínka na nezápornost některé proměnné, pak se jí odpovídající omezující podmínka tvoří jako rovnost, matice omezujících podmínek duální úlohy je transponovaná, vektor pravých stran a cílová funkce si vymění svá místa při přechodu od jednoho typu úloh k typu druhému.

Obsahem teorie duality je zkoumání vztahů takto vytvořených úloh mezi sebou, jejich řešení, optimálních řešení apod. Teorie duality existuje i v jiných oblastech např. v nelineárním programování, ale je odpovídajícím způsobem složitější.

4.1.5. Základní věty teorie duality.

Označme jako R = {x: A.x <=b }množinu plánů přímé úlohy (někdy této množině říkáme také množina přípustných řešení) a jako P = {y: AT.y = b , y >= 0}

Optimálním plánem přímé úlohy nazveme jakýkoliv plán x*,který má tu vlastnost, že

pro libovolný jiný plán x platí:

( c , x ) <=( c , x*)

Optimálním plánem duální úlohy nazveme jakýkoliv plán y*,který má tu vlastnost, že

pro libovolný jiný plán y platí:

( b , y ) >= ( b , y*)

Věta 4.1.5.1

Nechť xR a yP jsou libovolnými plány přímé a duální úlohy LP, pak platí:

( c , x ) <=( b , y )

Důkaz

Jelikož xR , pak A .x <=b. Vynásobme nyní tuto nerovnost skalárně vektorem y>=0.

( b , y ) >= ( A .x , y ) = ( x , AT. y ) = ( x , c ) = ( c , x )

Což bylo třeba dokázat, věta tedy platí.

Věta 4.1.5.2

Nechť x*, y* jsou libovolné plány přímé a duální a nechť dále platí následující rovnost:

( c , x* ) = ( b , y* ),

pak x* je optimálním plánem v přímé úloze a y* je optimálním plánem v duální úloze.

Důkaz

Důkaz plyne z předcházející věty.

Věta 4.11 (věta o dualitě)

Mají-li obě duální úlohy plány, pak mají obě i optimální plány a přitom platí, že

( c , x* ) = ( b , y* )

Důkaz

Podle věty 4.9 je jasné, že pokud má duální úloha plán, pak je hodnota cílové funkce přímé úlohy shora omezená a tedy existuje optimální řešení. Je to důsledkem toho, že konvexní polyedr je konvexní množina a cílová funkce je spojitá a podle dříve uvedené věty i ohraničená. Analogickou teorii je možné zopakovat i pro duální úlohu. Označme nyní optimální řešení přímé úlohy jako x* a optimální řešení duální úlohy jako y*. Nyní zbylo dokázat, že na optimálních řešeních se dosahuje rovnosti cílových funkcí.

Předpokládejme, že tomu tak není a platí

( c , x* ) <=( b , y* ) ale potom platí také

( AT. y* , x* ) <=( b , y* ) a odtud dále plyne

A .x* <=b.

Vypočtěme vektor e: 0 <=A .e <=b - A .x* >= 0. Předpokládejme dále, že mezi komponentami vektoru c existuje alespoň jedna kladná, označme ji písmenem i , pak řešení x+i = x*i + ei, x+=x*, pro všechny ostatní komponenty je lepší než řešení x* a to je spor s předpokladem. Totéž je možné dokázat i pro situaci, kdy jsou všechny koeficienty cílové funkce záporné, potom je třeba vektor e určit ze vztahu - A .e <=b - A .x*. Věta je dokázána.

Věta 4.1.5.3 (věta o stabilitě)

Nechť x*, y* jsou optimální plány přímé a duální úlohy LP. V takovém případě je-li pro některé i: yi>= 0 pak odpovídající omezující podmínka se v přímé úloze splňuje jako rovnost:

aij .xj = bi

j

Důkaz

A .x* <=b Nerovnici vynásobíme vektorem y*>=0

( b , y* ) >= ( A .x* , y*) = ( c , x* )

Podle předchozí věty pak plyne, že

( c , x* ) = ( b , y* )

no a to znamená, že

( b , y* ) = ( A .x* , y*)

a tedy ( b - A .x* , y* ) = 0.

No a nakonec si stačí uvědomit, že skalární součin dvou vektorů se rovná nule a jeden z vektorů je nezáporný, právě když se rovná nule každý člen. Je-li tedy yi>=0 , pak nutně odpovídající člen musí být roven nule a tím je věta o stabilitě dokázána.

Z uvedených vět plyne celá řada závažných důsledků, které budeme v budoucnu používat. Zformulujme alespoň některé z nich:

Důsledek 1

Pokud má jedna z duálních úloh optimální plán, má optimální plán i druhá úloha.

Důsledek 2

Jestliže jedna z duálních úloh nemá žádný plán a druhá jej má, pak cílová funkce druhé úlohy neomezeně klesá nebo neomezeně roste.

Důsledek 3

Jestliže x@, y@ jsou plány přímé a duální úlohy a platí, že pokud y@i>=0, pak

aij .xj = bi,

j

pak x@, y@ jsou optimálními plány.

Cvičení

Sestavte duální úlohy k zadaným úlohám a analyzujte je z hlediska existence řešení a chování cílové funkce:

1.

m a x {x1 + x2 }

2*x1 + x2 <=4

x1 + 2*x2 <=4

2.

m a x {x1 + 3*x2 }

x1 - x2 <=3

-x1 + x2 <=4


3.

m a x {x1 }

x1 - x2 <=1

4. Řešte následující úlohu LP

m i n { i*xi }

x1 >= 1 , x >= 0

x1 + x2 >= 2

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

x1 + ...+ xn >= n

4.1.6. Analytické metody řešení úloh lineárního programování

Analytické metody řešení můžeme rozdělit zhruba do dvou skupin, jsou to metody finitní a jednak metody iterační. V této kapitole se budeme zabývat pouze finitními metodami, jako příklad iterační metody je možné uvést některé některou z metod konvexního programování, které budou uvedeny v příslušné kapitole. V následujícím textu se budeme zabývat dvěma finitními metodami. Podrobně pouze metodou simplexovou a okrajově metodou elipsoidů.

4.1.7. Úvod do teorie simplexové metody.

Simplexová metoda je nejznámější a nejpoužívanější metodou pro řešení problémů lineárního programování. Jejími nejdůležitějšími vlastnostmi jsou:

1. Konečnost. Prakticky to znamená, že pokud existuje optimální řešení, nalezneme je za konečný počet kroků výpočtu nebo zjistíme, že optimální řešení neexistuje.

2. Jednoduchost algoritmu. Všechny výpočty v simplexové metodě provádíme srovnáváním nebo výpočtem podle jednoduchých vzorců, které obsahují pouze algebraické operace sčítání, násobení, dělení a odčítání.

Obecný postup výpočtu:

1. Nalezení krajního bodu polyedru-výchozího plánu

2. Zhodnocení, zda tento plán je optimálním plánem

3. Není-li tento plán optimálním, nalezneme z okolních krajních bodů polyedru takový, kterým co nejvíce zlepšíme současný plán. Ten označíme za plán výchozí a přejdeme zpět ke kroku 2.

Podstatou simplexové metody je tedy přechod v prostoru od jednoho krajního bodu polyedru k jinému, vhodnějšímu, proto se někdy simplexové metodě také říká metoda postupného zlepšování plánu. Každý bod prostoru je možné popsat prostřednictvím určité soustavy souřadnic a přitom stejný objekt se bude v různých soustavách souřadnic jevit různě. Důležitou roli zde sehrává pojem nositele hraničního bodu. Uveďme si nyní jednoduchý příklad:

Matice A a vektor b

1 2 3 6
2 5 1 5

Nositelem hraničního bodu může být například matice

1 2
2 5

To znamená, že můžeme vybrat ve dvojrozměrném lineárním prostoru bázi (souřadnicovou soustavu), která je složena z vektorů-sloupců x1 a x2. Těmto vektorům-sloupcům odpovídají proměnné vektoru x (komponenty,souřadnice), které adekvátně nazýváme bazickými proměnnými. Jelikož má pro kanonickou úlohu LP platit

A .x = b

bude platit i

AS-1. A .x = AS-1.b

Po úpravě budou prvky lineárního prostoru (matice a vektor) vypadat následovně:

1 0 13 20
0 1 -5 -7

Odtud jsou zřejmé i hodnoty bazických proměnných x1 = 20 , x2 = -7. Nebazickou proměnnou je proměnná x3, která je rovna nule. Nedostatkem je to, že takové řešení je obvykle pro úlohy lineárního programování nepřípustné. Jiná by byla situace, kdybychom vybrali jako matici AS matici

1 3
2 1

V takovém případě by bazickými byly vektory-sloupce x1, x3 a jim odpovídající bazické proměnné. Dostali bychom jiný vrchol polyedru. Je pochopitelně jednodušší než vždy hledat inversní matici, použít vylučovací proceduru Jordana - Gausse pro soustavy lineárních rovnic. Pro zajímavost si uvedeme program, který řeší soustavy lineárních rovnic metodou Jordana -Gausse s úplnou pivotací:

Algoritmus a program metody Jordana-Gausse.

PROGRAM GAUS; 
USES PRINTER; 
LABEL 99; 
CONST MI=1E-4; 
TYPE MAT=ARRAY[1..100,1..100] OF REAL; 
VAR M,N,ND,MD,I,J,K,K1,N1:INTEGER; 
T,MAX:REAL;S:BOOLEAN;A:MAT;Z:ARRAY[1..100] OF REAL; 
BEGIN WRITE('ZADEJ POCET NEZNAMYCH,DIMENZI SLOUPCE A RADKU:');READLN(N,ND,MD); 
WRITELN('ZADEJ MATICI SOUSTAVY:'); 
FOR I:=1 TO ND DO BEGIN FOR J:=1 TO MD DO READ(A[I,J]);READLN END; 
FOR I:=1 TO ND DO BEGIN FOR J:=1 TO MD DO WRITE(LST,A[I,J]:9:2);WRITELN(LST) END; 
S:=FALSE;N1:=N+1;K:=1; 
WHILE K<N DO BEGIN FOR J:=K TO N DO BEGIN MAX:=0.0; 
FOR I:=K TO N DO BEGIN T:=A[I,J];IF ABS(T)>=ABS(MAX) THEN MAX:=T END; 
S:=(MAX>=-(MI)) AND (MAX<MI); 
IF S THEN GOTO 99; 
FOR I:=K TO N1 DO A[J,I]:=A[J,I]/MAX END;MAX:=0.0; 
FOR I:=K TO N DO BEGIN T:=A[I,K];IF ABS(T)>=ABS(MAX) THEN BEGIN MAX:=T; 
J:=I END END; 
S:=(MAX>=-(MI)) AND (MAX<MI); 
IF S THEN GOTO 99; 
IF J<>=K THEN FOR I:=K TO N1 DO BEGIN T:=A[J,I];A[J,I]:=A[K,I];A[K,I]:=T END; 
K1:=K+1;FOR I:=K1 TO N DO BEGIN T:=A[I,K]/MAX; 
FOR J:=K1 TO N1 DO 
A[I,J]:=A[I,J]-T*A[K,J] END;K:=K+1 END; 
I:=N; 
REPEAT Z[I]:=A[I,N1]/A[I,I];K:=I-1; 
FOR J:=1 TO K DO A[J,N1]:=A[J,N1]-Z[I]*A[J,I];I:=K 
UNTIL K=0; 
99:IF S THEN WRITELN('TAKOVOU SOUSTAVU NERESIM!!!') ELSE BEGIN 
WRITELN(LST,'RESENI:');FOR I:=1 TO ND DO BEGIN T:=Z[I]; 
WRITELN(LST,'X(',I:3,') =',T:9:2) END END END. 

Příklad vstupních dat:

3 3 4

1 2 5 7

4 0 2 4

1 5 1 3

Výstupní sestava:

1.00 2.00 5.00 7.00

4.00 0.00 2.00 4.00

1.00 5.00 1.00 3.00

RESENI:

X( 1) = 0.40

X( 2) = 0.28

X( 3) = 1.21

Program Gaus v jazyku JavaScript

4.1.8. Matematický popis bazických plánů

Metoda postupného zlepšování bazických plánů, t.j. simplexová metoda, je založena na celkem jednoduché myšlence přechodu od jednoho bazického plánu (vrcholu polyedru) k dalšímu a to takovému, který co nejvíce zlepší hodnotu cílové funkce. Rozdíl proti výše uvedené metodě Jordana-Gause je tedy pouze v tom, jakým způsobem se určuje v jednotlivých krocích, který z vektorů bude v bázi a který ne.

Definice 4.1.8.1

Plán kanonické úlohy LP se nazývá bazickým plánem, jestliže jemu odpovídající soustava vektorů sloupců je lineárně nezávislá a tvoří bázi prostoru řešení.

Věta 4.1.8.1

Je-li úloha lineárního programování přípustná, pak pro ni existuje bazický plán.

Věta 4.1.8.2

Vektor x je bazickým plánem tehdy a jen tehdy, je-li krajním bodem polyedru přípustných řešení.

Věta 4.1.8.3

Existuje-li optimální plán úlohy lineárního programování, pak existuje i bazický optimální plán.

Definice 4.1.8.2

Bazický plán úlohy lineárního programování se nazývá degenerovaný, jestliže počet nenulových souřadnic v bazickém plánu je menší než m.

Definice 4.1.8.3

Úloha lineárního programování se nazývá nedegenerovaná, jestliže každý její bazický plán je nedegenerovaný. V opačném případě se nazývá degenerovaná.

4.1.9. Simplexová metoda pro nedegenerované úlohy LP.

Nechť je zadána maximalizační úloha lineárního programování v kanonické formě. Zavedeme novou proměnnou x0

x0 = ( c , x )

upravíme tento vztah do stejného tvaru, který mají všechny ostatní omezující podmínky a to

x0 - ( c , x ) = 0

A .x = b

Vektor x = ( x0,x1, ...,xn) je nyní charakterizován ještě i hodnotou cílové funkce x0. Navíc proměnná x0 se vyskytuje pouze v první rovnici a ještě s koeficientem +1 a proto může být považována vždy za bazickou. Předpokládejme, že máme k dispozici nějaký bazický plán, který podle podmínek úlohy musí být nezáporný. Tento plán je charakterizován určitou bází, kterou tvoří vektory-sloupce i1,i2, ...,im . Těmto vektorům odpovídá určitá matice AS. Vytvořme následující matici

0 c1 c2 ... cn
b a1 a2 ... an

Jelikož soubor vektorů-sloupců s indexy i1,i2, ...,im je lineárně nezávislým, pak k matici AS musí existovat inverzní matice AS-1. Nyní můžeme zavést nejdůležitější pojem v simplexové metodě a to simplexovou tabulku. Simplexovou tabulkou nazveme matici

U = AS-1 .AD

Základní myšlenka simplexové metody spočívá v přechodu od jedné báze k jiné bázi a to tak, že soustava bazických vektorů se liší pouze v jednom vektoru. Základní otázkou je, který z ostatních vektorů (nebazických) do báze zavést a který z vektorů (bazických) z báze vyloučit. Bazický vektor poznáme v simplexové tabulce podle toho, že jeho sloupec obsahuje samé nuly a pouze jednu jedničku. Proti této jedničce je pak v prvním sloupci simplexové tabulky hodnota jí odpovídající bázové proměnné. Koeficienty cílové funkce jsou umístěny v prvním řádku simplexové tabulky a charakterizují gradient cílové funkce, t.j. směr největšího růstu. Tyto koeficienty jsou pochopitelně v každé bázi jiné. Nebazické proměnné jsou v daném bazickém řešení rovny nule, koeficienty nebazických proměnných v cílové funkci v dané bázi jsou obecně nenulové, koeficienty cílové funkce, které odpovídají bazickým proměnným, jsou nulové.

Z výše uvedených faktů vyplývá :

A. Pokud v některé bázi v cílové funkci neexistují záporné koeficienty, pak zavedením jakékoliv nebazické proměnné do báze nemůže hodnota cílové funkce vzrůst (je-li koeficient kladný ,pak při změně hodnoty nebazické proměnné z nuly na kladné číslo funkce poklesne).Jedná se tedy o optimální řešení.

B. Jestliže v dané bázi existují v cílové funkci záporné koeficienty u nebazických proměnných (u bazických existovat nemohou), pak zavedením odpovídajícího vektoru do báze hodnota cílové funkce vzroste.

Je rozumné se jeví vybírat sloupec - bazický vektor, který obsahuje nejmenší zápornou hodnotu koeficientu cílové funkce. Prakticky to znamená, že musíme dosáhnout stavu, kdy se z tohoto sloupce stane bazický vektor. To je takový vektor sloupec, ve kterém budou samé nuly a pouze v jednom řádku jednička. Zatím ovšem nevíme ve kterém.

Doposud jsme se orientovali pouze na růst cílové funkce. Nyní je třeba myslet i na to, aby nový bazický plán byl bazickým plánem, t.j. vyhovoval omezujícím podmínkám (toho je možné dosáhnout provedením ekvivalentních úprav charakteristických pro metodu Jordana-Gausse), ale navíc byl i nezáporný. Právě tato druhá podmínka nám bude diktovat, který z původních bazických vektorů z báze vyloučíme a nahradíme ho novým bazickým vektorem.

Předpokládejme, že jsme vybrali sloupec s indexem K a řádek s indexem S. Pak se při úpravách Jordana-Gausse jednotlivé vektory-řádky naší matice budou měnit podle vztahu:

ia = ia - Sa * ( aik / aSK)

To v prvé řadě vyžaduje, aby prvek aSK byl kladný a pokud chceme, aby zůstala zachována nezápornost prvního sloupce, musí platit, že

bS/aSK <=bj/ajK pro každé j.

Po této analýze můžeme zformulovat dvě základní pravidla pro simplexovou metodu, která určují výběr vektoru zařazovaného do báze a vektoru vylučovaného z báze a v simplexové tabulce, t.j. klíčového sloupce a klíčového řádku v simplexové tabulce.


Pravidlo 1.(Výběr klíčového sloupce)

===================================

Do báze zavádíme vektor, který má v prvním řádku simplexové tabulky minimální záporné číslo. Pokud takový vektor sloupec neexistuje, v simplexové tabulce je zobrazeno optimální bazické řešení.

Pravidlo 2.(Výběr klíčového řádku)

=================================

Pro vybraný klíčový sloupec vytvoříme podíly mezi prvky vektoru b a kladnými prvky klíčového sloupce (mimo první řádek simplexové tabulky!!!). Vybereme minimální podíl a vektor odpovídající tomuto minimálnímu podílu potom z báze vyloučíme.

Tato dvě pravidla aplikuje tak dlouho, dokud je to možné.

4.1.10. Simplexová metoda pro degenerované úlohy

V případě degenerovaných úloh lineárního programování se v průběhu výpočtu může stát, že při aplikaci druhého pravidla nebude jen jeden minimální podíl. Důsledkem této situace bude, že se v následujícím kroku objeví v simplexové tabulce v prvním sloupci alespoň jedna z bazických proměnných s hodnotou 0. V takovém případě v dalším kroku, přechodu od jedné báze k bázi druhé nedojde ke změně hodnoty cílové funkce. Je nebezpečí, že se budeme znovu vracet k bázím, které jsme již prohlédli (vzniká nebezpečí zacyklení algoritmu). Je více způsobů, jak této situaci čelit. Základem všech je upřesnění pravidel výběru klíčového sloupce a řádku tak, aby výběr byl jednoznačný. První pravidlo je možno přeformulovat následovně:

Pravidlo 1a.(Výběr klíčového sloupce)

===================================

Do báze zavádíme "první" vektor, který má v prvním řádku simplexové tabulky minimální záporné číslo. Pokud takový vektor-sloupec neexistuje, v simplexové tabulce je zobrazeno optimální bazické řešení.

Upravíme i druhé pravidlo tak, aby bylo jednoznačné:

Pravidlo 2a.(Výběr klíčového řádku)

=================================

Pro vybraný klíčový sloupec vytvoříme podíly mezi prvky vektoru b a kladnými prvky klíčového sloupce (mimo první řádek simplexové tabulky!!!) "první v pořadí" minimální podíl. Vektor, odpovídající tomuto minimálnímu podílu potom z báze vyloučíme.

Definice 4.1.10.1

Vektor a=(a1,a2,...,an) nazveme lexikograficky větší než nulový vektor, jestliže první nenulová komponenta vektoru a je kladná. Vektor a je lexikograficky větší než vektor b, jestliže vektor a - b je lexikograficky větší než nulový vektor.

Druhé pravidlo můžeme zformulovat také jinak (a v tomto tvaru ho budeme i používat):

Pravidlo 2b.(Výběr klíčového řádku)

=================================

Pro vybraný klíčový sloupec vytvoříme podíly mezi prvky vektoru b a kladnými prvky klíčového sloupce (mimo první řádek simplexové tabulky!!!) a vybereme minimální podíl. Pokud je řádků s minimálním podílem více, vybíráme lexikograficky minimální řádek. Vektor odpovídající tomuto řádku z báze vylučujeme.

Příklad.

Mějme zadánu standardní úlohu lineárního programování v následujícím tvaru

m a x {x1 + 2 * x2 + x3}

x1 + 2 * x2 <=10 , x >= 0

x2 + 3 * x3 <=12

Nejprve si vytvoříme ze standardní úlohy úlohu kanonickou a to přidáním přídatných proměnných x4 x5 .Dále vyjádříme jiným způsobem cílovou funkci.

x1 + 2 * x2 + x4 = 10 , x >= 0

x2 + 3 * x3 + x5 = 12

x0 - x1 - 2 * x2 - x3 = 0

Sestavíme simplexovou tabulku a všimneme si, že v simplexové tabulce již existují bazické vektory - sloupce:

b x1 x2 x3 x4 x5
c 0 -1 -2 -1 0 0
10 1 2 0 1 0
12 0 1 3 0 1

Jsme tedy v situaci, kdy již máme přímo výchozí bazické řešení a můžeme provádět optimalizaci, t.j. hledat optimální řešení. Výchozí řešení není optimální, protože v řádku cílové funkce (je označen jako c a někdy jej nazýváme řídícím řádkem) jsou záporné koeficienty u nebazických vektorů (vektory jsou označeny v záhlaví tabulky podle jednotlivých proměnných).

b x1 x2 x3 x4 x5
c 0 -1 -2 -1 0 0
10 1 2 0 1 0
12 0 1 3 0 1

V předchozí tabulce je silně vyznačen řídící řádek.Nyní můžeme použít první pravidlo a vybrat klíčový sloupec podle minimálního záporného koeficientu v cílové funkci:

b x1 x2 x3 x4 x5
c 0 -1 -2 -1 0 0
10 1 2 0 1 0
12 0 1 3 0 1

K určení klíčového řádku použijeme druhého pravidla. Vytvoříme a porovnáme podíly mezi prvky sloupce b a sloupce pod x2. Jedná se však pouze o druhý a třetí řádek simplexové tabulky, protože vektor x0 z báze nikdy nevylučujeme (jinak bychom ztratili možnost pracovat s hodnotou cílové funkce).

10 / 2 = 5.00 12 / 1 = 12.00

Minimální podíl se je ve druhém řádku a tedy z báze budeme vylučovat vektor-sloupec x4.

b x1 x2 x3 x4 x5
c 0 -1 -2 -1 0 0
10 1 2 0 1 0
12 0 1 3 0 1

Dalším krokem je provedení jedné iterace metody Jordana -Gausse tak, aby se z klíčového sloupce stal sloupec bazický.

b x1 x2 x3 x4 x5
c 10 0 0 -1 1 0
5 0,5 1 0 0,5 0
7 -0,5 0 3 -0,5 1

Hodnoty nebazických proměnných jsou rovny nule. Nyní vidíme, že je opět možné použít pravidlo první k výběru klíčového sloupce a následně pravidlo druhé k výběru klíčového řádku. Klíčovým řádkem může být pouze poslední, třetí řádek. Provedeme opět úpravu simplexové tabulky a získáme následující tabulku:

b x1 x2 x3 x4 x5
c 12,3 -0,16 0 0 0,84 0,33
5 0,5 1 0 0,5 0
2,3 -0,16 0 3 -0,16 0,33

Názorně vidíme,jak při jednotlivých krocích simplexové metody roste hodnota cílové funkce z hodnoty 0 na 10.00 a na 12.3 .

Ani v předchozí tabulce, která je vypočtena pouze přibližně, není optimální řešení, proto provedeme další optimalizační krok. Po úpravě získáme opět novou tabulku

b x1 x2 x3 x4 x5
c= 13,9 0 0,32 0 1 0,33
x1= 10 1 2 0 1 0
x3= 3,9 0 0,32 1 0 0,33

Toto řešení je již optimální. Můžeme je vypsat v obyčejné formě asi takto:

Hodnota cílové funkce na optimálním řešení činí 13.9 jednotek.

Proměnná x1 má hodnotu 10.

Proměnná x3 má hodnotu 3.9.

Všechny ostatní proměnné jsou nulové.

Příklad.(Degenerovaná řešení)

Mějme zadánu standardní úlohu lineárního programování v následujícím tvaru

m a x {x1 + 2 * x2 + x3}

x1 + 2 * x2 <=10 , x >= 0

x2 + 3 * x3 <=5

Nejprve vytvoříme ze standardní úlohy úlohu kanonickou přidáním přídatných proměnných x4 x5 a dále vyjádříme jiným způsobem cílovou funkci.

x1 + 2 * x2 + x4 <=10 , x >= 0

x2 + 3 * x3 + x5 <=5

x0 - x1 - 2 * x2 - x3 = 0

Sestavíme simplexovou tabulku a všimneme si, že v simplexové tabulce již existují bazické vektory - sloupce. Výběr klíčového sloupce je jednoznačný - klíčovým sloupcem je třetí sloupec x2. Klíčovým řádkem může být stejně druhý i třetí řádek. Pokud použijeme pravidlo 2b o lexikograficky minimálním řádku, vybereme třetí řádek v simplexové tabulce.

b x1 x2 x3 x4 x5
c 0 -1 -2 -1 0 0
10 1 2 0 1 0
5 0 1 3 0 1

Vyloučíme tedy z báze vektor , odpovídající proměnné x5 a zavedeme do báze vektor, který odpovídá proměnné x2. Získáme následující simplexovou tabulku:

b x1 x2 x3 x4 x5
c 10 -1 0 5 0 2
0 1 0 -6 1 -2
5 0 1 3 0 1

Tato tabulka ukazuje, jak vypadá degenerované řešení. Ve sloupci b se objevuje u jedné bazické proměnné nulová komponenta. To znamená, že i když je proměnná x4 bazickou, má hodnotu nula! Proto se v příštím kroku při změně báze nezmění hodnota cílové funkce.

b x1 x2 x3 x4 x5
c 10 0 0 -1 1 0
0 1 0 -6 1 -2
5 0 1 3 0 1

Provedeme tedy ještě jeden optimalizační krok:

b x1 x2 x3 x4 x5
c 11,66 0 0,33 0 0 0,33
x1 = 10 1 2 0 1 0
x3 = 1,66 0 0,33 1 0 0,33


V tomto konkrétním případě jsme obdrželi již optimální řešení.

4.1.11. Metoda nalezení výchozího bazického plánu

V předchozím případě jsme měli již při formulaci úlohy k dispozici bazický plán. Tato situace se však často neopakuje. Obrovskou výhodou simplexové metody je především to, že ona sama nám umožní nejen vyřešit problém optimalizace, pokud máme k dispozici výchozí bazický plán, ale umožní nám tento plán i najít. Pokud bude mít úloha tvar kanonické nebo smíšené ĺohy lineárního programování, pak již nebudeme mít bazický výchozí plán bezprostředně k dispozici.

V tomto případě postupujeme obvykle tak, že k omezujícím podmínkám typu rovnost přidáme tzv. pomocné proměnné, které označíme jako vektor v a k omezujícím podmínkám typu větší nebo rovno přidáme nejprve přídatné proměnné s koeficientem -1, tím tyto podmínky převedeme na rovnost a opět použijeme pomocných proměnných v. Řešíme pak nejprve pomocnou úlohu s cílovou funkcí

m a x {- v1 - v2 - ...- vS }

a našimi doplněnými podmínkami. Proměnné v by mohly být bazickými, ale vyskytují se v pomocné cílové funkci, proto je třeba je nejprve vyjádřit prostřednictvím nebazických proměnných. Původní cílovou funkci udržujeme v simplexové tabulce, abychom později nemuseli zvlášť přepočítávat její koeficienty v nové bázi.

Mohou nastat dvě alternativy - hodnota pomocné cílové funkce se rovná při optimálním řešení nule, pak všechny pomocné proměnné se rovnají nule a v simplexové tabulce máme výchozí bazický plán původní úlohy. V takovém případě můžeme v dalším výpočtu opustit pomocnou úlohu, pomocné proměnné a vrátit se k řešení původní úlohy.

- Hodnota pomocné cílové funkce je při optimálním řešení menší než nula, nepodařilo se tedy vynulovat všechny pomocné proměnné a to znamená, že konvexní polyedr řešení původní úlohy je prázdná množina.

Nemůže nastat situace, ve které by hodnota pomocné cílové funkce byla kladná!!! A to z toho důvodu, že všechny (i pomocné ) proměnné jsou nezáporné. Pomocná úloha má tedy vždy optimální řešení.

Příklad.

Nechť je zadána následující úloha lineárního programování

m a x {4 * x1 + 4 * x2 }

2 * x1 + x2 = 1 , x >= 0

x1 + 2 *x2 = 1,


Přidáme k úloze pomocné proměnné v1 a v2.

2 * x1 + x2 + v1 = 1 , x >= 0

x1 + 2 *x2 + v2 = 1, , v >= 0

Vytvoříme pomocnou cílovou funkci

v0 = - v1 - v2 = -2 + 3 * x1 + 3 * x2

úpravou a převedením na odpovídající stranu rovnice pak získáme

v0 - 3 * x1 - 3 * x2 = - 2

a vytvoříme odpovídající simplexovou tabulku

b x1 x2 v1 v2
v -2 -3 -3 0 0
x 0 -4 -4 0 0
1 2 1 1 0
1 1 2 0 1

Po úpravě se simplexová tabulka změní na následující tabulku:

b x1 x2 v1 v2
v -0,5 0 -1,5 1,5 0
x 2 0 -2 2 0
0,5 1 0,5 0,5 0
0,5 0 1,5 0,5 1

Ve výše uvedené tabulce opět vybereme obvyklým způsobem klíčový řádek a klíčový sloupec a provedeme další optimalizační krok

b x1 x2 v1 v2
v 0 0 0 1 1
x 2,66 0 0 1,33 1,33
0,33 1 0 0,66 -0,33
0,33 0 1 -0,33 0,66

V této, poslední tabulce je hodnota pomocné cílové funkce rovna nule a v tabulce se tedy nachází optimální řešení pomocné úlohy a současně i výchozí bazický plán původní úlohy. Opustíme tedy pomocné proměnné a pomocnou účelovou funkci a vrátíme se k naší původní úloze:

b x1 x2
x 2,66 0 0
x1 = 0,33 1 0
x2 = 0,33 0 1

V této simplexové tabulce již máme dokonce optimální řešení (koeficienty proměnných v cílové funkci jsou nezáporné a proto můžeme výpočet ukončit.

4.1.12. Duálně simplexová metoda

Souvislosti mezi duální a přímou úlohou v lineárním programování nám umožňují vytvářet i jiné metody než je metoda simplexová. Nebudeme se jimi nějak zvláště zabývat. Pro řešení celočíselných úloh se nám však bude hodit postup, který využívá duálně simplexová metoda.

Tato metoda je založena na tom, že v simplexové tabulce je uchována přímá úloha lineárního programování i duální úloha lineárního programování.Pokud celou simplexovou tabulku otočíme kolem hlavní diagonály dostaneme simplexovou tabulku pro duální úlohu v obvyklé formě. Je to však zcela zbytečné. Je třeba si uvědomit, že abychom měli přípustné řešení duální úlohy (nazývá se pseudoplánem), musí být vektor-řádek c (mimo prvek ve sloupci b) nezáporný. Je-li tedy vektor c i vektor b nezáporný je v tabulce bazický plán přímé úlohy a současně pseudoplán duální úlohy a jejich hodnota (v průsečíku řádku c a sloupce b) je stejná. Podle teorie duality máme tedy optimální bazický plán. Pokud je v tabulce bazický plán, může vypadat tabulka např. takto:

b x1 x2 x3 x4 x5
c 5 -1 0 -2 1 0
y1 3 0 1 2 4 0
y2 2 2 0 1 3 1

Tabulka s pseudoplánem, který není současně bazickým plánem, může vypadat následovně :

b x1 x2 x3 x4 x5
c 5 1 0 2 1 0
y1 -3 0 1 2 4 0
y2 -2 2 0 1 3 1

Je zřejmé, že je nám jedno, zda budeme vycházet z plánu nebo pseudoplánu a budeme se snažit přivést ekvivalentními úpravami tabulku do optimální podoby tak, aby v ní byl plán, který je současně i pseudplánem. Jak postupovat v případě plánu již víme. V případě, kdy známe pseudoplán, můžeme obrátit kroky simplexové metody. Vybereme nejprve řádek podle stejného pravidla, jakého používala simplexová metoda.

Pravidlo 3.(Výběr řádku duální metodou)

=====================================

V simplexové tabulce vybereme takový řádek, ve kterém je ve sloupci vektoru b nejmenší záporná komponenta. Bazický vektor odpovídající tomuto řádku, budeme vylučovat z báze.

Při výběru klíčového sloupce musíme opět věnovat pozornost tomu, aby zůstala zachována přístupnost pseudoplánu, to znamená, aby vektor c zůstal nezáporný. Mimo to se musí změnit znaménko koeficientu ve sloupci vektoru b. Z těchto důvodů můžeme vybírat v klíčovém řádku, který jsme vybrali podle pravidla 3, pouze sloupce se zápornými koeficienty a vytvářet opět podíly s koeficienty v řádku c cílové funkce. Zformulujme pravidlo výběru sloupce.

Pravidlo 4.(Výběr klíčového sloupce)

===================================

Nechť podle pravidla 3 byl vybrán řádek s.Prohlédneme vektor-řádek s simplexové tabulky a najdeme všechny indexy j:1<j<n, pro které je asj<0. Označme J množinu všech těchto indexů. Vektor-sloupec k, který zařadíme do báze, vybereme podle vztahu:

ck/ask = m a x {cj/asj }.

Může nastat obdobná situace jako u degenerovaných úloh řešených simplexovou metodou. V takových případech je možné vytvořit analogická jednoznačná pravidla pro výbět řádku a sloupce.

Příklad.

Mějme zadánu následující úlohu lineárního programování

m i n {2 * x1 + 3 * x2 + x3 }

s omezujícími podmínkami

x1 + x2 >= 2 , x >= 0

x2 + x3 >= 6

Pokud bychom řešili tuto úlohu klasicky simplexovou metodou, přidali bychom dvě přídatné proměnné, kterými bychom převedli úlohu na kanonický tvar. Pak bychom přidali dvě pomocné proměnné, řešili pomocnou úlohu, po jejím vyřešení bychom se vrátili zpět k řešení naší původní úlohy s původní cílovou funkcí.

Nyní budeme postupovat jinak. Nejprve převedeme cílovou funkci na maximalizační podle vztahu

m i n F (x) = - m a x {- F (x) },

Nerovnice vynásobíme číslem (-1), přidáme přídatné proměnné a získáme následující simplexovou tabulku

b x1 x2 x3 x4 x5
c 0 2 3 1 0 0
-2 -1 -1 0 1 0
-6 0 -1 -1 0 1

V takto sestavené simplexové tabulce je pseudoplán ( v prvním řádku cílové funkce jsou pouze nezáporné koeficienty u proměnných). Tento pseudoplán není plánem a nevyhovuje omezujícím podmínkám přímé úlohy (podmínce nezápornosti). Naší snahou bude, aby tyto podmínky byly splněny. Vybereme podle pravidla 3 klíčový řádek a pak podle pravidla 4 klíčový sloupec. Klíčový sloupec je vybrán podle pravidla -1 >= -3. Provedeme klasickou úpravu simplexové tabulky a získáme novou simplexovou tabulku:

b x1 x2 x3 x4 x5
c -6 2 2 0 0 1
-2 -1 -1 0 1 0
6 0 1 1 0 -1

Dále postupujeme tak, jak jsme byli zvyklí. Vybereme podle pravidla 3 klíčový řádek a podle pravidla 4 klíčový sloupec (jsou označeny v následující tabulce). Po transformaci tabulky budeme mít následující optimální řešení

b x1 x2 x3 x4 x5
c -10 0 0 0 2 1
2 1 1 0 -1 0
6 0 1 1 0 -1

Hodnota cílové funkce není -10, jak by se mohlo chybně zdát. Musíme změnit znaménko cílové funkce vzhledem na převod minimalizační úlohy na úlohu maximalizační.

Celkově ovšem situace není tak růžová, jak se může na první pohled zdát. To že jsme měli výchozí pseudoplán bylo dáno především zvláštním tvarem úlohy. Stačilo by, aby v cílové funkci byl jediný záporný koeficient a byli jsme namydlení. Vzniká tedy otázka nalezení výchozího pseudoplánu. Ta je však obecně tak složitá, že je lepší řešit obecně úlohu simplexovou metodou. Přesto však existují situace, kdy se používá duální simplex velmi efektivně. Tyto případy jsou popsány v následujícím odstavci.

4.1.13. Úlohy s rostoucím počtem omezujících podmínek.

Při řešení praktických úloh často dochází k následujícím situacím:

1. Omezujících podmínek je velmi mnoho.

2. Omezující podmínky se vzájemně vylučují, ale všechny nejsou stejně důležité. Je možné je uspořádat podle důležitosti a na splnění všech podmínek není bezpodmíněně nutné trvat.

3. Omezující podmínky vznikají až při znalosti tvaru optimálního řešení a těmto dalším podmínkám nalezené optimální řešení nevyhovuje.

Pokud bychom v těchto 3 případech řešili úlohy klasickým postupem simplexové metody, vedlo by to k tomu, že po každém vyřešení optimalizační úlohy by vznikla úloha nová, která by se musela řešit zcela znovu. Tento postup by byl zdlouhavý a velmi nepohodlný. Je jednodušší postupovat následujícím způsobem. Vezmeme určitý počet omezujících podmínek, buďto těch, které známe nebo těch, o kterých víme, že budou muset být splněny v každém případě a vyřešíme úlohu klasickou simplexovou metodou. Pak přidáme další podmínky, které známe nebo které vzniknou při pohledu na optimální, ale přesto nevyhovující, řešení Tím vznikne nová úloha a nová simplexová tabulka, ve které bude pseudoplán (protože v důsledku optimálnosti předchozího řešení bude vektor řádek c nezáporný), ale v důsledku nesplnění dalších podmínek nebude nezáporný vektor sloupec b. Nyní můžeme provést jeden nebo více kroků duálně simplexovou metodou a nevracet se znovu k původní formulaci úlohy.

Jediný problém, který zde vzniká, je ten, že omezující podmínky jsou na optimálním řešení zobrazeny v jiné bázi (soustavě souřadnic), než byly na počátku řešení. Z tohoto důvodu musíme v nové podmínce vyjádřit bazické proměnné prostřednictvím proměnných nebazických.

Příklad.

Mějme následující úlohu lineárního programování

m a x {3 * x1 + 2 * x2 + x3 }

s omezujícími podmínkami

x1 + x2 + x3 <=10

2 * x1 + 2 * x3 <=8 , x >= 0

Sestavíme simplexovou tabulku a vyřešíme tuto úlohu

b x1 x2 x3 x4 x5
c 0 -3 -2 -1 0 0
10 1 1 1 1 0
8 2 0 2 0 1

Vybereme klíčový sloupec a klíčový řádek

b x1 x2 x3 x4 x5
c 12 0 -2 2 0 1.5
6 0 1 0 1 -0.5
4 1 0 1 0 0.5

Označíme znovu klíčový sloupec a řádek a provedeme přepočet tabulky

b x1 x2 x3 x4 x5
c 24 0 0 2 2 0.5
6 0 1 0 1 -0.5
4 1 0 1 0 0.5

Nyní máme v tabulce optimální řešení x1 = 4 , x2 = 6 a hodnotu cílové funkce 24. Proměnná x3 je rovna nule, ale my jsme dospěli k názoru, že (např. třetí odběratel vody by měl dostat alespoň polovinu toho, co dostane druhý)

x3 >= 0.5 * x2,

a proto musíme zavést novou proměnnou x6 a vyloučit bazickou proměnnou x2 z omezující podmínky:

x2 + x4 - 0.5 * x5 = 6 = >= x2 = 6 - x4 + 0.5 * x5

a

3 - 0.5 * x4 + 0.25 * x5 - x3 + x6 = 0

po úpravě

- x3 - 0.5 * x4 + 0.25 * x5 + x6 = -3

Doplníme nyní do simplexové tabulky řádek a sloupec, který odpovídá proměnné x6 :

b x1 x2 x3 x4 x5 x6
c 24 0 0 2 2 0.5 0
6 0 1 0 1 -0.5 0
4 1 0 1 0 0.5 0
-3 0 0 -1 -0.5 0.25 1

V této simplexové tabulce máme pseudoplán a můžeme provést krok duálně simplexovou metodou. Vybereme proto klíčový řádek a klíčový sloupec a vypočítáme podle pravidel duálně simplexové metody následující tabulku:

b x1 x2 x3 x4 x5 x6
c 18 0 0 0 1 1 2
x2 = 6 0 1 0 1 -0.5 0
x1 = 1 1 0 0 -0,5 0.75 1
x3 = 3 0 0 1 0.5 -0.25 -1

V této simplexové tabulce je již optimální řešení doplněné úlohy. První odběratel dostane jednu jednotku, druhý šest jednotek a třetí tři jednotky, což už vyhovuje doplněné poslední podmínce. Tímto způsobem by bylo možné pokračovat i ve výpočtu i dále.

Modifikací této metody je metoda řezných nadrovin, která se používá především pro řešení kombinatorických problému, řešených v oblasti lineárního programování.

4.1.14. Metoda elipsoidů v lineárním programování.

Simplexová metoda byla jedinou a velmi používanou v šedesátých a sedmdesátých letech. Teprve v roce 1972 vznikla otázka, jak je to s efektivností simplexové metody. V průměru se ukazovalo, že při m omezujících podmínkách a n proměnných je počet iterací simplexové metody roven zhruba n2.m. V roce 1972 však byla sestavena američany V.Kleaemem a J.Mentim úloha lineárního programování, která k výpočtu spotřebovala exp(2n-1) iteraci. Tento příklad dokázal, že simplexová metoda má exponenciální "těžkost" a je tedy špatná. Další následná otázka, která vznikla bylo, zda je to vlastnost jenom metody nebo zda je to vlastnost celé třídy úloh lineárního programování. Tato otázka byla zodpovězena teprve v roce 1979 a byl v tehdejším SSSR vytvořen nový algoritmus, který byl nazván metodou elipsoidů.

Označme h = m a x {aij }A = {aij}i,j

Věta 4.1.14.1

Pro řešení obecné úlohy lineárního programování je postačujících O(n4 * (n+m) * ln (h * n)) elementárních operací.

Důkaz tohoto tvrzení nebudeme provádět, prostě nemáme na něj připraven matematický aparát. Přesto si řekneme některé hlavní myšlenky. Metoda se opírá o známou nerovnici Adamara. Je-li d maximem z absolutních hodnot všech subdeterminantů rozšířené matice soustavy rovnic, pak platí

ln (d * n ) <=n * ln ( h * n )

Dále jestliže má soustava nerovnic řešení, pak je možné je najít v kouli

E0 = {x:|| x ||<=d * sqrt(n) }

Pokud tedy soustava má řešení, pak poslední vztah je dovoluje lokalizovat a celý postup metody elipsoidů silně připomíná metodu půlení intervalu.

Zaveďme funkci

o (x) = m a x {( A .x )i - bi }

1<i<n

Jedná se v podstatě o odklon v bodě od řešení soustavy rovnic. Položme x0 = 0 a považujme tento bod za střed koule (elipsoidu). Pokud o (x0) = 0, pak je tento bod řešením soustavy. Pokud tomu tak není, najde se taková rovnice v soustavě, pro kterou je odpovídající oi kladné. Je zřejmé, že každý vektor, který by měl tuto nerovnici splňovat musí ležet v jednom ze dvou poloprostorů oddělených nadrovinou, odpovídající této podmínce. Průnik tohoto poloprostoru s elipsoidem musí tudíž obsahovat řešení. Aby byl algoritmus jednotvárný opíšeme tomuto průniku nový elipsoid s menším poloměrem a můžeme náš postup zopakovat.

Popišme nyní tento algoritmus formálním způsobem. Označme elipsoid

E = {y: y = x + B .z , ||z ||= 1 }

KROK 1. Pro výchozí x vypočítáme odchylku o. Je-li nulová získali jsme řešení a dále nepokračujeme.

KROK 2. Vypočítáme vektor ßk = ( ß1,ß2,...,ßn) , kde ßk = BTk .aS (S - číslo řádku, pro který nebyla splněna podmínka (viz. výše)). Pokud je tento vektor nulový, zakončíme výpočet, pokud není vytvoříme matici Źk s prvky gkij = ßki * ßkj.

KROK 3. Definujeme nový elipsoid pomocí vztahů

xk+1 = xk - [ (n+1) * ||ßk ||]-1 .BTk .ßk,

Bk+1 = (1 + (4 * n)-2)*n*(n2-1)-1/2*{Bk+ ||ßk|| -2*{[(n-1)/(n+1)]-1/2*BkŹk}.

Vracíme se zpět ke kroku 2 atd.

Vysoká efektivnost algoritmu je pouze zdánlivá. Již podle uvedených čísel je zřejmé, že v průměru je simplex lepší. Metoda elipsoidů je velmi výhodná pouze pro řešení úloh kombinatorického typu, kde simplexová metoda selhává. To je i důvodem, proč se tato metoda v běžné praxi nerozšířila tak, jak se původně očekávalo.

Dalším problémem je, že na rozdíl od simplexové metody zde vypočítáváme druhé odmocniny a použitá čísla nemusí být přesná. Také počet aritmetických operací pro výpočet odmocniny nespecifikujeme, i když jej provádíme pouze jednou (nezávisí tedy ani od omezujících podmínek ani od proměnných).

4.2. Speciální úlohy lineárního programování

V předcházejících odstavcích byly popsány obecné metody řešení úloh lineárního programování. Tyto metody jsou použitelné i v následujících modelech, ale jsou velmi neefektivní. Ukazuje se, že v některých případech, pokud má matice omezujících podmínek speciální tvar, mohou být použity jiné metody, které jsou daleko efektivnější a pohodlnější než simplexová metoda.

4.2.1. Obecná dopravní úloha

Dopravní úloha byla jednou z prvních úloh lineárního programování, která byla s úspěchem využita v praxi. Jde o následující problém:

Nechť je zadáno m míst S1 ,S2 , ...,Sm výroby homogenního výrobku (uhlí, cementu, hnojiv, mouky apod.), a jeho produkce v místě Si je ai jednotek (kg, litrů, tun ). Předpokládejme, že se tento výrobek spotřebovává v n místech Q1 ,Q2 , ...,Qn. Spotřeba v místě Qj je bj jednotek.

Cílem operace je sestavit takový plán přepravy homogenního produktu z míst Si do míst Qj , abychom uspokojili spotřebu, nepřekročili produkci a minimalizovali přepravní náklady. Abychom mohli pokračovat ve formalizaci této úlohy, potřebujeme znát ještě některé další údaje. Nechť cij je cena potřebná k přepravě jedné jednotky výrobku z místa jeho výroby Si do místa jeho spotřeby Qj.

Budeme dále předpokládat, že přepravní náklady závisí lineárně na přepravovaném množství (což obecně není vždy pravda).

Plánem přepravy budeme nazývat soubor čísel ( xij)i=1,2,...,m ,který vyhovuje následujícím podmínkám: j=1,2,...,n

(4.2.1.1) xij = ai a xij = bj a xij>= 0

Význam jednotlivých rovnic je zřejmý. Z místa Si se musí odvézt právě tolik produkce, kolik se tam vyrobí a do místa Qj se musí dovézt právě tolik, kolik se tam spotřebuje. Není možné převážet záporné množství materiálu. Toto je však možné pouze tehdy, je-li dopravní problém vyrovnaný nebo jinými slovy, když platí:

(4.2.1.2) ai = bj

Při plánu přepravy x můžeme vyjádřit celkové přepravní náklady vztahem:

(4.2.1.3) cij * aij

Konečná formulace matematického modelu dopravní úlohy je:

"Na množině všech souborů čísel, která vyhovují podmínkám 4.2.1 najděte takový soubor x, který minimalizuje vztah 4.2.3."

Pokud by nebyl splněn vztah 4.2.1.2 řešíme situaci tak, že zavedeme fiktivního dodavatele nebo fiktivního odběratele a specifikujeme jeho kapacitu tak, aby se problém stal vyrovnaný. Je jasné, že dodávka od fiktivního dodavatele znamená pro odběratele, že nic nedostane a dodávka fiktivnímu odběrateli znamená pro dodavatele, že zboží u něj zůstane ležet. Při nedodání zboží mohou vznikat doplnitelné náklady z deficitu a ty potom mohou být zařazeny do úlohy rozšířením matice C nákladů na přepravu a podobně lze v případě fiktivního odběratele ocenit náklady, které budou vznikat jednotlivým dodavatelům na skladování jednotky zboží. V takovém případě úloha typu dopravní problém získá širší kontext.

Pokud si vypíšeme pro konkrétní případ matici omezujících podmínek, zjistíme, že má např. následující tvar:

m = 3 n = 4

1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1

První tři omezující podmínky se týkají dodavatelů, druhé čtyři odběratelů ( pokud je mezi sebou navzájem zaměníme, nic se nestane). Sečteme-li první tři řádky matice A, dostaneme jednotkový vektor stejně tako když sečteme čtyři další řádky matice. Všimneme si i toho, že v matici jsou pouze jedničky a nuly a ještě toho, že v každém sloupci jsou právě dvě jedničky. Vektory řádky matice jsou tedy lineárně závislé a proto soustava m+n vektorů nemůže tvořit bázi v prostoru řešení. Je to způsobeno tím, že problém je vyrovnaný. Je možné prověřit, že libovolných m+n-1 řádků je lineárně nezávislých.

Z toho, co jsme nyní řekli, plyne, že báze této úlohy lineárního programování má m+n-1 bazický vektor a tedy i (při nedegenerovaném řešení) m+n-1 bazickou, nenulovou proměnnou.

První, co bychom mohli ze speciálního tvaru úlohy vytěžit, je, jak jednoduše získat výchozí bazický plán. Víme, že v simplexové metodě jsme jej museli složitě počítat. Pro zajímavost : u této úlohy by při třech dodavatelích a čtyřech odběratelích měla simplexová tabulka 12 normálních proměnných a 7 pomocných , což je celkem 19 proměnných!!!

4.2.2. Metody nalezení výchozího bazického plánu.

Metoda severozápadního rohu.

Nechť m = 5 , n = 4, a = (6,8,3,9,14) , b = (10,18,7,5) a matice sazeb za přepravu jednotky materiálu má následující tvar:

10 3 12 1
8 5 20 3
1 9 4 10
12 6 10 15
9 9 8 3

Sestavme si nejprve prázdnou tabulku z jednotlivých čtverečků. Čtverečky zorganizujeme do šesti řad po pěti čtverečcích. Do prvních pěti řad a čtyř sloupců zapíšeme do levého horního rohu sazbu a do posledních čtverečků ve sloupci a v řádku pak nabízená a požadovaná množství:

10 3 12 1 6
8 5 20 3 8
1 9 4 10 3
12 6 10 15 9
9 9 8 3 14
10 18 7 5 40

Metoda severozápadního rohu funguje tak, že si nejprve vybereme levé horní pole tabulky (severozápadní roh - odtud název metody) a obsadíme je největší možnou hodnotou.

Součet obsazených polí v řádku musí být roven obsahu posledního pole v tomtéž řádku a současně součet obsazených polí ve sloupci musí být roven obsahu pole v posledním řádku odpovídajícího sloupce. Kromě toho mohou být v tabulce pouze nezáporné hodnoty.

Abychom dodrželi tyto požadavky, musíme umístit do levého horního pole minimum z hodnot 6 a 10 t.j. 6. V takovém případě jsou ale vyčerpány kapacity prvního dodavatele dodávkou prvnímu odběrateli a do všech ostatních polí první řádku napíšeme nuly. Požadavek prvního odběratele je třeba snížit o oněch šest jednotek, které již dostal. Prvním řádkem tabulky se již nemusíme zabývat a ve zbylé tabulce odpovídá severozápadnímu rohu pole (2,1). Situaci znázorňuje následující tabulka

10 3 12 1 6
8 5 20 3 8
1 9 4 10 3
12 6 10 15 9
9 9 8 3 14
10 18 7 5 40

Do pole (2,1) můžeme zapsat pouze 4 jednotky a tím vyčerpáme požadavky prvního odběratele, zbytek prvního sloupce vyplníme nulami a prvním sloupcem se již nebudeme zabývat. Kapacitu druhého dodavatele snížíme o čtyři jednotky a novým severozápadním rohem se stane prvek tabulky (2,2).

10
6
3
0
12
0
1
0
(6)
8
4
5
20
3
4 (8)
1
0
9
4
10
3
12
0
6
10
15
9
9
9
8
3
14
(4) (10) 18 7 5 40

Stejným způsobem můžeme postupovat dál a nakonec získáme následující tabulku, ve které je již celé výchozí bazické řešení. Toto řešení splňuje omezující podmínky,( tak bylo konstruováno) a navíc obsadilo nenulovými hodnotami právě požadovaných m+n-1 prvků tabulky, což znamená, že je to skutečně bazické řešení.

10
6
3
0
12
0
1
0
6
8
4
5
4
20
0
3
0
8
1
0
9
3
4
0
10
0
3
12
0
6
9
10
0
15
0
9
9
0
9
2
8
7
3
5
14
(4) (10) (18) (7) (5) 40

Pokud by se jednalo o nevyrovnaný dopravní problém, pak by tato konstrukce řešení neměla úspěch. Existují ovšem i degenerované úlohy a právě u těch se může stát, že je obsazeno méně než m+n-1 polí. Není obtížné dokázat, že platí následující věta:

Věta 4.2.2.1

Dopravní úloha je degenerovaná tehdy a jen tehdy, když součet prostředků některých dodavatelů je roven součtu požadavků některých odběratelů.

Pokud změníme kapacity dodavatelů z předcházejícícho příkladu,situace se projeví v následující tabulce takto:

10
10
3
0
12
0
1
0
10
8
0
5
4
20
0
3
0
4
1
0
9
3
4
0
10
0
3
12
0
6
9
10
0
15
0
9
9
0
9
2
8
7
3
5
14
10 18 7 5 40

Vidíme, že v tomto případě bude obsazených polí o jedno méně a to je tedy m+n-2. Obecně však stupeň degenerace úlohy může být vyšší a obsazených polí může byt pouze m nebo n.

Vypočtěme ještě pro zajímavost hodnotu cílové funkce na získaném řešení (před úpravou pro degeneraci),rovná se 282.

Indexová metoda nalezení výchozího bazického plánu.

Protože jsme absolutně nevyužili matici sazeb nákladů za přepravu, je velmi pravděpodobné, že nalezené výchozí bazické řešení je na hony vzdáleno optimálnímu řešení. Nabízí se jiná možnost, jak zaplňovat tabulku, a sice ne z nějakého severozápadu nebo jihovýchodu, ale podle minimální sazby. V následující tabulce nezaplníme jako první pole (1,1) ale pole (1,4) nebo (3,1) a tak postupujeme dále:

10
0
3
1
12
0
1
5
6
8
0
5
8
20
0
3
0
8
1
3
9
0
4
0
10
0
3
12
0
6
2
10
7
15
0
9
9
7
9
7
8
0
3
0
14
10 18 7 5 40

Hodnota cílové funkce při tomto bazickém řešení je rovna 256, což je lepší, ale ne zas až tak podstatně. Předešlé metody patří spíše k těm horším. Následující dvě metody dávají obvykle mnohem lepší výsledky.

Vogelova aproximační metoda ( VAM ).

Jedná se o jednu z metod, která se v praxi poměrně dobře osvědčila a dává poměrně dobré a často i uspokojivé řešení. Pravidla této metody jsou následující:

KROK 1. Pro každý řádek a každý sloupec stanovíme diferenci. Diference je rozdíl mezi minimálním a druhým nejmenším prvkem v řádku nebo ve sloupci. Pokud jsou v řádku nebo ve sloupci dva minimální prvky, je diference rovna nule.

Vybereme řádek nebo sloupec s největší diferencí a v něm obsadíme maximální možnou hodnotou pole s minimální sazbou. Vyškrtneme řádek nebo sloupec, ve kterém jsme již vyčerpali kapacity, znovu vypočítáme diference a postupujeme tak do vytvoření bazického řešení.

KROK 2. Pokud existuje v kroku 1 několik řádků nebo sloupců se stejnou maximální diferencí, vytvoříme z těchto řádků a sloupců submatici a v ní obsadíme minimální prvek.

KROK 3. Pokud se ukáže, že v kroku 2 je minimálních prvků víc, vytváříme pro tyto prvky druhé diference jako rozdíl mezi druhou nejmenší sazbou v řádku (sloupci) a mezi nejmenší sazbou v kolmém sloupci (řádku). Vybereme prvek s druhou maximální diferencí a ten obsazujeme.

Vraťme se k našemu příkladu a vypočtěmě jej metodou VAM.

10
3
12
1
6 Diference

2

8
5
20
3
8 2
1
9
4
10
3 3
12
6
10
15
9 4
9
9
8
3
14 5
10 18 7 5 40
Diference 7 2 4 2

Nejvyšší diference je v prvním sloupci, minimální sazba je zde hodnota 1, a proto budeme obsazovat proměnnou x13.

10
3
12
1
6 Diference

2

8
5
20
3
8 2
1
3
9
0
4
0
10
0
3 3, x
12
6
10
15
9 4
9
9
8
3
14 5
10 18 7 5 40
Diference 7, 1 2, 2 4, 2 2, 2

Nyní má nejvyšší diferenci řádek 5. V něm je minimální sazba v poli (5,4) a můžeme do něho umístit maximálně pět jednotek.

10
3
12
1
0
6 Diference

2, 7

8
5
20
3
0
8 2, 3
1
3
9
0
4
0
10
0
3 3, x
12
6
10
15
0
9 4, 4
9
9
8
3
5
14 5, 1
10 18 7 5 40
Diference 7, 1 2, 2 4, 2 2, 2, x

Stejným způsobem pokračujeme dál a nakonec obdržíme následující výchozí bazické řešení:

10
0
3
6
12
0
1
0
6
8
5
5
3
20
0
3
0
8
1
3
9
0
4
0
10
0
3
12
0
6
9
10
0
15
0
9
9
2
9
0
8
7
3
5
14
10 18 7 5 40

Hodnota cílové funkce při tomto bazickém řešení je 219 (jednotek) a je to podstaně lepší výsledek než nám poskytly předchozí metody.

Berkova aproximační metoda.(BAM)

Tato metoda byla publikována autorem v roce 1986. Dává řešení srovnatelná s metodou VAM, mnohdy i lepší a její předností je, že je snadno programovatelná. Její postup je do určité míry analogický algoritmu Littla.

KROK 1. Provedeme redukci matice sazeb analogicky algoritmu Littla. Provedeme ohodnocení stupně nul v redukované matici.

KROK 2. Obsazujeme pole odpovídající nule s maximálním stupněm maximálním množstvím přepravovaného materiálu.

KROK 3. Vypustíme řádek nebo sloupec, který jsme vyčerpali, provedeme novou redukci matice sazeb, vypočítáme stupně nul a vracíme se ke kroku 2.

Metodu si přiblížíme opět na našem modelovém příkladě.

Matice sazeb má následující tvar:

10 3 12 1
8 5 20 3
1 9 4 10
12 6 10 15
9 9 8 3

Po redukci sazeb získáme matici ve tvaru:

9 2 8 0^2
5 2 14 0^2
0^5 8 0^1 9
6 0^3 1 9
6 6 2 0^2

Po výpočtu stupně jednotlivých nul vidíme, že stejně jako v metodě VAM budeme obsazovat pole s indexy (3,1) hodnotou 3 a přitom vyloučíme třetí řádek matice:

4 2 7 0^2
0 2 13 0^0
1 0^3 0^1 9
1 6 1 0^1

Nyní se však jedná o pole (4,2) ,což je již jiný postup proti metodě VAM. Výsledná tabulka vypadá stejně jako pro metodu VAM, ale rozhodně to není pravidlo, spíše náhoda.