Cuprins
- I. Introducere .
- II. Capitolul I. Problema de programare liniară .
- 1.1. Inecuaţii şi sisteme de inecuaţii liniare .
- 1.2. Noţiuni generale privind problema programării liniare (PPL) .
- 1.3. Proprietăţile soluţiilor admisibile în PPL .
- 1.3.1. Teoreme fundamentale .
- 1.3.2. Soluţii de bază admisibile .
- 1.4. Interpretarea geometrică a PPL .
- 1.5. Diverse forme de reprezentare a PPL. Problema transporturilor ca caz particular al problemelor de programare liniară .
- 1.6. Aplicaţii economice a problemelor de programare liniară .
- III. Capitolul II. Metode de soluţionare a PPL .
- 2.1. Metoda Jordan-Gauss .
- 2.2. Metoda grafică de rezolvare a PPL .
- 2.3. Metoda simplex .
- 2.3.1. Trecerea de la o soluţie de bază admisibilă la alta .
- 2.3.2. Algoritmul metodei simplex. Tabelele simplex .
- 2.4. Metoda bazei artificiale cu coeficienţi de penalizare .
- 2.5. Metoda Gomory .
- V. Bibliografie .
Extras din proiect
Introducere
Progamarea liniară, ca disciplină matematică, a apărut la mijlocul secolului XX, primele lucrări fiind publicate de L. Kantorovici (1939) şi F. Hitchcock (1941).
Primele probleme rezolvate se refereau la organizarea optimă a transporturilor maritime, necesităţile de aprovizionare a frontului, planificarea misiunilor aviaţiei de bombardament.
În 1947 G. Dantzig şi J. Von Newmann creează metoda simplex, care stă la baza rezolvării problemelor de programare liniară. Ulterior programarea liniară a cunoscut un mare avînt prin lucrările unor matematicieni şi economişti ca T. Koopmans, L. Ford, D. Fulkerson, W. Cooper, H. Kuhn, găsindu-şi un cîmp foarte larg de aplicaţii în economie.
Astfel, programarea liniară poate fi utilizată la rezolvarea problemelor de genul:
- utilizarea raţională a materiei prime;
- optimizarea planului de producţie al unei întreprinderi;
- amplasarea optimă a producţiei;
- formarea planului optim de transportare a producţiei;
- administrarea rezervelor de producţie;
- şi multe altele, ce ţin de sfera planificării optimale.
În lucrarea de faţă am pus accent pe importanţa programării liniare în economie. Aplicînd asupra problemelor economice modelarea matematică, le-am adus la o formă care permite rezolvarea lor pe cale matematică, ţinînd cont de anumite legităţi economice (de exemplu, preţul şi cantitatea mărfii nu pot avea valori negative).
În capitolul II al lucrării de faţă am studiat aspectele generale privind problemele de programare liniară, am specificat proprietăţile soluţiilor, am descris interpretarea geometrică a acestora. De asemenea, am adus exemple de probleme economice, care necesită să fie optimizate.
În capitolul III am studiat metodele de soluţionare a problemelor deja modelate, atrăgînd o deosebită atenţie metodei simplex, care este una dintre cele mai eficiente şi mai rapide, dar care nu este universală, deoarece se aplică doar la modelele matematice în formă standard. Pentru rezolvarea automatizată a acestor modele am creat şi un program în limbajul C++, care lucrează cu metoda simplex. Cîteva probleme rezolvate vor fi incluse în anexă.
Am mai descris şi alte metode, care sunt preferabile metodei simplex în cazuri particulare. De exemplu, pentru modelele matematice în care figurează doar două necunoscute este binevenită metoda geometrică, iar pentru problemele de programare liniară în numere întregi – metoda Gomory.
Capitolul I. Problema de programare liniară
1.1. Inecuaţii şi sisteme de inecuaţii liniare
Definiţie. Inecuaţie liniară cu două necunoscute se numeşte inecuaţia de tipul
ax + by + c > 0 sau ax + by + c < 0, unde x şi y sunt variabile, iar a, b şi c – careva constante, cu condiţia ca măcar una din constantele a şi b să fie nenegativă.
Soluţie a sistemului de inecuaţii cu două necunoscute se numeşte perechea de valori a variabilelor, care satisface toate condiţiile de inegalitate din sistem.
De exemplu, soluţie a sistemului sistemului de inecuaţii
este fiecare din următoarele perechi de numere: (2; -1), (0; 3,5), (-5; -2,7).
Mulţimea de soluţii ale sistemului de inecuaţii este formată din intersecţia mulţimilor de soluţii a fiecărei inecuaţii din acest sistem. Deoarece avem inecuaţii cu două necunoscute, reiese că în planul de coordonate mulţimea de soluţii ale sistemului se reprezintă printr-o mulţime de puncte. [6]
Revenim la sistemul de inecuaţii liniare. Fiecare inecuaţie de acest fel generează soluţii, mulţimea cărora se reprezintă în planul de coordate ca un semiplan. În dependenţă de faptul dacă inecuaţia este strictă sau nu, semiplanul poate fi nemărginit sau mărginit, respectiv. Soluţia întregului sistem de inecuaţii liniare este, deci, intersecţia semiplanelor generate de inecuaţiile sistemului. În anumite cazuri mulţimea poate reprezenta o figură sau poate fi vidă. [1]
Preview document
Conținut arhivă zip
- Liniara in Solutionarea Problemelor cu Caracter Economic.doc