Explicarea substanțială a problemei. În asociație există n mașini capabile să transporte Qi tone de încărcătură pe lună (i = 1,2, ..., n) pe lună. Cu ajutorul lor este necesar să se asigure transportul de mărfuri (cherestea, șuruburi etc.) de la furnizori către consumatori pe n trasee în cantitate de tone Rj pe lună (j = 1,2, ..., n).
Sarcina este de a transporta toate încărcăturile cu costuri minime, pentru aceasta trebuie să porniți fiecare mașină una câte una și numai traseul acesteia. Dacă capacitatea mașinii de a transporta mărfuri este mai mică decât necesitățile consumatorului de această încărcătură, atunci mașina nu poate fi alocată acestui traseu. Prin urmare, o matrice C, care caracterizează costurile mașinii i, este compilată, în cazul în care este atribuită rutei j.
Metoda maghiară de rezolvare a problemelor de atribuire
Algoritmul metodei maghiare.
Sarcina de atribuire este un caz special al sarcinii de transport. astfel încât să o rezolvi puteți folosi orice algoritm de programare liniară, dar mai eficientă este metoda maghiară.
Caracteristicile specifice ale sarcinilor de atribuire au servit drept scuză pentru apariția unei metode maghiare eficiente pentru soluționarea lor. Ideea de bază a metodei ungare este de a trece de la valoarea inițială a unei matrice pătratică C a matricei echivalente cu elemente non-negativ se și n zerouri de sistem independent, dintre care două nu aparțin aceluiași rând sau aceeași coloană. Pentru un n dat, există n! soluții admise. Dacă matricea de alocare unitățile X n poziționate astfel încât fiecare rând și coloană este o singură unitate, aranjate conform aranjate matrice zero, valoarea echivalentă n independent Se, vom găsi soluții acceptabile problema de atribuire.
Trebuie avut în vedere faptul că pentru orice alocare inacceptabilă, valoarea corespunzătoare este presupusă în mod condiționat ca fiind egală cu un număr suficient de mare M în probleme la un nivel minim. Dacă matricea originală nu este pătrată, trebuie să introduceți numărul necesar de rânduri sau coloane și să atribuiți elementele elementelor determinate de condițiile problemei, eventual după reducere, iar alternativele dominante sunt scumpe sau ieftine pentru a exclude.
Articole similare
Trimiteți-le prietenilor: