PROGRAMARE LINIARĂ: PENTRU CE ESTE VORBA, MODELE, CONSTRÂNGERI, APLICAȚII - MATEMATICA - 2025

Programarea liniară este o metodă matematică care este utilizată pentru a optimiza ( a maximiza sau minimiza , după caz) o funcție ale cărei variabile sunt limitate, cât timp cât funcția și constrângerile sunt liniar variabile dependente.

În general, funcția de optimizat modelează o situație practică, cum ar fi profitul unui producător ale cărui contribuții, forță de muncă sau utilaje sunt limitate.

Figura 1. Programarea liniară este utilizată pe scară largă pentru optimizarea profiturilor. Sursa: Piqsels.

Unul dintre cele mai simple cazuri este cel al unei funcții liniare care trebuie maximizate, care depinde doar de două variabile, numite variabile de decizie. Poate fi de forma:

Z = k ₁ x + k ₂ y

Cu k ₁ și k ₂ constantă. Această funcție este cunoscută sub numele de funcție obiectivă. Desigur, există situații care merită mai mult de două variabile pentru studiu, fiind mai complexe:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ + …

Și constrângerile sunt, de asemenea, modelate matematic de un sistem de ecuații sau inegalități, la fel de liniare în x și y.

Setul de soluții din acest sistem se numește soluții fezabile sau puncte fezabile. Și dintre punctele fezabile există cel puțin unul, care optimizează funcția obiectivă.

Programarea liniară a fost dezvoltată în mod independent de fizicianul și matematicianul american George Dantzig (1914-2005) și de matematicianul și economistul rus Leonid Kantorovich (1912-1986) la scurt timp după al doilea război mondial.

Metoda de rezolvare a problemelor cunoscută sub numele de metoda simplex este creierul lui Dantzig, care a lucrat pentru Forțele Aeriene ale SUA, Berkeley University și Stanford University.

Figura 2. Matematicienii George Dantzig (stânga) și Leonid Kantorovici (dreapta). Sursa: F. Zapata.

Modele de programare liniară

Elementele necesare pentru a stabili un model liniar de programare, potrivit pentru o situație practică, sunt:

-Funcție obiectivă

-Variabile de decizie

-Restrictions

În funcția obiectivă definiți ce doriți să atingeți. De exemplu, să presupunem că doriți să maximizați profiturile obținute din fabricarea anumitor produse. Apoi se stabilește funcția „profit”, în funcție de prețul la care se vând produsele.

În termeni matematici, această funcție poate fi exprimată prescurtată folosind notația de însumare:

Z = ∑k _i x _i

În această ecuație, k _i sunt coeficienți și x _i sunt variabilele de decizie.

Variabilele de decizie sunt elementele sistemului al căror control este controlat, iar valorile lor sunt numere reale pozitive. În exemplul propus, variabilele de decizie sunt cantitatea fiecărui produs de fabricat pentru a obține profitul maxim.

În cele din urmă, avem constrângerile, care sunt ecuații liniare sau inegalități în ceea ce privește variabilele de decizie. Acestea descriu limitele problemei, care sunt cunoscute și pot fi, de exemplu, cantitățile de materie primă disponibile în fabricație.

Tipuri de restricții

Puteți avea un număr M de limitări, începând de la j = 1 până la j = M. Din punct de vedere matematic, restricțiile sunt de trei tipuri:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Prima restricție este de tipul ecuației liniare și înseamnă că trebuie respectată valoarea A _j , care este cunoscută.

Cele două restricții rămase sunt inegalități liniare și înseamnă că valorile cunoscute B _j și C _j pot fi respectate sau depășite, atunci când simbolul care apare este ≥ (mai mare sau egal cu) sau respectat sau nu depășit, dacă simbolul este ≤ (mai mic sau egal cu).

Exemplu de model

Domeniile de aplicare sunt foarte diverse, de la administrarea afacerilor la nutriție, dar pentru a înțelege metoda, mai jos este propus un model simplu al unei situații practice cu două variabile.

O patiserie locală este cunoscută pentru două specialități: tortul forestier negru și tortul sacripantin.

În prepararea sa, necesită ouă și zahăr. Pentru pădurea neagră aveți nevoie de 9 ouă și 500 g de zahăr, în timp ce pentru sacripantină aveți nevoie de 8 ouă și 800 g de zahăr. Prețurile respective de vânzare sunt de 8 $ și 10 $.

Problema este: Câte prăjituri de fiecare tip trebuie să facă panificația pentru a-și maximiza profitul, știind că are 10 kilograme de zahăr și 144 de ouă?

Variabilele de decizie

Variabilele de decizie sunt „x” și „y”, care iau valori reale:

-x: numărul de prăjituri negre din pădure

-y: prăjituri tip sacripantine

restricţii

Restricțiile sunt date de faptul că numărul prăjiturilor este o cantitate pozitivă și există cantități limitate de materie primă pentru prepararea lor.

Prin urmare, sub formă matematică, aceste restricții iau forma:

1. x ≥ 0
2. și ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Constrângerile 1 și 2 constituie condiția de non-negativitate expusă anterior și toate inegalitățile ridicate sunt liniare. În restricțiile 3 și 4 sunt incluse valorile care nu trebuie depășite: 144 de ouă și 10 kg de zahăr.

Funcție obiectivă

În cele din urmă, funcția obiectivă este profitul obținut la fabricarea cantității „x” de prăjituri negre de pădure plus cantitatea de „y” de sacripantine. Este construit prin înmulțirea prețului cu cantitatea de prăjituri făcute și adăugarea pentru fiecare tip. Este o funcție liniară pe care o vom numi G (x, y):

G = 8x + 10y

Metode de soluție

Diferitele metodologii de soluție includ metode grafice, algoritmul simplex și metoda punctului interior, pentru a numi câteva.

- Metoda grafică sau geometrică

Când aveți o problemă cu două variabile, precum cea din secțiunea anterioară, constrângerile determină o regiune poligonală în planul xy, numită regiune fezabilă sau regiune de viabilitate.

Figura 3. Regiunea fezabilă, unde se găsește soluția problemei de optimizare. Sursa: Wikimedia Commons.

Această regiune este construită folosind liniile de restricție, care sunt liniile obținute din inegalitățile restricțiilor, funcționând doar cu semnul egalității.

În cazul brutăriei care dorește să optimizeze profiturile, liniile de constrângere sunt:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Toate punctele din regiunea înconjurată de aceste linii sunt soluții posibile, deci există multe dintre ele. Cu excepția cazului în care regiunea fezabilă se dovedește a fi goală, caz în care problema prezentată nu are nicio soluție.

Din fericire, pentru problema de patiserie regiunea fezabilă nu este goală, o avem mai jos.

Figura 4. Regiunea fezabilă a problemei de patiserie. Linia cu câștig 0 traversează originea. Sursa: F. Zapata cu Geogebra.

Soluția optimă, dacă există, se găsește cu ajutorul funcției obiective. De exemplu, atunci când încercați să găsiți profitul maxim G, avem următoarea linie, care se numește linia iso-profit:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Cu această linie obținem toate perechile (x, y) care asigură un câștig dat G, deci există o familie de linii în funcție de valoarea lui G, dar toate cu aceeași pantă -k ₁ / k ₂ , deci sunt linii paralele.

Soluția optimă

Acum, se poate demonstra că soluția optimă a unei probleme liniare este întotdeauna un punct extrem sau un vertex al regiunii fezabile. Asa de:

Dacă linia cea mai apropiată de origine are un întreg segment în comun cu regiunea fezabilă, se spune că există soluții infinite. Acest caz apare dacă panta liniei iso-profit este egală cu cea a oricăreia dintre celelalte linii care limitează regiunea.

Pentru patiseria noastră, vârfurile de candidat sunt A, B și C.

- Metoda simplex a lui Dantzig

