- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Popisek: zápisky z přednášek
Zjednodušená ukázka:
Stáhnout celý tento materiální hodnoty ui, vj, tak, aby jejich součet se rovnal sazbě obsazeného pole
(více řad se stejným max počtem obsazovaných polí, můžeme si vybrat libovolnou z nich)
C´ij ……… cena ekvivalentní kombinace základních procesů
Cena ekvivalentní kombinace přeprav, distribuce
C´ij = ui + vj pro všechna xij = 0
výpočet provádíme pro všechna volná, neobsazená pole
V dalším kroku provedeme pro volná pole rozdíl C´ij – Cij
výsledek = 0 (hodnota účelové fce se nezmění)
výsledek = +
výsledek = -
∆Z min = - xij * ( C´ij – Cij)
- * + = - → fce klesne
- zajímají nás políčka, kde rozdíl ( C´ij – Cij) je kladný +, tzn., že dosud nejsem v optimálním řešení
Nejvyšší rozdíl – pole je pro nás perspektivní – (jako mohu provést změnu?)
→ Dantzigův uzavřený obvod
vztah mezi obsazenými políčky, který nám určuje rozsah změny
Nové řešení našeho příkladu
16
17
55
0
šipka označuje nejvyšší rozdíl
9. PŘEDNÁŠKA
Přiřazovací problém
speciální metodou v rámci dopravních úloh
ve své podstatě připomínají jednostupňové dopravní úlohy, ale není řešitelná běžnými úkony, protože jde o silně degenerovaný problém. Při řešení tohoto problému běžné algoritmy při řešení jednostup.. dopravních úloh selhávají a nenachází optimální řešení.
Princip problému
Dodavatel Spotřebitel
ai 1 D1 S1 1 m˛(počet možných přiřazení)
1 D2 S2 1 bj
. .
. .
. .
1 Dn Sn 1 *trasy – tij ; Nij ; Lij
nedělitelná množství
(kapacity D) trasy Cij (char. max nebo min !)
*sazby přiřazené D a S si můžeme ohodnotit
libovolně zvoleným kriteriem
*klasická vzdálenost Lij (Km)
*zájmový prostor
S1
S2
S3
S4
S5
ai
D1
4
7
12
15
6
1
D2
2
5
6
8
7
1
D3
3
4
5
6
8
1
D4
4
5
6
7
2
1
D5
3
5
6
6
3
1
bj
1
1
1
1
1
doplníme okrajové hodnoty (kapacita D a S = 1) *jedná se o matici!
- ∑min ∑ . ∑ Cij . xij -vektor přiřazení (políček)
i j
= 0
> 0
- ∑ ai = ∑ bj . xij *xij = 1
m n
PP (přiřaz.probl.) = ∑ ∑ Cij
C=1 j=1
Závěr:
zvláštnosti úlohy spočívají v tom, že matice úlohy je vždy čtvercová
okrajové hodnoty ai a bj = 1, tedy nedělitelné a tudíž i xij = 1 a účelová funkce je redukovaná n sazeb, z tohoto vyplývá, že řešení obsahuje pouze m polí. (místo 9
můžu 5) řešení obsahuje menší počet obrazových polí než M + N – 1 tudíž je degenerované a nelze využít klasické testy optimality pro řešení tohoto typu úloh vyvinul americký profesor [:kýn:] novou metodu, kterou nazval maďarská (na počest 2 maďarských profesorů : [:egerwary a konig: ]).
ti ve 30. letech pracovali na teorii sítí a grafů a stanovili zvláštní teorém na jehož základě je tato metoda stanovena.
Konug teorem (přehláska nad o) Princip řešení PP – praxe s tzv.trainsformem, redukovanou maticí, která má ovšem stejné vlastnosti jako matice původní. Redukovanou matici získáme pomocí tzx. Řadové redukce tzn. Že od každé řady tj. řádků a sloupce odečteme min. sazbu řady a tím dostaneme stav, že v každé řadě tj. v každém řádku a sloupci dostaneme alespoň jednu nulu. Pozn: protože ai a bj = 1 tak tyto vypouštíme Pozn: je lhostejné zda začínáme řádkovou nebo sloupcovou redukcí
1.krok: v prvním sloupci je nejnižší sazba 2 (matice!)
2
3
7
9
2
0
1
1
2
4
1
0
0
0
5
2
1
1
1
6
1
1
1
0
1
- od každého sloupce jsme odečetly nejnižší sazbu
Primárně redukovaná matice (o řádkové a sloupcové redukci) =>to samé, ale s řádky
0
1
5
7
2
0
1
1
2
5
1
0
0
0
6
2
1
1
1
0
1
1
1
0
1
D1 => S1
D5 => S4
D4 => S5
D3 => S2
2. krok: výběr nezávislých nul, nezávislá nula představuje prvek v bázi.
Matice je plně ekvivalentní s původní maticí.
Výběr nezávislých prvků (tzn. nezávislých nul). Nezávislá nula je chápána tou nulou, kterou označíme jako samu v řádku i sloupci = jde o jednoznačné přiřazení.
Pozn: výběr nezávislých nul = heurichstická, nejednoznačná cesta pokusů a omylů.
Pozn: výběr nezávislých nul začínáme od řádku s minimálním počtem nul. Kolmo na řadu, ze které byla nezávislá nula vybrána vedeme krycí čáru ! Krycí čára je grafickým testem optimality. Současně je ověřením správnosti postupu.
[: konig egerwary teorem :]
Maximální počet nezávislých nul, které lze vybrat z redukované matice = minimálnímu počtu krycích čar, kterými lze podrýt všechny nuly tabulky.
Závěr 1:postup je správný.
Závěr 2:dvě krycí čáry se nesmí křižovat v nezávislé nule.
3.krok: sekundární redukce
a)určíme minimálně přeškrtnuté prvky
*prvky přeškrtnuté jednou = beze změny¨
*prvky přeškrtnuté dvakrát = zvětšujeme
*prvky nepřeškrtnuté = zmenšujeme
0
0
4
7
1
0
0
0
2
4
2
0
0
1
6
3
1
1
2
0
1
0
0
0
0
*zpět do původní matice, kde nalezneme řešení :
4
7
12
15
6
2
5
6
8
7
3
4
5
6
8
4
5
6
7
2
3
5
6
6
3
4 4 6 6 2
Závěr:
V dalším postupu se nám podařilo vybrat 5 nezávislých nul tzn. našli jsme nejkratší možné optimální řešení !
*mohlo by se stát, že ani v tomto kroku nenajdeme optimální řešení
=> znovu opakovat sekundární redukci
(Maximalizace: 11 8 3 0 9 doplňky do max. sazby (15)
*a pokračovat úplně stejně jako u min.
10. PŘEDNÁŠKA
Metodický úvod do obecné teorie sítí a grafů
Teorie sítí a grafů je známa příbližně 80. let. Svým způsobem je to univerzální zobrazovací nástroj. Lze na něm definovat celou řadu úloh – patří sem např. minimální kostra grafu, průtok sítí, lamba nejkratší cesta, řez uzlem, kritická cesta, deterministická forma grafu, stochastická forma grafu, ekvivalentní typy rozhraní až po kombinované grafy a softwarové produkty typu MS PROJECT.
V roce 1989 firma IBM inzerovala asi 1080 algoritmů na síťové grafy. MS PROJECT přišel v roce 1990, dnes je verze 2003 – rozsáhlá problematika.
Uj
Ui
1
2
3
4
5
1
0,1
0,7
0,2
0
0
2
0
0,3
0
0,6
0,1
3
0
0,4
0,2
0
0,4
4
0
0
0
0,2
0,8
5
1
0
0
0
0
Představme si, že máme nějaký náhodný (= stochastický) proces. Tento proces může nabývat libovolný konečný počet stavů.
S1 – profesor opouští kancelář a má několik možností: jít na autobus (S2) nebo do knihovny (S3) a pak jet metrem domů (S5) nebo rovnou do hospody (S4); nebo nejdřív domů (S5) a pak do hospody (S5) nebo z knikovny (S3) domu autem atd.
Vytvořili jsme intuitivní hypotetickou představu cyklického síťového grafu, který nám znázorňuje možnou dynamiku vývoje systému (platí to pro libovolný náhodný proces – např. jdu několikrát na zkoušku) = to jest možnosti přechodu mezi jednotlivými stavy systému.
Příklad: Představme si, že v 10% musím vrátit (otázky: zavřel jsem okno?, vypnul jsem počítač?)
0,1 znamená = 10% možných případů¨
0,2 – jdu něco vrátit (např. do knihovny, do SICu)
0,7 – jdu na bus ze 70%
V této matici možných přechodů mezi stavy jsou koeficienty aij = P(ij) - pravděpodobnost ze stavu i do stavu j.
Musí ovšem platit, že n
∑ P(ij) = 1
j=1
(součet pravděpodobnosti = 1; součet dílčích pravděpodobnostních stavů dává jev jistý)
-- součet výstupů musí dávat 1 !!!
z S5 do S1 je přímá zpětná vazba
aij nabývají 3 možných charakteristik:
a) 0 – jestliže v tomto poli máme 0, nelze přejít ze stavu i do stavu j
b) 1 – přechod deterministický = přikázaný; ze stavu i je možné jít pouze do stavu j
c) P(ij) – přechod pravděpodobný – systém ze stavu i do stavu j přechází s nějakou statisticky odvozenou pravděpodobností (na základě distribučního rozdělení dle typů možností)
Pro potřeby algoritmu se mi nemůže nic ztratit. Jde o uzavřený cyklus v nějakém časovém intervalu.
Různé typy objektů se mohou chovat různě (něco je vždy poprvé a něco je vždy naposledy).
Mějme 6 uzlů. Pod pojmem Ui budeme rozumět pasivní = evidenční zobrazení možného stavu.
Mezi dvojicí uzlů Ui a Uj probíhá nějaká reálná operace, aktivita, činnost (nějaký process) – např. příprava na EMM
Příklad:
cesty prvního řádu
3
3
4
5 6
7
7 2 5
4
Tato spojnice se nazývá hrana (spojnice, subtrasa). Tuto spojnici (činnost) chci nějakým způsobem ohodnotit = kvantifikovat.
Intenzita [i;j] např. výkrmu prasat, studia
tij = doba trvání (např. 1 den, 2 dny, týden)
Lij = vzdálenost
Nij = oceňované náklady
Fij = čerpání limitovaného (omezeného) faktoru – např. pracovní síla, voda, jeřáb
Eij = nějaký kriteriální efekt plynoucí z této činnosti, operace, aktivity
Nějaké procesy se můžou chovat jinal – symetrie (rovnoměrnost) a asimetrie (nerovnoměrnost) procesů.
rektangularita (rovnoměrné chování náhodné proměnné)
Tento typ síťových grafů označujeme jako HOG (hranově orientovaný graf) = hrany jsou aktivní (kvantifikovatelné zobrazitelné procesy) a uzly jsou pasivní (evidují jejich návaznost, průběh).
Musíme udělat:
1) orientaci grafu – každému uzlu musíme přiřadit nějakou hodnotu, nějaké pořadové číslo
U malých grafů (přehledné, jednoduché, skromné) se používá: metoda škrtací
Počítače používají metodu: ford – Fulkersonova metoda (algoritmizace metody škrtací)
Smyslem orientace je to, aby pro všechny vztahy platilo Ui < Uj (index i < index j = j musí být větší než i)
- pro libovolnou dvojici uzlů platí, že i je menší
Cesty prvního řádu (přeškrtnuto 1x na obrázku) – jejich očíslování je libovolné
(pro uzly stejného řádu platí pravidlo libovolného pořadí). Cesty druhého řádu (přeškrtnuto 2x).
Existuje uzel, kam vstupují cesty 2 a nižšího řádu? Ano – tři
Existuje uzel, kam vstupují cesty 3 a nižšího řádu? Ano – čtyři
Vždy vstupní šipka má nižší číslo, než na výstupu operace
2) kvantifikace sítě - každé hraně (operaci) přiřadíme kvantifikační hodnotu tij (délka trvání operace ve zvolených časových jednotkách (minuty, hodiny, roky)
Příklad: permutujeme náhodně čísla........ (to znamená, že každé situaci jsme přiřadili konkrétní dobu jejího trvání)
Uj
Ui
0
1
2
3
4
5
0
x
3
7
5
1
x
4
3
2
x
2
4
3
x
6
5
4
x
7
5
x
Není zpětný cyklus – vyškrtneme prvky hlavní diagonály a z vlastností této matice, kterou si nazveme incidenční matice acyklického síťového grafu, vyplývají tyto vlastnosti:
hlavní diagonála není obsazena (tzn. žádný z uzlů neobsahuje zpětnou vazbu)
dolní trojúhelník (pod hlavní diagonálou) je 0, tzn. všechna políčka jsou 0 = tzn. že v síťovém grafu není žádný dílčí ani zpětný cyklus
jestliže jsme opustili nějaký stav, už nemáme možnost se do něj vrátit = po opuštění uzlu není návratu (není jiné cesty)
horní trojúhelník matice obsahuje v každé řadě, tj. v každém řádku i sloupci alespoň 1 nenulový prvek – graf je celistvý
Incidenční matici nazýváme (označujeme) jako ekvivalentní formu zobrazení síťového grafu.
V kazdém uzlu budeme pracovat se dvěma časovými parametry:
-- termín nejdříve možného výskytu uzlu
-- termín nejpozději přípustného výskytu uzlu
= -
Interferenční (kritická) rezerva uzlu = tuto interferenční rezervu dostanu jako rozdíl nejpozději přípustného výskytu a nejdříve možného výskytu uzlu
3) výpočet základních časových ukazatelů
- doba kdy skončí všechny činnosti má hodnotu 22 jednostek
= termín nejdříve možného výskytu konečného uzlu představuje minimální délku splnění všech operací (= projektu jako celku)
Kritická cesta, Výpočet incidenční matice, Časové rezervy, Metoda PERT
V teorii sítí a grafů obecně pracujeme se šesti typy uzlů
1) Uzel počátečníInput Output - obvykle označujeme nulou 0 1
žádná operace do něj nevstupuje, 0 N
ale 1 nebo více z něj může vystupovat
2) Uzel koncový
na konci síťového grafuInput Output
1 nebo více operací do něj vstupuje, 1 0
ale žádná nevystupuje N 0
3) Uzel přenosový (transformativní)
operace do něj vstupují11
i z něj vystupují
4) Uzel koncentrický (soustředný)
seběhne se několik operací,
aby ta následná mohla pokračovat1
N
5) Uzel excentrický (odstředivý, distributivní)
opakem koncentrického 1N
6) Uzel kombinovaný (redistributivní)
n operací se sbíhá a současně n operací pokračuje
Výpočet nejpozději přípustných termínů výskytu uzlů
Půjdeme v protisměru šipek, ale v případě, že z uzlu vychází více operací→ bude nás zajímat čas minimální ← Rev.
Postup- v konečném uzlu přepíšeme, že =
=
<
3
3
4
5 6
7
7 2 5
4
RI Interferenční rezerva uzlu
vnitřní rezerva uzlů
je to rozdíl mezi nejpozději přípustným a nejdříve možným termínem výskytu
RI = T1- T0 Interferenční rezerva je vztažena k uzlu
T0
0
1
2
3
4
5
0
0
X
3
7
3
1
X
7
2
X
3
X
4
X
22
5
X
T1
22
RI = T1- T0
Uzly, kde se interferenční rezerva rovná nule, jsou uzly kritické a těmito uzly prochází tzv. KRITICKÁ CESTA = nejdelší logická posloupnost operací od počátečního ke koncovému uzlu, současně je to nejdříve možný časový termín splnění projektu jako celku
7
Časové rezervy operací - 4 typy
REZERVA CELKOVÁ =
36 - 12 - 7 = 17
REZERVA VOLNÁ =
31 - 12 - 7 = 12
REZERVA NEZÁVISLÁ=
31 - 15 - 7 = 9
REZERVA ZÁVISLÁ prakticky nepoužíváme
12 15 31 36
t
K.C.
N.O.
O.T.
REZERVA CELKOVÁ- míra těsnosti na kritickou cestu
=možné prodloužení délky trvání operace nebo posunutí jejího počátku, aniž by došlo ke změnám časových parametrů kritické cesty(K.C.)
REZERVA VOLNÁ- míra těsnosti na návazné operace
= možné prodloužení délky trvání operace nebo posunutí jejího počátku, aniž by se změnily časové parametry operací návazných(N.O.)
REZERVA NEZÁVISLÁ
= možné prodloužení délky trvání operace nebo posunutí jejího počátku, aniž by se změnil jakýkoli jiný časový termín projektu(O.T)
4. Ekvivalentní forma síťového grafu – TABULKA OPERACÍ
OP
Název
Ui
Uj
Předchází
tij
a
m
b
σij
1
0
1
---
3
2
0
2
---
7
2
5
11
5,5
1,5
3
0
3
---
5
4
1
3
(0,1)
4
5
1
4
(0,1)
3
6
2
3
7
2
5
tij doba trvání může být chápána jako funkce náhodné proměnné
aoptimistický, nejkratší možný termín
bpesimistický termín
mnejběžnější, střední termín
pravděpodobná, očekávaná délka trvání činností operace
= a+4m+b obvyklá aproximace normálního rozdělení
6
= 2+20+11=1,5
6
STOCHASTICKÉ SÍŤOVÉ GRAFY
kde jednotlivé operace a jejich návaznosti nechápeme jako pevně dané, ale jako funkce náhodných proměnných
nejznámější metoda PERT
Přednášky z EMM 1
E
A
A-1
E
sklad
s3
s2
s1
M
M
třídička
P.K.
X2
X1
X3
(c
Zj-cj
A(m,n(
(x
( b
(
(v
(c
(y
(x
(c
(
( b
(
A(m,n(
A(m,n(
Zj-cj
S1
D1
S2
D2
S5
D3
D4
S3
S4
D5
Odhad v Km
01
04
03
02
0
0
0
0
0
6
4
2
6
4
S1
S2
S3
S4
S5
0,1
0,7
0,2
0,4
0,3
0,6
0,8
0,2
0,1
0,4
0,2
Ui
Uj
Ui
12
1
3
5
5
4
15
15
2
0
0
0
3
9
9
9
4
15
0
17
5
22
22
7
2
7
7
18
H
Uj
Ui
Ui
O
K
12
1
3
5
5
4
15
15
2
0
0
0
3
9
9
9
4
15
0
17
5
22
22
7
2
7
7
18
Úplná incidenční matice síťového grafu pro výpočet interferenční rezervy.
Incidenční matice se počítá přes prázdné prvky hlavní diagonály
15
12
Uj
Ui
31
36
Vloženo: 1.06.2010
Velikost: 1,24 MB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Mohlo by tě zajímat:
Skupina předmětu EAE01E - Ekonomicko matematické metody I.
Reference vyučujících předmětu EAE01E - Ekonomicko matematické metody I.
Podobné materiály
- AAE01E - Obecná fytotechnika - Přednášky
- AGE01E - Chov zvířat I. - Přednášky
- AGE01E - Chov zvířat I. - Přednášky
- EAE02E - Ekonomicko matematické metody II. - Přednášky
- EEE02E - Ekonomika agrárního sektoru PaA - Přednášky
- EEE16E - Ekonometrie PaA - Přednášky
- EEE33E - Investice a dlouhodobé financování - PaA - Přednášky
- EEE35E - Ekonomika veřejného sektoru - Přednášky
- EHE12E - Politologie - PAA - Přednášky (2)
- EHE12E - Politologie - PAA - Přednášky
- EJE04Z - Občanské právo - Přednášky - Pikola
- EJE05E - Obchodní právo - Přednášky
- EJE14E - Základy právních nauk - PAE - Přednášky
- EJE14E - Základy právních nauk - PAE - Přednášky
- ENE04E - Obecná ekonomie I. - Přednášky (2)
- ENE04E - Obecná ekonomie I. - Přednášky
- ENE05E - Obecná ekonomie II. - Prednasky - pokračování
- ENE05E - Obecná ekonomie II. - Přednášky - Pavelka
- ENE05E - Obecná ekonomie II. - Přednášky
- ENE15E - Obecná ekonomie III. - Přednášky
- ENE15E - Obecná ekonomie III. - Přednášky
- EPE09E - Psychologie a etika v podnikání - Přednášky - Kolman
- EPE10E - Psychologie osobnosti a komunikace - Přednášky
- ERE15E - Marketing I. PAA - Přednášky
- ERE49E - Kybernetika v řízení PAA - Přednášky
- ERE49E - Kybernetika v řízení PAA - Přednášky
- ERE61E - Teorie řízení PAA - Přednášky
- ESE15Z - Statistika I. - PAA - Přednášky
- ESE17E - Statistika II. - PAA - Přednášky (2)
- ESE17E - Statistika II. - PAA - Přednášky
- ETE05E - Informační systémy - Přednášky - celek
- ETE05E - Informační systémy - Přednášky - Šilerová
- ETE05E - Informační systémy - Přednášky
- ETE41E - ICT pro manažery - Přednášky
- EUE06E - Finance a úvěr - Přednášky
- EUE12E - Mezinárodní obchod - Přednášky
- EUE20E - Potravinářské zbožíznalství - Přednášky (2)
- EUE20E - Potravinářské zbožíznalství - Přednášky
- EUE21Z - Teorie účetnictví - PAA, INFO - Přednášky - Valder
- EUE21Z - Teorie účetnictví - PAA, INFO - Přednášky - Váchová
- EUE21Z - Teorie účetnictví - PAA, INFO - Přednášky
- EUE21Z - Teorie účetnictví - PAA, INFO - Přednášky
- EUE22E - Účetnictví pro podnikatele - PaE - Přednášky
- EUE28E - Základy obchodních nauk - Přednášky
- TAE21E - Matematika - Přednášky - Gurka
- ARE01E - Speciální fytotechnika - Přednášky - Vašák
- EEE08E - Ekonomika podniků I. PaE - Přednášky
- EEE08E - Ekonomika podniků I. PaE - Přednášky
- ERE02E - Administrativní technika VSRR - Přednášky ve wordu
- EHE55E - Věda, filosofie a společnost - PAE - přednášky
- AGE01E - Chov zvířat I - přednášky + výpisky ze skript
- EHE60E - Věda, filosofie a společnost - PAA - přednášky
- EJA05E - Základy právních nauk - Přednášky
- ABE01E - Základy fytotechniky - přednášky - houby
- ABE01E - Základy fytotechniky - výpisky z přednášky
- ABE01E - Základy fytotechniky - výpisky z přednášky
- ABE01E - Základy fytotechniky - výpisky z přednášky
- ABE01E - Základy fytotechniky - výpisky z přednášky
- ABE01E - Základy fytotechniky - výpisky z přednášky
- ARE01E - Speciální fytotechnika - přednášky
- EHE10E - Politologie - PaE - přednášky
- ERE07E - Kybernetika v řízení PAE - přednášky
- ARE01E - Speciální fytotechnika - Výtah ze sladů - přednášky
- EHE60E - Věda, filosofie a společnost - PAA - Přednášky
- ERE86E - Marketingová komunikace - KS PaE - Přednášky KS
- ESE27E - Základy statistiky - Přednášky
- ERE61E - Teorie řízení PAA - Přednášky Lhotská
- ERE39E - Teorie řízení PAE - Přednášky Lhotkská
- ERA09E - Teorie řízení - FAPPZ - Přednášky Lhotská
- ERE02E - Administrativní technika VSRR - Prednášky
- EAE01Z - Ekonomicko matematické metody I - přednášky
Copyright 2024 unium.cz