Lineární modely - 10. přednáška Lineární programování Ondřej Klíma 25. 4. 2013 10. přednáška Úlohy lineárního programování Osnova přednášky • Simplexy, rovnoběžnostěny a další konvexní množiny • Úloha lineárního programování • Dvoudimenzionální příklad • Simplexový algoritmus 10. přednáška Úlohy lineárního programování Simplexy Definice Nechť A0,...,Ai<\ek + '\ bodů afinního prostoru A v obecné poloze. Pak -rozměrný simplex A = A(A0,Ak) generovaný těmito body je definován jako množina všech afinních kombinací bodů A, s pouze nezápornými koeficienty, tzn. k A = {t0A0 + tiA,+--- + tkAk | ř,-G [0,1],^ř( = 1}. Jednorozměrný simplex je úsečka, dvourozměrný trojúhelník. Nestačí nám to. Chceme čtyřúhelníky a složitější prostorová tělesa. 10. přednáška Úlohy lineárního programování Rovnoběžnostěn Definice Nechť Ui,...,Uk jsou libovolné vektory v zaměření Rn, A&A, je libovolný bod. Rovnoběžnostěn Vk(A; u-\,..., Uk) c An je množina Vk{A;Ui,...,uk) = = {A + c-, ui H-----h ckuk | 0 < q < 1, / = 1,..., k}. Jsou-li vektory u^,...,Uk nezávislé, hovoříme o /c-rozměrném rovnoběžnostěnu Vk(A; u-\,...,Uk) Q An- Tj. rovnoběžník v M3 je rovnoběžnostěn (dimenze 2). 10. přednáška Úlohy lineárního programování Konvexní množiny Definice Podmnožina M afinního prostom se nazývá konvexní, jestliže s každými svými dvěma body A, B obsahuje i celou úsečku A(A,B). • Každá konvexní množina obsahuje s každými k + 1 body v obecné poloze i celý jimi definovaný simplex. • Konvexními množinami jsou např.: • prázdná podmnožina, • afinní podprostory, • úsečky, polopřímky p = {P + t ■ v; t > 0}, • obecněji /(-rozměrné poloprostory a = {P + u ■ Vi + ■ ■ ■ + tk ■ vk | ři,..., tk e R, tk > 0}, • úhly v dvojrozměrných podprostorech /3 = {P + ri ■ ví + fc ■ V5> | ri > 0, fc > 0}, • další: nekonečný jehlan, kužel, koule, mnohostěny. 10. přednáška Úlohy lineárního programování Konvexní obal Přímo z definice také plyne, že průnik libovolného systému konvexních množin je opět konvexní množina. Definice Průnik všech konvexních množin obsahujících danou množinu M nazýváme konvexní obal K.(M) množiny M. Věta Konvexní obal libovolné podmnožiny M c A je s K(M) = {^1 + • • • + tsAs | s G N, ti = 1, ^ > 0, A G M} Konvexní obaly konečných množin bodů se nazývají konvexní mnohostěny. Jsou-li definující body A0,... ,Ak konvexního mnohostěnu v obecné poloze, dostáváme právě /c-rozměrný simplex. 10. přednáška Úlohy lineárního programování Konvexní obal - příklad Příklad Rozhodněte, zda leží bod X = [2,1,0] uvnitř konvexního obalu bodů [0,2,1], [1,0,1], [3,-2,-1], [-1,0,1]._ Sestavíme nehomogenní lin. soustavu, pro koeficienty t-\, t2, ř3, ř4, afinní kombinace daných bodů, která dává bod X (jsou určeny jednoznačně, pokud dané body neleží v rovině). /O 1 3 -1^ í2\ 2 0 2 0 1 1 1 -1 1 h 0 V 1 1 1 J {t4J w Poslední rovnice udává, že jde o afinní kombinaci. Řešením soustavy dostáváme (ři, Í2, Í3, U) — (1,0,1 /2, -1 /2), nejedná se tedy o konvexní kombinaci. Bod X neleží v konvexním obalu. 10. přednáška Úlohy lineárního programování Lineární optimalizační úlohy Příklad (Modifikace příkladu 3.1 ze skript) Firma vyrábí šroubky a matice. • Šroubky i matice jsou lisovány - vylisování krabičky šroubků trvá 1 minutu, krabička matic je lisována 2 minuty. • Šroubky i matice balí do krabiček - krabička šroubků se balí 1 minutu, krabička matic 4 minuty. 9 Firma má k dispozici 2 hodiny času pro lisování a 3 hodiny času pro balení výrobků. • Vzhledem k poptávce chce firma vyrobit maximálně o 30 krabiček matic více než krabiček šroubků. 9 Firma nemůže vyrobit více než 110 krabiček šroubků. 9 Zisk z jedné krabičky je 20 Kč (šroubky) a 100 Kč (matice). Kolik krabiček šroubků a matic má firma vyrobit, chce-li dosáhnout maximálního zisku? 10. přednáška Úlohy lineárního programování Matematická formulace příkladu • Buď x-i počet krabiček šroubků, x2 počet krabiček matic. • Ze zadání dostáváme omezující podmínky: x-i + 2x2 < 120 + 4x2 < 180 x2 < 30 + Xi Xt < 110 • Účelová funkce (funkce udávající zisk při daném počtu vyrobených šroubků a matic) je 20x-\ + 100x2. • Předchozí soustava nerovnic zadává v M2 určitou oblast (implicitně x-| > 0 a x2 > 0) a optimalizace zisku znamená najít v této oblasti bod (případně body) s nejvyšší hodnotou účelová funkce. Tj. lze řešit „geometricky". • Optimální řešení: průsečík přímek p : x-i + 4x2 = 180 a q : x2 = 30 + Xt . Tj. bod = 12, x2 = 42. 10. přednáška Úlohy lineárního programování Formulace obecné úlohy lineárního programování Definice Obecnou úlohou lineárního programování rozumíme max{c • xT | A ■ xT < bT} kde c = (c-i,..., cm) je vektor účelové funkce, x = (x-\,..., xm) vektor promněnných, A e Matktm(R) matice soustavy lineárních omezení a b eRk vektor (omezení). V našem příkladě: m = 2, c = (20,100)a A ■ xT < bT je tvaru / 1 2^ /120\ 1 4 180 -1 1 30 1 0 110 -1 0 0 V o -\) ^ o ) 10. přednáška Úlohy lineárního programování Manipulace s úlohami lineárního programování • Minimalizaci nemá smysl formulovat zvlášť, neboť min{c • xT | ...} je totéž co max{-c • xT \ ...}. • Lze uvažovat i rovnice a • xT = p, které jsou ekvivalentní s dvojicí nerovnic a • xT < p, -a • xT < -p. • Naopak libovolnou nerovnici lze zavedením nové proměnné převést na rovnici s dodatečnou podmínkou {aA,..., am) ■ (xt ,..., xm)T < b0 {aA,... am, 1) • (xt ,..., xm, y)T = b0, y > 0. • Požadavek nezápornosti řešení lze rozšířit na všechny proměnné, neboť místo proměnné x lze vzít x = x' - x", kde x1 x" > 0. Definice Standardní úlohou lineárního programování rozumíme max{c • xT | A ■ xT = bT, x > 0} . 10. přednáška Úlohy lineárního programování Příklad ve tvaru standardní úlohy Máme 4 nerovnosti, takže potřebujeme 4 nové proměnné: y^, /2, /3, /4- Pak c = (20,100,0,0,0,0) a /4 • xT = bT je tvaru / 1 2 1 0 0 0\ x2 /120\ 1 4 0 1 0 0 y, 180 -1 10 0 10/2 = 30 V 1 0 0 0 0 1/ y3 \110/ \yj Tabulkový zápis standardní úlohy: -20 -100 0 0 0 0 0 1 2 1 0 0 0 120 1 4 0 1 0 0 180 -1 1 0 0 1 0 30 1 0 0 0 0 1 110 10. přednáška Úlohy lineárního programování Existence řešení úlohy lineárního programování Všimněme si, že body splňující systém omezení tvoří konvexní množinu. Jde totiž o průnik poloprostorů. Pro každou úlohu lineárního programování nastane právě jedna z následujících tří možností: • Optimální řešení neexistuje, protože neexistuje žádné přípustné řešení. • Optimální řešení neexistuje z důvodu neohraničenosti. (Úloha má ale přípustná řešení). • Existují optimální řešení (může jich být více). My se zpravidla budeme potýkat se situacemi třetího typu, protože jednak bývají přirozeně „omezeny zdroje" a navíc je k dispozici „triviální" (nulové) přípustné řešení. 10. přednáška Úlohy lineárního programování Příklady z praxe na úlohy lineárního programování V různých ekonomických modelech chceme minimalizovat náklady nebo maximalizovat zisk při omezeních. • Úlohy finančního plánování, související s optimalizací portfolia. Určujeme přitom objemy investic do jednotlivých investičních variant s cílem držet se daných omezení na rizika a optimalizovat přitom zisk, resp. při očekávaném objemu minimalizovat rizika. • Marketingové aplikace, např. alokace nákladů na reklamy v různých médiích nebo umísťování reklam do časových termínů. Omezujícími podmínkami bude disponibilní rozpočet, rozložení cílových skupin apod. • Výživové problémy, tj. návrh dávek různých komponent výživy s daným složením a omezujícími požadavky na celkové objemy výživových látek. • Personální Úlohy, kdy jsou pracovníci s různými kvalifikacemi a dalšími předpoklady rozdělováni do směn. • Distribuce zbOŽI ze skladů je třeba distribuovat zboží mezi zákazníky, při minimalizaci nákladů na dopravu. 10. přednáška Úlohy lineárního programování Simplexový algoritmus pro standardní úlohu • Idea - postupujeme z vrcholu do vrcholu po hranách a vylepšujeme hodnotu účelové funkce. • Řešíme zjednodušenou úlohu, kde Ax < b, s b > 0, tudíž máme „bezpracné" přípustné nulové řešení. • Obecně se musí startovní řešení najít, resp. ukázat, že neexistuje. My nebudeme dělat. 10. přednáška Úlohy lineárního programování Simplexový algoritmus - tabulkový zápis Tabulkový zápis standardní úlohy: -20 -100 0 0 0 0 0 1 2 1 0 0 0 120 1 4 0 1 0 0 180 -1 1 0 0 1 0 30 1 0 0 0 0 1 110 • Sloupce s pivotem - v pravém sloupci v řádku s pivotem se nachází aktuální hodnota příslušné proměnné. Zde = 120, y2 = 180, y3 = 30, y4 = 110. • Sloupce bez pivota - příslušná proměnná je nulová. Zde x-i = 0, x2 = 0. • Aktuální hodnota účelové funkce - pravý horní roh. Zde 0. 10. přednáška Úlohy lineárního programování Simplexový algoritmus - jeden krok výpočtu -Cl • • -Cn 0 au • ■ &\m Ol 3-km O Vybereme první sloupec zleva, který má v záhlaví záporný prvek. Nechť je to y-tý sloupec. O V y-tém sloupci vybereme z kladných čísel a,y to, pro které je poměr ^ minimální. O Eliminujeme celý y-tý sloupec této tabulky s pivotem a-,j (tzn. elementárními řádkovými transformacemi dané tabulky dosáhneme toho, že ve vybraném sloupci bude číslo 1 na místě a,y a jinak samé nuly). Poznamenejme, že pravý sloupec zůstává během výpočtu nezáporný. 10. přednáška Úlohy lineárního programování Simplexový algoritmus - příklad - první krok -20 -100 0 0 0 0 0 1 2 1 0 0 0 120 1 4 0 1 0 0 180 -1 1 0 0 1 0 30 1 0 0 0 0 1 110 0 - 100 0 0 0 20 2200 0 2 1 0 0 -1 10 0 4 0 1 0 -1 70 0 1 0 0 1 1 140 1 0 0 0 0 1 110 X1 = 110,x2 = 0,/! = 10, y2 = 70,y3 = 140,y4 = 0 10. přednáška Úlohy lineárního programování Simplexový algoritmus - příklad - druhý krok 0 -100 0 0 0 20 2200 0 2 1 0 0 -1 10 0 4 0 1 0 -1 70 0 1 0 0 1 1 140 1 0 0 0 0 1 110 0 0 50 0 0 -30 2700 0 1 1 2 0 0 1 2 5 0 0 -2 1 0 1 50 0 0 1 2 0 1 3 2 135 1 0 0 0 0 1 110 X1 = 110,x2 = 5,/! =0,y2 = 50,y3 = 135,y4 = 0 10. přednáška Úlohy lineárního programování Simplexový algoritmus - příklad - třetí krok 0 0 50 0 0 -30 2700 0 1 \ o 0 1 2 5 0 0 -2 1 0 1 50 0 0 -\ o 1 3 2 135 1 0 0 0 0 1 110 0 0 -10 30 0 0 4200 0 1 1 2 1 2 0 0 30 0 0 -2 1 0 1 50 0 0 5 2 3 2 1 0 60 1 0 2 -1 0 0 60 X1 = 60,x2 =30,/! =0,/2 = 0,/3 = 110,/4 = 50 10. přednáška Úlohy lineárního programování Simplexový algoritmus - příklad - čtvrtý krok 0 0 -10 30 0 0 4200 0 1 1 2 1 2 0 0 30 0 0 -2 1 0 1 50 0 0 5 2 3 2 1 0 60 1 0 2 -1 0 0 60 0 0 0 24 4 0 4440 0 1 0 1 5 1 5 0 42 0 0 0 - 1 5 4 5 1 98 0 0 1 - 3 5 2 5 0 24 1 0 0 1 5 4 "5 0 12 xA = 12,x2 =42,yi =24,y2 = 0,y3 = 0,y4 = 98 10. přednáška Úlohy lineárního programování Simplexový algoritmus - konec Konec výpočtu: • Celé záhlaví je nezáporné, máme optimální řešení. • Pokud během výpočtu narazíme na sloupec se záporným číslem v záhlaví, který je celý nekladný, pak optimální řešení neexistuje z důvodu neohraničenosti. V našem příkladě máme optimální řešení x-i = 12, x2 = 42 s optimální hodnotou účelové funkce 4.440. 10. přednáška Úlohy lineárního programování Požadavky • Konvexní obal - zda zadaný bod je vnitřní bod. • Geometrické řešení úlohy lineárního programování v rovině. • Algoritmické řešení zjednodušené úlohy lineárního programování. (Jednoduché zadání, kde kromě doplňkových proměnných jsou maximálně 2 původní proměnné.) 10. přednáška Úlohy lineárního programování