Hlavní práce6914_xcerm68.pdf, 253.4 kB Stáhnout

(1)

Vysoká škola ekonomická v Praze Fakulta informatiky a statistiky

BAKALÁ Ř SKÁ PRÁCE

PRAHA 2007 Č erná Martina

(2)

Vysoká škola ekonomická v Praze Fakulta informatiky a statistiky

Katedra ekonometrie

Studijní obor: Statistika a ekonometrie

Generování úloh lineárního programování

Autor bakalá ř ské práce: Č erná Martina

Vedoucí práce: Doc. Ing. Milada Lagová, CSc.

Rok obhajoby: 2007

(3)

Čestné prohlášení:

Prohlašuji, že jsem bakalářskou práci na téma „Generování úloh lineárního programování“ vypracovala samostatně a veškerou použitou

literaturu a další prameny jsem řádně označila a uvedla v přiloženém seznamu.

V Praze dne 31. července 2007 Martina Černá

(4)

Ráda bych na tomto místě vyjádřila poděkování své vedoucí bakalářské práce paní Doc. Ing. Miladě Lagové, CSc., za vstřícnost, odbornou pomoc a za cenné rady pří zpracování bakalářské práce.

(5)

OBSAH

1 ÚVOD... 7

2 SIMPLEXOVÁ METODA ... 8

2.1 JEDNOFÁZOVÁ SIMPLEXOVÁ METODA... 9

2.1.1 Algoritmus jednofázové simplexové metody: ... 9

2.2 DVOUFÁZOVÁ SIMPLEXOVÁ METODA... 10

2.3 MOŽNOSTI ZAKONČENÍ VÝPOČTU VÚLOHÁCH LP... 10

2.3.1 Úloha LP má optimální řešení ... 10

2.3.2 Úloha LP má neomezenou účelovou funkci ... 11

2.3.3 Úloha nemá přípustné řešení ... 11

2.4 MATICOVÉ VYJÁDŘENÍ SIMPLEXOVÉ TABULKY... 11

2.5 ZÁKLADNÍ POJMY ………....14

2.5.1 Základní věta lineárního programování... 14

2.5.2 Přípustné řešení ... 14

2.5.3 Základní přípustné řešení... 14

2.5.4 Optimální řešení ... 14

3 GENEROVÁNÍ... 15

3.1 PRINCIP GENEROVÁNÍ ÚLOHY LINEÁRNÍHO PROGRAMOVÁNÍ... 15

3.1.1 Generování pseudonáhodných čísel... 15

3.1.2 Generování od výsledku k zadání ... 15

3.2 VÝPOČET ZADÁNÍ... 17

3.2.1 Vzorový příklad ... 18

4 GENEROVÁNÍ V PROGRAMU LPPRO ... 21

4.1GENEROVÁNÍ ÚLOH ŘEŠENÝCH SIMPLEXOVOU METODOU... 21

4.2VZOROVÉ PŘÍKLADY... 23

4.2.1 Vzorový příklad 1: jedno optimální řešení ... 23

4.2.2 Vzorový příklad 2: jedno optimální řešení ... 26

4.2.3 Vzorový příklad 3: neomezená hodnota účelové funkce... 28

4.2.4 Vzorový příklad 4: minimalizace účelové funkce... 30

4.2.5 Vzorový příklad 5: alternativní optimální řešení ... 32

4.3 VÝZNAM VOLBY MAXIMÁLNÍHO DETERMINANTU... 34

4.4 GENEROVÁNÍ DOPRAVNÍHO PROBLÉMU... 35

4.4.1 Obecná formulace dopravního problému ... 35

(6)

4.4.2 Věty... 36

4.4.3 Generování dopravního problému v programu LP ... 36

4.5 VYUŽITÍ GENEROVANÝCH ÚLOH... 38

5 ZÁVĚR... 39

LITERATURA ... 40

PŘÍLOHY………...42

(7)

1 ÚVOD

Úkolem této bakalářské práce je popsat postup generování úloh lineárního programování. Zaměřím se na obecný postup generování a na jeho praktické využití. Generování je realizováno ve výukovém programu LPPro, který je v rámci grantu FRVŠ vyvíjen na katedře ekonometrie VŠE Praha.

Druhá kapitola se zabývá stručným popisem simplexové metody a maticovým vyjádřením simplexové tabulky. Ve třetí kapitole je popsán obecný postup generování a ve čtvrté kapitole je popsáno generování v programu LPPro a generování dopravního problému. V závěru jsou stručně popsány možnosti využití generovaných úloh ve výuce lineárního programování.

(8)

2 SIMPLEXOVÁ METODA

Simplexová metoda je univerzální metodou řešení úloh lineárního programování.

Uvažujme obecný model úlohy LP v maticovém tvaru:

Ax R b

x ≥ 0 (2.1)

z = c^Tx…max kde je:

A … matice strukturních koeficientů aij typu m × n x … vektor proměnných xj typu n × 1

b … vektor pravých stran omezení bi typu m × 1 c^T … vektor cenových koeficientů cj typu 1 × n R … vektor relačních znamének ≤ | = | ≥ typu m × 1 z … účelová funkce

Abychom mohli použít simplexovou metodu, musí být splněny následující podmínky:

1) pravé strany všech omezení jsou nezáporné

