Matematické Fórum

nordec · 12. 03. 2011 18:19

Ahoj, nějak si nejsem jistý svým řešením, a tak prosím o zkontrolování. Máme najít Hamiltonovskou kružnici s nejkratší délkou pro ohodnocený graf G = (V,E,c), kde c je délka hrany. A řešení formulovat jako úlohu celočíselného lineárního programování.

Mé řešení: minimalizovat $\sum_{i=0}^{n}{c_{u_iu_{i+1}}}$ , (kde $n \in N$ je počet vrcholů, $u \in V$ vrchol, $c_{u_iu_{i+1}}\in Z$ délka hrany z i-tého do i+1. vrcholu a nultý je zároveň n-tým vrcholem)

za podmínek $c_{u_iu_{i+1}}\le c_{u_iv}+c_{vu_{i+1}}$ (kde $v \in V$ )
$c_{u_iu_{i+1}}> 0$

Díky.

Matematické Fórum

#1 12. 03. 2011 18:19

Lineární programování

Zápatí