OPVP přednášky, cvičení Fábry Úvod do operačního výzkumu ... KOMPLET.pdf · a) Výroba...

OPVP – přednášky, cvičení - Fábry

1

Úvod do operačního výzkumu Operační výzkum = Výzkum operací. OV je výzkum systémů samostatných disciplín. Vojenské, strategické a taktické opce. Po skončení války přesun do ekonomie, řešení stavebních a výrobních opcí. Díky počítačům se neřešitelné úlohy staly řešitelnými. Operační výzkum-souhrn disciplín, zabývajících se řešením různých tříd rozhodovacích problémů.

Model = z hlediska OV je zjednodušený obraz nějakého reálného systému – zjednodušení reality (realitou myslíme např. podnik). Není dobré udělat přesný, příliš složitý model – pak nelze použít žádné řešení. Příliš jednoduchý model nelze použít na realitu. Při tvorbě modelu dbáme na: řešitelnost a způsob Optimalizace = pomocí modelu hledáme optimální řešení, strategii např. optimální výrobní program. Optimální řešení = nejlepší řešení. V množině řešení najít to nejlepší řešení, množina je daná omezením – tím, co nás v řešení omezuje. Fáze řešení rozhodovacího problému:

EM – si my musíme vymyslet sami EM – 3 výrobky X1 = počet vyrobených židlí X2= počet vyrobených křesel X3= počet vyrobených stolů Řešení: X1 = 700 X2= 500 X3= 200

Když vyjde desetinné číslo, není to reálný výsledek, nemůžu říct šéfovi, vyrábět 700,988 židlí.


2

V podmínkách je nutné definovat zaokrouhlování na celá čísla.

zjištění závislosti věku a výšky, nutnost vstupů – dat

Teorie Grafů Euler – pan Město, řeka, vedlo tam 7 mostů Úloha zněla – z libovolného místa projít po každém městě jen jednou a zase se vrátit zpět do výchozího místa. Připomíná to domeček jedním tahem.

Uzly Hrany Uzel stupně č. 3 – vychází z něj 3 hrany Teorie uzlů a hran – z každého uzlu vychází určitý počet hran. Aby šlo nakreslit jedním tahem, musí být jen dva uzly lichého stupně a ostatní sudého, pokud jsou právě dva uzly lichého stupně a ostatní sudého, lze obrazec kreslit jedním tahem. Pokud jsou dva uzly lichého stupně a ostatní sudého, lze obrazec kreslit jedním tahem, musí se začít v uzlu lichého stupně a v tom druhém uzlu lichého stupně skončíme. Říká se tomu Eulerův tah.

Eulerův cyklus (kružnice) – všechny uzly mají sudý počet hran. Vždy lze nakreslit jedním tahem. Počet hran se rovná počtu čar, které z uzlu vychází. Úloha čínského listonoše


3

Lineární programování

= základ OV Př. 1 - Pekárna Pekárna vyrábí housky a chleba. Suroviny – mouka, vejce, sůl, kmín. Soli a kmínu je dostatek. Vajec jen 3000 ks na den, mouky 1500 kg/den. Na výrobu 10ti housek je třeba 1kg mouky a 4 vejce. Na chleba je třeba 2 kg mouky a 3 vajíčka. Zisk z 1 housky je Kč 1,10 a z chleba je 10 Kč. Navrhněte výrobu tak, aby Z z prodaného pečiva byl maximální. Vše co vyrobíme i prodáme. (toto je EM) EM - vždy hledáme:

1) Cíl analýzy – maximalizace celkového denního zisku 2) Procesy – 2 procesy

a) Výroba housek b) Výroba chleba

3) Činitele – mouka, vajíčka

MM (vychází z EM): Když něco maximalizuji tzn. hledáme extrém (max., min.) fce.

1) Účelová (cílová) fce = lineární, musíme specifikovat, zda hledáme minimum nebo maximum tzn. a) maximalizační

b)minimalizační 2) Proměnná : x1, X2 3) Omezení (omezující podmínky) :

a) Lineární rce = b) Lineární nerovnice: ≤, ≥

Krok č. 1: Začínáme vždy proměnnými: x1 – počet vyrobených housek v desítkách ks/den X2 – počet vyrobených chlebů za den Pozn.

