Problema de transport este un caz particular sau un anumit caz ZLP sarcini de optimizare a rețelei aplicate în soluția de transport sarcinilor de selecție rutei planificate. Forma generală este formulată după cum urmează. Să luăm în considerare m furnizori diferiți (puncte de plecare) Pi, care au unele produse omogene în cantitățile Ai, respectiv. iar trimiterea acestor produse la n puncte de consum Qj este luată în considerare. j =. ale căror nevoi sunt egale cu bj, respectiv. Cunoscând ratele de transport al produsului de la punctul Pi la punctul Qj (costul unităților de transport de marfă) ij. Este necesar să se compileze un astfel de plan de transport astfel încât costul total al costurilor să fie minim.
Pentru această sarcină, este posibil să se completeze restricțiile privind lățimea de bandă, existența unor puncte de resetare intermediare, a surselor și a chiuvetelor de marfă. Modelul matematic al acestei probleme are forma:
Xij - numărul de unități de marfă de la i la punctul j.
Având în vedere că această problemă este un caz special al APL, sunt luate în considerare modalități speciale de rezolvare a acestor probleme.
Tabela de transport a problemei arată astfel:
Problema transportului are o soluție dacă Σai = Σbj (model închis).
Dacă Sai <∑bj. то вводят фиктивный пункт производства, и не все пункты в оптимальном решении будут удовлетворены в потребности.
Dacă Σai> Σbj, atunci nu toate stocurile vor fi exportate din punctele de producție, în soluție introduce un punct fictiv de consum. Rețineți că volumul de ieșire din punctul fictiv este egal cu diferența # 9474; Σai -Σbj # 9474;
Un ciclu dintr-o masă de transport este o linie închisă închisă care îndeplinește următoarele condiții:
1. Toate vârfurile poliliniei se află în celulele mesei de transport.
2. Marginile sunt dispuse în rânduri sau coloane, dar nu în diagonale.
3. La fiecare vârf există 2 margini: una - pe o linie, alta - pe o coloană a unei mese de transport.
4. Un set de celule într-o masă de transport este considerat a fi aciclic dacă nu există niciun ciclu, toate nodurile căruia se află în celulele acestui set.
Teorema. O soluție acceptabilă a problemei de transport este sprijinul, adică. setul de celule umplut este aciclic, adică conține celule m + n-1.
Definiția. Potențialul soluției de sprijin # 945; Problema de transport este numărul Ui. Vj j =. astfel încât Ui + Vj = Cij este rata celulei umplute.
Teorema (o condiție suficientă pentru optimitatea unei soluții de sprijin). Dacă pentru toate celulele neinchise (i, j) Ui + Vj = Cij. unde Ui și Vj sunt potențialele soluției de suport Această soluție de suport este optimă.
Metode de construire a soluțiilor de suport:
1. Metoda din colțul nord-vestic. Începem să umplem celula (1,1) - colțul nord-vestic al mesei, fie satisfăcând nevoia, fie epuizând rezervele în acest moment. Apoi, trecem la următoarea coloană sau rând, care depinde de disponibilitatea nevoilor și stocurilor, mergând ca și cum pe diagonala mesei, terminăm umplerea celulei (m, n), obținând o soluție de sprijin.
2. Metoda elementului minim. Dintre toate celulele, alegeți celula cu cel mai mic tarif Cks și începeți să umpleți din această celulă fie satisfăcând nevoia fie epuizând rezervele (dacă există mai multe astfel de celule, apoi completați toate aceste celule). Apoi continuăm să umplem celulele cu tarife mari, până când epuăm complet proviziile sau satisfacem cererea.
Metoda aproximării lui Fogel. La orice iterație găsim pentru toate rândurile și toate coloanele diferența dintre cele două tarife minime și le scriem într-un rând și coloană speciale ale tabelului. Printre diferențele pe care le alegem minimul. În rândul sau coloana care corespunde acestei diferențe, găsim tariful minim și umplem celula cu acest tarif la această iterație, fie epuizând rezervele, fie satisfăcând nevoile. Dacă tariful minim este același pentru mai multe celule ale rândului sau coloanei selectate, selectați celula care se află în coloană sau rând, respectiv, cu cea mai mare diferență dintre cele două tarife minime pentru acea coloană sau rând.
Notă: Dacă celulele umplute s-au dovedit a fi mai mici decât m + n-1, atunci în unele celule "0" este atașat la unele celule, astfel încât numărul total de celule umplutură devine m + n-1.
Algoritm pentru rezolvarea problemei de transport prin metoda potențialului.
1. Construiește o soluție de susținere a problemei de transport prin cele trei metode descrise mai sus. Pentru fiecare soluție de referință, găsiți valoarea funcției obiectiv și opriți-o la cea pentru care această valoare este minimă.
2. Găsiți potențialul celulelor umplute.
3. Pentru celulele goale verificați condiția de optimitate. Dacă condiția de optimitate este îndeplinită, atunci soluția obținută este optimă.
4. În caz contrar, alegeți celula (k, s) pentru care Uk + Vs> Cks și construiți ciclul tabelului de transport, atribuind semnul "+" celulei și alternând semnele din toate celelalte celule ale ciclului.
5. Re-calculăm tabelul conform următoarei reguli. Este necesar să selectați numărul r = min xij din celulele ciclului marcat cu semnul "-". În celulele ciclului marcat cu semnul "+", adăugați acest număr. În celulele ciclului marcat cu semnul "-", acest număr este scăzut. Celulele rămase ale ciclului nu se schimbă și celula în care a fost găsit r nu este umplută.
6. Vom reveni la punctul 2.
Un exemplu. Rezolva problema transportului
Articole similare
Trimiteți-le prietenilor: