MODELOVÁNÍ VÍCEETAPOVÝCH ROZHODOVACÍCH PROBLÉMŮ

24.09.1999 | Odborné konference

Modelling multiperiod decision problems

Eva Vaněčková

Adresa autora:

Katedra aplikované matematiky a informatiky, Jihočeská univerzita,

Zemědělská fakulta, České Budějovice

Anotace:

V příspěvku jsou uvedeny některé možnosti matematického modelování jednokriteriálních rozhodovacích problémů, ve kterých rozhodování neprobíhá jednorázově, ale je časově rozloženo do několika na sebe navazujících období. Některé z těchto problémů lze formulovat ve tvaru úloh dynamického nebo matematického programování. Tento přístup k zobrazení víceetapových rozhodovacích problémů je v příspěvku ilustrován na příkladech. Z modelů matematického programování jsou nejvíce zastoupeny modely lineárního programování se spojitými, celočíselnými i binárními proměnnými a distribuční modely.

Grafickým nástrojem pro zobrazení jednokriteriálních víceetapových úloh s prvky deterministickými i stochastickými jsou rozhodovací stromy.

Summary:

The paper deals with the decision problems that can be decomposed into partial decisions in single periods. These problems are called multiperiod decision problems. Their solution presents the destination of such a succession of decisions that guarantees the optimal value of the decision criterion.

Some multiperiod decision problems can be formulated as problems of dynamic programming or mathematical programming. The author shows some samples of these approaches to the modelling multiperiod decision problems and mentions references to the respective literature.

Ä graphical tool for modelling multiperiod decision problems with deterministic and stochastic elements is decision tree.

Klíčová slova:

víceetapové rozhodovací problémy; modelování; dynamické programování; matematické programování; rozhodovací stromy

Key words:

multiperiod decision problems; modelling; dynamic programming; mathematical programming; decision trees

Častým případem rozhodování ve všech oblastech lidské činnosti jsou víceetapové (vícestupňové) rozhodovací problémy, ve kterých rozhodování neprobíhá jednorázově, ale je časově rozloženo do několika na sebe navazujících období. Cílem řešení těchto víceetapových rozhodovacích problémů je stanovení takové posloupnosti rozhodnutí, která zajišťuje co nejlepší hodnotu zvoleného rozhodovacího kritéria.

Rozhodnutí v určité etapě rozhodovacího procesu může spočívat buď ve výběru nejvýhodnější varianty z dané množiny přípustných alternativ, nebo ve stanovení optimálních hodnot parametrů vztažených k jednotlivým etapám a zajišťujících optimální hodnotu rozhodovacího kritéria za celé sledované období. Vhodnou modelovou technikou pro víceetapové rozhodovací problémy tohoto druhého typu je matematické modelování.

Cílem předloženého příspěvku je roztřídění matematických modelů víceetapových rozhodovacích úloh do skupin se společným přístupem k jejich řešení a uvedení některých ilustrujících příkladů spolu s odkazy na příslušnou literaturu.

Modely víceetapových rozhodovacích úloh dělíme na modely deterministické a stochastické podle toho, zda zobrazovaný problém je deterministický nebo stochastický.

Jestliže důsledky rozhodnutí v každé etapě rozhodovacího procesu jsou jednoznačně určeny, jde o proces deterministický. Pokud důsledek rozhodnutí v některé etapě má náhodný charakter, rozhodovací proces je stochastický.

Víceetapové rozhodovací úlohy, které se týkají rozhodování v regulovatelných systémech a v nichž etapa představuje určitý stav systému, můžeme dělit na deterministické a stochastické podle toho, zda přechod z jednoho stavu do následujícího je dán jednoznačně nebo zda můžeme určit pouze jeho pravděpodobnost.

Jiné dělení matematických modelů víceetapových rozhodovacích úloh je odvozeno od způsobu zadání rozhodovacího kritéria a vztahů, které musí platit mezi jednotlivými etapami rozhodování. Z tohoto hlediska můžeme modely víceetapových rozhodovacích úloh rozdělit na modely využívající principy dynamického programování a na modely matematického programování.

V modelech dynamického programování je dána globální účelová funkce v podobě součtu dílčích funkcí představujících ohodnocení efektivnosti rozhodování v jednotlivých etapách. Vztahy mezi po sobě jdoucími etapami jsou dány rekurentními vzorci, které umožňují najít optimální řešení metodou zpětného průchodu.

V modelech matematického programování může být zadáno několik účelových funkcí, které explicitně vyjadřují závislost rozhodovacího kritéria na neznámých veličinách vztahujících se k jednotlivým časovým obdobím. Vztahy mezi těmito obdobími a tedy i mezi hledanými veličinami jsou vyjádřeny soustavou nerovnic a rovnic. Modely často obsahují celočíselné a binární proměnné.

Kromě modelů dynamického a matematického programování je výhodné pro jednokriteriální víceetapové rozhodovací úlohy použít též grafické modely, zejména rozhodovací stromy. Z hlediska teorie grafů je rozhodovací strom neorientovaný, souvislý, acyklický, hranově i uzlově ohodnocený graf. Hrany rozhodovacích stromů představují varianty rozhodování, které jsou předem známy. Rozhodovací strom může mít deterministický nebo stochastický charakter, přičemž za prototyp rozhodovacího stromu se obvykle považuje strom s prvky deterministickými i stochastickými (kromě jednoznačně daných rozhodnutí rozhodovatele se v rozhodovacím procesu vyskytují též náhodná rozhodnutí “přírody”).

V další části svého příspěvku uvedu některé příklady matematických modelů víceetapových rozhodovacích problémů, které jsou většinou převzaty z literatury.

LAŠČIAK a kol. 1983 formuluje a řeší v podobě úlohy dynamického programování likvidaci stáda skotu při jeho současné reprodukci během několika let tak, aby výsledný zisk byl maximální. Jako další úlohu dynamického programování uvádí rozdělení daných výrobních prostředků mezi několik odvětví tak, aby úhrnný zisk, který přinese jejich používání během určitého počtu let, byl maximální.

Bellmanův princip optimality, na kterém jsou založeny metody dynamického programování, využil ROLLO 1973 při konstrukci modelu pro sestavení plánu odvádění součástek z výroby do meziskladu, z něhož se převádí potřebné množství součástek na montáž. Cílem úlohy byla minimalizace nákladů na skladování součástek v meziskladu a nákladů spojených se zadáním jedné dávky do výroby.

Řadu víceetapových rozhodovacích problémů lze formulovat ve tvaru úloh lineárního programování. Příkladem může být rozhodování o nejvýhodnější výrobní struktuře podniku, který má časově proměnlivé dodávky surovin nebo požadavky na odbyt výrobků. Neznámé veličiny v této úloze představuje množství produktů vyrobených v uvažovaných obdobích. Omezující podmínky vyjadřují možnost přesunu surovin z jednoho období do následujícího stejně tak jako možnost odprodeje výrobků, které zbyly v předcházejícím období. Kritériem optimálnosti je maximalizace zisku za všechna období dohromady.

Modelů lineárního programování lze též použít při víceetapovém rozhodování o optimální velikosti výrobní dávky určitého produktu v jednotlivých obdobích. Cílem tohoto rozhodování je minimalizace výrobních nákladů, skladovacích nákladů a fixních nákladů na jednu výrobní dávku. V této úloze kromě neznámých představujících velikosti výrobní dávky v jednotlivých obdobích vystupují též binární proměnné nabývající hodnoty 1 nebo 0 podle toho, zda v daném období se bude či nebude vyrábět. Uvedený model popisuje TEMPELMEIER 1994.

Binární proměnné se vyskytují též v modelu pro optimalizaci časového harmonogramu kusové výroby, který uvádí PELIKÁN 1993. Cílem tohoto modelu je přiřadit každému výrobku termín zahájení výroby tak, aby v každé časové jednotce (měsíci) nebyly pokud možno překročeny kapacity hlavních výrobních zařízení a profesí. Problém je formulován v podobě úlohy cílového programování.

Jakožto úlohu celočíselného lineárního programování lze formulovat plánování nástupu pracovníků ve vícesměnném provozu s různou potřebou pracovníků během dne. Neznámými veličinami v této úloze jsou počty pracovníků, kteří musí nastoupit na začátku daných časových intervalů. V omezujících podmínkách je vyjádřen požadavek, aby v každém časovém okamžiku byl na pracovišti potřebný počet pracovníků. Kritériem optimálnosti je minimální počet pracovníků, zajišťující provoz během celého dne. Tento model popisuje např. ROLLO 1973. Podobný typ modelu bývá navrhován pro plánování vícesměnného provozu podnikové nákladní autodopravy (viz např. PICEK, KOŽÍŠEK 1990).

