Nie mogę załapać jednej rzeczy z wykładu. Jeżeli komiwojażer wyrusza z miasta \(\displaystyle{ 1}\) i ma odwiedzić \(\displaystyle{ n-1}\) miast i mam daną macierz odległości między miastami \(\displaystyle{ d _{ij}}\), oraz zmienne binarne \(\displaystyle{ x _{ij}}\), które mówią czy idzie bezpośrednio z miasta \(\displaystyle{ i}\) do miasta \(\displaystyle{ j}\). Problem w tym, że aby uniknąć cykli nie zawierających wierzchołka \(\displaystyle{ 1}\) mam użyć nierówności:
\(\displaystyle{ y _{i}-y _{j}+nx _{ij} \le n-1}\)
Nie za bardzo wiem, co te ograniczenia mówią. Jeżeli ktoś wie, proszę o wyjaśnienie.
Problem komiwojażera
-
matfka
- Użytkownik
- Posty: 181
- Rejestracja: 19 sty 2013, o 11:45
- Płeć: Kobieta
- Lokalizacja: polska
- Podziękował: 31 razy
- Pomógł: 3 razy
Problem komiwojażera
\(\displaystyle{ y \in Z ^{n}, i,j=2,...,n}\)
A czemu te \(\displaystyle{ y}\)-ki odpowiadają właśnie nie wiem. Myślałam, że może ktoś korzystał z takich ograniczeń i pomoże...
A czemu te \(\displaystyle{ y}\)-ki odpowiadają właśnie nie wiem. Myślałam, że może ktoś korzystał z takich ograniczeń i pomoże...