2) soustava vlastních omezení je upravena na soustavu rovnic 3) soustava rovnic je v kanonickém tvaru

Matematický model úlohy lineárního programování musíme nejprve převést na soustavu rovnic s nezápornými pravými stranami. Soustavu rovnic dále opravíme na kanonický tvar. Každá rovnice (včetně účelové funkce) musí obsahovat jednu základní proměnnou. K úpravě použijeme tyto postupy:

1) omezení se zápornou pravou stranou vynásobíme (-1)

2) omezení typu ≤ vyrovnáme na rovnici přičtením přídatné proměnné 3) omezení typu ≥ vyrovnáme na rovnici odečtením přídatné proměnné

(9)

4) v rovnicích, kde chybí proměnné s jednotkovým vektorem koeficientů, přičteme pomocnou proměnnou

5) proměnné v účelové funkci převedeme na levou stranu

Nyní dostáváme výchozí řešení simplexové metody. Optimální řešení dále počítáme buď jednofázovou nebo dvoufázovou simplexovou metodou.

2.1

Jednofázová simplexová metoda

Tuto metodu použijeme, pokud je model (2.1) po vyrovnání na rovnice v kanonickém tvaru. To znamená, že soustava omezení obsahuje jednotkovou submatici strukturních koeficientů a účelová funkce je v anulovaném tvaru.

Tento model získáme, jsou-li všechna omezení úlohy (2.1) zadána jako nerovnice typu “≤“.

2.1.1 Algoritmus jednofázové simplexové metody:

1) určíme minimální koeficient v řádce účelové funkce g = min (zj) = zk j = 1, 2,…, n + m - je-li g ≥ 0, je řešení optimální a výpočet končí

- je-li g < 0, je proměnná xk vstupující a k-tý sloupec je klíčový 2) určíme velikost vstupující proměnné xk = t jako:

a ik b i

t = min

pro i = 1, 2, …, m; aik > 0

Je – li:

a qk b q t =

je q-tý řádek klíčový a základní proměnná v tomto řádku je proměnnou vystupující.

(10)

V případě, že aik ≤ 0 pro všechna i = 1, 2,…, m, je řešení přípustné pro jakékoliv kladné t a hodnota účelové funkce není omezena. Úloha má nekonečně mnoho přípustných řešení, nemá ale řešení optimální. Výpočet končí.

3) vypočteme nové řešení podle transformačních vzorců Gaussovy metody úplné eliminace ¹⁾

4) opakujeme postup od bodu 1.

2.2 Dvoufázová simplexová metoda

Touto metodou řešíme ty úlohy, které mají některá omezení zadána ve tvaru nerovnice typu ≥ nebo ve formě rovnice. K získání výchozího řešení použijeme v tomto případě další druh proměnných – pomocné proměnné.

Řešení je rozděleno do dvou fází:

1) řešení úlohy s pomocnými proměnnými

• sestavíme pomocnou účelovou funkci, ve které minimalizujeme součet všech pomocných proměnných

• řešíme simplexovou metodou podle pomocné účelové funkce

• tato fáze skončí, je-li pomocná účelová funkce rovna nule 2) řešení původní úlohy jednofázovou simplexovou metodou

2.3 Možnosti zakon č ení výpo č tu v úlohách LP

Výpočet simplexovou metodou může skončit třemi různými způsoby.

2.3.1 Úloha LP má optimální řešení

Řešení úlohy LP je optimální, jestliže jsou všechny pravé strany omezení nezáporné a v maximalizační úloze jsou všechny koeficienty v řádce účelové funkce nezáporné (v minimalizační nekladné).

1 Podrobněji viz. např. Lineární modely, Lagová M., Jablonský J., Praha 2004,

(11)

Pokud jsou v optimálním řešení všechny redukované ceny u nezákladních proměnných nenulové, je toto optimální řešení jediné. Jediné optimální řešení je vždy základní.

Pokud je některá redukovaná cena v optimálním řešení u nezákladní proměnné rovna nule, můžeme tuto proměnnou zvolit jako vstupující, obvyklým způsobem určíme vystupující proměnnou, přepočteme simplexovou tabulku a dostaneme základní řešení, které má stejnou hodnotu účelové funkce. Je to tedy také řešení optimální (alternativní optimální řešení). Dalším optimálním řešením (ale nezákladním) je každá konvexní kombinace vektorů dosud známých optimálních řešení. Těchto konvexních kombinací je nekonečně mnoho, tudíž je také nekonečně mnoho optimálních řešení.

2.3.2 Úloha LP má neomezenou účelovou funkci

Úloha LP nemá omezenou hodnotu účelové funkce, pokud jsou všechny koeficienty zvoleného klíčového sloupce nekladné. To znamená, že vstupující proměnná může nabývat libovolně velkých kladných hodnot, aniž by porušila podmínky nezápornosti. Není omezena ani hodnota účelové funkce a nelze tedy stanovit hodnotu jejího extrému.

Tato situace není při řešení praktických úloh příliš obvyklá.

2.3.3 Úloha nemá přípustné řešení

Úloha LP nemá přípustné řešení, je-li minimum pomocné účelové funkce větší než 0. Pokud nemá úloha LP přípustné řešení, nemá ani řešení optimální.

2.4 Maticové vyjád ř ení simplexové tabulky

