Skripta 2004

ěchto pět výrobních procesů tvoří kostru ekonomického modelu, na jejich úrovni závisí spotřeba surovin (množství vystupujících činitelů). V našem případě je první výrobní proces charakterizován po technické stránce sloupcem koeficientů:
Při jednotkové úrovni prvního procesu - výroba jednotky (1kg) výrobku V1 :
0 spotřeba suroviny S1 (v kg)
0,05 spotřeba suroviny S2 (v kg)
0,1 spotřeba suroviny S3 (v kg)

1 spotřeba suroviny S4 (v kg)

Kriteriem optimality v našem problému je hodnota výroby v daných cenách. Snadno ji uvedeme do vztahu k úrovním procesů, ohodnotíme výsledek každého procesu - výrobu příslušného výrobku - danou cenou. Každý proces je tedy po ekonomické stránce charakterizovaná cenou výrobku, který je jeho výsledkem.
V dalším budeme matematicky formulovat probraný matematický model. Proměnné modelu musí vyjadřovat hledaný výrobní program, tj. úrovně jednotlivých výrobních procesů a tím současně množství jednotlivých výrobků, která mají být vyráběna. Budeme tedy potřebovat 5 proměnných: x1 .............x5. Jejich věcný smysl bude :
x1 .......množství výrobků V1 v kg, které bude vyráběno za den
x2 .......množství výrobků V2 v kg, které bude vyráběno za den
x3 .......množství výrobků V3 v kg, které bude vyráběno za den
x4 .......množství výrobků V4 v kg, které bude vyráběno za den
x5 .......množství výrobků V5 v kg, které bude vyráběno za den
Tyto proměnné, v souladu se svým věcným významem, mohou nabývat pouze nezáporných hodnot:
xj ≥ O , j = 1,2,....,5.
Množství výroby je omezeno ve spotřebě 3 surovin. Tyto omezení vyjádříme třemi lineárními nerovnostmi.
První nerovnost bude vyjadřovat omezení ve spotřebě suroviny S1. Na její pravé straně bude tedy hodnota 1 500, vyjadřující množství suroviny S1 v kg, jež je na den k dispozici. Levá strana musí vyjadřovat spotřebu suroviny S1 na denní výrobní program ve formě lineární funkce proměnných x1, x2,...,x5.
Na výrobek V1 není surovina S1 zapotřebí. Na 1 kg výrobku V2 je potřeba 0,4 kg suroviny S1. Spotřeba suroviny S2 na veškerou výrobu výrobku V2 je pak dána výrazem 0,4 .x 2 .
Analogicky pro spotřebu suroviny S1 na veškerou výrobu výrobku V3 platí: 0,3. x 3.
Spotřebu suroviny S1 na výrobu výrobků V 1 až V 5 vyjádříme jako součet:
0,4 .x2 + 0,3 .x3 + 0,6 .x4 + 0,6 .x5 .
Tato spotřeba suroviny S1 na uvažovaný výrobní program nesmí překročit limit ve spotřebě 1500 kg. Nerovnost bude tedy typu ≤ a bude znít:
0,4 x2 + 0,3 x3 + 0,6 x4+ 0,6 x5 ≤ 1 500
Zcela analogicky pro spotřebu suroviny S2 za celý denní výrobní program můžeme psát :
0,05 x1 + 0,2 x2 + 0,1 x3 + 0,1 x4 ≤ 300,
kde levá strana vyjadřuje spotřebu suroviny S2 (kg) na celý uvažovaný výrobní program - jako funkce proměnných x1, .....,x4, a pravá strana představuje množství suroviny S2 v kg, které je k dispozici.
Třetí nerovnost, vyjadřující omezení ve spotřebě suroviny S3 bude znít:
0,1 x1 + 0,2 x2 + 0,2 x3 + 0,1 x4+ 0,2 x5 ≤ 450.
Konečně musíme formulovat kriterium pro výběr optimálního výrobního programu. Tímto kritériem je podle zadání hodnota výroby v Kč.
Veškerou výrobu ohodnotíme danými cenami. Množství výrobku V1 ve výrobním programu x1 kg násobíme cenou 20 Kč za kg. Výraz 20.x1 pak představuje hodnotu výroby v Kč, kterou firma získá z výroby prvního výrobku. Podobně hodnota výroby ostatních výrobků bude Kč 120 x2, 100 x3, 140 x4, 40 x5. Hodnotu výroby celého výrobního programu lze pak vyjádřit lineární funkcí proměnných x1,............., x5:
20 x1 + 120 x2 + 100 x3 + 140 x4+ 40 x5 .....max.
Účelová funkce z (x1, x2, x3, x4, x5) vyjadřuje tedy hodnotu výroby firmy v Kč běžného denního programu.
Matematický model:
Hledáme nezáporné hodnoty proměnných x1, x2, x3, x4, x5, tj. nezáporný vektor X [x1, x2, x3, x4, x5], vyhovující nerovnostem
0,4 x2 + 0,3 x3 + 0,6 x4 + 0,6 x5 ≤ 1 500
0,05 x1 + 0,2 x2 + 0,1 x3 + 0,1 x4 ≤ 300
0,1 x1 + 0,2 x2 + 0,2 x3 + 0,1 x4 + 0,2 x5 ≤ 450
a maximalizující účelovou funkci
Z = 20 x1 + 120 x2 + 100 x3 + 140 x4+ 40 x5
Příklad 4.2
Výrobní program firmy stanoví, že při nezměněných podmínkách z předcházejícího příkladu musíme navíc respektovat požadavky odbytu, které stanoví, že výrobku V1 musí být vyrobeno alespoň 100kg a výrobku V5 alespoň 500kg.
Postup:
Proměnné, nerovnosti i účelová funkce zůstávají stejné jako v předcházejícím příkladě. Požadavky na výrobní program vyjádříme dalšími 2 nerovnostmi.
Požadavek, že množství výrobku V1 nesmí klesnout pod 100kg, vyjádříme nerovnicí x1 ≥ 100 a podobně x5 ≥ 500.
Matematický model :
Hledáme nezáporný vektor X [x1, x2, x3, x4, x5], vyhovující nerovnostem
0,4 x2 + 0,3 x3 + 0,6 x4 + 0,6 x5 ≤ 1 500
0,05 x1 + 0,2 x2 + 0,1 x3 + 0,1 x4 ≤ 300
0,1 x1 + 0,2 x2 + 0,2 x3 + 0,1 x4 + 0,2 x5 ≤ 450
x1 ≥ 100
x5 ≥ 500
a maximalizující účelovou funkci
Z = 20 x1 + 120 x2 + 100 x3 + 140 x4+ 40 x5
Další modifikace uvedeného základního příkladu 4.1 spočívá v tom, že určitá část produkce firmy se v praxi může použít jako polotovar (potřebný pro vlastní výrobu) a určitá část produkce se realizuje jako finální výrobek.
Příklad 4.3
Firma vyrábí čtyři výrobky V1, V2, V3, V4. Při sestavování výrobního programu je třeba počítat s omezenou kapacitou zařízení Z ( k dispozici je 1 200 hodin čtvrtletně) a s omezeným množstvím suroviny S (1 400 t na čtvrtletí). Výrobky V1 a V2 jsou polotovary potřebné pro výrobu výrobků V2, V3 a V4, mohou však být též prodávány. Odbytové ceny výrobků jsou : 300 Kč za 1 t výrobku V1, 600 Kč za 1 t výrobku V2, 1000 Kč za 1 t V3, 3000 Kč za 1 t V4. Technické koeficienty jsou uvedeny v tabulce 4.2.
Je třeba stanovit výrobní program tak, aby odbyt firmy byl maximální.
Rozbor problému:
Do výroby vstupují čtyři zdroje (zařízení, surovina, výrobek V1,výrobek V2) a vystupují čtyři výrobky (V1,až V4). Výrobky V1 a V2 jako polotovary jsou vstupujícími i vystupujícími činiteli. Definujeme výrobní procesy podobně jako v předcházejícím příkladě 3.1. První výrobní proces = výroba výrobku V1, atd. až čtvrtý výrobní proces = výroba výrobku V4. Existují zde závislosti mezi jednotlivými výrobními procesy. Výstup jednoho je vstupem dalšího procesu (polotovary V1 a V2). Tím je uskutečnění druhého až čtvrtého procesu vázáno na uskutečnění prvního procesu a podobně třetí a čtvrtý proces je vázán na druhý. Závislost mezi jednotlivými procesy ovlivní i tvorbu účelové funkce z. Tak např. při jednotkové úrovni třetího procesu se vyrobí 1 tuna výrobku V3 v hodnotě 1000 Kč (odbytová cena), zároveň se však spotřebuje 0,5 tuny výrobku V1 (o ceně 600 Kč za 1 tunu), které by bylo možno prodat za 300 Kč. Skutečný přínos jednotkové úrovně třetího procesu k hodnotě odbytu je pouze 700 Kč.
V1
V2
V3
V4
Zařízení Z
1,5
-
2
2,5
Surovina S
2
1,5
2
-
Výrobek V1
-
0,5
-
1
Výrobek V2
-
-
0,5
2
Tab.4.2 Spotřeba strojového času zařízení Z v hodinách, suroviny S a výrobku V1 a V2 v
tunách na 1 tunu výrobku.
Formulace matematického modelu:
Hledaný výrobní program je určen čtyřmi veličinami, vyjadřujícími úroveň čtyř výrobních procesů, tj. vyráběným množstvím výrobků V1 až V4. Pro určení výrobního programu potřebujeme tedy čtyři proměnné. První dvě nerovnosti, které vyjadřují omezení ve spotřebě kapacity zařízení a suroviny, stanovíme již známým způsobem. První nerovnost vyjádříme
1,5 x1 + 2 x3 + 2,5 x4 ≤ 1 200
kde na pravé straně je kapacita strojového zařízení, vyjádřená ve strojových hodinách a na levé straně kapacita, která je zapotřebí na výrobní program, je vyjádřena jako funkce proměnných úlohy (rovněž ve strojových hodinách).
Druhá nerovnost
2 x1 + 1,5 x2 + 2 x3 ≤ 1 400
vyjadřuje vztah mezi množstvím suroviny S v t, která je k dispozici (pravá strana nerovnosti) a reálnou spotřebou suroviny S (v tunách) na výrobní program (který je vyjádřen jako funkce proměnných úlohy - viz levá strana nerovnosti).
Další nerovnost vyjadřuje potřebnou relaci mezi výrobkem V1 jako polotovarem a ostatními výrobky. Spotřebu výroby V1 můžeme snadno vyjádřit pomocí koeficientů vstupů:
0,5 x2 + x4
Tato funkce proměnných x2 a x4 vyjadřuje spotřebu výrobku V1 jako polotovaru na výrobu výrobků V2 a V4. Spotřeba výrobku V1 nesmí překročit množství výrobku V1, jež je k dispozici. Nepředpokládáme, že by ve firmě byla nějaká zásoba výrobku V1. Proto můžeme spotřebovat nejvýš vyrobené množství výrobku V1, které je určeno výrobním programem tedy x1. Dostáváme nerovnost
0,5 x2 + x4 ≤ x1,
kde na levé straně je výrobní spotřeba výrobku V1 jako polotovaru na hledaný výrobní program a na pravé straně je množství výrobku V1, jež je k dispozici (vše v tunách).
Analogicky vyjádříme relaci mezi spotřebou výrobku V2 na výrobním programu a výrobou tohoto výrobku nerovností
0,5 x3 + 2 x4 ≤ x2 .
Hodnotu odbytu, která vyplývá z výroby (a prodeje) konkrétního výrobku dostaneme, vynásobíme-li koeficienty jednotkového přínosu k hodnotě odbytu množstvím výrobku. Účelovou funkci dostaneme jako součet hodnot odbytu pro všechny výrobky. Celková hodnota odbytu pak je
Z = 300 x1 + 450 x2 + 700 x3 + 1500 x4

