Celočíselné programování
Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 17. srpna 2008
- Zobrazeno: 1993×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
Celočíselné programování
Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958.
Obsah |
Úloha
Úlohou celočíselného programování je optimalizační úloha
navíc s podmínkou, že proměnné nabývají pouze celočíselných hodnot. Pokud některé z proměnných mohou nabývat hodnot neceločíselných, jedná se o úlohu smíšenou.
Nejčastější typ: lineární celočíselné programování, které řeší úlohu
přičemž:
- cTx označuje skalární součin vektorů c, x
- množina přípustných řešení M je popsána soustavou
- kde A je matice rozměru m × n, b je m-rozměrný vektor a c, x jsou n-rozměrné vektory. Součin Ax označuje součin matic. C ? {1,…,n} je množina indexů proměnných, které mají být celočíselné.
Patří sem např.:
- problém obchodního cestujícího (viz [2])
- problém batohu
Metody řešení
Metody řešení celočíselného programování:
- metody sečných nadrovin (metoda řezů): řešíme úlohu bez podmínek celočíselnosti. Je-li získané optimální řešení neceločíselné, potom odřízneme kus množiny přípustných řešení M, obsahující bod x, ale ve kterém neleží žádný celočíselný bod. Postup opakujeme než nalezneme celočíselné řešení (pro některé konkrétní algoritmy je konvergence zaručena).
- metoda větvení a mezí (branch & bound): úlohu rozdělíme na dvě podúlohy a řešíme rekursivně.
Pro lineární celočíselné programování existují další speciální algoritmy (Gomory,…)
Pro úlohy kde A je totálně unimodulární matice lze s výhodou použít metody pro řešení úloh obecného lineárního programování.
Reference
- Jan Pelikán: Diskrétní modely v operačním výzkumu, Professional Publishing, Praha 2001