2. cvičenie – formulácia a výsledky - LINGO 1. Úloha o optimálnom výrobnom pláne (optimálne využitie výrobných faktorov) a) maximalizácia zisku – NECELOČÍSELNE MODEL: !zadani ucelove fce; [UCELOVA_FCE] max = 120*x1+50*x2+150*x3+100*x4; !zadani omezeni; [DOSKY_I] 5*x1+x2+9*x3+12*x4<=1500; [DOSKY_II] 2*x1+3*x2+4*x3+x4<=1000; [PRAC_HOD] 3*x1+2*x2+5*x3+10*x4<=800; END Global optimal solution found. Objective value: Infeasibilities: Total solver iterations:
32000.00 0.000000 4
Variable X1 X2 X3 X4 Row UCELOVA_FCE DOSKY_I DOSKY_II PRAC_HOD
Value 266.6667 0.000000 0.000000 0.000000
Reduced Cost 0.000000 30.00000 50.00000 300.0000
Slack or Surplus 32000.00 166.6667 466.6667 0.000000
Interpretace: Zápis optimálního řešení: x* = (x1, x2, x3, x4, x5, x6, x7) = (266,67, 0, 0, 0, 166,67, 466,67, 0), z* = 32000 u* = (u1, u2, u3, u4, u5, u6, u7) = (0, 30, 50, 300, 0, 0, 40) Objective value Maximální zisk dielne v optimálnom výrobnom programe bude 32 000 Kč. Value = hodnota strukturních proměnných: 1
Dual Price 1.000000 0.000000 0.000000 40.00000
Maximálního zisku dielňa dosáhne optimálním výrobním programem, který se skládá z 266,67 kusov stolov, stoličky, písacie stoly a knižnice se vyrábět nebudou. Reduced cost (Redukovaná cena) – o kolik se musí změnit cenový koeficient v účelové funkci, aby se daný výrobek začal vyrábět respektive jaké budou náklady obětované příležitosti, pokud výrobek budeme vyrábět. u maximalizace: napr. jednotkový zisk u stoličky (x2) by musel zvýšiť aspoň o 30 Kč, aby bola zaradená do výrobného program (aby sa stoličky vyrábali). Je možné vyzkoušet na výše uvedeném příkladu, když změním v zápisu v LINGO v účelové funkci 50*x2 na 80*x2, tak sa optimální řešení změní z (266,67, 0, 0, 0, 166,67, 466,67, 0) na (80, 280, 0, 0, 820, 0, 0). u minimalizace: např. u směšovacího problému (vyrábím směs z krmiva K1 a K2 a v optimálním řešení jsou strukturní proměnné rovny K1=0 a K2 = 55 a redukované ceny K1 = 7 a K2=0) by se museli jednotkové náklady snížit u daného výrobku (krmiva K1) o 7 Kč, aby krmivo K1 bylo součástí směsi (“vyšla kladná hodnota ve slupečku Value”). Slack or Surplus – hodnota účelové funkce a přídatné proměnné (řádky odpovídají řádkům v definici modelu) první řádek je dosažená hodnota účelové funkce, druhý řádek značí, jaký je rozdíl mezi pravou a levou stranou prvního omezení – tj. rovnice: 5*x1+x2+9*x3+12*x4<=1500 – tj. o kolik je 5*x1+x2+9*x3+12*x4 menší než 1500 (při omezení typu >= o kolik je levá strana větší než pravá), je-li hodnota přídatné proměnné nulová, značí to, že omezení je v optimálním řešení splněné jako rovnost, pokud je některá z přídatných proměnných kladná, pak to znamená, že např. zásoba suroviny není spotřebována – tj. existují nevyužité zdroje – pokud tedy snížíme zásobu konkrétní suroviny o hodnotu přídatné proměnné, pak se optimální řešení nezmění, pokud bychom snížili zásobu suroviny, jejíž přídatná proměnná je nulová, snížení by se projevilo na optimálním řešení. Dual Price – duální (stínové) ceny – ukazují o kolik vzroste (resp. klesne při minimalizační) hodnota účelové funkce, pokud by se nám zvýšila hodnota pravé strany omezení o jednotku tzn. oceňuje nám vstupy. hodnota v prvním řádku (1) se neinterpretuje – vztahuje se k účelové funkci
u maximalizace a omezení je typu ≤: duální cena je vždy ≥ 0 (pozitivní duální cena zlepšuje hodnotu účelové funkce, t.j. u maximalizace ji zvyšuje), t.j. zvýší-li se počet pracovných hodín o 1 hodinu (za předpokladu, že ostatní hodnoty modelu zůstávají konstantní), vzroste celkový zisk o 40 Kč. Je možné vyzkoušet na výše uvedeném příkladu, když změním v zápisu v LINGO u omezení [PRAC_HOD] hodnotu 800 na 801, tak účelová funkce vzroste o 40 Kč (z 32 000 Kč na 32 040 Kč)
u maximalizace a omezení je typu ≥: duální cena je vždy ≤ 0 (negativní duální cena zhoršuje hodnotu účelové funkce, t.j. u maximalizace ji snižuje), vyzkoušet u příkladu 2 omezení x1-0.5*x2x4>=0 změnit na x1-0.5*x2-x4>=1, hodnota účelové funkce klesne z 280 000 na 279 850 (přesně o hodnotu duální ceny 150)
u minimalizace a omezení je typu ≤: duální cena je vždy ≥ 0 (pozitivní duální cena zlepšuje hodnotu účelové funkce, t.j. u minimalizace snižuje) 2
u minimalizace a omezení je typu ≥: duální cena je vždy ≤ 0 (negativní duální cena zhoršuje hodnotu účelové funkce, t.j. u minimalizace ji zvyšuje), vyzkoušet u příkladu 4 omezení 45*x1+40*x2>=40000 změnit na 45*x1+40*x2>=40001, hodnota účelové funkce se zvýší na 42 240,32 (přesně o hodnotu duální ceny 0,32)
maximalizace nebo minimalizace a omezení je =: duální cena může být ><= 0 (např. minimalizace a omezení a duální cena > 0 znamená zlepšení (snížení) hodnoty účelové funkce).
a) maximalizacia zisku – CELOCISELNE
MODEL: ! ucelova funkce; max = 120*x1+50*x2+150*x3+100*x4; ! omezeni; 5*x1+x2+9*x3+12*x4<=1500; 2*x1+3*x2+4*x3+x4<=1000; 3*x1+2*x2+5*x3+10*x4<=800; @GIN (x1); @GIN (x2); @GIN (x3); @GIN (x4); END Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations:
31970.00 31970.00 0.000000 0 4
Variable X1 X2 X3 X4 Row 1 2 3 4
Value 266.0000 1.000000 0.000000 0.000000 Slack or Surplus 31970.00 169.0000 465.0000 0.000000
3
Reduced Cost -120.0000 -50.00000 -150.0000 -100.0000 Dual Price 1.000000 0.000000 0.000000 0.000000
b) maximalizacia objemu produkcie MODEL: ! ucelova funkce; max = x1+x2+x3+x4; ! omezeni; 5*x1+x2+9*x3+12*x4<=1500; 2*x1+3*x2+4*x3+x4<=1000; 3*x1+2*x2+5*x3+10*x4<=800; END Global optimal solution found. Objective value: Infeasibilities: Total solver iterations:
360.0000 0.000000 3
Variable X1 X2 X3 X4 Row 1 2 3 4
Value 80.00000 280.0000 0.000000 0.000000 Slack or Surplus 360.0000 820.0000 0.000000 0.000000
4
Reduced Cost 0.000000 0.000000 0.8000000 1.200000 Dual Price 1.000000 0.000000 0.2000000 0.2000000
2. Úloha o optimálnom výrobnom pláne (optimálne využitie výrobných faktorov) – výroba polotovarov
MODEL: ! ucelova funkce; max = 450*x1+275*x2+600*x3+350*x4; ! omezeni; x1+2*x2+x3+3*x4<=1200; 3*x1+2*x2+3*x3+x4<=1400; x1-0.5*x2-x4>=0; x3<=150; x4>=100; END Global optimal solution found. Objective value: Infeasibilities: Total solver iterations:
280000.0 0.000000 3
Variable X1 X2 X3 X4 Row 1 2 3 4 5 6
Value 275.0000 0.000000 100.0000 275.0000 Slack or Surplus 280000.0 0.000000 0.000000 0.000000 50.00000 175.0000
5
Reduced Cost 0.000000 200.0000 0.000000 0.000000 Dual Price 1.000000 0.000000 200.0000 -150.0000 0.000000 0.000000
3. Úloha o optimálnom výrobnom pláne (optimálne využitie výrobných faktorov) – výroba kompletov a) x4 jako komplet [ks] MODEL: ! ucelova funkce; max = x4; ! omezeni; 0.05*x1+0.1*x2+0.1*x3<=200; 0.04*x1+0.02*x2+0.03*x3 <=80; x1-2*x4=0; x2-2*x4=0; x3-x4=0; END Global optimal solution found. Objective value: Infeasibilities: Total solver iterations:
500.0000 0.000000 0
Variable X4 X1 X2 X3 Row 1 2 3 4 5 6
Value 500.0000 1000.000 1000.000 500.0000 Slack or Surplus 500.0000 0.000000 5.000000 0.000000 0.000000 0.000000
b) x3 jako zpětný reflektor a zároveň komplet [ks] MODEL: ! ucelova funkce; max = x3; ! omezeni; 0.05*x1+0.1*x2+0.1*x3<=200; 0.04*x1+0.02*x2+0.03*x3 <=80; x1-2*x3=0; x2-2*x3=0; END Global optimal solution found. 6
Reduced Cost 0.000000 0.000000 0.000000 0.000000 Dual Price 1.000000 2.500000 0.000000 -0.1250000 -0.2500000 -0.2500000
Objective value: Infeasibilities: Total solver iterations:
500.0000 0.000000 0
Variable X3 X1 X2 Row 1 2 3 4 5
Value 500.0000 1000.000 1000.000 Slack or Surplus 500.0000 0.000000 5.000000 0.000000 0.000000
7
Reduced Cost 0.000000 0.000000 0.000000 Dual Price 1.000000 2.500000 0.000000 -0.1250000 -0.2500000
4. Úloha o výžive (zmiešavací-směšovací problém)
MODEL: ! ucelova funkce; min = 42*x1+45*x2; ! omezeni; 25*x1+35*x2>=20000; 45*x1+40*x2>=40000; 30*x1+35*x2>=32000; END Global optimal solution found. Objective value: Infeasibilities: Total solver iterations:
42240.00 0.000000 2
Variable X1 X2 Row 1 2 3 4
Value 320.0000 640.0000 Slack or Surplus 42240.00 10400.00 0.000000 0.000000
8
Reduced Cost 0.000000 0.000000 Dual Price -1.000000 0.000000 -0.3200000 -0.9200000
5. Úloha o výžive (zmiešavací-směšovací problém)
MODEL: ! ucelova funkce; min = 0.3*x1+0.9*x2; ! omezeni; x1+x2>=800; -0.21*x1+0.3*x2>=0; -0.03*x1+0.01*x2<=0; END Global optimal solution found. Objective value: Infeasibilities: Total solver iterations:
437.6471 0.000000 2
Variable X1 X2 Row 1 2 3 4
Value 470.5882 329.4118 Slack or Surplus 437.6471 0.000000 0.000000 10.82353
9
Reduced Cost 0.000000 0.000000 Dual Price -1.000000 -0.5470588 -1.176471 0.000000
