Obiectivului Coloana Coeficienții funcției Sa înregistrat cu aceiași indici ca vectorii de bază.
Coloana F0 componente pozitive ale programului de sprijin inițial în acesta, ca urmare a calculului obținut componente pozitive planul optim înregistrate. Coloanele P1 ... Pn înregistrat factor de limitare în necunoscut.
In (m + 1) rând -lea: F0 - valoarea curentă a funcției obiectiv; coloane pj scrise numere.
1. problema LP la forma canonică și pentru a găsi programul de sprijin inițial.
2. Se aduce tabelul inițial simplex.
3. Determinați dacă există cel puțin un număr negativ # 916; j în (m + 1) Rândul -lea. Dacă nu, găsit programul de sprijin este optim.
4. Găsiți cel negativ # 916 j și coloana corespunzătoare sunt denumite permisivă. Dacă în coloana de eliberare a numerelor nu a ij pozitive, funcția obiectiv nu este limitat la partea de sus, iar problema LP nu are nici o soluție.
5. Găsiți o coloană AIJ bi relație pozitivă rezolvarea. Minimul acestor relații determină rezoluția liniei.
6. La intersecția rândului și coloanei care permit determinarea elementului de autorizare.
7. Toate elementele de linii de soluționare a împărți un element de activare.
8. Toate elementele care permit coloanei (în afară permițând membru) se înlocuiește cu zerouri.
9. Elementele rămase din tabel sunt calculate de regula unui dreptunghi și este fixat în introducerea unei noi baze variabile. În acest caz, linia de rezoluție definește o variabilă care este exclus de la baza coloanei și prin permiterea - o variabilă care este introdus în baza.
10. Mergeți la pasul 3.
Acest plan de referință * X = (0; 8; 20; 0; 0; 96) este optimizat, deoarece toate # 916; j sunt non-negative.
Valoarea maximă a funcției la o decizie optimă este:
Fmax = 0 + 8 · 9 × 10 + 20 x 16 + 0 + 0 · 0 · 0 · 0 + 96 = 400
Sarcinile individuale. Rezolva metoda LP problema simplex. Opțiuni sarcini preia sarcini individuale, la punctul 1.1.
1.3. Metoda artificială bază.
În general, după conducere problema LP la forma canonică pentru a scrie direct sprijini planul eșuează, deoarece printre vectorii Pj. Nu m singur. În acest caz, problema este rezolvată de către LP o bază artificială.
Declarația problemei. Necesar pentru a găsi maximă a funcției
dar printre vectorii Pj nu m singur.
Definiția. Problema, care constă în determinarea valorilor maxime a funcției
numita extins în legătură cu problema inițială (1.10), (1.11).
M aici sunt unele mari numere pozitive ale căror valori nu sunt stabilite.
problemă extinsă (1.12), (1.13) are un plan de sprijin:
Variabile xn + 1. xn + 2 ... xn + m sunt numite artificial, și unitatea de sistem vectorilor Pn + 1. Pn + 2 + m ... Pn forme artificiale de bază.
Dacă în planul optim problema extins (1,12), (1,13), valorile variabilelor artificiale sunt zero, - există o sursă optimă a problemei (1.10), (1.11).
Prin urmare, procesul de rezolvare a problemei LP (1.10), (1.11) implică următoarele etape:
1. Pentru a face inițial problema extins tipul problemei (1.12), (1.13).
2. Găsiți un program de sprijin al problemei augmentată.
3. Folosind metoda simplex exclud calcule artificiale din vectorul bază. Rezultatul este un program de sprijin al problemei inițiale. În cazul în care variabilele artificiale excluse din baza nu este posibil, atunci problema LP este de nerezolvat.
4. Utilizarea problema inițială a găsit programul de sprijin (1.10), (1.11) sau metoda simplex sunt planul optim, sau setați-l unsolvability
Exemplu. Găsiți minim de
Reprezintă problema în forma canonică: