Matematici aplicate în economie · Optimizare liniară

Probleme de transport și de alocare

Avansat70 min

Pe această pagină

Ce înveți

  • Scrii o problemă de transport ca tabel de costuri, oferte și cereri și găsești o soluție inițială prin metoda colțului de nord-vest și prin metoda costului minim.
  • Verifici dacă un plan de transport este optim și îl îmbunătățești pe un ciclu de rute.
  • Rezolvi o problemă de alocare a sarcinilor prin metoda ungară.

Teorie

Multe decizii de zi cu zi ale unei firme sunt de forma „ce trimit unde” sau „cine face ce”: o brutărie care aprovizionează mai multe magazine, o firmă de curierat care împarte coletele între șoferi, un atelier care împarte lucrările între angajați. Ele sunt probleme de programare liniară cu o structură specială, pentru care există metode de rezolvare mult mai simple decât simplexul.

Partea 1. Problema de transport

Dacă notezi cu xijx_{ij} numărul de lăzi trimise de la laboratorul i la magazinul j și cu cijc_{ij} costul unei lăzi pe acea rută, modelul este:

min⁡C=∑i∑jcijxij,∑jxij=ai (oferta lui i),∑ixij=bj (cererea lui j),xij≥0\min C = \sum_{i} \sum_{j} c_{ij} x_{ij}, \quad \sum_{j} x_{ij} = a_i \ \text{(oferta lui i)}, \quad \sum_{i} x_{ij} = b_j \ \text{(cererea lui j)}, \quad x_{ij} \ge 0

În cuvinte: costul total este suma „lăzi × cost” pe toate rutele; tot ce iese dintr-un laborator este egal cu ce coace; tot ce intră într-un magazin este egal cu ce cere.

Dimensiunea problemei. Cu m furnizori și n beneficiari, modelul are m⋅nm \cdot n variabile (câte una pentru fiecare rută) și m+nm + n restricții. Una dintre restricții rezultă din celelalte (dacă știi că toate ofertele și primele n − 1 cereri sunt respectate, ultima cerere este respectată automat, pentru că totalurile sunt egale). De aceea un plan de bază folosește cel mult m+n−1m + n - 1 rute. Pentru brutărie: 6 rute posibile, 5 restricții, dintre care 4 independente.

Problema neechilibrată. Metodele de mai jos cer ca oferta totală să fie egală cu cererea totală. Dacă nu este așa, echilibrezi problema:

  • dacă ∑ai>∑bj\sum a_i > \sum b_j (se produce mai mult decât se cere), adaugi un beneficiar fictiv cu cererea ∑ai−∑bj\sum a_i - \sum b_j și costuri 0; lăzile trimise acolo rămân, de fapt, în laborator;
  • dacă ∑ai<∑bj\sum a_i < \sum b_j, adaugi un furnizor fictiv cu oferta ∑bj−∑ai\sum b_j - \sum a_i și costuri 0 (sau costul penalității pentru cererea neacoperită); cantitățile lui arată cât din cererea fiecărui magazin rămâne neacoperită.

Partea 2. Soluția inițială

Primul pas este un plan care respectă ofertele și cererile, chiar dacă nu e cel mai ieftin. Un astfel de plan folosește cel mult m + n − 1 rute (m laboratoare, n magazine), aici 2+3−1=42 + 3 - 1 = 4 rute.

Metoda colțului de nord-vest pornește din căsuța din stânga sus și trimite cât se poate:

  • L1 → M1: 40 de lăzi (M1 este acoperit, în L1 rămân 10);
  • L1 → M2: 10 lăzi (L1 s-a golit, M2 mai are nevoie de 40);
  • L2 → M2: 40 de lăzi (M2 este acoperit, în L2 rămân 30);
  • L2 → M3: 30 de lăzi.

Costul este 40×2+10×4+40×1+30×6=80+40+40+180=34040 \times 2 + 10 \times 4 + 40 \times 1 + 30 \times 6 = 80 + 40 + 40 + 180 = 340 de lei. Metoda este rapidă, dar nu se uită deloc la costuri.

Metoda costului minim umple întâi ruta cea mai ieftină, apoi următoarea, și tot așa:

  • L2 → M2 costă 1 leu: trimiți 50 de lăzi (M2 este acoperit, în L2 rămân 20);
  • L1 → M1 costă 2 lei: trimiți 40 de lăzi (M1 este acoperit, în L1 rămân 10);
  • rămâne doar M3: L1 → M3 primește 10 lăzi, iar L2 → M3 primește 20.