Metoda grafică sau geometrică este aplicabilă pentru două variabile. Cu toate acestea, este mai complicat atunci când există trei variabile și imposibil de utilizat pentru un număr mai mare de variabile.

Când se confruntă cu probleme cu mai mult de două variabile, se folosește metoda simplex, care constă dintr-o serie de algoritmi pentru a optimiza funcțiile obiective. Matricile și aritmetica simplă sunt adesea folosite pentru a efectua calculele.

Metoda simplex începe prin alegerea unei soluții fezabile și verificarea dacă aceasta este optimă. Dacă este, am rezolvat problema, dar dacă nu, continuăm spre o soluție mai aproape de optimizare. Dacă soluția există, algoritmul o găsește în câteva încercări.

Aplicații

Programarea liniară și neliniară sunt aplicate în multe domenii pentru a lua cele mai bune decizii în ceea ce privește reducerea costurilor și creșterea profiturilor, care nu sunt întotdeauna monetare, deoarece pot fi măsurate în timp, de exemplu, dacă doriți să minimizați timpul necesar să efectueze o serie de operații.

Iată câteva câmpuri:

-În marketing este folosit pentru a găsi cea mai bună combinație de media (rețele sociale, televiziune, presă și altele) pentru a face publicitate unui anumit produs.

-Pentru alocarea de sarcini adecvate personalului unei companii sau fabrici sau programarea acestora.

-În selectarea celor mai hrănitoare alimente și cu cel mai mic cost din industria animalelor și păsărilor de curte.

Exerciții rezolvate

- Exercitiul 1

Rezolva grafic modelul de programare liniară ridicat în secțiunile precedente.

Soluţie

Este necesar să graficăm setul de valori determinat de sistemul de restricții specificat în problemă:

1. x ≥ 0
2. și ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Regiunea dată de inegalitățile 1 și 2 corespunde primului cadran al planului cartezian. În ceea ce privește inegalitățile 3 și 4, începem prin a găsi liniile de restricție:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Regiunea fezabilă este un patrulater ale cărui vârfuri sunt punctele A, B, C și D.

Profitul minim este 0, deci linia 8x + 10y = 0 este limita inferioară, iar liniile iso-profit au panta -8/10 = - 0,8.

Această valoare este diferită de versanții celorlalte linii de restricție și, deoarece regiunea fezabilă este delimitată, soluția unică există.

Figura 5. Soluție grafică a exercițiului 1, care prezintă regiunea fezabilă și punctul de soluție C la unul dintre vârfurile respectivei regiuni. Sursa: F. Zapata.

Această soluție corespunde unei linii de pantă -0,8 care trece prin oricare dintre punctele A, B sau C, ale căror coordonate sunt:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Soluție optimă

Calculăm valoarea lui G pentru fiecare dintre aceste puncte:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Cel mai mare profit se găsește la fabricarea a 11 prăjituri pădure negre și 5.625 prăjituri sacripantine. Această soluție este de acord cu cea găsită prin intermediul software-ului.

- Exercițiul 2

Verificați rezultatul exercițiului anterior utilizând funcția Solver disponibilă în majoritatea foilor de calcul, cum ar fi Excel sau LibreOffice Calc, care încorporează algoritmul Simplex pentru optimizare în programarea liniară.

Soluţie

Figura 6. Detaliu al soluției din exercițiul 1 prin foaia de calcul Libre Office Calc. Sursa: F. Zapata.

Figura 7. Detaliu al soluției din exercițiul 1 prin foaia de calcul Libre Office Calc. Sursa: F. Zapata.

Referințe

1. Sclipitor. Programare liniară. Recuperat de la: fantastic.org.
2. Eppen, G. 2000. Cercetări operaționale în științe administrative. 5-a. Ediție. Sala Prentice.
3. Haeussler, E. 1992. Matematică pentru management și economie. 2a. Ediție. Grupo Editorial Iberoamericana.
4. Hiru.eus. Programare liniară. Recuperat din: trei.eus.
5. Wikipedia. Programare liniară. Recuperat din: es. wikipedia.org.