Metoda simplex modificată pentru rezolvarea problemelor de programare a obiectivelor. Metoda simplex modificată

Ideea de bază a metodei simplex modificate este de a utiliza matricea inversă curentă (și datele originale ale problemei) pentru a efectua calculele necesare pentru a determina variabilele de inclus și de exclus. Reprezentarea unei matrici inverse în formă multiplicativă vă permite să calculați o secvență de matrici inverse direct din datele sursă fără a utiliza mai multe operații de inversare pentru fiecare bază. Ca și în metoda simplex obișnuită, în acest caz baza inițială este întotdeauna matricea de identitate I, inversul căreia este această matrice însăși. Prin urmare, dacă
- succesiunea de matrici inverse corespunzătoare iterațiilor 1, 2,…,i și
este succesiunea de matrici corespunzătoare acestora, atunci

Secvența de substituții conduce la următoarea formulă:

(2.23)

Trebuie subliniat că reprezentarea multiplicativă a matricei inverse nu este procedura necesara pentru a implementa schema de calcul a metodei simplex modificate, iar la fiecare iterație puteți utiliza oricare dintre metodele de inversare a bazei curente. Când se utilizează metoda simplex modificată, este important ca matricele inverse să fie calculate într-un mod care să reducă impactul erorilor de rotunjire a mașinii.

Pașii algoritmului metodei simplex modificate sunt în esență aceiași cu cei ai algoritmului metodei simplex convenționale. După găsirea bazei inițiale I, se determină vectorul de coeficienți corespunzător funcție obiectivă, ale căror elemente se formează în funcție de faptul că variabilele de bază inițiale sunt reziduale (redundante) sau artificiale.

2.7.2. Reprezentarea multiplicativă a unei matrici inverse

În reprezentarea multiplicativă a matricei inverse, se utilizează o operație de algebră matriceală pentru a calcula elementele matricei inverse la noua matrice de vectori de bază din matricea inversă cunoscută a bazei anterioare, cu condiția ca cele două baze luate în considerare să difere doar în un vector coloană. Această metodă de reprezentare a matricei inverse este convenabilă de utilizat în schema de calcul a metodei simplex, deoarece bazele corespunzătoare fiecărei două iterații succesive diferă doar într-o singură coloană (ca urmare a înlocuirii vectorului coloană eliminat al bazei curente cu un nou vector coloană). Cu alte cuvinte, matricea de bază curentă și o nouă matrice de bază
, corespunzătoare următoarei iterații, diferă doar într-o singură coloană. Cu reprezentarea multiplicativă a matricei inverse
corespunzator noii baze se calculeaza prin inmultirea in stanga a inversului matricei curente
într-o matrice formată după anumite reguli .

Să definim matricea de identitate in felul urmator:

(2.24)

Unde - vector coloană unitară cu elementul i, egal cu unuși alte elemente, egal cu zero. Să presupunem că matricele sunt cunoscute Și
, și vector matrici este înlocuit cu un nou vector ; după cum se obișnuiește atunci când se descrie metoda simplex, vectorul este definit ca fiind inclus în bază și vector - așa cum este exclus din bază. Pentru a simplifica scrierea relațiilor matematice, folosim următoarea definiție
, în care va reprezenta al k-lea element
. Apoi noua matrice inversă
poate fi calculat folosind următoarea formulă:

(2.25)

cu conditia ca
. Dacă
, matrice
nu exista. Rețineți că matricea obtinut din matrice prin înlocuirea vectorului său r-a coloană coloană .

Problema de optimizareîn matematică este problema găsirii extremului unei funcţii reale într-o anumită regiune. De regulă, sunt luate în considerare domeniile aparținând și definite de un set de egalități și inegalități.

3.1. Descriere

Sarcină programare liniară constă în faptul că este necesar să se maximizeze sau să se minimizeze unele funcționale liniare pe un spațiu multidimensional sub anumite constrângeri liniare.

Fiecare dintre inegalitățile liniare ale variabilelor delimitează un semi-spațiu în spațiul liniar corespunzător. Ca urmare, toate inegalitățile leagă un anumit poliedru (posibil infinit), numit și con poliedric.