Costul este 50×1+40×2+10×5+20×6=50+80+50+120=30050 \times 1 + 40 \times 2 + 10 \times 5 + 20 \times 6 = 50 + 80 + 50 + 120 = 300 de lei, cu 40 de lei mai puțin.

Metoda Vogel (a diferențelor) dă de obicei un plan inițial și mai bun. Ideea: pentru fiecare linie și coloană calculezi o penalizare, diferența dintre cel mai mic și al doilea cel mai mic cost. Penalizarea arată cât pierzi dacă nu folosești ruta cea mai ieftină a liniei sau coloanei. Pașii:

  • calculezi penalizările tuturor liniilor și coloanelor rămase;
  • alegi linia sau coloana cu penalizarea cea mai mare și încarci în ea ruta cea mai ieftină cât se poate;
  • elimini linia sau coloana epuizată și reiei calculul.

Pentru brutărie, la primul pas penalizările liniilor sunt 4−2=24 - 2 = 2 (L1) și 4−1=34 - 1 = 3 (L2), iar ale coloanelor 4−2=24 - 2 = 2 (M1), 4−1=34 - 1 = 3 (M2) și 6−5=16 - 5 = 1 (M3). Cea mai mare penalizare (3) trimite la ruta L2 → M2, care primește 50 de lăzi. La pasul al doilea, L1 are penalizarea 5−2=35 - 2 = 3, cea mai mare, deci L1 → M1 primește 40 de lăzi. Restul merge la M3, ca la costul minim. Planul are tot 300 de lei; aici Vogel găsește direct optimul.

Partea 3. Este planul optim?

Ca să verifici un plan, te întrebi pentru fiecare rută nefolosită: ce se întâmplă dacă trimit pe ea o ladă? Ca ofertele și cererile să rămână corecte, trebuie să muți câte o ladă pe un ciclu de rute folosite, alternând „+1” și „−1”.

Pentru planul colțului de nord-vest, încerci ruta nefolosită L1 → M3:

  • +1 ladă pe L1 → M3 (+5 lei);
  • −1 ladă pe L2 → M3, ca M3 să primească tot 30 (−6 lei);
  • +1 ladă pe L2 → M2, ca L2 să trimită tot 70 (+1 leu);
  • −1 ladă pe L1 → M2, ca L1 să trimită tot 50 și M2 să primească tot 50 (−4 lei).

Variația costului este 5−6+1−4=−45 - 6 + 1 - 4 = -4 lei pe ladă. Este negativă, deci planul nu este optim: fiecare ladă mutată pe acest ciclu economisește 4 lei. Poți muta cel mult 10 lăzi (cât era pe L1 → M2, ruta cu „−1” cea mai mică), deci economisești 10×4=4010 \times 4 = 40 de lei și ajungi exact la planul de 300 de lei.

Când sunt multe rute, ciclurile se calculează mai repede cu potențiale (metoda potențialelor): pentru fiecare rută folosită scrii ui+vj=ciju_i + v_j = c_{ij}, pornind cu u1=0u_1 = 0, apoi pentru fiecare rută nefolosită calculezi:

Δij=cij−ui−vj\Delta_{ij} = c_{ij} - u_i - v_j

Planul este optim când toate valorile Δij\Delta_{ij} sunt mai mari sau egale cu 0. Pentru planul de 300 de lei: u1=0u_1 = 0, v1=2v_1 = 2, v3=5v_3 = 5, u2=6−5=1u_2 = 6 - 5 = 1 și v2=1−1=0v_2 = 1 - 1 = 0. Pentru rutele nefolosite, Δ12=4−0−0=4\Delta_{12} = 4 - 0 - 0 = 4 și Δ21=4−1−2=1\Delta_{21} = 4 - 1 - 2 = 1. Ambele sunt pozitive, deci 300 de lei este costul minim.

Algoritmul complet al metodei potențialelor:

  • Pasul 1. Calculezi potențialele uiu_i și vjv_j din rutele folosite (ui+vj=ciju_i + v_j = c_{ij}, cu u1=0u_1 = 0).
  • Pasul 2. Calculezi Δij=cij−ui−vj\Delta_{ij} = c_{ij} - u_i - v_j pentru rutele nefolosite. Dacă toate sunt mai mari sau egale cu 0, te oprești: planul este optim.
  • Pasul 3. Altfel, alegi ruta cu Δij\Delta_{ij} cel mai negativ și construiești ciclul ei: pornești din ea, te deplasezi alternativ pe linie și pe coloană doar prin rute folosite și revii în punctul de plecare. Marchezi colțurile alternativ cu „+” și „−”, începând cu „+” în ruta nouă.
  • Pasul 4. Cantitatea mutată este cea mai mică cantitate din colțurile cu „−”: θ=min⁡{xij din colțurile cu „−”}\theta = \min \{ x_{ij} \text{ din colțurile cu „−”} \}. O aduni în colțurile cu „+” și o scazi din cele cu „−”. Costul scade cu ∣Δij∣⋅θ\lvert \Delta_{ij} \rvert \cdot \theta. Revii la pasul 1.

Pentru planul colțului de nord-vest, potențialele sunt u1=0u_1 = 0, v1=2v_1 = 2, v2=4v_2 = 4, u2=1−4=−3u_2 = 1 - 4 = -3 și v3=6+3=9v_3 = 6 + 3 = 9. Rutele nefolosite au Δ13=5−0−9=−4\Delta_{13} = 5 - 0 - 9 = -4 și Δ21=4+3−2=5\Delta_{21} = 4 + 3 - 2 = 5. Intră ruta L1 → M3, cu θ=min⁡(10,30)=10\theta = \min(10, 30) = 10 și o scădere a costului de 4×10=404 \times 10 = 40 de lei, exact ciclul calculat mai sus.

Partea 4. Problema de alocare și metoda ungară

Exemplu ipotetic. Un atelier are trei angajați, A, B și C, și trei lucrări: montaj, vopsit și ambalat. Tabelul arată câte ore îi ia fiecăruia fiecare lucrare:

AngajatMontajVopsitAmbalat
A927
B643
C581

Metoda ungară creează zerouri în tabel, fără să schimbe alocarea optimă:

  • Pe fiecare linie, scazi cel mai mic număr din linie. A: (7, 0, 5); B: (3, 1, 0); C: (4, 7, 0).
  • Pe fiecare coloană, scazi cel mai mic număr din coloană. Doar prima coloană se schimbă (minimul 3): A: (4, 0, 5); B: (0, 1, 0); C: (1, 7, 0).
  • Cauți câte un zero pe fiecare linie și pe fiecare coloană. C are un singur zero, la ambalat; A are un singur zero, la vopsit; lui B îi rămâne montajul, unde are tot un zero.

Alocarea optimă este A la vopsit, B la montaj, C la ambalat, cu 2+6+1=92 + 6 + 1 = 9 ore în total, citite din tabelul inițial.

Când zerourile nu ajung. Uneori, după reduceri, nu se poate alege câte un zero pe fiecare linie și coloană. Atunci se aplică pasul de ajustare:

  • acoperi toate zerourile cu cât mai puține linii orizontale și verticale;
  • dacă numărul de linii este egal cu n, alocarea pe zerouri există; altfel continui;
  • alegi cel mai mic număr neacoperit, îl scazi din toate numerele neacoperite și îl aduni la numerele aflate la intersecția a două linii; restul rămân la fel. Reiei de la acoperire.

Exemplu ipotetic. Trei curieri, A, B și C, trebuie repartizați în trei cartiere. Timpii de livrare, în ore, sunt A: (4, 1, 3), B: (2, 0, 5), C: (3, 2, 2).

  • Reducerea pe linii (minimele 1, 0, 2): A: (3, 0, 2), B: (2, 0, 5), C: (1, 0, 0). Reducerea pe coloane (minimul primei coloane este 1): A: (2, 0, 2), B: (1, 0, 5), C: (0, 0, 0).
  • A și B au zero doar în cartierul 2, deci nu pot primi amândoi câte un zero. Zerourile se acoperă cu doar 2 linii (coloana 2 și linia lui C), mai puțin decât 3.
  • Cel mai mic număr neacoperit este 1 (B, cartierul 1). Îl scazi din numerele neacoperite și îl aduni la intersecția liniilor (C, cartierul 2): A: (1, 0, 1), B: (0, 0, 4), C: (0, 1, 0).
  • Acum alocarea pe zerouri există: A în cartierul 2, B în cartierul 1, C în cartierul 3, cu 1+2+2=51 + 2 + 2 = 5 ore în total.

