Lineární programování

24.9.2015

Lineární programování Radim Farana Podklady pro výuku pro akademický rok 2013/2014

Obsah Úloha lineárního programování. Formulace úlohy lineárního programování. Typické úlohy lineárního programování.

Literatura: JABLONSKÝ, Josef. Operační výzkum: kvantitativní metody pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007, 323 s. ISBN 978-80-86946-44-3.

Formulace úlohy lineárního programování 1. Stanovení cíle analýzy. 2. Identifikace rozhodovacích proměnných (xi), určení jejich počtu, významu, fyzikálního rozměru. 3. Definice optimalizačního kritéria, určení účelové funkce, stanovení cenových koeficientů. 4. Identifikace činitelů modelu. Stanovení omezujících podmínek.

1

24.9.2015

Typické úlohy lineárního programování Úlohy výrobního plánování. Úlohy finančního plánování. Plánování reklamy. Nutriční problém. Směšovací problém. Úloha dělení materiálu. Rozvrhování pracovníků. Distribuční úlohy lineárního programování.

Úlohy výrobního plánování nebo také problém alokace zdrojů. Cílem je maximalizace zisku nebo minimalizace nákladů na výroku při omezených zdrojích (lidských, materiálových, spotřeby energie, …) současně mohou být stanoveny minimální rozsahy výroby pro splnění již uzavřených zakázek.

Příklad 1 Firma vyrábí stůl a dva druhy židlí při omezeném množství dřeva a dostupném fondu pracovní doby Výrobek Dřevo [kg/ks] Práce [hod/ks]

noha k noha ke židli stolu 0,30 0,80 0,25 0,40

stůl 5,00 2,00

židle 1

židle 2

1,50 1,50

2,00 2,50

Stůl vyžaduje 4 nohy, židle 1 vyžaduje 4 nohy, židle 2 jen 2.

2

24.9.2015

Příklad 1  Dřeva je k dispozici 20 000 kg fond pracovní doby činí 12 000 hod.  Stůl se prodává za 8.000,- Kč, židle 1 za 1.200,- Kč, židle 2 za 1.800,- Kč, zbylé nohy je možno prodat: noha k židli za 50,- Kč, noha ke stolu za 120,- Kč.  Kromě samostatných výrobků se také prodává komplet stůl + 4 židle 2 za 14.900,- Kč. Těchto kompletů musí být vyrobeno nejméně 200 ks.

Formulace matematického modelu Úloha obsahuje 6 procesů, dva polotovary, tři výrobky a komplet, jejich počty určí proměnné x1, …, x6. Vzhledem ke spotřebě polotovarů bude účelová funkce: 50( x1  4 x4  2 x5 )  120( x2  4 x3 )  8000( x3  x6 )  z  max    1200 x4  1800( x5  4 x6 )  14900 x6 

z  max50 x1  120 x2  7520 x3  1000 x4  1700 x5  300 x6 

Omezující podmínky Spotřeba dřeva: 0,3x1  0,8x2

 5x3

 1,5x4

 2 x5

 1,5x4

 2,5x5

 20000

Spotřeba práce: 0,25x1  0,4 x2

 2 x3

 12000

Spotřeba polotovarů: 4 x4 4 x3

 2 x5

 x1  x2

3

24.9.2015

Omezující podmínky Je třeba zajistit výrobu kompletů:  x6

x3

 4x6

x5

Minimální počet kompletů x6

 200

Podmínky nezápornosti a celočíselnosti.

Řešení

Řešení pomocí MS-Excel

4

24.9.2015

Výsledek řešení

Výsledková sestava


5

24.9.2015

Úlohy finančního plánování nebo také optimalizace portfolia. Cílem je určit objem financí do jednotlivých investičních variant s cílem optimalizovat výnos případně minimalizovat riziko. Proměnnými jsou výše investic, omezení odpovídají investiční strategii, např. limitům investic do jednotlivých typů investičních variant.

Příklad 2 Investor se rozhodl investovat určitou částku do možných investic s očekávaným výnosem a rizikovým koeficientem: Investice Akcie A Akcie B Pokladniční poukázky Dluhopis A Dluhopis B Depozitní certifikáty