Hodnota odbytu má být maximální.

Matematický model:

Hledáme nezáporný vektor X [x1, x2, x3, x4], vyhovující nerovnostem
1,5 x1 + 2 x3 + 2,5 x4 ≤ 1 200
2 x1 + 1,5 x2 + 2 x3 ≤ 1 400
- x1 0,5 x2 + x4 ≤ 0
- x2 0,5 x3 + 2 x4 ≤ 0
a maximalizující účelovou funkci
Z = 300 x1 + 450 x2 + 700 x3 + 1500 x4
4.3. Grafické řešení úloh lineárního programování.
V této části uvádíme jednoduchou grafickou interpretaci lineárních optimalizačních metod. Předkládaná grafická metoda je vhodná pro řešení nejjednodušších problémů lineárního programování; těch, které lze popsat pomocí dvou činností či procesů a matematicky formulovat v uvedeném tvaru. Praktické problémy s tak malým počtem činností snad vůbec neexistují. Přesto považujeme za vhodné se zabývat touto problematikou a graficky vyřešit několik vzorových příkladů. Hlavním cílem této kapitoly je hlubší seznámení studenta se základní filozofií metod lineárního programování, s terminologií, a s ekonomickou interpretací numerického výsledku.
Příklad 4.4
Stanovte výrobní program podniku vyrábějícího dva druhy výrobků (označme je: výrobek A, výrobek B). Výrobní nároky, výrobní kapacity a prodejní podmínky jsou uvedeny dále.
Výrobní proces sestává ze tří operací (odlití, lisování a montáž), přičemž výrobní kapacity podniku jsou následující:
- kapacita slévárny je 80 jednotek A, nebo 100 jednotek B za určité období,
- kapacita lisovny je 200 jednotek výrobku A, nebo 60 jednotek výrobku B za období,
- kapacita montážní linky je 60 jednotek výrobku A a zároveň 80 jednotek výrobku B.
Cena obou typů výrobku (A,B) je kalkulována na částku 28.000.- Kč za jednotku. Pro maximální zjednodušení našeho příkladu neuvažujeme některé další faktory:
- situace na trhu (uvažujeme stejný zájem o výrobek A i B),
- rozdílné ceny surovin, dodací lhůty,
- záměry výzkumu a vývoje v podniku, atd.
Postup:
Formulace matematického modelu :
Uvedený výrobní program popíšeme soustavou dvou proměnných, které vyjadřují, kolik kusů výrobku A a B se bude vyrábět.
Pozn. - v reálné situaci je nutné zvážit typ použité proměnné
REAL, INTEGER (př. nelze vyrábět 26.85 automobilu, ale lze vyrábět 15.68 tun krmné směsi)
počet jednotek výrobku A označíme ........X1 (X1 ≥ 0 )
počet jednotek výrobku B označíme ........X2 (X2 ≥ 0 )
První omezující nerovnost bude vyjadřovat omezení v kapacitě slévárny. Celkovou kapacitu slévárny tedy budeme považovat za 100% a vypočteme procentní podíl potřebný na výrobu jednoho kusu výrobku každého typu. Výroba jednoho kusu výrobku typu A tedy obsadí 100/80 % kapacity slévárny a výroba jednoho kusu výrobku typu B obsadí 100/100 % kapacity slévárny. Vytížení slévárny na výrobu odlitků obou typů nemůže překročit její disponibilní kapacitu. Tímto dostáváme první omezující nerovnost ve tvaru:
100 100 100
------ x1 + ----- x2 ≤ 100 resp ------ x1 + x2 ≤ 100
80 100 80
Analogicky dostáváme nerovnost vyjadřující omezení v rámci kapacity lisovny:
100 100
------ x1 + ------ x2 ≤ 100
60
Další omezující nerovnosti budou vyjadřovat omezení v kapacitě montáže pro výrobek typu A a B:
- pro výrobek typu A: x1 ≤ 60
- pro výrobek typu B: x2 ≤ 80
což ve skutečnosti znamená, že provoz má montážní kapacitu 60 jednotek výrobku typu A a zároveň 80 jednotek výrobku typu B.
Pozn. - je třeba si uvědomit rozdíl mezi obsazením kapacity slévárny a lisovny, kde je použita formulace nebo na rozdíl od montáže, kde je použita formulace a, z tohoto důvodu stojí za povšimnutí, že zatímco v prvních dvou nerovnostech je kapacita vyjadřována v procentech, v dalších je již vyjadřována počtem kusů.
Účelová funkce vyjadřuje celkový výnos produkce ve zvolených jednotkách (např. Kč), jež má dosáhnout maximální hodnoty:
Z = 28.000 x1 + 28.000 x2 ---> MAX
V rámci řešení problému tedy hledáme vektor X = [x1, x2] vyhovující
omezujícím podmínkám:
x1 ≥ 0 (podmínka nezáporné produkce)
x2 ≥ 0 (podmínka nezáporné produkce)
1 1
---- x1 + ---- x2 ≤ 1 (omezená kapacita slévárny,%)
100
1 1
---- x1 + ---- x2 ≤ 1 (omezená kapacita lisovny,%)
200 60

