Software ve výuce operačního výzkumu na Univerzitě obrany

ÚVOD

Operační výzkum (z anglického operations research nebo operational research) započal jako interdisciplinární aktivita usilující o vyřešení komplexních vojenských problémů během druhé světové války. Ačkoli některé konkrétní modely a techniky využívané v operačním výzkumu byly rozpracovány již dříve, za počátky této disciplíny považujeme právě toto období. Jelikož se ukázalo, že metody operačního výzkumu jsou účinným nástrojem manažerského rozhodování, rozšířilo se po skončení války využití operačního výzkumu rovněž do civilní sféry. Během následujícího půlstoletí se operační výzkum vyvinul v plnohodnotnou akademickou disciplínu.

Na operační výzkum můžeme pohlížet jako na soubor matematických modelů a technik řešení komplexních manažerských problémů. Poskytuje kvantitativní analýzu problému, která umožňuje managementu přijmout objektivní rozhodnutí. Operační výzkum využívá znalosti a dovednosti z matematiky, inženýrství, obchodu, výpočetní techniky, ekonomie a statistiky a přispívá celé řadě aplikací v řízení, obchodu, průmyslu i armádě.

Klíčovou oblastí operačního výzkumu je matematické programování, zejména programování lineární. Na tuto oblast se primárně zaměřuje také předmět operační výzkum, jak je vyučován na Univerzitě obrany. Tento předmět je určen vojenským i civilním studentům ve studijních programech Řízení a použití ozbrojených sil a Bezpečnost a obrana. Jedná se o jeden z aplikovaných matematických předmětů vyučovaných Katedrou kvantitativních metod Fakulty vojenského leadershipu.

Aby studenti dokázali řešit úlohy lineárního programování, pochopit souvislosti a správně je interpretovat, je třeba, aby ovládali příslušné algoritmy, mezi nimiž ústřední postavení zaujímá simplexová metoda. Z tohoto důvodu se studenti v první řadě učí řešit úlohy ručně (metodou „tužka–papír“). Je ale logické, že v případě úloh většího rozsahu a zejména v praxi se od ručního řešení upouští ve prospěch specializovaných software. S některými (vybranými) z nich se studenti mohou seznámit právě v předmětu operační výzkum.

Existuje celá řada programů pro řešení úloh lineárního programování. Ty se mezi sebou liší např. dostupností (volně šířené programy vs. placené licence), cílovým užitím (programy výukové vs. profesionální), kapacitou (řešení úloh menšího – „školního“ – rozsahu vs. rozsáhlé reálné úlohy s mnoha parametry) atd. Při volbě vhodných ukázkových programů pro řešení úloh lineárního programování ve výuce operačního výzkumu jsme vzali v potaz zejména jejich dostupnost studentům Univerzity obrany a také jejich názornost při řešení těchto úloh.

Hlavním cílem předloženého textu je s pomocí vhodného ukázkového příkladu demonstrovat možnosti využití (vybraných) software ve výuce operačního výzkumu (konkrétně v oblasti lineárního programování). Vedlejšími cíli jsou dále (stručně) představit čtenáři operační výzkum jakožto vědeckou disciplínu a předmět vyučovaný na Univerzitě obrany a v neposlední řadě diskutovat přínosy (ev. náklady) zapojení zvolených software do výuky tohoto předmětu.

Tyto cíle kopíruje i struktura našeho příspěvku. První část textu představuje operační výzkum jakožto předmět a vědeckou disciplínu. Seznamujeme zde ve stručnosti čtenáře s původem operačního výzkumu, základními pojmy k němu se vázajícími, odvětvími, která pokrývá, a v neposlední řadě také s oblastmi aplikace jeho poznatků. Ve druhé části se zaměřujeme na předmět operační výzkum, který je vyučován na Univerzitě obrany, s důrazem kladeným na představení software používaných ve výuce. Ve třetí části navazuje ukázkový příklad, na němž demonstrujeme řešení pomocí zvolených metod – „ručně“ a s využitím software. V poslední části textu diskutujeme výhody a nevýhody spojené se zapojením software do výuky předmětu operační výzkum.  

1 OPERAČNÍ VÝZKUM JAKO VĚDNÍ DISCIPLÍNA

Za počátky operačního výzkumu obecně považujeme období druhé světové války, ačkoli některé jeho modely a techniky byly rozpracovány již dříve. Spojenecká vojska v tomto období čelila řadě komplexních problémů, které představovaly například otázky optimálního rozmístění radarů, rozmístění lodí zajišťujícího minimalizaci ztrát způsobených nepřátelskými ponorkami, strategie vzdušné obrany aj. Nalezení efektivního řešení takto složitých problémů vyžadovalo interdisciplinární přístup. Za tímto účelem byly v rámci ozbrojených sil, nejprve v Británii a poté i ve Spojených státech, vytvořeny speciální skupiny složené z expertů působících v rozličných vědních oborech. Jelikož tyto skupiny byly obvykle přiřazeny k velitelům pověřeným vojenskými operacemi, nazývaly se týmy operačního výzkumu (operational research teams) a jejich výzkum jako operační (operations research, resp. operational research).^[1]

Po skončení druhé světové války se řada z těchto expertů vrátila na své původní civilní pozice na akademické půdě či v průmyslu a začala zde aplikovat metody operačního výzkumu při řešení manažerských problémů. V tomto období se operační výzkum rozvíjel nejvíce ve Spojených státech. Ropné společnosti byly prvními, které začaly s využíváním modelů operačního výzkumu při řešení problémů velkovýroby a distribuce. K rychlému rozvoji operačního výzkumu přispělo zavedení počítačů na počátku padesátých let. Dalším faktorem, který urychlil jeho rozvoj, bylo zapojení operačního výzkumu jakožto předmětu do univerzitních kurikul (nejprve ve Spojených státech). Postupně se poznatky operačního výzkumu začaly aplikovat také ve službách v oblasti bankovnictví, zdravotní péče, komunikace, knihovnictví a přepravy.^[2]

Významnou osobností geneze operačního výzkumu byl G. B. Dantzig, autor simplexového algoritmu (vytvořil jej v roce 1947) a teorie lineárního programování.  Přibližně ve stejném období byly položeny základy teorie her díky publikaci Theory of Games and Economic Behavior (1944) od J. von Neumanna a O. Morgensterna. V roce 1950 vznikl ve Velké Británii první časopis věnovaný operačnímu výzkumu, Operational Research Quarterly, a  o dva roky později byla formálně představena simplexová metoda. Ve stejném roce vznikl časopis Operations Research ve Spojených státech, kde byla současně založena společnost ORSA (The Operations Research Society of America).^[3]

1.1 Definice operačního výzkumu a jeho odvětví

Čím se operační výzkum zabývá a jaké nástroje k tomu používá, bylo již naznačeno na několika místech výše v tomto příspěvku. Zde představíme některé vybrané definice této disciplíny.

The Institute for Operations Research and the Management Sciences definuje operační výzkum jako „vědecký proces transformace dat do porozumění tomu, jak (se) lépe rozhodovat“.^[4]

Dle jedné z definic The International Federation of Operational Research Societies (IFORS) je operační výzkum „procesem lepšího rozhodování prostřednictvím analýzy dat, matematického modelování, optimalizace a dalších analytických metod“.^[5]

University of Columbia in the City of New York uvádí, že „operační výzkum je aplikovanou vědou zabývající se kvantitativními rozhodovacími problémy, které se obvykle týkají alokace a kontroly omezených zdrojů“.^[6]

V učebním textu J. Jablonského nalezneme následující vymezení operačního výzkumu: „Operační výzkum […] je možné charakterizovat jako vědní disciplínu nebo spíše soubor relativně samostatných disciplín, které jsou zaměřeny na analýzu různých typů rozhodovacích problémů. […] Operační výzkum  nachází aplikace všude tam, kde se jedná o analýzu a koordinaci provádění operací v rámci nějakého systému. […] Cílem je přitom stanovit takovou úroveň provádění těchto operací nebo jejich vzájemný vztah tak, aby bylo zajištěno co možná nejlepší fungování celého systému.“^[7] Na operační výzkum tedy můžeme nahlížet jako na „prostředek pro nalezení nejlepšího řešení daného problému při respektování celé řady různorodých omezení, která mají na chod systému vliv“.^[8]

Operační výzkum pokrývá vícero odvětví: matematické programování, vícekriteriální rozhodování, teorii grafů, teorii zásob, teorii hromadné obsluhy (resp. teorii front), modely obnovy, Markovovy rozhodovací procesy, teorii her a simulace.^[9]

V našem předmětu a rovněž v tomto příspěvku se zaměřujeme především na oblast matematického programování – konkrétně programování lineárního. Matematické programování J. Jablonský definuje jako „odvětví operačního výzkumu, zabývající se řešením optimalizačních úloh, ve kterých se jedná o nalezení extrému daného kritéria, definovaného ve tvaru kriteriální funkce  proměnných, na množině variant určených soustavou omezujících podmínek, které jsou zadány ve tvaru lineárních nebo nelineárních rovnic či nerovnic“.^[10] Je-li výše zmíněná kriteriální funkce lineární, stejně jako všechny rovnice i nerovnice, hovoříme o lineárním programování.

1.2 Obecná úloha lineárního programování

Pomocí obecné úlohy lineárního programování můžeme modelovat reálné rozhodovací situace v případech, kdy všechny proměnné modelu jsou spojité, požadujeme optimalizaci jediné účelové funkce, a tato účelová funkce i všechny omezující podmínky jsou lineární.^[11]

Obecná úloha lineárního programování představuje problém nalezení optimálního řešení maximalizační nebo minimalizační úlohy s danou lineární účelovou funkcí při splnění systému lineárních omezení. Formulovat ji můžeme následovně:

Mějme  proměnných (neznámých) . Naším úkolem je najít takové hodnoty těchto proměnných, které by maximalizovaly (resp. minimalizovaly) zadanou lineární funkci těchto proměnných, při daném systému omezení, rovněž lineárních v těchto proměnných.^[12]

V případě maximalizační úlohy vypadá obecný matematický model následovně:

Množinu řešení určenou systémem vlastních omezujících podmínek (zde soustavou  nerovnic) nazýváme množinou všech přípustných řešení. (Jedná se o průnik množin určených jednotlivými omezujícími podmínkami, tzn. nerovnicemi či rovnicemi.) Na této množině potom hledáme extrém účelové funkce (maximum nebo minimum, dle typu a zadání úlohy).

Speciálními typy úloh lineárního programování jsou například dopravní úloha nebo přiřazovací problém.^[13]

1.3 Simplexová metoda

Standardním nástrojem řešení obecných úloh lineárního programování je simplexová metoda, jež může být využita v případě maximalizační i minimalizační úlohy s omezujícími podmínkami v obvyklém tvaru (tzn., ve tvaru soustavy lineárních rovnic a nerovnic). Simplexová metoda systematicky prochází řešení odpovídající vrcholům hranice množiny všech přípustných řešení (kterých je konečný počet), přičemž s každým přepočtem zlepšuje hodnotu účelové funkce, až do nalezení optima úlohy.^[14]

Přestože lineární rovnice dokázali naši předci vyřešit před tisíci let, řešení soustav lineárních nerovnic zůstávalo rébusem až do poloviny dvacátého století. Simplexová metoda řešení úloh lineárního programování vyvinutá G. B. Dantzigem^[15] byla první prakticky a výpočetně použitelnou metodou řešení soustav lineárních nerovnic.^[16]

Ruční výpočet (nalezení optimálního řešení) pomocí simplexové metody provádíme v tabulce. Simplexový algoritmus je popsán v našich skriptech^[17], v řadě učebnic a odborných textů^[18] i na internetu.

Před aplikací simplexového algoritmu převedeme soustavu lineárních rovnic a nerovnic (tvořenou soustavou omezujících podmínek) pomocí doplňkových proměnných na soustavu lineárních rovnic; tuto soustavu doplníme o anulovanou rovnici účelové funkce. Je-li výsledná soustava v kanonickém tvaru a jsou-li všechny pravé strany rovnic nezáporné, můžeme přistoupit k výpočtu simplexovou metodou. Výchozí přípustné řešení „zlepšujeme“ (je-li to třeba) pomocí simplexového algoritmu neboli přepočítáváme tak, že s každým krokem (iterací) se zlepšuje hodnota účelové funkce, až do nalezení optima úlohy. V případě, že výchozí řešení není přípustné, resp. soustava rovnic není v kanonickém tvaru, je třeba přistoupit k další transformaci soustavy pomocí umělých proměnných.

1.4 Využití poznatků operačního výzkumu

Poznatky operačního výzkumu a nástroje jím používané nacházejí uplatnění v mnoha odvětvích. Přehled praktických aplikací operačního výzkumu přináší například publikace Operations Research Applications.^[19] Každá z jejích kapitol je věnována jedné konkrétní oblasti, v níž se uplatňují poznatky operačního výzkumu. Těmito oblastmi jsou  letectví, e-obchod, energetické systémy, finance, armáda, výrobní systémy, projektový management, kontrola kvality, spolehlivost, řízení dodavatelského řetězce a vodní zdroje.^[20]

Co se týče vojenských aplikací, Weir a Thomas uvádějí, že operační výzkum existuje tak dlouho jako stálé vojsko a námořnictvo.^[21] Jako vědecká disciplína, která může být armádě nápomocna, byl nicméně uznán až ke konci třicátých let minulého století, kdy byli britští vědci povoláváni k využití svých znalostí ve vojenských operacích. Následoval rychlý růst této disciplíny a řada pokroků na poli operačního výzkumu byla přímo spojena s jejich vojenskými aplikacemi. Dle výše uvedených autorů je vojenský operační výzkum počátkem a skutečným základem disciplíny operačního výzkumu.^[22]

Lineární a celočíselné programování jsou v rámci armády využívány v řadě oblastí, většinou na strategické nebo operační úrovni. Na operační úrovni nacházejí využití například v problematice rozvržení operačního prostoru, směrování bezpilotních letadel nebo optimalizace ozdravení a obnovení poškozené země a výcvikových prostorů. Nejčastější uplatnění ovšem lineární a celočíselné programování nacházejí na úrovni strategické, v oblasti plánování operací velkého rozsahu. Ty se zaměřují na možné budoucí scénáře v případě mezinárodních konfliktů. Tyto scénáře jsou typicky modelovány pro dlouhá časová období (měsíce či roky). Vytvořené modely poskytují řídícím subjektům analytický nástroj vymezující dopady rozpočtových změn, struktury ozbrojených sil, zásob munice, rozmístění cílů, míry bojových ztrát atp. na bojeschopnost země ve válce. Může se také jednat o humanitární operace velkého rozsahu (např. typu pomoci při přírodních katastrofách). Uplatnění ve vojenských aplikacích nacházejí i další oblasti operačního výzkumu, jako jsou síťové optimalizace, vícekriteriální rozhodování, rozhodovací analýza, stochastické modely nebo simulace.^[23]

2 PŘEDMĚT OPERAČNÍ VÝZKUM NA UNIVERZITĚ OBRANY A VYUŽITÍ SOFTWARE

