Celočíselné programování
odvětví optimalizace
Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958.
Úloha editovat
Úlohou čistého (ryzího) 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íšeného celočíselného programování (na rozdíl od čistého).
Nejčastější typ: lineární celočíselné programování, které řeší úlohu
přičemž:
- 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í editovat
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.
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 editovat
- Jan Pelikán: Diskrétní modely v operačním výzkumu, Professional Publishing, Praha 2001
