Matematické Fórum

Zdravim,

predem bych se chtel omluvit, pokud sem toto tema nepatri. Ale s ohledem na to, jakym zpusobem linearni programovani pracuje, mi to neprijde jako ryze algoritmicky problem a tak doufam, ze i v matematicke casti tohoto fora najdu nekoho, kdo bude schopen o tomto diskutovat.

Ted k veci, pripravuji se na zkousku a nemuzu stale prijit na to, jakym zpusobem transformovat primarni ulohu problemu batohu a primarni ulohu problemu rozvrhu nedelitelnych uloh na procesorech.

O co jde, u problemu batohu mam mnozinu predmetu, ktere maji svou vahu a hodnotu, v_i a h_i, s tim, ze existuje vahovy limit V.

Jako primarni uloha bude tento problem zapsan relativne trivialne a to tak, ze si zavedu 0/1 promennou x_i znacicic, zda je polozka vybrana a ucelova funkce bude maximalizovat vahu vybranych predmetu.
Omezeni bude pak takov,e ze soucet vsech vybranych predmetu musi byt nejvyse roven V.
Dale bude promenna x_i omezena na hodnotu 0 a 1. Relaxaci ulohy pak pouze povolim, aby h_i nabyvala hodnoty intervalu 0..1

Nemuzu ale zatim prijit na to, jak tento tvar ulohy prepsat na dualni ulohu.
Napadlo me, ze by ucelova funkce byla minimalizace hodnoty V nasobene nejakou promennou y. A omezeni by pak bylo, ze v_i v soucinu s y musi byt vetsi h_i, ale to mi prijde jako nesmysl.

DIky za vase komentare. Pokud by se objevil nekdo, kdo by teto problematice rozumel, tak bych pak rozebral vice i ten problem procesoru a uloh.