1
OBECNÉ OPTIMALIZAČNÍ MODELY
2
Obsah
• Historická poznámka
• Úloha na volný extrém
• Úloha na vázaný extrém
• Optimalizační úloha
• Klasifikace optimalizačních úloh
• Možnosti řešení optimalizačních úloh
3
Historická poznámka
• Nalezení extrému funkce pomocí metod matematické analýzy - derivace atd.
• Praktické aplikace - omezení definičního oboru funkce
4
Úloha na volný extrém
min f(x) x Df kde Df je definiční obor funkce f(x).
minimální hodnota funkce na celém definičním oboru
5
Květák a kedlubny
• Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny.
• Zemědělec ví, že se náklady na produkci těchto dvou komodit skládají ze dvou částí– Náklady fixní ve výši 3500 Kč, které musí vynaložit vždy
– Variabilní náklady, které progresivně rostou vzhledem k obdělávané výměře. U květáku rostou přibližně podle funkce N1 = 0,25 x1
2-3x1, u kedluben zhruba podle funkce N2 = x22-4x2,
kde x1,2 jsou výměry plodin.
• Najděte výměru plodin s minimálními náklady.
6
Květák a kedlubny• Úloha na volný extrém
– Funkce nákladů• x1 výměra květáku (ar)
• x2 výměra kedluben (ar)
• Náklady
f(x) = 3500 + 0,25x12 - 3x1 + x2
2 – 4x2
• Kritérium
f(x) = 0,25x12 - 3x1 + x2
2 - 4x2 min
• Extrémx1 = 6, x2 = 2
7
Úloha na vázaný extrém
min f(x) x M M= x q(x) =0
úloha nalezení extrému funkce podél křivky q(x)=0
• Lagrangeova funkce
L(x,u) = f(x) + uT.q(x)
8
Květák a kedlubny
• Soukromý zemědělec se rozhoduje o výměře dvou druhů zeleniny. – Květák chce pěstovat na 8 arech.
• Zemědělec ví, že se náklady na produkci těchto dvou komodit skládají ze dvou částí– Náklady fixní ve výši 3500 Kč, které musí vynaložit vždy– Variabilní náklady, které progresivně rostou vzhledem k
obdělávané výměře. U květáku rostou přibližně podle funkce N1 = 0,25 x1
2-3x1, u kedluben zhruba podle funkce N2 = x22-4x2,
kde x1,2 jsou výměry plodin.
• Najděte výměru plodin s minimálními náklady.
9
Květák a kedlubny• Úloha na vázaný extrém
– Funkce nákladů• x1 výměra květáku (ar)• x2 výměra kedluben (ar)• Kritérium
f(x) = 0,25x12 - 3x1 + x2
2 – 4x2 min
– Křivka• q(x) = x1 – 8 = 0
• Řešení– Lagrangeova funkce
L(x1, x2, u) = 0,25x12 - 3x1 + x2
2 – 4x2 + u (x1 – 8)
– Extrémx1 = 8 a pak x2 = 20
10
Optimalizační úloha
min f(x) qi(x) 0 , i = 1, ..., m ,
xT=(x1, x2, ..., xn)T Rn ,
f(x) a qi (x) jsou reálné funkce více proměnných a x je prvek vektorového prostoru Rn.
11
Květák a kedlubny• Soukromý zemědělec se rozhoduje o výměře dvou druhů
zeleniny. – K dispozici má 35 arů půdy, na nichž by chtěl pěstovat květák a
kedlubny. Pro květák lze využít alespoň 8 arů.
• Zemědělec ví, že se náklady na produkci těchto dvou komodit skládají ze dvou částí– Náklady fixní ve výši 3500 Kč, které musí vynaložit vždy– Variabilní náklady, které progresivně rostou vzhledem k
obdělávané výměře. U květáku rostou přibližně podle funkce N1 = 0,25 x1
2-3x1, u kedluben zhruba podle funkce N2 = x22-4x2,
kde x1,2 jsou výměry plodin.
• Najděte výměru plodin s minimálními náklady.
12
Optimalizační úloha
Základní prvky optimalizačního modelu
proměnné - procesy
omezující podmínky
kriteriální - účelová funkce
Základní pojmy
přípustné a nepřípustné řešení
optimální řešení
13
Květák a kedlubny
• Model optimalizační úlohy– Proměnné
• x1 výměra květáku (ar)• x2 výměra kedluben (ar)
– Omezující podmínky• q1 (x) = x1 + x2 - 35 0 celková výměra• q2 (x) = x1 – 8 0 výměra květáku
– Kritérium• f(x) = 0,25x1
2 - 3x1 + x22 – 4x2 min
14
Květák a kedlubny
• Řešení v Excelu, modul Řešitel
Proměnné x
Parametry omezujících podmínek
Parametry kriteriální fce
q(x)
f(x)
<=>
0
min
15
Květák a kedlubny
• Řešení v Excelu, modul Řešitel
květák kedlubny
0 0
x1 x2
1 1 0 <= 35
1 0 >= 8
0,25 10 0
-3 -40 0
0 -------> MIN
náklady 3500
16
Klasifikace optimalizačních úloh Z hlediska počtu kritérií
jednokriteriální optimalizační model, vícekriteriální optimalizační model.
Z hlediska typu kritéria minimalizační model f(x) MIN maximalizační model f(x) MAX cílový model dosažení cíle f(x) = h
Podle typu použitých funkcí lineární optimalizační model nelineární optimalizační model
konvexní model - kvadratický konvexní model nekonvexní model.
17
Možnosti řešení optimalizačních úloh
Nalezení vektoru x splňujícího omezující podmínky qi(x) 0 , i = 1, ..., m
Nalezení minimální hodnoty účelové funkce f(x).
Grafický přístup Analytické metody Numerické metody
18
Nalezení přípustného řešeníProblém - nekonvexnost množiny přípustných řešení.
Když už jedno přípustné řešení najdeme, jak najít to optimální.
19
Nalezení extrému účelové funkceProblém - nekonvexnost účelové funkce - lokální a globální
extrémy. Kterým směrem postupovat k optimálnímu řešení?
20
Analytické metody• Lagrangeova funkce
L(x,u) = f(x) + uT.q(x)
• Sedlový bod
L(xopt, u) L(xopt, uopt) L(x, uopt)
• Kuhn-Tuckerovy podmínky - vlastnosti sedlového bodu
• Wolfeho algoritmus pro řešení kvadratických optimalizačních úloh
21
Numerické metody
• Gradientní metody
xk+1 = xk + k.sk
• Penalizační a bariérové metody
min f(x) + pk(x) x Rn • Heuristické metody
• metoda TOP TWENTY