1) Uvažujme pro jednoduchost model (2.1), ve kterém jsou všechna vlastní omezení zadána jako nerovnice “≤“:

Ax ≤ b

x ≥ 0 (2.2)

z = c^Tx…max

(12)

Tento model řešíme jednofázovou simplexovou metodou.

2) Výchozí řešení jednofázové simplexové metody je možno zapsat maticově:

A I b

–c^T 0^T 0

(2.3) kde je A … matice strukturních koeficientů aij typu m × n

I … jednotková matice vektorů přídatných proměnných typu m × m b … vektor pravých stran omezení bi typu m × 1

c^T… vektor cenových koeficientů cj typu 1 × n 0^T… m – složkový nulový vektor

0 … výchozí hodnota účelové funkce

V každé iteraci máme m základních proměnných, jejichž vektory tvoří bázi Bs (matice báze s-té iterace). K ní vypočteme inverzní matici Bs-1

. Aby tato inverzní matice Bs-1

existovala, musí být matice báze Bs regulární. Matici báze Bs rozšíříme o příslušnou část účelové funkce:

Bs 0

–c^TB 1

(2.4) kde je c^TB … vektor cen základních (bazických) proměnných.

Tuto matici invertujeme. Dostaneme rozšířenou inverzní matici báze v s-té iteraci Bs-1

:

Bs-1

0 c^TB· Bs-1

1

(2.5)

(13)

Násobením simplexové tabulky ve tvaru (2.3) rozšířenou inverzní maticí báze v s-té iteraci (2.5) dostaneme transformovanou simplexovou tabulku v s-té iteraci:

Bs-1

0 A I b

c^TB· Bs-1

1

·

–c^T 0^T 0

= Bs-1

·A Bs-1

Bs-1

·b c^TB· Bs-1

·A – c^T c^TB· Bs-1

c^TB· Bs-1

·b

(2.6) kde je

Bs-1

· A + 0 · ( – c^T) = Bs-1

matice transformovaných strukturních koeficientů Bs-1

· I + 0 · 0^T = Bs-1

inverzní matice báze v s-té iteraci Bs-1

· b + 0 · 0 = Bs-1

·b vektor transformovaných pravých stran c^TB · Bs-1

· A – c^T vektor redukovaných cen strukturních proměnných c^TB · Bs-1

· I + 1 · 0^T = c^TB · Bs-1

vektor duálních proměnných c^TB · Bs-1

· b + 1 · 0 = c^TB · Bs-1

· b hodnota účelové funkce

Vztahů (2.6) využíváme při generování úloh LP.

(14)

2.5 Základní pojmy

2.5.1 Základní věta lineárního programování

Věta: Má-li úloha lineárního programování optimální řešení, má také optimální řešení základní.

2.5.2 Přípustné řešení

Definice: Přípustné řešení úlohy lineárního programování ve tvaru (2.2) x = (x1, x2,…,xn+m)

je takové řešení, které vyhovuje všem podmínkám úlohy (všem vlastním omezením i podmínkám nezápornosti).

2.5.3 Základní přípustné řešení

Definice: Přípustné řešení úlohy x = (x1, x2,…,xn+m) je základním přípustným řešením úlohy lineárního programování (2.2), jestliže má nejvýše tolik kladných složek, kolik je lineárně nezávislých omezení, ostatní složky jsou rovny nule, přičemž vektory strukturních koeficientů odpovídající nenulovým složkám vektoru x jsou lineárně nezávislé.

2.5.4 Optimální řešení

Definice: Optimální řešení úlohy lineárního programování je přípustné řešení s nejlepší hodnotou účelové funkce (v případě maximalizace účelové funkce s nejvyšší hodnotou a v případě minimalizace s nejnižší hodnotou).

(15)

3 GENEROVÁNÍ

3.1 Princip generování úlohy lineárního programování

Úlohu lineárního programování je možno generovat metodou „od výsledku k zadání“. Metoda zaručuje řešitelnost úlohy, zajistí předem stanovené vlastnosti výsledku, např. celočíselnost řešení, jednoznačnost nebo naopak existenci alternativního optimálního řešení apod.

Generování úlohy lineárního programování vychází z velmi jednoduché úvahy:

• jestliže známe optimální řešení, můžeme pomocí vzorců z tabulky (2.6) vypočítat zadání, které mu odpovídá

• optimální řešení s požadovanými vlastnostmi tedy vygenerujeme (pomocí generátoru pseudonáhodných čísel) a vypočteme zadání 3.1.1 Generování pseudonáhodných čísel

Definice: Náhodným číslem nazveme veličinu, která má rovnoměrné rozdělení na intervalu (0,1) s hustotou pravděpodobnosti:

f (x) = 1, x ∈ (0, 1) f (x) = 0, jinak.

Pseudonáhodná čísla jsou generována na základě vztahu

x n+1 = f (xn), (3.1)

kde funkce f je deterministická. Tato čísla nejsou v pravém slova smyslu náhodná, jsou to tzv. pseudonáhodná čísla. Této pseudonáhodnosti, která s sebou nese možnost opakování stejné posloupnosti náhodných čísel, lze využít k získání stejných variant úloh s totožnými parametry

3.1.2 Generování od výsledku k zadání

Podle stanovených požadavků generujeme optimální řešení úlohy (2.2):

1) hodnoty proměnných – vektor xB