X1 = počet vyrobených housek v 10 ks za den (zisk je 11 Kč) X2 = počet vyrobených chlebů za den (zisk je 10 Kč)

Krok č. 2 účelová fce: Definice fce má vyjadřovat celkový zisk. Z= 11 X1 + 10 X2 max. Krok č. 3: Omezení: 1 X1 + 2 X2 ≤ 1500 kg/ den mouka 4 X1 + 3X2 ≤ 3000 ks/ den Vejce X1, X2 ≥ 0 Pozn. Když to bude týden, tak budeme dělit 1500/7mi nebo 5ti.


4

Lineární programování – definice ze skript

Lineární programování – disciplína operačního výzkumu, která se zabývá řešením rozhodovacích problémů. Musí se zde respektovat určité podmínky a najít řešení, při kterém je cíl splněn co nejlépe. Programování je synonymem pro plánování programů, lineární vyjadřuje, že všechny vazby v modelech jsou vazbami lineárními tzn. že matematické fce jsou fce lineární. V úlohách lineárního programování se vyskytují 2 základní modely:

1. Ekonomický model – vyjádření rozhodovacího problému formou jeho slovního, případně číselného popisu.

2. Matematický model – matematická formalizace ekonomického modelu rozhodovacího problému. Obsahuje n - počet strukturních proměnných v modelu, m - počet vlastních omezení, cj, j=1,2,..n – cenové koeficienty, bi, i=1,2,..m – hodnoty pravých stran, aij, j=1,2,..n, i=1,2,..m tzv. strukturní koeficienty, podmínky

Stupně řešení úloh lineárního programování: Základní řešení – každé základní řešení ekvivalentní soustavy rovnic, které vyhovuje

podmínkám nezápornosti; má maximálně tolik nenulových proměnných, kolik je lineárně nezávislých řádků této soustavy.

Přípustné řešení – řešení, které splňuje všechny omezující podmínky modelu, tj. soustavu vlastních omezení i podmínky nezápornosti

Optimální řešení – nejlepší ze všech přípustných řešení Fáze řešení rozhodovacího procesu 1) rozpoznání problému v rámci systému a jeho definice 2) formulace ekonomického modelu – cíl analýzy (max. zisk), popis procesů (výroba), popis činitelů (spotřeba omezujících zdrojů), popis mezi procesy a činiteli a cílem analýzy 3) matematický model – obsahuje stejné prvky jako ekonomický model 4) řešení matematického modelu 5) interpretace a verifikace výsledků 6) implementace


5

1.10.2009

Lineární programování - pokračování

Cílem je najít optimální výrobu z hlediska zisku. Chceme dosáhnout co největšího celkového zisku. Grafické řešení Př. č. 1 - Pekárna v lineárním programování

10 housek 1 chleba Zásoba

Mouka 1 2 1500 Kg

Vejce 4 3 3000 Ks

Zisk 11 10 MAX

Matematický model: 1. Proměnné:

x1 – počet housek vyrobených za jeden den (v desítkách) x2 – počet chlebů vyrobených za jeden den

2. Omezení:

a. vlastní omezení modelu:

x1 + 2x2 ≤ 1500 (na spotřebu mouky) 4x1 + 3x2 ≤ 3000 (na spotřebu vajec)

b. podmínky nezápornosti:

x1, x2 0

3. Účelová funkce: 11x1 + 10x2 → MAX Zápis modelu:

x1 – počet housek vyrobených za jeden den (v desítkách) x2 – počet chlebů vyrobených za jeden den

x1 + 2x2 ≤ 1500 4x1 + 3x2 ≤ 3000

x1, x2 0 z = 11x1 + 10x2 → MAX Řešení: x1 = 300, x2 = 600, z = 9300


6

Pro zjištění správné poloroviny musíme zjistit jakýkoli bod mimo přímku a dosadit do

rovnice, musí vyhovovat.

Uvnitř trojúhelníku jsou takové hodnoty, které vyhovují první omezující podmínce. 1500 kg

mouky stačí na všechny body uvnitř poloroviny.

Body v druhém trojúhelníku vyhovují druhé omezující podmínce. Hledáme body, které

vyhovují oběma podmínkám – průnik! – polorovin je o co nás zajímá, nazýváme tuto

množinu, množina přípustných řešení. Souřadnice bodů nám dávají přípustný výrobní

program – cílem je stále maximalizace zisku. Musíme dostat účelovou funkci – obrazem

účelové funkce je rovina procházející počátkem a odklánějící se nahoru od papíru, papír

zvednutý nad tabuli!! Kolmý průmět roviny do papíru – dostaneme přímku, všechny body na

této přímce odpovídají hodnotě zisku.

Zakreslením rovnice 11 x1 + 10 X2 = 11.10 jsme zjistili pořád stejnou hodnotu zisku rovna

110.

Přímka procházející bodem 0 ukazuje zisk 0. Nemá cenu se zabývat body, kde není žádný

zisk, chceme maximalizaci zisku. Budeme se pohybovat dál od osy x a y. Vynásobím si čísla

stejnými násobky a dostanu se dál od os.

Posouvám přímku do té doby ve stejném úhlu, dokud se nedotýká množiny přípustných

řešení, tím maximalizuji zisk. Násobím, dokud se nedostanu nakonec množiny přípustných

řešení.

Cílem je zjištění kolik se bude vyrábět, nikdy ne z grafu pomocí pravítka!!, musíme dopočítat

bod, který splňuje obě rovnice najednou – soustava dvou rovnic a dvou neznámých.

X1 + 2X2 = 1500 (vynásobím -4)

4X1 + 3X2 = 3000

5X2 = 3000

X2 = 600 – každý den se bude vyrábět 600 chlebů

X1 = 300 musíme vynásobit 10 – tzn. každý den se bude vyrábět 3000 housek

Déle musíme spočítat zisk – dosadíme hodnoty X1 a X2 do funkce:

Zo = 11x300 + 10x600 = 9300 Kč/ den

Musíme zjistit, jestli nám nezbývá nějaká mouka nebo vejce – dosazením do rovnic. V tomto

případě spotřebujeme vše.

DCV: Zakreslit účelovou fci:


7


8

Směšovací úloha

Míchají se tam dohromady nějaké látka – barvy, oleje, krmivo tak, abychom získali nějakou výslednou směs

s požadovanými vlastnostmi. Cílem je získat tu směs s co nejnižšími náklady. minimalizujeme.

Př.: Máme 4 krmivové směsi:

krmiva

K1 K2 K3 K4 bílkoviny 0 3 1 2 JEDNOTKY/KG

škrob 1 2 3 0 CENA 20 80 60 30 kg

Cena = náklady… máme získat směs, která bude obsahovat alespoň : 100 jednotek bílkovin, 300 jednotek škrobu a bude vážit alespoň 200 kg. Sestavte MM, pomocí jehož naplánujeme, kolik kterého krmiva máme nakoupit… X1 = množství K1 v kilogramech ve výsledné směsi x2 = množství K2 v kilogramech ve výsledné směsi X3= množství K3 v kilogramech ve výsledné směsi X4 = množství K4 v kilogramech ve výsledné směsi Cílem je minimalizovat náklady.

Účelová fxe bude tedy nějaká nákladová fce. Z = 20x1 + 80x2+ 60x3 + 30 x4 →min Omezení: psát si je zprava 3x2 + x3 + 2x4 ≥100 bílkoviny X1 + 2x2 + 3x3 ≥300 škrob X1 + x2 + X3 + X4 ≥200 škrob Když bychom přišli o 10% ztráty u vaření tak (by ten výsledek byl 220 ) z toho 10% tzn. 1,1 x 200 Podmínky celočíselnosti: tady bychom je nedávali X1,X2,X3,X4 ≥ 0. Vektor = zápis řešení X0

T = (X1, X2, X3, X4)

X0T = (120, 0,60,20) – kg směsi ve výsledné směsi, dohromady 200 kg.

Dostaneme účelové řešení. Z0 = 6600 Kč zaplatíme za 200 kg.


9

Možnosti zakončení výpočtu:

a)

b)


10

c)

d)


11

8.10.2009 Př. TENISOVÝCH RAKET