Ecuația W(x) = c, unde W(x) este funcționala liniară care trebuie maximizată (sau minimizată), generează hiperplanul L(c). Dependența de c generează o familie de hiperplane paralele. În acest caz, problema extremă are următoarea formulare: se cere să se găsească cel mai mare c astfel încât hiperplanul L(c) să intersecteze poliedrul cel puțin într-un punct. Rețineți că intersecția unui hiperplan optim și a unui poliedru va conține cel puțin un vârf și va fi mai mult de unul dacă intersecția conține o muchie sau o față k-dimensională. Prin urmare, maximul funcționalului poate fi căutat la vârfurile poliedrului. Principiul metodei simplex este că se selectează unul dintre vârfurile poliedrului, după care începe mișcarea de-a lungul marginilor sale de la vârf la vârf în direcția de creștere a valorii funcționalei. Când o tranziție de-a lungul unei muchii de la vârful curent la un alt vârf cu mai multe valoare ridicata funcțional este imposibil, se presupune că a fost găsită valoarea optimă a lui c.

Esența metodei simplex este că dacă numărul de necunoscute mai mult număr ecuații, atunci acest sistem nesigur cu nenumărate soluții. Pentru a rezolva sistemul, toate necunoscutele sunt împărțite în mod arbitrar în de bază și gratuite. Numărul de variabile de bază este determinat de numărul de ecuații liniar independente. Necunoscutele rămase sunt gratuite. Li se dau valori arbitrare și apoi sunt înlocuite în sistem. Orice set de necunoscute libere i se poate da un număr infinit de valori arbitrare, care vor da un număr infinit de soluții. Dacă toate necunoscutele libere sunt setate la zero, atunci soluția va consta din valorile necunoscutelor de bază. Această soluție se numește de bază.

În teoria programării liniare, există o teoremă care afirmă că printre soluțiile de bază ale sistemului se pot găsi optime și, în unele cazuri, mai multe soluții optime, toate care vor oferi un extremum al funcției obiectiv. Astfel, dacă găsiți un plan de bază și apoi îl îmbunătățiți, veți obține soluție optimă. Metoda simplex este construită pe acest principiu.

Secvența de calcule folosind metoda simplex poate fi împărțită în două faze principale:

1. aflarea vârfului inițial al mulțimii soluțiilor fezabile;

2. tranziție secvențială de la vârf la vârf, conducând la optimizarea valorii funcției obiectiv.

În unele cazuri, soluția inițială este evidentă sau definirea acesteia nu necesită calcule complexe, - de exemplu, când toate constrângerile sunt reprezentate de inegalități de forma „mai mică sau egală cu” (atunci vectorul zero este o soluție absolut acceptabilă, deși, cel mai probabil, este departe de a fi optimă). În astfel de probleme, prima fază a metodei simplex poate fi omisă cu totul. Metoda simplex este împărțită în consecință în fază singularăȘi

în două faze.

3.2. Algoritmul metodei simplex

Declarație de problemă consolidată

Luați în considerare următoarea problemă de programare liniară:

Acum să punem această problemă într-o formă echivalentă consolidată. Este necesar să se maximizeze Z, unde:

Aici x sunt variabilele din funcțional liniar original; x s – variabile noi care le completează pe cele vechi în așa fel încât inegalitatea să se transforme în egalitate; c – coeficienții funcționalei liniare inițiale; Z este variabila care trebuie maximizată. Semi-spațiile și la intersecție formează un poliedru reprezentând mulțimea soluțiilor fezabile. Diferența dintre numărul de variabile și ecuații dă numărul de grade de libertate. Mai simplu spus, dacă luăm în considerare vârful unui poliedru, acesta este numărul de muchii de-a lungul cărora ne putem continua mișcarea.

Apoi putem atribui valoarea 0 acestui număr de variabile și apelăm

Agenția Federală pentru Educație

Stat instituție educațională studii profesionale superioare

Universitatea Tehnică de Stat Perm

filiala Lysvensky

Departamentul de Economie

Lucrări de curs

la disciplina „Analiză de sisteme și cercetare operațională”

