Cine a creat metoda de programare liniară. Conceptul de programare liniară. Tipuri de probleme de programare liniară

Programarea liniară este una dintre cele mai importante ramuri ale matematicii, studiind teorii și metode de rezolvare a anumitor probleme. Această disciplină matematică a devenit utilizată pe scară largă în ultimii ani în diverse domenii ale economiei, tehnologiei și afacerilor militare, unde planificarea matematică și utilizarea calculatoarelor digitale automate joacă un rol important în dezvoltarea lor. Această ramură a științei studiază modelele 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 a fost publicată în 1939 monografia sa „Metode matematice de organizare și planificare a producției”. Cea mai importantă descoperire (descoperire) a lui L.V. Kantorovich a fost capacitatea de a formula clar matematic cele mai importante probleme de producție, ceea ce face posibilă găsirea unei abordări cantitative a acestor probleme, precum și rezolvarea lor prin metode numerice.

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 nefericire, opera sa a rămas neclară atât în ​​Uniunea Sovietică, cât și nu numai, și după cum notează Danzig: „...și în acest timp programarea liniară a devenit o adevărată artă”.

Planul optim al oricărui program liniar ar trebui să fie asociat automat cu prețuri optime sau, potrivit lui L.V. Kantorovich, cu „estimari determinate în mod obiectiv”. Această acumulare de cuvinte era 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. Se caracterizează printr-o expresie matematică a variabilelor, o anumită ordine, succesiune de calcule și 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 număr 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 producția de 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 celei mai optime opțiuni dintr-un număr mare de opțiuni 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.

Metodele de programare liniară sunt folosite pentru a rezolva multe probleme extreme care sunt adesea tratate în economie. Rezolvarea unor astfel de probleme se reduce la găsirea valorilor extreme (maximum și minim) ale unor funcții de mărimi variabile.
Programarea liniară se bazează pe rezolvarea unui sistem de ecuații liniare (cu transformare în ecuații și inegalități), când relația dintre fenomenele studiate este strict funcțională. Se caracterizează printr-o expresie matematică a variabilelor, o anumită ordine, succesiune de calcule (algoritm) și analiză logică. Poate fi utilizat numai în cazurile în care variabilele și factorii studiati au certitudine matematică și limitări cantitative, când, ca urmare a unei succesiuni cunoscute de calcule, factorii sunt interschimbabili, când logica din calcule, logica matematică sunt combinate cu o înţelegere logică a esenţei fenomenului studiat.
Folosind această metodă în producția industrială, de exemplu, se calculează productivitatea globală optimă a mașinilor, unităților, liniilor de producție (pentru o gamă dată de produse și alte valori date) și se rezolvă problema tăierii raționale a materialelor (cu randament optim a pieselor de prelucrat). În agricultură, este folosit pentru a determina costul minim al rațiilor de furaje pentru o anumită cantitate de furaj (după tip și nutrienți conținuti în acestea). Problema amestecului poate găsi aplicație și în producția de turnătorie (compoziția încărcăturii metalurgice). Aceeași metodă este folosită pentru a rezolva problema transporturilor, problema atașării raționale a întreprinderilor de consum de întreprinderile producătoare.
Toate problemele economice rezolvate prin programarea liniară se disting prin soluții alternative și anumite condiții limitative. A rezolva o astfel de problemă înseamnă a alege cel mai bun, Optimal, dintre toate opțiunile (alternative) admisibile posibile. Importanța și valoarea utilizării metodei de programare liniară în economie constă în faptul că opțiunea optimă este selectată dintr-un număr foarte semnificativ de opțiuni alternative. Este aproape imposibil să rezolvi astfel de probleme folosind alte metode.

Ca exemplu, luați în considerare rezolvarea problemei utilizării raționale a timpului de funcționare a echipamentelor de producție.
Conform planului operațional, secția de șlefuire a produs în prima săptămână a lunii decembrie 500 inele pentru rulmenți de tip A, 300 inele pentru rulmenți de tip B și 450 inele pentru rulmenți de tip B. Toate inelele au fost șlefuite pe două mașini interschimbabile de capacități diferite. Timpul mașinii pentru fiecare mașină este de 5000 de minute. Complexitatea operațiunilor (în minute pe inel) în fabricarea diferitelor inele este caracterizată de următoarele date (Tabelul 6.5).
Tabelul 6.5
Este necesar să se determine opțiunea optimă pentru distribuirea operațiunilor între mașini și timpul care ar fi petrecut cu această opțiune optimă. Să finalizăm sarcina folosind metoda simplex.
Pentru alcătuirea unui model matematic al acestei probleme, introducem următoarele simboluri: jc, x2, xъ, - respectiv, numărul de inele pentru rulmenți de tipurile L, B, B, produse pe mașina I; x4, x5, x6 - respectiv, numărul de inele pentru rulmenți de tipurile A, B, C, produse pe mașina II.
Forma liniară care reflectă criteriul de optimitate va arăta astfel:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 cu restricții
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Să transformăm condiția problemei prin introducerea de variabile suplimentare (auxiliare) și fictive. Să scriem condiția astfel:
spike lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Un sistem de ecuații care reflectă condițiile restrictive ale timpului computerului și cantitatea de produse produse:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Soluția la această problemă este prezentată în tabel. 6.6. Opțiunea optimă a fost obținută în a șaptea etapă (iterație). Dacă mașina I producea 125 de inele de lagăre de tip A, 450 de inele de lagăr de tip B și mașina II a produs 375 de inele de rulment de tip A și 300 de inele de lagăr de tip B, atunci cu o astfel de încărcătură de echipament ar fi 350 de minute de timp de mașină. eliberat pentru mașina II. Timpul total petrecut sub opțiunea optimă ar fi de 9650 de minute, în timp ce de fapt s-au petrecut 10.000 de minute de timp pe calculator.
O problemă foarte tipică rezolvată folosind programarea liniară este problema transportului. Semnificația sa este de a minimiza cifra de afaceri de marfă atunci când se livrează bunuri de larg consum de la producător la consumator, de la depozitele și bazele angro până la punctele de vânzare cu amănuntul. Poate fi rezolvată folosind metoda simplex sau metoda distribuției.
Soluția problemei transportului prin metoda distribuției a fost dată în cea de-a treia ediție a manualului „Teoria analizei economice” („Finanțe și statistică”, 1996).

Rezolvarea problemei utilizării raționale a mașinilor-unelte folosind metoda simplex

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

Programarea liniară (LP) este una dintre primele și cele mai amănunțite ramuri ale programării matematice. 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 de aplicare practică largă, precum și armoniei sale matematice.

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 utilizată în rezolvarea problemelor economice, cum ar fi managementul și planificarea producției; în sarcinile de determinare a amplasării optime a echipamentelor pe nave maritime și î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, constă în găsirea minimului (sau maximului) unei funcții liniare sub constrângeri 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 unui 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 intervalele maxime care asigură realizabilitatea fizică a unui obiect sau proces dat. 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ă un număr mare de opțiuni de comportament care aduc rezultate diferite, dintre care este necesar să alegeți cel mai bun unu. Programarea dinamică abordează rezolvarea unei anumite clase de probleme prin descompunerea lor în probleme mai mici, mai puțin complexe. În principiu, problemele de acest fel pot fi rezolvate prin căutarea prin toate opțiunile posibile și alegerea celei mai bune dintre ele, dar de multe ori 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 de 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 o metodă de soluție universală. Aproape fiecare problemă rezolvată prin această metodă se caracterizează prin propriile caracteristici și necesită căutarea celui mai potrivit set de metode pentru a o rezolva. Î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; întocmirea planurilor calendaristice pentru reparațiile curente și majore ale echipamentelor și înlocuirea acestora; cauta cele mai scurte distante de pe 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 la un k-lea pas dat. Î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, este selectat un control optim X*k, astfel încât rezultatul care este atins în pași de la a k-a la a n-a tură 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 general, problema de programare dinamică se formulează astfel: se cere determinarea unui control X* care transferă sistemul din starea inițială S0 în starea finală Sn, la care funcția obiectiv F(S0,X*) ia cea mai mare (cea mai mică) 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 (fără 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 controalelor optime 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 de la ultimul în conformitate cu algoritmul de baleiaj înapoi. La ultimul 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 ale variabilei de control X pentru k și S.

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 optimizării condiționate, să se găsească controlul optim la a doua. pas și așa mai departe până la ultimul pas.

Lucrare 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 grafic;

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

Creați un tabel simplex;

Rezolvați o problemă 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 foaia de calcul Excel;

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

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 unei drepte c1x1 + c2x2 = const. Să reprezentăm grafic funcția obiectiv pentru f(x)=0. pentru a construi dreapta 3x1 + 4x2 = 0, construiți vectorul rază N = (3; 4) și prin punctul 0 trageți o dreaptă perpendiculară pe acesta. Mutăm linia dreaptă construită F=0 paralelă cu ea însăși în direcția vectorului N.

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 variabile nenegative x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 la sistemul original de constrângeri, avem:

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

Tabelul 1.

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

În legătură cu dezvoltarea tehnologiei și creșterea producției industriale, sarcina de a găsi soluții optime în diverse sfere ale activității umane joacă un rol din ce în ce mai important. Instrumentul principal pentru rezolvarea acestor probleme a fost modelarea matematică - o descriere formală a fenomenului studiat și cercetarea 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ă construiți un model complex care ia în considerare toate trăsăturile subtile ale procesului studiat, acest lucru poate încălca sensul modelării, unul dintre obiectivele căreia este simplificarea formulării problemei, astfel încât este mai ușor de studiat (un model prea complex, de regulă, nu poate fi analizat) .

Într-un număr mare de 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 cu o dependență liniară. Un număr semnificativ de procese economice, tehnice și de altă natură sunt descrise destul de bine și complet de 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 satisfăcut.

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ă 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). Presupunând și, forma standard poate fi scrisă după cum urmează:

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ă pentru 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.

Linia de sus conține: titlul primei coloane, identificatorii tuturor variabilelor sarcinii (principale, suplimentare, auxiliare etc.) și titlul ultimei coloane. 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 al liniei este 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

Cometariu. 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ă, iar a celor nebază 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).

Această metodă este o metodă de enumerare intenționată a soluțiilor de referință la o problemă de programare liniară. Permite, într-un număr finit de pași, fie să se găsească o soluție optimă, fie să se stabilească că nu există o soluție optimă.

1. Indicați o metodă pentru găsirea soluției de referință optime
2. Indicați metoda de trecere de la o soluție de referință la alta, la care valoarea funcției obiectiv va fi mai apropiată de cea optimă, adică. indica o modalitate de a îmbunătăți soluția de referință
3. Stabiliți criterii care vă permit să opriți imediat căutarea soluțiilor de asistență la soluția optimă sau să trageți o concluzie despre absența unei soluții optime.

Algoritmul metodei simplex pentru rezolvarea problemelor de programare liniară

1. Aduceți problema în formă canonică
2. Găsiți soluția de suport inițială cu o „bază unitară” (dacă nu există o soluție de suport, atunci problema nu are o soluție din cauza incompatibilității sistemului de constrângeri)
3. Calculați estimări ale descompunerilor vectoriale pe baza soluției de referință și completați tabelul metodei simplex
4. Dacă criteriul de unicitate al soluției optime este îndeplinit, atunci soluția problemei se termină
5. Dacă este îndeplinită condiția existenței unui set de soluții optime, atunci toate soluțiile optime se găsesc prin enumerare simplă

Un exemplu de rezolvare a unei probleme folosind metoda simplex

Rezolvați problema folosind metoda simplex:

Soluţie:

Aducem problema în formă canonică.

Pentru a face acest lucru, introducem o variabilă suplimentară x 6 cu coeficient +1 în partea stângă a primei constrângeri de inegalitate. Variabila x 6 este inclusă în funcția obiectiv cu un coeficient de zero (adică nu este inclusă).

Primim:

Găsim soluția inițială de suport. Pentru a face acest lucru, echivalăm variabilele libere (nerezolvate) cu zero x1 = x2 = x3 = 0.

Primim soluție de referință X1 = (0,0,0,24,30,6) cu baza unitară B1 = (A4, A5, A6).

Noi calculăm estimări ale descompunerilor vectoriale condiții pe baza soluției de referință conform formulei:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vector de coeficienți ai funcției obiectiv pentru variabilele de bază
• X k = (x 1k, x 2k, ..., x mk) - vector de expansiune a vectorului corespunzător A k în funcție de baza soluției de referință
• C k este coeficientul funcției obiectiv pentru variabila x k.

Estimările vectorilor incluși în bază sunt întotdeauna egale cu zero. Soluția de referință, coeficienții de expansiune și estimările expansiunilor vectorilor de condiție bazate pe soluția de referință sunt scrise în tabel simplex:

În partea de sus a tabelului, pentru ușurința calculului estimărilor, se scriu coeficienții funcției obiectiv. În prima coloană „B” sunt înscriși vectorii incluși în baza soluției de referință. Ordinea în care acești vectori sunt scriși corespunde numărului de necunoscute permise în ecuațiile de constrângere. În a doua coloană a tabelului „C b” se scriu în aceeași ordine coeficienții funcției obiectiv pentru variabilele de bază. Cu aranjarea corectă a coeficienților funcției obiectiv în coloana „C b”, estimările vectorilor unitari incluși în bază sunt întotdeauna egale cu zero.

În ultimul rând al tabelului cu estimări ale Δ k în coloana „A 0” sunt scrise valorile funcției obiectiv pe soluția de referință Z(X 1).

Soluția suport inițial nu este optimă, deoarece în problema maximă estimările Δ 1 = -2, Δ 3 = -9 pentru vectorii A 1 și A 3 sunt negative.

Conform teoremei de îmbunătățire a soluției suport, dacă într-o problemă de maxim cel puțin un vector are o estimare negativă, atunci puteți găsi o nouă soluție suport pe care valoarea funcției obiectiv va fi mai mare.

Să determinăm care dintre cei doi vectori va duce la o creștere mai mare a funcției obiectiv.

Incrementul functiei obiectiv se gaseste prin formula: .

Calculăm valorile parametrului θ 01 pentru prima și a treia coloană folosind formula:

Se obține θ 01 = 6 pentru l = 1, θ 03 = 3 pentru l = 1 (Tabelul 26.1).

Găsim incrementul funcției obiectiv la introducerea în bază a primului vector ΔZ 1 = - 6*(- 2) = 12, iar al treilea vector ΔZ 3 = - 3*(- 9) = 27.

În consecință, pentru o abordare mai rapidă a soluției optime, este necesar să se introducă vectorul A3 în baza soluției de referință în locul primului vector al bazei A6, deoarece minimul parametrului θ 03 este atins în primul rând ( l = 1).

Efectuăm transformarea Jordan cu elementul X13 = 2, obținem a doua soluție de referință X2 = (0,0,3,21,42,0) cu baza B2 = (A3, A4, A5). (Tabelul 26.2)

Această soluție nu este optimă, deoarece vectorul A2 are o estimare negativă Δ2 = - 6. Pentru a îmbunătăți soluția, este necesar să se introducă vectorul A2 în baza soluției de referință.

Determinăm numărul vectorului derivat din bază. Pentru a face acest lucru, calculăm parametrul θ 02 pentru a doua coloană, este egal cu 7 pentru l = 2. În consecință, derivăm al doilea vector de bază A4 din bază. Efectuăm transformarea Jordan cu elementul x 22 = 3, obținem a treia soluție de referință X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabelul 26.3).

Această soluție este singura optimă, deoarece pentru toți vectorii care nu sunt incluși în bază estimările sunt pozitive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Răspuns: max Z(X) = 201 la X = (0,7,10,0,63).

Metoda de programare liniară în analiza economică

Metoda de programare liniară face posibila justificarea celei mai optime solutii economice in conditii de restrictii severe legate de resursele folosite in productie (mijloace fixe, materiale, resurse de munca). Utilizarea acestei metode în analiza economică face posibilă rezolvarea problemelor legate în principal de planificarea activităților unei organizații. Această metodă ajută la determinarea cantităților optime de producție, precum și a direcțiilor de utilizare cât mai eficientă a resurselor de producție disponibile organizației.

Prin această metodă se rezolvă așa-numitele probleme extreme, care constă în găsirea valorilor extreme, adică a maximului și minimului de funcții ale mărimilor variabile.

Această perioadă se bazează pe rezolvarea unui sistem de ecuații liniare în cazurile în care fenomenele economice analizate sunt legate printr-o dependență liniară, strict funcțională. Metoda de programare liniară este utilizată pentru a analiza variabilele în prezența anumitor factori limitatori.

Este foarte comun să se rezolve așa-numita problemă de transport folosind metoda de programare liniară. Conținutul acestei sarcini este de a minimiza costurile suportate în legătură cu exploatarea vehiculelor sub restricțiile existente privind numărul de vehicule, capacitatea lor de transport, durata de funcționare a acestora, dacă este nevoie de deservirea numărului maxim de clienți.

În plus, această metodă este utilizată pe scară largă în rezolvarea problemei de programare. Această sarcină constă într-o astfel de distribuție a timpului de funcționare pentru personalul unei organizații date, care ar fi cea mai acceptabilă atât pentru membrii acestui personal, cât și pentru clienții organizației.

Această sarcină este de a maximiza numărul de clienți deserviți în condiții de limitare a numărului de membri ai personalului disponibil, precum și a fondului de timp de lucru.

Astfel, metoda programării liniare este foarte comună în analiza plasării și utilizării diverselor tipuri de resurse, precum și în procesul de planificare și prognoză a activităților organizațiilor.

Cu toate acestea, programarea matematică poate fi aplicată și acelor fenomene economice, relația dintre care nu este liniară. În acest scop, pot fi utilizate metode de programare neliniară, dinamică și convexă.

Programarea neliniară se bazează pe natura neliniară a funcției obiectiv sau a constrângerilor, sau ambele. Formele funcției obiective și constrângerile de inegalitate în aceste condiții pot fi diferite.

Programarea neliniară este utilizată în analiza economică, în special, atunci când se stabilește relația dintre indicatorii care exprimă eficiența activităților unei organizații și volumul acestei activități, structura costurilor de producție, condițiile pieței etc.

Programarea dinamică se bazează pe construirea unui arbore de decizie. Fiecare nivel al acestui arbore servește drept etapă pentru determinarea consecințelor unei decizii anterioare și pentru eliminarea opțiunilor ineficiente pentru acea decizie. Astfel, programarea dinamică are o natură în mai multe etape, în mai multe etape. Acest tip de programare este folosit în analiza economică pentru a găsi opțiuni optime pentru dezvoltarea unei organizații atât acum, cât și în viitor.

Programarea convexă este un tip de programare neliniară. Acest tip de programare exprimă natura neliniară a relației dintre rezultatele activităților unei organizații și costurile acesteia. Programarea convexă (aka concavă) analizează funcțiile obiective convexe și sistemele de constrângeri convexe (puncte de fezabilitate). Programarea convexă este utilizată în analiza activităților economice cu scopul de a minimiza costurile, iar programarea concavă în scopul maximizării veniturilor sub restricțiile existente asupra acțiunii factorilor care influențează în sens invers indicatorii analizați. În consecință, cu tipurile de programare luate în considerare, funcțiile obiectiv convexe sunt minimizate, iar funcțiile obiectiv concave sunt maximizate.