"O celulă cu un tarif minim este aleasă și umplută cu numărul maxim posibil, în timp ce stocurile sau cerințele sunt epuizate (se șterge un rând sau o coloană), se selectează celula următoare cu un tarif minim, etc.
c) Metoda de aproximare Vogel.
Pentru a umple fiecare celulă, trebuie să găsiți diferențele dintre cele două tarife minime pentru toate coloanele și rândurile și să le scrieți în jos, respectiv, în partea de jos și din dreapta tabelului. Dintre diferențele găsite, alegeți maximul. În rândul (sau coloana), care corespunde acestei diferențe, umpleți celula cu tariful minim. În cazul în care diferențele maxime sunt oarecum la fel, alegeți unul la care corespunde tariful minim. Dacă tariful minim este același pentru mai multe celule într-un rând (coloană), atunci completați cea din coloana (rândul) având cea mai mare diferență dintre cele două tarife minime.
De regulă, atunci când construim planul de suport prin aceste trei metode, se aplică următoarea relație: Fb (x) Fb (x) Fα (x).
1. Creați un plan de sprijin prin una dintre metode.
Programul de suport construit trebuie verificat pentru optimitate, pentru care se folosește următoarea teoremă.
Teorema. Dacă pentru un anumit plan de suport al problemei de transport există astfel de numere și. că
pentru toți și, atunci acest plan este optim.
DEFINIȚIA 4. Numerele și (,) se numesc potențialul furnizorilor și consumatorilor.
astfel găsirea potențialului furnizorilor și consumatorilor care satisfac condițiile teoremei, demonstrăm optimitatea planului construit. Cum să le găsiți? pentru că numărul de celule umplut, xij> 0, este egal cu n + m-1 (plan nedegenerat), apoi sistemul (4) cu n + m necunoscute conține ecuația n + m-1. Am pus unul dintre necunoscuți egal cu zero și găsim succesiv valorile celor necunoscute. Apoi, pentru toate celulele libere, xij = 0, definim numere.
Dacă între numere nu există pozitive, atunci condițiile teoremei sunt îndeplinite, iar planul este optim. Dacă există un> 0, atunci planul construit nu este optim și ar trebui îmbunătățit.
Algoritm pentru îmbunătățirea planului:
1) între toate> 0 este aleasă maximul;
2) un ciclu de recalculare este construit pentru celula corespunzătoare;
3) marcați succesiv vârful ciclului de conversie cu semnele "+" și "-". începând cu "+" în celula sursă;
4) printre numerele care stau în celulele etichetate "-". determinarea minimului;
5) la valorile din celulele "+", adăugați acest număr minim și din valorile din celulele "-", acest număr este scăzut.
DEFINIȚIE 5. Ciclul de recalculare este o linie întreruptă a cărei vârfuri sunt situate în celulele ocupate, iar legăturile sunt de-a lungul rândurilor și coloanelor, iar la fiecare vârf al ciclului pot exista doar două legături.
Planul astfel modificat este verificat din nou pentru optimitate, adică trecerea la punctul 2.
3. Metoda chiriilor diferențiale
Spre deosebire de metoda potentialelor la care se face referire este mai întâi construită din, în mod succesiv și apoi a fost îmbunătățită, o metodă de rezolvare a problemei diferențiale chiriile imediat cel mai bine repartizat între consumatorii de produse și în editările ulterioare reduce treptat valoarea totală a ofertei nealocată.
Pentru a determina soluția problemei de transport prin metoda roții diferențiale, se folosește următorul algoritm:
În fiecare coloană se determină tariful minim și se selectează celula corespunzătoare.
2. Celulele alocate sunt umplute cu numerele maxime posibile.
3. Deoarece în general, această distribuție nu satisface toți consumatorii, pentru a reduce cantitatea de nevoi nesatisfăcute în etapele ulterioare, este necesar să se evalueze furnizorii.
DEFINIȚII 6. Liniile corespunzătoare furnizorilor ale căror stocuri au fost epuizate și nevoile consumatorilor alocați nu sunt satisfăcute sunt negative.
DEFINIȚII 7. Linii corespunzătoare furnizorilor ale căror stocuri nu sunt complet epuizate sunt pozitive.
DEFINIȚII 8. Linia corespunzătoare furnizorilor ale căror stocuri au fost epuizate și nevoile consumatorilor alocați sunt satisfăcute și au un rating zero. În acest caz, dacă cea de-a doua celulă umplută, aflată în coloana asociată cu rândul dat cu o altă celulă umplută, este situată în linia pozitivă, această linie nominală zero este considerată pozitivă. Altfel, este negativ.
4. Pentru fiecare coloană care are un tarif dedicat liniei negative, se găsesc diferențele dintre tariful selectat și cel mai apropiat tarif din linia pozitivă.
5. Dintre diferențele obținute, se determină minimul. Acest număr se numește chirie intermediară.
6. Se construiește un nou tabel, în timp ce tarifele în linii pozitive sunt suprascrise fără schimbare, iar tarifele în linii negative cresc cu suma chiriei intermediare.
7. Mergeți la pasul 1.
NOTĂ: a) dacă există mai mult de o celulă selectată într-un rând sau într-o coloană, completați, mai întâi, acele celule selectate care sunt singurele dintr-o coloană sau rând;
b) dacă este posibilă distribuirea tuturor rezervelor, se obține un plan optim al sarcinii de transport.
4. Constrângeri suplimentare ale sarcinii de transport
1. Căi interzise.
Dacă, din orice motiv, este imposibil să furnizăm produse de la așezarea Ai la Vj. rata acestei căi se presupune a fi în mod arbitrar mare, M, cij =
Trimiteți-le prietenilor: