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.

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (2): 3,5

Přečtěte si také

Vázaný extrém

Diskuse

Karel29.8.2010

@ stařičký student
Existuje vynikající programový systém, jehož demo-verse nestojí vůbec nic. Program se jmenuje LINGO a dá se stáhnout na adrese http://www.lindo.com
Demo-licence platí 30 dní. Program při startu vyžádá licenční kód nebo DEMO. Pokud kliknete na DEMO, můžete LINGO používat 30 dní, pak je nutné si na DEMO nakliknout znovu. Takže se jedná prakticky o časové neomezenou licenci.
Kapacita programu je omezená na 200 podmínek a 300 proměnných (LP) - pokud se dobře pamatuji - celočíselně a nelineární úlohy podléhají dalším omezením.
V případeě potřeby lze zakoupit odstupňovanou plnou licenci. Její nejvyšší stupeň nemá žádné omezení.
Pozdrav
Karel

Pavel Mička30.1.2010

Tak jsem přidal i to grafické řešení.

Pavel Mička19.1.2010

To graficke reseni si pisu na wishlist. Ono to ma stejne pouze omezeny vyznam, protoze to asi lze resit rozumne jeste ve 3D, ale do vyssich dimenzi bych se na papire nepoustel :-)))...tam to je ciste o simplexove metode nebo metodach vnitrniho bodu. Jinak by to asi taky chtel zminit dualni ulohu a veci kolem (toho je nejak vic, kdyz se to vezme do dusledku). Jinak k te aplikaci nejsem schopen poradit, protoze osobne pouzivam Matlab, ve kterem to lze delat velmi pohodlne (vizte kod).

Stařičký student19.1.2010

Kdysi, v dobách kdy jsem ještě studoval, kolovali mezi námi (tehdy) nelegální programy, které podobné příklady dokázali vyřešit. Já už dnes ručního výpočtu nejsem schopen, a grafické vymezení možných řešení (to byste měl mimochodem v teoretické části zmínit) mi nestačí. Existují dnes nějaké aplikace (freeware) umožňující najít řešení takovýchto jednodušších úloh (a složitějších třeba za poplatek nebo při zakoupení aplikace)?