Matematici aplicate în economie · Optimizare liniară
Probleme de transport și de alocare
Avansat70 min✓ Terminată
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 numărul de lăzi trimise de la laboratorul i la magazinul j și cu costul unei lăzi pe acea rută, modelul este:
Î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 variabile (câte una pentru fiecare rută) și 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 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ă (se produce mai mult decât se cere), adaugi un beneficiar fictiv cu cererea și costuri 0; lăzile trimise acolo rămân, de fapt, în laborator;
- dacă , adaugi un furnizor fictiv cu oferta ș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 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 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 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 (L1) și (L2), iar ale coloanelor (M1), (M2) și (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 , 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 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 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 , pornind cu , apoi pentru fiecare rută nefolosită calculezi:
Planul este optim când toate valorile sunt mai mari sau egale cu 0. Pentru planul de 300 de lei: , , , și . Pentru rutele nefolosite, și . Ambele sunt pozitive, deci 300 de lei este costul minim.
Algoritmul complet al metodei potențialelor:
- Pasul 1. Calculezi potențialele și din rutele folosite (, cu ).
- Pasul 2. Calculezi pentru rutele nefolosite. Dacă toate sunt mai mari sau egale cu 0, te oprești: planul este optim.
- Pasul 3. Altfel, alegi ruta cu 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 „−”: . O aduni în colțurile cu „+” și o scazi din cele cu „−”. Costul scade cu . Revii la pasul 1.
Pentru planul colțului de nord-vest, potențialele sunt , , , și . Rutele nefolosite au și . Intră ruta L1 → M3, cu și o scădere a costului de 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:
| Angajat | Montaj | Vopsit | Ambalat |
|---|---|---|---|
| A | 9 | 2 | 7 |
| B | 6 | 4 | 3 |
| C | 5 | 8 | 1 |
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 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 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.
Vezi datele ca tabel
| Serie | Lăzi mutate pe ruta L1 → M3 | Cost total (lei) |
|---|---|---|
| cost total | 0 | 340 |
| cost total | 10 | 300 |
| colțul de nord-vest: 340 lei | 0 | 340 |
| optim: 300 lei | 10 | 300 |
Încearcă să calculezi costul după 5 lăzi mutate: 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ă 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 .
Vezi datele ca tabel
| Serie | Număr de persoane (n) | Număr de variante sau pași |
|---|---|---|
| alocări posibile: n! | 1 | 1 |
| alocări posibile: n! | 2 | 2 |
| alocări posibile: n! | 3 | 6 |
| alocări posibile: n! | 4 | 24 |
| alocări posibile: n! | 5 | 120 |
| alocări posibile: n! | 6 | 720 |
| metoda ungară: n³ | 1 | 1 |
| metoda ungară: n³ | 2 | 8 |
| metoda ungară: n³ | 3 | 27 |
| metoda ungară: n³ | 4 | 64 |
| metoda ungară: n³ | 5 | 125 |
| metoda ungară: n³ | 6 | 216 |
Încearcă să calculezi câte alocări ar avea 8 angajați: , față de . 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 la optim înseamnă că există și alt plan cu același cost minim.
- Potențialele și 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.