Směšovací problém

Směšovací problém je jednou ze základních úloh lineárního programování.

Mějme n různých surovin, cílem je namíchat výsledný produkt tak, aby měl požadované složení, ale náklady na suroviny byly minimální. Počet jednotek suroviny j označíme x_j, cenu za jednotku c_j. Požadované složení je popsáno vektorem pravých stran b takovým způsobem, že řádek i značí předepsané množství i-té látky ve výsledném produktu. Jednotkové množství j-té suroviny obsahuje aij jednotek látky i.

Obdobou směšovacího problému je tzv. dietní (nutriční problém), jehož cílem je sestavit jídelníček takovým způsobem, aby obsahoval předepsané látky, ale cena byla minimální.

$\\min \\; \\{ {\\mathbb{c}}^{T} {\\mathbb{x}} : {\\mathbb{Ax}} = {\\mathbb{b}}, {\\mathbb{x}} \\geq 0 \\}$

Příklad

Pacient by měl denně sníst potraviny o úhrnné energetické hodnotě alespoň 12000kJ. Strava by měla obsahovat minimálně 475 gramů sacharidů, 67 gramů bílkovin a 83 gramů tuků.

Kilogram potraviny A má 3110kJ, obsahuje 0g sacharidů, 200g bílkovin a 0g tuků a stojí 159Kč.

Kilogram potraviny B má 9630kJ a obsahuje 500g sacharidů, 0g bílkovin a 0g tuků a stojí 20Kč.

Kilogram potraviny C má 2000kJ, obsahuje 0g sacharidů, 0g bílkovin a 100g tuků, stojí 40Kč.

Kilogram potraviny D má 20000kJ, obsahuje 0g sacharidů, 60g bílkovin a 830g tuků, stojí 200Kč.

Sestavte z těchto surovin vhodný dietní plán.

Řešení

$\\min \\; 159A + 20B + 40C + 200D$

Za podmínek:

500B = 475

$A \\geq 0$
$B \\geq 0$
$C \\geq 0$
$D \\geq 0$

Matlab


f = [159; 20; 40; 200];
A = [];
b = [];
Aeq = [
    0 500 0 0;
    200 0 0 60;
    0 0 100 830;
    3110 9630 2000 20000
    ];
beq = [475; 67; 83; 12000];
lb = [0 0 0 0];
ub = [];

linprog(f, A, b, Aeq, beq, lb, ub)

Pacient by měl sníst 0.3168kg potraviny A, 0.95kg potraviny B, 0.3265kg potraviny C, 0.0607kg potraviny D.

Literatura

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

Příklad

Řešení

Literatura

Doporučujeme