Sarcina vânzătorului de călătorie online

În sarcina vânzătorului care călătorește, pentru a forma ruta optimă de by-pass pentru n orașe, trebuie să alegeți una dintre cele mai bune dintre (n-1)! Variante după criteriul timpului, costului sau lungimii rutei. Această problemă este legată de definirea unui ciclu Hamiltonian de lungime minimă. În astfel de cazuri, setul tuturor soluțiilor posibile ar trebui prezentat sub forma unui grafic conectat la arbore, fără bucle și bucle. Rădăcina copacului îmbină întregul set de variante, iar vârfurile copacilor sunt subseturi de soluții parțial comandate.







Instrucțiuni. Selectați dimensiunea matricei (numărul de orașe). Soluția online recepționată este salvată într-un fișier Word și Excel (a se vedea exemple de soluții de călătorie pentru vânzători).

Modelul matematic al problemei vânzătorului călător

Problema formulată este o problemă cu numere întregi. Fie xij = 1. dacă călătorul se mută din orașul i în j-th și xij = 0. dacă nu este.
În mod formal, introducem (n + 1) un oraș situat în același loc ca primul oraș, adică Distanța de la ora (n + 1) la oricare altul, diferită de prima, este egală cu distanța de la primul oraș. În acest caz, dacă puteți ieși numai din primul oraș, atunci în (n + 1) orașul poate veni numai.






Vom introduce variabile intregi suplimentare egale cu numărul de vizite în acest oraș pe drum. u1 = 0, un + 1 = n. Pentru a evita căile închise, pentru a părăsi primul oraș și a ne întoarce la (n + 1), introducem constrângeri suplimentare care conectează variabilele xij și variabilele ui. (ui sunt numere întregi nonnegative).


ui -uj + nxij ≤ n-1, j = 2..n + 1, i = 1..n, i ≠ j, pentru i = 1 j ≠ n + 1
0≤ ui ≤ n, xin + 1 = xi1. i = 2..n

Metode pentru rezolvarea problemei vânzătorului călător
  1. metoda de ramificații și limite (algoritmul lui Little sau eliminarea sub-ciclurilor). Un exemplu de soluție filială și obligatorie;
  2. Metoda maghiară. Un exemplu de soluție este metoda maghiară.

Un exemplu. Ca traseu inițial, este aleasă oricare, de exemplu, X0 = (1,2), (2,3), (3,4), (4,5), (5,6), (6,1). Estima pentru această rută este F (X0) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Pentru a determina limita inferioară a setului, utilizați operația 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. Lungimea rutei este determinată de expresia: F (Mk) = Σdij. Și fiecare linie și coloană introduceți ruta o singură dată cu elementul dij.

Apoi, în timpul iterațiilor ulterioare, marginea ramurii este determinată. Întregul set de rute relative la această margine este împărțit în două subseturi (i, j) și (i *, j *).

Regulile de introducere a datelor

Adresați-vă întrebările sau lăsați-vă dorințele sau comentariile în partea de jos a paginii în secțiunea Disqus.
De asemenea, puteți lăsa o solicitare de ajutor în rezolvarea activității de control cu ​​partenerii noștri de încredere (aici sau aici).







Articole similare

Trimiteți-le prietenilor: