Celočíselné programování

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958.

Úloha[editovat | editovat zdroj]

Ú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ř.:

Metody řešení[editovat | editovat zdroj]

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 | editovat zdroj]

  • Jan Pelikán: Diskrétní modely v operačním výzkumu, Professional Publishing, Praha 2001

Externí odkazy[editovat | editovat zdroj]