Otázky

1. Co je to podmínka primární přípustnosti řešení?
Odp: = podmínka nezápornosti proměnných
2. Jakých hodnot může proměnná v rámci podmínky primární přípustnosti nabývat?
Odp:(proměnná může nabývat hodnot buď 0 a nebo je větší než 0)
3. Co jsou to bivalentní úlohy?
Odp.: umožňují se jednoznačně rozhodnout mezi úlohou A a B
4. Co je to Gommovyho algoritmus?
Odp.: automaticky nám najde nejbližší celočíselné řešení od řešení optimálního nečíselného
5. Kdo vytvořil Simplexovou metodu a kdy?
Odp.: profesor Dantzig (1945-50) – původně dáncig metoda
Co je to Simplexová metoda a jaký je její princip?
Odp.: univerzální metoda pro řešení soustavy lineárních rovnic
Jaké jsou kroky Simplexové metody?
Odp.:
definujeme proměnné úlohy
vytvoříme soustavu omezujících podmínek
vytvoříme vektor pravé strany (=vektor omezení)
definujeme typ účelové funkce
sestavíme výchozí symplexovou tabulku
8. Pomocí jakou dvou testů provádíme jednotlivě „iterační“ výpočetní kroky tak, až najdeme konečné optimální řešení v Simplexové metodě?
Odp.: test optima/optimality a test přípustnosti
9. Z čeho vychází Simplexová metoda?
Odp.: vychází z Gauss-Jordanovy metody úplné eliminace, kde základem jsou proměnné x1….xm
10. Jaké typy omezení můžu stanovit u proměnných v symplexové metodě a kolik?
Odp.:6 zákl. typů – rovnost, kapacitní, požadavkové, bilanční, poměrové, poměrově/přípustkové
11. Co je bazický vektor – bazická proměnná?
Odp.: vektor, který v sobě obsahuje jednotkový vektor, tedy vektor báze
12. Co je to jednotková matice?
Odp.: je to soustava ortogonálních vektorů (navzájem kolmých) → vytváří přirozenou bázi M dimenzionálního vektorového prostoru
13. Co jsou „ prohibitivní „ ceny/sazby?
Odp.: jsou to sazby, které algoritmicky znemožní, aby umělá pomocná proměnná vstoupila do optimální báze
14. Jakých hodnot nabývají prohibitivní sazby?
Odp.: jsou obvykle 10x, 100x, až 1000x větší než běžná sazba
15. Je u minimalizační úlohy prohibitivní sazba kladná nebo záporná a proč?
Odp.: je zde velká kladná sazba; Z(k+1)=……. vzorec
16. Co je to degenerace úlohy u Simplexu = degenerace řešení u Simplexu?
Odp.: takové řešení, jestliže v bázi je zařazena 1 nebo více proměn. s nulovou hodnotou
17. Co je základem duálně simplexového algoritmu?
Odp.: dualita
18. Jaké typy duality zmáte?
Odp.: symetrickou, asymetrickou a obecnou
19. Jaký je význam duality na jednotlivých úrovních?
Odp.:
1.úroveň – k odvozování matematický vět (struktury axiomů, predikátů, hypotéz, teorémů)
2.úroveň – duální simplexový algoritmus, který umožňuje řešit úlohy, které jsou primárně formálně nepřípustné
3.úroveň – umožňuje transpozici úlohy dle požadovaného rozsahu úlohy
4.úroveň – dualita je využívána ve speciálních úlohách při konstrukci tzv. okrajových duálních proměnných, které kriteriálně hodnotí vlastnosti zkoumané soustavy
20. Co nám zobrazují vektory záporné fiktivní proměnné?
Odp.: zobrazují možné překročení minimálně stanoveného požadavku
21. Co mám udávají kladné fiktivní proměnné?
Odp.: udávají nám nevyčerpání provozní (disponibilní) kapacity
22. Jak se mohou parametry modelu a struktura simplexu měnit?
Odp.:
přidávání nových procesů
přidávání různých typů omezujících podmínek
různé podmínky můžeme disagreagovat (rozčlenit) na libovolný konečný počet dílších podmínek
23. Jak převedeme matici singulární na regulární v případě převodu JDU na Simplex?
Odp.: vyškrtneme poslední podmínku
24. Kdy je řešení degenerované u JDU?
Odp.: pokud by bylo méně než m+ n – 1 vektorů
25. Co znamená Ui v simplexové metodě?
Odp.: řádková duální proměnná
26. Co znamená Vj v simplexové metodě?
Odp.: sloupcová duální proměnná
27. Co znamená systém cestní sítě mezi dodavateli a odběrateli v dopravní úloze?
Odp.: znamená, že mezi dodavateli a odběrateli existují spoje, hrany, cesty
28. Jaký je rozdíl v řešení u simplexu a v dopravní úloze?
Odp.: u simplexu může nastat žádné řešení, kdežto dopravní úlohy mají řešení vždy
29. Jakou techniku používáme v případě, že kapacita dodavatele a požadavky spotřebitele jsou tzv. nevyvážené
Odp.: používáme techniku tzv. fiktivního dodavatele nebo spotřebitele
30. Charakterizujte vyváženou dopravní úlohu?
Odp.: fiktivní dodavatel nebo spotřebitel mají nulovou hodnotu
31. Jaké znáte metody, jak nalézt výchozí základní řešení v dopravní úloze?
Odp.:
metoda severozápadního rohu (NWC)
indexová metoda – vzestupná, sestupná, kombinovaná
habrova frekvenční – aproximat. metoda, která rychle konverguje do řešení v blízkosti optima
VAM – přibližná řešení, která nejsou špatná
32. Je přiřazovací problém v dopravních úlohách silně degenerovaný, nebo ne?
Odp.: jde o silně degenerovaný problém (ve své podstatě připomínají jednostupňové dopravní úlohy, ale není řešitelná běžnými algoritmy JDU)
33. Proč se maďarská metoda nazývá „maďarská“?
Odp.: nazval profesor Kun, na počest 2 maďarských profesorů [egerwary a konig]
34. Co je nezávislá nula?
Odp.: je chápána tou nulou, kterou označíme jako samu v řádku i sloupci = jde o jednoznačné přiřazení
35. Co vyjadřuje pojem rektangularita?
Odp.: rovnoměrné chování náhodné proměnné
36. Jaký je význam zkratky HOG v teorii síťových grafů?
Odp.: HOG = hranově orientovaný graf
37. Jaký má v teorii síťových grafů význam orientace grafu?
Odp.: znamená, že každému uzlu musíme přiřadit nějakou hodnotu, pořadové číslo, kde I je menší než J
38. Napište 2 metody, které se využívají k orientaci grafu v teorii síťových grafů.
Odp.: u malých grafů (přehledné, jednoduché) se používá: metoda škrtací a pro složité počítače používají Ford – Fulkersonova metodu (algoritmizace metody škrtací)
39. Co znamená kvantifikace sítě?
Odp.: každé hraně (operaci) přiřadíme kvantifikační kodnotu tij (délka trvání operace ve zvolených časových jednotkách (minuty, hodiny, roky)
40. Jakým způsobem dostanu interferenční (kritickou) rezervu uzlu?
Odp.: dostanu ji jako rozdíl nejpozději přípustného výskytu a nejdříve možn