problemă de programare liniară au fost primul studiu detaliat al sarcinii de a găsi funcțiile extremum în prezența unor constrângeri inegalități. Prezența pe termen lung în numele de „programare“, deoarece primele studii și prima aplicare a problemelor de optimizare liniare au fost în domeniul economiei. Cuvântul englezesc «programare» înseamnă planificarea, pregătirea planurilor și programelor. Destul de firesc, terminologia reflectă relația strânsă care există între formularea matematică a problemei și interpretarea economică (studiul program economic optim). Termenul „programării liniare“, a fost propus de George. Danzig în 1949 pentru a studia problemele teoretice și algoritmice legate de optimizarea funcțiilor liniare cu constrângeri liniare.
Globală de programare liniară obiectiv (ZLP) se face referire la problema
și componenta non-conditie negativitate
Aici - sunt date numere reale, funcția este numită ținta. Vector - plan de sarcină. Un plan care satisface constrângerile de sistem (1.2), este admisibilă. Planul acceptabil, în care funcția obiectiv atinge o valoare maximă sau minimă se numește optimă. În următoarele cazuri:
1. numai planul optim;
2. Planurile optime set infinit;
3. Funcția obiectiv este nemărginit în setul de planuri fezabile;
Soluții admisibile 4. Domeniul constau dintr-un punct în care funcția obiectiv atinge simultan valorile maxime și minime.
EXEMPLUL 1 Luați în considerare următoarele ZLP
Noi rezolva această problemă grafic. Pentru a face acest lucru, vom construi un sistem de coordonate cartezian plan. Fiecare dintre inegalitățile (1.3) determină pe unele semiplanului. Intersecția orice număr de semiplanuri este un set convexă.
Să ne amintim că convexă se numește un set, oricare două puncte care pot fi conectate printr-un segment de linie, toate ale căror puncte aparțin setului. Un exemplu de un set convex este un triunghi.
Am construi două puncte fiecare dintre liniile de delimitare
Acestea sunt prezentate în Fig. 1.
Acum, în orice punct (de exemplu, la punctul O (0,0)) definesc modul în care se face semnul inegalității și selectați semiplanul dorit. Intersecția semiplanurilor selectate vor fi un triunghi, o multitudine de puncte ale triunghiului este fezabil set de soluții ZLP (1.3). Figura 1 prezintă triunghiul este pictat o culoare închisă.
Acum vom construi linia de nivelul functiei obiectiv
De origine pentru a construi un vector gradient,
ale căror componente sunt coeficienții funcției obiectiv. Acest vector indică direcția cea mai abruptă creștere funcției. Pentru simplificare figură arată vectorul.
Ne mutăm linia de nivel în direcția gradientului până la intersecția cu politopii de soluții fezabile. Primul punct de intersecție M este un punct de minim. Coordonatele acestui punct M (2,1) este determinată din sistem
Astfel, ZLP planul optim (1.3) este. Sfârșitul problemei.
Simetric de înregistrare forma ZLP este problema
Problemele economice ale teoriei (1.4) și (1.5) sunt cele mai frecvente.
În cele din urmă, canonic formoyzapisi ZLP numit sarcină
problema restricțiilor impuse de sistem (1.6) reprezintă un sistem algebric liniar. În matrice formă poate fi scrisă ca
ZLP pentru a avea o soluție, ea limitează sistemul ar trebui să fie de colaborare. Acest lucru este posibil, dacă rangul coincide cu rangul matricei augmented. denota
Variabilele ZLP corespunzătoare vectorilor de bază sunt numite de bază și desemnate BP. Variabilele rămase sunt libere și sunt desemnate de către societatea în comun. În cazul variabilelor libere egale cu zero, și în care variabilele de bază vor fi valori non-negative, soluția parțială rezultată (1.7) se numește soluție de referință (în sus).
Noi spunem că sistemul de constrângere (1,7) are formă preferată ZLP. în cazul în care partea dreapta a nonnegativeness partea stângă a constrângerii conține o variabilă care apare cu un coeficient egal cu unitatea, iar în constrângerile de odihnă-egalitate - un factor egal cu zero. De exemplu, în sistemul de constrângeri
prima și a doua constrângeri preferate speciile, iar al treilea - nu.
. G. Zh.Fure în 1820 și apoi în 1947 de către J. Danzig a propus o enumerare metodă direcționată de vârfuri adiacente în direcția creșterii funcției țintă - metoda simplex. a devenit un important în rezolvarea problemelor de programare liniară. academician sovietic, laureat al Premiului Nobel (1975) LV Kantorowicz, a formulat o serie de probleme de programare lineară și a sugerat (1939), metoda de rezolvare a acestora (metoda de rezolvare a multiplicatori), ușor diferită de metoda simplex.
O metodă de rezolvare a ZLP numit simplex. Se aplica numai înregistrarea forma canonică. Transformarea formei de înregistrare ZLP simetrice canonice. Să presupunem că problema inițială are forma (1.4). Introducem m variabile suplimentare Pentru a converti tipul de inegalitate în egalitate, vom adăuga la partea stângă a variabilelor suplimentare. Funcția obiectivă a acestor variabile intră cu coeficienți zero. Constrângerile de sistem din (1.4), ia forma
variabile de bază - - Aici gratuite. Prin urmare, programul de sprijin inițial va arăta.
Acum, ia în considerare problema (1.5). M introduce, de asemenea, variabile suplimentare, dar la inegalitățile de tip pentru a converti la capitaluri proprii, se scade din laturile din stânga ale variabilelor suplimentare. (În funcția obiectiv al acestor variabile intră cu coeficienți zero.)
Acum, cu toate acestea, sistemul are restricții formă preferată, deoarece variabilele suplimentare sunt în partea stângă (at) cu coeficienți egal cu -1. Prin urmare, planul de bază
Este inacceptabil. În acest caz, acesta a introdus o bază artificială. Variabilele funcția obiectiv sunt introduse cu un coeficient. în cazul în care - un mare număr pozitiv.
Problema rezultată se numește M-sarcină. referința corespunzătoare. Ea are întotdeauna o vedere preferată. Programul ei de sprijin inițial are
Să original ZLP arată
Mai mult, nici una dintre limitele nu sunt preferate variabile. M -problem scris ca
în cazul în care semnul + în funcția obiectiv se referă la problema la un nivel minim. Programul de sprijin inițială în acest caz este
Dacă unele dintre limitările sistemului sunt o formă preferată, nu ar trebui să se acorde variabile artificiale în acesta.
Exemplul 2. Se consideră următorul ZLP
Aici este problema de a forma canonică prin introducerea de variabile suplimentare
A doua ecuație nu conține variabila de bază, astfel încât se adaugă la această ecuație baza artificială. Rezultatul este o M-problemă
Să presupunem acum că forma preferată a ZLP
Problema (1.9) este scris în tabel, care se numește simplex
Aici, în primul rând sunt coeficienții funcției obiectiv în cazul în care variabilele relevante. În prima coloană sunt coeficienții funcției obiective ale variabilelor de bază.
Dăm acum teoremele de bază ale metodei simplex.
Teorema 1. Să presupunem că problema inițială este rezolvată la maxim. Dacă dintr-un program de sprijin toate estimările sunt non-negativ, atunci planul este optim.
Teorema 2. Să presupunem că problema inițială este rezolvată, cel puțin pentru o parte din planul de sprijin pentru toate evaluare nepozitiv, că un astfel de plan este optim.
Teorema 3. Dacă linia de index a ultimului tabel simplex care conține planul optim, există cel puțin un zero, valoare ce corespunde unei variabile liberă, ZLP are un set infinit de planuri optime.
Teorema 4. În cazul în care linia de index tabelul simplex ZLP conține un scor maxim negativ. și în coloana corespunzătoare nu este variabilă nici un element pozitiv, funcția obiectiv pe platourile de filmare nu este delimitat de mai sus planuri acceptabile.
Teorema 5. Dacă linia de index tabelul simplex ZLP cel puțin oferă o evaluare pozitivă. și în coloana corespunzătoare nu este variabilă nici un element pozitiv, funcția obiectiv pe setul de planuri admisibile nu este mărginită de mai jos.
Teorema 6. În cazul în care planul optim M-problemă cel puțin una dintre variabilele artificiale diferite de zero, atunci problema inițială nu are planuri valide, adică sistemul său este restricții incompatibile.