Algoritmul metodei simplex
1. Transformă disparități în materie de egalitate
2. Găsiți o soluție inițială bază fezabilă
3. Pe baza condițiilor de optimalitate determinate de variabila de intrare. Dacă nu există nici o variabilă de intrare, procesul este terminat.
4. Pe baza condițiilor de admisibilitate Puteți exclude variabila
5. Se calculează elementele noii linii de conducere
noua linie de conducere = linie de curent / element de pivotare
6. Se calculează elementele celorlalte rânduri, inclusiv z-line
noua linie = linie de curent - coeficienții acestuia din coloana de conducere * nou rând de pivot
Mergeți la pasul 3.
Pentru comoditate, procesul iterativ toate valorile sunt scrise în tabelul simplex.
2. Exemplu de soluție problemei PL cu ms Excel pachet
Pentru mai multe probleme de optimizare este convenabil de a folosi un model de programare liniară. Esența problemei constă în elaborarea unui sistem de inegalități care descriu constrângerile corespunzătoare ale problemei și sarcina de a optimiza funcția.
Pentru a găsi soluții la aceste modele, puteți utiliza MS Excel - căuta o soluție.
Luați în considerare modul de a face un model de programare liniară și pentru a găsi o soluție pe exemplu.
2.1. Declarația problemei
Trei masini piesa de prelucrat două tipuri (A și B), fiecare element de procesare trece pe toate mașinile. Este cunoscut detaliile de prelucrare pentru fiecare mașină, aparatul de lucru pe parcursul unui ciclu de producție și profiturile din vânzarea fiecărui tip de elemente audio (tabel de date). Creați un plan de producție pentru a asigura cea mai mare rentabilitate.
2.2. modelul matematic
Vom nota prin x1 și x2 numărul de unități de părți ale tipurilor A și B, care urmează să fie emise. Apoi, prelucrarea formularului A detaliile x1 pe prima mașină este de 1 * x1; Detalii X2 tip B, respectiv, 2 * x2. Timpul total de funcționare a mașinii I pentru fabricarea numărului planificat de părți egale 2 * x1 + x2. este limitată la 16 de ore de funcționare a mașinii într-un singur ciclu de producție. De aceea, trebuie să avem:
În mod similar, pentru mașinile II și III se obține inegalitatea, respectiv:
În plus, în definiția de referință valori x1 și x2. condiții trebuie îndeplinite: x1> = 0; x2> = 0;
Astfel, obținem un sistem numit sistem de constrângeri ale problemei:
Orice soluție (x1, x2) este un sistem de constrângeri se numește planul de producție sau a unui plan de obiective valabile.
Profit din vânzarea de unități ale părților x1 de tip A este de 4. x1 și x2 profit din vânzarea de unități de piese de tip B este 2x2. Profitul total din vânzarea produselor eliberate în conformitate cu planul (x1, x2) este egal cu:
Potrivit problema este necesară pentru a găsi un astfel de plan (x1, x2), în care profitul ar fi fost maxim.
Astfel, modelul matematic al problemei ca o problemă de programare liniară:
