Hledej
Zobraz:
Univerzity
Kategorie
Rozšířené vyhledávání
12 663
projektů
Přiřazovací problém (PP)
«»
| Přípona .docx |
Typ poznámky |
Stažené 1 x |
| Velikost 0,3 MB |
Jazyk český |
ID projektu 6927 |
| Poslední úprava 09.11.2015 |
Zobrazeno 1 427 x |
Autor: blackmagic |
Sdílej na Facebooku |
||
| Detaily projektu | ||
- Cena:
2 Kreditů - kvalita:
88,3% -
Stáhni
- Přidej na srovnání
- Univerzita:České vysoké učení technické v Praze
- Fakulta:Fakulta dopravní
- Kategorie:Technika » Doprava a spoje
- Předmět:Teorie grafů a její aplikace v dopravě
- Studijní obor:-
- Ročník:3. ročník
- Formát:MS Office Word (.docx)
- Rozsah A4:23 stran
Přiřazovací problém (PP)
1 Praktické úlohy přiřazování
Při formulaci obecného přiřazovacího problému vyjdeme z úloh praktického charakteru, které vedou na využití metod aplikované matematiky vyvinutých pro jejich řešení.
1.1 Úloha o přiřazení pracovníků
Výrobní podnik disponuje m pracovníky, které je nutné přiřadit na m pracovišť. Efektivnost „nasazení“ i. pracovníka na j. tou práci je možné kvantifikovat pomocí koeficientu cij , který vyjadřuje průměrnou úsporu materiálu na jednotku produkce, nebo průměrnou ztrátu (vadné výrobky, zmetky). V dalším budeme uvažovat, že koeficienty vyjadřují ztrátu. V případě, že i. pracovníka není možné na j. práci nasadit, položíme cij = . Koeficienty je možné sestavit do čtvercové matice C=(cij), i=1,…,m; j=1,…,m, kterou nazýváme matice sazeb. Úkolem je rozhodnout, o přiřazení pracovníků na jednotlivá pracoviště tak, aby bylo dosaženo minimálních průměrných ztrát materiálu na jednotku produkce. Jde o minimalizační úlohu.
1 Praktické úlohy přiřazování
Při formulaci obecného přiřazovacího problému vyjdeme z úloh praktického charakteru, které vedou na využití metod aplikované matematiky vyvinutých pro jejich řešení.
1.1 Úloha o přiřazení pracovníků
Výrobní podnik disponuje m pracovníky, které je nutné přiřadit na m pracovišť. Efektivnost „nasazení“ i. pracovníka na j. tou práci je možné kvantifikovat pomocí koeficientu cij , který vyjadřuje průměrnou úsporu materiálu na jednotku produkce, nebo průměrnou ztrátu (vadné výrobky, zmetky). V dalším budeme uvažovat, že koeficienty vyjadřují ztrátu. V případě, že i. pracovníka není možné na j. práci nasadit, položíme cij = . Koeficienty je možné sestavit do čtvercové matice C=(cij), i=1,…,m; j=1,…,m, kterou nazýváme matice sazeb. Úkolem je rozhodnout, o přiřazení pracovníků na jednotlivá pracoviště tak, aby bylo dosaženo minimálních průměrných ztrát materiálu na jednotku produkce. Jde o minimalizační úlohu.
Klíčová slova:
přiřazovací problém
formulace
dopravní úlohy
dopravní prostředek
řešení
Obsah:
- 1 Praktické úlohy přiřazování
1.1 Úloha o přiřazení pracovníků
1.2 Úloha o výběrovém řízení
1.3 Speciální případ dopravní úlohy
1.4 Úlohy o nasazování obslužných čet a dopravních prostředků
2 Formulace problému
3 Metody řešení
3.1 Řešení PP jako úlohy LP
3.2 Řešení PP jako analogie dopravního problému (distribučního problému) tabulkovou metodou
3.3 Řešení PP metodou pokrývajících čar
3.4 Řešení přiřazovacího problému metodou rozvoje stromu
3.5 Řešení PP jako aplikace Ford-Fulkersonovy metody pro určení maximálního toku na dopravní síti
3.6 Řešení PP jako aplikace úlohy obchodního cestujícího (Littlův algoritmus)
3.6.1 Princip metody Branch & Bound (větve a hranice)
3.6.2 Algoritmus pro nalezení minimální/maximální hamiltonovské kružnice grafu s n vrcholy
3.6.3 Algoritmus pro nalezení maximální hamiltonovské kružnice