Matematici aplicate în economie · Optimizare liniară
Programare liniară
Intermediar55 min✓ Terminată
Pe această pagină
Ce înveți
- Scrii o problemă de maximizare a profitului sau de minimizare a costurilor ca model de programare liniară.
- Rezolvi grafic o problemă cu două variabile, calculând funcția-obiectiv în vârfurile mulțimii soluțiilor admisibile.
- Aplici algoritmul simplex pas cu pas, într-un tabel, și citești din el planul optim.
Teorie
În lecția despre sisteme liniare, atelierul voia să folosească integral toate resursele. De cele mai multe ori, întrebarea unei firme este însă alta: ce plan de producție aduce cel mai mare profit, fără să depășească resursele pe care le are? Resursele dau inecuații, iar profitul este o funcție pe care vrei s-o faci cât mai mare. Metoda care răspunde la această întrebare se numește programare liniară.
Partea 1. Cum formulezi problema
Orice problemă de programare liniară are patru părți:
- variabilele de decizie: ce alegi (de exemplu, câte mese și câte scaune faci);
- funcția-obiectiv: mărimea pe care vrei s-o maximizezi (profitul, venitul) sau s-o minimizezi (costul);
- restricțiile: câte o inecuație pentru fiecare resursă limitată;
- condițiile de nenegativitate: nu poți produce un număr negativ de bucăți.
Forma generală a unei probleme cu n variabile și m restricții este:
unde este profitul pe o unitate din produsul j, este cât din resursa i consumă o unitate din produsul j, iar este cantitatea disponibilă din resursa i.
O problemă de minimizare a costurilor se scrie la fel, dar restricțiile sunt de obicei cu „≥”: ceva trebuie asigurat cel puțin. Exemplu ipotetic: un fermier amestecă două furaje, A (2 lei/kg) și B (3 lei/kg). Un kilogram de A dă 2 unități de proteine și 1 de energie, iar unul de B dă 1 unitate de proteine și 3 de energie. Animalele au nevoie de cel puțin 8 unități de proteine și 9 de energie. Modelul este , cu , și . Soluția (o poți verifica la final cu metoda grafică) este 3 kg de A și 2 kg de B, cu un cost de 12 lei.
Partea 2. Metoda grafică
Când ai doar două variabile, poți rezolva problema pe un desen.
Pașii metodei grafice:
- Desenezi fiecare restricție ca dreaptă, scriind „=” în loc de „≤”. Pentru ore: , care trece prin (0, 30) și (30, 0).
- Păstrezi partea permisă: pentru „≤”, partea dinspre origine (verifici cu punctul (0, 0): , adevărat).
- Intersecția tuturor părților permise este poligonul soluțiilor admisibile.
- Calculezi funcția-obiectiv în fiecare vârf al poligonului. Cea mai mare valoare (la maximizare) este optimul.
Pentru atelier, vârfurile sunt (0, 0), (20, 0), (10, 20) și (0, 30). Vârful (10, 20) este intersecția celor două drepte: scazi din și obții , apoi . Profitul în fiecare vârf:
- în (0, 0): ;
- în (20, 0): de lei;
- în (10, 20): de lei;
- în (0, 30): de lei.
Planul optim este 10 mese și 20 de scaune, cu un profit de 1300 de lei. Ambele resurse se consumă integral: de ore și de unități de lemn.
Partea 3. Algoritmul simplex
Cu trei sau mai multe produse nu mai poți desena problema. Algoritmul simplex face același lucru ca metoda grafică, dar cu calcule: pornește dintr-un vârf și trece, pas cu pas, într-un vârf vecin cu profit mai mare, până când niciun vecin nu mai e mai bun.
Mai întâi transformi inecuațiile în ecuații, adăugând câte o variabilă de compensare, care arată cât rămâne nefolosit din fiecare resursă:
Planul de pornire este „nu produc nimic”: , deci ore și de unități de lemn rămân nefolosite, iar . În ultima linie a tabelului se scrie funcția-obiectiv sub forma .
| Bază | x | y | s₁ | s₂ | Termen liber |
|---|---|---|---|---|---|
| s₁ | 1 | 1 | 1 | 0 | 30 |
| s₂ | 2 | 1 | 0 | 1 | 40 |
| Z | −50 | −40 | 0 | 0 | 0 |
Regulile unui pas (o iterație):
- Variabila care intră este cea cu coeficientul cel mai negativ în linia lui Z: produsul care aduce cel mai mult profit pe bucată.
- Linia care iese este cea cu cel mai mic raport „termen liber : coeficientul variabilei care intră” (doar pentru coeficienți pozitivi): resursa care se termină prima.
- Pivotarea: împarți linia aleasă la numărul de la intersecție (pivotul) și faci zerouri în restul coloanei, ca la metoda lui Gauss.
- Oprirea: când linia lui Z nu mai are niciun coeficient negativ, planul este optim.
Iterația 1. Intră x (coeficientul −50). Rapoartele sunt și , deci iese (lemnul se termină primul), iar pivotul este 2.
- Linia lui x: împarți linia lui la 2 și obții (1; 0,5; 0; 0,5 | 20).
- Linia lui : scazi din ea noua linie a lui x și obții (0; 0,5; 1; −0,5 | 10).
- Linia lui Z: aduni de 50 de ori noua linie a lui x și obții (0; −15; 0; 25 | 1000).
Ai ajuns în vârful (20, 0): 20 de mese, profit 1000 de lei. În linia lui Z mai există un coeficient negativ (−15), deci planul se poate îmbunătăți.
Iterația 2. Intră y. Rapoartele sunt și , deci iese , iar pivotul este 0,5.
- Linia lui y: înmulțești linia lui cu 2 și obții (0; 1; 2; −1 | 20).
- Linia lui x: scazi din ea jumătate din noua linie a lui y și obții (1; 0; −1; 1 | 10).
- Linia lui Z: aduni de 15 ori noua linie a lui y și obții (0; 0; 30; 10 | 1300).
| Bază | x | y | s₁ | s₂ | Termen liber |
|---|---|---|---|---|---|
| y | 0 | 1 | 2 | −1 | 20 |
| x | 1 | 0 | −1 | 1 | 10 |
| Z | 0 | 0 | 30 | 10 | 1300 |
Linia lui Z nu mai are coeficienți negativi, deci planul este optim: , , de lei, exact ca la metoda grafică. Numerele 30 și 10 din dreptul lui și au și ele un sens economic, pe care îl vei afla în lecția următoare.
Video
Solving Linear Programming Problems Using the Graphical Method (Maximization)
de Andrew Scarffe, PhD MBA
Se încarcă de pe YouTube
Solving Linear Programming Problems Using the Graphical Method (Maximization) · de Andrew Scarffe, PhD MBA · Deschide pe YouTube
Întrebare-ghid: Clipul este în engleză (feasible region = mulțimea soluțiilor admisibile, corner point = vârf, objective function = funcția-obiectiv). Urmărește cum se desenează fiecare restricție și cum se compară profitul în vârfuri, ca în Partea 2.
The Simplex Method (Step-by-Step Example)
de Zach's Math Zone
Se încarcă de pe YouTube
The Simplex Method (Step-by-Step Example) · de Zach's Math Zone · Deschide pe YouTube
Întrebare-ghid: Clipul este în engleză (pivot column = coloana variabilei care intră, slack variable = variabilă de compensare). Urmărește cum se alege pivotul și compară regula rapoartelor cu cea din Partea 3.
Exemple grafice
Primul grafic arată problema atelierului. Fiecare resursă este o dreaptă, iar zona colorată conține toate planurile care încap în cele 30 de ore și în cele 40 de unități de lemn. În dreptul fiecărui vârf este scris profitul.
Vezi datele ca tabel
| Serie | Mese (x) | Scaune (y) |
|---|---|---|
| ore: x + y = 30 | 0 | 30 |
| ore: x + y = 30 | 30 | 0 |
| lemn: 2x + y = 40 | 0 | 40 |
| lemn: 2x + y = 40 | 20 | 0 |
| soluții admisibile (vârf) | 0 | 0 |
| soluții admisibile (vârf) | 20 | 0 |
| soluții admisibile (vârf) | 10 | 20 |
| soluții admisibile (vârf) | 0 | 30 |
| 1200 lei | 0 | 30 |
| 1300 lei (optim) | 10 | 20 |
| 1000 lei | 20 | 0 |
Încearcă să alegi un punct din interiorul zonei, de exemplu (5, 10), și să calculezi profitul: de lei, mult sub 1300. Concluzie: în interior mai rămân resurse nefolosite, de aceea optimul este întotdeauna pe margine, într-un vârf.
Al doilea grafic arată de ce. Toate planurile cu același profit stau pe o dreaptă de forma , numită dreaptă de izoprofit. Când Z crește, dreapta se mută paralel, departe de origine.
Vezi datele ca tabel
| Serie | Mese (x) | Scaune (y) |
|---|---|---|
| 600 lei | 0 | 15 |
| 600 lei | 12 | 0 |
| 1000 lei | 0 | 25 |
| 1000 lei | 20 | 0 |
| 1300 lei | 0 | 32,5 |
| 1300 lei | 26 | 0 |
| soluții admisibile (vârf) | 0 | 0 |
| soluții admisibile (vârf) | 20 | 0 |
| soluții admisibile (vârf) | 10 | 20 |
| soluții admisibile (vârf) | 0 | 30 |
| (10, 20) | 10 | 20 |
Încearcă să imaginezi dreapta de 1400 de lei: ar trece prin (0, 35) și (28, 0), complet în afara zonei, deci niciun plan admisibil nu aduce 1400 de lei. Concluzie: împingi dreapta de izoprofit cât de departe poți; ultimul punct atins din zonă este planul optim.
Aprofundare
De ce optimul este într-un vârf
Pe o latură a poligonului, funcția-obiectiv este liniară: când te deplasezi de-a lungul laturii, profitul crește sau scade constant. De aceea cea mai mare valoare pe latură este la unul dintre capete, adică într-un vârf. Cum orice punct din interior poate fi împins spre o latură fără să scadă profitul, optimul (dacă există) se află într-un vârf. Aceasta este teorema fundamentală a programării liniare și explică de ce simplexul verifică doar vârfuri.
Cazuri speciale
- Mai multe soluții optime. Dacă un scaun ar aduce tot 50 de lei, dreptele de izoprofit ar fi paralele cu dreapta orelor, iar toate planurile de pe latura dintre (10, 20) și (0, 30) ar aduce același profit, 1500 de lei. În tabelul simplex final, asta se vede printr-un 0 în linia lui Z în dreptul unei variabile care nu este în bază.
- Problemă fără soluție. Dacă restricțiile se contrazic (de exemplu și ), mulțimea soluțiilor admisibile este vidă.
- Profit nemărginit. Dacă lipsește o restricție care limitează producția, zona se întinde la infinit și profitul poate crește oricât. În simplex, asta apare când coloana variabilei care intră nu are niciun coeficient pozitiv, deci nu se poate face niciun raport.
- Cantități întregi. Optimul poate ieși cu zecimale (de exemplu 10,5 mese). Rotunjirea nu dă întotdeauna cel mai bun plan întreg; pentru asta există programarea în numere întregi, o ramură separată.
Un caz real: placajul din Leningrad și Forțele Aeriene americane
În 1939, matematicianul sovietic Leonid Kantorovici a primit o problemă de la un trust de placaj din Leningrad: cum să împartă lucrul între mai multe mașini, ca să obțină cât mai mult placaj. Răspunsul lui, publicat în broșura „Metode matematice de organizare și planificare a producției”, conține primele idei ale programării liniare. Independent, în 1947, George Dantzig, care lucra la planificarea logisticii pentru Forțele Aeriene ale SUA, a inventat algoritmul simplex. În 1975, Kantorovici și Tjalling Koopmans au primit Premiul Nobel pentru economie pentru contribuțiile la teoria alocării optime a resurselor. Astăzi, variante ale simplexului rulează în programele care planifică zboruri, livrări și producția fabricilor.
Quiz
Verifică ce ai înțeles. Poți reîncerca oricând.