(16)

Vektor x lze rozdělit na dvě části:

• vektor xB [m x 1]

• vektor xN [(n – m) x 1]

Generujeme:

• m hodnot vektoru xB

• m indexů základních proměnných

• n – m hodnot vektoru xN hodnot doplníme nulami 2) matici strukturních koeficientů

• matici AN [m x (n-m)]

3) hodnoty koeficientů účelové funkce Opět je rozdělíme do dvou částí:

• vektor u^T je vektor koeficientů účelové funkce pod přídatnými proměnnými (stínové ceny)

• vektor r^T je vektor koeficientů účelové funkce pod strukturními proměnnými (redukované ceny)

Označíme: r^T= c^TB · Bs-1

· A – c^T (3.2)

u^T = c^TB · Bs-1

(3.3) kde:

r^T … je vektor koeficientů účelové funkce pod strukturními proměnnými u^T… je vektor koeficientů účelové funkce pod inverzní maticí báze (přídatnými proměnnými)

Ve vektoru r^T generujeme jen koeficienty u nezákladních proměnných, ostatní koeficienty jsou rovny nule. Proto můžeme jejich sloupce z matice A v dalších výpočtech vynechat.

Rovněž ve vektoru u^T generujeme jen koeficienty u nezákladních proměnných, ostatní koeficienty doplníme nulami.

(17)

Tyto vektory musí splňovat podmínky optimality:

1) pro maximalizaci účelové funkce: c^TB · Bs-1

· A – c^T≥ 0 c^TB · Bs-1 ≥ 0

2) pro minimalizaci účelové funkce: c^TB · Bs-1

· A – c^T≤ 0 c^TB · Bs-1 ≤ 0

3.2 Výpo č et zadání

Dopočítáváme tyto parametry úlohy lineárního programování:

• vektor c cenových koeficientů

• vektor b pravých stran

takové, aby byl vektor x = (xB, xN) optimem úlohy.

Nejdříve vytvoříme matici B tak, že nejdříve vygenerujeme indexy bazických proměnných. Pomocí indexů bazických proměnných vybereme z matice A submatici B a ověřujeme, zda je regulární.

Z takto zvolených matic B a Aa vektorů r^T a u^T lze sestavit právě jednu úlohu lineárního programování, jejímž optimem je vektor x.

Dostaneme tedy soustavu vztahů: r^T= c^TB · Bs-1

·A – c^T (3.2)

u^T= c^TB· Bs-1

(3.3)

xB = Bs-1

· b (3.4)

z nichž je možné vypočítat složky vektorů b a c. Vzhledem k tomu, že je matice BS regulární, existuje k ní inverzní matice Bs-1

. Ze vztahu (3.4) vypočteme složky vektoru b:

b = Bs· xB (3.5) Složky vektoru c^T a vektoru c^TB vypočítáme ze vztahů (3.3) a (3.4).

(18)

Dosazením získáme

c^T= u^T· A – r^T (3.6)

c^TB = u^T · Bs (3.7)

Poznámka: Vztah (3.6) můžeme také vyjádřit jen pro nezákladní proměnné.

Kvůli názornosti dalších výpočtů zde tuto úpravu neuvažujeme.

Postup generování ukážeme na jednoduché úloze lineárního programování řešené jednofázovou simplexovou metodou:

3.2.1 Vzorový příklad

Zadání úlohy x1 + x2 + 2x3 + x4 + 2x5 ≤ 260 x1 + 3x2 + x3 + 2x4 + 3x5≤ 710 x1 + x2 + x3 + 3x4 + 2x5 ≤ 25 xj ≥ 0; j = 1,2,3,4,5

z = 20x1 + 10x2 + 30x3 + 40x4 + 65x5 …max.

Řešení

Úlohu převedeme do kanonického tvaru a následně vyřešíme pomocí simplexové metody.

x1 + x2 + 2x3 + x4 + 2x5 + x 6 = 260

x1 + 3x2 + x3 + 2x4 + 3x5 + x7 = 710 (3.8) x1 + x2 + x3 + 3x4 + 2x5 + x8 = 250

xj≥ 0; j = 1, 2,…,8 -20x1 – 10x2 – 30x3 - 40x4 - 65x5 + z = 0

(19)

Výchozí simplexová tabulka

x1 x2 x3 x4 x5 x6 x7 x8 b

x6 1 1 2 1 2 1 0 0 260

x7 1 3 1 2 3 0 1 0 710

x8 1 1 1 3 2 0 0 1 250

z -20 -10 -30 -40 -65 0 0 0 0

Simplexová tabulka v s-té iteraci – optimální řešení

x1 x2 x3 x4 x5 x6 x7 x8 b

x6 0 0 1 -2 0 1 0 -1 10

x7 -1 1,5 -1 -3 0 0 1 -2 335

x5 0,5 0,5 0,5 1,5 1 0 0 0,5 125 z 12,5 22,5 2,5 57,5 0 0 0 32,5 8125 Generované hodnoty by byly: xB = [10; 335; 125]^T

u^T = [0; 0; 32,5]

r^T= [12,5; 22,5; 2,5; 57,5; 0 ], indexy bazických proměnných: 6, 7, 5.

Protože jsou mezi základními proměnnými i přídatné proměnné, uvažujeme rozšířenou matici A:

