Simplex - tabele - stadopedia

Pasul 5: utilizând Teorema 1 *, verificați soluția de bază pentru optimalitate:

Þdacă toți coeficienții funcției obiective pentru variabilele non-aleatoare sunt pozitivi, iar pentru cei de bază aceștia sunt egali cu zero. atunci criteriul de optimitate este îndeplinit. Apoi, mergeți la pasul 6 al algoritmului.







Þdacă există cel puțin un coeficient negativ cj în funcția obiectivă înainte de variabila non variabilă xj. Soluția de bază care staționează nu este optimă. În acest caz, folosind Teorema 3 *, investigăm posibilitatea unei tranziții la o nouă soluție de bază. Dacă se obține că o astfel de tranziție este posibilă, atunci este necesar să se schimbe o variabilă de bază în conformitate cu schema 1 *.

-Fie coeficientul cj în funcția obiectivă pentru variabila non-aleatoare xj <0. Тогда для всех положительных коэффициентов aik . стоящих в столбце “xj ” симлекс-таблицы, вычисляют разрешающий коэффициент по формуле:

- Dintre toți coeficienții de rezoluție, se găsește minimul. Fie rp = min (ri). Apoi, în al treilea rând al tabelului, variabila de bază originală este înlocuită cu variabila xj.

- După schimbarea unei variabile de bază, este necesară conversia tabelului simplex în forma următoare prin transformări echivalente:

-Acum, variabila xj va fi variabila de baza. Am obținut o nouă soluție de bază. Trebuie verificat pentru optimitate de Teorema 1 *. Dacă soluția de bază găsită este optimă, treceți la pasul 6 al algoritmului. În caz contrar, este necesară modificarea unei variabile de bază conform schemei 1 *.

6 pas: formularea concluziilor privind rezultatele deciziei Z.L.P.

Se ilustrează utilizarea tabelei simplex pentru soluția Z.L.P. de forma următoare:

Pasul 2 al algoritmului: Reducem sistemul de constrângeri la sistemul de ecuații liniare prin adăugarea de variabile suplimentare x4 și x5:

Pasul 3 al algoritmului: în acest caz, după introducerea unor variabile suplimentare, în fiecare dintre cele două ecuații ale sistemului există deja o variabilă selectată (x4 - în prima ecuație și x5 - în a doua).

4 algoritmi de pas: completați tabelul simplex (Tabelul 1):

Soluția de bază are forma: (x1, x2, x3, x4, x5) = (0,0,0,2,1). Soluția de bază găsită nu este optimă, deoarece nu toți coeficienții funcției obiective sunt ne-negativi. Prin urmare, este necesară modificarea unei variabile de bază. Pentru a face acest lucru, alegem una din variabilele pentru care funcția negativă (de exemplu variabila x1) se află în funcția obiectivă și se calculează coeficienții de rezolvare pentru această variabilă (Tabelul 1).







Deoarece cel mai mic coeficient de rezolvare este în al doilea rând al tabelului, este necesar să se înlocuiască variabila de bază x5 cu variabila x1. Din moment ce x1 este o variabilă de bază, este necesar să obținem prin intermediul transformărilor echivalente a11 = 0, c1 = 0 și a21 = 1.

În acest caz, pentru a obține:

a21 = 1. este necesar să divizăm al doilea rând al tabelului într-un coeficient de rezoluție;

a11 = 0. este necesar să se scadă din elementele primului rând elementele corespunzătoare ale celui de-al doilea rând;

c1 = 0. este necesar să adăugați rândurile a doua și a treia a tabelului.

După aceste transformări, obținem Tabelul 2 (p. 28).

Am obținut o nouă soluție de bază (x1, x2, x3, x4, x5) = (1,0,0,1,0). Soluția de bază alocată nu oferă maximum funcția obiectivă (nu este optimă), deoarece nu toți coeficienții funcției obiective sunt numere non-negative.

Deci înainte de variabila x2 în funcția obiectivă există un coeficient c2 = -2. Prin urmare, este necesară modificarea unei variabile de bază. Dar din moment ce există un singur coeficient pozitiv a12 = 2 în coloana "x2" (Tabelul 2), care se află în primul ciclu al tabelului, nu este nevoie să se calculeze coeficienții de rezolvare. Putem imediat concluziona că variabila de bază x4 trebuie înlocuită cu variabila x2. Din moment ce x2 este o variabilă de bază, este necesar să obținem prin intermediul unor transformări echivalente a12 = 1, c2 = 0 și a22 = 0.

În acest caz, pentru a obține:

c1 = 0. este necesar să adăugați al doilea și al treilea rând din tabel;

a12 = 1. este necesar să împărțiți al doilea rând al tabelului în 2;

a22 = 0. Este necesar să se adauge la elementele liniei a doua elementele corespunzătoare ale primei, obținute după înmulțirea cu 2;

Vom face toate transformările din Tabelul 3.

După cum arată Tabelul 3 compun o nouă soluție de bază, echivalentul a elibera de bază membri variabile nonbasic - la zero (x1, x2, x3, x4, x5) = (3/2, 1/2, 0,0,0). Această soluție de bază este optimă (prin Teorema 1 *), deoarece toți coeficienții funcției obiectiv este de numere non-negative. Prin urmare, o bază este găsită pentru a furniza valoarea maximă a funcției obiectiv: f (x) = x1 + x2 - x3. Astfel, max (f (x)) = 2 + 5x3 + x4 = 2. Setul Z.L.P rezolvat.

Sarcini pentru soluții independente

Sarcina 1. Rezolvați grafic problema de programare liniară. Găsiți valoarea maximă și minimă a funcției F (x) pentru constrângerile date.

Sarcina 2. Întreprinderea produce produse de 2 tipuri P1 și P2 din materii prime de 3 tipuri a1, a2, a3. Rezervele de materii prime sunt egale cu b1, b2, respectiv b3. Consumul de tip i de material brut (ai) pe unitate de produs j (Pj) este egal cu aij.

Găsiți planul de producție care oferă întreprinderii venitul maxim (valorile tuturor parametrilor sunt date în Tabelul 1-9).

Rezolva problema grafic.

Tabelul 1. Tabelul 2. Tabelul 3.

Este necesar să găsim un plan pentru încărcarea mașinilor, în care rezultatul va fi maxim (în termeni monetari).

4. Romakhin M.I. Elemente de algebră liniară și programare liniară. -M .: Școala superioară, 1963.

5. Karasev A.I. Kremer N.Sh. Savelieva T.I. Metode matematice și modele în planificare. -M .: Economia, 1987.

6. Kantorovich LV Gorstko A.B. Soluții optime în economie - M .: Science, 1972.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: