Cele mai multe sarcini de management are unele particularități. Primul este faptul că deciziile sunt luate pe baza informațiilor. Uneori, acest tip de problemă poate fi formulată (de obicei, după unele simplificări), în așa fel încât ele au fost rezolvate cu ajutorul metodei matematice care are numele de programare liniară.
Acest lucru scoate în evidență una dintre modalitățile de rezolvare a problemelor de programare liniară (ZLP), respectiv programarea liniară cu numere reale metoda simplex (în mod specific - o metodă de bază artificială).
Simplex - metoda
Multe probleme de management se reduc la modul în care să aloce resurse limitate la cele mai bune avantaj. În limbajul de modele matematice, acest lucru înseamnă că dorim să maximizeze (maximizarea) ceva (de exemplu, profitul) sau a minimiza (minimiza) ceva (de exemplu, cost). De obicei, aceasta este o funcție de ceva (care este cunoscut sub numele de funcția obiectiv) a unui număr de factori, numite variabile. Acest proces este numit optimizare.
De multe ori, aceste întrebări pot fi formulate (de obicei, după unele simplificări), în așa fel încât ele au fost rezolvate cu ajutorul metodei matematice care are numele de programare liniară.
O problemă comună de programare liniară (OZLP) dată în formă arbitrară, numită o sarcină, care necesită maximizarea (minimizarea) funcția
a ij x j <= a i0 ( i = 1, …, s) (2)
a ij x j = un i0 (i = s + 1, ..., m) (3)
x j> = 0 (j = 1, ..., t)
Există diferite forme de înregistrare ZLP, dar la locul de muncă ne interesează înregistrarea sub formă ZLP canonică, deoarece acesta este utilizat pe scară largă prin metoda simplex este aplicabilă această formă de scriere.
problemă de programare liniară în sarcină formă de înregistrare canonică se numește, care este necesară pentru a maximiza funcția
a ij x j = a i0 (i = 1, ..., m) (5)
x j> = 0 (j = 1, ..., n) (6)
Notă: problema de minimizare f poate fi înlocuită în mod oficial de problema maximizarea funcției (-f).
Pentru a exprima ideea generală a metodei simplex, vom prezenta câteva concepte de bază legate de programarea liniară:
Setul de numere X = (x 1, ..., x n), satisface toate constrângerile problemei este apelată.
Setul de numere X = (x 1, ..., x n), numit planul de referință, în cazul în care acesta corespunde unui punct extrem al soluțiilor poliedru.
Plan X = (x 1, ..., x n), livrarea într-o funcție numită extremum optimă.
Deci, esența simplex - metoda este ordonata de verificare numai programele de sprijin în care obiectivul de valoare funcției crește. Așa că am ajuns treptat la planul optim (în cazul în care problema este rezolvabilă).
Rețineți, de asemenea, că orice problemă rezolvabilă de programare liniară poate fi redus la forma canonică. Reducerea inegalității la egalitate se realizează prin introducerea unor variabile ne-negative suplimentare în funcția obiectiv cu coeficienți zero. Pentru sistemul de fantome inegalităților constrângeri pentru forma canonică, trebuie să evidențiați limitările baza unitatea de sistem.
Restricții de forma „# 63,“ - constrângerile legate de resurse. In dreapta este ceea ce folosim în producția de stânga - ceea ce obținem. Sub aceste constrângeri introduc variabile suplimentare, cu un coeficient de „1“, formând o bază unitară. Funcția obiectivă a acestor variabile vor fi incluse cu „0“ factor. Aceste variabile sunt definite punct de vedere economic. De obicei, ele reprezintă sub-cheltuieli de resurse (restul).
„=“ Tipul de restricții. De multe ori, în ciuda faptului că restricțiile au forma de capitaluri proprii, o bază de unitate nu iasă în evidență sau greu să iasă în evidență. În acest caz, variabilele artificiale sunt introduse pentru unitatea de bază de creare. Constrângerile de sistem intră într-o „1“ coeficient și funcția obiectiv cu «M» coeficient, care tinde la infinit (pentru Fmin - «+ M», atunci când Fmax - «-M»). (Metoda bază artificială).
Restricții de forma „# 63,“ - restricții planificate. variabile suplimentare (X), care transportă un anumit sens economic - depășirilor de resurse sau supra-îndeplinirea planului, supraproducție, a adăugat cu un factor „-1“, funcția obiectiv - cu un factor de „0“. Și variabile artificiale ca și în cazul precedent.
ZLP decizie cel mai rațional poate fi făcută sub formă de tabel. Acestea sunt cunoscute sub numele simplex. In diverse literatura tabele simplex construiesc ușor diferite unele de altele. Cea mai acceptabilă, în opinia mea sunt tabelele descrise în tabelul. 1.
Metoda de baze artificiale
Așa cum am menționat mai sus, de multe ori o problemă cu baza de unitate de alocare. Într-un astfel de caz, este preferată o metodă de bază artificială. Împreună cu sarcina inițială, sarcina este considerata extinsa compilat pe baza originalului, prin introducerea unor variabile nenegative artificiale și funcția obiectiv scăzând suma variabilelor artificiale înmulțit cu un număr arbitrar de mare pozitiv M. Rezultatul este o așa-numită M-sarcină.
F = cj xj - x n + i (7)
a ij + x n + i = o i0 (i = 1, ..., m) (8)
x j> = 0 (j = 1, ..., n + m) (9)
Sistemul (8) variabilele x n + i (i = 1, ..., m) formează o bază numită artificial. Când x 1 = ... = x n = 0 (8) primește inițial planul de referință M sarcini: (0, ..., 0, 10, ..., un m0).
Obținerea unui plan optim a problemei inițiale cu implicarea M-problema se bazează pe următoarele afirmații:
1. În cazul în care planul sarcinii M optim toate variabilele artificiale egale cu zero (x1, ..., x n; 0, ..., 0), planul (x 1, ..., xn) este optimă pentru problema originală.
2. Dacă în planul optim M-sarcină, cel puțin una dintre variabilele artificiale este pozitiv pentru orice M mare, problema inițială nu a fost un singur plan.
3. În cazul în care M-problema este de nerezolvat, atunci problema inițială este de nerezolvat.
La metoda de decizie ZLP a bazelor artificiale variabile artificiale trebuie administrate numai în acele ecuații care nu sunt permise pe „naturale“ variabile de bază.
După cum reiese din (7) În acest moment funcția obiectiv conține doi termeni
tabele, prin urmare simplex pentru a atribui două linii f (Tabelul 1.3.) și optimalitatea este verificat mai întâi de-al doilea rând care corespunde sumei
Numai după ce toate elementele acestei linii va fi egală cu zero, optimalitate este verificat pentru un semn al primului rând care corespunde sumei
Cu excepția bazei de variabile artificiale corespunzătoare acestora este coloane coborât (nu cont) ca variabile artificiale înapoi la baza nu sunt introduse.