Problema agent de vanzari pentru formarea ruta de ocolire n orașe optime trebuie să aleagă cele mai bune de (n-1)! opțiuni pentru timpul criteriu, costul sau lungimea traseului. Această problemă este legată de definirea unui ciclu hamiltonian de lungime minimă. În aceste cazuri, trebuie furnizate setul tuturor soluțiilor posibile sub forma unui arbore - grafic conectat nu conține cicluri sau bucle. Rădăcina arborelui unește toate varietate de opțiuni, iar partea de sus a arborelui - un subset de soluții parțial comandate.
Instrucțiuni. Selectați dimensiunea matricei (numărul de orașe). Soluția rezultată este stocată online, în fișiere Word și Excel (a se vedea. Exemple de soluții problema comis-voiajorului).
Modelul matematic al problemei comis-voiajorului
Problema formulată - o problemă de întreg. Să hij = 1 în cazul în care se mută de călătorie de la al i-lea oraș din j-lea și Hij = 0. În cazul în care acest lucru nu este așa.
Formal, introducem orașul (n + 1) situate în același loc și primul oraș, adică distanța de la (n + 1) la oricare alt oraș, diferit de primul, egală cu distanța de la primul oraș. În acest caz, în cazul în care primul dintre oraș poate merge numai în (n + 1), orașul poate veni numai.
Noi introducem variabile întregi suplimentare egal cu numărul de pe acest oraș pe drum. u1 = 0, onu + 1 = n. Pentru a evita căile închise, pentru a iesi din primul din oraș și a reveni la (n + 1), introducem constrângeri suplimentare care leagă variabilele xij și variabile UI. (numere întregi). nenegative Ui
-uj + nxij ui ≤ n-1, j = 2..N + 1, i = 1..n i ≠ j, cu i = 1, j ≠ n + 1
0≤ ≤ n ui, xin + 1 = xi1. i = 2..N
- ramură și metoda legată (algoritm mic sau subcycles excepție). soluții EXEMPLU prin ramură și legat;
- Metoda maghiar. soluții EXEMPLU Metoda maghiar.
Exemplu. In fiecare exemplu, X0 = (1,2) este selectată ca calea principală, (2,3), (3,4), (4,5), (5,6), (6,1). Evaluarea pentru această rută este egal cu F (X0) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Pentru a determina este utilizat limita inferioara a operațiunii de reducere. pentru care fiecare rând al matricei D sunt elemente minime: di = min (j) dij
Suma constante de conducere definește limita inferioară a H = Σdi + Σdj = 9 + 52 + 13 + 17 + 8 + 10 + 0 + 20 + 0 + 5 + 0 + 0 = 134. Matricea Elementele dij corespund distanței de la punctul i la litera j. Traseul este definit prin expresia: F (Mc) = Σdij. Fiecare rând și coloană sunt incluse în traseu o singură dată cu dij elementul.
Apoi, în timpul iterații ulterioare, nervura ramură este determinată. Toate numeroasele trasee de pe acest coaste rupte în două subseturi (i, j) și (i *, j *).