Lineární programování Alternativní optimální řešení-způsob zakončení výpočtu, při kterém nemá úloha LP pouze jediné optimální řešení. Nepřípustné řešení-řešení,kt nevyhovuje alespoň jedné omezující podmínce úlohy. Omezující podmínky-soustava vlastních omezení, podmínky nezápornosti, případně další speciální podmínky definované v úloze LP. Optimální řešení úlohy LP-nejlepší ze všech přípustných řešení. Podmínky nezápornosti-omezení, která zabezpečují, že budou všechny proměnné modelu kladné, případně nulové. Pomocná účelová fce-minimalizační účel fce doplněná k modelu s cílem vyloučit z něj všechny pomocné proměnné a získat tak výchozí základní řešení úlohy LP. Pomocné proměnné-uměle doplněné proměnné k ekvivalentní soustavě rovnic s cílem získat kanonický tvar. Přídavné proměnné-proměnné, které vyjadřují rozdíl mezi kapacitou zdroje a jeho čerpáním(u omezení typu“ =<“), případně mezi úrovní plnění a minimálním požadavkem (u omezení typu „>=“), které se doplňují k modelu pro převedení soustavy nerovnic na soustavu rovnic. Přípustné řešení úlohy LP-řešení,kt splňuje všechny omezující podmínky modelu, tj. soustavu vlastních omezení i podmínky nezápornosti. Rozšířená soustava rovnic-soustava vzniklá z ekvivalentní soustavy rovnic po doplnění pomocných proměnných. Stínové ceny-koef příslušející omezujícím podmínkám ve tvaru nerovnic vyjadřující změnu hodnoty účelové fce na jednotku pravé strany. Účelová (kriteriální) fce-vyjádření cíle optimalizace v matematické podobě. Vlastní omezení-.podmínka ve tvaru nerovnice či rovnice, vyjadřující například omezenou kapacitu zdrojů, technologické vztahy, požadavky odběratelů apod. Základní proměnné-proměnné, kterým v kanonickém tvaru soustavy lin rovnic odpovídá jednotkový vektor-jejich hodnoty jsou rovny hodnotám pravých stran. Základní řešení úlohy LP-každé základní řešení ekvivalentní soustavy rovnic, které vyhovuje podmínkám nezápornosti; má maximám ě tolik nenulových proměnných, kolik je lineárně nezávislých řádků této soustavy. Základní věta LP-má-li úloha LP optimální řešení,má také základní optimální řešení; podle této věty stačí hledat optimální řešení pouze mezi základními řešeními úlohy LP(kterých je konečný počet).


12

X2=480


13


14

PŘ. mikiny, trička


15

X2=400


16

Troška teorie z hodiny:

Přípustné řešení LP je takové řešení, které vyhovuje všem omezujícím podmínkám úlohy,

včetně podmínek nezápornosti.

Množina přípustných řešení je množina všech takových řešení – konvexní množina buněk –

jakékoli dva body množiny spojím, tak celá spojnice musí ležet. Hranice je tvořena lineárními

množinami „útvary“.

Konvexní POLYEDR (mnohoúhelník), útvar, kde jsou úhly mezi čarami: (krychle, kvádr,

čtyřstěn,…)

Kulečníková koule je konvexní množina bodů, obličej není. Spojené body musí tvořit rovinu!!

V LP je množina přípustných řešení konvexní polyedr!! Pokud by to tak nebylo,

základní věta LP by byla neplatná.

Vyrovnání nerovnice na rovnici:

X1 + 2X2 + X3 = 1500

K levé straně přičítám (je menší nebo rovno)

4X1 + 3X2 + X4 = 3000

Tato soustava je ekvivalentní soustavou rovnic k původní soustavě nerovnic.

K nekonečnému počtu řešení existuje určitý počet základních řešení. Tato soustava má

nekonečně mnoho řešení, konečný počet řešení je základním řešením. Máme základní

proměnné – těch je vždy tolik, kolik máme rovnic (2) a nezákladní proměnné jsou ty zbylé →

(tady také 2 – to je náhoda). Základní proměnná může být i strukturní i přidaná, v základním

řešení si základní proměnné dopočítáme a nezákladní proměnné jsou 0 – volíme.

řešení X1 X2 X3 X4 zisk

1 0 0 1500 3000 0

2 0 750 0 750 7500

3 0 1000 -500 0 X

4 1500 0 0 -3000 X

5 750 0 750 0 8250

6 300 600 0 0 9300

Jelikož chceme maximalizovat zisk, vidíme které řešení je maximální!

Můžeme očekávat 6 základních řešení, ale všech 6 nemusí existovat. Jsou to základní řešení

ekvivalentní soustavy rovnic. Ale pouze některé z nich jsou přípustnými řešeními z hlediska

úlohy LP, konkrétně 4 – 1,2,5,6 – řešení 3,4 – není přípustné z hlediska podmínek.


17

Základní věta LP – pokud á úloha LP optimální řešení, pak má také optimální řešení

základní. Při hledání optimálního řešení se stačí soustředit na základní řešení, kterých je

omezený počet. Alespoň jedno ze základních řešení musí být optimální.


18


19


20


21


22


23


24

22.10.09 U portfolia můžeme definovat proměnné: a) velikost investované částky b) podíl - např. 1/6 c) počet nakoupených akcií/obligací

Příklad SPORTKA

Přesné zadání je k dispozici na webu.

- K dispozici 4 mil. => z toho investovat část tak, aby výnos byl min. 300 tis.; do akcií bylo investováno min. ½ investované částky

x Kč / ks výnos p.a. riziko

akcie 500 10% 6

obligace 700 12% 3

- Cíl = účel = minimalizovat riziko - Znám cenu CP => mohu mít jejich počet za proměnnou => x1 = počet akcií, x2 = počet obligací

Z = 6x1 + 3x2 (min)

Omezující:

x1, x2 ≥ 0 x1, x2 є Z

500*x1 + 700*x2 ≤ 4000000 max. investovaná částka

(500*x1)*0,1 + (700*x2)*0,12 ≥ 300000 min. výnos

500*x1 ≥ 0,5 * (500*x1 + 700*x2) investovaná částka min. z 50% akcie 250*x1 - 350*x2 ≥ 0

Výpočet pomocí řešitele:

akcie obligace

množství 2728 1948

riziko 6 3 22212

pravá strana

cena za CP 500 700 2727600

4000000

Výnos p.a. 50 84 300032

300000

podíl na i. 250 -350 200

0

Výpočet:

250*x1 - 350*x2 ≥ 0 => x1 = 350/250 x2 = 7/5 x2

500*7/5 x2 + 700*x2 = 4000000

700*x2 + 700*x2 = 4000000

x2 = 4000000 / 1400

x2 = 2857 => x1 = 2857*7/5 = 4000


25

(500*7/5*x2)*0,1 + (700*x2)*0,12 = 300000

70*x2 + 84*x2 = 300000

154*x2 = 300000

x2 = 1948 => x1 = 7/5*1948 = 2728

Z = 6x1 + 3x2 => 6*4000 + 3*2857 = 32.571

Z = 6x1 + 3x2 => 6*2728 + 3*1948 = 22.212

Průsečíky v grafu jsou 2, *4000, 2857+ ale neodpovídá zadané podmínce - minimalizovat riziko.

Řezné úlohy

Příklad PLOT

- K dispozici jsou latě 2m - Potřebujeme laťky 80cm -1200ks; 50cm -3100ks; 30cm -500ks

Počet neznámých bude počet možností, jak dvoumetrové latě nařezat na 80, 50 a 30cm laťky Cíl = účel = minimální počet rozřezaných 2m latí

i 1 2 3 4 5 6 7 8 9

80cm 2 1 1 1 0 0 0 0 0

50 cm 0 2 1 0 4 3 2 1 0

30 cm 1 0 2 4 0 1 3 5 6

odpad 10 20 10 0 0 20 10 0 20

Xi = # 2m latí rozřezaných podle i-tého schématu (i = 1, 2,…, 9)

x1, x2, …, x9 ≥ 0

x1, x2 …, x9 є Z

2x1 + x2 + x3 + x4 = 1200 (80-ti cm latěk)

X1

X2


26

2x2 + x3 +4 x5 +3 x6 +2 x7 + x8 = 3100 (50-ti cm latěk)

x1 + 2x3 +4 x4 + x6 + 3x7 +5 x8 +6 x9 = 500 (30-ti cm latěk)

účelová funkce: Z = x1 + x2 + … + x9 → min

účelová f-ce pro zadání minimalizovat odpad: Z = 10x1 + 20x2 + … + 20x9 → min

účelová f-ce pro zadání minimalizovat počet odřezků: Z = x1 + x2 + x3 + x6 + x7 + x9 → min

Dělící problém

Příklad KRMÍTKA A BUDKY

Výstava za 20 dní PC krmítka 260 PC budky 570 pracovní doba 8h/den

