4 Metoda bază artificială 72
4.1 două etape simplex Metoda 72
4.2 Exemplu de rezolvare a problemei de către o bază artificială 76
4.3 Întrebări și exerciții de 82
Așa cum sa discutat în secțiunea 3, pentru a aplica algoritmul metodei simplex, aveți nevoie pentru a începe rezolvarea problemelor de programare liniară cu unele programe de sprijin. Că planul ar putea fi construit, sarcina ar trebui să fie scris în formă canonică cu termeni constant non-negativ și au un set complet de variabile de bază.
Orice problemă de programare liniară poate fi redus la forma canonică. În cazul în care liberă între membrii săi sunt negative, apoi, înmulțirea ambele părți ale restricțiilor corespunzătoare pe -1, ușor de realizat non-negativitatea a tuturor membrilor liberi. Cu toate acestea, nu orice problemă conține o bază gata. Dacă nu, utilizați metodele de bază artificiale. Utilizarea unor astfel de tehnici furnizează metoda simplex versatilitate, adică capacitatea de a rezolva cu ajutorul oricărei probleme de programare liniară.
Luați în considerare una dintre modificările metodei de baze artificiale - metoda simplex cu două faze.
4.1 Metoda simplex de două etape
Să sarcina de programare liniară în formă canonică, cu un punct de vedere constant non-negativ nu conține setul complet de variabile de bază:
În acest caz, pentru a se aplica aceasta metoda simplex, metoda de bază artificială. Introduceți m non-negativ variabile y1. v2. um. una din fiecare ecuație. Aceste variabile nazyvayutiskusstvennymi. și sarcina sostavlyayutrasshirennuyu. având următoarea formă *:
Această unitate de sarcină are m coloane cu variabile artificiale care alcătuiesc baza artificială.
Lema. Problema (19) este întotdeauna solubil.
Dovada. Este clar că gama de planuri admisibile (CCT) ale acestei probleme nu poate fi gol: există cel puțin un plan de valabil - planul de bază, care corespunde bazei originale. De fapt, planul este X = (x1, x2. ..., xn. Y1. Y2. ..., ym) = (0, 0, ..., 0, b1, b2. ..., bm) ODP problemă (19).
Funcția obiectiv nu poate fi limitat, deoarece nu poate fi mai mică decât zero (este suma variabilelor non-negativ).
Teorema despre proprietățile obiectivelor optime ale planului de expansiune:
Ie dacă problema optimă extinsă este pozitiv (adică echivalent cu a spune că cel puțin o variabilă fictivă în ceea ce privește U * este pozitiv), atunci problema originală IER este goală.
Cu alte cuvinte, în cazul în care U * toate variabilele artificiale sunt egale cu 0, atunci un plan de X (0). alcătuit din componente xj * U * plan. Este valabil pentru problema inițială.
Dovada primei părți Teorema realizată de contradicție. Să presupunem că există yi> 0, iar problema EIR (18) nu este goală, adică, acolo X` = planul (x1 `. xn`) ODP problemă (18). Luați în considerare U` = planul (x1 `. Xn`,
Acest din urmă sistem este adevărat, deoarece problema X`ODP (18).
Pe plan U` funcția obiectiv a problemei (19) Z` = 0 (suma zero variabile artificiale). Cu toate acestea, ținând cont de ipoteza, sarcina optimă (19) este pozitiv, adică, Mai multe Z`. Având în vedere că problema (19), cel puțin, U * planul poate să nu fie optimă, în cazul în care există un plan valabil, în cadrul căreia valoarea funcției obiectiv este mai mică. Avem o contradicție, prima parte a teoremei.
A doua parte a teoremei substituind direct U dovedit * U * = (x1 *. * Xn. 0. 0) în restricția sarcinii (19). Din moment ce acest plan este valabil pentru problema (19), ecuațiile de sistem se transformă în adevărate egalitate. Ele coincid exact cu ecuațiile de (18), prin substituirea în ea planul de X (0) = (și de constrângerile de nenegativitate sunt de asemenea îndeplinite) (x1 * xn *.):
Din limitările de performanță ale (19) urmează constrângerile de execuție ale problemei (18): prin urmare, planul X (0) - valabil pentru problema (18).
Sensul teoremei de mai sus este că, pentru a rezolva problema de programare liniară va fi posibilă numai dacă vom reuși în a scăpa de toate variabilele artificiale *. De fapt, aceste variabile artificiale în construcția sarcinilor extinse au fost „stoarse“ între partea stângă și dreaptă a ecuațiilor. De fapt, partea din stânga a restricțiilor au fost de drepturi egale, nici o diferenta nu ar trebui să fie printre ei. Iar problema va fi rezolvată numai în cazul în care „diferența“ - o variabilă artificială - va fi în măsură să anuleze toate restricțiile.
Când variabilele artificiale sunt reduse la zero (derivat de la bază), acestea pot fi excluse din calcul. Sarcina rezultată va fi diferită de funcția țintă inițială (sistemul transformat de restricții extinse sarcini vor fi, în esență un sistem de constrângeri transformate ale problemei inițiale). Prin urmare, va merge doar la o funcție obiectiv diferit - problemă (18).
în două etape metoda algoritmul simplex este construit pe baza acestei teoreme. care este după cum urmează:
Prima etapă. Construit o sarcină extinsă, care este de obicei rezolvată prin metoda simplex.
Două etape. În cazul în care problema a extins concluzia pozitivă optimă pe insolubilitatea problemei inițiale, ca OTM = . În cazul în care este zero, procesul trece la decizia prin metoda simplex problema inițială, deoarece programul de sprijin, valorile corespunzătoare ale variabilelor * XJ.
Cu referire la tabelul simplex acest mijloc de tranziție care modifică coloană Sat în funcție de valoarea coeficienților funcției obiective ale problemei inițiale și recalculat linia criterial: se calculează o sumă de produse de elemente de coloane laterale dreapta a mesei la elementele coloană simplex Sat. și în toate coloanele cu excepția B, se scade din aceste sume Cj.
este recomandabil să se respecte următoarele recomandări pentru rezolvarea problemelor:
a) Dacă problema inițială are o singură coloană, la una sau mai multe variabile (adică partea bazei), acest fapt poate fi utilizat în construcția problemei extinse. Și anume, baza artificială nu este introdus complet, lipsește doar variabilele de bază. În acest caz, construcția funcției obiectiv minimizează suma numai problema extinse variabile artificiale.
b) selectați rezoluția coloanei, deci este recomandabil să se efectueze o modalitate de primă de bază din variabilele artificiale (dacă este posibil).
c) variabile de conversie corespunzătoare acestor coloane tabel simplex nu este necesară după variabilele de ieșire ale bazei artificiale.