1.1 Modelul matematic al problemei de transport (TOR)
Să presupunem că există puncte de plecare A1, A2, ..., Am. în care există o sarcină uniform în cantități a1, a2, ..., AM cootvetstvenno și n destinații B1, B2, ..., Bn. ale căror nevoi în această încărcătură sunt egale cu b1, b2, ..., bn. Cij este cunoscut pentru costul transportului unei unități de marfă de la punctul de plecare i până la punctul de consum j. Este necesar de a face planul de transport, astfel încât stocurile de fiecare furnizor ar fi eliminate, cererea fiecărui client este îndeplinită, iar valoarea totală a tot traficul a fost minimă.
Numărul de celule de bază
m + n-1 = 3 + 4-1 = 6.
Notă. Atunci când găsirea planul inițial de transport este un caz de degenerării, ca urmare a valorilor de calcul xij se dovedește că la punctul nevoile Bj sunt îndeplinite și rezerve Ai punctul epuizat. Apoi, atât rândul, cât și coloana sunt eliminate din considerare în același timp. Se recomandă introducerea așa-numitului zero de bază într-una din celulele rândului și coloanei de ieșire (de preferință în celulă cu cel mai mic cost). Această celulă este considerată de bază (este scrisă 0), iar numărul total de celule de bază rămâne egal cu m + n -1.
1.3.2 Metoda elementului minim
Planul inițial de transport primit printr-o metodă dintr-un colț nord-vest nu depinde de costul lor și, prin urmare, în cazul general este departe de cel mai bun. Metoda elementului minim ia în considerare costul transportului. Planul inițial corespunzător permite furnizarea costului total de transport, care este mai aproape de cel optim.
În această metodă, conform formulei (11), celulele cu cel mai mic cost de transport sunt umplute succesiv. Dacă există mai multe celule cu cea mai mică valoare, atunci oricare dintre ele este aleasă.
Exemplul 2. Gasiti planul initial de transport in TOR folosind metoda elementului minim.
Se scrie matricea de transport (tabelul 1.3).
Tabelul 1.3.
Metoda potențialului este o metodă care asigură îmbunătățirea planului inițial de transport. În același timp, există o tranziție de la un plan de transport la altul (de la o matrice de transport la alta), până când reducerea costurilor totale de transport devine imposibilă.
7. Pentru celulele libere găsim sumele potențialelor corespunzătoare, le plasăm în matricea din colțul din dreapta jos al celulelor libere.
8. Pentru celulele libere, verificăm îndeplinirea condiției de optimitate: pentru. Pentru celulele (1.4) și (2.1), condiția nu este îndeplinită.
9. Pentru celulele libere, construim ciclul desemnat.
10. Facem o schimbare de-a lungul ciclului pe celula (2,1) devine baza. și celula (1,1) este liberă.
11. Continuăm la pasul 2 al algoritmului metodei potențiale.
12. Construim o nouă matrice de transport.
Pentru celula liberă (1.4), condiția de optimitate nu este îndeplinită. Construim un ciclu desemnat pentru aceasta, realizăm un schimb de ciclu pe celulă (1.4), devenind baza. celula (2,4) - liberă. Construim o nouă matrice de transport.
13. Continuați cu pasul 2 al metodei potențiale:
Pentru toate celulele libere
Planul rezultat este optim:
Cu acest plan, costul de transport:
metode de soluționare a problemelor de transport
2Soluția problemei transportului. Metoda din colțul nord-vestic
Există 3 furnizori de produse lactate - compania „Wimm-Bill-Dann“, SA „Petmol“ și SRL „Piskarevskiy“ - și produse omogene patru consumatori: SA „Lenstroikeramika“ pentru angajați pentru munca grea, periculoase, „Agrotorg“ SRL pentru continuare revânzare către public, Grupul CJSC TANDER și OJSC DIXY pentru revânzarea ulterioară către public.