Předmět operační výzkum, jak je vyučován na Univerzitě obrany, pokrývá čtyři hlavní oblasti, kterými jsou lineární programování (konkrétně úlohy výrobního plánování, směšovací a rozdělovací úlohy), distribuční úlohy (dopravní úlohy a přiřazovací problémy), vícekriteriální optimalizace (vícekriteriální hodnocení variant a vícekriteriální lineární programování) a teorie her (maticové hry). Klíčové postavení mezi uvedenými tématy zaujímá problematika lineárního programování. Základní studijní literaturu předmětu představuje elektronický studijní text Operační výzkum.^[24]

V každé z probíraných oblastí jsou studenti nejprve seznámeni s teoretickými východisky řešené problematiky. Je jim představen obecný matematický model situace, kterou se zabýváme, skládající se z omezujících podmínek a účelové funkce, jejíž extrém hledáme (ve všech případech se jedná o lineární rovnice, resp. nerovnice). Následně je studentům vysvětlen algoritmus řešení dané úlohy, vedoucí k nalezení optimálního řešení. Ten poté procvičujeme pomocí série slovních úloh (ukázkových i k vlastnímu řešení studenty).

Ruční počítání a řešení úloh lineárního programování doplňujeme ukázkou jejich řešení s využitím zvolených software. Jak jsme již zmínili v úvodu našeho příspěvku, při volbě software pro řešení úloh lineárního programování v předmětu operační výzkum jsme vycházeli zejména z jejich dostupnosti studentům Univerzity obrany a také jejich názornosti při řešení těchto úloh (resp. provázanosti s ručními výpočty, jak jsou v předmětu vyučovány). Řešení příkladů je tak demonstrováno zejména v programech Microsoft Excel (dále také jen „Excel“) – prostřednictvím doplňku „Řešitel“ – a Linear Program Solver (dále jen „LiPS“). První z uvedených programů je všem studentům i zaměstnancům Univerzity obrany bezplatně k dispozici v rámci balíčku „Office 365 pro studenty a zaměstnance“, který je přístupný na intranetu univerzity. Program LiPS je optimalizační balíček, jenž je volně ke stažení na internetových stránkách.^[25]

Řešitel je doplněk programu Microsoft Excel, který je k dispozici po jeho instalaci. Pomocí tohoto doplňku můžeme, mimo jiné, řešit úlohy lineárního programování s využitím simplexové metody. Řešitel dokáže nalézt extrém (minimum nebo maximum) funkce zadané vzorcem v cílové buňce při současném splnění omezujících podmínek formulovaných pomocí dalších vybraných buněk. Úlohu naformulujeme v příslušném listu Excelu a Řešitel po svém spuštění nalezne a zobrazí její optimální řešení (existuje-li). S pomocí tohoto doplňku jsme schopni řešit veškeré úlohy řešitelné simplexovou metodu. Je ale třeba jej v Excelu nejprve zavést.^[26]

Program LiPS byl vyvinut pro výukové účely. Zaměřuje se na řešení úloh lineárního, celočíselného a cílového programování. LiPS využívá modifikovanou simplexovou metodu, jejíž pomocí dokáže řešit úlohy velkého rozsahu. Zahrnuje také citlivostní analýzu umožňující studium chování modelu v případě změny jeho parametrů (pravých stran vlastních omezení, koeficientů účelové funkce nebo samotné matice soustavy). V případě cílového programování umožňuje řešení úloh pomocí lexikografické metody a metody váženého součtu.

Studenti jsou v rámci předmětu operační výzkum seznámeni také s existencí online kalkulaček pro řešení úloh lineárního programování.^[27] Jejich užívání je ale spojeno s několika nedostatky. Vedle reklam vstupujících mezi jednotlivé výpočty představuje hlavní nevýhodu těchto pomůcek nejistota ohledně jejich (plné) funkčnosti a jejich „trvanlivosti“.

3 UKÁZKOVÉ ŘEŠENÍ ÚLOHY LINEÁRNÍHO PROGRAMOVÁNÍ POMOCÍ VYBRANÝCH SOFTWARE

V této části s pomocí vzorového příkladu ukážeme řešení úlohy lineárního programování prostřednictvím zvolených software a provázanost tohoto řešení s ručním výpočtem. Je třeba čtenáře upozornit, že níže uvedený příklad je ilustrační, zjednodušený tak, aby dobře posloužil svému účelu (tj. ukázkovému řešení). Použité programy (Řešitel v Excelu a LiPS) jsou samozřejmě schopny řešit úlohy výrazně většího rozsahu.

3.1 Zadání úlohy

Firma zbrojního průmyslu vyrábí pistole a samopaly. Klíčovými surovinami pro jejich výrobu jsou ocel, hliník a titan. Při výrobě 1 ks pistole spotřebuje firma 600 g oceli, 100 g hliníku a 20 g titanu. Při výrobě 1 ks samopalu spotřebuje 3 000 g oceli, 50 g hliníku a 75 g titanu. Pro týdenní produkci firma disponuje 3 030 kg oceli, 100 kg hliníku a 90 kg titanu. Zisk firmy z 1 ks pistole je 4 000 Kč, z 1 ks samopalu 10 000 Kč. Úkolem je stanovit optimální týdenní výrobní plán (tedy určit, kolik se má v rámci jednoho týdne vyrobit pistolí a kolik samopalů), aby firma dosáhla maximálního zisku.

Výše uvedené slovní zadání, které nazýváme ekonomickým modelem úlohy, je možno zapsat i ve formě tabulky obsahující ekvivalentní informace:^[28]

Tabulka č. 1:  Ekonomický model úlohy

Pomocí tabulkového zadání snadno převedeme ekonomický model do jazyka matematiky – vytvoříme odpovídající matematický model úlohy:

Neznámé (proměnné) , resp.  představují množství vyrobených pistolí, resp. samopalů (oboje v kusech), funkce  odpovídající hodnotu zisku (v tisících Kč).

3.2 Řešení úlohy pomocí grafické metody

Jelikož úloha obsahuje pouze dvě neznámé, můžeme její řešení nalézt i graficky. V kartézské soustavě souřadné každý bod roviny o souřadnicích  představuje právě jedno řešení. Pomocí omezujících podmínek (nerovnic) nejprve určíme množinu všech přípustných řešení , na které poté nalezneme maximum účelové funkce . Grafické řešení úlohy demonstruje obrázek 1.

Obrázek č. 1: Grafické řešení úlohy

Pomocí grafické metody jsme nalezli optimum úlohy, jemuž v obrázku odpovídá bod . Jedná se o průsečík hraničních přímek polorovin určených první a druhou podmínkou (nerovnicí). Na základě této vědomosti snadno dopočteme souřadnice bodu . Dopočítáme rovněž hodnotu účelové funkce v optimu:  tis. Kč, a můžeme zformulovat závěr úlohy:

Pro firmu je optimální v rámci jednoho týdne vyrobit 550 ks pistolí a 900 ks samopalů. Dosáhne tím maximálního zisku ve výši 11,2 mil. Kč.

3.3 Ruční řešení úlohy pomocí simplexové metody

Řešitel v Excelu i LiPS využívají při řešení úloh lineárního programování simplexovou metodu. Tabulka níže demonstruje jednotlivé kroky řešení zadané úlohy pomocí simplexové metody při ručním výpočtu. Klíčový prvek v každém kroku je zvýrazněn modrým rámečkem.

Tabulka č. 2: Ruční výpočet pomocí simplexové metody

Početně – pomocí simplexové metody – jsme samozřejmě obdrželi stejný výsledek jako v případě grafické metody:

Pro firmu je optimální během jednoho týdne vyrobit 550 ks pistolí a 900 ks samopalů. Dosáhne tím maximálního zisku ve výši 11,2 mil. Kč. Spotřebuje se veškeré disponibilní množství ocele i hliníku a 78,5 kg titanu (zbude 11,5 kg nespotřebovaného titanu).

3.4 Řešení úlohy pomocí Řešitele v Excelu

Při řešení úlohy pomocí doplňku Řešitel je nejprve třeba ji v prázdném listu Excelu naformulovat. Vložíme sem tabulkové zadání ekonomického modelu, jak je uvedeno v tabulce 1.

Obrázek č. 2: Tabulková podoba ekonomického modelu úlohy v Excelu

Mezi matici soustavy a řádek odpovídající účelové funkci vložíme volný řádek a mezi matici soustavy a sloupec disponibilního množství vložíme tři volné sloupce. Pod účelovou funkcí vynecháme dva volné řádky a pod ně přidáme řádek, kam vložíme pole s označením „Vyráběné množství“. Buňky tohoto řádku (B9 a C9) budou obsahovat předem neznámá množství jednotlivých typů zbraní, která budou tvořit optimální výrobní plán. Tato množství nejprve nastavíme na hodnotu rovnu nule.

Do prostředního volného sloupce vložíme pole s označením „Použité množství“. Buňky tohoto sloupce (E2 až E4) budou tvořit celková množství použitých surovin. V každém řádku tato množství vypočítáme jako skalární součin vektoru vyráběného množství jednotlivých typů zbraní (buňky B9 a C9) a řádku obsahujícího jednotková množství suroviny (tzn., množství suroviny potřebná na výrobu jednoho kusu příslušného typu zbraně). Využijeme zde funkce „SOUČIN.SKALÁRNÍ“, která je implementována v Excelu (viz obrázek 3). V tuto chvíli jsou všechna množství použitých surovin rovna hodnotě nula.

Obrázek č. 3: Příprava tabulky Řešiteli

Nakonec přidáme pole s označením „Celkový zisk“ a do buňky pod něj (G9) vložíme vzorec pro výpočet výsledné hodnoty účelové funkce (viz obrázek 4). Tu získáme jako skalární součin vektoru vyráběných množství jednotlivých typů zbraní (buňky B9 a C9) a vektoru příslušných jednotkových zisků (buňky B6 a C6). Celkový zisk je v tuto chvíli roven nule.

Obrázek č. 4: Příprava tabulky Řešiteli (pokračování)

Nyní je úloha lineárního programování připravena pro zadání Řešiteli. Spustíme jej na záložce „Data“. Do pole „Účelová funkce“ vložíme buňku obsahující vzorec pro výpočet celkového zisku (G9). Zvolíme možnost „Max“, jelikož hledáme maximum účelové funkce. Do pole „Proměnné modelu“ vložíme buňky odpovídající (hledanému) vyráběnému množství (B9 a C9). Dále přidáme tři omezující podmínky požadující, aby jednotlivá množství použitých surovin byla menší nebo rovna jejich příslušným disponibilním množstvím. Zaškrtneme možnost „Nastavit podmínky nezápornosti“, neboť nás zajímají jen nezáporná řešení, a jako metodu řešení vybereme „Simplexovou metodu“. Zadání potvrdíme stisknutím tlačítka „Řešit“ (viz obrázek 5).

Obrázek č. 5: Zadání úlohy Řešiteli

Objeví se dialogové okno oznamující, že „Řešitel nalezl optimální řešení“, a po odsouhlasení volby „Uchovat řešení řešitele“ si můžeme podobu optimálního řešení prohlédnout přímo v našem pracovním listu (viz obrázek 6). Nalezené optimální řešení se samozřejmě shoduje s výsledky získanými výše.

Obrázek č. 6: Optimální řešení úlohy nalezené Řešitelem

3.5 Řešení úlohy v programu LiPS

Program LiPS umožňuje vkládat zadání úlohy textově (prostřednictvím vlastního kódovacího jazyku programu lpx) nebo v podobě tabulky. Zvolíme-li druhou variantu, vybereme v programu možnost „Tabular“, resp. „Table Model“. Před vyplněním samotné tabulky zadáme, že náš model bude obsahovat dvě proměnné, tři vlastní omezení a jednu účelovou funkci maximalizačního typu. Na základě těchto parametrů LiPS vygeneruje tabulku, kterou vyplníme hodnotami podle našeho zadání (viz ekonomický model v tabulce 1 nebo na obrázku 2).

Obrázek č. 7: Zadání modelu úlohy v programu LiPS

Program LiPS má u proměnných modelu automaticky předvoleny hodnoty dolních hranic (rovny nule) a horních hranic (nekonečno). Proměnné jsou přednastaveny jako spojité, mohou tedy nabývat všech reálných hodnot větších nebo rovných nule.

Řešení úlohy spustíme zeleným tlačítkem na horní liště (viz obrázek 7), resp. klávesou F5. Program v novém okně vygeneruje řešení v podobě simplexových tabulek odpovídajících jednotlivým krokům výpočtu simplexovým algoritmem (viz obrázky 8. a, b, c).

Obrázek č. 8 a, b, c: Řešení úlohy simplexovým algoritmem v LiPS

V souladu se simplexovým algoritmem, jak jej známe z ručního výpočtu, jsou u každého kroku (pod tabulkou) uvedeny vstupující proměnná, hodnoty podílového kritéria a vystupující proměnná. Výhodou takto vygenerovaného řešení je, že tabulka je svým rozložením velmi podobná tvaru tabulky při ručním počítání simplexovým algoritmem. Doplňkové proměnné jsou značeny písmenem  a číslicí. V posledním řádku simplexové tabulky jsou uvedeny hodnoty koeficientů účelové funkce. Je třeba upozornit, že se nejedná o anulovaný tvar rovnice účelové funkce, s jakým jsou studenti zvyklí ručně počítat (hodnoty koeficientů odpovídají tvaru rovnice účelové funkce před jejím anulováním). Algoritmus ale pracuje stejně.

Program LiPS nalezl optimální řešení po třech přepočtech (iteracích) simplexové tabulky. Odpovídá mu hodnota účelové funkce 11 200 (tis. Kč). Výsledky řešené úlohy shrnují dvě tabulky, které si můžeme prohlédnout na obrázku 9.

Obrázek č. 9: Řešení nalezené programem LiPS

Ve druhém sloupci první tabulky vidíme, že optimální výrobní plán představují hodnoty , . Třetí sloupec této tabulky rekapituluje jednotkové zisky z příslušných typů zbraní. Hodnoty redukovaných cen ve čtvrtém sloupci vyjadřují, o kolik jednotek by se změnila hodnota účelové funkce při zařazení jednoho kusu odpovídajícího výrobku (typu zbraně) do výrobního plánu. Oba typy zbraní se již vyrábějí, a proto hodnoty jim odpovídajících redukovaných cen jsou rovny nule.

Druhý sloupec druhé tabulky shrnuje, kolik je při realizaci optimálního výrobního plánu spotřebováno jednotlivých surovin. Třetí sloupec této tabulky rekapituluje vlastní omezení úlohy, tzn. disponibilní množství odpovídajících surovin. Hodnoty stínových (duálních) cen ve čtvrtém sloupci vyjadřují, o kolik by se změnila hodnota účelové funkce při doplnění příslušné suroviny o jednotku. Navýšení kapacity ocele, resp. hliníku o jednotku by vedlo ke zvýšení hodnoty účelové funkce o 2/675 tis. Kč (2,96 Kč), resp. 1/45 tis. Kč (22,22 Kč). Hodnota stínové ceny titanu je rovna nule, neboť tato surovina není při realizaci optimálního výrobního plánu plně vyčerpána.

4 DISKUZE: ZAPOJENÍ SOFTWARE DO VÝUKY OPERAČNÍHO VÝZKUMU

Zapojení software do výuky, v podobě ukázkových řešení probíraných úloh prostřednictvím specializovaných programů, jistě napomůže její názornosti. Věříme, že také přispěje ke zvýšení atraktivity vyučovaného předmětu pro studenty.

Samotné řešení úloh lineárního programovaní s využitím software ale nesmí „jít na úkor“ porozumění principům simplexové metody (a dalších používaných algoritmů) a schopnosti řešit tyto úlohy ručně (metodou „tužka–papír“). S využitím softwarových výpočtů matematických úloh se obecně může pojit riziko, že student (resp. uživatel) bude schopen zadání úlohy do programu vložit, spustit její řešení a poté převzít výsledky, aniž by porozuměl samotnému principu použitého výpočtu.

I z tohoto důvodu byly pro zapojení do výuky zvoleny právě výše uvedené nástroje. V případě doplňku Řešitel v programu Excel studenti bohužel „nevidí“, jak probíhá hledání optimálního řešení s pomocí simplexové metody. Při samotném zadávání („naprogramování“) úlohy Řešiteli (tzn. při přípravě pracovního listu v Excelu a naformulování požadavků Řešiteli) je ale třeba hluboké porozumění problému, jehož vyřešení od Řešitele požadujeme. Studenti při přípravě úlohy k jejímu zpracování Řešitelem v Excelu prakticky vytvářejí matematický model úlohy, který je potom (již „na pozadí“) doplňkem vyřešen pomocí simplexové metody. 

Výhodou programu LiPS, na druhé straně, je, že kromě řešení, resp. konečného výsledku úlohy, poskytuje také detailní postup řešení v podobě jednotlivých kroků (přepočtů) simplexové tabulky, jak se je studenti učí v předmětu operační výzkum. Studenti mohou s jednotlivými kroky tabulky porovnávat svá ruční řešení nebo alespoň u každého z kroků pozorovat průběh výpočtu simplexovým algoritmem (výběr vstupující a vystupující proměnné, resp. klíčového sloupce a klíčového řádku). Výhodu programu spatřujeme rovněž v tom, že vstup (zadání úlohy) je možné realizovat jednak algebraicky (textovým souborem ve formátu lpx), jak je tomu v případě většiny software pro řešení úloh lineárního programovaní, ale také v podobě tabulky. Tvar vstupní tabulky odpovídá zadání úloh, jak se s ním studenti seznamují v předmětu, a také podobě vstupu online kalkulaček pro řešení úloh lineárního programování dostupných volně na internetu.

Mezi slabšími stránkami zvolených software můžeme zmínit skutečnost, že má-li řešená úloha optimální řešení, Řešitel v Excelu i program LiPS naleznou právě jedno. Existuje-li optimálních řešení více, pro nalezení alternativních optim se musíme obrátit ke „staré dobré“ ruční metodě výpočtu.

Pokud jsme na straně výhod zapojení software do výuky operačního výzkumu uvedli zvýšení názornosti a atraktivity předmětu, na straně druhé musíme zmínit s tím spojenou časovou zátěž. Zapojit používání výpočetních programů do výuky bez současného zvýšení časové dotace předmětu a neučinit tak na úkor (teoretickému) porozumění problematice (viz rizika zmíněná výše) je pro vyučující výzvou.

ZÁVĚR

Ačkoli v období geneze operačního výzkumu byl rozvoj této disciplíny úzce spojen s jejím využitím ve vojenských aplikacích, její poznatky nacházejí široké uplatnění i v civilní sféře. Modely a techniky operačního výzkumu jsou využívány v celé řadě oblastí, kterými jsou například letectví, projektový management, finance, kontrola kvality a další.

K  poválečnému rozmachu operačního výzkumu přispěl zejména rozvoj výpočetní techniky, také ale jeho zavedení jakožto vyučovacího předmětu do univerzitních osnov. Nejinak je tomu v České republice, kde se lineární programování – tvořící jeden z pilířů operačního výzkumu – v různých obdobách vyučuje na vysokých školách s matematickým, ekonomickým nebo technickým zaměřením. Praktická výuka tohoto předmětu bývá do větší nebo menší míry doplněna ukázkami řešení úloh pomocí vybraných software. Programů pro řešení úloh lineárního programování existuje celá řada, s rozličnou úrovní dostupnosti. Studenti mohou jako pomůcku při řešení těchto úloh využívat i různých online internetových kalkulaček, k těmto nástrojům je ale třeba přistupovat s obezřetností.

V předmětu operační výzkum, jak je vyučován na Univerzitě obrany – resp. v jeho praktické části, seznamujeme studenty se softwarovým řešením úloh lineárního programování zejména prostřednictvím doplňku Řešitel v programu Microsoft Excel a programu Linear Program Solver (LiPS). Pro zapojení právě těchto dvou programů jsme se rozhodli především z důvodu jejich dostupnosti našim studentům a rovněž pro jejich názornost. Tu spatřujeme zejména v tom, že naformulování úlohy Řešiteli v Excelu vyžaduje hluboké porozumění řešené problematice; program LiPS zase umožňuje studentům procházet jednotlivé kroky simplexového algoritmu jako při ručním počítání.

Hlavním cílem našeho příspěvku bylo s pomocí ukázkového řešení úlohy lineárního programování demonstrovat možnosti využití doplňku Řešitel v Excelu a programu LiPS ve výuce operačního výzkumu. Jelikož i v tomto případě nám šlo o názornost, zvolili jsme ilustrační příklad, který představoval značné zjednodušení (ve srovnání s komplexními reálnými problémy). Oba výše uvedené programy dokáží samozřejmě řešit úlohy podstatně většího rozsahu (zadání obsahující více proměnných i omezujících podmínek), přičemž princip zadání úlohy a „naprogramování“ jejího řešení zůstává stejný.

Věříme, že zapojení software do výuky operačního výzkumu přispěje k atraktivitě a uchopitelnosti tohoto předmětu pro naše studenty. Zároveň ale budeme pokračovat v kladení důrazu na perfektní porozumění a ovládání ručních výpočtů, ze kterých tyto a další software vycházejí.

POZNÁMKY K TEXTU A CITACE

^[1] RAVINDRAN, A. Ravi. Operations research methodologies. Boca Raton: CRC Press, c2009. Operations research series. ISBN 978-1-4200-9182-3, s. xvii.

^[2] Zpracováno dle RAVINDRAN, A. Ravi. Operations research methodologies. Boca Raton: CRC Press, c2009. Operations research series. ISBN 978-1-4200-9182-3, s. xvii-xviii.

^[3] SRINIVASAN, G. Operations Research: principles and applications. PHI Learning Pvt. Ltd., 2017, s. xvii-xviii.

^[4] What are Operations Research and Analytics? The Institute for Operations Research and the Management Sciences [online]. [cit. 2021-9-10]. Dostupné z: https://www.informs.org/Explore/Operations-Research-Analytics.

^[5] What is OR? The International Federation of Operational Research Societies [online]. [cit. 2021-9-10]. Dostupné z: https://www.ifors.org/what-is-or/.

^[6] Industrial Engineering and Operations Research. Columbia University in the City of New York [online]. [cit. 2021-9-10]. Dostupné z: https://www.ieor.columbia.edu/about.

^[7] JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007. ISBN 978-80-86946-44-3, s. 9.

^[8] JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007. ISBN 978-80-86946-44-3, s. 10.

^[9] viz JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007. ISBN 978-80-86946-44-3, s. 13-17.

^[10] Tamtéž, s. 13.

^[11] RAVINDRAN, A. Ravi. Operations research methodologies. Boca Raton: CRC Press, c2009. Operations research series. ISBN 978-1-4200-9182-3, s. 1-4.

^[12] BLUMENFELD, Dennis. Operations research calculations handbook. Boca Raton: CRC Press, 2001. ISBN 0849321271, s. 140.

^[13] viz BLUMENFELD, Dennis. Operations research calculations handbook. Boca Raton: CRC Press, 2001. ISBN 0849321271, s. 146-152.

^[14] Tamtéž, s. 157.

^[15] DANTZIG, George Bernard. Linear Programming and Extensions, Princeton, Univ. Press, Princeton, NJ, 1963.

^[16] RAVINDRAN, A. Ravi. Operations research methodologies. Boca Raton: CRC Press, c2009. Operations research series. ISBN 978-1-4200-9182-3, s. 1-4.

^[17] ŠMEREK, Michal a Zuzana ŠPAČKOVÁ. Operační výzkum. Brno: Univerzita obrany, 2021. ISBN 978-80-7582-407-3, s. 46-58.

^[18] Viz např. DANTZIG, George Bernard. Linear Programming and Extensions, Princeton, Univ. Press, Princeton, NJ, 1963, s. 94-99, RAVINDRAN, A. Ravi. Operations research methodologies. Boca Raton: CRC Press, c2009. Operations research series. ISBN 978-1-4200-9182-3, s. 1-26 až 1-28 nebo v českém jazyce JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007. ISBN 978-80-86946-44-3, s. 50-60.

^[19] RAVINDRAN, A. Ravi. Operations research applications. Boca Raton: CRC Press, c2009. Operations research series. ISBN 1420091867.

^[20] Tamtéž.

^[21] Tamtéž, s. 363.

^[22] Tamtéž, s. 364.

^[23] Více viz RAVINDRAN, A. Ravi. Operations research applications. Boca Raton: CRC Press, c2009. Operations research series. ISBN 1420091867, s. 364-373.

^[24] ŠMEREK, Michal a Zuzana ŠPAČKOVÁ. Operační výzkum. Brno: Univerzita obrany, 2021. ISBN 978-80-7582-407-3.

^[25] Linear Program Solver. SourceForge [online]. 2013 [cit. 2021-9-8]. Dostupné z: https://sourceforge.net/projects/lipside/.

^[26] Viz například Zavedení doplňku Řešitel v Excelu. Microsoft [online]. [cit. 2021-9-8]. Dostupné z: https://support.microsoft.com/cs-cz/office/zaveden%C3%AD-dopl%C5%88ku-%C5%99e%C5%A1itel-v-excelu-612926fc-d53b-46b4-872c-e24772f078ca.

^[27] Např. IZQUIERDO GRANJA, Daniel a Juan José RUIZ. PHPSimplex [online]. 2006 [cit. 2021-9-10]. Dostupné z: http://www.phpsimplex.com/simplex/simplex.htm?l=en.

^[28] Před zápisem údajů do tabulky jsme sjednotili jednotky hmotnosti na gramy.