Rovnomerné rozvrhy a fuzzy lineárne programovanie

27. Apríl, 2011, Autor článku: Ladovský Tomáš, Informačné technológie
Ročník 4, číslo 4 Pridať príspevok

Článok sa zaoberá problematikou tvorby rovnomerných rozvrhov. Pod rovnomernými rozvrhmi si môžeme napríklad predstaviť rozpisovanie služieb vodičom autobusov, v ktorom rozpisujeme služby tak, aby vodiči autobusov mali zrovnomernené pracovné výkony. Rovnomerné rozvrhy môžeme zovšeobecniť a matematicky formulovať ako problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice.

Nás zaujíma špeciálne dvojriadková matica, ktorej riadkové súčty zrovnomerňujeme pomocou fuzzifikovanej úlohy o batohu. Takto vzniknutý model fuzzy bivalentného programovania riešime pomocou Belmanovho a Zadehovho princípu rozhodovania.

1. Úvod

V tomto článku rozumieme pod pojmom tvorba rozvrhu alebo rozvrhovanie proces rozhodovania, ktorý sa používa vo výrobnom priemysle, vo verejnej doprave a v iných odvetviach a službách. Pracuje s prideľovaním aktivít k zdrojom nad danými časovými periódami a snaží sa optimalizovať jednu alebo viac kritériálnych funkcií tak, aby boli splnené všetky podmienky priradené k jednotlivým aktivitám a zdrojom. Z iného pohľadu je tvorba rozvrhov problémom časového plánovania a kombinatorickej optimalizácie. To sú problémy v ktorých vystupujú diskrétne premenné a v ktorých množina prípustných riešení je konečná. V každom z týchto problémov sa skrýva možnosť kombinatorickej explózie.

Rozvrh je súbor údajov, z ktorého je zrejmé, v ktorých časových intervaloch sa majú jednotlivé aktivity realizovať na ktorých zdrojoch. Zdrojmi môžu byť vodiči autobusov, stroje v dielni, viacnásobné/viacjadrové procesory, dopravné prostriedky, robotníci na pracovisku a veľa iného. Aktivitami môžu byť turnusy v autobusovej doprave, úlohy (operácie) vo výrobnom procese, vykonávanie počítačových programov, etapy pri stavebnom projekte a iné. Každá aktivita má naplánovanú dobu trvania.

V reálnom živote sa stretávame so zrovnomerňovaním pracovných zaťažení/výkonov strojov/vodičov za dané časové (periodické) obdobie rozvrhovania. Aby sme vedeli optimalizovať rovnomernosť rozvrhov, potrebujeme poznať mieru nerovnomernosti, ktorá je jednou z optimalizovaných kritériálnych funkcií a môže nadobúdať nasledujúci tvar

$f_{dev}(x_1, \dots, x_m) = \frac{1}{m} \sum_{i=1}^{m} \frac{|x_i-\bar{x}|}{\bar{x}}$

(1)

Za predpokladu, že vytvárame rozvrh vo výrobnom odvetví, predstavujú jednotlivé premenné $x_1$ až $x_m$ plánované pracovné zaťaženia m strojov a $\bar{x}$ je ideálnym pracovným zaťažením strojov, v tomto prípade priemernou hodnotou, ktorú spočítame ako

$\bar{x} = \frac{1}{m} \sum_{i=1}^{m} x_i$

Rozvrhy, ktoré vznikli optimalizáciou miery nerovnomernosti, nazývame rovnomernými rozvrhmi. Vzhľadom na známu Grahamovu [3] klasifikáciu ide o neštandardný typ rozvrhov.

Pod pojmom rovnomerné rozvrhy pri neistote rozumieme v nasledujúcom texte také rovnomerné rozvrhy, ktorých veľkosť aktivít je neistá a/alebo podmienky priradené k jednotlivým aktivitám a zdrojom sú vyjadrené neisto. S neistou kritériálnou funkciou a/alebo s neistými podmienkami sa môžeme stretnúť, ak napríklad modelujeme doby trvania aktivít pomocou fuzzy čísel a/alebo definujeme podmienky priradené k aktivitám a zdrojom neisto a chceme takto modelovaný problém riešiť pomocou optimalizačných algoritmov lineárneho programovania. Za týchto podmienok vznikajú modely lineárneho programovania, ktoré nemusia byť jednoznačne definovateľné. Ich definovateľnosť závisí na type neurčitosti a ich špecifikácií, ktorú stanovil tvorca rozhodnutí. Preto triedy problémov fuzzy lineárneho programovania môžeme všeobecne klasifikovať ako [1]:

PLP s ostrou účelovou funkciou a fuzzy nerovnosťami.
PLP s fuzzy účelovou funkciou a ostrými nerovnosťami.
PLP s fuzzy účelovou funkciou a fuzzy nerovnosťami.
PLP s fuzzy zdrojmi a fuzzy koeficientami, teda elementy c, b a A sú fuzzy.

Na riešenie takto zadefinovaného PLP použijeme v článku Bellmanov a Zadehov princíp modelu fuzzy tvorby rozhodnutí [1]

2. Matrix permutation problem

Rovnomerné rozvrhy môžeme zovšeobecniť a matematicky formulovať ako kombinatorický problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice, ktorý anglicky označujeme ako matrix permutation problem MPP [5]. Vhodným preusporiadaním stĺpcov matice môžeme docieliť väčšiu rovnomernosť riadkových súčtov matice/rozvrhu.

Definícia 1 (Matrix permutation problem [4])

Nech M={1,2,…,m} a N={1,2,…,n} sú konečné neprázdne množiny a nech $A=(a_{ij})\in\mathfrak R^{m\times n}$ je reálna matica rozmeru $m\times n$ . Hľadá sa taká matica permutácií $\Psi = (\psi_j)_{j\in N}$ stĺpcov matice A pre ktorú platí:

$\min\Big\{ f(s^{\psi}_1,s^{\psi}_2,\dots,s^{\psi}_m) | s^{\psi}_i=\sum_{j\in\mathcal N} a_{\psi_{ij},j},\forall i\in\mathcal M, \psi_j =$

$= (\psi_{1j},\psi_{2j}\dots,\psi_{mj})\in\Pi(\mathcal M),\forall j\in\mathcal N \Big\}$

kde f je nejaká miera nerovnomernosti vektora reálnych čísel, $s^{\psi}_i$ je i-ty riadkový súčet matice ${\mathrm A}^\psi$ a $\Pi(\mathcal M)$ je množina všetkých permutácií množiny $\mathcal M$ . Riešením takto formulovanej úlohy MPP je matica ${\mathbb A}^\psi = (a_{\psi_{ij},j})$ .

MPP je zložitosti $O((m!)^n)$ . Z tohoto dôvodu sú exaktne riešiteľné len veľmi malé inštancie. Na riešenie veľkých inštancií môžeme použiť heuristické metódy. Najznámejšou a najvhodnejšou heuristickou metódou, ktorá je veľmi rýchla a dosahuje veľmi dobré výsledky, je stochastická-dekompozičná metóda [4,5].

Príklad1 (Rozpisovanie služieb vodičom autobusov, alias (MPP))

Majme 4 vodičov autobusov a 5 pracovných dní. Pre každý pracovný deň majú byť pridelené 4 turnusy, pričom prvok $a_{ij}$ matice $\mathbb A=(a_{ij})\in\mathfrak R$ zodpovedá pracovnému času [min] i-teho turnusu v j-ty deň.

$\mathbb A=\left( \begin{array}{c c c c c} 660 & 540 & 530 & 460 & 680 \\ 630 & 500 & 570 & 630 & 710 \\ 510 & 640 & 680 & 580 & 650 \\ 450 & 460 & 540 & 450 & 680 \end{array} \right)$

Tvorca rozvrhu chce priradiť vodičom turnusy na jednotlivé dni tak, aby hodnota miery nerovnomernosti (1) bola minimálna. Ak ich priradí každý deň rovnako, tak že i-ty vodič dostane priradený i-ty turnus, t.j. $\psi_{ij} = i$ , tak by miera nerovnomernosti bola rovná hodnote $f_{dev}=0.056$ . Táto hodnota nás informuje o tom, že týždenné výkony vodičov sú priemerne odchýlené od ideálnej hodnoty o 5,6%. Potom tvorca rozvrhu použije stochastickú-dekompozičnú metódu a vygeneruje pomocou nej nasledovnú maticu permutácií $\Psi$ a maticu $\mathbb A^{\psi}$ .

