9 Úloha celočíselné optimalizace Úlohy lineárního programování již ponecháme za námi a podíváme se na novou zajímavou třídu optimalizačních úloh: V praxi se totiž často vyskytují okolnosti formulace úloh, ve kterých některé (či všechny) vystu- pující proměnné mohou nabývat pouze celočíselných hodnot. (Například nemůžeme jednoho pracovníka "přepůlit" na dva úkoly, započatý pracovní úkon třeba nelze přerušit, nemůžeme poslat na trasu linky pouze čtvrt autobusu, a podobně.) Zmíněné okolnosti pak vedou na úlohy celočíselné lineární optimalizace, neboli celočíselné programování IP. V zásadě se dá říci, že úloha IP je úlohou LP s dodatečnými podmínkami celočíselnosti proměnných. Tato analogie je však zavádějící, neboť úlohy IP jsou nesrovnatelně komplikovanější při formulaci i obtížnější při řešení. Stručný přehled lekce ˇ Ukázat matematické formulace úloh celočíselné optimalizace. ˇ Formální zápis úloh IP a MIP pomocí matic a vektorů. ˇ Základní popis metody větvení a mezí pro řešení úloh IP. Petr Hliněný, FI MU 1 IA102 "OU": Celočíselná optimalizace 9.1 Úvodní příklady IP Opět pro názornost výkladu začneme hned s jednoduchými příklady úloh celočíselné optimalizace. Poznamenáváme, že pro tuto třídu úloh se používají zkratky IP nebo obecněji MIP. (Z anglického Integer Programming.) Příklad 9.1. Opět se vraťme ke starému známému Příkladu 3.1 o lupíncích a hranol- cích s dodatečným požadavkem, že musíme vyrábět (kvůli balení produktů) lupínky i hranolky v celočíselných násobcích množství 15kg. Řešení: Použijeme původní LP formulaci úlohy 2 + 1.5h 100 0.4 + 0.2h 16 , h 0 , ale přidáme dodatečnou podmínku = 15z1, h = 15z2, kde z1, z2 N . (1) Graficky si tuto formulaci vyznačíme na Obrázku 9.1. Všimněme si, že je nově nalezené řešení = 15kg, h = 45kg mírně horší než v Příkladě 3.1 bez podmínky celočíselnosti = 20kg, h = 40kg. Je přirozené, že přidáním dalších podmínek se kvalita řešení může zhoršit. Petr Hliněný, FI MU 2 IA102 "OU": Celočíselná optimalizace 80 66 40 15 15 40 50 80 h 0.4 + 0.2h 16 2 + 1.5h 100 80 + 50h max Obrázek 9.1: Grafický význam formulace a řešení úlohy IP (Příklad 9.1): Množina řešení původní úlohy LP je šrafovaná, možná řešení v celočíselných násobcích 15kg jsou značená tečkami a celočíselné optimum je vyznačeno kroužkem. Petr Hliněný, FI MU 3 IA102 "OU": Celočíselná optimalizace 2 Příklad 9.2. Letecká společnost přepravuje cestující z města S do čtyř sousedních měst A,B,C,D. Na dnešní den jsou požadavky na přepravu do města A 110 cestujících, do B 70, do C 58 a do D 62 cestujících. Naše společnost přitom má k dispozici dva typy letadel: Prvního typu má 6 letadel s kapacitou po 33 místech a s fixní cenou letu 120. Druhého typu má 4 letadel s kapacitou po 60 místech a s fixní cenou letu 190. Navrhněte, kolik letadel kterého typu má dnes společnost vypravit do kterého města, aby pokryla požadavky přepravy a zároveň minimalizovala cenu letů. Schematickým obrázkem si zadání zakreslíme takto: s s s ss f A B CD S 110 70 5862 typ let. počet kapacita cena 1 6 33 120 2 4 60 190 Petr Hliněný, FI MU 4 IA102 "OU": Celočíselná optimalizace Řešení: Nechť n1X značí počet letadel prvního typu letících do města X = A, B, C, D. Podmínky celkového počtu letadel jednotlivých typů zformulujeme: n1A + n1B + n1C + n1D 6 n2A + n2B + n2C + n2D 4 Podmínky přepravy cestujících zní: 33n1A + 60n2A 110 33n1B + 60n2B 70 33n1C + 60n2C 58 33n1D + 60n2D 62 Účelová funkce je taktéž zřejmá min 120(n1A + n1B + n1C + n1D) + 190(n2A + n2B + n2C + n2D). Co nám ještě ve formulaci úlohy chybí? ­ neuvedli jsme podmínky celočíselnosti n1A, n1B, n1C, n1D, n2A, n2B, n2C, n2D N . S dodatečnými celočíselnými podmínkami již optimální řešení vyjde n1B = 1, n1D = 2, n2A = 2, n2B = 1, n2C = 1, n2D = 0 , neboli do města A poletí dvě velká letadla, do B malé a velké, do C jedno velké a do D dvě malá. O způsobech obecného řešení úloh IP si řekneme za chvíli. 2 Petr Hliněný, FI MU 5 IA102 "OU": Celočíselná optimalizace 9.2 Formulace úlohy (M)IP Při matematické formulaci úloh celočíselné optimalizace postupujeme podobně jako při úlohách LP. Definice 9.3. Úloha celočíselné (lineární) optimalizace je úlohou najít max c (x, z) za podmínek A (x, z)T b x, z 0 z Z Složky vektoru x jsou reálné proměnné, složky z jsou celočíselné proměnné, oba typy se volně mísí v lineárních nerovnostech vyjařujících podmínky úlohy. Hodnoty složek z obvykle mohou nabývat jen konečně mnoha hodnot. Značení: Takto zadané úloze se obvykle říká smíšená se zkratkou MIP (mixed IP), vyjadřujíce fakt, že ve formulaci se mísí celočíselné i reálné proměnné. Zkratka IP pak označuje úlohu celočíselné optimalizace bez reálných proměnných, což je poměrně častý praktický případ. Petr Hliněný, FI MU 6 IA102 "OU": Celočíselná optimalizace Definice: Úloha MIP je v základním tvaru, pokud je formulována jako max c (x, z) : A (x, z)T b x 0 z {0, 1} Proměnným zi {0, 1} se říká binární proměnné. V praxi se ukazuje, že obvykle mohou celočíselné proměnné nabývat jen konečně mnoha hodnot (například 0, 1, . . ., k) a v jiných případech omezení hodnot celočíselných pro- měnných lze snadno do úlohy doplnit. Proto se nadále budeme zabývat jen úlohami MIP s omezenými celočíselnými proměnnými. Věta 9.4. Každou úlohu MIP s omezenými celočíselnými proměnnými lze převést na základní tvar. Důkaz: Každou celočíselnou proměnnou zi {0, 1, ..., ki} (dle předpokladů omezená) nahradíme l = log2(ki +1) proměnnými z0 i , z1 i , ..., zl-1 i a píšeme zi = z0 i +2z1 i +...+ 2l-1 zl-1 1 (jako v binárním zápise hodnoty zi). Je zřejmé, že každá přípustná hodnota zi jednoznačně odpovídá jisté přípustné posloupnosti hodnot z0 i , z1 i , ..., zl-1 i {0, 1}l , která vyjadřuje číslice binárního zápisu čísla zi. Nakonec případně rovnosti a nerovnosti podmínek úlohy převedeme do základního LP tvaru podle Věty 3.5. 2 Petr Hliněný, FI MU 7 IA102 "OU": Celočíselná optimalizace Zobecněné formulace úloh MIP Lema 9.5. Do základního tvaru úlohy MIP lze převést také úlohy diskrétní optimali- zace, ve kterých se vyskytují diskrétní proměnné t následujících typů: ˇ Proměnné s více diskrétními reálnými hodnotami, tj. proměnná ti {1, 2, . . . , k}, kde 1, . . . , k jsou libovolná reálná čísla. ˇ Semikontinuální proměnné, tj. proměnná ti {0} [, ] nabývající nulové hod- noty nebo hodnoty z intervalu [, ] (neobsahujícího nulu). ˇ Proměnné s více intervalovými hodnotami, tj. proměnná ti [1, 1][2, 2] . . . s hodnotami ze sjednocení několika disjunktních intervalů. Důkaz: Je vidět, že stačí dokázat třetí bod, jelikož první dva jsou jeho speciál- ními případy. Nechť se množina přípustných hodnot pro ti skládá z l intervalů [1, 1], [2, 2], . . . , [l, l]. Použijeme l - 1 binárních proměnných zi2, . . . , zil a do- datečné podmínky zi,2 + . . . + zi,l 1 1 + l j=2 zij(j - 1) ti 1 + l j=2 zij(j - 1) . Proměnné zij nám tak "vyberou", ve kterém z intervalů bude ležet hodnota ti. (Všim- něte si, že první nerovnost zaručuje, že bude vybrán jen jeden interval.) 2 Petr Hliněný, FI MU 8 IA102 "OU": Celočíselná optimalizace 9.3 Řešení MIP relaxací a větvením Nyní si zjednodušeně uvedeme jednu ze základních metod pro řešení úloh MIP. Definice 9.6. LP - relaxací úlohy MIP základního tvaru max c (x, z) : A (x, z)T b x 0 z {0, 1} je úloha LP ve tvaru: max c (x, z) : A (x, z)T b z 1 x, z 0 LP relaxaci základní úlohy MIP vlastně získáme rozšířením přípustného oboru pro proměnné z z hodnot 0, 1 na celý interval [0, 1]. Geometricky si lze představit polyedr všech přípustných řešení LP-relaxace a v něm obsažené "mřížové" body odpovídající přípustným celým hodnotám z {0, 1} , podobně Obrázku 9.1. Podrobněji viz příští lekce. Petr Hliněný, FI MU 9 IA102 "OU": Celočíselná optimalizace Fakt: Množina přípustných řešení úlohy MIP je právě průnikem množiny přípustných řešení její LP-relaxace s mřížovými body {z {0, 1} }. Definice: Hodnotu optimálního řešení LP-relaxace úlohy MIP nazýváme (LP-)relaxační mezí pro původní úlohu MIP. Fakt: Hodnota optimálního řešení úlohy MIP není nikdy lepší než hodnota její LP- relaxační meze. Proto pokud najdeme přípustné řešení úlohy MIP dosahující hodnoty její relaxační meze, máme optimální řešení. Petr Hliněný, FI MU 10 IA102 "OU": Celočíselná optimalizace Algoritmus 9.7. Jednoduchá metoda větvení a mezí s lineární relaxací Mějme danou úlohu MIP v základním tvaru, tj. s binárními proměnnými z. Nechť f je globální proměnná inicializovaná f = -. Procedura branch&bound( U: úloha MIP) 1. L = LP-relaxace U, so = optimální řešení L, ro = relaxační mez. 2. Pokud L nemá přípustné řešení nebo ro f, vrátíme se bez řešení return . 3. Pokud L nemá optimální řešení z důvodu neomezenosti a zároveň v některém přípustném řešení L jsou složky z celé, položíme f = a vrátíme return . 4. Pokud so je přípustné (celoč.) řešení U, položíme f = ro a vrátíme return so . 5. Zvolíme binární proměnnou zi (nedeterministicky) v U a vytvoříme jejím dosaze- ním podúlohy U0 := (U zi = 0) , U1 := (U zi = 1) . Zavoláme rekurzivně s1 = branch&bound( U1) a s2 = branch&bound( U2) zároveň nedeterministicky. Vracíme lepší z obou řešení return max (s1 , s2 ) . Návratová hodnota procedury je optimálním řešením úlohy U s účelovou funkcí f. Pokud f = -, úloha nemá přípustné řešení, pokud f = , úloha nemá optimální řešení z důvodu neomezenosti. Petr Hliněný, FI MU 11 IA102 "OU": Celočíselná optimalizace Tvrzení 9.8. Algoritmus 9.7 vždy (pro jakoukoliv volbu vykonání a pořadí nedetermi- nistických kroků) skončí a správně nalezne optimální řešení. Důkaz: Nechť d je počet binárních proměnných ­ složek z. Pak zřejmě žádná větev rekurze není hlubší než d, neboť každým zanořením se sníží počet binárních proměnných v úloze. Nakonec pokud úloha U neobsahuje binární proměnné (z nemá složky), tak se vždy aplikuje jeden z kroků 2,3,4 před 5 a rekurze se ukončí. Takže algoritmus skončí po O(2d ) iteracích procedury branch&bound. Předpokládejme, že optimální řešení úlohy U má binární složky rovny zo . Pak ve větvi rekurze, která odpovídá volbám hodnot z jako v zo bude toto řešení nalezeno jako přípustná relaxační mez úlohy L . (Úloha U z = zo je již úlohou LP, kterou umíme přesně vyřešit.) Toto přípustné řešení pak jako nejlepší možné (případně jedno z několika stejné hodnoty) bude vráceno procedurou branch&bound. 2 Různými implementačními způsoby volby proměnné zi pro "větvení" se budeme zabývat v příští kapitole. (Algoritmus korektně funguje pro jakoukoliv volbu, ale vhodnou volbou jej lze výrazně urychlit.) Podívejme se blíže na analýzu složitosti v důkaze 9.8 ­ časový odhad O(2d ) je velmi "špatný" již pro poměrně malé hodnoty d. Co však způsobuje tento exponenciální nárust složitosti algoritmu? Je to prohledávání mnoha větví až do úplného konce, do hloubky d. Naši snahou při implementaci algoritmu tedy musí být co nejrychleji "zabít" všechny neperspektivní větve rekurze. V praxi se s největším potenciálem k vyloučení větví rekurze ukazuje krok 2, když relaxační mez vyjde horší než nejlepší dosud nalezené řešení. K aplikaci tohoto kroku však již nějaké přípustné řešení potřebujeme mít nalezené. . . Petr Hliněný, FI MU 12 IA102 "OU": Celočíselná optimalizace 9.4 Jednoduché ukázky řešení IP Příklad 9.9. Letecká společnost má přepravit 141 lidí z města A do B. K dispozici má čtyři letadla: kapacita cena letu posádka L1 90 300 7 L2 60 210 4 L3 50 200 3 L4 33 130 2 Která letadla má zvolit, aby dosáhla nejlevnějšího řešení? Řešení: max - 300z1 - 210z2 - 200z3 - 130z4 U: pro 90z1 + 60z2 + 50z3 + 33z4 zi {0, 1} f = - U LP relaxace max - 300z1 - 210z2 - 200z3 - 130z4 90z1 + 60z2 + 50z3 + 33z4 141 0 zi 1 Řešení. . . Výsledek: poletí L1 a L2. 2 Petr Hliněný, FI MU 13 IA102 "OU": Celočíselná optimalizace