Metoda simplex pentru rezolvarea problemelor de programare liniară. Un exemplu de rezolvare a unei probleme directe și duale folosind metoda simplex

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 acceptabile solutie de baza găsit și ar trebui să treceți la pasul 5 al algoritmului, corespunzător 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 rezolvare.

Î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, situat la intersecția rândului principal și a coloanei principale, se numește element de conducere sau de rezoluție. Găsirea elementului conducător încheie munca cu fiecare tabel simplex obișnuit.

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 se împarte şi la elementul conducător, dar se iau cu semnul opus. Elementele b" r şi c" l se calculează după acelaşi principiu.

Restul formulelor 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 este găsită soluție optimă sau se ajunge la concluzia că 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ă mai 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ă admisibilă. 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 fiind de bază și compunem 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ârful ODZP din Fig. 1 îi corespunde. 2 Elementul de conducere este conturat și selectat în conformitate cu pasul 5 al algoritmului de rezolvare a problemelor. Masa 4 corespunde soluției optime a problemei, deci: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.

Orez. 2. Soluție grafică sarcini

Pentru a simplifica procesul de rezolvare, datele inițiale ale problemei programare liniară Când se rezolvă folosind metoda simplex, acestea sunt scrise în tabele simplex speciale. Prin urmare, se numește una dintre modificările metodei simplex simplex tabelar metodă. 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ă are următoarea vedere:

	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ă minimul - semnele coeficienților funcție obiectivă F sunt inversate 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 termenilor liberi, atunci trecem la primul pas; dacă nu există, atunci la al doilea.

Pasul 2. Verificați optimitatea.

