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