Celočíselné programovanie

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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

Úloha[upraviť | upraviť zdroj]

Ú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, xn-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.:

Metódy riešenia[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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

Externé odkazy[upraviť | upraviť zdroj]