Matematické programování 13. března 2022 1 Linerární programování 2 Celočíselné programování Matematické programování Řada rozvrhovacích problémů může být formulována jako matematické programy Lineární programování, nelineární programování, celočíselné programování Předměty PřF:M0160 Optimalizace ESF:BKM_OPRO Optimalizace a rozhodování Hana Rudová, FI MU: Matematické programování 2 13. března 2022 Lineární programování Lineární program (LP) Minimalizace c1x1 + c2x2 + · · · + cnxn za předpokladu a11x1 + a12x2 + · · · + a1nxn ≥ b1 a21x1 + a22x2 + · · · + a2nxn ≥ b2 · · · am1x1 + am2x2 + · · · + amnxn ≥ bm xj ≥ 0 pro j = 1, . . . , n xj ∈ R pro j = 1, . . . , n V maticovém zápisu: minimalizace c x za předpokladu Ax ≥ b x ≥ 0 Hana Rudová, FI MU: Matematické programování 3 13. března 2022 Lineární programování: příklad Výrobce vyrábí 3 výrobky A, B, C, na které spotřebuje materiál M a pracovní dobu P Maximalizujeme denní "Zisk"za předpokladu, že platí: zisk z 1 kusu A = 500 Kč, spotřebujeme 4M a 2P. zisk z 1 kusu B = 800 Kč, spotřebujeme 1M a 5P. zisk z 1 kusu C = 300 Kč, spotřebujeme 2M a 1P. přitom platí denní omezení materiálu M≤30 kusů a pracovních hodin P≤48 hodin (např. 6 lidí pracujících 8 hodin denně) Jak lze použít obecný LP vzorec? max(Zisk) = 500*A + 800*B + 300*C (c1 = 500, x1 = A,...) 4*A + 1*B + 2*C ≤ 30 (omezení materiálu) 2*A + 5*B + 1*C ≤ 48 (omezení prac. hodin) Jak bude vypadat výsledek? V jakých proměnných budeme mít uloženou odpověď na naši otázku? Co budou vyjadřovat? Bude to použitelné v praxi? Max vs. min není problém, neboť platí: max f (x) = −min(−f (x)) pro x ∈ Rn Hana Rudová, FI MU: Matematické programování 4 13. března 2022 Lineární programování: metody řešení Pro malé 2D, 3D problémy si často vystačíme s grafickým řešením cíl je rovnice s parametrem = vrstevnice v ploše omezení jsou poloroviny oblast řešení je průnik polorovin (polyedr, tj. mnohostěn) řešení je průnik rovnice s parametrem a vzniklého polyedru Simplexová metoda efektivní nalezení řešení většinou polynomiální čas použití v praxi pro řešení rozsáhlých problémů Elipsoidová metoda Metoda vnitřních bodů Hana Rudová, FI MU: Matematické programování 5 13. března 2022 Celočíselné programování Celočíselné programování (integer programming IP) lineární programování + všechny proměnné celočíselné Mixed-integer programming (MIP) použity celočíselné i reálné obory hodnot proměnných Mnohem obtížnější než lineární programování Pro rozvrhování mnohem užitečnější Hana Rudová, FI MU: Matematické programování 6 13. března 2022 Celočíselné programování a metody řešení Pracuje se s LP relaxací celočíselného programu, tj. z celočíselného programu jsou odstraněna omezení požadující řešení z oboru celých čísel a řešíme lineární programy a řešíme lineární programy Metoda řezné roviny (cutting plane) generována přídavná lineární omezení (řezné roviny), která musí být splněna v celočíselném řešení přídavná omezení zužují množinu přípustných řešení při zachování celočíselných řešení řešení LP relaxace celočíselného programu s přídavnými omezeními pokud nenalezeno řešení celočíselné, přidáváme dalsí řezné roviny a opakujeme postup Metoda větví a mezí (branch and bound) větvení na rozhodovacích proměnných (xj = r v LP řešení pak přidáme xj ≤ r , xj ≥ r ) lineární programy s přidanými omezeními poskytují hranice (meze) Hybridní metody kombinace různých metod např. kombinace metody větví a mezí a řezných rovin (branch and cut)Hana Rudová, FI MU: Matematické programování 7 13. března 2022 Ukázka problému: rozvrhování směn Směna: množina period, kdy zaměstnanec pracuje často je směna chápána jako množina po sobě jdoucích period př. denní směna 6:00-18:00, noční směna 18:00-6:00 Problém rozvrhování směn cyklus je dán předem např. 1 den je cyklus, časová jednotka (perioda) je hodina je dáno několik vzorků směn s odlišnou cenou cíl je minimalizovat celkovou cenu Problém si popíšeme jako matematický celočíselný program minimalizace n j=1 cj xj za předpokladu: n j=1 aij xj ≥ bi ∀i : 1 ≤ i ≤ m xj ≥ 0 ∀j : 1 ≤ j ≤ n xj ∈ Z ∀j : 1 ≤ j ≤ n Hana Rudová, FI MU: Matematické programování 8 13. března 2022 Formulace problému a řešení m period (hodin) př. od 10:00 do 21:00 V periodě i, i = 1, . . . , m je potřeba bi zaměstnanců př. 10:00: 3, 11:00: 4, 12:00 6, ... n vzorků směn př. 10:00 – 18:00, 13:00 – 21:00, 18:00 – 21:00, ... Každý zaměstnanec přiřazen právě jednomu vzorku Vzorek směny j je vektor (a1j , a2j , . . . , amj ) aij = 1: i je pracovní perioda aij = 0: jinak př. směna 18:00 – 21:00 odpovídá (0,0,0,0,0,0,0,0,1,1,1) pro 10:00 – 21:00 Cena přiřazení zaměstnance na směnu j: cj xj : proměnná reprezentující počet zaměstnanců přiřazených ke směně j Cíl: minimalizace celkové ceny přiřazených zaměstnanců Problém je NP-těžký, nicméně A má speciální tvar, kde směna je dána jako kontinuální posloupnost 1 platí: řešení tohoto lineárního programu je vždy celočíselné Hana Rudová, FI MU: Matematické programování 9 13. března 2022 Příklad rozvrhování směn v obchodě Obchod otevřen od 10:00 do 21:00 5 vzorků (typů) směny Vzorek Doba Hodin Cena 1 10-18 8 50 2 13-21 8 60 3 12-18 6 30 4 10-13 3 15 5 18-21 3 16 Požadavky na počet zaměstnanců v obchodě Hodina 10 11 12 13 14 15 16 17 18 19 20 Počet zaměstnanců 3 4 6 4 7 8 7 6 4 7 8 Lineární relaxace c = (50, 60, 30, 15, 16) A =                   1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1                   b =                   3 4 6 4 7 8 7 6 4 7 8                  Řešení (x1, x2, x3, x4, x5) = (0, 0, 8, 4, 8) Hana Rudová, FI MU: Matematické programování 10 13. března 2022 Omezující podmínky 13. března 2022 3 Problém splňování podmínek Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk } konečná množina hodnot (doména) D = D1 ∪ . . . ∪ Dk Omezení c na Y je podmnožina D1 × . . . × Dk omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: proměnné: A,B domény: {0,1} pro A {1,2} pro B omezení: A=B nebo (A,B) ∈ {(0,1),(0,2),(1,2)} Omezení c definováno na y1, . . . yk je splněno, pokud pro d1 ∈ D1, . . . dk ∈ Dk platí (d1, . . . dk) ∈ c příklad (pokračování): omezení splněno pro (0, 1), (0, 2), (1, 2), není splněno pro (1, 1) Hana Rudová, FI MU: Omezující podmínky 12 13. března 2022 Problém splňování podmínek (CSP) Dána konečná množina proměnných V = {v1, . . . , vn} konečná množina hodnot (doména) D = D1 ∪ . . . ∪ Dn konečná množina omezení C = {c1, . . . , cm} omezení je definováno na podmnožině V Problém splňování podmínek je trojice (V , D, C) (constraint satisfaction problem CSP) Příklad: proměnné: A,B,C domény: {0,1} pro A {1} pro B {0,1,2} pro C omezení: A=B, B=C Řešení CSP přiřazení hodnot všem proměnným, které splňuje všechna omezení (d1, . . . , dn) ∈ D1 × . . . × Dn je řešení (V , D, C) pro každé ci ∈ C na vi1 , . . . vik platí (di1 , . . . dik ) ∈ ci Hana Rudová, FI MU: Omezující podmínky 13 13. března 2022 Filtrace domén Příklad: Da = {1, 2}, Db = {1, 2, 3} a < b ⇒ hodnota 1 může být z Db bezpečně vyřazena Podmínky se používají aktivně pro odstranění nekonzistencí z problému nekonzistence = hodnota, která nemůže být součástí žádného řešení (nesplňuje nějakou podmínku) Tato tzv. filtrace domén je realizována procedurou REVISE, kterou má každá podmínka Hana Rudová, FI MU: Omezující podmínky 14 13. března 2022 Hranová konzistence (arc consistency AC) Říkáme, že podmínka je hranově konzistentní, pokud pro každou hodnotu každé její proměnné existuje kombinace hodnot pro další proměnné v podmínce tak, že je podmínka splněna Říkáme, že hodnota je podporována/má podporu. REVISE procedura pro hranovou konzistenci odstraní z domén proměnných všechny hodnoty, které nemají podporu Příklad: A=B+C je hranově konzistentní pro B,C ∈ {1,2}, A ∈ {2,3,4} (hodnota 3 proměnné A má např. podporu (3,1,2) pro (A,B,C)) A=B je hranově konzistentní pro A ∈ {0,1}, B ∈ {1,2,3} A=B není hranově konzistentní pro A ∈ {1,2,3}, B ∈ {1,2} (hodnota 3 proměnné A není podporována) CSP je hranově konzistentní, pokud jsou všechny podmínky hranově konzistentní. Hana Rudová, FI MU: Omezující podmínky 15 13. března 2022 Zajištění hranové konzistence Jak zařídit hranovou konzistenci v CSP? Každá podmínka musí být zrevidována Příklad: X in 1..6, Y in 1..6, Z in 1..6, X