Lineární programování-úvod a příklady s využitím Řešitele Ing.J.Skorkovský,CSc. Použití •Dělení profilů (cutting, trim loss) •Mixování směsí (blending,diet) •Dopravní problémy (tok materiálu do bodu určení a plánování trasy- shortest route) •Přiřazování zdrojů limitovaných kapacitami (assignment) • •Zdroj : Operation Management, Quality and Competitiveness in a global environment, Russel and Taylor (v knihovně) • Zadání-formulace modelu Výrobek Označení Práce /hod Materiál/ks Výnos/ks Miska x1 1 4 40 Hrnek x2 2 3 50 Jaká kombinace výrobků bude mít největší výnos při ohraničení typu maximální kapacity výroby v čase=40 hodin a množství materiálu, které je omezeno 120 kg hlíny ? Poznámka : obdobná úloha z pohledu průtoku byla řešena v ukázce P&Q , kde bylo omezení ve zdroji B a v maximální kapacitě času 2400 minut) Základní struktura a terminologie •Minimalizujeme námi vytvořenou cílovou funkci ve tvaru : • • Z = c1*x1+c2*x2+…..+cn*xn vzhledem k matici omezujících podmínek : • •A11*x1 + A12*x2+ …+ A1n*xn (<>=) B1 •A22*x1 + A22*x2+ …+ A2n*xn (<>=) B2 • •Am1*x1 + Am2*x2+ …+ Amn*xn (<>=) B2 • •V klasickém výše uvedená soustava lineárních rovnic je Ax=B •Řešení soustavy lineárních rovnic např. algoritmem GAUSS-JORDAN není s pomocí doplňku Excelu typu Řešitel (Solver) nutné !!! •xij : proměnná, které řešíme (decision variables= úroveň aktivity operace, kterou proměnná specifikuje) •Bi : omezující podmínky, povolené odchylky od normy (omezení v čase a materiálu) •cj : koeficienty účelové (cílové) funkce (v našem případě konkrétně výnosy) •Aij : koeficienty omezení (práce a materiál na jednotku výrobku) • • Příklad I (úvod do problému-praktická ukázka) Výrobek Označení Práce /hod Materiál/ks Výnos/ks Miska x1 1 4 40 Hrnek x2 2 3 50 Cílová funkce : Z= 40*x1+50*x2, kterou musíme maximalizovat Maximální kapacita výroby = 40 hodin a Maximální množství materiálu =120 kg Specifikace omezení úlohy s pomocí matice 2x2 : 1*x1 + 2*x2 =40 (práce) 4*x1 + 3*x2 =120 (materiál) Vyřešení rovnic (ručně) -> x1=24 a x2=8 a po dosazení do cílové funkce dostaneme Z=40*24+50*8=1360 (optimální náklad odpovídající bodu B – viz další obrázek) Z = c1*x1+c2*x2+…..+cn*xn Grafické řešení Využití Řešitele Nastavení Excelu Využití Řešitele Miska Hrnek Total Kapacita Proměnné (x1, x2) 0 0 Výnos 40 50 0 Materiál 4 3 0 120 Práce 1 2 0 40 x1=Miska , x2=Hrnek, max 40 hod (B1), max 120 kg (B2) Cílová funkce Z = x1*c1 + x2*c2 = 40*x1+50*x2 Z 4 * x1 + 3 *x2 =120 (omezení max množství materiálu)=B1 1 * x1 + 2 *x2 = 40 (omezení max kapacitou práce)=B2 x1 x2 Výrobek Označení Práce /hod Materiál/ks Výnos/ks Miska x1 1 4 40 Hrnek x2 2 3 50 Zadání Zadání formou tabulky Využití Řešitele Z = x1*c1 + x2*c2 = 40*x1+30*x2 E7=C7*C4+D7*D4=4*x1+3*x2=120 E8=C8*C4+D8*D4=x1+2*x2=40 Využití Řešitele Změna úlohy- jiné výnosy jiná omezení typu práce na dvou strojích a jejich kapacitní omezení OK ?