Metoda simplex tabelar

Una dintre metodele de rezolvare a problemelor de optimizare ( asociată de obicei cu găsirea minimului sau maximului) programare liniară numit . Metoda simplex include un întreg grup de algoritmi și metode pentru rezolvarea problemelor de programare liniară. Una dintre aceste metode, care presupune înregistrarea datelor sursă și recalcularea lor într-un tabel special, se numește metoda tabulară simplex.

Să luăm în considerare algoritmul metodei simplex tabulare folosind exemplul soluției sarcina de productie , care se rezumă la găsirea unui plan de producție care să asigure profit maxim.

Date de intrare pentru problema metodei simplex

Compania produce 4 tipuri de produse, prelucrandu-le pe 3 masini.

Standardele de timp (min./buc) pentru prelucrarea produselor pe mașini sunt specificate de matricea A:

Fondul de timp de funcționare a mașinii (min.) este specificat în matricea B:

Profitul din vânzarea fiecărei unități de produs (RUB/buc) este dat de matricea C:

Scopul sarcinii de producție

Întocmește un plan de producție care să maximizeze profitul întreprinderii.

Rezolvarea problemei folosind metoda simplex tabelar

(1) Să notăm cu X1, X2, X3, X4 numărul planificat de produse de fiecare tip. Apoi planul dorit: ( X1, X2, X3, X4)

(2) Să notăm constrângerile planului sub forma unui sistem de ecuații:

(3) Atunci profitul tinta este:

Adică, profitul din îndeplinirea planului de producție ar trebui să fie maxim.

(4) Pentru a rezolva problema rezultată pe extremul condiționat, înlocuim sistemul de inegalități cu sistemul ecuatii lineare prin introducerea de variabile suplimentare nenegative în el ( X5, X6, X7).

(5) Să acceptăm următoarele plan de referință:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Să introducem datele în tabel simplex:

În ultima linie introducem coeficienții funcției obiectiv și valoarea acesteia însăși cu semnul opus;

(7) Selectați în ultima linie cel mai mare (modulo) un număr negativ.

Să calculăm b = N / Elemente_din_coloana_selectată

Dintre valorile calculate ale lui b alegem cel mai puţin.

Intersecția coloanei și rândului selectate ne va oferi elementul de rezolvare. Schimbăm baza într-o variabilă corespunzătoare elementului de rezolvare ( X5 la X1).

Elementul de rezolvare în sine se transformă în 1.
Pentru elementele liniei de rezoluție – a ij (*) = a ij / RE ( adică împărțim fiecare element la valoarea elementului de rezoluție și obținem date noi).
Pentru elementele coloanei de rezoluție, acestea sunt pur și simplu resetate la zero.
Recalculăm elementele rămase ale tabelului folosind regula dreptunghiului.

a ij (*) = a ij – (A * B / RE)

După cum puteți vedea, luăm celula curentă care este recalculată și celula cu elementul de rezolvare. Ele formează colțuri opuse ale dreptunghiului. Apoi, înmulțim valorile din celulele celorlalte 2 colțuri ale acestui dreptunghi. Acest lucru ( A * B) împărțire la elementul de rezolvare ( RE). Și scade din celula curentă care este recalculată ( a ij) Ce s-a întâmplat. Obținem o nouă valoare - a ij (*).

(9) Verificați din nou ultima linie ( c) pe prezența numerelor negative. Dacă nu sunt acolo, a fost găsit planul optim, mergeți la ultima etapă rezolvarea problemei. Dacă există, planul nu este încă optim și tabelul simplex trebuie recalculat din nou.

Din moment ce în ultima linie avem din nou numere negative, începem o nouă iterație de calcule.

(10) Deoarece nu există elemente negative în ultima linie, asta înseamnă că am găsit planul optim de producție! Și anume: vom produce acele produse care s-au mutat în coloana „Base” - X1 și X2. Cunoaștem profitul din producția fiecărei unități de producție ( matricea C). Rămâne să înmulțim volumele de producție găsite ale produselor 1 și 2 cu profit pe 1 bucată, obținem finalul ( maxim! ) profit pentru un plan de producție dat.

RĂSPUNS:

X1 = 32 buc., X2 = 20 buc., X3 = 0 buc., X4 = 0 buc.

P = 48 * 32 + 33 * 20 = 2.196 rub.

Galyautdinov R.R.

Pentru a simplifica procesul de rezolvare, datele inițiale ale unei probleme de programare liniară la rezolvarea acesteia folosind metoda simplex sunt înregistrate în tabele simplex speciale. Prin urmare, se numește una dintre modificările metodei simplex metoda tabulară simplex. Problemă de programare liniară în formă canonică:

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1

Tabelul sursă pentru sarcină arată astfel:

	x 1	x 2	...	xn-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1.1	a 1.2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2.1	a 2.2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

x 1 , x 2 , x n - variabile inițiale, x n+1 , x n+2 , x n+m - variabile suplimentare. Am luat toate variabilele suplimentare ca de bază, iar variabilele originale ca nebază(cele suplimentare sunt scrise în prima coloană a tabelului simplex și cele originale în primul rând). La fiecare iterație, elementele tabelului simplex sunt recalculate în funcție de anumite .

Algoritmul metodei simplex.

Etapa pregătitoare

Reducem problema LP la formă canonică

F=a 0.1 x 1 +a 0.2 x 2 +...a 0.n x n +b 0 → max

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1

a 2.1 x 1 +a 2.2 x 2 +...a 2.n x n +x n+2 =b 2

.......................................

a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m

Dacă în problema inițială este necesar să se găsească un minim, semnele coeficienților funcției obiectiv F se schimbă în opus a 0,n = -a 0,n . Semnele coeficienților condițiilor limită cu semnul „≥” se schimbă și ele în sens opus. Dacă condiția conține semnul „≤”, coeficienții se vor scrie fără modificări.

Pasul 0. Creați un tabel simplex corespunzător problemei inițiale

	x 1	x 2	...	xn-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1.1	a 1.2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2.1	a 2.2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

Pasul 1. Verificare de validare.

Verificăm elementele coloanei b (termeni liberi) pentru pozitivitate dacă nu există printre ele negative, atunci se găsește o soluție admisibilă (o soluție corespunzătoare unuia dintre vârfurile poliedrului de condiții) și trecem la; pasul 2. Dacă există elemente negative în coloana de termeni liberi, atunci selectăm dintre ele maximul în modul - specifică rândul principal k. În această linie găsim și elementul negativ absolut maxim a k,l - specifică coloana principală - l și este element conducător. Variabila corespunzătoare rândului de început este exclusă din bază, variabila corespunzătoare coloanei de început este inclusă în bază. Recalculam tabelul simplex conform .

Dacă printre termenii liberi există elemente negative - dar în linia corespunzătoare - nu există, atunci condițiile problemei sunt inconsecvente și nu are soluții.

Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci trecem la primul pas, dacă nu există, apoi la al doilea;

Pasul 2. Verificați optimitatea.

În etapa anterioară a fost găsită o soluție fezabilă. Să-l verificăm dacă este optim tabel simplex, situate în linia F (neținând cont de elementul b 0 - valoarea curentă a funcției obiectiv) nu sunt negative, atunci s-a găsit soluția optimă.

Dacă șirul F conține elemente negative, atunci soluția necesită îmbunătățire. Dintre elementele negative ale șirului F, îl alegem pe cel cu valoarea absolută maximă (excluzând valoarea funcției b 0)

a 0,l =min(a 0,i )

l - coloana în care se află va fi cea de conducere. Pentru a găsi rândul de început, găsim raportul dintre termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie nenegative.

b k /a k,l =min (b i /a i,l ) pentru a i,l >0, b i >0

k - rândul pentru care această relație este minimă - cea de conducere. Elementul a k,l este elementul conducător (permisiv). Variabila corespunzătoare rândului principal (x k) este exclusă din bază, variabila corespunzătoare coloanei principale (x l) este inclusă în bază.

Recalculăm tabelul simplex cu . Dacă în masa noua după recalculare, rămân elemente negative în linia F, mergeți la pasul 2

Dacă este imposibil să găsiți rândul principal deoarece nu există elemente pozitive în coloana principală, atunci funcția din regiunea soluțiilor fezabile ale problemei nu este limitată - algoritmul se termină.

Dacă toate elementele din rândul F și coloana de termeni liberi sunt pozitive, atunci soluția optimă a fost găsită.

Reguli de transformare a tabelului simplex.