očekávaný rizikový výnos [%] koeficient 18,00 10 12,00 7 6,50 1 8,50 3 9,25 5 8,00 2

Příklad 2  Riziko vyjádřené váženým součtem rizikových koeficientů nesmí být vyšší než 5 (čím vyšší hodnota, tím vyšší riziko)  Do dluhopisů musí být investováno nejméně 40 % částky.  Pokladniční poukázky musí být nakoupeny alespoň dvojnásobně proti objemu akcií.  Podíl každé varianty nesmí přesáhnout 30 %.  Cílem je maximalizovat výnos při dodržení této investiční strategie.

6

24.9.2015

Formulace matematického modelu Úloha obsahuje 6 procesů jejich podíl na celku (100 %) určí proměnné x1, …, x6. Vzhledem k očekávaným výnosům bude účelová funkce: z  max0,18x1  0,12 x2  0,065x3  0,085x4  0,0925x5  0,08x6 

Omezující podmínky Celková investovaná částka: x1  x2

 x3

 x4

 x5

 x6

 100

Nejméně 40 % do dluhopisů: x4

 x5

 40

Pokladniční poukázky alespoň dvojnásobně oproti akciím: 2 x1  2 x2

 x3

Omezující podmínky Celková míra rizika není větší než 5: 10 x1  7 x2  1x3  3x4  5 x5  2 x6 5 x1  x2  x3  x4  x5  x6

Po úpravě:

5x1  2 x2  4 x3  2 x4  3x6  0

Maximální podíl každé investice do 30 %: x j  30, j  1, 2, ..., 6

Podmínka nezápornosti: x j  0, j  1, 2, ..., 6

7

24.9.2015

Řešení


Výsledek řešení

8

24.9.2015



Citlivostní sestava

9

24.9.2015

Limitní sestava

Plánování reklamy neboli media selection problem. Alokace rozpočtu na reklamu do jednotlivých médií, případně konkrétního časového okna. Proměnné mohou být počet opakování reklamy v daném médiu, omezující podmínky vychází z omezeného rozpočtu, definice cílové skupiny, reklamní strategie.

Příklad 3 Reklamní agentura má naplánovat reklamní kampaň za 10 mil. Kč. K dispozici je 5 médií – televize, rozhlas, časopisy, noviny a billboardy. Podle zkušeností vede 1.000 Kč investované do příslušných médií zapůsobí na 750, 420, 300, 360 a 180 osob.

10

24.9.2015

Příklad 3 Zadavatel stanovil podmínky: do TV a rozhlasu nelze umístit více než 50 % rozpočtu, do každého z médií musí být umístěno alespoň 10 % rozpočtu, do žádného z médií nelze umístit více než 30 % rozpočtu, musí být osloveno alespoň 2,5 mil. osob věku 30 ÷ 50 let, 0,8 mil. osob s příjmem nad 15.000,- Kč, 1,5 mil. osob s nejméně středoškolským vzděláním.

Příklad 3 Vliv jednotlivých médií: Druh média věk 30 - 50 let příjem > 15.000,- Kč SŠ vzdělání

TV 320 120 350

rozhlas časopisy noviny billboardy počet osob na 1.000,- Kč 280 140 240 120 90 60 60 50 200 120 140 60

Formulace matematického modelu  Proměnné odpovídají objemu vynaložených prostředků pro jednotlivá média.  Účelová funkce maximalizuje celkový vliv reklamy z  max720 x1  420 x2  300 x3  360 x4  180 x5 

11

24.9.2015

Omezující podmínky Celkový rozpočet reklamy: x1  x2

 x3

 x4

 x5

 10

Do TV a rozhlasu umístit nejvýše 5 mil.: x1  x2

 5

Pro každé médium nejméně 1 mil.: x j  1, j  1, 2, ..., 5

Omezující podmínky Pro každé médium nejvýše 3 mil.: x j  3, j  1, 2, ..., 5

Podmínky pro věk, příjem a vzdělání: 320 x1  280 x2

 140 x3

