Optimální výrobní program

Optimální výrobní program je jednou z typových úloh lineárního programování.

Výrobce vyrábí n výrobků, z nichž každý vyžaduje m různých surovin. Na výrobu výrobku j-tého typu se spotřebuje aij jednotek i-tého zdroje. Všechny zdroje jsou omezené a můžemke použít maximálně bi jednotek i-tého druhu. Zisk z prodeje výrobku j-tého typu je cj. Cílem úlohy je maximalizovat zisk z výroby.


\\max \\; \\{ {\\mathbb{c}}^{T} {\\mathbb{x}} : {\\mathbb{Ax}} \\leq {\\mathbb{b}}, {\\mathbb{x}} \\geq 0 \\}

Příklad

Mějme továrnu, která vyrábí židle a stoly. Na židli jsou zapotřebí 2 prkna 8 hřebíku, na stůl 4 prkna a 12 hřebíků. Židli prodáváme za 100Kč a stůl za 150Kč. Na skladě máme 201 prken a 463 hřebíků. Kolik máme vyrobit židlí a stolů tak, aby byl zisk maximální?

Řešení

Matlab

\\max \\; 100z + 150s

Za podmínek:

2z + 4s \\leq 201
8z + 12s \\leq 463
z \\geq 0
s \\geq 0

f = [-100; -150]; % matlab minimalizuje, funkci je treba otocit
A = [2 4; 8 12];
b = [201; 463];
lb = [0,0];
ub = [+inf, +inf];

linprog(f, A, b, [], [], lb, ub)

Měli bychom vyrobit 30 židlí a 18 stolů.

Simplexový algorimus

Nejprve příklad přepíšeme do požadovené formy.

\\max \\; 100z + 150s

Za podmínek:

2z + 4s + a = 201
8z + 12s + c = 463
z \\geq 0
s \\geq 0

Zadání přepíšeme do simplexové tabulky.

zsacb
2410201
81201463
-100-150000

Provedeme první iteraci simplexového algoritmu.

zsacb
-2/301-1/3140/3
2/3101/12463/12
00025/211575/2

Nalezené řešení je sice optimální, ale ze simplexové tabulky vidíme, že není jediné, protože u nebázové proměnné máme nulový koeficient. Proto dopočítáme řešení podle první proměnné. Celkové řešení bude konvexní kombinací prvního a druhého dílčího řešení.

zsacb
011-1/4341/4
13/201/8463/8
00025/211575/2

Celkové řešení je:


\\mathbb{x^{*}} = 
\\lambda \\cdot 
\\left[
   \\begin{matrix} 
      {{463} \\over {8}} \\\\ \\\\ 
      0
   \\end{matrix}
\\right]

 + (1 - \\lambda) \\cdot 
\\left[
\\begin{matrix} 
   0 \\\\ \\\\
   {{463} \\over {12}} 
\\end{matrix}
\\right]

Z duálních proměnných je vidět, že při zvýšení zásob prken o 1 nedojde ke zvýšení zisku, naproti tomu při zvýšení zásob hřebíků o jednotku se zvýší zisk o 25/2

Grafické řešení
Grafické řešení problému

Grafické řešení

Jednoduché případy lineární optimalizace lze také řešit graficky. Tento postup je únosný maximálně pro 3 proměnné (3D prostor).

Postup je velmi intuitivní - do prostoru zakreslíme příslušné poloprostory omezení a vznikne polyedr přípustných řešení. Dále zakreslíme vektor kriteriální funkce nebo jeho normály a na základě jeho směru zjistíme na tomto mnohostěnu bod (nebo více bodů), který je maximálním nebo minimálním řešením daného problému.

Literatura

  • ŠTECHA, Jan. Optimální rozhodování a řízení : Přednášky. [s.l.] : Vydavatelství ČVUT, 2002. 241 s. ISBN 80-01-02083-5.







Doporučujeme