$\Psi=\left( \begin{array}{c c c c c} 4 & 3 & 4 & 3 & 4 \\ 3 & 2 & 2 & 2 & 1 \\ 2 & 4 & 3 & 1 & 3 \\ 1 & 1 & 1 & 4 & 2 \end{array} \right)$

$\mathbb A^{\psi}=\left( \begin{array}{c c c c c} 450 & 640 & 540 & 580 & 680 \\ 510 & 500 & 570 & 630 & 680 \\ 630 & 460 & 680 & 460 & 650 \\ 660 & 540 & 530 & 450 & 710 \end{array} \right)$

Pre tento rozvrh získavame nasledujúcu hodnotu miery nerovnomernosti $f_{dev}=0.001$ .

V predošlom texte sme sa dozvedeli, že rovnomerné rozvrhy môžeme zovšeobecniť a matematicky formulovať ako problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice. Veľmi zaujímavá varianta problému (MPP) vzniká pre dvojriadkovú maticu, viď. nasledujúci text.

3. Problém dvojriadkovej matice

Problém rovnomernosti riadkových súčtov stĺpcovo permutovanej \textit{dvojriadkovej matice} (MPP2r) môžeme transformovať na úlohu o batohu. Klasická úloha o batohu KUB je jednou z najznámejších a najpoužívanejších úloh matematického bivalentného programovania. KUB tvorí jadro mnohých heuristických metód. Jej matematická formulácia je nasledovná.

Definícia 2 (Klasická úloha o batohu KUB)

Úlohu o batohu môžeme formulovať ako úlohu, v ktorej máme predmety rôznych cien a hmotností zabaliť do batohu tak, aby jeho hodnota bola čo možno najväčšia a nebola prekročená jeho nosnosť. Nech $N, |N| = n$ je konečná množina, c je n-prvkový vektor cien predmetov, a je n-prvkový vektor hmotností predmetov, b je nosnosť batohu a x je n-prvkový vektor rozhodovacích premenných. Potom úlohu o batohu možno formulovať ako nasledujúcu úlohu bivalentného lineárneho programovania.

$\left. \begin{array}{c} \max Z = \sum_{j\in N}{c_j x_j} \\ s.t. \\ \sum_{j\in N}a_j x_j \leq b, \\ x_j\in\{0,1\}, pre \quad \forall j\in N \end{array} \right\}$

(2)

Veta1 (Transformácia MPP2r na KUB)

Pre danú maticu $\mathbb D = (d_{ij})$ typu $2\times n$ a maticu permutácií $\Psi = (\psi_j)_{j\in N}$ množiny $\mathcal M=\{1,2\}$ môžeme úlohu MPP2r pretransformovať na klasickú úlohu o batohu pomocou substitúcie

$c_j = a_j = d_{1j}-d_{2j},\quad\text{pre}\quad \forall j = 1,2,\dots, n$

(3)

$b = \frac{1}{2}\sum_{j=1}^{n} (d_{1j}-d_{2j}),$

(4)

kde vektor rozhodnutí $x = (x_1, x_2, \dots, x_n)$ priradenia predmetu do batohu formulujeme ako