pe tema: „Metoda simplex în formă de prezentare”

Completat de un elev din grupa VIVT-06-1:

Startseva N. S.

Verificat de profesor:

Mukhametyanov I.T.

Lysva 2010

Introducere. 3

Programare matematică. 5

Metoda grafică. 6

Metoda simplex tabelar. 6

Metodă baza artificiala. 7

Simplex modificat– metoda. 7

Dual simplex - metoda. 7

Vedere generală a problemei de programare liniară. 9

Rezolvarea unei probleme de programare liniară folosind metoda simplex. unsprezece

Proceduri de calcul ale metodei simplex. unsprezece

Teorema 1: 13

Teorema 2: 14

Teorema 3: 15

Teorema 4: 15

Teorema 5: 15

Trecerea la un nou plan de referință. 15

Sarcină dublă. 17

Teorema 1 (prima teoremă a dualității) 18

Teorema 2 (a doua teoremă a dualității) 18

Concluzie. 20

Soluția optimă a problemei de programare liniară se numără printre soluțiile de referință. Ideea metodei simplex este că, după o anumită regulă, soluțiile de referință sunt sortate până când este găsită cea optimă dintre ele. Prin sortarea soluțiilor de referință, în esență, sortăm diverse variabile de bază, adică , la pasul următor, o variabilă este transferată din rândul celor de bază, iar în schimb o anumită variabilă din numărul de libere în numărul celor de bază.

7x 1 +5x 2 →max

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 plan de referință original

x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

La nivel intuitiv, este clar că va fi firesc să crești x 1, deoarece coeficientul pentru acesta este mai mare decât pentru x 2. Lăsând x 2 =0, putem crește până când x 3 , x 4 , x 5 , x 6 rămân nenegative.

x 1 =min(19/2;13/2;∞;18/3)=6

Aceasta înseamnă că atunci când x 1 =6, x 6 =0, adică x 1 intră în numărul celor de bază, iar x 6 intră în numărul celor libere.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2 ; x 6) =42-7/3 x 6 +5 x 2

Cu un plan de referință dat (6;0;7;1;15;0) x 2, transferați de la variabilele libere la variabilele de bază:

x 2 =min(∞;7/3;1/11;15/3)=1

Exprimați x 2 prin x 4

x 2 =1+2/3 x 6 - x 4

Exprimăm variabilele necunoscute și funcția obiectiv în termeni de variabile libere:

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 este pozitiv, prin urmare poate fi crescut

x 6 =min(18;∞;3;6)=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

În funcția obiectiv, toți coeficienții variabilelor sunt negativi, valoarea funcției nu poate fi mărită; în mod similar transformăm variabilele rămase, găsim planul de referință, din care determinăm x 1, x 2.

1. Intersecția mulțimilor închise, un set de restricții netriviale.

2. Mulțimea soluțiilor unui sistem de inegalități și ecuații liniare nestrictive este închisă.

αX=(αx 1 ,x 2 ,…, αx n)

X+Y=(x 1 +y 1, x 2 +y 2,... x n +y n)

Coordonatele liniare X 1 ,X 2 ,…X n se numesc punct P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Mulțimea P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 pentru i= 1,…k n åR i =1, 1≤ i ≤k combinație liniară convexă de puncte x 1 ,x 2 ,…x n . Dacă k=2, atunci această mulțime se numește segment. X 1,X 2 – capete ale segmentului. Un punct de colț al unei mulțimi închise este un punct care nu este o combinație liniară netrivială de puncte din mulțime (punct de colț).

Non-trivialitate înseamnă că cel puțin unul dintre λ este diferit de 0 sau 1.

Orice soluție de referință la o problemă de programare liniară este un punct de colț al regiunii soluțiilor fezabile.

Dacă o problemă de programare liniară are o soluție unică, atunci se află printre punctele de colț ale ODP. Și dacă există mai multe soluții, atunci printre soluții există mai multe unghiulare, astfel încât mulțimea tuturor soluțiilor să fie combinația lor liniară convexă.