La crearea unui nou tabel simplex, apar următoarele modificări:

În locul variabilei de bază x k scriem x l ; în locul variabilei nebazice x l scriem x k.
elementul conducător se înlocuiește cu valoarea inversă a k,l "= 1/a k,l
toate elementele coloanei principale (cu excepția a k,l) sunt înmulțite cu -1/a k,l
toate elementele liniei de conducere (cu excepția a k,l) sunt înmulțite cu 1/a k,l
elementele rămase ale tabelului simplex sunt transformate după formula a i,j "= a i,j - a i,l x a k,j / a k,l

Schema de transformare pentru elementele unui tabel simplex (cu excepția rândului principal și a coloanei principale) se numește schemă „dreptunghi”.

Element convertit a i,j iar cei trei factori corespunzători acesteia sunt tocmai vârfurile „dreptunghiului”.

. Algoritmul metodei simplex

Exemplul 5.1. Rezolvați următoarea problemă de programare liniară folosind metoda simplex:

Soluţie:

eu repetare:

x3, x4, x5, x6 x1,x2. Să exprimăm variabilele de bază în termeni de cele libere:

Să reducem funcția țintă la următoarea vedere:

Pe baza problemei obținute, vom forma tabelul simplex inițial:

Tabelul 5.3

Tabel simplex original

				Relații evaluative

Conform definiției soluției de bază, variabilele libere sunt egale cu zero, iar valorile variabilelor de bază sunt egale cu valorile corespunzătoare ale numerelor libere, adică:

Etapa 3: verificarea compatibilității sistemului de restricții PAP.

La această iterație (în Tabelul 5.3), semnul de inconsecvență al sistemului de constrângeri (semnul 1) nu este identificat (adică nu există o linie cu un număr liber negativ (cu excepția liniei funcției obiectiv) în care să nu existe să fie cel puțin un element negativ (adică coeficient negativ pentru o variabilă liberă)).

La această iterație (în Tabelul 5.3), semnul de nemărginire al funcției obiectiv (semnul 2) nu a fost identificat (adică nu există nicio coloană cu un element negativ în rândul funcției obiectiv (cu excepția coloanei numerelor libere). ) în care nu ar exista cel puţin un element pozitiv) .

De când s-a găsit solutie de baza nu conține componente negative, atunci este acceptabil.

Etapa 6: verificarea optimității.

Soluția de bază găsită nu este optimă, deoarece conform criteriului de optimitate (semnul 4) nu ar trebui să existe elemente negative în linia funcției obiectiv (numărul liber al acestei linii nu este luat în considerare la considerarea acestui criteriu). Prin urmare, conform algoritmului metodei simplex, trecem la etapa 8.

Întrucât soluția de bază găsită este admisibilă, vom căuta coloana de rezolvare după următoarea schemă: determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.3, există două astfel de coloane: coloana „ x1„și coloana” x2" Din astfel de coloane se selectează cel care conține cel mai mic element din rândul funcției țintă. Ea va fi cea permisivă. Coloana " x2" conține cel mai mic element (–3) în comparație cu coloana " x1

Pentru a determina linia de rezolvare, găsim rapoartele pozitive estimate ale numerelor libere la elementele coloanei de rezoluție se acceptă ca fiind rezolvată linia care corespunde celui mai mic raport de evaluare pozitivă;

Tabelul 5.4

Tabel simplex original

În tabelul 5.4, cea mai mică relație de evaluare pozitivă corespunde liniei „ x5„, prin urmare, va fi permisiv.

Elementul situat la intersecția coloanei de activare și a rândului de activare este acceptat ca activator. În exemplul nostru, acesta este elementul care se află la intersecția liniei „ x5„și coloane” x2».

Elementul de rezolvare arată o bază și o variabilă liberă care trebuie schimbate în tabelul simplex pentru a trece la o nouă soluție de bază „îmbunătățită”. ÎN în acest caz, acestea sunt variabile x5Și x2, în noul tabel simplex (Tabelul 5.5) le schimbăm.

9.1. Transformarea elementului rezolutiv.

Elementul de rezoluție din tabelul 5.4 este convertit după cum urmează:

Introducem rezultatul rezultat într-o celulă similară din Tabelul 5.5.

9.2. Conversie șir de rezoluție.

Împărțim elementele rândului de rezolvare a tabelului 5.4 la elementul de rezolvare al acestui tabel simplex, rezultatele se încadrează în celule similare ale noului tabel simplex (tabelul 5.5). Transformările elementelor șirului de rezoluție sunt date în Tabelul 5.5.

9.3. Conversia coloanei de rezoluție.

Împărțim elementele coloanei de rezoluție din tabelul 5.4 la elementul de rezoluție al acestui tabel simplex, iar rezultatul este luat cu semnul opus. Rezultatele obținute se încadrează în celule similare ale noului tabel simplex (Tabelul 5.5). Transformările elementelor coloanei de rezoluție sunt date în Tabelul 5.5.

9.4. Transformarea elementelor rămase ale tabelului simplex.

Transformarea elementelor rămase ale tabelului simplex (adică elementele care nu sunt situate în rândul de rezolvare și coloana de rezolvare) se efectuează conform regulii „dreptunghi”.

De exemplu, luați în considerare transformarea unui element situat la intersecția liniei " x3„ și coloanele „”, îl vom desemna condiționat „ x3" În tabelul 5.4, desenăm mental un dreptunghi, al cărui vârf se află în celula a cărei valoare o transformăm (adică în celula „ x3"), iar celălalt (vertex diagonal) este într-o celulă cu un element de rezoluție. Celelalte două vârfuri (ale celei de-a doua diagonale) sunt determinate în mod unic. Apoi valoarea transformată a celulei " x3" va fi egală cu valoarea anterioară a acestei celule minus fracția, în numitorul căreia se află elementul de rezoluție (din tabelul 5.4), iar în numărător este produsul altor două vârfuri neutilizate, adică:

« x3»: .

Valorile altor celule sunt convertite în mod similar:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Ca urmare a acestor transformări, a fost obținut un nou tabel simplex (Tabelul 5.5).

II repetare:

Etapa 1: întocmirea unui tabel simplex.

Tabelul 5.5

Tabel simplexII iterații

				Estimată relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.5):

După cum puteți vedea, cu această soluție de bază valoarea funcției obiectiv = 15, care este mai mare decât cu soluția de bază anterioară.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.5 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.5 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.5) conține un element negativ: –2 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.5, există o singură astfel de coloană: „ x1" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.6, minimul este relația corespunzătoare liniei „ x3" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.6

Tabel simplexII iterații

				Estimată relaţie
				3/1=3 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.6) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.7.

III repetare

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.7

Tabel simplexIII iterații

				Estimată relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.7):

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.7 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.7 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este admisibilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.7) conține un element negativ: –3 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru). caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.7, există o singură astfel de coloană: „ x5" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.8, minimul este relația corespunzătoare liniei „ x4" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.8

Tabel simplexIII iterații

				Estimată relaţie

				5/5=1 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.8) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor din tabelul simplex sunt prezentate în Tabelul 5.9.

IV repetare

Etapa 1: construirea unui nou tabel simplex.

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.9

Tabel simplexIV iterații

				Estimată relaţie
			–(–3/5)=3/5

			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Etapa 2: determinarea soluției de bază.

Ca urmare a transformărilor simplex s-a obţinut o nouă soluţie de bază conform Tabelului 5.9, soluţia este următoarea:

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.9 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.9 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este admisibilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită în conformitate cu caracteristica 4 este optimă, deoarece nu există elemente negative în linia funcției obiectiv a tabelului simplex (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică) .

Etapa 7: verificarea alternativei soluției.

Soluția găsită este unică, deoarece nu există elemente zero în linia funcției obiectiv (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se consideră această caracteristică).

Răspuns: valoare optimă funcţia obiectivă a problemei luate în considerare =24, care se realizează la.

Exemplul 5.2. Rezolvați problema de programare liniară de mai sus cu condiția ca funcție obiectivă este minimizat:

Soluţie:

eu repetare:

Etapa 1: formarea tabelului simplex inițial.

Problema originala programarea liniară este dată în formă standard. Să o aducem la forma canonică prin introducerea unei variabile suplimentare nenegative în fiecare dintre constrângerile de inegalitate, i.e.

În sistemul de ecuații rezultat luăm ca variabile permise (de bază). x3, x4, x5, x6, atunci variabilele libere vor fi x1,x2. Să exprimăm variabilele de bază în termeni de cele libere.

Dacă enunțul problemei conține restricții cu semnul ≥, atunci acestea pot fi reduse la forma ∑a ji b j prin înmulțirea ambelor părți ale inegalității cu -1. Să introducem m variabile suplimentare x n+j ≥0(j =1,m) și să transformăm restricțiile în formă de egalități

(2)

Să presupunem că toate inițiale variabilele sarcinii x 1 , x 2 ,..., x n – nebază. Atunci variabilele suplimentare vor fi de bază, iar o anumită soluție a sistemului de constrângeri are forma

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)

Deoarece în acest caz valoarea funcției obiectiv F 0 = 0, putem reprezenta F(x) după cum urmează:

F(x)=∑c i x i +F 0 =0 (4)

Tabelul simplex inițial (tabelul simplex 1) este compilat pe baza ecuațiilor (2) și (4). Dacă variabilele suplimentare x n+j sunt precedate de semnul „+”, ca în (2), atunci toți coeficienții din fața variabilelor x i și termenul liber b j sunt introduși în tabelul simplex fără modificări. La maximizarea funcției de obiectiv, coeficienții sunt introduși în rândul de jos al tabelului simplex cu semne opuse. Termenii liberi din tabelul simplex determină soluția problemei.

Algoritmul de rezolvare a problemei este următorul:

primul pas. Membrii coloanei de membri liberi sunt vizualizați. Dacă toate sunt pozitive, atunci a fost găsită o soluție de bază admisibilă și trebuie să treceți la pasul 5 al algoritmului, care corespunde găsirii soluției optime. Dacă tabelul inițial simplex are termeni liberi negativi, atunci soluția nu este validă și ar trebui să treceți la pasul 2.

al 2-lea pas. Pentru a găsi o soluție admisibilă, se efectuează și este necesar să se decidă care dintre variabilele nebazice să includă în bază și ce variabilă să se elimine din bază.

Tabelul 1.

x n

variabile de bază	Membri gratuiti sub restricții	Variabile non-bazice
variabile de bază	Membri gratuiti sub restricții	x 1	x 2	...	x l	...
x n+1	b 1	un 11	un 12	...	un 1l	...	un 1n
x n+2	b 2	un 21	un 22	...	un 2l	...	un 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	b2	un r1	un r2	...	un rl	...	arn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	un m1	un m2	...	un ml	...	un mn
F(x)max	F 0	-c 1	-c 2	...	-c 1	...	-c n

