pod tym linkiem http://en.wikipedia.org/wiki/Travelling_salesman_problem punkt 3.Integer linear programming formulation
jest tam pare wzorów, może mi ktoś powiedzieć co to jest to u?? tam jak mamy ui - uj, cała reszte wiem i tylko tego niewiem
0
0
? Przecież wikipedia linkuje do opisu:
http://en.wikipedia.org/wiki/Integer_programming
To jest w pewnym sensie redukcja problemu komiwojażera to problemu ILP. Oba są NP-zupełnie więc można taką redukcję wielomianową przeprowadzić. Można ją tez przeprowadzić z dowolnego innego problemu NP-zupełnego (chociaż czasem jest to dość skomplikowane). To jest sposób pokazania w jaki sposób rozwiązać problem X znając rozwiązanie problemu Y. Problemy NP-zupełne mają to do siebie że muszą się wszystkie do siebie redukować, więc rozwiązanie jednego z nich pozwoliłoby na rozwiazanie wszystkich.
0
No to czym jest to u??
Mam zadanko, narysowany graf, wypisana funkcja celu i ograniczenia, wszystko wiem skąd się wzięło, poza ograniczeniami w których jest u, bo nie wiem czym jest to u
0
http://support.sas.com/documentation/cdl/en/ormpug/63352/HTML/default/viewer.htm#ormpug_milpsolver_sect020.htm
Tu masz napisanie skąd to wzięli.
0
Nie możesz napisać wprost?? Ja już widziałem to, i takie tekstu nie przeczytam po angielsku, a po polsku nigdzie nie mogę znaleźć, więc napisałem na forum.
0
Ok, lepiej niż tu: http://www.math.uwaterloo.ca/tsp/methods/opt/subtour.htm nie znalazlem tego opisanego.
To jest warunek na to żeby nie rozpatrywać sytuacji gdy liczymy sobie wesoło rozwiazanie TSP dla kawałka grafu, a to rozwiazanie jest bez sensu bo nie ma mozliwości dołączenia go do reszty grafu.
To this end, we know that any tour will contain at least two roads going between the two clusters. We can therefore add a constraint that states that the sum of the corresponding variables must be at least two.
More generally, let S be any collection of cities having at least 2 and at most n-1 members (that is, S cannot be the entire set of cities in the TSP) and let T denote the remaining cities. To forbid the subtour through the cities S, we can add condition that the sum of the variables corresponding to roads from S to T must be at least 2.
Chodzi o to że pomiędzy dwoma dowolnymi podzbiorami miast muszą być przynajmniej 2 drogi.