OPTPV_20141202 02

Zhrnutie prednášky

Prednáška nadväzuje na tému binárnej a celočíselnej optimalizácie a na príklade plaveckého tímu vysvetľuje pojem permutačnej matice, ktorá má v každom riadku aj stĺpci práve jeden nenulový prvok. Tento koncept sa prepája s problémom obchodného cestujúceho ako klasickým NP-ťažkým problémom, pri ktorom sa diskutuje otázka P=NP, zložitosť riešenia (n faktoriál) a jej súvislosť s kryptografiou. Porovnáva sa polynomiálna zložitosť lineárnych a kvadratických programov s exponenciálnou zložitosťou NP-ťažkých úloh. V druhej časti sa predstavuje problém umiestnenia skladu (facility location problem), kde sa formulujú spojité premenné (množstvo dodaného tovaru) a binárne premenné (otvorenie skladu), spolu s konštantami ako dopyt, fixné náklady a kapacita skladu. Na záver sa začína zostavovať účelová funkcia minimalizujúca súčet prepravných a fixných nákladov.

• - Permutačná matica má v každom riadku a stĺpci práve jeden nenulový prvok.
• - Problém obchodného cestujúceho je klasický NP-ťažký binárny optimalizačný problém.
• - Otázka P=NP zostáva nevyriešená a súvisí s bezpečnosťou šifrovacích algoritmov.
• - Lineárne a kvadratické programy majú polynomiálnu zložitosť, NP-ťažké problémy exponenciálnu (2^n alebo n!).
• - Existujú aproximačné algoritmy dávajúce približné, nie optimálne riešenia NP-ťažkých úloh.
• - Problém umiestnenia skladu kombinuje spojité premenné (množstvo tovaru) a binárne premenné (otvorenie skladu).
• - Cieľová funkcia minimalizuje súčet prepravných nákladov a fixných nákladov na prevádzku skladov.

Zhrnutie pripravené s pomocou AI z prepisu videa.