Metoda simplex constă în găsirea mai întâi a unei anumite soluții de referință a problemei (planul de referință inițial), apoi, trecerea intenționată de la un plan de referință la altul, căutarea planului optim. Dacă sunt mai multe dintre ele, atunci se găsesc toate cele de colț, iar mulțimea soluțiilor este reprezentată ca combinație liniară a acestora.

Trecerea la un nou plan de referință

F1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 se poate dovedi, unde υ k este minimul considerat mai sus, care se determină prin introducerea k-a variabilă în bază, și Δ k =åс j x j ( 1) -С k, unde n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) este o estimare a k-a variabilă , deci dacă problema maximă este rezolvată, atunci valoarea ΔF 2 trebuie să fie pozitivă, Δk trebuie să fie negativă. La rezolvarea problemelor minime, ΔF 2 este negativ, Δ k este pozitiv. Aceste valori sunt calculate și dacă între ΔF 2 toate valorile nu sunt pozitive, atunci când se rezolvă probleme minime, este invers. Dacă la rezolvarea unui maxim există mai multe pozitive între ΔF 2, atunci introducem în bază vectorul la care această valoare atinge un maxim, iar dacă problema se rezolvă pentru un minim iar între ΔF 2 există mai multe negative. cele, atunci vectorul cu cea mai mică valoare ΔF 2 este inclus în bază, adică cu cea mai mare valoare absolută. Când aceste condiții sunt îndeplinite, se garantează cea mai mare modificare posibilă a valorii funcției.

Soluția problemei va fi unică dacă pentru orice vector x k neincluși în bază, se estimează Δ k ≠0, dacă cel puțin unul dintre aceștia Δ k = 0, atunci soluția nu este unică, pentru a găsi o altă soluție trecem la un alt plan de referință, inclusiv în baza x k, unde Δ k =0. Căutarea prin toate aceste soluții de sprijin le formează într-o combinație liniară, care va fi soluția problemei.

Dacă pentru orice Δ k coeficienții pentru variabila x k ≤ 0 contrazic condiția de optimitate, atunci sistemul de restricții nu este limitat, adică nu există un plan optim.

Problemă dublă

O problemă duală (DP) este o problemă de programare liniară auxiliară formulată folosind anumite reguli direct din condițiile problemei directe. Interesul de a determina soluția optimă a unei probleme directe prin rezolvarea problemei sale duale se datorează faptului că calculele la rezolvarea unei DP se pot dovedi a fi mai puțin complexe decât la rezolvarea unei probleme directe (DP). Complexitatea calculelor când decizia PPP depinde mai mult de numărul de constrângeri decât de numărul de variabile. Pentru a merge la telecomanda, este necesar ca cunostintele tehnice sa fie scrise in standard formă canonică. Când se prezintă PP-ul în formă standard, variabilele x j includ și variabile redundante și reziduale.

Problema dubla are:

1. m variabile corespunzătoare numărului de constrângeri ale problemei directe;

2. n restricţii corespunzătoare numărului de variabile ale problemei directe.

Problema duală se obține prin transformarea structurală simetrică a condițiilor problemei directe după următoarele reguli:

· Fiecare constrângere b i PD corespunde unei variabile y i PD;

· Fiecărei variabile x j PD îi corespunde o constrângere C j PD;

· Coeficienții pentru x j din constrângerile PD devin coeficienții din stânga constrângerii PD corespunzătoare;

· Coeficienții C j pentru x j în funcția țintă a PD devin constanți în partea dreaptă a constrângerii PD;

· Constantele de constrângere b i PD devin coeficienți ai funcției țintă PD.

Luați în considerare următoarele două probleme:

F = С 1 x 1 +С 2 x 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 x 1 +b 2 x 2 +... +b n x n →min

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

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

a 1 n y n + a 2 m y n + ... + a nm y n ≤C n

In acest munca de curs s-au pus bazele metode matematice rezolvarea problemelor de programare liniară. Prin urmare, s-a acordat mai multă atenție următoarelor secțiuni:

1. Fundamentele metodelor matematice și aplicarea acestora;

2. Rezolvarea problemelor folosind metoda simplex.