120 x1  90 x2 350 x1  200 x2

 240 x4

 60 x3  120 x3

 120 x5

 2500

 60 x4

 50 x5

 800

 140 x4

 60 x5

 1500

Řešení

12

24.9.2015


Výsledek řešení


13

24.9.2015



Limitní sestava

14

24.9.2015

Nutriční problém nebo také úloha o výživě. Problém návrhu denní dávky výživy pro konkrétní osobu. Proměnnými jsou množství jednotlivých komponent s různým složením. Omezení stanovují množství jednotlivých výživových komponent.

Příklad 4 Studenti chtějí zajistit nutričně vyváženou stravu pomocí produktů nejmenovaného rychlého občerstvení s nabídkou 9 produktů. Cílem je co nejlevnější skladba potravin splňujících určené nutriční požadavky.

Příklad 4 Požadavky: energetická hodnota minimálně 3000 kcal, obsah bílkovin minimálně 65 g, obsah uhlohydrátů minimálně 375 g, obsah tuků maximálně 120 g, každou z potravin je možno použít nejvýše dvakrát.

15

24.9.2015

Příklad 4 Nutriční hodnoty potravin Produkt Big Mac Hamburger 1/8 Zeleninový burger Hranolky Salát Mléko Coca cola Big Mac menu Hamburger menu

Energie [kcal] Bílkoviny [g] 479 517 341 425 54 120 184 1202 1240

25 32 12 5 4 9 0 31 39

Tuky [g] 22 25 11 21 2 4 0 49 52

Uhlohydráty [g] 44 40 50 54 5 12 46 158 155

Cena [Kč] 49 45 39 15 29 15 19 89 75

Formulace matematického modelu  Proměnné odpovídají počtům jednotlivých potravin, bude jich tedy 9.  Účelová funkce minimalizuje náklady na stravu: z  min49 x1  45x2  39 x3  15x4  29 x5  15x6  19 x7  89 x8  75x9 

Omezující podmínky Energetická hodnota: 479 x1  517 x2  341x3  425x4  54 x5  120 x6  184 x7  1202 x8  1240 x9  3000

Obsah bílkovin: 25x1  32 x2  12 x3  5x4  4 x5  9 x6  31x8  39 x9  65

Obsah tuků: 22 x1  25x2  11x3  21x4  2 x5  4 x6  49 x8  52 x9  120

16

24.9.2015

Omezující podmínky Obsah uhlohydrátů: 44 x1  40 x2  50 x3  54 x4  5x5  12 x6  46 x7  158x8  155x9  375

Každý produkt je možno koupit nejvýše dvakrát, po celých kusech: x j  2, j  1, 2, ..., 9 x j  0, j  1, 2, ..., 9

x j  celé , j  1, 2, ..., 9

Řešení


17

24.9.2015

Výsledek řešení



18

24.9.2015

Směšovací problém Cílem je vytvoření směsi požadovaného složení. Proměnnými jsou množství jednotlivých použitelných komponent s minimalizací jejich ceny. Omezením jsou požadovaná množství jednotlivých přísad.

Příklad 5 Máme vyrobit slitinu, která bude obsahovat 40 % cínu, 35 % zinku a 25 % olova. Můžeme využít slitiny A, B, C, D a E, známého složení a ceny za kg. Cílem je nejlevnější skladba komponent. Zvolíme množství 100 Kg, což nám umožní dobře spočítat procenta složek.

Příklad 4 Vlastnosti dostupných komponent Komponenta Obsah Sn [%] Obsah Zn [%] Obsah Pb [%] cena [Kč/kg]

A 60 10 30 22

B 25 30 45 20

C 45 45 10 41

D 40 50 10 37

E 50 20 30 27

19

24.9.2015

Formulace matematického modelu  Proměnné odpovídají množství jednotlivých komponent, bude jich tedy 5.  Účelová funkce minimalizuje náklady na slitinu:

z  min22 x1  20 x2  41x3  37 x4  27 x5 

Omezující podmínky Množství směsi: x1  x2  x3  x4  x5  100

