MME I - cv. cˇ . 1
27. 9. 2010
Kl´ıcˇ ov´a slova: u´ lohy LP, formulace modelu.
1
´ Ulohy Line´arn´ıho programov´an´ı
Line´arn´ı programov´an´ı je jednou z cˇ a´ st´ı operaˇcn´ıho v´yzkumu a zpravidla se pouˇz´ıv´a ˇ sen´ı tˇechto u´ loh si pro ˇreˇsen´ı optimalizaˇcn´ıch u´ loh ekonomick´ych model˚u. Reˇ m˚uzˇ eme rozdˇelit do 4 krok˚u: 1. Formulace ekonomick´eho modelu. • ujasnˇen´ı probl´emu, • popisuje procesy (ˇcinnosti), cˇ initele (podm´ınky) a c´ıl optimalizace, • v ek. modelu mus´ı b´yt stanoveny vˇsechny kvantitativn´ı vztahy mezi procesy, cˇ initely a c´ılem a stanoveny jednotky ve kter´ych je mˇeˇr´ıme. 2. Formulace matematick´eho modelu. • pˇreformulov´an´ı ekonomick´eho modelu, • promˇenn´e xi , i = 1...n, • vlastn´ı omezen´ı (nerovnice typu ≥, ≤, =, • nevlastn´ı omezen´ı (xi ≤ 0, • u´ cˇ elovou funkci. ˇ sen´ı matematick´eho modelu. 3. Reˇ • r˚uzn´e metody pro jednotliv´e typy pˇr´ıklad˚u, univerz´aln´ı Simplexov´a metoda. 4. Rozbor v´ysledn´eho ˇreˇsen´ı. • ekonomick´a interpretace, • verifikace, • anal´yza zmˇen.
´ 1.1 Typy uloh LP Typick´ymi u´ lohami line´arn´ıho programov´an´ı jsou: • u´ lohy v´yrobn´ıho pl´anov´an´ı • smˇesˇovac´ı probl´emy 1
MME I - cv. cˇ . 1
27. 9. 2010
• u´ lohy o optim´aln´ım dˇelen´ı materi´alu • distribuˇcn´ı u´ lohy Mezi dalˇs´ı aplikace patˇr´ı: u´ lohy finanˇcn´ıho pl´anov´an´ı, pl´anov´an´ı reklamy, rozvrhov´an´ı pracovn´ık˚u, u´ lohy LP s podm´ınkami celoˇc´ıselnosti (probl´em batohu, probl´em obchodn´ıho cestuj´ıc´ıho, pˇriˇrazovac´ı probl´em) atd. ´ 1.1.1 Ulohy v´yrobn´ıho pl´anov´an´ı • urˇcen´ı druhu a mnoˇzstv´ı v´yrobk˚u, kter´e se budou vyr´abˇet z celkov´e nab´ıdky, • omezen´e kapacity, • dodrˇzet poˇzadavky, • c´ılem optimalizace obvykle maximalizace zisku, trˇzeb nebo mnoˇzstv´ı v´yrobk˚u, popˇr. minimalizace n´aklad˚u apod., • promˇenn´a oznaˇcuje druh v´yrobku, jej´ı hodnota urˇcuje mnoˇzstv´ı vyr´abˇen´eho v´yrobku ve stanoven´ych jednotk´ach. Pˇr´ıklad 1 ˇ Firma vyr´ab´ı sˇroubky a matice. Sroubky i matice jsou lisov´any – vylisov´an´ı krabiˇcky ˇ sˇroubk˚u trv´a 1 minutu, krabiˇcka matic je lisov´ana 2 minuty. Sroubky i matice bal´ı do krabiˇcek, ve kter´ych je pak prod´av´a – krabiˇcka sˇroubk˚u se bal´ı 1 minutu, krabiˇcka matic 4 minuty. Firma m´a k dispozici 2 hodiny cˇ asu pro lisov´an´ı a 3 hodiny cˇ asu pro balen´ı v´yrobk˚u. Vzhledem k popt´avce je tˇreba vyrobit alespoˇn o 90 krabiˇcek sˇroubk˚u v´ıce neˇz krabiˇcek matic. Z technick´ych d˚uvod˚u nelze vyrobit v´ıce neˇz 110 krabiˇcek sˇroubk˚u. Zisk z jedn´e krabiˇcky sˇ roubk˚u je 40 Kˇc, z jedn´e krabiˇcky matic 60 Kˇc. Firma nem´a pot´ızˇ e s odbytem v´yrobk˚u. Kolik krabiˇcek sˇroubk˚u a matic m´a firma vyrobit, chce-li dos´ahnout maxim´aln´ıho zisku? Pˇr´ıklad 2 ˇ Cokol´ adovna vyr´ab´ı 5 druh˚u v´yrobk˚u. Spotˇrebov´av´a 3 z´akladn´ı suroviny: tuk, kakao a cukr, jeˇz jsou k dispozici v omezen´em mnoˇzstv´ı : 1500 kg, 300 kg, a 450 kg na den . Kapacita strojov´eho zaˇr´ızen´ı je dostateˇcn´a, stejnˇe tak energie, pracovn´ı s´ıly i dalˇs´ı zdroje jsou k dispozici v dostateˇcn´em mnoˇzstv´ı. Spotˇreba surovin na v´yrobky je uvedena v tabulce.
2
MME I - cv. cˇ . 1
27. 9. 2010
Tab. 1: Koeficienty spotˇreby surovin v kg na 1kg v´yrobku a odbytov´e ceny za 1kg v´yrobku: V1
V2 V3 V4 V5 kapacita TUK 0,4 0,3 0,6 0,6 1500 KAKAO 0,05 0,2 0,1 0,1 300 CUKR 0,1 0,2 0,2 0,1 0,2 450 Cena 20 120 100 140 40 ´ 1.1.2 Smˇesˇovac´ı ulohy • vytvoˇren´ı smˇesi poˇzadovan´ych vlastnost´ı, • d´ana nab´ıdka sloˇzek (komponent), • omezen´ı disponibiln´ıho mnoˇzstv´ı sloˇzek, • jsou urˇceny poˇzadovan´e vlastnosti smˇesi (napˇr. v´aha, obsah sloˇzky v %, obsah v´yzˇ ivn´e l´atky), • c´ılem je vˇetˇsinou minimalizovat n´aklady na vytvoˇren´ı smˇesi, • promˇenn´e urˇcuj´ı pouˇzit´e sloˇzky a jejich mnoˇzstv´ı. Pˇr´ıklad 3 Denn´ı j´ıdeln´ıcˇ ek sestaven´y dle z´asad racion´aln´ı v´yzˇ ivy je zapotˇreb´ı doplnit o 21 g tuk˚u, nejv´ysˇe 57 g sacharid˚u a alespoˇn 35 g b´ılkovin a 2 mg vitaminu C. Jak´e mnoˇzstv´ı sojov´ych bob˚u a n´ızkoenergetick´eho jogurtu uspokoj´ı tyto poˇzadavky pˇri minim´aln´ıch v´ydaj´ıch? Podkladov´e u´ daje pro vyˇreˇsen´ı tohoto probl´emu, vztaˇzen´e na 100 g uveden´ych potravin, jsou obsaˇzeny v tab. 2. Tab. 2: obsah potˇrebn´ych zˇ ivin ve v´yrobc´ıch: boby jogurt
b´ılkoviny (g) 35 5
tuky (g) 14 2
sacharidy (g) vitam´ın C (mg) 28 – 7 0,4
cena (Kˇc) 3 4
ˇ ´ 1.1.3 Rezn´ e ulohy ´ • jinak ,,Ulohy o optim´aln´ım dˇelen´ı materi´alu“, ˇreˇs´ı se probl´em dˇelen´ı vˇetˇs´ıch celk˚u na menˇs´ı cˇ a´ sti, • v LP jde o jednorozmˇern´e celky (d´elka), napˇr. provazy, tyˇce, trubky apod.,
3
MME I - cv. cˇ . 1
27. 9. 2010
• je zn´ama d´elka dˇelen´ych kus˚u a jejich poˇcet, • je urˇcena d´elka a poˇcet poˇzadovan´ych kus˚u, • poˇzadavky na to, vjak´em pomˇeru maj´ı vznikl´e menˇs´ı cˇ a´ sti b´yt, kolik minim´alnˇe resp. maxim´alnˇe jich m´a vzniknout, kolik je k dispozici vˇetˇs´ıch kus˚u apod. • c´ılem je vˇetˇsinou minimalizace odpadu, ale tak´e minimalizace spotˇreby materi´alu nebo n´aklad˚u, • kaˇzd´y vˇetˇs´ı celek lze na menˇs´ı cˇ a´ sti rozˇrezat celou ˇradou zp˚usob˚u – je zn´amo nebo je tˇreba sestavit tzv. “ˇrezn´e sch´ema”, • procesem a tud´ızˇ i promˇennou je zde pouˇzit´ı jednoho z moˇzn´ych zp˚usob˚u dˇelen´ı vˇetˇs´ıho celku, hodnota promˇenn´e ukazuje cˇ etnost jeho pouˇzit´ı, • u´ loha o dˇelen´ı materi´alu m˚uzˇ e b´yt i v´ıcerozmˇer-n´a, tzn. dˇelen´ı ploˇsn´ych nebo prostorov´ych pˇredmˇet˚u. V tomto pˇr´ıpadˇe jiˇz nejde o u´ lohy LP. Pˇr´ıklad 4 V z´ameˇcnick´e fimˇe je tˇreba naˇrezat 3 druhy kovov´ych tyˇc´ı T1, T2, T3, pˇriˇcemˇz tyˇce T1 maj´ı d´elku 110 cm, tyˇce T2 90 cm a tyˇce T3 60 cm. K dispozici jsou tyˇce standardn´ı d´elky 240 cm, kter´e je tˇreba rozˇrezat. Pˇr´ıpustn´y je takov´y zp˚usob ˇrez´an´ı tyˇc´ı, pˇri kter´em nebude odpad pˇresahovat 40 cm. Je tˇreba naˇrezat 700 tyˇc´ı T1, 400 tyˇc´ı T2 a 1500 tyˇc´ı T3. M´ame stanovit takov´y pl´an ˇrez´an´ı tyˇc´ı, pˇri kter´em se na splnˇen´ı poˇzadavk˚u: • pouˇzije co nejmenˇs´ı poˇcet tyˇc´ı standardn´ı d´elky, • proˇreˇze co nejm´enˇe materi´alu (bude minimalizov´an celkov´y odpad), • pouˇzije co nejmenˇs´ı poˇcet ˇrez˚u.
2
Formulace matematick´eho modelu
Pro v´ysˇe uveden´e u´ lohy si naformulujme matematick´e modely.
3
´ Dom´ac´ı ukol
Na procviˇcen´ı naformulujte matematick´y model:
4
MME I - cv. cˇ . 1
27. 9. 2010
Pˇr´ıklad 5 Podnik vyr´ab´ı v´yrobky V1, V2, V3, V4 ze surovin S1 a S2, kter´e jsou k dispozici v mnoˇzstv´ı 10,05 t a 8,04 t. V´yrobek V1 slouˇz´ı t´ezˇ jako polotovar pro v´yrobu v´yrobk˚u V2 a V3. Spotˇreba surovin (v kg) a polotovaru V1 (v ks) na 1 kus jednotliv´ych v´yrobk˚u je patrna z tab. 3, kter´a obsahuje t´ezˇ ceny prodan´ych v´yrobk˚u (v Kˇc). Tab. 3: S1 S2 V1 cena
V1 V2 V3 V4 2 15 26 12 3 8 18 40 – 1 2 – 200 1500 3100 1250
Stanovte takovou strukturu v´yroby, pˇri kter´e by prodejem v´yrobk˚u z´ıskan´ych z dan´eho mnoˇzstv´ı surovin bylo dosaˇzeno maxim´aln´ıch trˇzeb. Pˇr´ıklad 6 Investiˇcn´ı spoleˇcnost m´a investovat 50 mil. Kˇc do cenn´ych pap´ır˚u. V u´ vahu pro tuto investici pˇrich´az´ı pˇet variant (akcie tˇr´ı r˚uzn´ych spoleˇcnost´ı A1, A2, A3 a dva druhy obligac´ı O1, O2). Kaˇzd´a z tˇechto pˇeti variant je charakterizov´ana oˇcek´avanou m´ırou v´ynosu v procentech za rok a bezrozmˇern´ym koeficientem, kter´y ud´av´a m´ıru rizika t´eto investice (ˇc´ım vyˇssˇ´ı koeficient, t´ım vyˇssˇ´ı riziko). Charakteristiky dan´ych pˇeti variant jsou uvedeny v n´asleduj´ıc´ım pˇrehledu:
v´ynos [%] m´ıra rizika
A1 A2 A3 25 18 20 9 5 7
O1 O2 14 12 3 1
Investiˇcn´ı strategie spoleˇcnosti pˇredpokl´ad´a: • do obligac´ı bude investov´ano minim´alnˇe 50 % celkovˇe investovan´e cˇ a´ stky, • celkov´a m´ıra rizika by nemˇela b´yt vyˇssˇ´ı neˇz 5 (celkov´a m´ıra rizika se vypoˇcte jako v´azˇ en´y aritmetick´y pr˚umˇer mˇer rizika jednotliv´ych variant – v´ahy jsou v tomto pˇr´ıpadˇe investovan´e cˇ a´ stky), • kaˇzd´a z variant bude nakoupena v minim´aln´ım objemu 5 mil. Kˇc. C´ılem modelu je naj´ıt takovou strukturu portfolia, kter´a bude maximalizovat celkov´y oˇcek´avan´y v´ynos a pˇritom bude respektovat uvedenou investiˇcn´ı strategii.
5