METODA SIMPLEX MODIFICATĂ Metoda simplex nu este cea mai eficientă
procedură computerizată, întrucât calculează şi
stochează informații care nu sunt necesare pentru curent
iterație și nu poate fi folosit deloc pentru
luarea deciziilor în timpul iterațiilor ulterioare. Pentru
coeficienţii variabilelor non-principale din ecuaţie
(0), coeficienții principalelor variabile introduse
în alte ecuații și în partea dreaptă a ecuațiilor la
Fiecare iterație folosește doar cea relevantă
informație. Prin urmare, este nevoie de o procedură care
pot obține aceste informații în mod eficient, fără
calcule și stocare a tuturor celorlalți coeficienți
(aceasta este metoda simplex modificată).

Acesta calculează și stochează doar informații
necesar pentru acest moment, și date importante
transmite într-o formă mai compactă.
Folosește operații matrice, deci
este necesar să descriem problema folosind matrice.
Litere majuscule, evidențiate cu aldine
reprezintă matrici, majuscule,
cele cu caractere aldine reprezintă
vectori.
Cursivele sunt mărimi scalare, evidențiate zero
(0) indică vectorul zero (elementele sale sunt egale
zero, atât rânduri, cât și coloane), zero (0)
reprezintă numărul normal 0. Folosind
matrice forma standard a modelului liniar
programarea ia forma:

Maximizați Z = c x,
conform
A x ≤ b și x ≥ 0,
unde c este un vector rând
x, b și 0 vectori coloană

A - matrice
Pentru forma augmentată, vector coloană
variabile fictive:
Restrictii:
I = (m × m matrice de identitate)
0 = (n + m elemente ale vectorului zero)

Găsirea unei soluții de bază fezabile
Abordarea generală a metodei simplex este de a obține
secvență de îmbunătățire a soluțiilor OA până la
până când se găsește cea optimă
soluţie. Una dintre caracteristicile cheie
metoda simplex modificată - cum
găsește o nouă soluție OD după ce o definește
principal (de bază) și non-bază (non-bază)
variabile. Având în vedere aceste variabile, rezultatul
soluție principală – soluție a m ecuații
În care n variabile nebazice din n + m
elemente
sunt setate egale cu zero.

