Linear programming-introduction Úvod do principu lineárního programování Ing.J.Skorkovský,CSc. KPH-ESF-MU Czech Republic USE- Oblasti použití •Slitting and Levelling of material (coils, bars, sheets)-Cutting material, trimming,… (dělení materiálu) •Blending - blending, diet, feeding rations for animals, .. (míchání krmných směsi podle receptu veterináře,..) •Transport problems - material flow from stock to the destination and route planning - shortest route (optimalizace dopravních tras) •Assignment of resources with limited capacities - CCR=Capacity Constraint Resource – přiřazení úkolů(zakázek) zdrojům s omezenou kapacitou (v podstatě zdroje typu DRUM) •Sources : Operation Management, Quality and Competitiveness in a global environment, Russel and Taylor (ESF library),… • Dělení materiálu aida_200_ton_press_x64z 18 Řezaní (dělení) ocelových svitků Zakázka 2 Zakázka1 = ořez Zpátky do skladu (RTS) Základní problém optimalizace je, aby se RTS minimalizoval, protože jinak jde o nevyužitý materiál, který má charakter šrotu Zpátky do skladu (RTS) = Return to Stock (RTS) Zakázka 3 Formulation of the model - formulace modelu Výrobek Popis Práce/hod Materiál/ks Výnos/ks Dish (Miska) x1 1 4 40 Mug (Hrnek) x2 2 3 50 Which combination of products will have the greatest return at the limits of maximum production capacity type = 40 hours and the amount of material, that is limited to 120 kg of clay (jíl)? Note: A similar task in terms of flow was solved in the P&Q example based on TOC (only valid for Czech student), where the limitation was in resource B and with a maximum capacity of 2400 minutes. Při které kombinaci vyráběných produktů (miska a hrnek) budeme mít největší výnos když máme možnost pracovat maximálně 40 hodin (limit kapacity) a nemůžeme využít více jak 120 kg jílu (hrnčířské hlíny) – omezení materiálové CZ Formulace modelu Výrobek Popis Práce/hod Materiál/ks Výnos/ks Miska x1 1 4 40 Hrnek x2 2 3 50 Při které kombinaci vyráběných produktů (miska a hrnek) budeme mít největší výnos když máme možnost pracovat maximálně 40 hodin (limit kapacity) a nemůžeme využít více jak 120 kg jílu (hrnčířské hlíny) – omezení materiálové Poznámka : podobný úkol je řešený v již odpřednášeném příkladu, ve kterém se zjišťovala Optimální kombinace dvou produktů (P&Q) s použitím podle TOC principů, kde limitní kapacita každého strojního centra bylo 2400 minut. Strojní centru, které bylo úzkým místem (Drum nebo jinak také CCR ) bylo centrum B TOC P and Q class problem prezentace CCR= Capacity Constrained Resource Basic structures and used terminology Základní rovnice a terminologie •We minimize our target function Z (cílová funkce) in the form of: • Z = c1*x1+c2*x2+…..+cn*xn with respect to the matrix of restrictive conditions: • (in our case c1=40 and c2=50) – v našem příkladu c1=40 a c2=50 • •A11*x1 + A12*x2+ …+ A1n*xn (<>=) B1 •A21*x1 + A22*x2+ …+ A2n*xn (<>=) B2 • •Am1*x1 + Am2*x2+ …+ Amn*xn (<>=) Bm • •It is classical system of linear equations je Ax=B (restrictive conditions-omezení ) •The solving of such a linear equation system, e.g. By use of GAUSS-JORDAN algorithm is not required with the help of Excel Solver (Excel Řešitel) •xij : decision variable= level of operation activity specified by this variable •Bi : restrictive conditions (podmínky omezení) •allowed deviations from the norm (in time and material) •cj : coefficient of the target function (v našem případě c1=40 a c2=50 •Aij : restrictive coefficients : work and material for one unit (pcs) of the product • • Systém lineárních rovnic kde prvky vektoru B (B1,B2,..) reprezentují ohraničení 40 hodin (B1) a 120 kilogramů (B2) Example I (introduction to the problem – practical demonstration ) Target function: Z= 40*x1+50*x2, which we must maximize (maximalizovat výnos) Maximal production capacity = 40 hours and Maximal quantity of material =120 kg ( jsou to dva prvky matice B (40,120) – omezení) Specifications of task restrictions by use of 2x2 matrix ( 2 x 2 matice) 1*x1 + 2*x2 =40 (work- no more than 40 hours) (ne více než 40 hod) 4*x1 + 3*x2 =120 (materiál=kg jílů )->x1=(40-2x2)+3x2=120…. Manual solving : -> x1=24 a x2=8 and after substitution od variables (vyřešení 2 lineárních rovnic o 2 neznámých) in target function we will get Z=40*24+50*8=1360 (maximální výnos) (optimal Return meets the point B – see next slide) Z = c1*x1+c2*x2+…..+cn*xn (classical equation from) Z = co největší výnos) Výrobek Popis Práce/hod Materiál/ks Výnos/ks Dish (miska) x1 1 4 40 Mug (hrnek) x2 2 3 50 Graphical solution- grafické zobrazení Use of Solver (Czech EXCEL) Excel Setup Solver Complements Supplement Solver Solver Use o solver (see actual Excel formulas on one of the the next slides) Dish Mug Total Capacity Variables (x1, x2) 0 0 Return 40 50 0 Material 4 3 0 120 Work 1 2 0 40 x1=Dish , x2=Mug, max 40 hod (B1), max 120 kg (B2) Target function Z = x1*c1 + x2*c2 = 40*x1+50*x2 Z 4 * x1 + 3 *x2 =120 - capacity restrictions= max quantity of material =B1 1 * x1 + 2 *x2 = 40 -capacity restrictions by max work capacity=B2 x1 x2 Assignment Assignment entered in table Product Description Work /hour Material/pcs Return/pcs Dish x1 1 4 40 Mug x2 2 3 50 Solver start Použití Řešitele (Only for Czech course - not for MPH_AOPR ) Z = x1*c1 + x2*c2 = 40*x1+50*x2 E5=C4*C5+ D4*D5 (cílová funkce ) E7=C7*C4+D7*D4=4*x1+3*x2=120 E8=C8*C4+D8*D4=x1+2*x2=40 Use of solver (ENG) Z = x1*c1 + x2*c2 = 40*x1+30*x2 F10=D10*D6+E10*E6=4*x1+3*x2=120 F11=D11*D6+E11*D6=x1+2*x2=40 Solve it Target Variables Restrictions Využití Řešitele (use of Solver) Use of Solver (English) New Excel List Změna úlohy- jiné výnosy jiná omezení typu práce na dvou strojích a jejich kapacitní omezení Pro kurzy BPH-PIS1, MPH-RIOP a MKH-RIOP – domácí cvičení OK ?