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 a_ij jednotek i-tého zdroje. Všechny zdroje jsou omezené a můžemke použít maximálně b_i jednotek i-tého druhu. Zisk z prodeje výrobku j-tého typu je c_j. 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$

Matlab


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

$z \\geq 0$
$s \\geq 0$

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

z	s	a	c	b
2	4	1	0	201
8	12	0	1	463
-100	-150	0	0	0

Provedeme první iteraci simplexového algoritmu.

z	s	a	c	b
-2/3	0	1	-1/3	140/3
2/3	1	0	1/12	463/12
0	0	0	25/2	11575/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í.

z	s	a	c	b
0	1	1	-1/4	341/4
1	3/2	0	1/8	463/8
0	0	0	25/2	11575/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 Kč

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.