Matematické Fórum

Ahoj,

řeším následující problém s tvorbou omezujících podmínek. Mám tři činnosti (A,B,C) vybíhající z téhož uzlu daného grafu, které bude vykonávat tentýž pracovník. Nebudou tudíž vykonávány současně, ale za sebou. Do modelu je potřeba přidat podmínky, které vyjádří celkovou délku jednotlivých činností. Například, pokud pracovník vykoná činnosti v pořadí B,C,A, fakticky to znamená, že délka činnosti C se prodlouží o B a délka A se prodlouží o B+C. Z tímto účelem jsem vytvořil následující:

dA = A + B*p + C*(1-r)

dB = B + C*q + A*(1-p)

dC = C + A*r + B*(1-q)

V optimálním řešení pak budou stanoveny hodnoty binárních proměnných p,q,r.
Je-li např. p=q=1, pak:

dA = A + B + C,
dB = B + C,
dC = C.

Tedy pořadí vykonání činností je C,B,A. (C není prodloužena, B je prodloužena o C a A je prodloužena o B+C.)

Je jasné, že aby omezení dávala smysl, musí být délka jedné činnosti rovna "třem písmenům", druhé dvěma a třetí "jednomu písmenu". Např. takováto situace je nepřípustná:

dA = A + B,
dB = B + C,
dC = C + A.

To lze zajistit podmínkami:

p+q+r >= 1,
p+q+r <= 2.

Doposud je to snadné. Problém mám ale s formulací podmínek pro čtyři činnosti.


dA = A + B*p + C*(1-r) + D*s
dB = B + C*q + A*(1-p) + D*t
dC = C + A*rij + B*(1-q) + D*uij
dD = D + A*(1-s) + B*(1-t) + C*(1-u)

Mám poněkud problém se stanovením omezení pro binární proměnné p,q,r,s,t,u. Možností je totiž spousta a není to již tak snadné jako v předchozím případě. Napadá někoho nějaké elegantní řešení? Přijmu klidně i přeformulování podmínek pro délku činností. A nemám nic proti součinu proměnných, ten se dá snadno linearizovat (u bin. prom.).

Díky!