Sklad: 500 prken 110cm; 150 prken 140cm, vruty 3000ks

Spotřeba: Krmítko Budka

prkno 30cm 1 2

prkno 25cm 1 4

vruty / ks 8 16

čas min 30 60

Prkno: 110 cm 140 cm Krmítko Budka

Schéma x 1 2 3 4 5 6 7 8 9 10 11

30cm 3 2 1 0 4 3 2 1 0 1 2

25cm 0 2 3 4 0 2 3 4 5 1 4

odpad cm 20 0 5 10 20 0 5 10 15 0 0

x10 = # vyrobených krmítek x11 = # vyrobených budek Účelová funkce = maximalizovat výnos z prodeje : Z = 260*x10 + 570*x11 → max

x1 = # prken rozřezaných podle schématu číslo 1

x9 = # prken rozřezaných podle schématu číslo 9

x10 = # vyrobených krmítek

x11 = # vyrobených budek

Omezující: x1 - x11 є Z Λ x1 - x11 ≥ 0

8*x10 + 16*x11 ≤ 3000


27

0,5*x10 + x11 ≤ 160

x1 + x2 + x3 + x4 ≤ 500

x5 + x6 + x7 + x8 + x9 ≤ 150

3x1 + 2x2 + x3 + 4x5 + 3x6 + 2x7 + x8 ≥ x10 + 2x11

3x1 + 2x2 + x3 + 4x5 + 3x6 + 2x7 + x8 - x10 - 2x11 ≥ 0

2x2 + 3x3 + 4x4 + 2x6 + 3x7 + 4x8 + 5x9 ≥ x10 + 4x11

2x2 + 3x3 + 4x4 + 2x6 + 3x7 + 4x8 + 5x9 - x10 - 4x11 ≥ 0

Řešení Excel:

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11

množství 0 64 0 0 48 0 0 0 102 0 160

výnos 260 570 91200

pravá strana

vruty 8 16 2560 ≤ 3000

hodiny 0,5 1 160 ≤ 160

110cm p. 1 1 1 1 0 0 0 0 0 0 0 64 ≤ 500

140m p. 0 0 0 0 1 1 1 1 1 0 0 150 ≤ 150

30cm díly 3 2 1 0 4 3 2 1 0 -1 -2 0 ≥ 0

25cm díly 0 2 3 4 0 2 3 4 5 -1 -4 0 ≥ 0

Řešení lindo viz. DÚ příloha.

Dopravní problém

Příklad BRAMBŮRKY

Firma chce otevřít 3 nové provozovny – Benešov, Jihlava, Tábor

Firma má 2 sklady – Humpolec, Pelhřimov

Cena za dopravu je uvedena za 1t přepravovaných brambor.

Benešov

Humpolec

Jihlava

Pelhřimov

Tábor


28

výrobna Benešov Jihlava Tábor Týdenní kapacita

skladu v t Sklad

Humpolec 330 250 350 70

Pelhřimov 300 240 250 80

Týdenní požadavek

výrobny v t 45 60 35

150

140

Otázka je: Odkud – kam – kolik bude třeba odvézt

Xij = objem přepravy (t brambor) mezi i-tým dodavatelem a j-tým odběratelem

Z = 330x11 + 250x12 + 350x13 + 300x21 + 240x22 + 250x23

Omezující: (co nesmím překročit – kapacity, co musím dodržet – požadavky výroben)

x11 + x12 + x13 ≤ 70 (kapacita Humpolec)

x21 + x22 + x23 ≤ 80 (kapacita Pelhřimov)

x11 + x21 = 45 (požadavek Benešov)

x12 + x22 = 60 (požadavek Jihlava)

x13 + x23 = 35 (požadavek Tábor)

Podmínky: xij ≥ 0; i = 1, 2; j = 1, 2, 3

B J T Fiktivní odběratel

H 60 10

P 45 35

Z = 37.250,-

Řešit lze v Excelu.

Jedná se o nevyrovnaný dopravní problém = součty kapacit a součty požadavků se liší – tuto nerovnováhu lze vyrovnat pomocí fiktivních činitelů (fiktivní odběratel – ve skutečnosti nikdo zásobu neodebere, ale vyrovnají se tím součty).


29

29.10.2009

Kontejnerový dopravní problém