Pentru a face acest lucru, selectați oricare dintre elementele negative ale coloanei de termeni liberi (fie b 2 conducător sau rezolvător. Dacă nu există elemente negative în rândul cu un termen liber negativ, atunci sistemul de constrângeri este inconsecvent și problema nu are solutie.

În același timp, variabila care este prima care își schimbă semnul atunci când NP x l selectat crește este exclusă din BP. Acesta va fi x n+r, al cărui indice r este determinat din condiție

acestea. variabila care are cel mai mic raport dintre termenul liber și elementul coloanei principale selectate. Această relație se numește relație simplex. Trebuie luate în considerare numai relațiile simplex pozitive.

Se numește linia corespunzătoare variabilei x n+r conduce sau permite. Elementul tabelului simplex a rl, care se află la intersecția rândului principal și coloanei principale, se numește element de conducere sau de rezoluție. Găsirea elementului conducător încheie lucrul cu fiecare tabel simplex succesiv.

al 3-lea pas. Se calculează un nou tabel simplex, ale cărui elemente sunt recalculate din elementele tabelului simplex pasul anteriorși sunt marcate cu un prim, adică b" j , a " ji , c " i , F" 0 . Elementele sunt recalculate folosind următoarele formule:

Mai întâi, noul tabel simplex va completa rândul și coloana care conduceau în tabelul simplex anterior. Expresia (5) înseamnă că elementul a" rl în locul elementului conducător este egal cu reciproca elementului din tabelul simplex anterior. Elementele rândului a ri sunt împărțite la elementul conducător, iar elementele coloana a jl sunt de asemenea împărțite la elementul conducător, dar sunt luate cu semnul opus Elementele b" r și c" l se calculează după același principiu.

Formulele rămase pot fi scrise cu ușurință folosind .

Dreptunghiul este construit conform vechiului tabel simplex în așa fel încât una dintre diagonalele sale să fie formată din elementele recalculate (a ji) și conducătoare (a rl) (Fig. 1). A doua diagonală este determinată în mod unic. Pentru a găsi un nou element a" ji, produsul dintre elementele diagonalei opuse împărțit la elementul principal este scăzut din elementul a ji (acesta este indicat de semnul „-” de lângă celulă). Elementele b" j, (j≠r) și c" i sunt recalculate în același mod. (i≠l).

al 4-lea pas. Analiza noului tabel simplex începe cu primul pas al algoritmului. Acțiunea continuă până când se găsește o soluție de bază fezabilă, de ex. toate elementele coloanei flotante trebuie să fie pozitive.

al 5-lea pas. Considerăm că a fost găsită o soluție de bază admisibilă. Ne uităm la coeficienții dreptei funcției obiectiv F(x) . Un semn al optimității unui tabel simplex este nenegativitatea coeficienților pentru variabilele nebazice din rândul F.

Orez. 1. Regula dreptunghiulară

Dacă printre coeficienții rândului F există și negativi (cu excepția termenului liber), atunci trebuie să treceți la o altă soluție de bază. La maximizarea funcției obiectiv, baza include una dintre variabilele nebazice (de exemplu x l), a cărei coloană corespunde maximului valoare absolută coeficientul negativ c l în rândul de jos al tabelului simplex. Acest lucru vă permite să selectați variabila a cărei creștere duce la o îmbunătățire a funcției de obiectiv. Coloana corespunzătoare variabilei x l se numește coloană principală. În același timp, acea variabilă x n+r este exclusă din bază, al cărei indice r este determinat de relația simplex minimă:

Rândul corespunzător lui x n+r se numește lider, iar elementul tabelului simplex a rl, care se află la intersecția rândului principal și coloanei principale, se numește element conducător.

al 6-lea pas. conform regulilor prezentate la pasul 3. Procedura continuă până când se găsește o soluție optimă sau se ajunge la concluzia că aceasta nu există.

În timpul optimizării soluției, dacă toate elementele din coloana principală sunt nepozitive, atunci rândul principal nu poate fi selectat. În acest caz, funcția din regiunea soluțiilor fezabile ale problemei nu este mărginită de sus și F max ->&∞.

Dacă, la următorul pas al căutării unui extremum, una dintre variabilele de bază devine egal cu zero, atunci soluția de bază corespunzătoare se numește degenerată. În acest caz, apare o așa-numită buclă, caracterizată prin faptul că o anumită frecvență aceeași combinație de BP începe să se repete (se păstrează valoarea funcției F) și este imposibil să treci la o nouă soluție de bază fezabilă. Loopingul este unul dintre principalele dezavantaje ale metodei simplex, dar este relativ rar. În practică, în astfel de cazuri, de obicei refuză să introducă în bază variabila a cărei coloană corespunde valorii absolute maxime a coeficientului negativ din funcția de obiectiv și selectează aleatoriu o nouă soluție de bază.

Exemplul 1. Rezolvați problema

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Folosind metoda simplex și dați o interpretare geometrică a procesului de rezolvare.

O interpretare grafică a soluției problemei este prezentată în Fig. 2. Valoarea maximă a funcției obiectiv se realizează la vârful ODZP cu coordonatele . Să rezolvăm problema folosind tabele simplex. Să înmulțim a doua constrângere cu (-1) și să introducem variabile suplimentare pentru a aduce inegalitățile sub formă de egalități, apoi

Luăm variabilele inițiale x 1 și x 2 ca nebaze și considerăm x 3, x 4 și x 5 suplimentare ca de bază și alcătuim un tabel simplex (tabelul simplex 2). Soluția corespunzătoare tabelului simplex. 2, nu este valabil; elementul conducător este conturat și selectat în conformitate cu pasul 2 al algoritmului anterior. Următorul tabel simplex. 3 definește o soluție de bază admisibilă vârfului ODZP din Fig. 1. 2 Elementul de conducere este conturat și selectat în conformitate cu pasul 5 al algoritmului de rezolvare a problemelor. Masa 4 meciuri soluție optimă sarcini, deci: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Orez. 2. Soluție grafică sarcini