A =

 







 







1 0 0 2 3 1 1 1

0 1 0 3 2 1 3 1

0

1

2

1

2

1

(20)

Z matice A vybereme matici BS

BS =

2 0 0

3 1 0

2 0 1

a ověříme, zda je tato matice regulární

det BS = det

2 0 0

3 1 0

2 0 1

= 2 ≠ 0 matice je regulární

Podle vzorce Bs· xB = b dopočítáme složky vektoru b:

2 0 0

3 1 0

2 0 1

·















 125 335 10

=















 250 710 260

Podle vzorce u^T· Bs= c^TB dopočítáme složky vektoru bazických cen c^TB

[ 0; 0; 32,5] ·

2 0 0

3 1 0

2 0 1

= [0; 0; 65]

A podle vzorce u^T · A – r^T = c^Tdopočítáme složky vektoru cen c^T

[0; 0; 32,5] ·

2 3 1 1 1

3 2 1 3 1

2 1 2 1 1

= [32,5; 32,5; 32,5; 97,5; 65 ] = u^T · A

[32,5; 32,5; 32,5; 97,5; 65 ] - [12,5; 22,5; 2,5; 57,5; 0 ] =[20; 10; 30; 40; 65]

Vypočtené vektory jsou tedy:

b=















 250 710 260

c^TB = [0; 0; 65]

c^T= [20; 10; 30; 40; 65]

(21)

4 Generování v programu LPPro

Program LPPro umožňuje generovat zadání úloh:

• řešených simplexovou metodou

• dopravních problémů

Úlohy jsou generovány v sériích po 5, maximální počet úloh v jedné sérii je 25.

Program uloží a popř. vytiskne zadání úloh a jejich optimální řešení.

4.1 Generování úloh ř ešených simplexovou metodou

V programu LPPro musíme nejprve zvolit úvodní údaje úlohy, jako je počet omezení, počet proměnných a extrém funkce. Dále musíme zvolit parametry generované úlohy. První skupinou parametrů úlohy je typ úlohy.

Druhou skupinou parametrů je volba velikosti strukturních koeficientů, pravých stran, stínových cen a maximálního determinantu. Dále musíme zvolit počet úloh, které chceme generovat.

Úvodní údaje úlohy

Počet omezení 2 3

Počet proměnných 2 3 4 Extrém funkce max. min.

Parametry generované úlohy Typ úlohy

• jedno OŘ

• alternativní OŘ

• neomezeno

Generované optimální řešení je vždy celočíselné, volí se intervaly hodnot proměnných, stínových cen a strukturních koeficientů a numerická obtížnost výpočtu (pomocí determinantu).

(22)

Volba velikosti (celá čísla z intervalu):

Strukturních koeficientů

<0;2> <1;4> <-2;2> <- 4;4> <0;0>

Pravých stran <10; 50> <10; 95>

Stínových cen <11; 30> <11; 100>

Maximálního determinantu

2 3 4 5 6 7 8 9 10

Počet úloh

Po zadání parametrů program LP generuje požadovaný počet úloh.

Předtím, než program LP vygeneruje regulární matici báze v s-té iteraci může dojít k tomu, že vygeneruje matici singulární, kterou nelze použít a postup generování v dané sérii musí být opakován. Počet singulárních matic B vygenerovaných během jedné série je vidět v příloze 1, 3 a 4.

Pokud máme příliš specifické požadavky na generované úlohy, nebo požadujeme jejich velký počet, může se stát, že se programu nepodaří je v jedné sérii ani na 400 pokusů vygenerovat. Nebo může nastat situace, kdy je počet generovaných úloh menší než počet požadovaných úloh. V tomto případě je možno v generování pokračovat zadáním úlohy se stejnými parametry.

Program LPPro vygeneruje matici A, indexy bazických proměnných a vytvoří matici Bs. V případě, že se generování úlohy podaří (tzn., že je nalezena regulární matice Bs), vygeneruje vektor xB, vektor u^T (stínové ceny), vektor r^T (redukované ceny), matici A a indexy bazických proměnných.

Na základě generovaných hodnot program LP vypočte podle výše uvedených vzorců (3.5), (3.6) a (3.7) vstupní údaje.

Známe matici báze Bs a vektor xB, proto můžeme podle transformačního vzorce (3.5) vypočítat vektor pravých stran b.

1 5 10 15 20 25

(23)

Bs · xB = b

Vektor u^T známe a proto podle transformačního vzorce (3.6):

u^T· Bs= c^TB

vypočítáme vektor c^TB.

Použijeme transformační vzorec (3.7):

u^T · A – r^T = c^T

kde vektor r^T známe, tak dopočítáme vektor c^T.

Nyní máme dopočítané všechny složky a můžeme sestavit jak úvodní zadání simplexové metody, tak výsledky.

4.2 Vzorové p ř íklady

4.2.1 Vzorový příklad 1: jedno optimální řešení

V programu LPPro chceme vygenerovat úlohu, která má následující parametry:

• Počet omezení: 2

• Počet proměnných: 3

• Extrém funkce: maximum

• Typ úlohy: 1 optimální řešení

• Velikost strukturních koeficientů: aij ∈∈∈∈ < 0; 2 > pro všechna i = 1, 2 j = 1, 2, 3

• Velikost pravých stran: bi ∈∈∈∈ < 10; 95 > pro všechna i = 1, 2

• Velikost stínových cen: ui ∈∈∈∈ <11; 100 > pro všechna i = 1, 2

• Maximální determinant: 2

(24)

Úloha lineárního programování má jediné optimální řešení jen tehdy, pokud jsou v simplexové tabulce všechny stínové a redukované ceny u nezákladních proměnných při maximalizaci účelové funkce kladné, při minimalizaci záporné.

Program LP vygeneroval tyto hodnoty:

u^T = [55; 55]

r^T = [25; 0; 0]

xB = [40; 50]^T

indexy bazických proměnných: 3, 2 A =

Nyní můžeme vybrat z matice A matici Bs.

Bs =

Ověříme, zda je tato matice regulární

det BS = det = 2 ≠ 0 matice je regulární

Kdyby byla matice BS singulární, museli bychom generování opakovat.

Vektor x snadno stanovíme pomocí vektoru xBT

a indexů báze:

x = [0; 50; 40; 0; 0]

Hodnota účelové funkce z = u^T · BS · xB

z = [55; 55]

·

_{= 17050}

Vektory b, c^TB a c^T vypočítal program LP podle transformačních vzorců. Vyjdeme ze vzorce Bs· xB = b:

(25)

Odtud je:

b =

Dále vyjdeme ze vzorce u^T · Bs= c^TB

[55; 55]

·

= [220; 165]

c^TB = [220; 165]

Nyní vyjdeme ze vzorce: u^T ·A – r^T = c^T [55; 55] · = [165; 165; 220]

[165; 165; 220] - [25; 0; 0] = [140; 165; 220]

Vektor cenových koeficientů je tedy: c^T= [140; 165; 220].

Vypočtením vektorů b, c^TB a c^Tjsme dostali toto zadání úlohy LP:

Interpretace x1 x2 x3 Rel. b

Omezení 1 1 1 2 <= 130

Omezení 2 2 2 2 <= 180

Účelová

funkce 140 165 220 max.

Na tomto příkladě názorně vidíme aplikaci metody "od výsledku k zadání".

Nejdříve program LP vygeneroval matici A, vektory xBT

, u a r, což je v podstatě

"výsledek". Na základě toho vypočítal vstupní údaje, což je "zadání".

Vygenerované zadání příkladu a iterace výpočtu jsou uvedeny v příloze 5.

Zde je vidět, že žádný zlomek nemá jmenovatel větší než zvolený determinant, tj. 2.

(26)

4.2.2 Vzorový příklad 2: jedno optimální řešení Nyní si vygenerujeme úlohu, která má tyto parametry:

• Velikost strukturních koeficientů: aij ∈∈∈∈ < -2; 2 > pro všechna i = 1, 2 j = 1, 2, 3

• Velikost stínových cen: ui ∈∈∈∈ <11; 100 > pro všechna i = 1,2

• Maximální determinant: 4 Program LP vygeneroval tyto hodnoty:

u^T = [90; 40]

r^T= [0; 0; 75]

xB = [20; 60]^T

indexy bazických proměnných: 1, 2

A =

Bs = 



 



 −

1 1

2 2

a opět ověříme její regularitu

det BS = 4 ≠ 0 matice je regulární Dosazením do vzorce Bs· xB = b dostaneme:

(27)



 



 −

1 1

2

2 · =

b =

Pravá strana u prvního omezení vyšla záporná. To je ale nepřípustné, pravá strana nesmí být nikdy záporná. Proto musíme první omezení u zadání úlohy LP vynásobit (-1). Z omezení typu “≤“ dostaneme omezení typu “≥“.

Další postup je obdobný jako u předchozího příkladu.

Stanovíme vektor x:

x = [20; 60; 0; 0; 0]

Hodnotu účelové funkce z a vektory c^TB a c^Tdopočítal program LP podle známých transformačních vzorců.

z = 10400

c^TB = [-140; 220]

c^T = [-140; 220; -335]

Dostaneme toto zadání úlohy LP:

Interpretace X₁ X₂ X₃ Rel. b

Omezení 1 -2 2 -2 = 80

Omezení 2 1 1 -2 <= 80 Účelová

funkce -140 220 -335 max.

(28)

4.2.3 Vzorový příklad 3: neomezená hodnota účelové funkce Nyní vygenerujeme úlohu, která má tyto parametry:

• Typ úlohy: neomezeno

• Velikost strukturních koeficientů: aij ∈∈∈∈ < -2; 2 > pro všechna i = 1,2 j = 1,2,3

Pokud při dopočítávání vektoru b vyjde některá pravá strana záporná, musíme omezení vynásobit × (-1). Omezení typu “≤“ se nám změní buď na omezení typu “=“ nebo “≥“. Pokud chceme, aby měla generovaná úloha neomezenou hodnotu účelové funkce, volíme omezení typu “≥“. Nyní může, ale také nemusí, nastat situace s neomezenou hodnotou účelové funkce.

u^T = [15; 15]

r^T = [0; 65; 0]

xB = [90; 40]^T

Nyní vybereme matici Bs

BS =

(29)

a opět ověříme její regularitu

det BS = 2 ≠ 0 matice je regulární Dosazením do vzorce Bs· xB = b dostaneme:

· =

b =

Pravá strana u prvního omezení je záporná, první omezení vynásobíme × (-1). Z omezení typu “≤“ dostaneme omezení typu “≥“.

Další postup je opět obdobný jako u předchozích příkladů. x = [40; 0; 90; 0; 0]

z = 3900 c^TB = [30; 30]

c^T = [30; -20; 30]

Zadání úlohy LP:

Interpretace X₁ X₂ X₃ Rel. b Omezení 1 2 1 1 >= 170

Omezení 2 0 2 1 <= 90

Účelová

funkce 30 -20 30 max.

(30)

4.2.4 Vzorový příklad 4: minimalizace účelové funkce Nyní si uvedeme příklad na minimalizační úlohu:

• Extrém funkce: minimum

• Velikost strukturních koeficientů: aij ∈∈∈∈ < 1; 4> pro všechna i = 1,2 j = 1,2

• Velikost pravých stran: bi ∈∈∈∈ <10; 50> pro všechna i = 1,2

V minimalizační úloze jsou místo omezení typu “≤“ omezení “ ≥“. Jinak je postup shodný s postupem u maximalizačních úloh.

Generované hodnoty:

u1 = -10 u2 = -15

Vzhledem k tomu, že se jedná o úlohu s minimalizací účelové funkce, dostaneme v řádce z u optimálního řešení hodnoty menší nebo rovny 0.

Záporné hodnoty stínových cen mají význam při jejich interpretaci. Do vektoru u^T je ale vždy píšeme s kladnými znaménky.

u^T = [10; 15]

r^T = [0; 0]

xB = [30; 30]^T

(31)

Nyní vybereme matici báze BS. V tomto se případě se matice A a matice BS shodují. Je tomu tak proto, že je počet proměnných roven počtu omezení a indexy báze jsou 1, 2.

Bs =

a ověříme její regularitu

det BS = det = 2 ≠ 0 matice je regulární Známým postupem dostaneme:

x = [30; 30; 0; 0]

z = 2400

b =

c^TB = [25; 55]

c^T = [25; 55]

Zadání úlohy LP:

Interpretace X₁ X₂ Rel. b Omezení 1 1 1 >= 60 Omezení 2 1 3 >= 120

Účelová

funkce 25 55 min.

(32)

4.2.5 Vzorový příklad 5: alternativní optimální řešení

• Extrém funkce: minimum

• Typ úlohy: alternativní OŘ

• Velikost strukturních koeficientů: aij ∈∈ ∈∈ < 1; 4 > pro všechna i = 1, 2

j = 1,2,3

• Velikost pravých stran: bi ∈∈∈∈ < 10; 50 > pro všechna i = 1,2

• Velikost stínových cen: ui ∈∈∈∈ < 10; 30 > pro všechna i = 1,2

Všechny redukované ceny zi u alternativního optimálního řešení vyhovují podmínkám optimality a zároveň je alespoň jeden koeficient zi u nezákladní proměnné roven 0.

u1 = -10 u2 = -15 u^T = [10; 15]

r^T = [0; 0; 0]

xB = [40; 40]^T

indexy bazických proměnných: 3, 2

A =

Bs = 



 



 1 2

3 4

(33)

det BS = det = -2 ≠ 0 matice je regulární Známým postupem dostaneme:

x = [0; 40; 40; 0; 0]

z = 4600

b =

c^TB = [70; 45]

c^T = [70; 45; 70]

Zadání úlohy LP:

Interpretace X1 X2 X3 Rel. b Omezení 1 4 3 4 >= 280 Omezení 2 2 1 2 >= 120

Účelová

funkce 70 45 70 min.

(34)

4.3 Význam volby maximálního determinantu

Volbou maximálního determinantu matice báze Bs ve všech iteracích vlastně volíme numerickou obtížnost řešení úlohy lineárního programování.

Výpočet determinantu v jednotlivých iteracích si ukážeme na následujícím příkladu řešeném simplexovou metodou:

x1 x2 x3 x4 x5 x6 b t

x4 1 1 2 1 0 0 160 80

x5 1 3 1 0 1 0 100 100

x6 1 1 1 0 0 1 120 120

z -20 -10 -30 0 0 0 0

x3 0,5 0,5 0 0,5 0 0 80 160 x5 0,5 3,5 0 -0,5 1 0 20 40 x6 0,5 0,5 0 -0,5 0 1 40 80

z -5 5 0 15 0 0 2400

x3 0 -2 1 1 -1 -0,5 60

x1 1 5 0 -1 2 0 40

x6 0 -2 0 0 -1 1 20

z 0 30 0 10 10 0 2600

det B1 = 1 det B2 = 2 det B3 = 1

Při generování této úlohy jsme zadali požadavek, aby byl maximální determinant roven 2.

(35)

4.4 Generování dopravního problému

4.4.1 Obecná formulace dopravního problému

Dopravní problém je nejjednodušší úlohou, která patří do skupiny distribučních úloh. Jedná se o rozvržení rozvozu homogenního zboží od dodavatelů ke spotřebitelům tak, aby byly minimalizované celkové náklady, které souvisí s tímto rozvozem. Od obecné úlohy lineárního programování řešené simplexovou metodou se liší především svým matematickým modelem:

pro xij ≥ 0

pro i = 1, 2, …, m j = 1, 2,…, n kde je:

ai … kapacita i – tého dodavatele bj … požadavek j – tého odběratele

