Metode economico-matematice
În aceste condiții, este necesar să se determine planul de aprovizionare directă de cereale de la punctele de producție la lifturi, în care toți vânzătorii au luat de cereale disponibile pentru silozuri de cereale, capacitate de silozuri ar fi complet încărcate, iar valoarea totală a costurilor de transport de cereale ar fi minim.
Sarcina poate fi ușor redusă la așa-numitul One marfă (cereale) modele clasice de transport, pentru care există soluții mai multe metode, dintre care unul este descris mai jos.
Declarația formală și notația matematică zadachi.Dano:
m - numărul de puncte de producție (i = 1,2 m.);
n - numărul de puncte de consum (j = 1,2 n.);
ai - suma de ieșire în punctul i-lea (i = 1,2 m.);
bj - cerere solvent pentru produse în paragraful j-a (j = 1,2 n.);
CJI - costul unității de producție directe furnizează elementul i-lea în producția de j-lea punct de consum.
Doriți să găsiți un plan de livrări directe, în care costurile totale de transport vor fi minime.
Să Hij prin livrarea de la producător la utilizator j -lea i -lea.
Este evident că problema se reduce la a găsi valorile Hij, oferind un cost total minim:
Să presupunem că există un echilibru cerere-ofertă:
Apoi, constrângerile de sarcini poate fi scris ca:
În cazul în care se încalcă echilibrul (3.2). Puteți introduce un volume suplimentare de producători sau de diferențele de consum de producție și de consum fictive, stabilind valoarea de a comunica cu el la zero.
Spre deosebire de constrângerile generale program liniar de transport problemă consistentă o mulțime de planuri este limitat și, prin urmare, această problemă este întotdeauna rezolvabilă.
Rețineți că m + n constrângeri (3.3) - (3.4) sunt liniar dependente, iar una dintre ele pot fi neglijate. Prin urmare, planul problemă de transport de referință nu poate conține mai mult m + n 1-componente pozitive. Programele de sprijin, care reprezintă mai puțin de m pozitiv + n-1. Ei au numit degenerat.
3.2. Soluție de J. Danzig
După verificarea modelului închis (balanța cererii și ofertei agregate), se procedează la alegerea programului de sprijin inițial. Ghidat de regula: următoarea rută selectat setat transport maxim admisibil. epuizează stratul de astfel capacitatea furnizorului sau a consumatorului.
Esența uneia dintre metodele de căutare ale programului de sprijin inițial - metoda colțul de nord-vest. Începem cu „colțul de nord-vest a“ „tabla de șah“, adică celule cu (1,1) și ia = min X11 (a1, b1) = min (5,5) = 5 (posibila transport maxim cu cerere și ofertă corespunzătoare). Este evident că, atunci când X12 = X13 = X14 = 0 și X21 = X31 = 0. Ia colțul de nord-vest al matricei din rândul și coloana excluse, adică, celula (2,2), și găsesc X22 = min (a2, b2) = min (8,5) = 5. Este evident că atunci când X32 = 0. Apoi căutăm X23 = min (a2 -X22, b3) = min (8-5,5) = 3 și X24 = 0. Ca restante de doar o componentă a planului de linie, ordinea de selecție nu contează și pentru a obține valorile X33 și X34.
Conform acestei teoreme, în cazul planurilor optime în fiecare pereche de condiții duble Xij i 0, + vj £ UI ij> condiție, inegalitatea strictă, condițiile adecvate sunt îndeplinite în calitate de egalitate strictă.
Prin urmare, optimalitatea este formulat după cum urmează: un plan de transport valabil, și numai atunci este optim atunci când fiecare element de producție și de consum poate fi asociat cu evaluarea (variabile duale), următoarele două condiții:- numărul de puncte de voturi de producție (UI) și consum (VJ), între care transportul planificat este costul unitar al transportului produsului (CJI) între aceste puncte, adică
Cu ajutorul testului optimalităii formulat poate verifica nu numai pentru optimalitate orice plan valabil, dar și în cazul metodei nu-punct pentru îmbunătățirea planului.
Referindu-ne la exemplul avem în vedere:
Criteriul de optimalitate al problemei (D ij = + vj -Cij ui J 0) nu este îndeplinită; Prin urmare, nu a găsit planul optim și este recomandabil să meargă la celălalt sprijinirea planului. mai aproape de optim.
D ij Valorile negative indică faptul că transportul conform instrucțiunilor dezavantajoase (pentru fiecare unitate de produs transportabil pot suferi pierderi, în comparație cu planul de referință precedent, la ij valoare D). În celulele unde D ij> 0. Pe de altă parte, efectul poate fi obținut în D ij cantitatea pe unitatea de transport.
În exemplul nostru, o astfel de celulă 34 D = +2. Determinarea volumului ofertei în cușcă, ar trebui să fie ghidate de următoarele considerente:
· Punerea în ea o anumită cantitate de transport ar trebui să se scadă aceeași sumă de la alte celule ocupate, să nu perturbe raporturile de bilanț, de import și export;
· Numărul de celule incluse în noul plan de transport, ar trebui să rămână neschimbate (unul mai puțin decât numărul total de furnizori și clienți). Prin urmare, în loc de celule a mers în jos unul din planul anterior de transport de celule ar trebui să fie excluse.
Ambele condiții sunt ușor de realizat, în cazul în care livrările pentru a efectua o redistribuire a „buclă închisă“.
Lăsați volumul de noi de aprovizionare este Q> 0. Sign «- Q» eticheta celulei din care se va deduce valoarea redistribuită semn de livrare «+ Q» - dimpotrivă. Valoarea dorită de aprovizionare redistribuit determina valoarea minimă a sta în celule cu semnul „minus“.
Deoarece toate valorile lui D ij nonpositive se poate afirma planul optim găsit. Comparativ cu primele costuri echivalentelor up au fost reduse cu 4 unități (L (X0) = 75 ® L (X1) = 71).
Prin modul în care, în cazul în care planul optim găsit va afișa un D ij valoare zero pentru orice „celule neocupate“ (componenta nonground), indică faptul că există alte planuri optime (de tranziție la planul, care este egală cu Q. componentei corespunzătoare nu însoțite de modificări în valoarea funcției obiectiv , QD ij = 0).
3.3. Modificări ale problemei de transport
Problema numirii personalului
Problema găsirii distribuției cu eficiența totală maximă conduce la problema, caracterizată printr-o maximizare cerința de transport a funcției obiectiv. În procesul de rezolvare a acestei probleme este suficient pentru a alege programul de sprijin inițial pentru o eficiență maximă și pentru a atinge valorile de destinație D IJ i 0.
Problema de transport într-un cadru de rețea
Problema apare atunci când rețeaua de transport cu noduri intermediare și constrângeri cu privire la capacitățile de comunicare. Aceste probleme sunt rezolvate prin tehnici mai sofisticate, cum ar fi celebrul „metoda maghiar“. pe baza relațiilor de dualitate.
Problema transportului în criteriul de timp
Aici criteriul optimalitate nu este legată de costul și timpul pentru a efectua trafic complexe (în caz de urgență pentru a efectua transferul de mărfuri în cel mai scurt timp posibil, indiferent de cost). Aceste obiective sunt atinse prin setarea din nou problema duală care implică algoritmul de căutare „debit maxim în rețelele de transport“ (același algoritm este folosit în metoda menționată unguresc) [1].
Acest grup de lucru pledează pentru un fel de prelungire a transportului problemă apare atunci când se fixează resursele în funcție de tipul de muncă, la stabilirea vehiculelor pentru rutele în pregătirea soldurilor de energie, în planificarea operațiunilor militare cu cea mai mare înfrângere obiectivelor în alocarea comenzilor între companii și așa mai departe. N.
Un exemplu de una dintre aceste probleme este problema.
Există m tipuri de vehicule în cantități Ai (i = 1 m). care trebuie să fie alocate n volum de trafic egal rute Bj (j = 1 n). Costurile de exploatare și volumul de trafic de un singur tip de mașină i-lea pe ruta j-lea sunt ij și lij. Necesar pentru a găsi distribuția cu costuri minime de operare.
problemă maximă de curgere
Considerăm rețeaua de transport, care pune în evidență elemente - surse (apa, petrol, gaze, autoturisme) și chiuvete (consumatori). Fiecare arc (segment) care conectează punctele i și j. Numărul mapate dij> 0. numit capacitate arc trecere - numărul maxim de agenți (apa, gaz, avioane, automobile, etc ...), care se poate întinde pe un arc de cerc corespunzător unitatea de timp. Necesar pentru a găsi debitul maxim în rețea (astfel încât să nu izbucni conducta la o presiune, modul de siguranță de mișcare, etc.).