Pentru rezolvarea problemelor liniare. Construirea problemei M în metoda bazei artificiale

Metoda simplex. Algoritm. Semnul optimității planului de referință.

Din interpretarea geometrică a ZLP este clar că maximul sau minimul funcției se realizează în punctul de colț al poliedrului convex - ODP - sistem de constrângeri. Prin urmare, metoda simplex se bazează pe ideea de a lua în considerare și de a testa optimitatea numai punctele de colț - vârfurile poliedrului, și nu întregul set infinit al punctelor sale.

Orez. Interpretarea geometrică a ideii metodei simplex

în cazul a două (Figura a) și a trei (Figura b) variabile.

Simplex este un poligon convex în spațiu n-dimensional cu n+1 vârfuri care nu se află în același hiperplan (hiperplanul împarte spațiul în 2 semi-spații).

Metoda simplex este o procedură de calcul bazată pe principiul îmbunătățirii secvențiale a soluției. În acest caz, trecem de la un punct de bază la altul. Sens funcţie obiectivă imbunatatindu-se mereu.

Soluție de bază– aceasta este una dintre soluțiile acceptabile găsite în ODR.

Variabile față de care sistemul este rezolvat ecuații liniare, sunt numite de bază. Apoi toate celelalte variabile sunt numite gratuit.

S-a dovedit că, dacă există o soluție optimă, atunci aceasta va fi găsită într-un număr finit de pași, cu excepția cazurilor de buclă.

Algoritmul metodei simplex:

1. Construiește model matematic sarcini.

Convertiți modelul matematic rezultat în formă canonică, în care: părțile din dreapta condițiilor sunt nenegative; condițiile sunt egalități (dacă este necesar, introduceți variabile artificiale).
Construiți un tabel simplex și găsiți planul de referință inițial pentru rezolvarea problemei. Multe variabile care sunt de bază, luată ca inițială solutie de baza. Valorile acestor variabile sunt egale cu termenii liberi. Toate celelalte variabile sunt zero.
Verificarea optimității soluției de bază se realizează folosind estimări speciale ale coeficienților funcției obiectiv (vezi ultima linie tabele). Dacă problema este rezolvată la max, atunci toate estimările trebuie să fie nenegative, dacă la min, atunci toate estimările trebuie să fie nepozitive.
Trecerea la o nouă soluție de bază. Evident, planul optim ar trebui să includă o variabilă care va crește funcția obiectiv în cea mai mare măsură. La rezolvarea problemelor maxime, planul optim include produse a căror producție este cea mai profitabilă. Aceasta este determinată de valoarea maximă pozitivă a estimării coeficienților funcției obiectiv. Coloana tabelului care conține această estimare se numește coloana principală. Dacă cel puțin un element al coloanei este pozitiv, atunci se găsește rândul general (în caz contrar, sarcina are nr solutie optima). Dacă există zerouri în această coloană, atunci trebuie să luați o altă coloană. Pentru a găsi rândul general, toți membrii liberi (resurse) sunt împărțiți în elementele corespunzătoare ale coloanei generale (rata de consum de resurse pe unitate de produs). Cel mai mic este selectat dintre rezultatele obținute, iar rândul corespunzător se numește rând general. Ea corespunde unei resurse care limitează producția la acest pas. Un element de tabel simplex situat la intersecția unui rând general și a unei coloane se numește element general. Toate elementele șirului general, inclusiv membrul liber, sunt împărțite în elementul general. Ca urmare, elementul general devine egal cu 1. În continuare, este necesar ca toate celelalte elemente ale coloanei generale să devină egale cu 0. Coloana generală trebuie să devină una. Toate liniile, cu excepția celei generale, sunt convertite după cum urmează: elemente primite linie nouăînmulțiți cu elementele corespunzătoare ale coloanei generale și scădeți produsul rezultat din elemente linie veche. Valoarea noilor variabile de bază va fi obținută în celulele corespunzătoare ale coloanei de termeni liberi (regula dreptunghiurilor).
Soluția de bază rezultată este verificată pentru optimitatea (pasul nr. 4). Dacă este optim, atunci calculele se opresc, în caz contrar se găsește o nouă soluție de bază (pasul nr. 5).

Semnul optimității planului de referință

Dacă rezolvăm o problemă pentru max, atunci toate estimările trebuie să fie nenegative.

Dacă rezolvăm o problemă pentru min, atunci toate estimările trebuie să fie nepozitive.

Dacă planul de referință nu este optim, trebuie să treceți la un plan de referință mai bun. Pentru a face acest lucru, alegem cea mai proasta estimare. Va corespunde coloanei de rezoluție. După aceasta, trebuie să găsiți linia de activare.

Θ (coloana relațiilor simplex) nu este trasată pentru liniile cu negativ și valori zero. Dintre toate θ, alegem cea mai mică, acest lucru se face întotdeauna, indiferent dacă problema inițială este min sau max.

Linia de rezolvare arată întotdeauna ce element trebuie eliminat din bază, iar coloana de rezolvare arată întotdeauna ce element trebuie introdus în bază.

Vedere tabelară a PPP. Simplex - tabele.

METODA SIMPLEX DE REZOLVAREA ZLP

3.1. Caracteristici generaleși principalele etape ale metodei simplex

Fondatorii metodei simplex sunt matematicianul sovietic L.V. Kantorovich și matematicianul american J. Dantzig.

Folosind metoda simplex, puteți rezolva orice problemă sau puteți descoperi imposibilitatea acesteia. Multe clase speciale ZLP poate fi rezolvat prin alte metode care sunt mai eficiente pentru aceste clase. Cu toate acestea, avantajul metodei simplex este versatilitatea acesteia. Aproape toate computerele au fost dezvoltate programe standard a rezolva ZLP simplex- metoda.

Să descriem idee generală metoda simplex.

Credem că PLP-ul este înscris formă canonică iar funcția obiectiv trebuie redusă la minimum. După cum știm deja, planul optim ar trebui căutat printre planurile de bază ale ZLP. Metoda simplex nu parcurge toate planurile de referință (ceea ce adesea ar fi imposibil din cauza lor cantitate uriașă), și, pornind de la un plan de referință inițial, se trece secvențial la alte planuri de referință cu o scădere a funcției obiectiv. Metoda simplex încetează să funcționeze atunci când fie se găsește planul de referință optim, fie se stabilește imposibilitatea de rezolvare a problemei.

La decizia PPP Metoda simplex poate fi utilizată pentru a distinge următoarele etape:

1) aducerea ZLP la forma canonică;

2) aducerea sistemului de ecuații liniare la forma Jordan cu părțile drepte nenegative, verificând simultan nesolubilitatea ZLP din cauza inconsecvenței sistemului de constrângeri liniare;

3) studiul planului de referinţă pentru optimitate;

4) studiul ZLP pentru indecizia datorată nelimitării de jos asupra ODD-ului funcției obiectiv;

5) trecerea la un nou plan de referință „mai bun”.

Pentru a reduce și organiza înregistrările atunci când se rezolvă ZLP folosind metoda simplex, se folosesc așa-numitele tabele simplex. Pentru a utiliza un tabel simplex, ZLP trebuie convertit în formă tabelară. Se face așa.

Fie ZLP-ul să fie scris în formă canonică (2.3-2.5). Pentru a reduce ZLP la formă tabelară, sistemul (2.4) ar trebui mai întâi redus la forma Jordan cu părțile drepte nenegative. Să presupunem că această formă Jordan are forma (2.6). Să exprimăm din (2.6) variabilele de bază în termeni de cele libere:

Prin substituirea în funcția obiectiv (2.3) în loc de variabilele de bază expresiile acestora prin variabile libere conform formulelor (3.1), excludem astfel variabilele de bază din funcția obiectiv. Funcția obiectiv va lua forma:

ÎN formă tabelară functia obiectiv se scrie astfel:

Unde .

Nota următoarele caracteristici forma tabelară a PPP:

a) sistemul de ecuații liniare este redus la forma Jordan cu laturile drepte nenegative;

b) variabilele de bază sunt excluse din funcţia obiectiv şi se scrie sub forma (3.3).

Să trecem acum la descrierea tabelului simplex. Fie ZLP-ul să fie scris sub formă tabelară:

(3.4)

Apoi tabelul simplex completat arată astfel.

Tabelul 3.1.

Bază	Variabile	Membri gratuiti
			...	x k			...
			...				...
			...				...
. . .	. .	. .	...	. .	. .	. .	...	. .	. . .
			...				...
f			...				....

Plan de bază PPL: ..., se numește planul de referință corespunzător acestui tabel simplex. După cum se poate observa din formula (3.2), valoarea funcției obiectiv pentru acest plan de referință este egală cu γ 0.

Să ne uităm la un exemplu. Reduceți următorul ZLP la formă tabelară și completați tabelul simplex:

În primul rând, ZLP ar trebui adus la forma canonică. Pentru a face acest lucru, funcția f trebuie înlocuit cu - f:

Sistemul de ecuații trebuie scris în forma Jordan cu părțile drepte nenegative. Tehnica generală prin care se realizează acest lucru va fi discutată mai târziu (Secțiunea 3.7). În exemplul nostru, o astfel de formă Jordan există deja cu variabilele de bază și . Să excludem variabilele de bază din funcția obiectiv - f. Pentru a face acest lucru, le exprimăm în termeni de expresii libere și substituim aceste expresii în funcția obiectivă.

Vederea tabelară a ZLP este următoarea:

Să completăm tabelul simplex (pentru a scurta intrările, prima coloană este intitulată „B”, ultima coloană este „Q”).

Tabelul 3.2.

B			Q
		-5
	-7	-2
-f	-4		-20

Planul de referință corespunzător acestui tabel simplex are forma:

Valoarea funcției - f cu acest plan de referință este - 20.

Să existe un tabel simplex completat. Să formulăm condiția de optimitate pentru planul de referință.

Dacă rândul de jos al unui tabel simplex conține toate numerele, cu excepția, poate, a celui din dreapta, nepozitiv, atunci planul de referință corespunzător acestui tabel este optim.

Pentru simplitate, vom justifica validitatea acestei afirmații cu un exemplu. Lăsați tabelul simplex completat să arate astfel:

Tabelul 3.3.

B				Q
		-1
			-1
f	-5	-3	-1

Valoarea funcției obiectiv pentru planul de referință corespunzător tabelului simplex este egală cu 6. Să scriem funcția obiectiv în formă tabelară: , unde . Deoarece pentru orice soluție admisibilă a ZLP variabilele iau numai valori nenegative, atunci de la ultima intrare functia obiectiv se poate observa ca valoarea sa in orice punct al ODD nu este mai mica de 6. In consecinta, valoarea minima a functiei obiectiv pe ODD este 6 si se realizeaza cu un plan de referinta corespunzator tabelului simplex, .

3.4. Condiția pentru indecizia ZLP datorită nelimitării de jos asupra ODD-ului funcției obiectiv.

Dacă tabelul simplex este completat pentru ZLP, atunci ODD-ul sarcinii nu este gol, astfel încât planul de referință corespunzător tabelului simplex aparține ODD-ului. Cu toate acestea, ZLP poate fi de nerezolvat din cauza nelimitării de jos asupra ODD-ului funcției obiectiv.

Condiția de indecidibilitate este formulată după cum urmează.

Dacă un tabel simplex conține cel puțin o coloană, alta decât cea din dreapta, care are un număr pozitiv în rândul de jos și numere nepozitive în toate celelalte rânduri ale coloanei, atunci ZLP este de nerezolvat din cauza nelimității de mai jos. ODD-ul funcției obiectiv.

Pentru a justifica acest lucru, vom folosi din nou un exemplu.

Tabelul 3.4.

B				Q
			-2
	-3		-1
f		-1

Coloana din rândul de jos conține un număr pozitiv, iar rândurile rămase conțin numere nepozitive. Să dovedim indecizia ZLP.

Să scriem forma Jordan corespunzătoare tabelului simplex și să transferăm termenii care conțin , la partea dreaptă. Primim

Fie a un număr pozitiv arbitrar. Evident, ZLP are următoarea soluție fezabilă:. Să calculăm valoarea funcției obiectiv pentru această soluție fezabilă. Din tabelul 3.4 avem:

. Cu soluția fezabilă specificată f = 4 - 2a. Din aceasta vedem că valoarea funcției obiectiv poate deveni atât de mică cât se dorește pentru suficient mare importanta O. Cu alte cuvinte, funcția obiectiv nu este mărginită de jos pe EDO. Prin urmare, ZLP este indecidabil.

3.5. Trecerea la un nou plan de referință.

Să presupunem că nu sunt îndeplinite condițiile de optimitate și indecidibilitate. Apoi metoda simplex trece la un nou plan de referință. Această tranziție se realizează prin eliminarea uneia dintre variabilele de bază din bază și introducerea uneia dintre variabilele libere în bază. În acest caz, trebuie îndeplinite următoarele două condiții:

1) noua bază trebuie să fie în continuare admisibilă, i.e. părțile din dreapta formei Jordan corespunzătoare trebuie să fie în continuare nenegative;

2) cu un nou plan de referință, valoarea funcției obiectiv nu trebuie să depășească valoarea acesteia cu planul de referință anterior.

Se numește coloana unui tabel simplex care conține variabila introdusă în bază coloana generală. Se numește linia care conține variabila derivată din bază linie generală. Se numește elementul de la intersecția rândului general și coloanei generale element general.

Regula pentru alegerea unui element general.

Orice coloană a tabelului simplex, alta decât cea din dreapta, care are un număr pozitiv în rândul de jos, este selectată ca coloană generală. Apoi sunt luate în considerare doar acele rânduri ale tabelului simplex, altele decât cel mai mic, care au numere pozitive la intersecția cu coloana generală. Pentru fiecare dintre aceste rânduri se calculează raportul dintre termenul liber și elementul din coloana generală. Rândul pentru care acest raport este minim este selectat drept general. Elementul de la intersecția rândului general și coloanei generale va fi elementul general.

Să ilustrăm această regulă cu un exemplu.

Tabelul 3.5.

B			Q
	2	-1

	-2
F

Puteți selecta fie coloană, fie coloană ca coloană generală. Să alegem (cel mai adesea se alege coloana cu cel mai mare număr pozitiv în partea de jos). Acum să începem să alegem linia generală. Pentru a face acest lucru, luați în considerare două linii - și . Facem rapoarte 4:2 și 8:3. Raportul 4:2 are o valoare mai mică, așa că selectam prima linie ca pe cea generală. Prin urmare, elementul general este 2 - se află la intersecția coloanei și rândului.

După selectarea elementului general, trebuie să treceți la un nou plan de referință, în care variabila devine de bază, iar variabila x 1 devine liberă. Coeficientul pentru în noua formă Jordan trebuie să fie egal cu 1. Prin urmare, primul rând din tabelul 3.5 este împărțit la 2. Apoi se înmulțește primul rând rezultat cu (-3) și se adună la al doilea rând , exclude din a doua ecuație. În mod similar, folosind procedura Jordan, o excludem din a treia ecuație și din funcția obiectiv (aceasta din urmă necesită o formă tabelară a ZLP).

Ca rezultat, obținem următorul tabel.

Tabelul 3.6

B						Q



f						-2

Vă rugăm să rețineți că în coloana Q primele trei rânduri conțin numere nenegative, adică noua bază este încă valabilă. Acesta nu este un fapt întâmplător: acesta va fi întotdeauna cazul dacă se respectă cu strictețe regula de alegere a unei linii generale. În plus, valoarea funcției obiectiv cu noul plan de referință este egală cu -2, cu cel vechi era egală cu 12. „Îmbunătățirea” planului de referință garantează regula de alegere a coloanei generale. Deși nu dovedim cu strictețe aceste fapte, trebuie avut în vedere că ele apar întotdeauna.

Privind la tabelul H.6, vedem că nici condiția de optimitate a planului de referință și nici condiția de insolubilitate a ZLP nu sunt îndeplinite. Aceasta înseamnă că trebuie să selectăm din nou elementul general și să trecem la un nou tabel simplex. Cititorul poate face asta singur.

3.6. Algoritm tabular simplex.

Să existe un tabel simplex completat. Rezumând cele de mai sus, obținem următorul algoritm rezolvarea ZLP folosind metoda simplex.

1. Dacă în rândul de jos al tabelului simplex toate numerele, cu excepția poate celui din dreapta, sunt nepozitive, atunci planul de referință corespunzător tabelului simplex este optim, iar algoritmul se oprește. În caz contrar, treceți la punctul 2.

2. Dacă tabelul simplex conține o coloană, alta decât cea din dreapta, care are un număr pozitiv în rândul de jos și numere nepozitive în toate celelalte rânduri, atunci ZLP este de nerezolvat din cauza nemărginirii de dedesubt asupra ODD-ului funcţie obiectiv, iar algoritmul se opreşte. În caz contrar, treceți la punctul 3.

3. Selectați orice coloană, alta decât cea din dreapta, care are un număr pozitiv în linia de jos - să o numim generală. Apoi luăm în considerare rândurile tabelului simplex, altele decât cel de jos, care au numere pozitive în coloana generală. Pentru fiecare dintre aceste rânduri, calculăm raportul dintre termenul liber și elementul din coloana generală. Rândul pentru care această relație este minimă este rândul general. Elementul de la intersecția coloanei generale și a rândului general va fi elementul general. Treci la punctul 4.

4. Creăm un nou tabel simplex în care:

1) variabila din linia generală este derivată din bază; o variabilă în coloana generală este introdusă în bază;

2) linia generală se împarte într-un element general;

3) folosind procedura Jordan, toate numerele coloanei generale, cu excepția lui 1, care se află în rândul general, sunt făcute egal cu zero. Treci la punctul 1.

Exemplul I. Rezolvați folosind metoda simplex

Problema este scrisă în formă canonică, trebuie să o aduceți în formă tabelară. Sistemul de ecuații este scris în forma Jordan cu părțile drepte nenegative (variabilele de bază și ). Este necesar să se reducă funcția obiectiv la formă tabelară. Pentru a face acest lucru, exprimăm variabilele de bază în termeni de cele libere

x 3 =10 - 2x 1 - x 2

x 4 = 8 - x 1 - 2x 2

și înlocuiți-l în funcția obiectiv

Pentru a obține o formă tabelară, scriem funcția după cum urmează:

Acum avem o vedere tabelară a ZLP:

Să completăm primul tabel simplex

Tabelul 3.7

B					Q


F

În Tabelul 3.7, nu sunt îndeplinite condițiile de optimitate și indecidibilitate. Să alegem ca coloană generală , care are un număr pozitiv în linia de jos. Apoi, comparând rapoartele 10:3 și 8:1, selectăm prima linie ca cea generală. În tabel elementul general este 2.

Acționând în conformitate cu punctul 4 al algoritmului tabular simplex, să trecem la tabelul 3.8.

Tabelul 3.8

B		Q


F	-5	-22

Condițiile de optimitate și indecidibilitate nu sunt îndeplinite. Selectați elementul general din tabelul 3.8 și treceți la următorul tabel

Tabelul 3.9

B					Q


F					-24

Tabelul 3.9 satisface condiția de optimitate.

Răspuns: plan optim

Valoarea minima funcția obiectiv f min = - 24.

Exemplul 2. Rezolvați folosind metoda simplex:

În primul rând, ZLP-ul trebuie adus la forma canonică

Acum aducem ZLP-ul într-o formă tabelară. Vedem că sistemul de ecuații este scris în forma Jordan cu părțile drepte nenegative (și variabilele de bază z). Cu toate acestea, funcția obiectiv include o variabilă de bază. Avem:

Prin urmare, imaginea tabelară a ZLP este următoarea:

Completați tabelul simplex (Tabelul 3.10).

Tabelul 3.10

B			z	Q
	-1
z		-2
g				-1

După selectarea elementului general, mergeți la tabelul 3.11

Vedere tabelară a PPP. Simplex - tabele.

METODA SIMPLEX DE REZOLVAREA ZLP

3.1. Caracteristici generale și etapele principale ale metodei simplex

Fondatorii metodei simplex sunt matematicianul sovietic L.V. Kantorovich și matematicianul american J. Dantzig.

Folosind metoda simplex, puteți rezolva orice problemă sau puteți descoperi imposibilitatea acesteia. Multe clase speciale de probleme pot fi rezolvate prin alte metode care sunt mai eficiente pentru aceste clase. Cu toate acestea, avantajul metodei simplex este versatilitatea acesteia. Pentru aproape toate computerele, au fost dezvoltate programe standard pentru rezolvarea problemelor folosind metoda simplex.

Să descriem ideea generală a metodei simplex.

Credem că ZLP este scris în formă canonică și funcția obiectiv trebuie redusă la minimum. După cum știm deja, planul optim ar trebui căutat printre planurile de bază ale ZLP. Metoda simplex nu parcurge toate planurile de referință (ceea ce de multe ori ar fi imposibil din cauza numărului lor imens), ci, pornind de la un plan de referință inițial, se trece secvenţial la alte planuri de referinţă cu scăderea funcţiei obiectiv. Metoda simplex încetează să funcționeze atunci când fie se găsește planul de referință optim, fie se stabilește imposibilitatea de rezolvare a problemei.

Când rezolvați o problemă folosind metoda simplex, pot fi distinse următoarele etape:

1) aducerea ZLP la forma canonică;

2) aducerea sistemului de ecuații liniare la forma Jordan cu părțile drepte nenegative, verificând simultan nesolubilitatea ZLP din cauza inconsecvenței sistemului de constrângeri liniare;

3) studiul planului de referinţă pentru optimitate;

4) studiul ZLP pentru indecizia datorată nelimitării de jos asupra ODD-ului funcției obiectiv;

5) trecerea la un nou plan de referință „mai bun”.

În formă tabelară, funcția obiectiv este scrisă după cum urmează:

Unde .

Să remarcăm următoarele caracteristici ale formei tabelare a PPP:

a) sistemul de ecuații liniare este redus la forma Jordan cu laturile drepte nenegative;

b) variabilele de bază sunt excluse din funcţia obiectiv şi se scrie sub forma (3.3).

Să trecem acum la descrierea tabelului simplex. Fie ZLP-ul să fie scris sub formă tabelară:

(3.4)

Apoi tabelul simplex completat arată astfel.

Semnul optimității planului de referință

Dacă într-un tabel simplex care conține un anumit plan de suport, toate elementele rândului f (cu excepția termenului liber) sunt nenegative, atunci acest plan de sprijin este optim.. Lăsați în rândul f al tabelului. 2.b 0j > (i=1, ..., n m). În planul de referință x 0 conținut în acest tabel, valorile tuturor variabilelor libere x m+j sunt egale cu zero și f(x 0) =b 00. Dacă creșteți oricare dintre variabilele libere x m+ j, atunci, așa cum se poate observa din egalitatea (2.5), din cauza nenegativității lui b 0j, valoarea lui f(x) va începe să scadă. În consecință, la x o funcția f(x) atinge cea mai mare valoare, ceea ce înseamnă că x 0 este într-adevăr planul de referință optim.

Abilitatea de a trece de la un plan de referință la altul

După cum s-a menționat mai sus, esența metodei simplex este procesul de demonstrare a următorului criteriu: dacă în rândul f al unui tabel simplex care conține un plan de referință, există cel puțin un element negativ (fără numărarea termenului liber), care corespunde unei coloane cu cel puțin un element pozitiv, atunci puteți, prin transformarea bazei, să treceți la alt plan de referință cu mare valoare funcția țintă.

Să demonstrăm acest semn. Să stabilim regulile de selectare a variabilelor pentru o astfel de transformare a bazei inițiale B o cu un plan de referință x 0 într-o nouă bază B 1 cu un plan de referință x 1 la care; valoarea funcției f crește, adică f(x i)>f(x 0). Apoi, conform regulii de recalculare a elementelor din tabelul simplex, le transformăm într-o bază nouă, care ne va permite să găsim componentele noului plan de referință.

Să presupunem că în tabel. 2.1, de exemplu, b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) care dintre variabile ar trebui eliminată din baza anterioară pentru a face loc variabilei x m+s;

2) ce valoare ar trebui să ia noua variabilă de bază x m+s în noul plan de referință.

Pentru a rezolva întrebările puse, să presupunem că în egalitățile (2.4) toate x m+j, cu excepția x m+s, sunt egale cu zero. Apoi

x i = b io -b este x m+s (i=l, ..., m)

Din aceste egalități este clar că odată cu creșterea x m+s valorile acelor variabile de bază x i pentru care coeficienții b sunt<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. Pe măsură ce x m+s crește, valorile acestor variabile vor începe să scadă și va veni un moment după care vor lua valori negative și condiția (2.3) nu va mai fi îndeplinită. Acest lucru nu poate fi permis. Prin urmare, să aflăm până la ce valoare limită x m+s poate fi mărită fără a încălca condiția de nenegativitate a variabilelor de bază. În acest scop, scriem din sistemul (2.6) acele egalități în care b este >0. Să presupunem că aceasta se referă la egalități cu numere i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Variabilele de bază x d, ..., x k, ..., x p vor rămâne nenegative atâta timp cât x m+s satisface sistemul de inegalități

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 sau x m+s< b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s< b po /b ps

adică la x m+s
Fie cea mai mică dintre fracțiile b io /b corespunde cu i = k, adică.

min ( b io /b este )= b k0 /b ks .

Atunci putem spune că atâta timp cât x m+s nu depășește valoarea b k0 /b ks , adică x m+s 0, atunci variabila x k va deveni egală cu marcajul: x k = b k0 -- b ks b ko /b ks =0, și astfel baza va fi transformată B o = (x 1 ; ...; x k ; . ..; x m ) într-o bază nouă, în care variabila x m+s trece de la grupul liber la cele de bază, iar variabila x k ia locul lui x m+s în grupul liber. În același timp, toate celelalte variabile libere sunt încă egale cu zero, iar variabilele de bază rămase sunt încă pozitive. În consecință, planul de bază x 1 în noua bază B 1 = (x 1 ; ...; x m+s ; ...; x m ) va avea m componente pozitive și m-n zero. În planul x 1, unele variabile de bază pot lua valori zero în două cazuri:

1) când în plan x 0 există variabile de bază egale cu zero;

2) când cea mai mică dintre fracțiile b io /b este va corespunde la două sau mai multe numere i. În cazul nostru, aceasta corespunde doar cu i = k.

Variabila care trebuie inclusă în bază este determinată de elementul negativ al șirului f. Din egalitatea f =b oo - b os x m+s este clar că atunci când b 0s<0 и фиксированном x m+s >0, valoarea lui f(x) depinde de valoarea absolută a coeficientului b 0s: cu cât |b 0s | este mai mare, cu atât valoarea f(x) va primi în noua bază mai mare. Dar din această egalitate este, de asemenea, clar că valoarea funcției obiectiv în noua bază depinde și de valoarea luată de noua variabilă de bază x m+s. Vom alege o variabilă introdusă în bază, concentrându-ne doar pe elementele negative ale rândului f. Prin urmare, atunci când în rândul f sunt mai multe elemente negative, vom introduce în bază variabila x m+j corespunzătoare elementului negativ cu cea mai mare valoare absolută. Coloana de coeficienți pentru o variabilă inclusă în bază se numește rezolvare. Astfel, prin alegerea unei variabile introduse în bază (sau alegând o coloană de rezoluție) pe baza elementului negativ al rândului f, ne asigurăm că funcția f crește.

Este puțin mai dificil să determinați variabila care trebuie exclusă din bază. Pentru a face acest lucru, ei compun raporturile dintre termenii liberi și elementele pozitive ale coloanei de rezoluție (astfel de relații se numesc simplex) și găsesc cel mai mic dintre ei, ceea ce determină rândul (rezolvarea) care conține variabila exclusă. Alegerea unei variabile excluse din bază (sau alegerea unei linii de rezoluție) conform relației simplex minime garantează pozitivitatea componentelor bazei în noul plan de referință.

Deci, am demonstrat că în condițiile specificate în semn este într-adevăr posibil să se treacă de la un plan de referință la altul cu o valoare mare a funcției obiectiv f(x).

Rețineți că știm deja valoarea noii variabile de bază x m+s din noul plan de referință: este egală cu b ko /b ks . În ceea ce privește valorile numerice ale variabilelor de bază rămase în noul plan de referință și valoarea corespunzătoare a lui f(x), acestea pot fi găsite numai după schimbarea sistemului de variabile de bază x 1 ;..., x m+s ; ...,x m va fi exprimat printr-un sistem modificat de variabile libere x m+1,…,x k,…, x n. Pentru a face acest lucru, să setăm; reguli prin care condiţiile unei probleme se transformă dintr-o bază în alta.

Coeficientul b ks = 0 la x m+s din această ecuație se numește element de rezoluție. În egalitatea (2.7), noua variabilă de bază x m+s este exprimată în termeni de variabile libere, printre care se află acum fosta variabilă de bază x k. Astfel, variabilele x m+s și x k au schimbat roluri.

Să exprimăm în mod similar variabilele de bază rămase printr-un nou set de variabile libere. În acest scop, înlocuim valoarea x m+s din egalitățile rămase (notăm f cu x 0, atunci egalitatea va fi inclusă în sistem la i = 0)

Aducerea unui sistem la o nouă bază se numește transformare simplex. Dacă transformarea simplex este considerată o operație algebrică formală, atunci se poate observa că, în urma acestei operații, rolurile sunt redistribuite între două variabile incluse într-un anumit sistem de funcții liniare: o variabilă trece de la dependentă la independentă, iar cealaltă. , dimpotrivă, de la independent la dependent . Această operație este cunoscută în algebră ca etapa de eliminare a lui Jordan.