Matematici aplicate în economie · Optimizare liniară

Programare liniară

Intermediar55 min

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:

max⁡Z=c1x1+c2x2+…+cnxn,ai1x1+ai2x2+…+ainxn≤bi (i=1,…,m),xj≥0\max Z = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n, \quad a_{i1} x_1 + a_{i2} x_2 + \ldots + a_{in} x_n \le b_i \ (i = 1, \ldots, m), \quad x_j \ge 0

unde cjc_j este profitul pe o unitate din produsul j, aija_{ij} este cât din resursa i consumă o unitate din produsul j, iar bib_i 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 min⁡C=2a+3b\min C = 2a + 3b, cu 2a+b≥82a + b \ge 8, a+3b≥9a + 3b \ge 9 și a,b≥0a, b \ge 0. 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: x+y=30x + y = 30, care trece prin (0, 30) și (30, 0).
  • Păstrezi partea permisă: pentru „≤”, partea dinspre origine (verifici cu punctul (0, 0): 0+0≤300 + 0 \le 30, 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 x+y=30x + y = 30 din 2x+y=402x + y = 40 și obții x=10x = 10, apoi y=30−10=20y = 30 - 10 = 20. Profitul în fiecare vârf:

  • în (0, 0): Z=0Z = 0;
  • în (20, 0): Z=50×20=1000Z = 50 \times 20 = 1000 de lei;
  • în (10, 20): Z=50×10+40×20=500+800=1300Z = 50 \times 10 + 40 \times 20 = 500 + 800 = 1300 de lei;
  • în (0, 30): Z=40×30=1200Z = 40 \times 30 = 1200 de lei.

Planul optim este 10 mese și 20 de scaune, cu un profit de 1300 de lei. Ambele resurse se consumă integral: 10+20=3010 + 20 = 30 de ore și 2×10+20=402 \times 10 + 20 = 40 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ă:

x+y+s1=30,2x+y+s2=40,s1,s2≥0x + y + s_1 = 30, \quad 2x + y + s_2 = 40, \quad s_1, s_2 \ge 0

Planul de pornire este „nu produc nimic”: x=y=0x = y = 0, deci s1=30s_1 = 30 ore și s2=40s_2 = 40 de unități de lemn rămân nefolosite, iar Z=0Z = 0. În ultima linie a tabelului se scrie funcția-obiectiv sub forma Z−50x−40y=0Z - 50x - 40y = 0.

Bazăxys₁s₂Termen liber
s₁111030
s₂210140
Z−50−40000

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 30:1=3030 : 1 = 30 și 40:2=2040 : 2 = 20, deci iese s2s_2 (lemnul se termină primul), iar pivotul este 2.

  • Linia lui x: împarți linia lui s2s_2 la 2 și obții (1; 0,5; 0; 0,5 | 20).
  • Linia lui s1s_1: 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 10:0,5=2010 : 0{,}5 = 20 și 20:0,5=4020 : 0{,}5 = 40, deci iese s1s_1, iar pivotul este 0,5.

  • Linia lui y: înmulțești linia lui s1s_1 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ăxys₁s₂Termen liber
y012−120
x10−1110
Z0030101300

Linia lui Z nu mai are coeficienți negativi, deci planul este optim: x=10x = 10, y=20y = 20, Z=1300Z = 1300 de lei, exact ca la metoda grafică. Numerele 30 și 10 din dreptul lui s1s_1 și s2s_2 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.

01020304051015202530Mese (x)Scaune (y)ore: x + y = 30lemn: 2x + y = 401200 lei1300 lei (optim)1000 lei
Restricția orelor x + y ≤ 30 și restricția lemnului 2x + y ≤ 40 delimitează un patrulater cu vârfurile (0, 0), (20, 0), (10, 20) și (0, 30). Profitul cel mai mare, 1300 de lei, se obține în vârful (10, 20).
Vezi datele ca tabel
Mulțimea soluțiilor admisibile a atelierului
SerieMese (x)Scaune (y)
ore: x + y = 30030
ore: x + y = 30300
lemn: 2x + y = 40040
lemn: 2x + y = 40200
soluții admisibile (vârf)00
soluții admisibile (vârf)200
soluții admisibile (vârf)1020
soluții admisibile (vârf)030
1200 lei030
1300 lei (optim)1020
1000 lei200

Încearcă să alegi un punct din interiorul zonei, de exemplu (5, 10), și să calculezi profitul: 50×5+40×10=65050 \times 5 + 40 \times 10 = 650 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 50x+40y=Z50x + 40y = Z, numită dreaptă de izoprofit. Când Z crește, dreapta se mută paralel, departe de origine.

01020304051015202530Mese (x)Scaune (y)600 lei1000 lei1300 lei(10, 20)
Dreptele 50x + 40y = 600, 1000 și 1300 sunt paralele. Ultima care mai atinge zona colorată este cea de 1300 de lei, care o atinge doar în vârful (10, 20).
Vezi datele ca tabel
Dreptele de izoprofit
SerieMese (x)Scaune (y)
600 lei015
600 lei120
1000 lei025
1000 lei200
1300 lei032,5
1300 lei260
soluții admisibile (vârf)00
soluții admisibile (vârf)200
soluții admisibile (vârf)1020
soluții admisibile (vârf)030
(10, 20)1020

Î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 x+y≤10x + y \le 10 și x+y≥20x + y \ge 20), 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.

1. Ce este funcția-obiectiv într-o problemă de programare liniară?

Alege o singură variantă.

2. Dacă o problemă de programare liniară are o soluție optimă, atunci există o soluție optimă într-un vârf al mulțimii soluțiilor admisibile.

Alege o singură variantă.

3. Un atelier are 30 de ore de montaj, iar o masă cere 1 oră și un scaun 1 oră. Cum se scrie restricția orelor?

Alege o singură variantă.

4. Funcția-obiectiv este Z = 50x + 40y, iar vârfurile mulțimii soluțiilor admisibile sunt (0, 0), (20, 0), (10, 20) și (0, 30). Care este profitul maxim, în lei?

Scrie un număr.

lei

5. Ce arată o variabilă de compensare s₁ = 5 pentru restricția orelor de montaj?

Alege o singură variantă.

6. În tabelul simplex, linia lui Z este (−50; −40; 0; 0). Ce variabilă intră în bază?

Alege o singură variantă.

7. Variabila x intră în bază. În coloana ei, coeficienții sunt 1 (linia orelor, termen liber 30) și 2 (linia lemnului, termen liber 40). Care este cel mai mic raport, adică numărul de mese la care se oprește iterația?

Scrie un număr.

mese

8. Un fermier amestecă furajul A (2 lei/kg) și furajul B (3 lei/kg), cu restricțiile 2a + b ≥ 8 și a + 3b ≥ 9. Vârfurile zonei admisibile sunt (0, 8), (3, 2) și (9, 0). Care este costul minim, în lei?

Scrie un număr.

lei