LINEÁRNÍ PARAMETRIZACE V PROSTŘEDÍ MS EXCEL

24.09.1999 | Odborné konference

Linear parametrization in MS EXCEL

L. Dö meová, J. Získal

Adresa autorů:

Katedra operační a systémové analýzy, PEF ČZU Praha

Kamýcká 129, 165 21 Praha 6 - Suchdol

Anotace:

Prudký rozvoj informačních technologií vyvolává i změny při uplatňování klasických ekonomicko matematických metod. Důležitým nástrojem systémové analýzy jsou metody parametrického lineárního programování, které umožňují zkoumat závislost optimálního řešení úlohy lineárního programování na měnících se vstupních datech modelu. Možnost změny těchto dat je vyjádřena pomocí proměnných parametrů na jejichž hodnotách pak závisí optimální řešení úlohy.

K vyjádření vstupních dat pomocí proměnných parametrů může vést buď neznalost těchto údajů při formulaci modelu nebo snaha vyjádřit jedním modelem daný systém v různých situacích při změněných vstupních údajích.

Pro parametrizaci konkrétních úloh existuje příslušný software, ale jeho použití je náročné zejména z interpretačního hlediska.

Cílem tohoto příspěvku je ukázat jak lze klasickou parametrizaci realizovat moderními prostředky , které poskytuje modelování v tabulkových procesorech. Jsou uvedeny možnosti využití programu Microsoft Power Point pro názornou prezentaci postupu výpočtu. Výhodou je možnost propojení na tabulkový procesor a využití řady grafických prostředků, které přispívají k snadnější práci s modelem, lepšímu pochopení problému a usnadňují interpretaci získaných výsledků.

Summary:

The rapid development of information technologies calls for changes in application of classical OR methods. Methods of parametric linear programming are important tools of system analysis which enable to study dependence of the optimal solution on changes in input parameters of the model. The possible change in inputs is expressed by variable parameters and the optimal solution value depends on them.

Usage input data in parameter form could be either result of lack of information in the phase of model formulation or intention to use the same model in different situations.

The parametrization software exists but its exploitation is difficult, especially interpretation. This contribution deals with classical parametrization realized in spread sheet. For presentation of the method we used Microsoft Power Point. Its advantage is connection with spread sheet and graphic presentation which leads to better understanding of the model and easier interpretation of obtained results.

Klíčová slova:

Lineární parametrizace, statický model LP, vektor parametrů, interval přípustných hodnot, modifikovaná metoda parametrického programování, tabulkový procesor MS EXCEL.

Key words:

Linear parmetrization, static linear programming model, parameter vector, range of acceptable values, parametric programming - modified method, work sheet MS EXCEL.

Úvod

Znalostně orientovaný přístup definuje rozhodování jako aktivitu, která vytváří novou část znalostí vyjadřujících závaznost k určitému směru činnosti. Tento nový přístup k rozhodování se začal prosazovat od konce osmdesátých let a podle něho manažer preferuje ty směry činnosti o nichž se domnívá, že jsou dostatečně dobré. Pojem optimum není chápán jako ztotožnění s extrémem nebo výběrem kompromisního řešení. Začíná se prosazovat pojem “optimum seeking” podle kterého se rozhoduje tak, aby věci měly správnou míru, čili konečné rozhodnutí je podřízeno manažerovi.

Manažer potřebuje mít o řešeném problému k dispozici dostatek informací, které získává různým způsobem pomocí různých metod a informačních technologií. Jedním z nejrozšířenějších nástrojů v oblasti zemědělství se staly lineární statické optimalizační modely. Aby se rozšířila jejich vypovídací schopnost rozvíjely se různé jejich modifikace a metody pro transformaci vstupních údajů modelu do potřebné formy. Jednou z metod, která umožňuje zjistit pomocí téhož statického modelu dopad různých změn na chování zkoumaného systému je lineární parametrizace. Ta se stala účinným prostředkem metodické analýzy a syntézy, která směřuje k vytváření dokonalejších ekonomických systémů.

Protože proces zvládnutí parametrického programování bývá obtížný, chceme v tomto příspěvku ukázat jeho zjednodušení a zefektivnění pomocí tabulkového procesoru.

Modifikovaná metoda lineárního parametrického programování

Lineární parametrizací nazýváme postup, při kterém vyhledáváme všechny optimální báze odpovídající plynulé lineární změně některé konstanty modelu lineárního programování. Dále uvedená metoda vychází z pojmu intervalu přípustných hodnot jednotlivého parametru. Přípustnými hodnotami rozumíme ty hodnoty parametru, pro něž zůstane optimální řešení v téže bázi.

Uvažujme úlohu:

Nalézt maximum kriteriální funkce

(1)

za podmínek

(2)

Uvažujeme změnu pravých stran soustavy omezujících podmínek.