$\psi_j = \left\{ \begin{array}{c} (1,2), \text{vlozime j-ty predmet do batohu, t.j. } x_j = 1 \\ (2,1), \text{nevlozime j-ty predmet do batohu, t.j. } x_j = 0 \end{array} \right.$

Dôkaz 1 (Transformácia MPP2r na KUB)

Majme maticu $\mathbb D=(d_{ij})$ rozmeru $2\times n$ , pre ktorú hodnotu ideálneho riadkového súčtu spočítame ako

$\bar{s} = \frac{1}{2}\sum_{j=1}^{n} (d_{1j} + d_{2j})$

Nech $\Psi = (\psi_j)_{j\in N}$ je matica permutácií a nech vektor $x = (x_1, x_2, \dots, x_n)$ predstavuje rozhodnutia, ktoré môžeme formulovať ako:

$x_j = \left \{ \begin{array}{c} 1 \quad potom \quad \psi_{j} = (1,2) \\ 0 \quad potom \quad \psi_{j} = (2,1) \end{array} \right.$

Aby boli riadkové súčty matice čo najrovnomernejšie, alebo aby sa v ideálnom prípade rovnali ideálnemu riadkovému súčtu, potom musí urobiť tvorca rozvrhu také rozhodnutia $\bf{x}$ , pre ktoré platí nasledujúca rovnosť

$\sum_{j=1}^{n}d_{1j}x_j + \sum_{j=1}^{n}d_{2j}(1-x_j) = \bar{s}$

ktorú môžeme po dosadení $\bar{s}$ a pomocou substitúcií $c_j = a_j = d_{1j}-d_{2j}$ a $b = \frac{1}{2}\sum_{j=1}^{n} (d_{1j}-d_{2j})$ prepísať na tvar

$\sum_{j=1}^{n}c_jx_j = b$

Bez ujmy na všeobecnosti môžeme rovnosť rozpísať na nerovnosti

$\sum_{j=1}^{n}a_jx_j \leq b$

(5)

$\sum_{j=1}^{n}c_jx_j - b \geq 0$

(6)

Aby sme úspešne transformovali zadanú úlohu na model úlohy o batohu, môžeme z ľavej strany nerovnosti (6) vypustiť konštantu b a nerovnosť použiť ako účelovú funkciu, ktorú maximalizujeme. Prvá nerovnosť (5) zaručuje, že súčet prvého riadku nepresiahne hodnotu b. Druhá nerovnosť (6) (účelová funkcia) sa naopak pokúša naakumulovať súčet prvého riadku čo najtesnejšie k hodnote b. Po takýchto úpravách získavame model klasickej úlohy o batohu (2).

Príklad 2 (Ilustračný príklad problému MPP2r)

Príkladom aplikácie KUB pri tvorbe rovnomerných rozvrhov môže byť nasledujúca úloha: Nech elementy matice $\mathbb D=(d_{ij})$ rozmeru $2\times 5$ predstavujú pracovné časy i-teho turnusu, ktorý máme prejsť v j-ty deň.

$\mathbb A=\left( \begin{array}{c c c c c} 35 & 45 & 25 & 45 & 20 \\ 25 & 30 & 22 & 30 & 35 \end{array} \right)$

Pre každý deň 5-dňového obdobia máme rozhodnúť o tom, ktorému z dvojice vodičov pridelíme ktorý turnus, tak aby celkové kumulované výkony oboch vodičov, boli čo najviac rovné ideálnemu výkonu

$\bar{s} = \frac{1}{2}\sum_{j=1}^{n} (d_{1j} + d_{2j}) = 156$

za celé časové obdobie. Nech vektor x predstavuje rozhodnutia, ktoré môžeme formulovať ako:

$x_j = \left \{ \begin{array}{c} 1 \\ 0 \end{array} \right.$

1 – Ak sa rozhodneme priradiť prvému vodičovi prvý turnus s časom spracovania $d_{1j}$ a druhému vodičovi druhý turnus s časom spracovania $d_{2j}$ v j-ty pracovný deň,
0 – Ak sa rozhodneme priradiť prvému vodičovi druhý turnus s časom spracovania $d_{2j}$ a druhému vodičovi prvý turnus s časom spracovania $d_{1j}$ v j-ty pracovný deň.

Nech usporiadaná petica $c = a = (10,15,3,15,-15)$ predstavuje cenu a váhu predmetu a b=14 predstavuje nosnosť batohu. Riešením úlohy (2) získame nasledujúcu usporiadanú peticu rozhodnutí $x = (1, 1, 1, 0, 1)$ , pre ktorú je matica permutácií $\Psi$ rovná hodnotám

$\Psi=\left( \begin{array}{c c c c c} 1 & 1 & 1 & 2 & 1 \\ 2 & 2 & 2 & 1 & 2 \end{array} \right)$

a riadkové súčty sú rovné $s^{\Psi} = (155, 157)$ .

Nasledujúci text bližšie formuluje a ilustračne rieši problém fuzzy úlohy o batohu FUB$ vzhľadom na vyššie klasifikované problémy fuzzy lineárneho programovania a to na základe Bellmanovho a Zadehovho princípu modelu fuzzy tvorby rozhodnutí.

4. Belmanov a Zadeho princíp

Model fuzzy tvorby rozhodnutí je charakterizovaný množinou možných akcií/alternatív X, a množinou cieľov $G_i$ pre $i=1,2,\dots,m$ popri množine obmedzení $C_j$ pre $j=1,2,\dots,n$ . Každá z množín $G_i$ a $C_j$ je vyjadrená pomocou fuzzy množiny. Pre takýto model tvorby rozhodnutí navrhli Bellman a Zadeh [2] v ich priekopnickej práci, že fuzzy rozhodnutie je určené pomocou agregovania fuzzy množín $G_i$ a $C_j$ , pričom hlavným znakom je symetria medzi cieľmi a obmedzeniami. Na základe takéhoto prístupu doporučili použiť ako agregačný operátor fuzzy prienik. Preto fuzzy rozhodnutie D môže byť definované ako fuzzy množina $D = (G_1 \cap G_2 \cap \dots \cap G_m) \cap (C_1 \cap C_2 \cap \dots \cap C_n)$ , inými slovami $\mu_D: X \rightarrow [0,1]$ je dané pomocou

$\mu_D(x) = \min_{i,j}\left( \mu_{G_i}(x), \mu_{C_j}(x) \right)$

Akonáhle je fuzzy rozhodnutie $D$ známe, môžeme definovať $x^* \in X$ ako optimálne rozhodnutie, ak

$\mu_{D}(x^*) = \max_x\mu_D(x)$

Inou možnosťou je zvoliť stupeň $\alpha$ ( $0 < \alpha < 1[/latex]) a určiť všetky body [latex]x^*\in X[/latex], pre ktoré je [latex]\mu_D(x^*)\geq\alpha[/latex]. Takéto rozhodnutia [latex]x^*[/latex] budú mať hodnotu aspoň stupňa [latex]\alpha[/latex] funkcie členstva. Príklad 3 Ilustračný príklad fuzzy rozhodovacieho problému [10] Ako ilustráciu riešme fuzzy rozhodovací problém, v ktorom máme vypočítať skutočný výkon vodiča x [hod], ktorý je približne 60 [hod] za týždeň (fuzzy obmedzenie C) a zároveň je väčší ako 50 [hod] (fuzzy cieľ G). Pre tento príklad môžeme obmedzenie a cieľ vyjadriť pomocou ich funkcií príslušenstva a to nasledujúco <table style="width:100%;"> <tr> <td style="text-align:center;"><img src='http://s0.wp.com/latex.php?latex&bg=ffffff&fg=000000&s=0' alt='' title='' class='latex' />\mu_C(x) = (1 + (1/300)(x - 60)^4)^{-1}$

$\mu_G(x) = \left\{ \begin{array}{ccc} 0 & , & x \leq 50 \\ (1+5(x-50)^{-2})^{-1} & , & x > 50 \end{array} \right.$

Ďalej poznamenajme, že v tomto prístupe sú ciele a obmedzenia symetrické a preto môžeme zapísať $\mu_G(x)$ ako $\mu_C(x)$ a naopak. Podľa Bellmanovho a Zadehovho prístupu [2] je fuzzy rozhodnutie $D$ rovné $G\cap C$ a teda

$\mu_D(x) = \min(\mu_G(x), \mu_C(x))$

Diagram (obrázok 1) znázorňuje fuzzy rozhodovací problém a identifikuje optimálne riešenie $x^*$

Fig. 1. Grafická reprezentácia μ_D a x^*

5. Ostrá účelová funkcia a fuzzy kapacitné podmienky

Teraz sa pokúsime riešiť úlohu o batohu s ostrou účelovou funkciou a fuzzy kapacitnou nerovnosťou $\lessapprox$ , ktorú čítame fuzzy menšie alebo rovné ako, vo svetle Bellmanovho a Zadehovho princípu. Na riešenie použijeme nesymetrický Verdegayov prístup [7,8] rozšírený o symetrický Wernersov model [9], ktorý podľa Bellmanovho a Zadehovho symetrického prístupu doporučuje okrem vhodnej voľby funkcie príslušnosti nerovnosti [7,8], navrhnúť aj funkciu príslušnosti pre účelovú funkciu. Teda fuzzy kapacitná nerovnosť úlohy o batohu je vhodnou voľbou funkcie príslušnosti transformovaná na ostrú nerovnosť. Verdegay doporučuje voliť funkciu príslušnosti na základe nasledujúcej úvahy. Ak platí

$\sum_{j\in N}a_j x_j \leq b$

potom je kapacitná podmienka absolútne splnená, ale ak

$\sum_{j\in N}a_j x_j \geq b+p$

kde p predstavuje kapacitnú toleranciu batohu, potom je kapacitná podmienka absolútne porušená. Teraz môžeme definovať spojitú neklesajúcu lineárnu funkciu príslušnosti $\mu_C$ kapacitnej podmienky ako

$\mu_C(a^Tx) = \left\{ \begin{array}{ccc} 1 & \text{pre} & a^Tx b+p \end{array} \right.$

Pre vhodnú voľbu funkcie príslušnosti účelovej funkcie doporučuje Werners vyriešiť nasledujúce dva modely klasickej úlohy o batohu

$\begin{array}{c} LP1 \\ \max Z_0 = \sum_{j\in N}{c_j x_j} \\ s.t. \\ \sum_{j\in N}a_j x_j \leq b \\ x_j\in\{0,1\}, \quad pre \quad \forall j\in N \end{array}$

$\begin{array}{c} LP2 \\ \max Z_1 = \sum_{j\in N}{c_j x_j} \\ s.t. \\ \sum_{j\in N}a_j x_j \leq b+p \\ x_j\in\{0,1\}, \quad pre \quad \forall j\in N \end{array}$

Hodnoty účelovej funkcie $Z_0$ a $Z_1$ predstavujú porade cenu batohu za najmenej a najviac priaznivých podmienok. Teraz môžeme pomocou hodnôt $Z_0$ a $Z_1$ definovať spojitú neklesajúcu lineárnu funkciu príslušnosti $\mu_C$ účelovej funkcie ako

$\mu_G(c^Tx) = \left\{ \begin{array}{ccc} 0 & \text{pre} & c^Tx < Z_0 \\ \frac{c^Tx-Z_0}{Z_1-Z_0} & \text{pre} & Z_0 \leq c^Tx \leq Z_1 \\ 1 & \text{pre} & c^Tx > Z_1 \end{array} \right.$

Za pomoci funkcií príslušnosti $\mu_G$ a $\mu_C$ a podľa Bellmanovho a Zadehovho symetrického prístupu, môžeme fuzzy úlohu o batohu s ostrou účelovou funkciou a kapacitnou fuzzy nerovnosťou, riešiť pomocou nasledujúceho bivalentného lineárneho programovania

$\begin{array}{c} \max \alpha \\ s.t. \\ \mu_G(x)\geq \alpha \\ \mu_C(x)\geq \alpha \\ \alpha\in[0,1] \\ x_j\in\{0,1\}, pre \quad \forall j\in N \end{array}$

Dosadením funkcií príslušnosti $\mu_G$ a $\mu_C$ obdržíme nasledujúci problém

$\begin{array}{c} \max \alpha \\ s.t. \\ c^Tx\geq Z_1\alpha+Z_0(1-\alpha) \\ a^Tx\leq b + (1-\alpha)p \\ \alpha\in[0,1] \\ x_j\in\{0,1\}, pre \quad \forall j\in N \end{array}$

(7)

Funkciu príslušnosti fuzzy kapacitnej podmienky a fuzzy účelovej funkcie môžeme vidieť na obrázku 2.

Fig.2 Podľa Bellmanovho a Zadehovho prístupu [2] je funkcia príslušnosti fuzzy rozhodnutia $\mu_D$ rovná prieniku funkcie príslušnosti fuzzy kapacitnej podmienky $\mu_C$ a funkcie príslušnosti fuzzy účelovej funkcie $\mu_C$ .

Príklad 4 (UB s ostrou účelovou funkciou a fuzzy nerovnosťou)

Pokračujme v príklade(2). Problém riešme pomocou fuzzy úlohy o batohu [9], pre ktorú definujeme ceny a váhu predmetov ako $c_j = a_j = d_{1j}-d_{2j}$ pre $\forall j = 1,\dots,5$

$c = a = \left( \begin{array}{c c c c c} 10 & 15 & 3 & 15 & -15 \end{array} \right)$

a nosnosť batohu je rovná hodnote $b = \frac{1}{2}\sum_{j=1}^{n}c_j = 14$ .

Po vyriešení úlohy LP1 obdržíme vektor rozhodnutí $x = (1,1,1,0,1)$ s hodnotou účelovej funkcie $Z_0 = 13$ . Po vyriešení úlohy LP2 s parametrom tolerancie $p=6$ obdržíme vektor rozhodnutí $x = (0,1,1,1,1)$ s hodnotou účelovej funkcie $Z_1 = 18$ . Teraz môžeme riešiť fuzzy úlohu o batohu 7, ktorej riešením je vektor rozhodnutí $x = (0,1,0,1,1)$ , premennou $\alpha = 0.4$ s rozvrhom

$\mathbb R = \left( \begin{array}{c c c c c} 25 & 45 & 22 & 45 & 20 \\ 35 & 30 & 25 & 30 & 35 \end{array} \right)$

s mierou nerovnomernosti $f_{dev} = 0.006$ a s hodnotou účelovej funkcie $Z = 15$ . Funkciu príslušnosti fuzzy kapacitnej podmienky a fuzzy účelovej funkcie s optimálnym riešením $c^Tx = a^Tx = 15$ môžeme vidieť na obrázku 3.

Fig. 3 Z dôvodu bivalentnoti premenných nie je optimálne riešenie rovné maximálnej hodnote prieniku fuzzy množiny cieľov a podmienky.

6. Fuzzy účelová funkcia a fuzzy kapacitné podmienky

Teraz sa pokúsime riešiť úlohu o batohu s fuzzy účelovou funkciou a fuzzy kapacitnou nerovnosťou. Na riešenie použijeme symetrický Zimmermannov prístup, v ktorom je funkcia príslušnosti kapacitnej podmienky volená rovnako ako pri predošlej Wernersovej metóde. V tomto prípade ale Zimmerman predpokladá, že fuzzyfikovaný operátor účelovej funkcie $\widetilde{\max}$ je chápaný v zmysle dosiahnutia čo možno najlepšie aspiračnej hladiny $Z$ . Vzhľadom na tento predpoklad môžeme zapísať matematický model úlohy o batohu ako

$\begin{array}{c} \text{Najdi } x, \text{pre ktore} \\ s.t. \\ c^Tx \gtrapprox Z \\ a^Tx \lessapprox b \\ x\in\{0,1\}^n \end{array}$

(8)

Na vyriešenie problému (8) musíme najskôr vhodne zvoliť funkciu príslušnosti pre obe fuzzy nerovnosti a aplikovať Bellmanov a Zadehov princíp na obdržanie fuzzy rozhodnutia.

Nech $p_G$ a $p_C$ predstavujú povolené tolerancie účelovej funkcie a kapacitnej podmienky. Nech $\mu_G$ značí funkciu príslušnosti účelovej funkcie a $\mu_C$ predstavuje funkciu príslušnosti kapacitnej podmienky fuzzy úlohy o batohu problému (8), ktoré môžeme písať ako

$\mu_C(a^Tx) = \left\{ \begin{array}{ccc} 0 & \text{pre} & c^Tx < Z - p_G \\ 1 - \frac{Z-c^Tx}{p_G} & \text{pre} & Z - p_G \leq c^Tx \leq Z \\ 1 & \text{pre} & c^Tx > Z \end{array} \right.$

$\mu_C(a^Tx) = \left\{ \begin{array}{ccc} 1 & \text{pre} & a^Tx b+p_C \end{array} \right.$

Teraz na základe Bellmanovho a Zadehovho princípu sme schopní identifikovať fuzzy rozhodnutie a vyriešiť problém systému fuzzy nerovností odpovedajúcich problému (8). Substitúciou funkcií príslušností obdržíme nasledujúci ostrí problém bivalentného lineárneho programovania,

$\begin{array}{c} \max \alpha \\ s.t. \\ \quad c^Tx\geq Z-(1-\alpha)p_G \\ \quad a^Tx\leq b + (1-\alpha)p_C \\ \quad \alpha\in[0,1] \\ \quad x\in\{0,1\}^n\end{array}$

(9)

Ak dvojica $(x^*,\alpha^*)$ je optimálnym riešením (9), potom povieme, že $x^*$ je optimálnym riešením problému (8) a $\alpha^*$ je stupeň, s ktorím tvorca rozvrhu dosiahol aspiračný level $Z$ .

Príklad 5 (s fuzzy účelovou funkciou a fuzzy nerovnosťou)

Aj tentoraz použime zadanie príkladu 2. Problém riešme pomocou fuzzy úlohy o batohu (9), pre ktorú môžeme definovať ceny a váhu predmetov ako $c_j = a_j = d_{1j}-d_{2j}$ pre $\forall j = 1,\dots,5$

$c = a = \left( \begin{array}{c c c c c} 10 & 15 & 3 & 15 & -15 \end{array} \right)$

a nosnosť batohu je rovná hodnote $b = \frac{1}{2}\sum_{j=1}^{n}c_j = 14$ .

Z nerovnosti (6) tentoraz nebudeme vypúšťať kapacitné obmedzenie batohu, ale použijeme ho ako aspiračný level $Z = b$ . Pre toleranciu aspiračného levelu ceny batohu a toleranciu nosnosti batohu sú volené nasledujúce hodnoty $p_G = 4$ a $p_C = 6$ .

Dosadením hodnôt c, a, Z, b, $p_G$ a $p_C$ do matematického modelu (9) a jeho riešením obdržíme optimálny vektor rozhodnutí $x^*=(0,1,0,1,1)$ a $\alpha = 0.83$ . Funkciu príslušnosti fuzzy kapacitnej podmienky a fuzzy účelovej funkcie s optimálnym riešením $c^Tx = a^Tx = 15$ môžeme vidieť na obrázku 4.

Fig. 4 Obrázok zobrazuje prienik funkcie príslušnosti účelovej funkcie s funkciou príslušnosti kapacitnej podmienky a optimálne riešenie $x^* = 15$ úlohy.

7. Záver

Článok sa zaoberal problematikou tvorby rovnomerných rozvrhov. Táto problematika je taktiež známa pod menom “problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice”, ktorá je známa pod anglickým menom Matrix Permutation Problem, ktorý je výpočtovo jedným z najkomplexnejších matematických modelov súčastnosti. Zaujala nás hlavne dvojriadková matica MPP2r, ktorej riešenie je použiteľné v heuristických metódach. MPP2r sme pretransformovali na klasickú úlohu o batohu KUB.

Vďaka charakteru MPP2r a vhodného matematického tvaru úlohy o batohu, sa MPP2r stala vhodným ilustračným príkladom aplikácie Belmanovho a Zadehovho princípu fuzzy rozhodovania. Teda na riešenie MPP2r pretranformovaného na KUB sme použili najskôr nesymetrický Verdegayov prístup rozšírený o symetrický Wernersov model, pomocou ktorého sme riešili fuzzifikovanú úlohu o batohu s ostrou účelovou funkciou a fuzzy kapacitnou nerovnosťou. Potom sme MPP2r riešili pomocou symetrického Zimmermannovho prístupu s fuzzy účelovou funkciou a fuzzy kapacitnou nerovnosťou.

Poďakovanie

Táto práca vznikla s podporou grantovej agentúry VEGA vrámci riešenia projektu 1/0374/11 “Modelovanie a optimalizácia mobility a infraštruktúry v logistických sieťach.”.

References

Bector, C.R., Chandra, S., Fuzzy Mathematical Programming and Fuzzy Matrix Games, Springer Berlin Heidelberg New York, ISBN 3-540-23729-1, 2005
Bellman, R.E., Zadeh, L.A., Decision making in a fuzzy environment, Management Science, vol. 17, pp. 141-164, 1970
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, 1979
Peško, Š., Optimalizácia NP-ťažkých dopravných rozvrhov, ŽU Žilina, Habilitačná práca, 2002
Peško, Š., The Matrix Permutation Problem in Interval Arithmetic, Journal of Information, Control and Management Systems, vol. 1, num. 1, 2006
Fiedler, M., Nedoma, J., Ramík, J., Rohn, J., Zimmermann, K., Linear Optimization Problems with Inexact Data, Springer, ISBN 0-387-32697-9, 2006
Verdegay, J.L., Fuzzy mathematical programming, in M.M. Gupta and E. Sanches (eds.), Fuzzy Information and Decision Processes, North Holland, Amsterdam, 1982
Verdegay, J.L., A dual approach to solve the fuzzy linear programming problem, Fuzzy Sets and Systems, vol. 14, pp. 131-141, 1984
Werners, B., Interactive multiple objective programming subject to flexible contraints, European Journal of Operations research, vol. 31, pp. 342-349, 1987
Zimmermann, H.J., Fuzzy Set Theory and Its Applications, 3. Edition, Kluwer Academic Publichers, Nowell, MA, USA, 1996
GNU Linear Programming Kit (GLPK), Package for solving large-scale linear programming (LP) and mixed integer programming (MIP)

O časopise

Meta

RSS

Rovnomerné rozvrhy a fuzzy lineárne programovanie

Napísať príspevok

Rubriky

Burza práce

Štúdijné materiály

Archív