Programare liniară

Programarea liniară — este o ramură a programării matematice și o metodă larg utilizată în cercetarea operațională, dedicată elaborării teoriei și metodelor de rezolvare a problemelor de determinare a extremului (maximului sau minimului) unei funcții liniare în prezența unor restricții liniare.

Programarea liniară (PL) este unul dintre cele mai puternice și frecvent utilizate instrumente pentru rezolvarea problemelor de optimizare în economie, management, planificare, logistică și alte domenii.

Obiect și destinație

Problema de bază a programării liniare — constă în găsirea celei mai bune (optime) modalități de alocare a resurselor limitate pentru atingerea unui anumit scop, atunci când atât scopul, cât și restricțiile privind utilizarea resurselor pot fi exprimate prin dependențe liniare.

• Programarea liniară permite rezolvarea unor probleme practice precum:
• Planificarea optimă a producției.
• Optimizarea fluxurilor de transport (problema transportului).
• Alocarea optimă a investițiilor.
• Tăierea optimă a materialelor. Problema de repartizare.

Formularea matematică a problemei PL

Problema standard de programare liniară se formulează astfel:

Este necesar să se găsească valorile variabilelor de decizie care maximizează sau minimizează funcția obiectiv liniară. Totodată, asupra variabilelor de decizie se impun restricții sub forma unui sistem de ecuații liniare și/sau inegalități liniare. De regulă, se adaugă condiția de nenegativitate a variabilelor de decizie (valorile lor trebuie să fie mai mari sau egale cu zero), ceea ce este adesea dictat de sensul fizic sau economic al problemei.

Matematic, aceasta înseamnă lucrul cu funcții liniare și sisteme de ecuații/inegalități liniare.

Concepte fundamentale ale PL

• Variabile de decizie (Variabile controlabile): Mărimi ale căror valori trebuie determinate în procesul de rezolvare a problemei (de exemplu, volumele de producție ale diferitelor produse, cantitatea de resurse direcționate spre diferite scopuri).
• Funcția obiectiv: O funcție liniară a variabilelor de decizie, a cărei valoare trebuie maximizată sau minimizată. Ea exprimă cantitativ scopul problemei (de exemplu, profitul total, costurile totale).
• Restricții: Sistemul de ecuații liniare și/sau inegalități liniare pe care trebuie să le satisfacă variabilele de decizie. Restricțiile reflectă limitele resurselor, cerințele tehnologice, sarcinile planificate și alte condiții ale problemei.
• Domeniul soluțiilor admisibile (DSA): Mulțimea tuturor combinațiilor de valori ale variabilelor de decizie care satisfac toate restricțiile problemei. Geometric, în spațiul multidimensional, DSA reprezintă un poliedru convex, posibil nemărginit sau vid.
• Soluție admisibilă: Orice combinație de valori ale variabilelor care aparține DSA.
• Soluție optimă: O soluție admisibilă pentru care funcția obiectiv atinge valoarea sa extremă (maximă sau minimă). Dacă o soluție optimă există, ea se află întotdeauna la granița DSA, cel puțin într-unul dintre vârfurile poliedrului convex al DSA (teorema fundamentală a PL).

Metode de rezolvare a problemelor PL

Există mai multe metode principale pentru rezolvarea problemelor de programare liniară:

• Metoda grafică: Se aplică pentru problemele cu două variabile de decizie. Permite reprezentarea vizuală a DSA și a funcției obiectiv în plan și găsirea soluției optime prin analiza vârfurilor DSA sau prin deplasarea dreptei de nivel a funcției obiectiv.
• Metoda simplex: Un algoritm iterativ universal, elaborat de George Dantzig. Metoda trece succesiv de la un vârf al DSA la un vârf vecin, îmbunătățind valoarea funcției obiectiv la fiecare pas, până când este găsită soluția optimă. Este metoda clasică și cea mai cunoscută de rezolvare a problemelor PL.
• Metodele punctului interior: O clasă alternativă de algoritmi, apărută ulterior metodei simplex. Acestea se deplasează spre soluția optimă prin interiorul DSA, nu pe granițele sale. Aceste metode sunt deosebit de eficiente pentru rezolvarea problemelor PL de dimensiuni foarte mari.

Dualitatea în programarea liniară

Oricărei probleme de programare liniară (numită problemă primară) i se poate asocia o altă problemă PL, numită problemă duală. Problemele primară și duală sunt strâns legate între ele:

Soluția unei probleme furnizează informații despre soluția celeilalte. Valorile optime ale funcțiilor obiectiv în ambele probleme coincid (dacă acestea există). Variabilele problemei duale au o importantă interpretare economică — ele corespund prețurilor umbră (sau evaluărilor duale) ale resurselor, indicând cu cât se va modifica valoarea optimă a funcției obiectiv a problemei primare la o mică modificare a restricției privind resursa corespunzătoare.

Aplicații ale PL

Programarea liniară are aplicații largi în:

• Economie și afaceri (planificarea producției, logistică, finanțe, marketing).
• Industrie (optimizarea proceselor tehnologice, gestiunea stocurilor, tăierea materialelor).
• Transport (optimizarea rutelor, a orarelor). Agricultură (optimizarea suprafețelor cultivate, a rațiilor de hrănire).
• Energetică (optimizarea încărcării capacităților de generare).

Bibliografie

• Dantzig, G. Programarea liniară, aplicațiile și generalizările sale. — Moscova: Progress, 1966.
• Iudin, D. B., Goldstein, E. G. Programarea liniară (teorie, metode și aplicații). — Moscova: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Vezi și

• Cercetarea operațională
• Optimizare
• Funcția obiectiv
• Restricții
• Domeniul soluțiilor admisibile
• Soluție optimă