Dezvoltarea unei metode de programare liniară. Teoria programarii liniare

2. Concept programare liniară. Tipuri de probleme de programare liniară

Programarea liniară (LP) este una dintre primele și cele mai amănunțite secțiuni studiate programare matematică. Programarea liniară a fost secțiunea din care a început să se dezvolte disciplina „programare matematică”. Termenul „programare” din titlul disciplinei nu are nimic în comun cu termenul „programare (adică compilarea unui program) pentru un computer”, deoarece Disciplina „programarii liniare” a apărut chiar înainte de vremea când calculatoarele au început să fie utilizate pe scară largă pentru a rezolva probleme matematice, de inginerie, economice și de altă natură.

Termenul „programare liniară” a apărut ca urmare a unei traduceri inexacte a limbajului englezesc „programare liniară”. Unul dintre semnificațiile cuvântului „programare” este a face planuri, a planifica. În consecință, traducerea corectă a englezei „programare liniară” nu ar fi „programare liniară”, ci „planificare liniară”, care reflectă mai exact conținutul disciplinei. Cu toate acestea, termenii programare liniară, programare neliniară, programare matematică etc. au devenit general acceptate în literatura noastră și, prin urmare, vor fi păstrate.

Așadar, programarea liniară a apărut după cel de-al Doilea Război Mondial și a început să se dezvolte rapid, atrăgând atenția matematicienilor, economiștilor și inginerilor datorită posibilității unei largi aplicare practică, precum și armonia matematică.

Putem spune că programarea liniară este aplicabilă rezolvării modelelor matematice ale acelor procese și sisteme care se pot baza pe ipoteza unei reprezentări liniare a lumii reale.

Programarea liniară este folosită pentru a rezolva sarcini economice, în sarcini precum managementul și planificarea producției; în probleme de determinare amplasare optimă echipamente pentru nave maritime, în ateliere; în probleme de stabilire a planului optim de transport al mărfurilor (problema de transport); în probleme de repartizare optimă a personalului etc.

Sarcina programării liniare (LP), așa cum este deja clar din cele de mai sus, este de a găsi minimul (sau maximul) funcţie liniară sub restricții liniare.

Există mai multe metode de rezolvare a problemelor LP. Această lucrare va discuta unele dintre ele, în special:

Metoda grafica de rezolvare a problemei LP;

Metoda simplex;

Rezolvarea problemei LP folosind foaia de calcul Excel;

3. Conceptul de programare neliniară

În majoritatea problemelor de inginerie, construcția model matematic nu poate fi redusă la o problemă de programare liniară.

Modelele matematice în problemele de proiectare a obiectelor reale sau a proceselor tehnologice trebuie să reflecte procesele fizice reale și, de regulă, neliniare care au loc în ele. Variabilele acestor obiecte sau procese sunt interconectate prin legi fizice neliniare, cum ar fi legile conservării masei sau energiei. Ele sunt limitate la intervale extreme care asigură fezabilitatea fizică a acestui obiect sau proces. Ca urmare, majoritatea problemelor de programare matematică întâlnite în proiectele de cercetare și problemele de proiectare sunt probleme de programare neliniară (NP).

În această lucrare, vom considera o astfel de metodă de rezolvare a problemelor NP ca metoda multiplicatorilor Lagrange.

Metoda multiplicatorului Lagrange vă permite să găsiți maximul (sau minimul) unei funcții sub constrângeri de egalitate. Ideea principală a metodei este de a trece de la problema găsirii unui extremum condiționat la problema găsirii extremului necondiționat al unei funcții Lagrange construite.

4. Programare dinamică

Programarea dinamică este un aparat matematic care vă permite să găsiți rapid soluția optimă în cazurile în care situația analizată nu conține factori de incertitudine, dar există număr mare opțiuni de comportament care aduc rezultate diferite, dintre care este necesar să o alegem pe cea mai bună. Programarea dinamică abordează rezolvarea unei anumite clase de probleme prin descompunerea lor în părți, mai mici și mai mici. sarcini complexe. În principiu, problemele de acest fel pot fi rezolvate prin enumerarea tuturor opțiuni posibileși alegerea celor mai bune dintre ele, dar adesea o astfel de căutare este foarte dificilă. În aceste cazuri, procesul de luare a unei decizii optime poate fi împărțit în etape (etape) și studiat folosind metoda programare dinamică.

Rezolvarea problemelor prin metode de programare dinamică se realizează pe baza principiului optimității formulat de R.E Bellman: comportamentul optim are proprietatea că oricare ar fi starea inițială a sistemului și soluția inițială, soluția ulterioară trebuie să determine comportamentul optim în raport cu. starea obţinută ca urmare a soluţiei iniţiale.

Astfel, planificarea fiecărei etape trebuie efectuată ținând cont de beneficiul general obținut la finalizarea întregului proces, ceea ce permite optimizarea rezultatului final în funcție de criteriul selectat.

Cu toate acestea, programarea dinamică nu este metoda universala solutii. Aproape fiecare problemă rezolvată prin această metodă se caracterizează prin propriile caracteristici și necesită căutarea celui mai potrivit set de metode pentru rezolvarea acesteia. În plus, volumele mari și complexitatea rezolvării problemelor în mai multe etape cu multe stări duc la necesitatea de a selecta probleme de dimensiuni reduse sau de a utiliza informații comprimate.

Programarea dinamică este utilizată pentru a rezolva probleme precum: distribuția investițiilor de capital limitate între noi domenii de utilizare a acestora; elaborarea regulilor de gestionare a cererii și a stocurilor; compilare planuri calendaristice reparații curente și majore ale echipamentelor și înlocuirea acestora; cauta cele mai scurte distante reteaua de transport etc.

Fie ca procesul de optimizare să fie împărțit în n pași. La fiecare pas, este necesar să se definească două tipuri de variabile - variabila de stare S și variabila de control X. Variabila S determină în ce stări se poate găsi sistemul. dat kth pas. În funcție de S, la acest pas este posibil să se aplice unele controale care sunt caracterizate de variabila X. Aplicarea controlului X la pasul k aduce un rezultat Wk(S,Xk) și transferă sistemul într-o stare nouă S"( S,Xk). Pentru fiecare stare posibilă la pasul k, dintre toate controalele posibile, control optim X*k astfel încât rezultatul obținut în pași de la k-a la n-a se dovedește a fi optim. Caracteristica numerică a acestui rezultat se numește funcția Bellman Fk(S) și depinde de numărul pasului k și de starea sistemului S.

Toate soluțiile la problemă sunt împărțite în două etape. În prima etapă, care se numește optimizare condiționată, funcția Bellman și controalele optime sunt găsite pentru toate stările posibile la fiecare pas, începând cu ultimul.

După ce funcția Bellman și controalele optime corespunzătoare sunt găsite pentru toți pașii de la a n-a la primul, se realizează a doua etapă de rezolvare a problemei, care se numește optimizare neconstrânsă.

ÎN vedere generală Problema programarii dinamice este formulata astfel: se cere determinarea unui control X* care transfera sistemul din starea initiala S0 in starea finala Sn, la care functia obiectiv F(S0,X*) ia cea mai mare (mai mica). ) valoare.

Caracteristicile modelului matematic de programare dinamică sunt următoarele:

problema de optimizare este formulată ca un proces de control finit în mai multe etape;

funcţia obiectiv este aditivă şi egală cu suma funcţiilor obiectiv ale fiecărui pas

alegerea controlului Xk la fiecare pas depinde doar de starea sistemului la acest pas Sk-1 și nu afectează pașii anteriori (nu feedback);

starea sistemului Sk după fiecare pas de control depinde doar de starea anterioară a sistemului Sk-1 și această acțiune de control Xk (fără efect secundar) și poate fi scrisă ca o ecuație de stare:

la fiecare pas, controlul Xk depinde de un număr finit de variabile de control, iar starea sistemului Sk depinde de un număr finit de variabile;

controlul optim X* este un vector determinat de succesiunea optimului controale pas cu pas:

X*=(X*1, X*2, …, X*k, …, X*n),

al cărui număr determină numărul de pași ai sarcinii.

Optimizare conditionata. După cum sa menționat mai sus, în această etapă se găsesc funcția Bellman și controalele optime pentru toate stările posibile la fiecare pas, începând cu ultima în conformitate cu algoritmul de baleiaj înapoi. Pe ultimul al n-lea pas găsirea controlului optim X*n și a valorii funcției Bellman Fn(S) nu este dificilă, deoarece

Fn(S)=max(Wn(S,Xn)),

unde se caută maximul peste toate valorile posibile ale lui Xn.

Alte calcule sunt efectuate conform relației de recurență care conectează funcția Bellman la fiecare pas cu aceeași funcție, dar calculată la pasul anterior:

Fk(S)=max(Wk(S,Xk)+Fk+1(S"(S,Xk))).(1)

Acest maxim (sau minim) este determinat de toate valorile posibile pentru k și S variabila de control X.

Optimizare necondiționată. După ce funcția Bellman și controalele optime corespunzătoare sunt găsite pentru toți pașii de la a n-a la primul (la prima etapă k=1 starea sistemului este egală cu starea sa inițială S0), a doua etapă de rezolvare a problemei este efectuate. Controlul optim se găsește la primul pas X1, a cărui aplicare va conduce sistemul la starea S1(S,x1*), știind care este posibil, folosind rezultatele. optimizare condiționată, găsiți controlul optim la a doua etapă și așa mai departe până la ultimul pas.

Lucrări de laborator Nr. 1 (Problemă de programare liniară)

Pentru o anumită formulare matematică a problemei LP, presupunând suplimentar condiția de non-negativitate a variabilelor, efectuați următoarele acțiuni:

Rezolvați problema metoda grafica;

Aduceți problema la forma canonică a notației;

Creați un tabel simplex;

Rezolvați problema folosind metoda simplex manual sau folosind un computer;

Efectuați formularea problemei LP duale;

Obține o soluție la problema duală din tabelul simplex obținut anterior și analizează rezultatele obținute;

Verificați rezultatele soluției în tabel procesor Excel;

Scrieți un raport care să conțină rezultatele pentru fiecare articol.

Resurse	Rezerve	Produse
		P1	P2
S1	18	0.2	3
S2	13.1	0.7	2
MV	23	2.3	2
Profit pe unitate de producție în U.E.		3	4

Metoda grafică. Pentru a construi un poligon soluție, transformăm sistemul original

, primim

Să desenăm liniile de delimitare.

Funcția liniară F=f(x) este ecuația dreptei c1x1 + c2x2 = const. Să reprezentăm grafic funcția obiectiv pentru f(x)=0. pentru a construi dreapta 3x1 + 4x2 = 0, se construiește vectorul rază N = (3; 4) și prin punctul 0 se trage o dreaptă perpendiculară pe acesta. Mutăm linia dreaptă construită F=0 paralelă cu ea însăși în direcția vectorului N.

Figura 1 – Metoda grafică

Din figura 1 rezultă că această dreaptă devine linia de referință în raport cu poligonul de soluții construit în punctul B, unde funcția F își ia valoarea maximă. Punctul B se află la intersecția dreptelor 0,7x1 + 2x2 ≤ 13,1 și 2,3x1 + 2x2 =23/ Pentru a-i determina coordonatele, rezolvăm sistemul de ecuații:

Plan optim de sarcini: x1 = 6.187; x2 = 4,38, înlocuind valorile lui x1 și x2 în funcția obiectiv, obținem Fmax = 3*6,187+4*4,38=36,08.

Astfel, pentru a obține profitul maxim de 36,06 USD, este necesar să planificați producția a 6 unități. produse P1 și 4 unități. produse P2.

Forma canonică a problemei LP. Să scriem problema alocării resurselor în formă canonică. Adăugând la sistem original restricții asupra variabilelor nenegative x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, avem:

Tabel simplex al LP. În cazul variabilelor de bază (x3, x4, x5), tabelul inițial simplex va arăta astfel:

Tabelul 1.

	-x1	-x2
x3 =	0,2	3	18
x4 =	0,7	2	13,1
x5 =	2,3	2	23
f(x) =	3	4

Ea corespunde deja planului de referință x(0) = T (coloana termenilor liberi).

Dintre problemele de optimizare din teoria deciziei, cele mai cunoscute sunt problemele de programare liniară, în care funcția maximizată F(X) este liniară, iar constrângerile A sunt specificate prin inegalități liniare. Să începem cu un exemplu (vezi).

Sarcina de producție. Atelierul poate produce scaune și mese. Este nevoie de 5 unități de material pentru a produce un scaun și 20 de unități (picioare de mahon) pentru a produce o masă. Un scaun necesită 10 ore de muncă, o masă necesită 15. Există 400 de unități de material și 450 de ore de muncă. Profitul pentru producerea unui scaun este de 45 USD, iar pentru producerea unei mese este de 80 USD. Câte scaune și mese trebuie să faci pentru a obține profit maxim?

Să notăm: X 1 - numărul de scaune realizate, X 2 - numărul de mese realizate. Problema de optimizare are forma:

45 X 1 + 80 X 2 → max,

5 X 1 + 20 X 2 ≤ 400,

10 X 1 + 15 X 2 ≤ 450,

Prima linie conține funcția obiectiv - profit la producerea X 1 scaune și X 2 mese. Trebuie maximizat prin alegere valori optime variabilele X 1 și X 2. În acest caz, trebuie îndeplinite restricții de material (a doua linie) - nu s-a folosit mai mult de 400 de picioare de lemn de mahon. Și, de asemenea, restricții de muncă (linia a treia) - nu mai mult de 450 de ore petrecute.

În plus, nu trebuie să uităm că numărul de mese și numărul de scaune sunt nenegative.

Astfel, constrângerile materiale sunt descrise ca un poligon convex, în special un triunghi. Acest triunghi se obține prin tăierea zonei adiacente originii din primul cadran. Separarea este efectuată printr-o linie dreaptă corespunzătoare celei de-a doua linii a problemei inițiale, înlocuind inegalitatea cu egalitatea. Linia dreaptă intersectează axa X 1, corespunzătoare scaunelor, în punctul (80.0). Asta înseamnă că dacă tot materialul ar fi folosit pentru a face scaune, s-ar face 80 de scaune. Aceeași linie dreaptă intersectează axa X 2, corespunzătoare tabelelor, în punctul (0,20). Asta înseamnă că dacă tot materialul ar fi folosit pentru a face mese, s-ar face 20 de mese. Pentru toate punctele din interiorul triunghiului, inegalitatea este satisfăcută, dar nu egalitatea - materialul va rămâne.

De asemenea pot fi descrise și restricțiile de muncă (Fig. 2).

Astfel, restricțiile de muncă sunt, de asemenea, descrise ca un triunghi. Acest triunghi se obține și prin tăierea zonei adiacente originii din primul cadran. Limitarea este efectuată printr-o linie dreaptă corespunzătoare celei de-a treia linie a problemei inițiale, înlocuind inegalitatea cu egalitatea. Linia dreaptă intersectează axa X 1, corespunzătoare scaunelor, în punctul (45.0). Asta înseamnă că dacă s-ar folosi toate resursele de muncă pentru a face scaune, s-ar fabrica 45 de scaune. Aceeași linie dreaptă intersectează axa X 2, corespunzătoare tabelelor, în punctul (0,30).

Aceasta înseamnă că dacă toți lucrătorii sunt desemnați să facă mese, vor fi făcute 30 de mese. Pentru toate punctele din interiorul triunghiului, inegalitatea este satisfăcută, nu egalitatea - unii dintre lucrători vor fi inactivi. Vedem asta solutie evidenta

nu - pentru producția de 80 de scaune există material, dar nu sunt destui muncitori, iar pentru producția de 30 de mese există forță de muncă, dar nu există material. Aceasta înseamnă că ambele trebuie făcute. Dar în ce raport? Pentru a răspunde la această întrebare, trebuie să „combini” Fig. 1 și Fig. 2, obținând suprafața solutii posibile

Astfel, setul de valori posibile pentru volumele de producție de scaune și mese (X 1, X 2) sau, în alți termeni, setul A, care stabilește restricții asupra parametrului de control în problema generală de optimizare, reprezintă intersecția a două triunghiuri, adică patrulater convex prezentat în Fig. 3. Cele trei vârfuri ale sale sunt evidente - acestea sunt (0,0), (45,0) și (0,20). A patra este intersecția a două linii drepte - limitele triunghiurilor din Fig. 1 și Fig. 2, adică. rezolvarea unui sistem de ecuații

5 X 1 + 20 X 2 = 400,

10 X 1 + 15 X 2 = 450.

Din prima ecuație: 5 X 1 = 400 - 20 X 2, X 1 = 80 - 4 X 2. Înlocuiți în a doua ecuație: 10 (80 - 4 X 2) + 15 X 2 = 800 - 40X 2 + 15 X 2 = 800 - 25 X 2 = 450, prin urmare, 25 X 2 = 350, X 2 = 14, de unde X 1 = 80 - 4 x 14 = 80 -56 = 24. Deci al patrulea vârf al patrulaterului este (24, 14).

Trebuie să găsim maximul unei funcții liniare pe un poligon convex. (ÎN caz general programare liniara - maximul unei functii liniare pe un poliedru convex situat intr-o dimensiune finita spațiu liniar.) Ideea de bază a programării liniare este că maximul este atins la vârfurile poligonului. În cazul general - la un vârf, iar acesta este singurul punct maxim. În special - în două, iar apoi segmentul care le conectează constă și din puncte maxime.

Funcția obiectiv 45 X 1 + 80 X 2 ia o valoare minimă de 0 la vârful (0,0). Pe măsură ce argumentele cresc, această funcție crește în dimensiune. La vârful (24.14) ia valoarea 2200. În acest caz, linia dreaptă 45 X 1 + 80 X 2 = 2200 trece între restricțiile directe 5 X 1 + 20 X 2 = 400 și 10 X 1 + 15 X 2 = 450, intersectându-se în același punct. Din aceasta, precum și din verificarea directă a celor două vârfuri rămase, rezultă că maximul funcției obiectiv, egal cu 2200, se realizează la vârful (24,14).

Astfel, rezultatul optim este: 24 de scaune și 14 mese. În acest caz, toate resursele materiale și toate resursele de muncă sunt folosite, iar profitul este egal cu 2.200 USD.

Problemă dublă. Fiecare problemă de programare liniară are o așa-numită problemă duală corespunzătoare. În ea, față de problema inițială, rândurile se transformă în coloane, inegalitățile își schimbă semnul, în loc de maxim se caută un minim (sau invers, în loc de un minim, se caută un maxim). Sarcina duală la cea duală este însăși sarcina originală. Să comparăm problema inițială (în stânga) și cea duală (în dreapta):

45 X 1 + 80 X 2 → max, 400 W 1 + 450 W 2 → min,

5 X 1 + 20 X 2 ≤ 400, 5 W 1 + 10 W 2 ≥ 45,

10 X 1 + 15 X 2 ≤ 450, 20 W 1 + 15 W 2 ≥ 80,

X 1 ≥ 0, W 1 ≥ 0,

X 2 ≥ 0. W2 ≥ 0.

De ce este atât de importantă sarcina dublă? Se poate dovedi că valorile optime ale funcțiilor obiectiv din problema originală și duală coincid (adică maximul din problema originală coincide cu minimul din problema duală). În acest caz, valorile optime ale lui W 1 și W 2 arată costul materialului și, respectiv, al forței de muncă, dacă sunt evaluate prin contribuția lor la funcția obiectiv. Pentru a evita confuzia cu prețurile de piață ale acestor factori de producție, W 1 și W 2 se numesc „estimari determinate în mod obiectiv” ale materiilor prime și ale forței de muncă.

Programarea liniară ca disciplină științifică și practică. Dintre toate problemele de optimizare, problemele de programare liniară se disting prin faptul că constrângerile lor sunt sisteme de inegalități sau egalități liniare. Constrângerile definesc poliedre liniare convexe într-un spațiu liniar finit. Funcțiile obiectiv sunt de asemenea liniare.

Astfel de probleme au fost rezolvate pentru prima dată de matematicianul sovietic L.V. Kantorovich (1912-1986) în anii 1930 ca sarcini ale managementului producției pentru a optimiza organizarea producției și procesele de producție, de exemplu, procesele de încărcare a mașinilor și de tăiat foi de materiale. După al Doilea Război Mondial, sarcini similare au fost preluate în Statele Unite. În 1975, T. Koopmans (1910-1985, născut în Olanda, a lucrat în principal în SUA) și academician al Academiei de Științe a URSS L.V. Kantorovich au primit premii Nobel pentru economie.

Să luăm în considerare câteva probleme de programare liniară.

Problemă de optimizare a amestecului (versiunea simplificată). La o uzină chimică pentru optimizare proces tehnologic trebuie să creați cel mai ieftin amestec care să conțină cantitatea necesară de anumite substanțe (să le notăm T și H).

Valoarea energetică a amestecului (în calorii) nu trebuie să fie mai mică decât valoarea specificată. Pentru simplitate, lăsați amestecul să fie format din două componente - K și C. Cât de mult din fiecare dintre ele ar trebui să fie inclusă în amestec? Datele inițiale pentru calcule sunt date în tabelul 3.

Tabelul 3. Date inițiale în problema de optimizare a amestecului.

3,8 K + 4,2 C → min,

0,10 K + 0,25 C ≥ 1,00,

1,00 K + 0,25 C ≥ 5,00,

110,00 K + 120,00 C ≥ 400,00,

Soluția sa grafică este prezentată în Fig. 4. Fig.4. Soluție grafică

În Fig. 4, pentru ușurința percepției, cele patru linii drepte sunt desemnate prin numere (1) - (4). Linia dreaptă (1) este linia dreaptă 1,00K + 0,25C = 5,00 (limită pentru substanța H). Trece, așa cum se arată în figură, prin punctele (5,0) pe axa absciselor și (0.20) pe axa ordonatelor. Vă rugăm să rețineți că valorile acceptabile ale parametrilor (K, C) se află deasupra liniei drepte (1), spre deosebire de cazurile considerate anterior în problema de producție anterioară.

Dreptul (2) este drept 110,00 K + 120,00 C = 400,00 (limită de calorii). Să observăm că în regiunea lui C non-negativ este situat peste tot sub linia dreaptă (1). Într-adevăr, acest lucru este adevărat atunci când K = 0, dreapta (1) trece prin punctul (0,20), iar dreapta (2) trece prin punctul (0, 400/120). Punctul de intersecție a două drepte se găsește la rezolvarea sistemului de ecuații

1,00 K + 0,25 C = 5,00,

110,00 K + 120,00 C = 400,00.

Din prima ecuație K = 5 - 0,25 C. Înlocuiți în a doua: 110 (5 - 0,25 C) + 120 C = 400, din care 550 - 27,5 C + 120 C = 400. Prin urmare, 150 = - 92,5 C , adică soluția este obținută pentru C negativ. Aceasta înseamnă că pentru toate C pozitive, linia dreaptă (2) se află sub linia dreaptă (1). Aceasta înseamnă că dacă restricțiile privind H sunt îndeplinite, atunci restricțiile calorice sunt în mod necesar îndeplinite. Ne confruntăm cu un nou fenomen - unele restricții din punct de vedere matematic se pot dovedi a fi inutile. Din punct de vedere economic, ele sunt necesare și reflectă trăsăturile esențiale ale enunțului problemei, dar înîn acest caz, structura internă a sarcinii s-a dovedit a fi astfel încât restricția calorică nu este implicată în formare zonă valabilă

parametrii și găsirea unei soluții.

În consecință, intervalul de valori admisibile ale parametrilor (K, C) este nelimitat de sus. Se distinge de întregul plan prin axele sale de coordonate (se află în primul cadran) și liniile drepte (1) și (4) (se află deasupra acestor drepte). Regiunea valorilor permise ale parametrilor (K, C) poate fi numită „poligon nelimitat”. Minimul funcției obiectiv 3,8 K + 4,2 C poate fi atins doar la vârfurile acestui „poligon”. Sunt doar trei vârfuri. Acestea sunt intersecții cu axele absciselor (10,0) și ordonatelor (0,20) ale dreptelor (1) și (4) (în fiecare caz, cea care satisface ambele restricții este luată din două intersecții). Al treilea vârf este punctul de intersecție al dreptelor (1) și (4), ale căror coordonate se găsesc la rezolvarea sistemului de ecuații

0,10 K + 0,25 C = 1,00,

1,00 K + 0,25 C = 5,00.

Din a doua ecuație K = 5 - 0,25 C, din prima 0,10 (5 - 0,25 C) + 0,25 C = 0,5 - 0,025 C + 0,25 C = 0,5 + 0,225 C = 1, de unde C = 0,5/0,225 = 20 9 și K = 5 - 5/9 = 40/9. Deci, A = (40/9; 20/9).

Linia dreaptă (3) din Fig. 4 este o linie dreaptă corespunzătoare funcției țintă 3,8 K + 4,2 C. Trece între liniile drepte (1) și (4), care stabilesc restricțiile, iar minimul este atins în punctul A , prin care trece o linie dreaptă (3). Prin urmare, minimul este 3,8x40/9 + 4,2x20/9 = 236/9. Problema optimizării amestecului a fost complet rezolvată.

Problema duală, construită după regulile descrise mai sus, are forma de mai jos (repetăm ​​aici problema inițială de optimizare a amestecului pentru a demonstra clar tehnologia de construire a problemei duale):

3,8 K + 4,2 C → min, W 1 + 5 W 2 + 400 W 3 → max,

0,10 K + 0,25 C ≥ 1,00, 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8,

1,00 K + 0,25 C ≥ 5,00, 0,25 W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2,

110,00 K + 120,00 C ≥ 400,00, W 1 ≥ 0,

K ≥ 0, W 2 ≥ 0,

C ≥ 0. W3 ≥ 0.

Valoarea minimă în problema directă, așa cum ar trebui să fie, este egală cu valoarea maxima V dubla problema, adică ambele numere sunt 236/9. Interpretarea variabilelor duale: W 1 este „costul” unei unități de substanță T, iar W 2 este „costul” unei unități de substanță H, măsurat „prin contribuția lor” la funcția obiectiv. În acest caz, W 3 = 0, deoarece limitarea numărului de calorii nu participă la formarea soluției optime. Deci, W 1, W 2, W 3 sunt așa-numitele. evaluări determinate obiectiv (după L.V. Kantorovich) ale resurselor (substanțe T și H, calorii).

Planificarea gamei de produse si a volumelor de productie. Să revenim la organizarea producției. Compania poate produce bucatarii automate (tip de oale), cafetiere si samovar. Tabelul 4 prezintă datele privind capacitatea de producție disponibilă la întreprindere (în unități de produse).

Tabelul 4. Capacitate de productie (in buc.)

		Aparate de cafea	samovari
Ștampilare
Volumul emisiunii
Profit specific (pe produs)

În acest caz, ștanțarea și finisarea sunt efectuate pe același echipament. Vă permite să ștampilați timp specificat sau 20.000 de bucătării, sau 30.000 de aparate de cafea, sau ambele, în cantitate nu mai mică. Dar asamblarea se realizează în zone separate.

Problema de programare liniară are forma:

X 1 ≥ 0, X 2 ≥ 0, X 3 ≥ 0, (0)

X 1/200 + X 2/300 + X 3/120 ≤ 100, (1)

X 1/300 + X 2/100 + X 3/100 ≤ 100, (2)

X 1/200 ≤ 100, (3)

X 2 / 120 ≤ 100, (4)

X 3 / 80 ≤ 100 , (5)

F = 15 X 1 + 12 X 2 + 14 X 3 → max.

Aici:
(0) este condiția obișnuită în economie pentru non-negativitatea variabilelor,
(1) - limitarea capacităților de ștanțare (exprimată ca procent pentru ușurința percepției),
(2) - limitarea opțiunilor de finisare,
(3) - restricții de asamblare pentru bucătării,
(4) - același pentru râșnițele de cafea,
(5) - același lucru pentru samovar (după cum sa menționat deja, toate cele trei tipuri de produse sunt asamblate pe linii separate).

În sfârșit, funcția obiectiv F este profitul total al întreprinderii.

Rețineți că inegalitatea (3) rezultă din inegalitatea (1), iar inegalitatea (4) rezultă din (2). Prin urmare, inegalitățile (3) și (4) pot fi imediat eliminate.

Să notăm imediat un fapt interesant. După cum se va stabili, în planul optim X 3 = 0, i.e. Nu este rentabil să produci samovar.

Anterior

În legătură cu dezvoltarea tehnologiei și creșterea producției industriale, sarcinile de a găsi solutii optimeîn diverse sfere ale activităţii umane. Instrumentul principal pentru rezolvarea acestor probleme a fost modelare matematică-- o descriere formală a fenomenului studiat și a cercetării folosind instrumente matematice.

Orice model al unui proces real presupune idealizare și abstractizare, dar acestea nu trebuie să se îndepărteze prea mult de conținutul problemei pentru ca modelul construit să nu piardă trăsăturile esențiale ale obiectului modelat, adică să-i fie adecvat. Pe de altă parte, dacă construiești un model complex care să ia în considerare toate caracteristici subtile procesului studiat, atunci aceasta poate încălca sensul modelării, unul dintre obiectivele căreia este simplificarea formulării problemei, astfel încât să fie mai ușor de studiat (un model prea complex, de regulă, nu poate fi analizat).

ÎN număr mareÎn cazuri, primul grad de aproximare la realitate este un model în care toate dependențele dintre variabilele care caracterizează starea obiectului sunt presupuse a fi liniare. Există o analogie completă aici cu cât de foarte importante și adesea cuprinzătoare sunt obținute informații despre comportamentul unei funcții arbitrare pe baza studiului derivatei sale - această funcție este înlocuită în vecinătatea fiecărui punct dependență liniară. Un număr semnificativ de procese economice, tehnice și de altă natură sunt descrise destul de bine și complet modele liniare. Aceasta determină importanța rolului jucat de programarea liniară - o metodă de găsire a extremului condiționat al unei funcții liniare pe o mulțime specificată folosind relații liniare precum egalități și inegalități (constrângeri liniare).

Condiții de aplicabilitate a modelului liniar

Divizibilitate. Dacă metoda este aplicată cu intensitățile a și b (a< b), то его можно применять с любой интенсивностью x .

Această condiție nu este banală. Dacă, de exemplu, intensitatea unui loc de muncă este măsurată prin numărul de lucrători alocați acestuia, atunci numai valorile întregi ale intensității sunt acceptabile. Dacă intensitatea este măsurată prin numărul de ore-om pe zi, atunci principiul divizibilității este aparent îndeplinit.

Proporționalitate. Intrările, ieșirile și utilitățile produse de fiecare metodă sunt proporționale cu intensitatea acesteia.

Aceasta este o condiție a randamentelor constante (în toate sensurile), a absenței economiilor de scară. O atenție deosebită trebuie acordată atenție identificării intervalului de intensitate al unei metode tehnologice în care această metodă satisface condiția de proporționalitate. De exemplu, dacă un sudor sudează un container în 6 ore, atunci doi sudori se pot ocupa probabil de treaba în 3 ore. Dar șase oameni nu vor găti un recipient într-o oră.

Aditivitate. Sunt însumate utilitățile și - pentru fiecare ingredient - costurile și output-urile produse prin toate metodele.

Principiul aditivității necesită o descriere atentă și consecventă a nomenclaturii incluse în model: metode tehnologice, ingrediente, utilități.

Forme pentru scrierea problemelor de programare liniară

În forma sa cea mai generală, problema LP este scrisă după cum urmează:

• 2 (2)
• 3 (3)

• 4 (4)
• 5 (5)

Definiție 1. Matricea se numește matricea problemei (1) - (5). ?

O reprezentare mai unificată a problemei LP este forma standard:

pentru i (1,…, m), x 0.

Caracteristicile formei standard: toate variabilele sunt nenegative (n1 = n), nu există restricții de egalitate (m1 = 0). Dacă CF este maximizat, atunci m2 = 0 și nu există restricții de forma (3); în caz contrar m2 = m și nu există restricții de forma (4). Crezând și forma standard se poate scrie astfel:

6c x max (min) la Ax () b, x 0. (6)

Dar cea mai simplă formă este forma canonică de scriere a problemelor LP.

Definiția 2. Problema (1) - (4) este prezentată în formă canonică dacă toate restricțiile, cu excepția condițiilor de nenegativitate a variabilelor, sunt egalități (m1 = m) și toate variabilele sunt nenegative (n1 = n) . ?

Problema LP în formă canonică are deci forma

• 7c x max (min) la Ax = b, x 0. (7)
• 1.2 Bazele metodei simplex

Să luăm în considerare problema LP în formă canonică:

• 9 (9)
• 10x 0 (10)

Fie și rândul i și respectiv coloana j a matricei A0. Vom presupune că rândurile matricei sunt liniar independente.

Orice problemă LP poate fi redusă la formă canonică; dacă o problemă în formă canonică este rezolvabilă, atunci printre soluțiile ei există cel puțin un punct extrem al mulțimii soluțiilor admisibile; punctele extreme ale setului de soluții admisibile la problema LP în formă canonică coincid cu BDD.

Pe baza faptelor de mai sus, ne putem imagina următoarea procedură rezolvarea problemei. Să verificăm într-un fel dacă problema are o soluție și, dacă da, să o aducem la forma canonică. Fie matricea A0 de formă canonică să aibă dimensiunea m × n și rangul m. Să construim toate m × m-submatrice ale matricei A0, eliminând cele degenerate, submatricele rămase corespund bazelor matricei A0; Să selectăm bazele admisibile dintre ele și să construim BFS-urile corespunzătoare. Să alegem un BDD care oferă maximul funcției obiectiv.

Dar un astfel de algoritm nu poate fi implementat în practică, deoarece numărul de BDD-uri crește exponențial odată cu dimensiunea problemei (numărul de variabile și/sau constrângeri). Procedura poate fi accelerată dacă este organizată în așa fel încât în ​​timpul procesului de enumerare a BDR să nu scadă valoarea CF (îmbunătățire consecventă a planului). Aceasta este ideea originală a metodei simplex, care este implementată după cum urmează.

1. 3 tabele simplex

programare liniară optimizare simplex

Transformările problemei LP în formă canonică, efectuate prin metoda simplex, sunt reprezentate convenabil ca transformări ale tabelelor simplex. Vederea generală a tabelului simplex, care corespunde iterației curente a metodei simplex, este prezentată în Tabelul 1.

ÎN linia de susînregistrate: titlul primei coloane, identificatorii tuturor (principal, suplimentar, auxiliar etc.) variabilele problemeiși ultimul titlu de coloană. Următoarele m linii descriu ecuațiile problemei sub forma:

pe care le au la începutul iterației. Mai întâi, este specificat identificatorul variabilei de bază (în baza curentă) pentru ecuația corespunzătoare. Urmează apoi coeficienții variabilelor (în ordinea în care sunt scrise variabilele pe prima linie). Ultimul element rândurile sunt partea dreaptă a constrângerii.

Linia de jos corespunde ecuației

12, unde și. (12)

reprezentand CF. Variabila z joacă în ea rolul unei variabile de bază (are coeficient de 1 și nu este inclusă în alte ecuații); numărul F este partea dreaptă a ecuației (12), valoarea CF pe soluția de bază curentă.

Tabelul 1. Vedere generală a tabelului simplex

Comentariu. Tabelul descrie sistemul de ecuații (11), astfel încât BDD-ul curent poate fi obținut prin setarea variabilelor de bază egale cu elementele corespunzătoare din ultima coloană, și variabilelor non-bazice egale cu zero. ?

La iterația luată în considerare, se întâmplă următoarele.

Dacă nu există elemente negative în rândul z sau în coloanele corespunzătoare variabilelor, atunci BDD-ul curent este optim și variabilele bazei optime sunt scrise în prima coloană a tabelului. În caz contrar, coloana variabilei xs pentru care s< 0, становится направляющим.

Dacă toate elementele coloanei ghid sunt nepozitive, atunci problema este nelimitată. În caz contrar, calculăm raportul dintre elementele ultimei și ale coloanelor de ghidare pentru toate rândurile care au un element pozitiv în coloana de ghidare. Rândul r pentru care acest raport este minim devine un ghid. În prima coloană a următorului tabel simplex, variabila xs va lua locul variabilei xj(r).

Acum ars este un element de activare. Elementele din următorul tabel simplex sunt calculate folosind formulele:

13 la la i r (13)

• 14 (14)
• 15 (15)

Se consideră j = j(k). Din (11) și (12) rezultă că coloana j (de bază) are un unu în rândul k și zerouri în rândurile rămase: j = 0, aij = 1 pentru i = k, în caz contrar aij = 0. Fie k r (coloana j se păstrează în noua bază). Atunci ari = 0 și din (13), (14), (16) rezultă că pentru toate i și. Ținând cont de acest lucru, să formulăm regulile pentru transformarea unui tabel simplex atunci când trecem la o nouă bază:

• · în antetul liniei de ghidare punem antetul coloanei de ghidare;
• · Împărțiți toate numerele liniei de ghidare la elementul de rezolvare;
• · coloana de ghidare devine una, cu una în rândul de ghidare;
• · coloanele bazei curente cu numere diferite de j(r) nu se modifică;
• · toate celelalte numere din tabel (inclusiv elementele din rândul de jos și din ultima coloană) sunt recalculate folosind formulele (13) - (15), (16).

Programare liniară

Programare liniară- o disciplină matematică dedicată teoriei și metodelor de rezolvare a problemelor extreme pe mulțimi de spațiu vectorial -dimensional definite prin sisteme de ecuații liniare și inegalități.

Programarea liniară este un caz special programare convexă, care la rândul său este un caz special de programare matematică. În același timp, stă la baza mai multor metode de rezolvare a problemelor de programare cu numere întregi și neliniare. O generalizare a programării liniare este programarea liniară fracțională.

Multe proprietăți ale problemelor de programare liniară pot fi, de asemenea, interpretate ca proprietăți ale poliedrelor și astfel formulate și dovedite geometric.

Poveste

Metoda punctului interior a fost menționată pentru prima dată de I. I. Dikin în 1967.

Sarcini

Problema principală (standard) de programare liniară se numește problema găsirii minimului unei funcții obiective liniare (forma liniară) de forma:

in conditii

, .

Problema programarii liniare va avea vedere canonică , dacă în problema principală în locul primului sistem de inegalități există un sistem de ecuații:

,

Problema principală poate fi redusă la una canonică prin introducerea unor variabile suplimentare.

Problemele de programare liniară de cea mai generală formă (probleme cu constrângeri mixte: egalități și inegalități, prezența variabilelor libere de constrângeri) pot fi reduse la unele echivalente (având același set de soluții) prin înlocuirea variabilelor și înlocuirea egalităților cu o pereche de inegalităților.

Este ușor de observat că problema găsirii maximului poate fi înlocuită cu sarcina găsirii minimului luând coeficienți cu semnul opus.

Exemple de probleme

Potrivire maximă

Luați în considerare problema de potrivire maximă într-un grafic bipartit: există mai mulți băieți și fete, iar pentru fiecare băiat și fată se știe dacă sunt atractivi unul pentru celălalt. Trebuie să mă căsătoresc număr maxim cupluri cu simpatie reciprocă.

Să introducem variabile care corespund perechii dintre -băiat și -fată și să satisfacem restricțiile:

cu funcţie obiectivă. Se poate arăta că printre soluțiile optime la această problemă există una întreagă. Variabilele egale cu 1 vor corespunde cuplurilor care ar trebui să fie căsătorite.

Debit maxim

Să existe un grafic (cu muchii orientate), în care pentru fiecare muchie să fie debitului. Și sunt date două vârfuri: dren și sursă. Este necesar să se indice pentru fiecare margine cât lichid va curge prin ea (nu mai mult decât capacitatea sa) astfel încât să se maximizeze debitul total de la sursă la scurgere (lichidul nu poate apărea sau dispărea la toate vârfurile cu excepția scurgerii și sursei).

Să luăm ca variabile cantitatea de lichid care curge prin coastă. Apoi

,

unde este capacitatea acelei margini. Aceste inegalități trebuie să fie completate de egalitatea cantității de fluid care intra și care iese pentru fiecare vârf, cu excepția scurgerii și sursei. Ca o funcție, este firesc să se ia diferența dintre cantitatea de fluid care iese și care intra la sursă.

O generalizare a problemei anterioare este fluxul maxim al costului minim. În această problemă, sunt date costurile pentru fiecare margine și trebuie să selectați debitul cu costul minim dintre fluxurile maxime. Această problemă se rezumă la două probleme de programare liniară: mai întâi trebuie să rezolvați problema debitului maxim și apoi adăugați la această problemă constrângerea , unde este cantitatea debit maxim, și rezolvați problema cu caracteristică nouă- costul fluxului.

Aceste probleme pot fi rezolvate mai repede decât algoritmi generali rezolvarea problemelor de programare liniara datorita structurii speciale a ecuatiilor si inegalitatilor.

Sarcina de transport

Există o anumită marfă omogenă care trebuie transferată de la depozite la fabrici. Pentru fiecare depozit se știe câtă marfă conține, iar pentru fiecare fabrică este cunoscută cererea de marfă. Costul transportului este proporțional cu distanța de la depozit la fabrică (se cunosc toate distanțele de la al-lea depozit la a--a fabrică). Este necesar să compuneți cel mai mult plan ieftin transport.

Variabilele decisive în acest caz sunt cantitățile de marfă transportate de la al-lea depozit la a-lea fabrică. Acestea îndeplinesc restricțiile:

Funcția obiectiv are forma: , care trebuie minimizată.

Joc cu sumă zero

Există o matrice de dimensiuni. Primul jucător alege un număr de la 1 la , al doilea - de la 1 la . Apoi verifică numerele și primul jucător primește puncte, iar al doilea jucător primește puncte (numărul ales de primul jucător primește al doilea). Trebuie să găsim strategia optimă pentru primul jucător.

Să presupunem că într-o strategie optimă, de exemplu, primul jucător trebuie să aleagă un număr cu probabilitate . Atunci strategia optimă este o soluție la următoarea problemă de programare liniară:

, , (),

în care funcția trebuie maximizată. Valoarea în soluția optimă va fi așteptarea primei primului jucător în cel mai rău caz.

Algoritmi de rezolvare

Cel mai faimos și utilizat pe scară largă în practică pentru a rezolva sarcină comună Programarea liniară (LP) este o metodă simplex. În ciuda faptului că metoda simplex este un algoritm destul de eficient care a arătat rezultate bune atunci când decide probleme aplicate LP, este un algoritm cu complexitate exponențială. Motivul pentru aceasta este natura combinatorie a metodei simplex, care enumeră secvenţial vârfurile poliedrului de soluţii fezabile atunci când se caută soluţia optimă.

Primul algoritm polinom, metoda elipsoidului, a fost propus în 1979 de matematicianul sovietic L. Khachiyan, rezolvând astfel problema pentru o lungă perioadă de timp rămas nerezolvată. Metoda elipsoidală are o natură complet diferită, necombinatorie decât metoda simplex. Cu toate acestea, din punct de vedere computațional, această metodă s-a dovedit a fi nepromițătoare. Cu toate acestea, însuși faptul complexității polinomiale a problemelor a condus la crearea unei clase întregi algoritmi eficienti LP - metode de punct interior, primul dintre care a fost algoritmul lui N. Karmarkar propus în 1984. Algoritmii de acest tip folosesc o interpretare continuă a problemei LP, când în loc să enumere vârfurile poliedrului pentru soluții la problema LP, se efectuează o căutare de-a lungul traiectoriilor în spațiul variabilelor problemei care nu trec prin vârfurile lui. poliedrul. Metoda punctului interior, care, spre deosebire de metoda simplex, traversează puncte din interiorul regiunii fezabile, utilizează metode de programare neliniară cu barieră logartică dezvoltate în anii 1960 de Fiacco și McCormick.

Vezi de asemenea

• Metodă grafică pentru rezolvarea unei probleme de programare liniară

Note

Literatură

• Thomas H. Corman și colab. Capitolul 29. Programarea liniara // Algoritmi: constructie si analiza = INTRODUCERE IN ALGORITMI. - Ed. a II-a. - M.: „Williams”, 2006. - P. 1296. - ISBN 5-8459-0857-4
• Akulich I.L. Capitolul 1. Probleme de programare liniară, Capitolul 2. Probleme speciale de programare liniară // Programarea matematică în exemple și probleme. - M.: Şcoala superioară, 1986. - 319 p. - ISBN 5-06-002663-9
• Karmanov V. G. Programare matematică. - editia a 3-a. - M.: Nauka, 1986. - 288 p.
• Danzig George Bernard „Amintiri despre începutul programării liniare”

Legături

• - Pachet de optimizare gratuit conceput pentru a rezolva probleme de programare liniare, întregi și obiective.
• Vershik A. M. „Despre L. V. Kantorovich și programarea liniară”
• Bolshakova I. V., Kuralenko M. V. „Programare liniară. Manual educațional și metodologic pentru test.”
• Barsov A. S. „Ce este programarea liniară”, Prelegeri populare despre matematică, Gostekhizdat, 1959.
• M. N. Vyalyi Inegalități liniare și combinatorie. - MCNMO, 2003.

Fundația Wikimedia.

• 2010.
• Salten, Felix

Glagow, Martina

Vedeți ce este „programarea liniară” în alte dicționare: programare liniară - - programare liniară O zonă de programare matematică dedicată teoriei și metodelor de rezolvare a problemelor extreme caracterizate printr-o relație liniară între ... ...

Programare liniară

Programare liniară Ghidul tehnic al traducătorului - un domeniu de programare matematică consacrat teoriei și metodelor de rezolvare a problemelor extreme caracterizate printr-o relație liniară între variabile. În forma sa cea mai generală, problema L.p. se poate scrie asa. Dana......

Dicționar economic și matematic Programarea liniară este una dintre cele mai importante ramuri ale matematicii, studiind teorii și metode de rezolvare. anumite sarcini . Această disciplină matematică a devenit ultimii ani utilizat pe scară largă în diverse zone economie, tehnologie și afaceri militare, unde planificarea matematică și utilizarea digitalului automat. calculatoare Această secțiune

știința studiază modele de optimizare liniară. Cu alte cuvinte, programarea liniară este despre numere

Termenul de „programare liniară” a fost propus pentru prima dată de economistul american T. Koopmans în 1951. În 1975. Matematicianul rus L.V. Kantorovich și T. Koopmans au primit Premiul Nobel pentru Științe Economice pentru contribuția lor la teoria alocării optime a resurselor. T. Koopmans a promovat metode de programare liniară și a apărat prioritățile lui L.V Kantorovich, care a descoperit aceste metode. Istoria programării liniare în SUA datează din 1947, când J. Danzig a scris despre aceasta în lucrarea sa. L.V. Kantorovich a studiat posibilitatea aplicării matematicii în probleme de planificare, pe baza căreia monografia sa " Metode matematice organizarea și planificarea producției." Cea mai importantă descoperire (descoperire) a lui L.V. Kantorovich a fost capacitatea de a formula clar matematic cele mai importante sarcini de producție

Dacă primele lucrări ale lui L.V Kantorovich ar fi primit o evaluare adecvată la vremea lor, atunci ar exista o probabilitate mare de avansare și mai mare a programării liniare în prezent. Din păcate, opera sa a rămas neclară atât în ​​Uniunea Sovietică, cât și în afara ei, și după cum notează Dantzig: „...și în acest timp programarea liniară a devenit o adevărată artă”.

Designul optim al oricărui program liniar ar trebui să fie asociat automat cu preturi optime sau, potrivit lui L.V. Kantorovich, cu „evaluări determinate în mod obiectiv”. Această acumulare de cuvinte a fost menită să sporească „critica” termenului. Esența descoperirii economice a lui L.V. Kantorovich constă în relația dintre soluțiile optime și prețurile optime.

Metode de programare liniară

Folosind metode de programare liniară se rezolvă un număr mare de probleme extreme legate de economie. În aceste cazuri se găsesc valorile extreme (maximum și minim) ale unor funcții de mărimi variabile.

Baza programării liniare este soluția unui sistem de ecuații liniare, care sunt transformate în ecuații și inecuații. Este caracterizat expresie matematică cantități variabile, o anumită ordine, succesiune de calcule, analiză logică. Este aplicabil:

• în prezența certitudinii matematice și a limitărilor cantitative între variabilele și factorii studiati;
• când factorii sunt interschimbabili datorită succesiunii de calcule;
• în cazul îmbinării logicii matematice cu o înţelegere a esenţei fenomenelor studiate.

În producția industrială, această metodă ajută la calcularea productivității globale optime a mașinilor, unităților, liniilor de producție (dacă sunt date gama de produse și valorile corespunzătoare), precum și la rezolvarea problemei utilizării raționale a materialelor (cu cele mai multe cantitate profitabilă de piese de prelucrat).

În agricultură, această metodă este folosită pentru a determina costul minim al rațiilor de furaje, ținând cont de o anumită cantitate de furaj (pe baza tipurilor și nutrienților pe care îi conțin).

În turnătorie această metodă ajută la rezolvarea problemei amestecurilor incluse în sarcina metalurgică. Aceeași metodă ne permite să rezolvăm problema transportului, problema atașării cât mai optime a întreprinderilor consumatoare de întreprinderile producătoare de produse.

O trăsătură distinctivă a tuturor problemelor economice care pot fi rezolvate prin metode de programare liniară este alegerea opțiunilor de soluție, precum și anumite condiții limitative. Rezolvarea unei astfel de probleme înseamnă alegerea celei mai optime dintre toate opțiunile alternative.

Valoarea esențială a utilizării metodelor de programare liniară în economie este alegerea cea mai mare varianta optima din cantitate uriașă toate opțiunile posibile. Este aproape imposibil să rezolvi astfel de probleme în alte moduri pentru a găsi gradul de raționalitate în utilizarea resurselor în producție.

Una dintre principalele probleme rezolvate prin programarea liniară este problema transportului, care urmărește reducerea la minimum a rulajului de marfă a bunurilor de larg consum la livrarea acestora de la producător la consumator.