Lineární programování

Lineární programování Úlohy LP patří mezi takové úlohy matematického programování, ve kterých jsou jak kriteriální funkce, tak i všechny rovnice a nerovnice podmínek výhradně tvořeny lineárními výrazy. To znamená:  všechny proměnné se vyskytují pouze v první mocnině,

 nejsou argumentem žádné funkce,  nesmí se násobit mezi sebou.

Fáze aplikace lineárního programování 1. Vytvoření ekonomického modelu (činnosti, činitele, strukturní koeficienty, kritérium optimality).

2. Sestavení matematického modelu. 3. Řešení matematického modelu. 4. Ekonomická interpretace výsledků řešení matematického modelu.

Vztah mezi ekvivalenty matematického a ekonomického modelu Matematický model

proměnné

x1, x2, ………. , xn

Ekonomický model

úroveň hospodářských činností

a11, a12, …….. , amn koeficienty strukturní koeficienty c1, c2, ……….., cn konstanty

b1, b2, ……..…, bm

proměnná

z

disponibilní množství zdrojů nebo požadované množství výsledků hodnota kriteriálního ukazatele

Rozdělení metod lineárního programování Podle rozsahu použití:  univerzální metody,  speciální metody. Podle stupně přesnosti:  přesné,  přibližné (aproximační).

Základní typy úloh lineárního programování  úlohy výrobní (sortimentní, kapacitní),

 úlohy dopravní,

 úlohy směšovací,  úlohy rozmísťovací (přiřazovací),  úlohy minimalizující odpad.

Formulace matematického modelu 1. Analýza ekonomického modelu – činnosti, zdroje, výsledky činností, kritérium optimality. 2. Stanovení proměnných – věcný význam a rozměrová charakteristika.

3. Vyjádříme lineárními rovnicemi a nerovnicemi omezení úlohy: 

pravá strana: omezené disponibilní množství vstupujícího činitele,



levá strana: potřebné množství vstupujícího zdroje nebo produkované množství vystupujícího činitele, vždy ve formě lineární funkce.

4. Vyjádříme kritérium optimality lineární funkcí.

Úloha LP ve standardní formě Nalézt optimum (maximum nebo minimum) funkce: z = c1x1 + c2x2 + …….. + cnxn … max (min) kriteriální (účelová) funkce za podmínek: a11x1 + a12x2 + ……….. + a1nxn <=> b1 a21x1 + a22x2 + ……….. + a2nxn <=> b2 …………………………………………………………..

omezující podmínky

…………………………………………………………..

am1x1 + am2x2 + ………. + amnxn <=> bm xj  0 , kde j = 1, …………, n

podmínka nezápornosti

Výrobní problém Nalézt takový výrobní program, s nímž je spojen maximální efekt (zisk, hodnota výroby) nebo minimální náklady (pracnost). Omezení:  limitující zdroje (pracovní síly, suroviny, energie, kapacity zařízení),  limitující požadavky (odbytové, finanční). Omezení mohou být shora nebo zdola, mohou mít též povahu rovností.

Dopravní problém

Určení takového plánu přepravy homogenní (vzájemně zastupitelné) produkce od skupiny dodavatelů ke skupině odběratelů tak, aby celkové přepravní náklady byly minimální.

Označení použitých veličin Di

dodavatelé (i = 1, 2, …, m)

Sj

spotřebitelé (j = 1, 2, …, n)

ai

kapacity dodavatelů

bj

požadavky spotřebitelů

cij

cena za přepravu jednotky produktu od Di k Sj

xij

objem přepravovaného produktu od Di k Sj

Ekonomický model dopravního problému

D2

x21

Spotřebitelé S2 … c12 x12 … c22 x22 …

…

…

…

Dodavatelé

S1 c11

D1

x11 c21

cm1 Dm Požadavky spotřebitelů

xm1 b1

… cm2

xm2 b2

… …

Kapacity dodavatelů

Sn c1n

x1n

a1 c2n

x2n

a2

…

… cmn

xmn bn

am

Vyrovnaný dopravní problém

m

n

i 1

j1

ai   b j

Řádková omezení x11 + x12 + ………. + x1n = a1 x21 + x22 + ………. + x2n = a2

……………………………… xm1 + xm2 + ……… + xmn = am

Sloupcová omezení x11 + x21 + ………. + xm1 = b1 x12 + x22 + …….… + xm2 = b2 ……………………………… x1n + x2n + ………. + xmn = bn

Podmínka nezápornosti řešení xij  0 Kriteriální funkce: z = x11c11 + x12c12 + … + xmncmn … min

Nevyrovnaný dopravní problém m

n

i 1

j1

m

n

ai   b j

ai   b j

i 1

 fiktivní spotřebitel

 fiktivní dodavatel

j1

Dále se postupuje jako u vyrovnaného dopravního problému.

Problém nepoužitelnosti některé komunikace

Jestliže některou komunikaci nelze použít, uvede se do odpovídajícího políčka místo skutečné ceny za přepravu cena prohibitivní (velmi vysoká). Tato cena při dalším matematickém řešení problému zajistí, že daná komunikace nebude obsazena.

Nezastupitelné dodávky Určitý spotřebitel musí odebrat od určitého dodavatele jisté množství produktu. Velikost tohoto produktu se odečte jak od celkové velikosti kapacit dodavatelů, tak i od celkové velikosti požadavků spotřebitelů. Kriteriální funkce:

m n

z    c ij x ij  c nd x nd i 1 j1

Řešení matematického modelu Rozlišujeme:  přípustné řešení

základní přípustné řešení optimální řešení

Přípustné řešení je takové řešení soustavy lineárních rovnic, které vyhovuje všem podmínkám úlohy. Množina přípustných řešení může být prázdná, omezená, neomezená nebo otevřená.

Základní řešení

je přípustné řešení, které má nejvýše tolik kladných složek, kolik je lineárně nezávislých rovnic tvořících vlastní omezení (tj. v našem případě nejvýše m kladných složek a nejméně n – m nulových složek za předpokladu, že n > m).

Optimální řešení

je základní přípustné řešení s nejlepší hodnotou účelové funkce (v případě maximalizace s nejvyšší, v případě minimalizace s nejnižší hodnotou).

Základní věta lineárního programování

Má-li úloha lineárního programování optimální řešení, má také základní přípustné řešení.

Počty řešení úlohy lineárního programování 1. Úloha nemá optimální řešení. 2. Úloha má jediné optimální řešení.

3. Úloha má nekonečně mnoho optimálních řešení (se stejnou hodnotou kriteriální funkce). 4. Účelová funkce může na množině přípustných řešení neomezeně růst nebo neomezeně klesat.

Grafické řešení úloh LP

Lze použít pouze při řešení nejjednodušších úloh, v nichž se vyskytují dvě proměnné a vlastní omezení jsou vyjádřena nerovnostmi.

Postup řešení 1. Sestrojíme oblast přípustných řešení. 2. Na množině přípustných řešení hledáme maximum (minimum) kriteriální funkce. 3. Dosadíme-li za z různé hodnoty, dostaneme soustavu rovnoběžných přímek. 4. Z této soustavy vybereme přímku, která má s množinou přípustných řešení alespoň jeden společný bod a je přitom nejdále od počátku (při hledání maxima), resp. nejblíže počátku (při hledání minima).

Příklad Balírny čaje plánují v následujícím období výrobu dvou čajových směsí – lesní směs a ovocný čaj. Pro výrobu obou směsí mají k dispozici od dodavatelů 4 000 kg drcených šípků, 600 kg květu ibišku, 350 kg černého rybízu a 200 kg ostružin. Složení obou směsí je uvedeno v tabulce (v kg na 1 000 balení čaje). Zisk z prodeje 1 000 balení lesní směsi je 2 000 Kč, ovocného čaje 1 300 Kč.

Složení směsí čaje Složka