În etapa anterioară a fost găsită o soluție fezabilă. Să verificăm optimitatea.Dacă printre elementele tabelului simplex aflate în rândul F (neluând în considerare elementul b 0 - valoarea curentă a funcției obiectiv) nu există 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 maximă absolută (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ă - cel 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 folosind . 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 acestuia sunt tocmai vârfurile „dreptunghiului”.

Al nostru tabel simplex este o matrice extinsă a sistemului de constrângeri cu câteva coloane și rânduri suplimentare. Să luăm în considerare un exemplu de tabel simplex pentru următoarea problemă:

Găsiți valori variabile x 1 ... x 5, pentru care funcția:

Q =

x 1

x 2

acceptă maxim valoare, sub rezerva următoarelor restricții:

x 1

x 2

x 3

(1)

x 1

x 2

x 4

(2)

x 2

x 5

(3)

x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

Tabelul simplex arată astfel:

x 1

x 2

x 3

x 4

x 5

Soluţie

Atitudine

x 3

x 4

x 5

-1

-2

Cel mai linia de sus- pur informativ, indică scopul coloanelor. Coloana „BP” este, de asemenea, informațională; fiecare celulă a acestei coloane conține numele unei variabile care se află în ecuația corespunzătoare a sistemului de constrângeri. În exemplul nostru, în prima ecuație, variabila X 3, în a doua X 4, în a treia X 5.

Coloanele X 1...X 5 conțin coeficienți pentru variabilele corespunzătoare din ecuațiile sistemului de constrângeri (fiecare ecuație are o linie separată). Coloana „Soluție” conține inițial termenii liberi ai ecuațiilor corespunzătoare. Ele arată, de asemenea, valorile pentru soluția curentă, afișate de tabelul simplex, la un anumit pas (iterație) de rezolvare a problemei.

Coeficienții funcției obiectiv sunt reflectați în tabelul simplex din rândul „Q”; termenul liber, ca și în cazul ecuațiilor sistemului de constrângeri, este inițial scris în coloana „Soluție”. Este și valoarea funcției obiectiv, dar scrisă cu semnul opus (acesta este convenabil pentru metoda simplex). În exemplul nostru, tabelul simplex prezentat corespunde unei anumite soluții în care variabilele X 3, X 4, X 5 sunt egale cu 64, 70, respectiv 18 (vezi coloana „Soluție”), iar variabilele rămase sunt egale la zero. Valoarea funcției obiectiv „Q” este egală cu două (ceea ce este ușor de verificat prin înlocuirea valorilor variabilelor în expresia funcției obiectiv).

În exemplul nostru, termenul liber este egal cu -2 (minus doi) deoarece în înregistrarea funcţiei obiectiv se scrie împreună cu variabilele pe o parte a semnului egal, iar termenii liberi din ecuaţiile sistemului de constrângeri pe cealaltă. Prin urmare, înainte de a-l scrie în tabel, trebuie mutat la dreapta semnului egal.

Linia „Q” în în acest exemplu alocat galben, asta înseamnă că va fi folosit pentru a lua o decizie cu privire la alegerea unei coloane de rezoluție (numită uneori coloană ghid). Coloana de rezolvare corespunde unei variabile care va fi introdusă în bază (în listă) la următoarea iterație de rezolvare a problemei. Scopul unei astfel de înlocuiri a bazei este de a îmbunătăți valoarea funcției obiectiv. Criteriul de selectare a unei coloane de rezolvare este coeficientul maxim pozitiv din rândul „Q” atunci când se rezolvă o problemă maximă sau coeficientul minim negativ când se rezolvă o problemă minimă. Dacă după următoarea iterație nu există coeficienți pozitivi (în timpul maximizării) sau negativi (în timpul minimizării) în linie, atunci soluția optimă a fost obținută. În exemplul nostru, coloana de rezolvare este selectată prin coeficientul 7 (maxim pozitiv deoarece problema este pentru maxim), corespunde variabilei X 2, aceasta va fi introdusă în bază la următoarea iterație. Numerele din coloana de ghidare sunt colorate în roșu.

Linia de rezolvare (de ghidare) este, de asemenea, colorată în roșu; corespunde unei variabile care va fi eliminată din bază (listă) la următoarea iterație. Pentru a-l determina, se calculează și se completează coloana „Ratio”. Elementele sale reprezintă relațiile dintre elementele coloanei „Soluție” cu elementele corespunzătoare ale coloanei de ghidare (cu excepția rândului „Q”). Linia de rezoluție este selectată în funcție de valoarea minima din toate relațiile. Important este că aceste rapoarte sunt calculate numai pentru elementele pozitive ale coloanei de ghidare. Dacă la o iterație nu există coeficienți pozitivi în coloana de ghidare, atunci funcția obiectiv problema initiala nelimitat, problema nu are soluție.
În exemplul nostru, linia de ghidare este selectată în funcție de raportul minim de 16, corespunde cu X 3 și această linie va fi îndepărtată de la bază la următoarea iterație (locul ei va fi luat de X 2).

Formăm următoarea parte a tabelului simplex. În loc de variabila x6, planul 1 va include variabila x2.

Linia corespunzătoare variabilei x2 din planul 1 se obține prin împărțirea tuturor elementelor dreptei x6 din planul 0 la elementul de rezoluție RE=1. În locul elementului de rezoluție din planul 1 obținem 1. În celulele rămase ale coloanei x2 din planul 1 scriem zerouri.

Astfel, în noul plan 1 se completează rândul x2 și coloana x2. Toate celelalte elemente ale noului plan 1, inclusiv elementele rândului index, sunt determinate de regula dreptunghiului. Pentru a face acest lucru, selectăm patru numere din planul vechi, care sunt situate la vârfurile dreptunghiului și includ întotdeauna elementul de rezolvare.

RE. NE = SE - (A*B)/RE

STE - element al planului vechi, RE - element rezolutor (1), A și B - elemente ale planului vechi, formând dreptunghi cu elementele STE și RE.

Să prezentăm calculul fiecărui element sub forma unui tabel:





(0)-(2 * (-2+2M)):1	(-1-M)-(-2 * (-2+2M)):1	(-2+2M)-(1 * (-2+2M)):1	(-M)-(-1 * (-2+2M)):1	(-M)-(0 * (-2+2M)):1	(0)-(0 * (-2+2M)):1	(0)-(1 * (-2+2M)):1	(0)-(0 * (-2+2M)):1

Obținem un nou tabel simplex

Iterația nr. 1.

1. Verificarea criteriului de optimitate. Planul de referință actual nu este optim deoarece există coeficienți pozitivi în rândul indicelui.
2. Definirea unei noi variabile de bază. Vom alege coloana corespunzătoare variabilei x1 drept primară, deoarece acesta este cel mai mare coeficient.
3. Definirea unei noi variabile libere. Să calculăm valorile lui Di în rânduri ca coeficient de împărțire: bi / ai1 și să alegem cel mai mic dintre ele:

min (-, 1: 3, -) = 1/3

Prin urmare, a doua linie este prima.

Elementul de rezolvare este egal cu (3) și este situat la intersecția coloanei principale și a rândului principal

Formăm următoarea parte a tabelului simplex.

În loc de variabila x7, planul 2 va include variabila x1. Linia corespunzătoare variabilei x1 din planul 2 se obține prin împărțirea tuturor elementelor dreptei x7 din planul 1 la elementul de rezoluție RE=3

În locul elementului de rezoluție din planul 2 obținem 1. În celulele rămase ale coloanei x1 din planul 2 scriem zerouri.

Astfel, în noul plan 2 se completează rândul x1 și coloana x1. Toate celelalte elemente ale noului plan 2, inclusiv elementele rândului index, sunt determinate de regula dreptunghiului.

Să prezentăm calculul fiecărui element sub forma unui tabel





(0)-(1 * (-5+3M)):3	(-5+3M)-(3 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(-2+M)-(1 * (-5+3M)):3	(-M)-(-1 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(2-2M)-(-1 * (-5+3M)):3	(0)-(1 * (-5+3M)):3

Obținem un nou tabel simplex:

3.1.
3.2.
3.3.
3.4.
3.5.
3.6. Exemplul (1) de rezolvare a problemei LP folosind metoda tabelului simplex
3.7. Exemplul (2) de rezolvare a problemei LP folosind metoda tabelului simplex

Ideea metodei tabelului simplex este de a enumera în mod intenționat vârfurile unui simplex. Pentru a începe căutarea, trebuie să selectați un vârf de referință de la care să începeți căutarea. Metoda simplex de rezolvare a unei probleme de programare liniară se bazează pe trecerea de la un plan de referință la altul (prin enumerarea simplexului vârfurilor) în timpul căreia valoarea funcției obiectiv crește (descrește). Tranziția specificată este posibilă dacă se cunoaște un plan de referință inițial. Pentru a întocmi un astfel de plan, este necesar să se efectueze o analiză vectorială, pe baza căreia să se determine vârful de referință de la care va începe căutarea.Sistemul de inegalități este redus la forma canonică:

x 1 + A 1,m+1* x m+1 + ... + A 1s* x s +...+ A 1n * x n = b 1 ;

x 2 + A 2,m +1* x m+1 + ... + A 2s * x s +...+ A 2n* x n = b 2 ;

x m + A m,m+1* x m+1 + ... + A ms* x s +...+ A mn* x n = b m.

Variabilele x 1, x 2,...,x m, incluse cu coeficienți unitari într-o singură ecuație a sistemului și cu zero coeficienți în restul, se numesc de bază. În sistemul canonic, fiecare ecuație corespunde exact unei variabile de bază. Odihnă n-m variabile(x m+1 , ...,x n) se numesc variabile nebazice.

3.1. Aducerea unui model matematic la forma canonică

Să dăm model matematic probleme la formă canonică.Pentru a face acest lucru, să scăpăm de semnele de inegalitate introducând variabile suplimentare și înlocuind semnul de inegalitate cu un semn egal. Se adaugă o variabilă suplimentară pentru fiecare inegalitate exclusiv, iar această variabilă este specificată în funcția obiectiv cu un coeficient de zero. Regula de introducere a variabilelor suplimentare: cu ">=" - variabila este introdusa in inegalitate cu un coeficient de +1; la "<=" - с коэффициентом (-1).

Mai mult, uneori, când nu există o variabilă de bază în ecuație, pentru a face o variabilă suplimentară negativă una de bază, puteți înmulți întreaga ecuație cu (-1).

De asemenea, puteți reorienta funcția obiectiv de la minim la maxim sau invers prin înmulțirea tuturor coeficienților variabilelor din această funcție cu (-1).

3.2. Analiza vectoriala

În analiza vectorială, se construiesc vectori pentru fiecare variabilă: coordonatele componente ale vectorului n-dimensional (n-număr de ecuații ale sistemului) vor fi coeficienții acestei variabile în ecuațiile corespunzătoare.

După cum sa menționat mai sus, un vector în care există un coeficient unitar într-o singură ecuație și zero coeficienți în altele se numește de bază.În sistemul canonic, fiecare ecuație corespunde exact unei variabile de bază. După verificarea tuturor restricțiilor, sistemul este obținut în formă canonică și devine posibilă completarea tabelului simplex inițial.

3.3. Metoda variabilelor artificiale

Se întâmplă adesea să existe mai puțini vectori de bază decât numărul de ecuații, adică. mai multe ecuaţii nu conţin variabile de bază. În acest caz, utilizați metoda variabilelor artificiale pentru a adăuga variabile de bază.

Deoarece variabilele introduse nu sunt legate de esența problemei LP în formularea originală, este necesar să se asigure că variabilele artificiale dispar. Acest lucru se poate face folosind metoda simplex în două etape.

Etapa 1. Se consideră o funcție obiectiv artificială, egală cu suma variabilelor artificiale, care este minimizată folosind metoda simplex. Cu alte cuvinte, variabilele artificiale sunt excluse. Dacă valoarea minimă a problemei auxiliare este zero, atunci toate variabilele artificiale dispar și se obține o soluție de bază admisibilă a problemei inițiale. În continuare, este implementată etapa 2. Dacă valoarea minimă a problemei auxiliare este pozitivă, atunci cel puțin una dintre variabilele artificiale este și ea pozitivă, ceea ce indică inconsecvența problemei inițiale, iar calculele se opresc.

Etapa 2. Soluția de bază fezabilă găsită în prima etapă este îmbunătățită în conformitate cu funcția obiectivă a problemei originale LP bazată pe metoda simplex, i.e. tabelul optim al etapei 1 se transformă în tabelul inițial al etapei 2 și funcția obiectiv se modifică.

3.4. Construcția unui tabel simplex

Alege soluție de bază fezabilă inițială. Soluție de bază este o soluție obținută pentru valorile zero ale variabilelor nebazice, adică x i =0, i=m+1,...,n. Soluția de bază se numește soluție de bază admisibilă, dacă valorile variabilelor de bază incluse în acesta sunt nenegative, i.e. x j = b j>=0, j=1,2,...,m. În acest caz, funcția obiectiv va lua următoarea formă: S = c b* X b = c 1* b 1+ c 2* b 2 +...+c m* b m . Completem tabelul inițial al metodei simplex:

Tabelul 2.3

c b x b c 1 c 2 ... cm c m+1 ... c n b i
bază x 1 x 2 ... x m x m+1 ... x n
de la 1 x 1 1 0 ... 0 a 1,m+1 ... A n b 1
de la 2 x 2 0 1 ... 0 A 2,m+1 ... a 2 n b 2
... ... ... ... ... ... ... ... ... ...
cm x m 0 0 ... 1 a m,m+1 ... a m n b m
S

3.5. Analiza tabelului simplex

Calculați vectorul estimărilor relative c folosind regula produsului punctual

c j = c j - c b* S j,

Unde

Cu b - vector de estimări ale variabilelor de bază;

S j - a j-a coloană din sistemul canonic corespunzătoare temeiului luat în considerare.

Suplimentăm tabelul original c - linie.

Tabelul 2.4

baza x 1 x 2 ... x m x m+1 ... x n cu 1 x 1 1 0 ... 0 A 1,m+1 ... a 1 n b 1cu 2 x 2 0 1 ... 0 A 2,m+1... a 2 n b 2... ... ... ... ... ... ... ... ... ... c m x m 0 0 ... 1 A m,m+1 ... a m n b m 0 0 ... 0 ... W

c b	x b	c 1	c 2	...	cm	c m+1	...	c n	b i

c- linia

3. Dacă toate estimările c j <=0 (c j >= 0), i=1,...,n, atunci soluția fezabilă curentă este maxima (minima). Soluția a fost găsită.

4. În caz contrar, o variabilă nebază x r cu cea mai mare valoare trebuie introdusă în bază c j în loc de una dintre variabilele de bază (Tabelul 2.5).

Folosind regula raport minim min( b eu/ A ir) definim variabila x p derivata din baza. Dacă coeficientul A atunci este negativ b eu/ A ir =infinit. Ca urmare, intersecția coloanei în care se află variabila de intrare x r nebază și linia în care se află variabila de bază de ieșire x p va determina poziția elementului de conducere al tabelului (Tabelul 2.6).

Tabelul 2.5

		c m+1			b i
	bază	x m+1
de la 1		a 1,m+1	a 1 r	a 1 n
de la 2		a 2,m+1	a 2 r	a 2 n

		a m,m+1	a m r	a m n	b m
c- linie

Tabelul 2.6

c m+1

b i

b i /

aer

x m+1

de la 1

a 1,m+1

a 1 r

a 1 n

b 1/ A 1r

de la 2

a 2,m+1

a 2 r

a 2 n

b 2 / A 2r

cu p

a p,m+1

un pr

apn

b p / A relatii cu publicul

a m,m+1

a m r

a m n

b m

b m / A nr

c- linie

6. Aplicăm transformări elementare pentru a obține o nouă soluție de bază fezabilă și un nou tabel. Ca rezultat, elementul principal ar trebui să fie egal cu 1, iar elementele rămase ale coloanei elementului principal ar trebui să ia valoarea zero.

Calculăm noile scoruri relative folosind regula transformării scalare și trecem la pasul 4.