Cena přepravy je dána za pronájem vagonu (kontejner), nevztahuje se na jednotku přepravovaného materiálu (cena za 1 kontejner je stejná bez ohledu na míru jeho naplnění – tedy zda je plný či prázdný).

výrobna Benešov Jihlava Tábor Týdenní kapacita

skladu v t Sklad

Humpolec 4200 4800 5300 70

Pelhřimov 5100 3400 3700 80

Týdenní požadavek

výrobny v t 45 60 35

150

140

Cena je za 1 vagon “odkud – kam“; kapacita jednoho kontejneru je 18t

xij = objem přepravy v t mezi i-tým dodavatelem a j-tým odběratelem yij = počet kontejnerů použitých na přepravu objemu t brambor mezi i-tým dodavatelem a j-

tým odběratelem

Z = 4200y11 + 4800y12 + 5300y13 + 5100y21 + 3400y22 + 3700y23 → min

Omezující: (co nesmím překročit – kapacity, co musím dodržet – požadavky výroben)

x11 + x12 + x13 ≤ 70 (kapacita Humpolec)

x21 + x22 + x23 ≤ 80 (kapacita Pelhřimov)

x11 + x21 = 45 (požadavek Benešov)

x12 + x22 = 60 (požadavek Jihlava)

x13 + x23 = 35 (požadavek Tábor)

Jak definovat vagóny..??? xij ≤ 18yij

když yij = 0 = pak nejede vagon, nevezu do daného místa žádné zboží…

Podmínky: xij ≥ 0; i = 1, 2; j = 1, 2, 3

yij ≥ 0; i = 1, 2; j = 1, 2, 3; yij є Z

Řešení je v knížce (2.6, str. 46-8), opět možno řešit v Excelu.

Přiřazovací problém

- přiřazuji vždy 2 skupiny prvků, v obou skupinách je stejný počet prvků a každý smí být přiřazen jen jednomu z druhé skupiny (jako párování v tanečních)

- cílem je seskupit prvky z obou skupin tak, aby v páru byl vždy 1 a 1 z každé skupiny prvků - podmínkou je maximalizace celkové spokojenosti

DÚ – jak zajistit maximální spokojenost na tanečním parketu??? o Index spokojenosti – max (spokojenost = ten, kdo chce s někým tančit, s ním také

bude v páru) o Body – 1 za lingo, 2 za realizaci pro 5 párů


30

Příklad BAGRY

Firma má 4 garáže, v každé po jednom bagru a 4 staveniště, kde musí pracovat vždy 1 bagr; bagry by měly najet co nejméně km.

Michle Prosek Radlice Trója

G1 5 22 12 18

G2 15 17 6 10

G3 8 25 5 20

G4 10 12 19 12

1. Nevím, co s tím => vyberu diagonálu => 39km