x1 ≤ 60 (omezená kapacita montáže A)
x2 ≤ 80 (omezená kapacita montáže B)
které je nutné doplnit o maximalizující funkci:
Z = 28.000 x1 + 28.000 x2.
Cílem této pasáže je objasnění základních principů lineárního programování na poměrně jednoduchém příkladě. Jelikož použití grafické metody je omezeno na velice jednoduché úlohy a zároveň dosažitelná přesnost je limitována, omezíme se v dalším textu na výklad základních pravidel řešení. Pro tento účel je k dispozici výukový program (LINEARG), který řeší grafickým způsobem úlohy tohoto typu. Tento program naleznete v adresáři C:\OSA\LINEARG\.
Řešení tohoto problému rozdělíme do dvou částí. Nejdříve je to přesná identifikace množiny přípustných řešení, dále potom nalezení optimálního řešení.
Každý bod grafu představuje určitý výrobní program. Množina M všech bodů vyhovujících podmínkám nezápornosti a nerovnosti (S), (l), (m1) a (m2) tvoří pětiúhelník omezený bodem 0,0 a průsečíky omezujících přímek. Množinu M nazýváme množinou přípustných řešení. Každý bod x z množiny M znázorňuje výrobní program, který je uskutečnitelný danou kapacitou (tzv. přípustný výrobní program). Tomuto výrobnímu programu odpovídá konkrétní hodnota x1 a x2, a dále pak celkový výnos (hodnota maximalizující funkce Z).
Body ležící na přímce (s) znázorňují výrobní programy (graficky zobrazené spuštěným programem LINEARG), které beze zbytku vyčerpávají kapacitu slévárny, podobně je tomu v případě lisovny a montáže. Vnitřní body množiny M naproti tomu představují výrobní programy nevyužívající plně disponibilních kapacit.
Ve druhé části postupu, budeme hledat bod x0 v množině M, v němž dosahuje funkce Z maxima. Při tomto postupu využijeme základní větu lineárního programování (zhruba řečeno, pokud existuje optimální řešení, existují i základní řešení).
Skutečně nalezené optimální řešení x0 je vrcholem, a je tedy základním řešením. Postupujeme-li po soustavě rovnoběžek Z, které znázorňují účelovou funkci, směrem od počátku, je zřejmé, že poslední bod, kde se přímka účelové funkce dotýká množiny přípustných řešení, je na hranici této množiny. K nalezení bodu x0 můžeme dojít i analytickou cestou:
- v našem konkrétním případě jej získáme výpočtem z rovnic
x1 x2 x1 x2
---- + ---- = 1 a ---- + ---- = 1.
80 100 200 60
Hledaný vektor: x0 = [42, 105; 47, 368] Z = 2.505.244
Poznámka - kontrola správnosti výsledku:
Z = 28.000 x1 + 28.000 x2
Z = (28.000 * 42,105) + (28.000 * 47,368) = 2.505.244
Uvedený příklad řešil problém, ve kterém se jednalo o nalezení maximální hodnoty účelové funkce. V praxi se však vyskytují i opačné případy, to znamená nalezení minimální hodnoty účelové funkce (např. návrh optimálního složení krmné směsi, složení vsázky do vysoké pece, atd.). Tyto úlohy jsou řešeny téměř identickým způsobem:
- identifikace množiny přípustných řešení M,
- nalezení bodu x0 z množiny M pomocí soustavy rovnoběžek (pozor, v případě optimálního řešení je vzdálenost bodu x0 od počátku nejmenší).
X2
100 (s ) x 1 = 60
x 2 = 80
80

60

Xo

M
25 ( l )


25 60 80 200 X1
z = 700 000 z = 2 505 244


Obr. 4.1. Grafické řešení LP problému – příklad 4.4.
Příklad 4.5
Grafickým způsobem určete výrobní program, který zajistí maximální hodnotu produkce podniku vyrábějícího dva druhy výrobků A a B. Výroba je omezena zásobami surovin. Pro zjednodušení neuvažujte vedlejší vlivy a omezení výroby, situaci na trhu, atd.

Surovina Spotřeba suroviny na jednotku Zásoba suroviny
výrobku A výrobku BS1 3 jednotky 5 jednotek 150 jednotek
S1