Problema de alocare de maximizare. Dacă tabelul conține profituri sau punctaje pe care vrei să le maximizezi, scazi fiecare număr din cel mai mare număr din tabel și aplici metoda ungară tabelului obținut („regretele”). Dacă sunt mai multe sarcini decât persoane, adaugi persoane fictive cu timpi 0, ca tabelul să fie pătrat.

Video

How to Find a BFS for a Transportation Problem, Northwest Corner, Min Cost and Vogel's

de Shokoufeh Mirzaei

Se încarcă de pe YouTube

How to Find a BFS for a Transportation Problem, Northwest Corner, Min Cost and Vogel's · de Shokoufeh Mirzaei · Deschide pe YouTube

Întrebare-ghid: Clipul este în engleză (supply = ofertă, demand = cerere, basic feasible solution = soluție inițială admisibilă). Urmărește ordinea în care se umplu căsuțele la colțul de nord-vest și la costul minim, ca în Partea 2.

How to Solve an Assignment Problem Using the Hungarian Method

de Shokoufeh Mirzaei

Se încarcă de pe YouTube

How to Solve an Assignment Problem Using the Hungarian Method · de Shokoufeh Mirzaei · Deschide pe YouTube

Întrebare-ghid: Clipul este în engleză. Urmărește ce se face când zerourile nu ajung pentru o alocare completă: se acoperă zerourile cu cât mai puține linii și se ajustează tabelul (pas descris în Partea 4).

Exemple grafice

Primul grafic arată ce se întâmplă cu costul total al brutăriei când muți lăzi pe ciclul din Partea 3, pornind de la planul colțului de nord-vest.

010020030040024681012Lăzi mutate pe ruta L1 → M3Cost total (lei)cost totalcolțul de nord-vest: 340 leioptim: 300 lei
Fiecare ladă mutată pe ciclul L1 → M3, L2 → M3, L2 → M2, L1 → M2 scade costul cu 4 lei. Se pot muta cel mult 10 lăzi, iar costul coboară de la 340 la 300 de lei, minimul.
Vezi datele ca tabel
Costul transportului pe ciclul de îmbunătățire
SerieLăzi mutate pe ruta L1 → M3Cost total (lei)
cost total0340
cost total10300
colțul de nord-vest: 340 lei0340
optim: 300 lei10300

Încearcă să calculezi costul după 5 lăzi mutate: 340−5×4=320340 - 5 \times 4 = 320 de lei. Concluzie: pe un ciclu, costul scade cu aceeași sumă la fiecare ladă, deci merită să muți cât de mult permite ruta cu „−1” cea mai încărcată.

Al doilea grafic arată de ce ai nevoie de o metodă și nu încerci toate variantele. Cu n persoane și n sarcini există n!=1×2×…×nn! = 1 \times 2 \times \ldots \times n alocări posibile, iar numărul lor crește mult mai repede decât munca cerută de variantele moderne ale metodei ungare, care este de ordinul lui n3n^3.

0200400600800123456Număr de persoane (n)Număr de variante sau pașialocări posibile: n!metoda ungară: n³
Pentru 3 persoane există 6 alocări, dar pentru 6 persoane sunt 720, iar pentru 10 ar fi 3 628 800. Numărul de pași al metodei ungare (în variantele moderne) crește mult mai încet, aproximativ ca n³: 27 pentru 3 persoane și 216 pentru 6.
Vezi datele ca tabel
Alocări posibile față de pașii metodei ungare
SerieNumăr de persoane (n)Număr de variante sau pași
alocări posibile: n!11
alocări posibile: n!22
alocări posibile: n!36
alocări posibile: n!424
alocări posibile: n!5120
alocări posibile: n!6720
metoda ungară: n³11
metoda ungară: n³28
metoda ungară: n³327
metoda ungară: n³464
metoda ungară: n³5125
metoda ungară: n³6216

Încearcă să calculezi câte alocări ar avea 8 angajați: 8!=40 3208! = 40\,320, față de 83=5128^3 = 512. Concluzie: încercarea tuturor variantelor devine imposibilă repede, de aceea se folosesc metode care merg direct spre optim.

Aprofundare

De ce metoda ungară nu strică alocarea optimă

Fiecare alocare completă folosește exact un număr de pe fiecare linie. Dacă scazi 2 din toată linia lui A, timpul total al oricărei alocări scade cu exact 2 ore, deci ordinea alocărilor (care e mai bună decât care) rămâne aceeași. La fel pentru coloane. După reduceri, toate numerele sunt mai mari sau egale cu 0, deci o alocare care folosește doar zerouri are totalul 0 în tabelul redus, cel mai mic posibil.

De ce funcționează pasul de ajustare? Teorema lui Kőnig spune că numărul minim de linii care acoperă toate zerourile este egal cu numărul maxim de zerouri care se pot alege câte unul pe linie și pe coloană. Cât timp ajung mai puțin de n linii, alocarea completă nu există. Ajustarea creează cel puțin un zero nou într-o zonă neacoperită și nu face niciun număr negativ, iar totalul oricărei alocări complete se schimbă cu aceeași sumă, deci alocarea optimă rămâne aceeași.

Rute interzise și costuri mari

Uneori o rută nu se poate folosi (un pod închis, un magazin la care un laborator nu are voie să livreze). Atunci i se dă un cost foarte mare, notat M, mai mare decât orice cost din problemă. Metodele o vor evita singure, iar dacă planul optim tot o folosește, înseamnă că problema nu are soluție fără ea. Aceeași idee se folosește în problema de alocare pentru o persoană care nu poate face o anumită sarcină.

Excepții și nuanțe

  • Dacă ofertele și cererile sunt numere întregi, planul optim de transport iese tot în numere întregi. Nu ajungi la „12,5 lăzi”, ceea ce în alte probleme de programare liniară se poate întâmpla.
  • Dacă un plan folosește mai puțin de m + n − 1 rute (caz numit degenerat), se adaugă o rută cu 0 lăzi, ca să poți calcula toate potențialele.
  • Un Δij=0\Delta_{ij} = 0 la optim înseamnă că există și alt plan cu același cost minim.
  • Potențialele uiu_i și vjv_j sunt, de fapt, variabilele problemei duale: un fel de prețuri ale pâinii „la poarta laboratorului” și „la ușa magazinului”, ca în lecția despre dualitate.

Un caz real: de la convoaiele din război la metoda ungară

Problema de transport a fost formulată în 1941 de matematicianul american Frank Hitchcock, iar în timpul celui de-al Doilea Război Mondial Tjalling Koopmans a studiat cum să fie folosite navele comerciale ale Aliaților pentru a transporta cât mai multă marfă cu cât mai puține drumuri în gol. În 1955, Harold Kuhn a publicat metoda pentru problema de alocare și a numit-o „metoda ungară”, în onoarea matematicienilor maghiari Dénes Kőnig și Jenő Egerváry, pe ale căror rezultate se baza. Astăzi, variante ale acestor metode sunt folosite pentru a repartiza comenzile între curieri sau cursele între șoferii aplicațiilor de transport.

Quiz

Verifică ce ai înțeles. Poți reîncerca oricând.

1. Când este echilibrată o problemă de transport?

Alege o singură variantă.

2. De unde pornește metoda colțului de nord-vest?

Alege o singură variantă.

3. O problemă de transport are 3 depozite și 4 magazine. Câte rute folosește cel mult o soluție inițială obținută prin colțul de nord-vest?

Scrie un număr.

rute

4. Un plan de transport trimite 40 de lăzi cu 2 lei, 10 lăzi cu 4 lei, 40 de lăzi cu 1 leu și 30 de lăzi cu 6 lei. Cât este costul total, în lei?

Scrie un număr.

lei

5. Pentru o rută nefolosită, ciclul de îmbunătățire dă o variație a costului de −4 lei pe ladă. Ce înseamnă?

Alege o singură variantă.

6. La un plan de transport, potențialele sunt u₂ = 1 și v₁ = 2, iar costul pe ruta nefolosită L2 → M1 este 4 lei. Cât este Δ₂₁ = c₂₁ − u₂ − v₁?

Scrie un număr.

7. Cum arată tabelul [[9, 2, 7], [6, 4, 3], [5, 8, 1]] după reducerea pe linii din metoda ungară (scazi minimul fiecărei linii)?

Alege o singură variantă.

8. Trei angajați au timpii (în ore) A: 9, 2, 7; B: 6, 4, 3; C: 5, 8, 1 pentru lucrările montaj, vopsit și ambalat. Care este timpul total minim, în ore, dacă fiecare face exact o lucrare?

Scrie un număr.

ore