K víceetapovým rozhodovacím problémům patří řízení zásob, při kterém lze též uplatnit modely lineárního programování. Příkladem může být deterministický model zásob, který uvádí UNČOVSKÝ a kol. 1985. Neznámé veličiny v tomto modelu představují nakoupené množství výrobků na začátku každého období. Omezující podmínky zajišťují nepřekročení kapacity skladu a pokrytí potřeby výrobků v každém období. V účelové funkci je vyjádřen požadavek minimálních výdajů na nákup výrobků za celé sledované období.

Při matematickém modelování některých víceetapových rozhodovacích problémů lze využít modelů dopravních úloh, které jsou zvláštním případem úloh lineárního programování.

Ve tvaru dopravní úlohy lze formulovat rozvrhování výroby v rámci několika období, jestliže pro každé období i je známá výrobní kapacita podniku (ai), požadavek odběratelů (bi) a náklady na výrobu a skladování jednotkového množství produkce vyrobeného v i-tém období a odeslaného v j-tém období (cij). Neznámé veličiny xij představují množství produkce vyrobené v i-tém období a odeslané v j-tém období. Kritériem optimálnosti jsou minimální výrobní a skladovací náklady za všechna sledovaná období. Omezující podmínky vyjadřují požadavek, aby se nepřekročila výrobní kapacita podniku v jednotlivých obdobích a aby byly uspokojeny požadavky odběratelů v každém období.

Formulaci víceetapového optimálního plánování výroby a zásob v podobě dopravní úlohy, ve které je navíc ještě výroba rozdělena na řádnou a přesčasovou pracovní dobu, uvádí KORDA a kol. 1967, JABLONSKÝ 1998.

Jiným příkladem aplikace modelu dopravního problému při řešení víceetapových rozhodovacích úloh je plánování oprav a rezerv strojů. Cílem je minimalizace nákladů na normální opravy, rychloopravy, popř. na nákup nových strojů, jestliže v daném období počet použitelných strojů je menší než jejich potřeba. Tato úloha je v literatuře uváděna v různých obměnách (viz např. KORDA a kol. 1967), přičemž původní problém se týkal oprav leteckých motorů za 2. světové války (viz HUŠEK, VEJMOLA, HAVELKA 1982).

Některé víceetapové rozhodovací problémy jsou v literatuře formulovány ve tvaru úloh dynamického i matematického programování. Oba tyto typy modelů uvádí PITEL a kol. 1988 při optimálním plánování výroby tvarovaného krmiva v jednotlivých měsících z hlediska minimalizace nákladů na jeho výrobu a uskladnění, HUŠEK, VEJMOLA, HAVELKA 1982 při optimálním plánování výroby pšenice v jednotlivých letech z hlediska maximalizace tržeb z jejího prodeje po uspokojení vlastní potřeby uvažovaného zemědělského podniku, SILVER, PYKE, PETERSON při optimálním řízení zásob.

Modelů lineárního programování lze použít při víceetapovém rozhodování i v případech, kdy výběr nejvýhodnější varianty rozhodování může být ovlivněn náhodným rozhodnutím "přírody". Příkladem dvouetapového rozhodovacího problému tohoto typu je nákup paliva před zimou a v průběhu zimy nebo prodej zemědělských rostlinných produktů hned po jejich sklizni a později. Za předpokladu, že pro určitý stav "přírody" lze daný problém formulovat jako úlohu lineárního programování, SCHRAGE 1995 doporučuje pro řešení úloh uvedeného typu tento postup: do matematického modelu úlohy lineárního programování zahrnout proměnné, které se vztahují k oběma uvažovaným etapám a ke všem možným stavům "přírody", a vytvořit účelovou funkci, která se skládá z části deterministické vztahující se k prvnímu období a z části stochastické vztahující se k druhému období. V této stochastické části účelové funkce se uplatňují pravděpodobnosti, s jakými nastanou jednotlivé stavy přírody. Pomocí analýzy senzitivnosti je pak možné zkoumat vliv velikosti těchto pravděpodobností na řešení takto formulované úlohy. Uvedený postup pro řešení víceetapových rozhodovacích problémů s náhodnými alternativami lze zobecnit pro více než dvě etapy, avšak se zvětšujícím se počtem období velmi rychle narůstá velikost úlohy.

Při výčtu možností pro modelování víceetapových rozhodovacích problémů nelze opomenout simulační techniku, která odstraňuje některé výpočetní nesnáze při řešení úloh dynamického a matematického programování analytickými metodami. Rozvoj simulačních postupů na počítačích je zárukou jejího širokého využívání.