VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY Obor: Statistika a ekonometrie
Název bakalářské práce
Modely cílového programování a jejich aplikace
Autor: Vedoucí bakalářské práce:
Romana Suchanová prof. Ing. Josef Jablonský, CSc.
Prohlášení: Prohlašuji, že jsem bakalářskou práci na téma „Modely cílového programování a jejich aplikace“ zpracovala samostatně. Veškerou použitou literaturu a další podkladové materiály uvádím v seznamu použité literatury.
Praha, 5. 4. 2009
Romana Suchanová
2
Poděkování: Chci poděkovat prof. Ing. Josefu Jablonskému, CSc. za jeho trpělivost, podporu a pomoc při zpracovávání bakalářské práce.
3
Obsah 1
Úvod .......................................................................................................................... 5
2
Úlohy vícekriteriálního lineárního programování ............................................... 6 2.1 Princip agregace účelových funkcí ....................................................................... 7 2.2 Minimalizace vzdálenosti od ideálních hodnot ..................................................... 7 2.3 Kompromisní řešení podle minimální komponenty.............................................. 8 2.4 Cílové programování ............................................................................................. 8
3
Cílové programování .............................................................................................. 9 3.1 Cíle ........................................................................................................................ 9 3.2 Formulace obecného modelu cílového programování ........................................ 10 3.3 Obecný model v systému LINGO ....................................................................... 13
4
Robustní cílové programování ............................................................................. 16 4.1 Problém cílového programování ......................................................................... 16 4.2 Robustní řešení úlohy cílového programování ................................................... 17 4.3 Problém jednokriteriálního lineárního programování pro M-robustní řešení problému cílového programování ............................................................................... 18
5
Příklady .................................................................................................................. 20 5.1 Úloha výrobního plánování ................................................................................. 20 5.1.1
Maximalizace příjmů z prodeje ................................................................... 21
5.1.2
Minimalizace pracovníků ............................................................................ 22
5.1.3
Řešení pomocí cílového programování ....................................................... 23
5.2 Optimalizace portfolia ......................................................................................... 25 5.3 Nutriční problém ................................................................................................. 27 6
Závěr....................................................................................................................... 30
Seznam použité literatury............................................................................................ 31
4
1 Úvod Cílové programování se již dlouhou dobu úspěšně používá v praxi. Jde o techniku řešení optimalizačních úloh, kde se místo optimalizace jedné účelové funkce minimalizují odchylky od cílových hodnot. Umožňuje nám stanovit si cílové hodnoty, kterých chceme dosáhnout.
Modely cílového programování jsou pružnější než standardní modely lineárního programování. Používají se například při plánování pracovních sil, výběru výstavby, plánování sdělovacích prostředků, ve výrobním plánování a v dopravních problémech. Běžné optimalizační modely nemusí pro modelování chování podniků stačit. V praxi mají podniky více cílů zároveň a někdy si mohou tyto cíle vzájemně odporovat.
Knih a článků věnovaných tématu cílového programování vyšlo mnoho. Například literatura [6], [7], [8], [9], [10], [11], [12] a [13]. První publikace používající cílové programování byla napsána Charnesem a kolegy (1955).
Cílové programování je nejčastější metoda při hledání kompromisního řešení úloh vícekriteriálního programování. Cílem této práce je sestavit obecný model cílového programování a uvést jeho použití na praktických příkladech.
Ve druhé kapitole popisuji vlastnosti úloh vícekriteriálního programování a různé způsoby hledání kompromisního řešení. Ve třetí kapitole se již zabývám cílovým programováním, popisuji jeho vlastnosti a formuluji obecný model. Čtvrtá kapitola je věnována robustnímu cílového programování a v páté kapitole uvádím několik praktických příkladů řešených pomocí obecného modelu.
5
2 Úlohy vícekriteriálního lineárního programování U úloh vícekriteriálního lineárního programování chceme optimalizovat několik
{
účelových funkcí na množině přípustných řešení X, X = x ∈ R n Ax ≤ b, x ≥ 0}, a nalézt kompromisní řešení, které musí být nedominované. Řešení je nedominované, jestliže neexistuje přípustné řešení, které by jej dominovalo, tj. neexistuje jiné přípustné řešení, které by bylo lépe nebo stejně hodnocené podle všech účelových funkcí. Předpokládáme, že účelové funkce a omezující podmínky jsou lineární. V literatuře [1] je tato úloha formulována takto:
maximalizovat z1 = c11x1 + c12x2 +… + c1nxn, z2 = c21x1 + c22x2 +… + c2nxn, .
(2.1)
. zk = ck1x1 + ck2x2 +… + cknxn, za podmínek a11x1 + a12x2 +… + a1nxn ≤ b1, a21x1 + a22x2 +… + a2nxn ≤ b2,
(2.2)
. . am1x1 + am2x2 +… + amnxn ≤ bm, xj ≥ 0, j = 1, 2, …, n, nebo maticově: maximalizovat z1 = c1x, z2 = c2x, .
(2.3)
. zk = ckx,
6
za podmínek
{
x ∈ X = x ∈ R n Ax ≤ b, x ≥ 0},
(2.4)
kde ci je vektor cenových koeficientů i-té účelové funkce, i = 1, 2, …, k.
Kompromisní řešení úlohy vicekriteriálního lineárního programování můžeme vypočítat pomocí několika principů. Já se v této práci zabývám principem agregace účelových funkcí, minimalizací vzdálenosti od ideálních hodnot, minimální komponentou a cílovým programováním.
2.1 Princip agregace účelových funkcí Účelové funkce ohodnotíme vahami, vytvoříme jednu agregovanou účelovou funkci a řešíme klasickou úlohu LP. Podle [1] formulujeme úlohu: maximalizovat k
z = ∑ vi c i x ,
(2.5)
i =1
za podmínek (2.4), kde vi, i = 1, 2,…, k, jsou váhy a
∑v
i
= 1.
Kompromisním řešením podle principu agregace účelových funkcí je krajní bod množiny přípustných řešení za předpokladu, že existuje jedno řešení.
2.2 Minimalizace vzdálenosti od ideálních hodnot Stanovíme si ideální hodnoty pro účelové funkce a budeme minimalizovat vážený součet odchylek od ideálních hodnot. Ideální hodnoty můžeme získat optimalizací jednotlivých účelových funkcí na množině přípustných řešení. Úlohu zapíšeme podle [1] takto: minimalizovat k
(
)
z = ∑ vi z iopt − c i x ,
(2.6)
i =1
7
za podmínek x∈X,
(2.7)
kde vi je váha i-té účelové funkce (vi > 0) a z iopt je ideální hodnota i-té účelové funkce.
Stejně jako u principu agregace i v tomto případě existuje-li jedno řešení, je kompromisním řešením krajní bod množiny přípustných řešení.
2.3 Kompromisní řešení podle minimální komponenty Jde o maximalizaci nejhorší hodnoty ze všech účelových funkcí. Minimální komponentu si označíme D. Podle [1] řešíme následující úlohu LP: maximalizovat D,
(2.8)
za podmínek c1x ≥ D, c2x ≥ D, .
(2.9)
. ckx ≥ D, x∈X.
Na rozdíl od předchozích postupů se zde přidávají nové podmínky, a proto nalezené kompromisní řešení nemusí být krajním bodem množiny přípustných řešení.
2.4 Cílové programování Cílové programování se velmi často používá k nalezení kompromisního řešení úloh vícektriteriálního programování a jeho vlastnosti jsou popsány níže.
8
3 Cílové programování
3.1 Cíle U úloh cílového programování existují pevné a volné cíle.
Pevné cíle jsou to samé jako omezující podmínky v klasické úloze LP a je jim přiřazena určitá cílová hodnota. Pevné cíle musejí být splněny. Například máme určitou spotřebu práce při výrobě nábytku a nesmíme překročit kapacitu práce (to je cílová hodnota). Můžeme je formulovat následovně: n
∑a
ij
x j ≤ bi
i = 1, 2,…, m.
(3.1)
j =1
Volné cíle nemusí být přesně splněny. Snažíme se cílové hodnotě co nejvíce přiblížit. Chceme minimalizovat odchylky od cílových hodnot. Kladné a záporné odchylky jsou vyjádřeny pomocí odchylkových proměnných d i− (záporná odchylková proměnná od ité cílové hodnoty) a d i+ (kladná odchylková proměnné od i-té cílové hodnoty). Např.: firma si definuje jako volný cíl zisk 4 000 000 Kč za rok. Budeme se tedy snažit najít řešení blízké této hodnotě. Řešení může být nižší nebo vyšší než 4 000 000 Kč. Obecný zápis vypadá takto: n
∑c
ij
x j + d i− − d i+ = g i ,
i = 1, 2, …, k,
(3.2)
j =1
n
kde
∑c
ij
x j je levá strana omezující podmínky a gi je cílová hodnota.
j =1
Pokud model cílového programování obsahuje více cílů, můžeme jejich důležitost vyjádřit buď pomocí vah, nebo lexikograficky. Váhy jsou bezrozměrná čísla a vyjadřují nám důležitost jednotlivých cílů. Při lexikografickém způsobu minimalizujeme nejdříve odchylky od nejdůležitějšího cíle a postupujeme k nejméně důležitému cíli.
9
3.2 Formulace obecného modelu cílového programování Účelová funkce u cílového programování minimalizuje odchylky od cílových hodnot. Můžou v ní být zahrnuty obě odchylkové proměnné nebo jenom jedna z nich (kladná nebo záporná).
Při minimalizaci záporné odchylky dostaneme řešení, které se zdola bude co nejvíce blížit zadané cílové hodnotě, ale může být libovolně vyšší než tato hodnota (např. hodnota zisku). V případě minimalizace kladné odchylky je tomu naopak. Řešení může být libovolně nižší než cílová hodnota, ale shora se bude co nejvíce přibližovat cílové hodnotě (např. hodnota nákladů). Při minimalizace kladné i záporné odchylky dostaneme řešení, které se cílové hodnotě co nejvíce přibližuje z obou stran.
Jestliže je důležitost cílů vyjádřena vahami, můžeme minimalizovat vážený součet odchylek nebo maximální váženou odchylku.
Minimalizace váženého součtu odchylek je formulována takto: minimalizovat k
∑ (v
− i
d i− + vi+ d i+ )
i =1
z=
gi
,
(3.3)
za podmínek n
∑a
ij
x j ≤ bi ,
i = 1, 2,…, m,
ij
x j + d i− − d i+ = g i ,
i = 1, 2, …, k,
j =1 n
∑c
(3.4)
j =1
d i− ≥ 0, d i+ ≥ 0, d i− d i+ = 0,
i = 1, 2, …, k,
kde v i− a v i+ jsou váhy a gi je cílová hodnota.
Minimalizace vážené maximální odchylky je formulována takto: minimalizovat D,
(3.5)
10
za podmínek n
∑a
ij
x j ≤ bi ,
i = 1, 2,…, m,
ij
x j + d i− − d i+ = g i ,
i = 1, 2, …, k,
j =1 n
∑c
(3.6)
j =1
vi− d i− + vi+ d i+ ≤ D, gi
i = 1, 2, …, k,
d i− ≥ 0, d i+ ≥ 0 ,d i− d i+ = 0,
i = 1, 2, …, k,
kde D je maximální hodnota vážené odchylky, v i− a v i+ jsou váhy a gi je cílová hodnota.
Cíle a odchylky od cílů jsou v různých jednotkách. Je tedy lepší vyjádřit odchylky relativně (procentně) a ne absolutně. Proto odchylky dělím cílovými hodnotami. 1 je stoprocentní plnění cílů.
Teď budu formulovat obecný model úlohy cílového programování. Uvažuji dvoustupňové odchylky. Odchylky od cílových hodnot v intervalu pimin ,p imax
jsou
(
ohodnoceny penále s1vi a odchylky od cílových hodnot v intervalu − ∞, p imin a p imax ,∞ ) jsou ohodnoceny penále s 2 v i . Hodnota s2 je několikrát větší než hodnota s1.
Na obrázku 3.1 vidíte penalizační funkci.
s2vi−
s1vi+ pimin
pimax
Obrázek 3.1: Penalizační funkce.
11
Obecným model: minimalizovat D,
(3.7)
za podmínek n
∑c
ij
x j + d i−1 + d i−2 − d i+1 − d i+2 = g i ,
i = 1, 2,…, k, gi ≠ 0,
j =1
vi ((d i−1 + d i+1 ) s1 + (d i−2 + d i+2 ) s 2 ) ≤ D, gi
i = 1, 2,…, k, gi ≠ 0,
n
∑a
x j ≤ bi ,
i = 1, 2,…, m,
d i−1 ≤ g i − pimin g i ,
i = 1, 2,…, k,
d i+1 ≤ p imax g i -g i ,
i = 1, 2,…, k,
DH j ≤ x j ≤ HH j ,
j = 1, 2, …, n,
d i−1 , d i−2 , d i+1 , d i+2 ≥ 0,
i = 1, 2, …, k,
ij
j =1
(3.8)
kde n je počet proměnných, k je počet volných cílů, m je počet pevných cílů, cij je cenový koeficient j-té proměnné, gi je cílová hodnota, s1 a s2 jsou trestné koeficienty v případě, že hodnota proměnné je menší nebo větší než cíl. d i−1 , d i−2 , d i+1 , d i+2 jsou odchylkové proměnné,
pimin < 1 a pimax > 1 jsou parametry penalizační funkce, xj je strukturní proměnná modelu, HHj a DHj je horní a dolní hranice proměnné xj,
12
3.3 Obecný model v systému LINGO LINGO je jeden z několika systémů na podporu modelování. Je produktem společnosti Lindo Systems, Inc, která umožňuje stáhnutí studentské verze systému z jejich www stránek. LINGO využívá zabudované řešitele lineárních a nelineárních úloh i s podmínkami celočíselnosti. Obsahuje speciální modelovací jazyk a velmi dobře spolupracuje s aplikacemi jako je MS Excel nebo MS Access. Tyto aplikace můžeme využít pro grafickou prezentaci vstupů a výstupů.
Model můžeme do programu zapsat v obecné podobě pomocí výše uvedeného modelovacího jazyka. Takto zapsaný model se velmi podobá matematickému zápisu modelu a stačí ho jen spojit s datovým souborem. Můžeme pouze měnit čísla v datovém souboru a není třeba pro daný typ úlohy provádět celý zápis znovu.
Model můžeme do systému LINGO zadávat buď přímo, nebo pomocí modelovacího jazyka. Já se v této práci budu věnovat pouze zápisu pomocí modelovacího jazyka.
Zápis modelu pomocí modelovacího jazyka obsahuje základní sekce SETS, vlastní tělo modelu a DATA. Celý model začíná příkazem MODEL: a končí příkazem END.
Obecný model v systému LINGO: MODEL: SETS: plan/@OLE('Data.xls','plan')/:v,cil,d1plus,d1min,d2plus,d2min,optimum,pmin,pmax; prom/@OLE('Data.xls','promenne')/:x,HH,DH; omez/@OLE('Data.xls','kapacita')/:b; matice1(omez,prom):a; matice2(plan,prom):cena; ENDSETS min=D; @FOR(plan(i)|cil(i)#NE#0:@sum(prom(j):cena(i,j)*x(j))+d1min(i)+d2min(i)-d1plus(i)d2plus(i)=cil(i)); @FOR(plan(i)|cil(i)#NE#0:s1*v(i)*(d1min(i)+d1plus(i))/cil(i)+s2*v(i)*(d2min(i)+ d2plus(i))/cil(i)<=D);
13
@FOR(omez(i): @sum(prom(j):a(i,j)*x(j))<=b(i)); @FOR(plan(i)|cil(i)#NE#0:d1min(i)<=cil(i)-pmin(i)*cil(i); @FOR(plan(i)|cil(i)#NE#0:d1plus(i)<=pmax(i)*cil(i)-cil(i)); @FOR(prom:@BND(HH,x,DH)); @FOR(plan(i): optimum(i)= @sum(prom(j):cena(i,j)*x(j))); DATA: s1=1; s2=10; DH=@OLE('Data.xls'); HH=@OLE('Data.xls'); a=@OLE('Data.xls'); b=@OLE('Data.xls'); cena=@OLE('Data.xls'); cil=@OLE('Data.xls'); pmin=@OLE('Data.xls'); pmax=@OLE('Data.xls'); v=@OLE('Data.xls'); @OLE('Data.xls')=optimum; @OLE('Data.xls')=x; ENDDATA END
Sekce SETS obsahuje definici množin a atributů. Každý prvek množiny je charakterizován jedním nebo více atributy. Soubory prvků, jejichž počet nezávisí na jiných množinách, nazýváme primitivní množiny. Množina, jejíž počet prvků závisí přímo na počtu prvků primitivní množiny, se nazývá odvozená množina. Sekce začíná klíčovým slovem SETS: a končí klíčovým slovem ENDSETS. Pro zadání množin používám v obecném modelu funkci @OLE, která nám umožňuje načíst prvky primitivných množin z MS Excelu.
Po definici množin následuje vlastní tělo modelu, které odpovídá matematické formulaci úlohy. Obsahuje soustavu rovnic a nerovnic a maximalizační nebo minimalizační kritérium. Při zápisu modelu můžeme používat některé z mnoha funkcí. Nejčastější jsou funkce @SUM a @FOR. Funkce @SUM nám vrací součet hodnot
14
výrazu pro určené prvky množiny a zápis funkce @FOR můžeme číst takto: pro dané prvky množiny proveď uvedené výrazy.
Vstupní data zadáváme v sekci DATA. Tato sekce začíná příkazem DATA: a končí příkazem ENDDATA. Data můžeme zadat buď přímo, nebo je můžeme importovat z MS Excelu pomocí funkce @OLE. Příkaz atribut(y) = @OLE ('jméno souboru', 'jméno bloku') nám umožňuje importovat data z Excelu do systému LINGO. Příkaz @OLE ('jméno souboru', 'jméno bloku') = atribut(y) nám umožňuje exportovat výsledky ze systému LINGO do Excelu.
15
4 Robustní cílové programování Jedná se o nový přístup k cílovému programování. Stejně jako u jiných optimalizačních technik se můžeme při aplikaci cílového programování setkat s problémy souvisejícími s nejistými nebo se měnícími okolnostmi. Jestliže dojde ke změně okolností, musíme model upravit. Řešením tohoto problému může být použití robustního cílového programování.
Robustní optimální řešení je takové řešení, které je optimální i v případě, že se změní parametry rozhodovací situace.
4.1 Problém cílového programování Uvažujeme speciální případ obecného modelu, ve kterém jsou pouze minimalizační cíle (zahrnuje díky možnosti vynásobení -1 i maximalizační případ) a lineární účelovou funkci. Podle literatury [16] zformulujeme model následovně: n
∑c
ij
x j ≤ˆ g i ,
j =1 n
∑a
ij
x j ≤ bi
i = 1, 2,…, m,
(4.1)
j =1
x ≥ 0.
Odpovídající jednocílová formulace: minimalizovat k
∑v d i
+ i
,
(4.2)
i =1
za podmínek j
∑c
ij
x j −d i+ + d i− = d i ,
i = 1, …, k
x j ≤ bi
i = 1, 2,…, m,
i =1 n
∑a
ij
(4.3)
j =1
x ≥ 0, d i− ,d i+ ≥ 0,
i = 1, …, k,
16
kde gi je cílová hodnota a vi jsou váhy. Koeficient cij (i = 1, …, k; j = 1, …, n) se může měnit. Má vliv na cíle záporným směrem. Koeficient j-té proměnné v i-tém omezení bude mít pravděpodobně hodnotu cij (i = 1, …, k; j = 1, …, n) nebo cij ∈ ( cij ,cij ) , (i = 1, …, k; j = 1, …, n).
4.2 Robustní řešení úlohy cílového programování Použiji koncept robustnosti optimálního řešení navrhovaný Bertsimasem a Simem (2003). Jejich základní představa shrnutá podle literatury [16]: a) Robustní optimální řešení je takové řešení, které je optimální i pro nejhorší možné hodnoty koeficientů uvnitř předpokládaných intervalů (nejhorší znamená minimální pro maximalizační účelovou funkci a pro větší nebo rovnající se omezení a maximální v dalších případech). b) Striktním použitím výše uvedené definice bychom získali pesimistický případ, který by snížil řešení navedením koeficientů na jejich nejhorší možné hodnoty. Takové robustní řešení můžeme získat velmi snadno, ale jeho kvalita je nízká. Vzhledem k předpokladu, že se všechny koeficienty mohou měnit v záporném směru současně, může být tento přístup považován za příliš pesimistický. c) Předpokládá se, že se budou měnit jen některé koeficienty a není tedy nutné vědět, které se změní (například nepůjde dolů cena všech výrobků, ale jen některých). Je pouze potřeba určit pro účelovou funkci a jednotlivá omezení maximální počet koeficientů, které se mohou změnit.
Využijeme tento přístup v problému (4.1) s cij ∈ ( cij ,cij ) , i = 1, …, k; j = 1, …, n. Zavedeme M-robustní řešení, ve kterém podle zdroje [16] M = (mi )i =1 a mi (i = 1, …, k) k
je celé číslo nepřesahující n a vyjadřuje kolik koeficientů v i-tém omezení se může změnit. Normální optimální řešení získáme v případě, že mi = 0 a pesimistické řešení v případě, že mi = n.
17
4.3 Problém jednokriteriálního lineárního programování pro Mrobustní řešení problému cílového programování Na základě modelu od Bertsimase a Sima (2003) získáme následující model podle literatury [16], jehož řešení bude M-robustní: minimalizovat k
∑v d i
+ i
(4.4)
,
j =1
za podmínek k
∑c
ij
x j + max
∑Θ
Si ⊂{1,...n} j∈S j Si ≤ mi
j =1
ij
x j − d i+ + d i− = g i ,
i = j, …, k
n
∑a
ij
x j ≤ bi
i = 1, 2,…, m, (4.5)
j =1
x ≥ 0, d i− ,d i+ ≥ 0,
i = 1, …, k,
kde Θij (i = 1, …, k; j = 1, …n) jsou odchylky, které negativně ovlivňují dosažení cílů.
Optimální řešení tohoto modelu je nejhorší hodnota celkové odchylky. Při změně koeficientu mi můžeme vidět, jak tento koeficient ovlivňuje optimální hodnotu celkové odchylky. Výše formulovaný problém není lineární. Můžeme jej na lineární transformovat prostřednictvím lemna, jak je uvedeno ve zdroji [16]: Lemna: β i ( x1 ,x 2 ,...,x n ) = max
∑Θ
S i ⊂{1,...n} j∈S j Si ≤ mi
ij
x j,
i = 1,…, k
(4.6)
Pro každý vektor (x1, x2, …, xn), i = 1, 2, …, k, βi ( x1 , x 2 ,..., x n ), je optimální hodnota účelové funkce problému lineárního programování následující: minimalizovat n
∑p
ij
+ mi z i
(4.7)
j =1
za podmínek z i + pij ≥ Θij x j ,
j = 1, …, n,
pij ,z i ≥ 0,
j = 1, …, n.
(4.8)
18
Můžeme poté formulovat problém lineárního programování, které bude mít M-robustní řešení: Minimalizovat k
∑v d i
+ i
,
(4.9)
j =1
za podmínek n
∑c
n ij
j =1
x j + ∑ pij + mi z z − d i+ + d i− = g i , i = 1, …, k, j =1
z i + pij ≥ Θij x j ,
j = 1, …, n; i = 1, …, k,
p ij ,z i ≥ 0,
j = 1, …, n; i = 1, …, k,
n
∑a
ij
x j ≤ bi
i = 1, 2,…, m,
(4.10)
j =1
x ≥ 0, d i− ,d i+ ≥ 0,
i = 1, …, k,
Přístup, který je zde navrhován se nazývá pesimistický přístup. Člověk, který rozhoduje, může najít řešení pro různé stupně nejistoty nebo pesimismu tím, že změní jeden parametr za cíl.
19
5 Příklady 5.1 Úloha výrobního plánování Firma AB vyrábí batohy, cestovní tašky a kabelky. Na batoh se spotřebuje 5 m2 látky, na tašku 8 m2 látky a na kabelku 4 m2 látky. Pracovníkům trvá 120 minut vyrobit batoh, 200 minut vyrobit cestovní tašku a 100 minut vyrobit kabelku. Spotřebuje se 5 zipů na batoh, 3 zipy na cestovní tašku a 2 zipy na kabelku. Batoh stojí 500 Kč (z toho 250 Kč zisk), cestovní taška 1 000 Kč (z toho 600 Kč zisk) a kabelka 650 Kč (z toho 300 Kč zisk). Aby se firma uživila, musí mít měsíční zisk alespoň 60 000 Kč. Firma má měsíčně k dispozici 800 m2 látky a 700 ks zipů. Jejím cílem je maximalizace příjmů z prodeje a minimalizace pracovníků.
Batoh
Cestovní taška
Kabelka
Kapacita (měsíční)
2
Látka [m ]
5
8
4
800
Zipy [ks]
5
3
2
700
Zisk [Kč]
250
600
300
X
Práce [min]
120
200
100
X
Cena [Kč]
500
1000
650
X
Tabulka 5.1: Spotřeba materiálu.
Matematický model je formulován takto: maximalizovat z1 = 500x1 + 1 000x2 + 650x3, minimalizovat z2 = 120x1 + 200x2 + 100x3,
20
za podmínek 5x1 + 8x2 +4x3 ≤ 800, 5x1 + 3x2 +2x3 ≤ 700, 250x1 + 600x2 +300x3 ≥ 60 000, xj ≥ 0, j = 1, 2, 3, xj – celé. Nejprve vyřeším příklad pomocí klasického lineárního programování a poté použiji programování cílové. 5.1.1
Maximalizace příjmů z prodeje
Zadání příkladu do programu LINGO vidíte na obrázku 5.2 a jeho řešení na obrázku 5.1.
Obrázek 5.1: Řešení v programu LINGO
21
Obrázek 5.2: Zadání v programu LINGO Optimální řešení xopt = (0;0;200) a účelová funkce zopt = 130 000. Firma bude vyrábět 200 kabelek a její příjem z prodeje bude 130 000 Kč.
5.1.2
Minimalizace pracovníků
Příklad jsem řešila v programu LINGO. Zadání příkladu je na obrázku 5.4 a jeho řešení na obrázku 5.3.
Obrázek 5.3: Řešení v programu LINGO. 22
Obrázek 5.4: Zadání v programu LINGO. Optimální řešení xopt = (0;100;0) a účelová funkce zopt = 20 000. Firma bude vyrábět 100 cestovních tašek a počet pracovníků bude 20 000. 5.1.3
Řešení pomocí cílového programování
Vektor vah je v = (0,6;0,4). Cílová hodnota pro příjem z prodeje g1 = 120 000 Kč a pro počet pracovníků g2 = 18 000 minut. Minimalizace váženého součtu odchylek: minimalizovat z = 0,6 d1− /120000 + 0,4d 2+ / 18000,
za podmínek 500 x1 + 1000 x 2 + 650 x 3 + d1− − d 1+ = 120000 120 x1 + 200 x 2 + 100 x3 + d 2− − d 2+ = 18 000
5x1 + 8x2 +4x3 ≤ 800, 5x1 + 3x2 +2x3 ≤ 700, 250x1 + 600x2 +300x3 ≥ 60 000, xj ≥ 0, j = 1, 2, 3. xj – celé.
23
Příklad je řešen v programu LINGO. Výsledky vidíte na obrázku 5.5.
Obrázek 5.5: Data a řešení v Excelu. Kompromisní řešení je xopt = (0;68;64) a účelová funkce zopt = (109 600; 20 000). Aby firma maximalizovala příjem z prodeje a zároveň minimalizovala počet pracovníků, musí vyrobit 68 ks cestovních tašek a 64 ks kabelek. Vidíme, že cílové hodnoty nebyly přesně splněny. Příjem z prodeje je menší o 10 400 Kč a počet pracovníků je větší o 2 000. V tabulce 5.2 porovnávám optimální řešení získaná optimalizací jednotlivých účelových funkcí a pomocí cílového programování minimalizací váženého součtu odchylek. xopt
zopt
Maximalizace příjmů z prodeje
(0;0;200)
130 000
Minimalizace počtu pracovníků
(0;100;0)
20 000
Minimalizace váženého součtu odchylek
(0;68;64)
(109 600; 20 000)
Tabulka 5.2: Porovnání řešení. 24
5.2 Optimalizace portfolia Firma Investment, s. r. o. se rozhodla investovat 1 500 000 Kč do cenných papírů. Rozhoduje se mezi několika následujícími alternativami: vládní obligace, státní dluhopisy, depozitní certifikáty, akcie firmy A, akcie firmy B a dluhopis firmy C. Firma odhadla roční očekávaný výnos jednotlivých variant a jejich rizikovost. Riziko je vyjádřeno bezrozměrným číslem (čím větší hodnota, tím větší riziko). Na poradě se firma dohodla na těchto pravidlech: a) Do dluhopisů nesmí být investováno více než 40% dostupných prostředků. b) Investice do akcií firmy A musí činit alespoň 20% dostupných prostředků. c) Do akcií firmy B se nesmí investovat více než 500 000 Kč. Cílem je dosažení průměrné míry rizika 6 a očekávaného zisku alespoň 10% p. a.. Vektor vah v = (0,3;0,7). V následující tabulce 5.2.1 jsou uvedeny výnosy a rizika jednotlivých variant.
Investice
Očekávaný výnos [%]
Riziko
Vládní obligace
6
2
Státní dluhopisy
4,5
1
Depozitní certifikáty
7
3
Akcie firmy A
15
8
Akcie firmy B
18
10
Dluhopis firmy C
9,5
5
Tabulka 5.3: Přehled investic.
Matematický model formulujeme následovně: maximalizovat
z=
6 x1 + 4,5 x 2 + 7 x3 + 15 x 4 + 18 x5 + 9,5 x6 , 1500000
z=
2 x1 + x 2 + 3x3 + 8 x 4 + 10 x5 + 5 x6 , 1500000
minimalizovat
25
za podmínek x1 + x2 + x3 + x4 + x5 + x6 = 1 500 000, x6 ≤ 600 000, x4 ≥ 300 000, x5 ≤ 500 000, xj ≥ 0, j = 1, 2, …, 6. Příklad jako úloha cílového programování: minimalizovat z = 0,3d1− /10 + 0,7d 2+ /6, za podmínek 6 x1 + 4,5 x 2 + 7 x3 + 15 x 4 + 18 x5 + 9,5 x 6 + d 1- - d1+ = 10 * 1 500 000, 2 x1 + x 2 + 3 x3 + 8 x 4 + 10 x5 + 5 x 6 + d 2- - d 2+ = 6 * 1 500 000,
x1 + x2 + x3 + x4 + x5 + x6 = 1 500 000, x6 ≤ 600 000, x4 ≥ 300 000, x5 ≤ 500 000, xj ≥ 0, j = 1, 2, …, 6. Řešení v programu LINGO exportované do Excelu vidíte na obrázku 5.6.
Obrázek 5.6: Data a řešení v Excelu.
26
Kompromisní řešení je xopt = (0;0;424 709,3; 300 000; 175 290,7; 600 000) a účelová funkce zopt = (16 328 200; 8 427 035). Očekávaný výnos je větší o 9% než cílová hodnota a riziko je o 6,4% menší než cílová hodnota. Firma investuje 424 709,3 Kč do depozitních certifikátů, 300 000 Kč do akcií firmy A, 175 290,7 Kč do akcií firmy B a 600 000 Kč do dluhopisů firmy C.
5.3 Nutriční problém Vybrala jsem 11 druhů potravin z jídelního lístku společnosti KFC. V tabulce jsou uvedeny jejich nutriční hodnoty. Cílem je vybrat takové složení potravin, abychom minimalizovali cenu, maximalizovat obsah vápníku (Ca) a respektovali tyto podmínky: a) obsah bílkovin alespoň 70 g, b) obsah tuku maximálně 120 g, c) obsah karbohydrátu alespoň 150g, d) obsah vlákniny alespoň 10g, e) obsah energie alespoň 1500 kcal, f) obsah hořčík (Mg) alespoň 250mg. Vektor vah je (0,7;0,3) a cílové hodnoty jsou g1 = 600 kč (pro cenu) a g2 = 1 200mg (pro obsah vápníku).
Obsah
Obsah
bílkovin
tuku
[g]
[g]
Obsah Karbohy -drátů
Obsah vlákniny [g]
[g]
Energie
Mg
Ca
Cena
[kcal]
[mg]
[mg]
[Kč]
Zinger
28,5
22,3
39,2
0
471,3
41,9
32,8
69
Twister
21,5
20,9
36,9
0
421,6
38
38,2
74
Longer
13,9
7,5
36,7
1
265,8
30,6
34
29
7,3
7,6
3,5
0,1
109,2
6,8
36,1
13
0,7
0,2
2,5
0
13,9
6,1
19,1
39
10,1
7,5
13,7
4,8
143,2
30
89,2
99
Hot Wings Garden salát Salát Caesar
27
Popcorn
30,5
10,3
11
0
258,4
37,5
11,8
63
Hranolky
2,2
12,7
26,1
6,2
202,7
20,4
7,7
30
Colestaw
1,7
8,9
11,9
0,4
133,2
14,6
55
36
Kukuřice
6,5
4,1
48,7
7,9
226,5
73,9
10,2
39
5,5
3,2
23,7
1,2
140,7
14,8
125,7
24
Jogurt s višněmi
Tabulka 5.4: Přehled nutričních hodnot.
Matematický model formulujeme takto: maximalizovat z = 32,8 x1 + 38,2 x 2 + 34 x 3 + 36,1x 4 + 19,1x 5 + 89,2 x 6 + 11,8 x 7 + 7,7 x8 + 55 x9 + 10,2 x10 + 125,7 x11 ,
minimalizovat z = 69 x1 + 74 x 2 + 29 x 3 + 13 x 4 + 39 x 5 + 99 x 6 + 63 x 7 + 30 x8 + 36 x 9 + 39 x10 + 24 x11 ,
za podmínek 28,5 x1 + 21,5 x 2 + 13,9 x 3 + 7,3 x 4 + 0,7 x 5 + 10,1x 6 + 30,5 x 7 + 2,2 x8 + 1,7 x 9 + 6,5 x10 + 5,5 x11 ≥ 70, 22,3 x1 + 20,9 x 2 + 7,5 x3 + 7,6 x 4 + 0,2 x 5 + 7,5 x 6 + 10,3 x 7 + 12,7 x8 + 8,9 x 9 + 4,1x10 + 3,2 x11 ≤ 120, 39,2 x1 + 36,9 x 2 + 36,7 x 3 + 3,5 x 4 + 2,5 x 5 + 13,7 x 6 + 11x 7 + 26,1x8 + 11,9 x9 + 48,7 x10 + 23,7 x11 ≥ 150, 0 x1 + 0 x 2 + 1x 3 + 0,1x 4 + 0 x 5 + 4,8 x 6 + 0 x 7 + 6,2 x 8 + 0,4 x 9 + 7,9 x10 + 1,2 x11 ≥ 10, 471,3 x1 + 421,6 x 2 + 265,8 x3 + 109,2 x 4 + 13,9 x 5 + 143,2 x 6 + 258,4 x 7 + 202,7 x8 + 133,2 x9 + 226,5 x10 +
+ 140,7 x11 ≥ 1500, 41,9 x1 + 38 x 2 + 30,6 x 3 + 6,8 x 4 + 6,1x 5 + 30 x 6 + 37,5 x 7 + 20,4 x8 + 14,6 x 9 + 73,9 x10 + 14,8 x11 ≥ 250,
xj ≥ 0, j = 1, 2, …, 11, xj – celé. Model jako úloha cílového programování: minimalizovat z = 0,7 d1− /600 + 0,3d 2+ /1200, za podmínek 32,8 x1 + 38,2 x 2 + 34 x 3 + 36,1x 4 + 19,1x 5 + 89,2 x 6 + 11,8 x 7 + 7,7 x 8 + 55 x 9 + 10,2 x10 + 125,7 x11 + d 1- - d 1+ = 1200, 69 x1 + 74 x 2 + 29 x 3 + 13 x 4 + 39 x 5 + 99 x 6 + 63 x 7 + 30 x 8 + 36 x 9 + 39 x10 + 24 x11 + d 1- - d 1+ = 600,
28,5 x1 + 21,5 x 2 + 13,9 x 3 + 7,3 x 4 + 0,7 x 5 + 10,1x 6 + 30,5 x 7 + 2,2 x8 + 1,7 x 9 + 6,5 x10 + 5,5 x11 ≥ 70, 22,3 x1 + 20,9 x 2 + 7,5 x3 + 7,6 x 4 + 0,2 x 5 + 7,5 x 6 + 10,3 x 7 + 12,7 x8 + 8,9 x 9 + 4,1x10 + 3,2 x11 ≤ 120,
28
39,2 x1 + 36,9x 2 + 36,7 x3 + 3,5 x 4 + 2,5 x 5 + 13,7 x 6 + 11x 7 + 26,1x8 + 11,9 x9 + 48,7 x10 + 23,7 x11 ≥ 150, 0 x1 + 0 x 2 + 1x 3 + 0,1x 4 + 0 x 5 + 4,8 x 6 + 0 x 7 + 6,2 x 8 + 0,4 x 9 + 7,9 x10 + 1,2 x11 ≥ 10, 471,3 x1 + 421,6 x 2 + 265,8 x 3 + 109,2 x 4 + 13,9 x 5 + 143,2 x 6 + 258,4 x 7 + 202,7 x 8 + 133,2 x 9 + 226,5 x10 +
+ 140,7 x11 ≥ 1500, 41,9 x1 + 38x 2 + 30,6 x 3 + 6,8 x 4 + 6,1x 5 + 30 x 6 + 37,5 x 7 + 20,4 x8 + 14,6 x9 + 73,9 x10 + 14,8 x11 ≥ 250,
xj ≥ 0, j = 1, 2, …, 11, xj – celé. Příklad jsem řešila v programu LINGO aplikací obecného modelu. Řešení příkladu se exportovalo do Excelu (obrázek 5.7).
Obrázek 5.7: Data v Excelu. Kompromisní řešení je xopt = (1;0;3;0;1;1;1;0;1;1;7) a účelová funkce zopt = (1 200; 600). Optimální dávka potravin je následující: 1 Zinger, 3 Longery, 1 Garden salát, 1 salát Caesar, 1 popcorn, 1 Colestaw, 1 kukuřice a 7 jogurtů s višněmi. Cílové hodnoty jsou splněny přesně.
29
6 Závěr Cílem mé práce bylo sestavit obecný model cílového programování, který by se dal aplikovat na různé typy standardních příkladů lineárního programování. Při použití obecného modelu, který jsem sestavila, pouze stačí měnit data v datovém souboru. Jeho použití je jednoduché. Aplikaci obecného modelu jsem ukázala na několika nejčastějších úlohách lineárního programování (výrobní problém, optimalizace portfolia a nutriční problém). Ve všech příkladech používám stále stejný obecný model.
Firmy se v dnešní době neustále rozrůstají. Mají velké množství různých cílů, které chtějí optimalizovat. Právě cílové programování umožňuje podnikům optimalizovat všechny cíle zároveň. Můžou si pomocí vah nebo lexikograficky určit, které cíle jsou pro ně nejdůležitější a které jsou méně důležité.
30
Seznam použité literatury [1] Jablonský, J.: Operační výzkum. Professional publishing, 2002. [2] Jablonský, J.: Programy pro matematické modelování. Oeconomica, Praha 2007. [3] Dlouhý, M., Jablonský, J.: Modely hodnocení efektivnosti produkčních jednotek. Professional publishing, 2004. [4] Jablonský, J.: Integer goal programming applications using modelling systems and excel, Proceeding of the Conference MOPGP'00, Ustron 2000, Poland, pp.195201 [5] Jelínek, F.: Optimální řízení a cílové programování v činnosti podniku: [Autoreferát kand. dis.], Praha, 1987. [6] Ijiri, Y.: Management Goals and Accounting for Control, Amsterdam: NorthHolland Publishing Company, 1965. [7] Lee, S.M.: Goal Programming for Decision Analysis, Philadelphia: Auerbach Publishers Inc., 1972. [8] Spronk, J.: Interactive Multiple Goal Programming: Applications to Financial Planning, Amsterdam: Martinus Nijhoff, 1981. [9] Ignizio, J.P.: Introduction to Linear Goal Programming, Thousand Oaks, CA: Sage Publications, 1986. [10] Romero, C., Rehman, T.: Multiple Criteria Analysis for Agricultural Decisions, Amsterdam: Elsevier, 1989. [11] Schniederjans, M.J.: Goal Programming: Methodology and Applications, Boston: Kluwer Academic Publishers, 1995. [12] Tamiz, M., ed.: Multi-Objective Programming and Goal Programming: Theories and Applications, Berlin: Springer-Verlag, 1996. [13] Ballestero, E., Romero, C.: Multiple Criteria Decision Making and Its Applications to Economie Problems, Boston: Kluwer Academic Publishers, 1998. [14] Charnes, A., Cooper, W. W., Ferguson, R.: "Optimal estimation of executive compensation by linear programming," Management Science vol. 1, no. 2, 1955, 138-151.
31
[15] Bertsimas, D., Sim, M: Robust discrete optimization and network flows. Math. Program. 2003, Ser. B 98, 49-71
Internetové zdroje [16] http://matwbn.icm.edu.pl/ksiazki/cc/cc33/cc3336.pdf, (24. 3. 2009) [17] http://www.kfc.cz/index.php?sec=nutricni-hodnoty, (24.3.2009) [18] http://findarticles.com/p/articles/mi_qa3661/is_200408/ai_n10297971/?tag= content; col1, (6.4.2009)
32
