Metoda simplex de programare liniară

Esența metodei simplex

Luați în considerare problema standard de LP:

În cazul în care setul de soluții fezabile de constrângeri de consistență în (4.1), putem arăta că formează o regiune poligonală convexă în spațiul n-dimensional. În cazul în care această zonă este limitată, ne vom referi la ea ca un poligon convex în spațiul n-dimensional. În conformitate cu teorema fundamentală a programării liniare, în cazul în care problema LP are o soluție, funcția obiectiv atinge o valoare optimă în cel puțin un punct colț al soluțiilor poligon. În cazul în care funcția obiectiv atinge o valoare optimă în mai mult de un punct unghiular, acesta ajunge la aceeași decizie în orice punct al segmentului de legătură acestor puncte. Prin urmare, din punct de vedere teoretic problema LP nu este complicat. Suficient pentru a găsi un număr finit de vârfuri ale poligonului și calcula soluții în valorile funcției obiectiv. Dintre toate aceste valori selectați cea mai mare și cea mai mică.

Din punct de vedere practic, situația este mult mai complicată. În primul rând, un simplu brute soluții de forță poligon poate fi imposibilă din cauza numărului foarte mare de vârfuri ale poligonului. Și în al doilea rând, chiar și cu un număr mic de noduri, problema de a găsi vârful coordonatele de complexitate comparabile cu problema originală. Prin urmare, este nevoie de o metode de enumerare focalizate, a căror esență, în mod evident, este de a rezolva, nu toate de sus, și du-te de la orice nod la cea în care „nici mai rău“ valoare funcție obiectivă decât cea anterioară. Una dintre aceste metode este metoda simplex.

Definiții de bază simplex metoda.

Noi credem că toate inegalitățile din (4.1) au forma. în cazul în care există inegalități de forma. acestea conduc cu ușurință la inegalitate. multiplicând partea dreaptă și stângă a (-1). Aici este o problemă LP standard (4.1) la forma canonică. Pentru a face acest lucru, introducem variabile suplimentare non-negative. și pentru a obține problema LP canonice corespunzătoare:

Restricții (4.2) sistem este un sistem de m ecuații liniare, în care gradul de acest sistem se presupune a fi m. Acest sistem are un număr infinit de soluții. Apoi, n-m variabile pot lua valori arbitrare (aceste variabile vor fi numite o variabilă liberă) și celelalte variabile sunt exprimate în termeni m variabilele libere (acestea vor fi numite variabile de bază).

Definiția 4.1. Soluție de ecuații liniare, în care toate variabilele sunt libere la zero, numit o soluție bazică.

Definiția 4.2. Soluție de bază, în care toate componentele sunt non-negativ, este o soluție de bază admisibilă.

Definiția 4.3. Soluție de bază admisă este numită non-degenerate. în cazul în care sunt exact componentă pozitivă, în caz contrar, este numit degenerat.

Construcția primului tabel simplex.

Presupunem că problema LP este înregistrată ca (4.2). În rezolvarea problemei prin metoda simplex este convenabil să se folosească așa-numitele tabele simplex. Noi transformam (4.2) rezultă prin selectarea, ca variabile de bază, variabile suplimentare:

Trebuie remarcat faptul că în (4.3), înainte de „valoarea“ semne în prima și a doua linii ar trebui să fie „minus“ semn.

Pe baza (4.3) constituie primul tabel simplex.

Tab.1. Primul tabel simplex

Găsirea soluție de bază.

Soluția de bază toate variabilele libere egale cu zero, iar variabilele de bază sunt libere de elemente.

Validarea soluțiilor de bază.

1. Un criteriu de bază pentru o decizie să fie valabilă dacă tabelul simplex toate elementele libere, cu excepția, poate, ultima, non-negativ.

În cazul în care soluția de bază este acceptabilă, atunci vom merge la pasul 3, în caz contrar verifica consistența constrângerilor originale.

Criteriul 2. Verificați restricțiile de compatibilitate. Restricțiile sunt incompatibile în cazul în care cel puțin o linie, cu excepția ultima, cu un element negativ liber, toate valorile sunt pozitive.

Dacă incoerență detectată, soluția unei probleme acolo.

În cazul în care neconcordanța nu este dezvăluit și soluția de bază este inacceptabilă, atunci vom merge la pasul 4.

Verificați soluția optimă.

Dacă soluția de bază permisă, apoi soluția este testată pentru criteriul optimalitate folosind 3.

Criteriul 3. Funcția obiectiv va avea o valoare maximă (minimă) în cazul în care acestea din urmă sunt elemente ale coloanelor „libere“ variabile sunt non-negativ (non-pozitiv). În acest caz, valoarea maximă (minimă) a funcției obiectiv este egală cu ultimul element din coloana „elementele disponibile“.

În cazul în care o soluție de bază validă nu este optimă, este necesar să se verifice limitarea funcției obiectiv în conformitate cu criteriul 4.

Criteriul 4. Ținta este mărginită de mai sus (mai jos), adică există o valoare maximă (minimă) a funcției obiectiv, în cazul în care la fiecare iterație în fiecare coloană nu satisface optimalitatea, există cel puțin una pozitivă, nu în ultimul în elementul coloană.

În cazul în care funcția obiectiv este nemarginit identificat mai sus (mai jos), punctul de maxim (minim) nu există.

În cazul în care nu a relevat funcție obiectiv nemărginit de mai sus (mai jos), apoi mergeți la pasul 4.

Fiind elementul permisiv.

1. Găsirea rezolvarea coloanei.

a) soluție bazică inacceptabilă.

Linia care conține elementul liber negativ (cu excepția ultimului rând), elementul selectabilă negativ. Coloana j, care este adoptat elementul selectat ca rezolvarea;

b) soluția de bază este permis, care nu este optimă.

Coloana este luată ca rezolvarea oricărei coloane „variabila liberă“, din care acesta din urmă nu îndeplinește criteriul elementului optimality 3.

2. Găsirea liniei de rezoluție.

Tipul trase fracție. în care există elemente care permit coloana j și este elemente libere, astfel, au același semn. Deoarece linia de rezoluție este selectată pentru care valoarea minimă a găsit fracții.

Notă. În cazul în care elementul de selecție care permite ambiguu, puteți alege oricare dintre ele. Ar putea fi ușor afectată doar de numărul de iterații, dar nu afectează soluția optimă. În practică, se recomandă să selecteze cea mai mică dintre elementele negative și cele mai multe dintre pozitive.

După ce a constatat elementul care permite trece la pasul 5.

Să presupunem că activați elementul este. care este încadrat în tabelul 1. În acest caz, variabila de bază trebuie să fie stabilite în variabila gratuit și - în bază. Componentele noului tabel simplex, care este completat de următoarele reguli.

1. În locul valorii elementului de dizolvare este înregistrată.

2. Liniile de rezoluție elemente sunt împărțite la un element de a permite, și anume

3. Elementele care permit coloanei împărțită în elemente de rezoluție și sunt luate cu semn opus, adică,

4. Elementele rămase. . completat în conformitate cu regula dreptunghiului. Inițial construit dreptunghi, unul dintre nodurile din care este elementul care necesită modificări, iar vârful opus este întotdeauna fixat la elementele. Apoi, celula care necesită modificări scade fracțiune numitorul care este egal cu elementul de separare, iar numărătorul este produsul dintre celelalte două vârfuri ale dreptunghiului, adică.:

Ca rezultat, vom obține un nou tabel de conversie simplex (tabelul 2).

Tabelul 2. tabelul simplex Transformat

După pasul 5, trebuie să mergeți la a doua repetare de la pasul 1, dar utilizând tabelul deja transformat.

Exemplu. Găsiți valoarea maximă a funcției obiectiv F la constrângerile date:

Pregatim condițiile problemei la metoda simplex. Pentru a face acest lucru, mai întâi vom da toate inegalității la forma. Pentru a face acest lucru, se înmulțește partea stângă și dreaptă a treia inegalitatea (-1) și a obține:

Acum vom introduce în fiecare inegalitate variabile suplimentare pentru a trece la problema LP canonică:

Deoarece variabilele de bază este convenabil de a alege variabile suplimentare și notați sistemul în forma (4.3):

O parte din primul tabel simplex.

1 pas. Am găsit o soluție de bază. Soluția de bază toate variabilele libere sunt egale cu 0, iar variabilele de bază sunt egale cu elementele lor libere respective:

Etapa 2. Verificăm admisibilitatea soluției de bază rezultată. Este inacceptabil, deoarece există un element negativ (3).

Etapa 3. Noi verificam compatibilitatea restricțiilor. Restricțiile sunt compatibile, deoarece în conformitate cu un element negativ liber (3), există elemente mai negativ (1).

Având în vedere că neconcordanța nu este identificat, vom trece la pasul 4.

Pasul 4. Este necesar să se găsească un element care să permită.

Să ne găsim de autorizare pe coloană. Avem un punct). Am ales cel mai mic element negativ în rândul cu un element negativ liber (3). Un astfel de element unic, este (-1). Coloana, care conține elementul (o coloană) este luată ca coloana rezolvare.

Pentru a găsi rezoluție linii definesc raportul pozitiv minim de elemente liber la elementele care permit coloanei. Din moment. atunci vom obține o rezoluție a liniei.

Element situat la intersecția coloanei și rândul permisive este elementul permisiv (caseta evidențiată). El subliniază faptul că variabila de bază traduce în variabila gratuit și - în bază.

Transformați tabelul simplex utilizând regulile de conversie:

1. În locul valorii elementului de dizolvare este înregistrată.

2. Liniile de rezoluție elemente sunt împărțite la un element permite (1).

3. Elementele care permit coloanei împărțite în elementul (1), care permite și este luată cu semnul opus.

4. Elementele rămase sunt completate prin dreptunghiul regula. De exemplu, elementul situat la intersecția coloanei și rând. Acesta va fi egal.

Ca urmare, conversia tabelului simplex obținem:

1 pas. Am găsit o soluție de bază.

Etapa 2. Verificăm admisibilitatea soluției de bază rezultată. Este permisă, de exemplu. A. Toate componentele sale nu sunt negative.

Deoarece soluția de bază este fezabilă, atunci vom merge la pasul 3.

Etapa 3. Toate elementele ultimele coloane „libere variabile“ sunt pozitive (2 și 5), și în consecință a găsit o soluție de bază validă asigură maximul funcției obiectiv și valoarea maximă funcției obiectiv egală cu ultimul element din coloana „elemente disponibile“:

Acum vom găsi minimul funcției obiectiv. Din moment ce avem o soluție de bază validă, dar nu livrează un minim al funcției obiectiv, avem nevoie pentru a verifica funcția mărginit în conformitate cu criteriul 4, în care funcția obiectiv este mărginită de mai jos, în cazul în care fiecare coloană, care nu îndeplinesc optimalitatea, există cel puțin una pozitivă Element. Noi ambele coloane „variabile libere“ nu îndeplinesc criteriul de optimalitate în cel mai puțin, t. Pentru a. Ambele ultimul element (2 și 5) sunt pozitive. Aceste coloane au elemente pozitive (1 și 4), prin urmare, nu unbounded identificate mai jos și de a trece la pasul 4.

Pasul 4. Este necesar să se găsească un element care să permită.

Să ne găsim de autorizare pe coloană. Avem b). Selectați orice coloană „variabile libere“, din care acesta din urmă nu îndeplinește criteriul de optimalitate pentru un element minim. Din moment ce avem două coloane nu îndeplinesc criteriul de optimalitate, unele dintre elementele pozitive pe care le alege cea mai mare, și între 2 și 5 au cea mai mare 5 și, prin urmare, coloana va fi permisă.

Pentru a găsi rezoluție linii definesc raportul pozitiv minim de elemente liber la elementele care permit coloanei. am găsit:

. atunci vom obține o rezoluție a liniei.

Etapa 5. Noi transformăm tabelul simplex și a obține:

1 pas. Am găsit o soluție de bază.

Etapa 2. Verificăm admisibilitatea soluției de bază rezultată. Este permisă, de exemplu. A. Toate componentele sale nu sunt negative.

Deoarece soluția de bază este fezabilă, atunci vom merge la pasul 3.

Etapa 3. Soluție de bază admisă minimizează funcția obiectiv, adică. A. Toate cele mai recente elemente ale coloanei „libere variabile“ sunt negative și, în același timp,

Astfel, cea mai mare valoare a funcției obiectiv are la. iar cea mai mică valoare de la. Vedem că soluțiile optime găsite prin metoda simplex, coincide cu soluțiile găsite de metoda geometrică.