Řešení úloh lineárního programování v MS EXCEL

17.4.10

Řešení úloh lineárního programování v MS EXCEL

Doc. Ing. Alois Fiala, CSc.

V následujícím textu stručně popíšeme pouze základní úkony nutné k vyřešení úlohy LP v MS Excel. Detailnější informace a popisy dalších možností řešení optimalizačních úloh v Excelu lze najít v manuálech a specializovaných učebnicích.

 NahoruZadání vstupních údajů

Nejprve musíme do listu zadat hodnoty neřiditelných veličin, tj. prvky matice A a vektorů b a c (vektor b je vhodné zapsat jako sloupec, kdežto vektor c jako řádek) s případným popisem (význam, jednotky).

Dále je nutné vyhradit buňky pro vektor rozhodovacích proměnných (opět jako řádek). Tyto buňky nemusíme vyplňovat (pak jsou tam implicitně hodnoty 0) nebo je můžeme vyplnit nějakými nenulovými hodnotami (např. hodnotami 1). Druhá možnost je vhodnější, protože tyto buňky pak vstupují spolu s buňkami neřiditelných veličin do nějakých vzorců a při použití nenulových hodnot máme možnost kontroly těchto vzorců.

 NahoruNeřiditelná veličina

Ještě je třeba vyhradit buňku pro neřiditelnou veličinu z. Tato veličina je obecně dána vzorcem

 NahoruSkalární součin

a tento vzorec také musíme zadat do příslušné buňky. Uvedený výraz vlastně představuje skalární součin vektorů c a x, a tedy je k tomu vhodné využít funkci SOUČIN.SKALÁRNÍ, která se nachází v repertoáru matematických funkcí Excelu.

Nyní máme na ploše listu zachyceny všechny veličiny matematického modelu, a mohli bychom tedy tento model přepsat do Excelu. Abychom si však vytvoření modelu v Excelu usnadnili, vyhradíme na ploše další buňky pro hodnoty levých stran vlastních omezení, které jsou dány výrazy

Tyto výrazy zadáme do příslušných buněk opět pomocí funkce SOUČIN.SKALÁRNÍ, protože i-tý výraz je vlastně skalární součin i-tého řádku matice A a vektoru x.

 NahoruZadání modelu a jeho řešení

Když teď máme připraveny všechny potřebné veličiny, zavoláme nástroj zvaný Řešitel (Solver), který se nachází v nabídce Nástroje. Pokud jej v této nabídce nenajdeme, musíme jej zaškrtnout v podnabídce Doplňky. Jestliže tam není, pak to znamená, že nemáme k dispozici kompletní verzi Excelu.

Po zavolání řešitele se nám objeví okno Parametry Řešitele, ve kterém musíme zadat:

• která buňka reprezentuje účelovou funkci (pole Nastavit buňku),

• zda chceme dosáhnout jejího maxima, minima nebo nějaké zadané hodnoty,

• které buňky odpovídají rozhodovacím proměnným (pole Měněné buňky),

• omezující podmínky.

 NahoruOmezující podmínky

Omezující podmínky se zadávají pomocí tlačítka Přidat. Po kliknutí na toto tlačítko se otevře okno Přidat omezující podmínku se třemi poli. Do pole Odkaz na buňku se musí zadat adresa buňky odpovídající levé straně omezující podmínky (tuto adresu nemusíme zadávat textově, stačí na ni kliknout myší). V prostředním poli zvolíme příslušný symbol nerovnosti nebo rovnice a do pole Omezující podmínka zadáme odkaz na buňku odpovídající pravé straně omezující podmínky. Do tohoto pole můžeme zadat i konkrétní hodnotu, ale to není příliš vhodné, protože to ztěžuje případné budoucí úpravy modelu. Chceme-li přidávat další podmínku, klikneme na tlačítko Přidat (aktuální podmínka se uloží a objeví se okno pro přidání další podmínky). Chceme-li zadávání omezujících podmínek ukončit, klikneme na tlačítko OK, čímž se vrátíme do okna Parametry řešitele. Pomocí jednoho okna Přidat omezující podmínku můžeme zadat celou skupinu omezujících podmínek, které mají stejný symbol nerovnosti nebo rovnice (buňky odpovídající levým a pravým stranám těchto podmínek musejí ovšem na ploše listu vytvářet souvislé skupiny). Do pole Odkaz na buňku zadáme skupinu buněk obsahujících levé strany omezujících podmínek (zadání se provede přejetím myši přes tyto buňky) a do pole Omezující podmínka zadáme buňky reprezentující příslušné pravé strany.