Obsah cínu: 0,60 x1  0,25x2  0,45x3  0,40 x4  0,50 x5  0,40( x1  x2  x3  x4  x5 ) 0,20 x1  0,15x2  0,05x3  0,10 x5  0

Omezující podmínky Obsah zinku: 0,10 x1  0,30 x2  0,45x3  0,50 x4  0,20 x5  0,35( x1  x2  x3  x4  x5 )  0,25x1  0,05x2  0,10 x3  0,15x4  0,15x5  0

Obsah olova: 0,30 x1  0,45x2  0,10 x3  0,10 x4  0,30 x5  0,25( x1  x2  x3  x4  x5 ) 0,05x1  0,20 x2  0,15x3  0,15x4  0,05x5  0

Podmínka nezápornosti: x j  0, j  1, 2, ..., 5

20

24.9.2015

Řešení


Výsledek řešení

21

24.9.2015



Limitní sestava

22

24.9.2015

Úloha dělení materiálu Problémem je minimalizace nákladů na výrobu stanoveného množství dílů z delších tyčí. Každou tyč je možno použít více způsoby, proměnnými jsou počty těchto použití. Omezení udávají počty dostupných tyčí a počty výsledných dílů.

Příklad 6 Firma nakupuje traverzy délky 5,5 metrů a potřebuje traverzy: 3 metry – nejméně 1 000 ks, 2,2 m – nejméně 1 700 ks, 1,4 m – nejméně 2 000 ks.

Cílem firmy je vyrobit požadované počty traverz tak, aby celkový odpad v metrech byl minimální (nebo spotřeba materiálu byla minimální).

Řezná schémata Způsob dělení 3m 2,2 m 1,4 m Odpad [m]

1 1 1 0 0,3

2 1 0 1 1,1

3 0 2 0 1,1

4 0 1 2 0,5

5 0 0 3 1,3

23

24.9.2015

Formulace matematického modelu  Proměnné odpovídají množství jednotlivých řezných plánů, bude jich tedy 5.  Účelová funkce minimalizuje odpad:

z  min0,3x1  1,1x2  1,1x3  0,5x4  1,3x5   V případě minimalizace spotřeby materiálu:

z  minx1  x2  x3  x4  x5 

Omezující podmínky Požadavek na traverzy 3 m: x1  x2  1000

Požadavek na traverzy 2,2 m: x1  2 x3  x4  1700

Požadavek na traverzy 1,4 m: x2  4 x4  3x5  2000

Podmínka nezápornosti a celočíselnosti.

Řešení

24

24.9.2015


Výsledek řešení


25

24.9.2015


Rozvrhování pracovníků Rozvrhování pracovníků na směny má řadu omezujících podmínek, požadavky na počty pracovníků, jejich kvalifikaci apod. Proměnné udávají zda pracovník na směnu jde nebo ne (1 – 0).

Příklad 7 Máme za úkol rozdělit kolektiv do dvojic. Kvalita volby pro každou dvojici byla vyjádřena body 1 ÷ 10: Kvalita spolupráce P1 P2 P3 P4

P2 9

P3 3 1

P4 4 7 4

26

24.9.2015

Formulace matematického modelu  Proměnné odpovídají jednotlivým dvojicím: x12, …, x1n, x23, …, x2n, …, xn-1n. Celkově je jich tedy  n   4  4!       6  k   2  2!.2!

 Účelová funkce maximalizuje součet součinů cena*proměnná: z  max   c x n 1

n

i 1 j i 1

ij ij

z  max9 x12  3x13  4 x14  1x23  7 x24  4 x34

Omezující podmínky Celkový počet dvojic: x12  x13  x14  x23  x24  x34  2

Každá osoba může být zapojena jednou: x12  x13  x14  1 x12  x23  x24  1 x13  x23  x34  1 x14  x24  x34  1

Všechny proměnné binární (0, 1)

Řešení

27

24.9.2015


Výsledek řešení


28

24.9.2015

Distribuční úlohy lineárního programování Jedná se o optimalizaci distribuce zboží mezi dodavateli a odběrateli. Tyto úlohy mají poněkud odlišnou strukturu a věnují se jim speciální metody.

29

Lineární programování

Recommend Documents