Změnu pravých stran soustavy podmínek si vyjádříme pomocí vektoru parametrů

jehož složky nazýváme parametry a vyjadřují změnu příslušné složky bi vektoru b ve tvaru

(3)

Je-li B-1 matice transformace příslušná k matici optimální báze B, pak je řešení úlohy dáno vztahem:

(4)

Mění-li se právě jedna k-tá složka vektoru pravých stran původní soustavy podmínek o číslo

dostaneme ve složkovém vyjádření

(5)

Chceme-li, aby řešení zůstalo přípustné v bázi B, musí být splněna podmínka

(6)

Čísla a ik jsou koeficienty z k-tého sloupce matice transformace B-1 a mohou nabývat kladných, záporných nebo nulových hodnot. Z tohoto hlediska provedeme rozbor soustavy (6).

Pro a ik > 0 je řešením soustavy nerovností (6) nerovnost

(7)

a pro a ik > 0

(8)

tj. interval přípustných hodnot parametru l k je omezen nerovností

(9)

Neexistuje-li a ik > 0, klademe

neexistuje-li a ik > 0, klademe

Postup při parametrizaci jedné složky bi

1. Podle (7) a (8) se určí

2. Postup směrem “dolů”

Položí se

a určí se

kde

je k-tý sloupec matice B-1

3. Ve vektoru xB je jedna složka nulová, ta určuje klíčový řádek. Nová báze se určí pomocí duálního simplexového algoritmu.

1. Do sloupce pro vektor xB opíšeme nalezený vektor xBl

2. V novém kroku určíme

, při čemž

a dostaneme interval

kde

6. Dosadíme

a postup opakujeme.

1. Parametrizace “dolů” je ukončena:

když a) neexistuje

8. Obdobně se postupuje při parametrizaci “nahoru”.

Modelování v tabulkových procesorech

Tabulkové procesory představují plně integrovaná, uživatelská prostředí. Jde o softwarový nástroj pro automatizovanou práci s tabulkami. V následujícím chceme ukázat na ilustrativním příkladu použití procesoru MS EXCEL při parametrizaci jedné složky vektoru pravých stran soustavy omezujících podmínek úlohy LP.

Změny hodnoty účelové funkce při všech změnách b2

Závěr

Metoda parametrického lineárního programování se stala důležitým nástrojem systémové analýzy. Umožňuje zkoumat závislost optimálního řešení úlohy LP na měnících se vstupních datech modelu. Možnost změny těchto dat je vyjádřena pomocí proměnných parametrů na nichž pak závisí i optimální řešení dané úlohy.

Závislost vstupních dat modelu LP, tj. vektoru pravých stran, vektoru cen a matice technicko ekonomických koeficientů na proměnných parametrech může být vyjádřena různými funkcemi. Nejjednodušším typem této závislosti je je závislost lineární a pro ni je také nejvíce propracovaná lineární parametrizace.

V tomto příspěvku uvádíme možnost využití moderních prostředků, které postupně současná výpočetní technika při parametrizaci jedné složky vektoru pravých stran. Podobně jako při lineární parametrizaci vektoru požadavků, můžeme i při lineární parametrizaci vektoru cen, resp. jednotlivých prvků matice technicko ekonomických koeficientů, určit takové realizovatelné hodnoty všech parametrů, které za daných podmínek zajišťují dosažení absolutního extrému příslušné kriteriální funkce.

Z tabulkových procesorů jsme použili MS Excel se kterým máme dobré zkušenosti. Shrneme výhody jeho použití pro danou problematiku:

· didaktičnost- názornost, snadnější pochopení postupu metody při výuce;

· integrovanost - k řešení možno využít přímo některé softwarové nástroje např. LINKOSU, (což je optimalizační modul pro řešení modelů LP, který je integrální součástí prostředí Excel 5.0 a byl vyvinut pracovníky katedry Dr. Šubrtem a Dr. Brožovou;)

· srozumitelnost - možno vytvářet tabulky a grafy;

Z výsledků lineární parametrizace lze zjistit např. účelnost nebo neúčelnost změny technických mezí parametrů, které v dané variantě řešení příznivě ovlivňují hodnocení kriteriální funkce atd. Všechny zjištěné údaje lze využít nejen k přetváření zkoumaného systému směrem k lepšímu, ale též k pokusům o ovlivňování jeho okolí, zejména z hlediska marketingu.

Z hlediska vlastního procesu modelování existuje v oblasti agrobyznisu řada námětů pro využití lineární parametrizace. K vyjádření vstupních dat modelu pomocí proměnných parametrů může vést v řadě případů neznalost, resp. nemožnost získat tyto údaje nebo potřeba rozboru optimálního výsledku vzhledem k různým hodnotám vstupních dat.

Jednou z nesporných dalších výhod parametrizace je, že umožňují vyjádřit pomocí jednoho modelu sledovaný systém v různých situacích.