Podmínky nezápornosti můžeme zadat rovněž pomocí okna Přidat omezující podmínku s tím, že do pole Omezující podmínka zadáme hodnotu 0. Pokud jsou ale podmínky nezápornosti vztaženy na všechny rozhodovací proměnné, je výhodnější tyto podmínky zadat v okně Možnosti Řešitele.

 NahoruParametry řešitele

Než dáme pokyn k řešení, je třeba zkontrolovat a případně upravit nastavení možností řešitele. Po kliknutí na příslušné tlačítko v okně Parametry Řešitele se objeví okno Možnosti řešitele, ve kterém je možno nastavit různé parametry týkající se řešení lineárních, nelineárních a celočíselných úloh (některé volby jsou zde implicitně nastaveny a můžeme je v případě potřeby upravit). Zaměřme se pouze na základní volby týkající se lineárních úloh.

 NahoruLineární model

Pomocí polí Maximální čas a Iterace můžeme omezit dobu trvání výpočtu. Jestliže do vyčerpání zadané doby nebo stanoveného počtu iterací není nalezeno optimální řešení (nebo se nezjistí, že úloha žádné přípustné či optimální řešení nemá), tak výpočet skončí. Údaj v poli Přesnost určuje, s jakou přesností se bude omezující podmínka považovat za splněnou. Pole Tolerance se týká problémů s podmínkami celočíselnosti proměnných a pole Konvergence se používá u nelineárních problémů. S nelineárními problémy souvisí také volby Extrapolace, Derivace a Metody. Jestliže řešíme úlohu LP, musíme zatrhnout volbu Lineární model. Pokud bychom to neudělali, úloha by se neřešila simplexovou metodou, ale metodou pro řešení nelineárních úloh a nezískali bychom tak podrobné údaje pro citlivostní analýzu jako v případě použití simplexové metody. Zaškrtnutí políčka Nezáporná čísla způsobí, že bude nastavena dolní mez 0 pro všechny rozhodovací proměnné (měnitelné buňky), pro které jsme hodnotu dolní meze nezadali při zadávání omezujících podmínek. Zaškrtnutím políčka Automatické měřítko se aktivuje automatická úprava měřítka v případech, kdy se výrazně liší velikost vstupů a výstupů. Jestliže zaškrtneme políčko Zobrazit výsledek iterace, výpočet se po každé iteraci přeruší. Po kliknutí na tlačítko Uložit model se zobrazí dialogové okno, ve kterém můžeme zadat umístění, do nějž můžeme model uložit. Toto tlačítko se používá pouze v případech, kdy s listem chceme uložit více než jeden model. Jestliže pracujeme pouze s jedním modelem, pak je tento model uložen automaticky. Kliknutí na tlačítko Načíst model zobrazí dialogové okno, ve kterém můžeme zadat odkaz na model, který chceme načíst.

 NahoruVýsledky řešení

Kliknutím na tlačítko OK potvrdíme nastavení možností řešitele, čímž se vrátíme do okna Parametry Řešitele. Výpočet pak spustíme kliknutím na tlačítko Řešit. Po ukončení procesu řešení se objeví okno Výsledky řešení. V případě, že bylo nalezeno optimální řešení, objeví se zde text: "Řešitel nalezl řešení, které splňuje všechny omezující podmínky.“ Vypočtené hodnoty rozhodovacích proměnných a účelové funkce se objeví v příslušných buňkách na ploše listu. Tyto hodnoty máme možnost uchovat nebo se vrátit k původním hodnotám a dále máme možnost požádat o vygenerování výsledkové, citlivostní a limitní zprávy. Jestliže úloha nemá konečné optimální řešení, v okně Výsledky řešení se objeví text "Hodnota nastavované buňky není konvergentní“. Neexistence přípustného řešení je signalizována textem: "Řešitel nenalezl vhodné řešení.“

Příklad 1

Řešme v Excelu úlohu z příkladu 1 v § 17/4.1 (po zanedbání podmínek celočíselnosti). Matematický model této úlohy vypadá následovně:

                             

z	=	4 x1	+	6 x2	→	max
3 x1	+	3 x2	≤	210
x1	+	2 x2	≤	100
x1	≤	60
x2	≤	40
x1 ,	x2	≥	0

Následující tabulka zachycuje zadání veličin modelu.

Matice A soustavy podmínek se nachází v buňkách C3 - D6, vektor b pravých stran omezujících podmínek v buňkách F3 - F6 a vektor c koeficientů účelové funkce v buňkách C7 - D7. Rozhodovacím proměnným jsou vyhrazeny…