2. Hledám minimum – takže najdu nejnižší hodnotu (zabarvím hodnoty, které již nepřipadají do úvahy – růžová, pak zelená, pak žlutá a pak zbude poslední volné pole :oD – součet 32km

Otázka je, zda je toto optimum..??? Tento postup nemusí vždy vést k OPTIMÁLNÍMU řešení – proč..?? Tak mrk na tuhle tabulku (stačí tam dopsat nulu):

Tomuto postupu se říká HEURETICKÝ ALGORITMUS (heuristika). Je založen na rozumné úvaze, úloha se stává řešitelnou v relativně krátkém čase, ale nezaručuje vždy optimální řešení. Heuristických řešení je více, poskytují relativně spolehlivé výsledky, často blízké optimu.

Co je v uvedeném příkladě proměnná..? To, co chci zjistit!!!

Počet proměnných..?? 16 (4x4)

xij = 1 nebo 0; 1 – když i-tý bagr pojede na j-té staveniště; 0 – nic nejede nikam (xij je bivalentní – binární nebo také nula-jedničková proměnná – to je už slang)

i = 1, 2, 3, 4; j = 1, 2, 3, 4

právě 4 proměnné = 1, ostatní = 0

Z – chci najet co nejméně Km Z = 5x11 + 22x12 + … + 12x44 → min

Omezující: Na každé místo patří právě jeden bagr, každý bagr je přiřazen právě jednomu staveništi

M P R T

G1 5

G2 17

G3 5

G4 12

M P R T

G1 5

G2 10

G3 5

G4 12

M P R T

G1 5

G2 10

G3 5

G4 120


31

x11 + x12 + x13 + x14 = 1 x21 + x22 + x23 + x24 = 1 každý bagr jede právě na 1 staveniště x31 + x32 + x33 + x34 = 1 x41 + x42 + x43 + x44 = 1

x11 + x21 + x31 + x41 = 1 x12 + x22 + x32 + x42 = 1 na každé staveniště pojede právě 1 bagr x13 + x23 + x33 + x43 = 1 x14 + x24 + x34 + x44 = 1

V Excelu lze zadat podmínku binárnosti tam, kde se zadává podmínka celočíselnosti.

Teorie grafů

Pro začátek zapomeneme na to, že tohle (to nahoře) je graf!!!

Protože tohle je graf:

Skládá se ze dvou množin prvků: = uzly

= hrany

Hrana je - orientovaná (jako jednosměrka)

- neorientovaná (obousměrná)

Na 51 a 52 straně je příklad s mosty (najít cestu tak, abych po každém mostě šla jen jednou – lze to znázornit i pomocí grafu ;o)

Neorientovaný graf – takový, který má všechny hrany neorientované

Orientovaný graf – takový, který má všechny hrany orientované (dohoda je, že mixlý graf nebereme)

Cesta mezi dvojicí uzlů i a j – je taková posloupnost na sebe vzájemně navazujících hran, která začíná v uzlu i a končí v uzlu j

Orientovaná cesta – má smysl jen v orientovaném grafu; je taková cesta, která respektuje orientaci všech hran (v obrázku výše by to byla cesta 1-6)

1

6

3

2 4

5

7 8 9 10


32

Neorientovaná cesta – má smysl jen v orientovaném grafu; je taková cesta, která nemusí respektovat orientaci hran (v obrázku výše by to byla cesta 6-1)

Cyklus = uzavřená cesta – je taková cesta, která začíná a končí ve stejném uzlu (je to cesta přes různé uzly, přičemž bych neměla žádným uzlem projít 2x)

Souvislý graf – mezi každou dvojicí uzlů existuje alespoň jedna cesta (v orientovaném grafu alespoň jedna neorientovaná cesta); na obrázku níže je jeden nesouvislý graf

Úplný graf – mezi každou dvojicí uzlů existuje hrana

Strom – graf, který nemá cyklus – je acyklický

– musí být souvislý

– měl by být neorientovaný

– uzlů je vždy o 1 víc než hran (když jednu hranu umažu, stane se z grafu nesouvislý graf, když naopak jednu přidám, vznikne cyklus a tím pádem už to není strom).

Ke každé hraně mohu přidat číslo – mohu ji ohodnotit (obvykle tím zaznamenávám vzdálenost mezi jednotlivými uzly) – takový graf se nazývá hranově ohodnocený

Uzlově ohodnocený graf – ohodnotím jednotlivé uzly (to nebudeme moc používat)

Síť – síťový graf – je graf souvislý, orientovaný, hranově nebo uzlově ohodnocený a má 1 vstup a 1 výstup

- vstup – uzel, ze kterého hrany jen vystupují - Výstup – uzel, do kterého hrany pouze vstupují

6.11.09

Úkol Taneční

Navrhněte způsob, jak zajistit maximální celkovou spokojenost všech tanečních párů v tanečním

sále. (1 bod).

Uvedený způsob demonstrujte na příkladu s 5 dívkami a 5 chlapci v tanečním kurzu. Úlohu

vyřešte v MS Excel (2 body).


33

Tzn. teď x11 + X12+X13 ….. NEDOPOČÍTÁVALI JSME TO!!!


34


35


36


37

Doučko:


38


39

Úkoly Kostra, Cesta a Tok

U následujícího grafu najděte:

1. Jeho minimální kostru (2 body).

2. Nejkratší cesty z uzlu č. 1 do všech ostatních uzlů (2 body).

3. Hodnotu maximálního toku z uzlu č. 1 do uzlu č. 7 (2 body).

Date post:	09-Dec-2020
Category:	Documents
Upload:	others
View:	7 times
Download:	0 times

OPVP přednášky, cvičení Fábry Úvod do operačního výzkumu ... KOMPLET.pdf · a) Výroba...

Documents