Celočíselné programovanie

Celočíselné programovanie je odvetvie optimalizácie, prvá úloha celočíselného programovania bola riešena v roku 1958.

 Úloha 
Úlohou celočíselného programovania je optimalizačná úloha

navyše s podmienkou, že premenné nadobúdajú len celočíselné hodnoty. Ak niektoré z premenných môžu nadobúdať hodnoty neceločíselné, ide o úlohu zmiešanú.

Najčastejší typ: lineárneho celočíselného programovania, ktoré rieši úlohu

pričom:
  označuje skalárny súčin vektorov c, x
 množina prípustných riešení M je popísaná sústavou

 kde A je matica rozmeru m × n, b je m-rozmerný vektor a c, x sú n-rozmerné vektory. Súčin Ax označuje súčin matíc.  C ⊆ {1,…,n} je množina indexov premenných, ktoré majú byť celočíselné.

Patrí sem napr.:
 problém obchodného cestujúceho
 problém batohu

 Metódy riešenia 
Metódy riešenia celočíselného programovania:
 metódy sečných nadrovín (metóda rezov): riešime úlohu bez podmienok celočíselnosti. Ak je získané optimálne riešenie neceločíselné, potom odrežeme kus množiny prípustných riešení M, obsahujúcu bod x, ale v ktorom neleží žiadny celočíselný bod. Postup opakujeme až nájdeme celočíselné riešenie (pre niektoré konkrétne algoritmy je konvergencia zaručená).
 metóda vetvenia a medzí (branch & bound): úlohu rozdelíme na dve podúlohy a riešime rekurzívne.

Pre lineárne celočíselné programovanie existujú ďalšie špeciálne algoritmy (Gomory,…).

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

 Externé odkazy 
 http://cam.zcu.cz/~ryjacek/students/ps/TGD2.pdf  (str 43 – 56)
 http://dce.felk.cvut.cz/rdu/rozvrhovani/download/rdu_c1.pdf (užitočné odkazy)
 http://www1.osu.cz/studium/mopv2/celocis 
 http://www.fhi.sk/files/katedry/kove/predmety/Linearne_programovanie/Fendek/LP_Int_progr_ii.pdf (Gomoryho algoritmus)

Kategória:Matematická optimalizácia
Kategória:Programovanie