Lesní směs

Ovocný čaj

Drcený šípek

30

35

Květ ibišku

7

4

Černý rybíz

2

1

Ostružina

1

0

Matematický model úlohy 30 x1  35x 2  4000 7 x1  4 x 2  600 2 x1  x 2  350 x1  200 x1  0 x2  0 z  2000 x1  1300 x 2

Grafické řešení úlohy x2

x1

Optimální řešení úlohy x1 = 40 tis. ks x2 = 80 tis. ks z = 184 000 tis. Kč

Čerpání surovin: šípek: 30 * 40 + 35 * 80 = 4 000 kg ibišek: 7 * 40 + 4 * 80 = 600 kg černý rybíz: 2 * 40 + 1 * 80 = 160 kg (rezerva 190 kg) ostružiny: 1 * 40 = 40 kg (rezerva 160 kg)

Analýza citlivosti Umožňuje zjistit, jaký vliv mají změny omezujících podmínek na optimální řešení. Např. v našem příkladu nebyly zcela vyčerpány dvě složky – černý rybíz a ostružiny. Výrobu však nelze zvýšit, protože první dvě složky byly zcela spotřebovány. Bylo by pro firmu výhodné nakoupit dodatečné množství např. šípku? Pokud ano, jak velké množství?

Změna objemu produkce Jestliže balírny získají navíc 1 kg drcených šípků, změní se optimální řešení následovně:

30x1  35x 2  4001 7 x1  4x 2  600

x1  39,968 x 2  80,056 Rohový bod reprezentující optimální řešení se posune nepatrně směrem vlevo nahoru.

Grafické řešení úlohy x2

x1

Změna zisku z  2 000.39,968  1 300.80,056  184 008,8 Kč Jestliže firma zvýší dodatečně množství šípků o 1 kg, hodnota zisku vzroste o 8,80 Kč.  marginální výnos (stínová cena) – ukazuje, jaký vliv má jednotková změna omezujících podmínek na hodnotu kriteriální funkce.

Přípustný rozsah změny S postupným zvyšováním dodávek drcených šípků se bude postupně měnit i oblast přípustných řešení. V určitém okamžiku nastane nová situace, kdy se některá z dalších omezujících podmínek stane podmínkou vyčerpávající a naopak omezující podmínka pro drcený šípek již vyčerpávající nebude. Z grafu vyplývá, že tímto novým omezením se stane ibišek, tj. bod x1 = 0, x2 = 150.

Horní mez pro šípek

Kombinace x1 = 0, x2 = 150 bude vyžadovat 35 * 150 = 5 250 kg drcených šípků.

Stínová cena ibišku 30 x1  35x 2  4000 7 x1  4x 2  601

x1  40,28 x 2  79,76 z  2 000.40,28  1 300.79,76  184 248 Kč Stínová cena ibišku je 248 Kč. Z ekonomického hlediska je výhodnější využít možnost vyšších dodávek ibišku.

Horní mez pro ibišek

Maximální možné optimální řešení se objeví v bodě x1 = 133,33 a x2 = 0. Tato kombinace vyžaduje: 7 * 133,33 = 933,33 kg ibišku.

Grafické řešení úlohy x2

x1

Rekapitulace – citlivost omezení Stínová cena

Disponibilní množství

8,80

Květ ibišku

Omezení

Přípustný rozsah změny od

do

4000

2571,429

5250,000

248,00

600

457,143

933,333

Černý rybíz

0,00

350

160,000



Ostružiny

0,00

200

140,000



Drcený šípek

Citlivost kriteriální funkce Proměnná

Optimální Kriteriální hodnota koeficient

Přípustný rozsah změny od

do

x1

40

2 000

1114,286

2275,000

x2

80

1 300

1142,857

2333,333

Cena lesní směsi se může pohybovat mezi 1114 až 2275 Kč, resp. ovocného čaje od 1143 do 2333 Kč, aniž by došlo ke změně optimálního řešení x1 = 40, x2 = 80.