Eliminarea acestor n variabile prin setarea lor la zero,
obţinem un sistem de ecuaţii m cu m variabile
(variabile principale (de bază):
unde este vectorul variabilelor de bază:
obţinut prin excluderea non-bazic (non-bazic)
variabile:

Și matricea de bază
Rezultatul obţinut prin excluderea coloanelor corespunzătoare
coeficienţii variabilelor nebazice din .
(În plus, elementele xB și coloanele B sunt în diferite
Bine). Metoda simplex introduce doar de bază
variabile astfel încât B este nedegenerat, deci
matrice inversă B-1 va exista întotdeauna.
Pentru a rezolva B x B = b, ambele părți sunt înmulțite cu B-1:
B-1 B x B = B-1 b.

cB este un vector ale cărui elemente sunt coeficienți
funcții obiective (inclusiv zerouri pentru manechin
variabile) pentru elementele xB corespunzătoare.
Funcția obiectiv pentru această soluție de bază este:

Exemplu:
- Iterația 0
asa de
asa de

10.

- Iterația 1
asa de
asa de

11.

- Iterația 2
asa de
asa de

12. Forma matriceală pentru setul curent de ecuații

Forma matriceală pentru un set de ecuații,
care apar în tabelul simplex pentru orice iterație
metoda originală simplex. Pentru sistemul sursă
ecuații, forma matricei este:
Operații algebrice efectuate folosind metoda simplex (înmulțiți ecuația cu o constantă și adăugați
produsul unei ecuații cu alta) sunt exprimate în
forma matriceală, după înmulțirea ambelor părți
sistemul original de ecuații în corespunzătoare
matrici

13.

14.

Această matrice va avea aceleași elemente ca și matricea de identitate
matrice, cu excepția faptului că fiecare produs
pentru o anumită operație algebrică va fi nevoie
spațiul necesar pentru efectuarea acestei operații,
folosind înmulțirea matriceală. Chiar și după episod
operații algebrice pe mai multe iterații,
mai putem concluziona că această matrice
ar trebui să fie pentru întreaga serie, folosind ceea ce știm despre noi
partea dreapta sistem nou ecuații. După orice
iterații, xB = B-1b și Z = cB B-1b, deci părțile drepte
noul sistem de ecuaţii a luat forma

15.

Din moment ce realizăm aceeași serie
operații algebrice cu ambele părți
set original, pentru a multiplica dreptul și
în partea stângă, folosim aceeași matrice.
Prin urmare,
Forma matriceală dorită a sistemului de ecuații
după orice iterație:

16.

Exemplu: formă matriceală obținută după iterația 2
pentru problema fabricii de sticlă folosind B-1 și cB:

17.

Folosind mărimile xB = B-1 b și Z = cB B-1 b:

18.

Doar B-1 trebuie primit pentru calcul
toate numerele tabelului simplex din original
parametrii sarcinii (A, b, cB). Oricare dintre aceste numere
poate fi obtinut individual ca
De regulă, se efectuează numai înmulțirea vectorială
(un rând pe coloană) în loc de complet
înmulțirea matriceală. Numerele necesare pentru
efectuarea de iterații ale metodei simplex poate fi
primiți după cum este necesar fără a cheltui
calcule inutile pentru a obține toate numerele.

19. Scurtă prezentare a metodei simplex modificate

1. Inițializare: Ca și în metoda originală simplex.
2. Iterație: Pasul 1 Determinați elementul de bază (principal) introdus
variabile: La fel ca în metoda originală simplex.
Pasul 2 Determinați variabilele de bază de ieșire: Ca în original
metoda simplex, cu excepția numărării numai a celor necesare pt
a acestor numere [coeficienții variabilelor de bază introduse în
fiecare ecuație cu excepția ecuației. (0), apoi, pentru fiecare strict
coeficient pozitiv partea dreaptă această ecuație].
Pasul 3 Determinați o nouă soluție OD: obțineți B-1 și setați xB=B-1b.
3. Analiza optimității: Ca și în metoda originală simplex, pt
cu excepția numărării numai a numerelor necesare pentru această analiză,
adică coeficienții variabilelor non-bazice (non-bazice) în
Ecuația (0).
La pasul 3 al iterației, B-1 poate fi obținut de fiecare dată când se utilizează
standard program de calculator pentru inversare (inversare)
matrici. Deoarece B (apoi B-1) se schimbă puțin de la o iterație la
alta, este mai eficient sa se obtina un nou B-1 (notat B-1 nou) de la
B-1 pe iterația anterioară(B-1 vechi). (Pentru soluția originală OA).

Există multe metode de rezolvare a problemelor de programare liniară. Să luăm în considerare una dintre ele, metoda simplex îmbunătățită (modificată).

Mai întâi, să vă spunem care este metoda simplex. Cuvântul SIMPLEX în sensul său obișnuit înseamnă simplu, necompus, spre deosebire de COMPLEX.

Această metodă a primit mai multe forme (modificări) diferite și a fost dezvoltată în 1947 de G. Danzig.

Esența metodei simplex este că, dacă numărul de necunoscute este mai mare decât numărul de ecuații, atunci sistemul dat este incert cu un număr infinit de soluții. Pentru a rezolva sistemul, toate necunoscutele sunt împărțite în mod arbitrar în de bază și gratuite. Numărul de variabile de bază este determinat de numărul de ecuații liniar independente. Necunoscutele rămase sunt gratuite. Li se dau valori arbitrare și sunt substituite în sistem. Orice set de necunoscute libere i se poate da un număr infinit de valori arbitrare, care vor da un număr infinit de soluții. Dacă toate necunoscutele libere sunt setate la zero, atunci soluția va consta din valorile necunoscutelor de bază. Această soluție se numește de bază.

În teoria programării liniare, există o teoremă care afirmă că printre soluțiile de bază ale sistemului se pot găsi optime și, în unele cazuri, mai multe soluții optime, dar toate vor oferi un extremum al funcției obiectiv. Astfel, dacă găsiți un plan de bază și apoi îl îmbunătățiți, veți obține o soluție optimă. Metoda simplex este construită pe acest principiu.

Una dintre modificările metodei simplex este metoda simplex îmbunătățită. În literatură, această metodă se regăsește și sub denumirea de metoda matricei inverse sau metoda simplex modificată.

Când se rezolvă probleme de programare liniară în care n (numărul de variabile) este semnificativ mai mare decât m (numărul de constrângeri), metoda simplex îmbunătățită necesită mult mai puține operații de calcul și memorie de calculator în comparație cu altele.

Metoda simplex îmbunătățită implementează aceeași idee de bază ca metoda simplex convențională, dar aici la fiecare iterație nu se recalculează întreaga matrice A -1, inversul matricei de constrângeri A, ci doar acea parte care se referă la baza curentă A X.

Să luăm în considerare pas cu pas pașii rezolvării unei probleme de programare liniară folosind metoda simplex îmbunătățită:

1. La începutul primului ciclu, cunoaștem matricea inversă (matricea identității), solutie de baza x b = b.
2. Pentru fiecare variabilă nebază, formăm diferența caracteristică j folosind ecuația:

j = c j -- = c j -- P j , (2)

unde sunt variabilele duale, care pot fi găsite după cum urmează:

unde c x este vectorul de coeficienți ai funcției obiectiv pentru variabilele de bază.

3. Presupunând că se utilizează regula standard pentru selectarea coloanei de intrare, găsim:

4. Dacă s 0, procedura se oprește. Soluția de bază actuală este optimă.
5. Dacă s 0, calculați coloana transformată:

= (, ...,) . (2.4)

Dacă toate sunt 0, procedura se oprește: optimul este nelimitat.

7. În caz contrar, găsim variabila derivată din baza:

8. Construim o matrice mărită:

și transformă-l cu elementul conducător. Primele m coloane dau inversul matricei noii baze.

9. Transformați soluția de bază:

x b i x b i -- * , i r, (2.7)

și treceți la etapa 2.

Această opțiune este numită și metoda simplex modificată, deoarece reduce cantitatea de calcul la fiecare pas. Ideea este că la fiecare pas forma canonică a problemei pentru baza curentă poate fi obținută independent de alte astfel de forme direct din înregistrarea originală. sarcină standard LP.

Pentru a face acest lucru aveți nevoie de:

1. Păstrați evidența originală a sarcinii pe toată durata operațiunii metodei, acesta este prețul pe care trebuie să-l plătiți pentru o performanță mai mare;
2. Utilizați așa-numitele simplex - multiplicatori p - coeficienți pentru trecerea directă de la înregistrarea originală a problemei la forma sa actuală de bază canonică;
3. Folosiți baza inversată BO№ - o matrice de dimensiune m x m, care vă permite să calculați coloana principală aґs la fiecare pas și să actualizați simplexul - factorii p.

Metoda simplex îmbunătățită are avantaje semnificative față de forma standard. Acest lucru se aplică cerințelor de precizie, viteză și memorie. Cele mai multe dintre aceste avantaje sunt determinate de faptul că, de regulă, matricele mari probleme liniare(adică cu n>m>100) sunt slab umplute, conținând un procent mic de elemente diferite de zero.

O densitate de 5% sau mai puțin este obișnuită. O formă îmbunătățită a metodei simplex este mai capabilă să profite de avantajele care decurg din acest fapt. În această formă, diferențele caracteristice și vectorul conducător sunt calculate direct din datele originale. Deoarece matricea originală este slab umplută, iar înmulțirea ar trebui efectuată numai atunci când ambii factori sunt diferit de zero, timpul de calcul este redus semnificativ.

În plus, utilizarea numai a datelor originale înseamnă că posibilitatea de a acumula erori de rotunjire este redusă. Dimpotrivă, standard tabele simplex, chiar dacă sunt umplute inițial slab, sunt umplute rapid cu elemente diferite de zero în timpul procesului iterativ. Astfel, timpul de calcul crește, iar din moment ce fiecare tabel este calculat din cel precedent, acumularea de erori poate începe să joace un rol mai serios.