cij … cena distribuce jedné jednotky od i – tého dodavatele k j – tému odběrateli

m … počet dodavatelů n … počet odběratelů

(36)

4.4.2 Věty

Věta (1): Dopravní problém má přípustné řešení.

Věta (2): Dopravní problém má základní řešení.

Věta (3): Dopravní problém má optimální řešení.

K řešení dopravního problému není nutné použít simplexovou metodu.

Řešení pomocí této metody by bylo zbytečně příliš složité. Pro získání výchozího základního řešení existuje řada různých, tzv. aproximačních metod, jako je např. metoda severozápadního rohu, indexní metoda nebo Vogelova aproximační metoda. Následuje test optimality. V případě, že už se jedná o řešení optimální, výpočet končí. Pokud ne, vypočítáme nové základní řešení s lepší (resp. ne horší) hodnotou účelové funkce a znovu provedeme test optimality.

Také generování dopravního problému je jednodušší. V tomto případě není nutné použít metodu “od výsledku k zadání “, protože podle věty (3) existuje vždy optimální řešení.

4.4.3 Generování dopravního problému v programu LP

Opět si musíme zvolit úvodní údaje úlohy (počet dodavatelů a počet odběratelů) a parametry generované úlohy (výchozí řešení, vyrovnaná nebo nevyrovnaná úlohy). Dále volíme velikost cenových koeficientů, kapacit a požadavků a počet úloh, které chceme vygenerovat.

Úvodní údaje úlohy

Počet dodavatelů 2 3 4 5 6 7 8 Počet odběratelů 2 3 4 5 6 7 8

(37)

Parametry generované úlohy Výchozí řešení

• SZR

• indexní

• VAM Úloha

• vyrovnaná

• nevyrovnaná Volba velikosti

Cenových koeficientů

jednotky desítky stovky tisíce desetitisíce standardní

Kapacit a

požadavků

jednotky desítky stovky tisíce desetitisíce standardní

Počet úloh

Příklady generovaných úloh jsou uvedeny v příloze – viz příloha 6 a 7.

1 5 10 15 20 25

(38)

4.5 Využití generovaných úloh

Generované úlohy mají tu výhodu, že zvolením maximální hodnoty determinantu matice báze Bs zajistíme přibližně stejnou výpočetní obtížnost generovaných úloh. Zvolíme si, kolik úloh chceme vygenerovat, zadáme, jak by měl vypadat výsledek (velikost strukturních koeficientů, pravých cen, extrém funkce, atd.) a počítač vygeneruje zadaný počet úloh s přibližně stejnou náročností a s různým numerickým zadáním.

Generování úloh je tedy vhodnou pomůckou pro učitele. Lze ho využít např, při zkouškových testech nebo při zadávání domácích úkolů. Program vygeneruje až 25 úloh stejného typu s odlišným numerickým zadáním, což odpovídá počtu studentů na jednom cvičení. Každý student tedy může dostat jiné zadání. Generování usnadní práci učiteli i tím, že program vytvoří úlohu ve formě tabulky, která je připravena k vytisknutí. Ke každé úloze nám program poskytne výsledky. Učitel tedy nemusí každý příklad počítat a pomůže mu to především při opravování testů nebo domácích úkolů.

Dále mohou generované úlohy využívat studenti při samostatném procvičování. Program nejenže vygeneruje zadání úlohy, ale je možné vytisknout si i tabulky jednotlivých iterací. Tím si může student kontrolovat správnost výpočtu v každém kroku. Generování slouží jako vhodná náhrada cvičebnice.

(39)

5 ZÁV Ě R

Cílem této bakalářské práce bylo popsat postup generování úlohy lineárního programování a praktické využití těchto generovaných úloh.

Generování jsem realizovala v programu LPPro. V práci je popsán jak obecný postup generování úlohy lineárního programování, tak postup v programu LP.

V krátké podkapitole jsem také zmínila generování dopravního problému, které se liší od generování úlohy lineárního programování. V jedné kapitole jsem také krátce popsala simplexovou metodu.

V budoucnu by bylo možno uvažovat o generování jiných úloh matematického programování nebo i dalších disciplin operačního výzkumu.

(40)

LITERATURA

• Lagová, M. – Jablonský, J.: Lineární modely, Oeconomia, Praha 2004

• Jablonský, J.: Operační výzkum: Kvantitativní modely pro ekonomické rozhodování, Professional Publishing, Praha 2002

• Krupová, I. : Generování úloh řešitelných simplexovou metodou na počítači EC 1045, diplomová práce VŠE, Praha 1987

• Stupáková, J.: Programový systém pro řešení úloh z lineárního programování, diplomová práce VŠE, Praha 1986

(41)

P Ř ÍLOHY

(42)

Příloha 1

Generované úlohy lineárního programování – jedno OŘ.

(43)

Příloha 2

Generovaná úloha – tiskový náhled.

(44)

Příloha 3

Generované úlohy lineárního programování – alternativní OŘ.

(45)

Příloha 4

Generované úlohy lineárního programování – neomezená účelová funkce.

(46)

Příloha 5

Tiskový náhled – řešení po krocích.

(47)

Příloha 6

Dopravní problém – vyrovnaný.

(48)

Příloha 7

Dopravní problém – nevyrovnaný.