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 un circuit de calcul metoda simplex modificată, 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.

1. 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 unul nou 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ă .

1.5.1. O schemă de calcul bazată pe transformarea matricelor inverse. Analizând procedura de calcul a metodei simplex din punctul de vedere al estimării intensității muncii, este ușor de observat că cea mai critică în acest sens este etapa de recalculare a valorilor. AȘi b la trecerea de la un plan de bază la altul (clauza 3 a algoritmului). Cu toate acestea, în cazul în care numărul de constrângeri ale problemei mîn mod clar mai puține variabile n, puteți obține „economii” semnificative efectuând la următoarea iterație q Transformarea Jordan-Gauss nu peste matrice A(β ( q)), și peste matricea Δ -1 (β ( q)). Acest lucru ia în considerare și faptul că, dacă este necesar, folosind formula (1.26), se poate obține întotdeauna A(β ( q)) prin Δ -1 (β ( q)). Mai mult, pentru a efectua acțiunile procedurii simplex descrise mai sus, nu am avut nevoie de fapt de o matrice A(β ( q)) în întregime. În realitate, doar linia de rating a fost folosită în el A 0 (β ( q)) și coloana de conducere a l(β ( q)). Aceste considerații stau la baza schemei de calcul a metodei simplex, bazată pe transformarea matricelor inverse, numită și metoda simplex modificată. Primul acest algoritm a fost propus în 1951 în lucrările lui L. V. Kantorovich.

Schema de calcul a metodei simplex modificate corespunde unui sistem de tabele T 1 și T 2 (q) . Masa T 1 (orez. 1.7) este comună tuturor iterațiilor și servește la obținerea unei linii de estimări pentru linia de bază curentă A 0 (β ( q)). Dacă notăm cu δ i(β ( q)) (iÎ 0: m) rânduri ale matricei Δ -1 (β ( q)), apoi din (1.26), în special, rezultă că

După cum se vede din orez. 1.7, T 1 este format din trei blocuri:

Ø Ø centrul contine matricea A;

Ø Ø în blocul din stânga tabelului la fiecare iterație se adaugă zero rânduri ale matriceiΔ -1 (β ( q))pentru baza actuală;

Ø Ø bloc inferior situat sub matricea A, la fiecare iterație se completează cu o linie de estimări a planului curent, calculată folosind formula (1.42).

Tabel simplex T 2 (q) arătat în orez. 1.8, corespunde bazei admisibile KZLP β ( q) primit la q a iterație. Coloană N(β ( q)) conține numerele coloanelor de bază (în succesiunea apariției în bază); coloană b(β ( q)) - componente ale vectorului de constrângere relativ la baza curentă β ( q); Δ -1 (β ( q)) - matrice inversă matricei coloanelor extinse ale bazei curente β ( q); grafic a l conține un vector extins de condiții introduse în bază la iterația curentă, iar graficul următor conține coordonatele a l(β ( q)) din aceeași coloană în baza curentă β ( q) .

Prin analogie cu paragraful 1.4.1, vom descrie schema formală a algoritmului metodei simplex modificate.

0-etapă. Găsirea unei linii de bază fezabile.

1. Pentru a găsi o bază admisibilă se poate aplica metoda de minimizare a reziduurilor, discutată la paragraful 1.4.5. În acest caz, pentru a rezolva problema auxiliară, se utilizează procedura metodei simplex modificate. Ca rezultat al etapei 0 obținem o linie de bază fezabilă X(β (1)) și matricea corespunzătoare Δ -1 (β (1)) și vectorul b(β(1)).

2. Completați partea centrală a tabelului T 1 care conține matricea A.

3. Conținutul matricei Δ -1 (β (1)) și vector b(β (1)), obținut în etapa de căutare a unui plan de bază admisibil, se trece în tabel T 2 (1) .

4. Setați numărul iterației curente q egal cu 1 și treceți la etapa I.

Etapa 1. Iterare standard a algoritmului- realizat pentru următorul plan de bază X(β ( q)).

1°. Verificarea optimității planului de bază curent. Conținutul rândului zero al tabelului T 2 (q) - δ 0 (β ( q)) este rescris în coloana corespunzătoare a tabelului T 1 . Folosind formula (1.42) calculăm și completăm linia A 0 (β ( q)). Vedem linia de rating A 0 (β ( q)). Există două opțiuni:

1. A 0 (β ( q))≥0 -plan corespunzător bazei curente a problemei, optim. Procesul de calcul este finalizat. Conform formulelor (1.33) și (1.32), se scrie planul optim pentru problemă X* = X(β ( q)) Și valoare optimă funcție obiectivă f(X*) = f(X(β ( q))).

1". În linia de rating A 0 (β ( q)) există cel puțin un element A 0, j(β ( q))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план X(β ( q)) - suboptimal. Numărul este selectat l, corespunzător unui element care are un punctaj negativ minim (maxim în valoare absolută):

l coloana a matricei A devine conducereși trebuie introduse în următoarea bază. Să trecem la punctul 2° al algoritmului.

2°. Definirea unei coloane derivate dintr-o bază. Rescrierea coloanei principale a l de la masă T 1 la tabelul curent T 2 (q) . Conform formulei a l(β ( q)) = Δ -1 (β ( q))a l completați coloana corespunzătoare din tabel T 2 (q) . Există două opțiuni:

2". Pentru toată lumea iО 1: Poștă(β ( q))≤0. Se concluzionează că nelimitarea funcției obiective iar procesul de calcul se încheie.

2". Există cel puțin un index iО 1: m, pentru care a i, l(β ( q))>0. Conform regulii (1.27), locația este determinată r si numarul Nr(β ( q)) pentru o coloană derivată din bază. Să trecem la punctul 3° al algoritmului.

3°. Recalcularea relativă la noua bază a elementelor coloanei bȘi matriciΔ -1. Tranziția la o nouă bază β ( q+1) , care se obține prin introducerea β ( q) coloană a lși scoaterea unei coloane din ea a r, se efectuează după formule similare cu formulele (1.28)-(1.31). Arata ca:

Setăm numărul iterației curente q: =q+l și mergeți la primul punct al algoritmului.

În concluzie, subliniem că, datorită avantajelor de mai sus, metoda simplex modificată este de fapt utilizată în software, conceput pentru a rezolva probleme canonice programare liniară.

1.5.2. Exemplu deciziile PPP metoda simplex modificată. Să prezentăm o soluție la problema considerată anterior (1.34)-(1.35), bazată pe utilizarea procedurii metodei simplex modificate. Prin analogie cu secțiunea 1.4.3, se începe cu alegerea unei baze inițiale evidente formate din coloane (5,2,3). Pentru aceasta, Δ -1 (β ( q)) Și b(β ( q)), deci completând tabelele inițiale T 1 și T 2(1) nu este dificil.

În prima iterație rescriem linia zero

din T 2 (1) in T 1 și înmulțind-o cu matricea A, primim o linie de evaluări

Deoarece A 0 (β (1)) conține elemente negative, atunci concluzionăm că planul corespunzător bazei β (1) nu este optim și, alegând cea mai mică estimare negativă (-88), obținem numărul coloanei introdus în baza, l= 4.

Rescrierea coloanei

de la masă T 1 in T 2 (1) și recalculați coordonatele sale în raport cu baza curentă, adică înmulțiți matricea Δ -1 (β ( q)), situat în tabel T 2 (1) în stânga, pe A 4 .

După completarea tabelului T 2 (1) Cu datele de pe coloană introduse în noua bază, puteți trece la determinarea numărului coloanei de ieșire. Această procedură este efectuată în analogie completă cu metoda simplex convențională. Având în vedere relațiile elementelor b i(β(1)) și a i, l(β (1)) pentru ( iО1: m| a i, l(β (1))>0) și după ce am determinat minimul dintre ele, constatăm că r= 2. Prin urmare, coloana cu număr N 2 (β ( q)) = 2 trebuie să fie derivat din bază. Astfel, obținem o altă bază admisibilă pentru problema cu N(β (2)) = (5, 4, 3). Element A 2.3(β(1)) conduce (încercuit). Aplicând formulele (1.43)-(1.46), trecem la tabelul simplex corespunzător celei de-a doua iterații T 2 (2) și setați indicele iterației curente q = 2.

Repetând aceiași pași (pot fi urmăriți cu ușurință din tabelele prezentate aici) T 2 (2) și T 2 (3), la a treia iterație obținem planul optim al problemei și valoarea optimă a funcției obiectiv, care sunt extrase din coloana a doua a tabelului. T 2 (3) . Este ușor de observat că în procesul de soluționare am „trecut” prin aceeași secvență de planuri de bază admisibile care a fost întâlnită în secțiunea 1.4.3.

Să explicăm calculele a i , j ¢ folosind „regula dreptunghiului”. Este necesar să luați elementul de activare ak, sși conectați-l mental cu coeficientul a cărui nouă valoare doriți să găsiți. Această linie ar trebui considerată diagonala principală; pe ea este construit un dreptunghi, ale cărui laturi sunt rânduri și coloane. Trebuie să desenați o diagonală secundară în dreptunghi, apoi valoarea noului coeficient va fi egală cu valoarea sa inițială, din care se scade produsul elementelor situate pe diagonala secundară împărțit la elementul de rezolvare. Să explicăm aceste acțiuni în diagramă (Fig. 1.9). Înainte de a completa tabelul simplex, ecuațiile originale trebuie prezentate în forma (1.21).

	a k,j
			a i,j

Să ne uităm la esența transformărilor metodei simplex folosind exemplul 1.4. Să ne amintim inegalitățile de constrângere și funcția obiectivă din acest exemplu și să găsim max funcție obiectiv folosind metoda de mai sus:

F = 908X 1 + 676X 2 ® max.

X 1 + X 2 14,

X 2 10,

10 X 1 + 8 X 2 120,

7X 1 + 5 X 2 70,

4X 1 + 2X 2 28,

.

Să o transformăm în formă canonică prin introducerea unor variabile suplimentare Xj 0 și transformând inegalitățile în egalități. Trebuie remarcat faptul că, dacă există un semn „” în inegalitate, atunci cu o variabilă liberă se scrie „-”, în caz contrar - „+”:

X 1 + X 2 = 14 - X 3,

X 2 = 10 - X 4,

10 X 1 + 8 X 2 = 120 - X 5,

7X 1 + 5 X 2 = 70 - X 6,

4X 1 + 2X 2 = 28 - X 7.

Pentru a începe procedura metodei simplex, mai întâi trebuie să găsiți o soluție de referință din setul de soluții de bază ale sistemului de ecuații rezultat. Luând în considerare acest lucru, există trei etape în rezolvarea problemelor folosind metoda simplex:

Găsirea soluției de bază inițiale și formarea tabelului simplex inițial;

Determinarea unei soluții acceptabile;

Determinarea soluției optime.

etapa 1

Iniţială solutie de baza sisteme pe care le găsim prin asumarea variabilelor libere X 1Și X 2 .

Apoi X 3 = 14 - X 1 - X 2,

X 4 = 10 - X 2,

X 5 =120 - 10X 1 - 8X 2,

X 6 = 70 - 10X 1 - 5X 2,

X 7 = 28 - 4X 1 - 2X 2,

F = 908X 1 + 676X 2 = 0.

Să transformăm aceste ecuații în aspect normal:

X 3 = 14 - (X 1 + X 2),

X 4 = 10 - (0X 1 + X 2),

X 5 =120 - (10X 1 + 8X 2),

X 6 = 70 - (7X 1 + 5X 2),

X 7 = 10 - (4X 1 + 2X 2),

F = 0 + 908 X 1 + 676 X 2.

Scriem sistemul de ecuații rezultat sub forma tabelului simplex original (Tabelul 1.9). În tabel 1.9 nu există termeni liberi negativi. În consecință, am obținut o soluție suport (admisibilă), deoarece o soluție admisibilă este orice soluție nenegativă (pentru care > 0 ), dar nu este optim.

Evident, dacă pentru toate necunoscutele din funcția obiectiv F Dacă coeficienții ar fi pozitivi, atunci valoarea maximă ar fi atinsă F. Din aceasta rezultă semnul optimității unei soluții admisibile: V F- rândul tabelului simplex nu trebuie să aibă coeficienți negativi.

Tabelul 1.9

Variabile de bază X b	Membru gratuit	Variabile libere
X 1	X 2
X 3
X 4
X 5
X 6
X 7
F		- 908	- 676

a 2-a etapă

Să reamintim că operația principală a metodei simplex este în esență aceea că o variabilă de bază este înlocuită cu o variabilă liberă. . În acest caz, operațiunea de înlocuire se efectuează în următoarele condiții:

Valoarea funcției obiective F noua soluție de referință (admisibilă) trebuie să fie mai mare decât cea anterioară;

Noua soluție a sistemului trebuie să fie și de referință (admisibilă).

În exemplul nostru, prima condiție este îndeplinită dacă elementul de activare este pozitiv și este selectat în coloana coeficientului negativ F-linii.

A doua condiție este îndeplinită dacă elementul de rezoluție este găsit ca raport pozitiv minim dintre elementele coloanei cu membri liberi și elementele corespunzătoare ale coloanei de rezoluție.

Conform regulii enunțate mai sus, pentru a găsi o soluție admisibilă, variabilele de bază și libere sunt schimbate. Pentru a face acest lucru, găsiți un element de rezolvare (este încadrat în Tabelul 1.9). În cazul nostru, coloana permisivă ar trebui să fie ca X 1 , asa de X 2. Împărțirea variabilelor libere la valorile corespunzătoare X 1Și X 2 (cu excepția liniei F), găsim cea mai mică valoare pozitivă. Este important de reținut că pentru coloană X 1 :

Este important de reținut că pentru coloană X 2:

Cel mai mic raport 28/4 definește rândul de rezolvare și coloana de rezolvare, iar intersecția coloanei de rezolvare și rândul de rezolvare este elementul de rezolvare un ks= 4. În tabel. 1.9 marchem coloana de autorizare și rândul de permise cu săgeți (®). După ce a hotărât un ks, construiți următorul tabel, în care variabilele incluse în rândul și coloana elementului de rezolvare sunt schimbate ᴛ.ᴇ. converti variabilele de bază în variabile libere, iar cele libere în variabile de bază.

În exemplul nostru, schimbăm variabilele X 7 Și X 1 , notat în tabel. 1,9 săgeți. Coeficienții noului tabel. 1,10 se găsește din coeficienții vechiului tabel. 1.9, folosind expresiile date în tabel. 1.8 și „regula dreptunghiului”. În tabel 1.10 din nou nu avem o soluție optimă.

Tabelul 1.10

Variabile de bază X b

Membru gratuit B

Variabile libere

X 7

X 2

X 3

- 1/4

1/2

X 4

X 5

-5/2

X 6

-7/4

3/2

X 1

1/4

1/2

F

-222

Conform regulilor descrise mai sus în tabel. 1.10 găsim elementul de rezolvare 1 și construim un nou tabel. 1.11 prin înlocuirea bazei ( X 4Și X 2). Subliniem în special faptul că pentru a găsi elementul de rezolvare trebuie să alegem cea mai mică valoare pozitivă, ᴛ.ᴇ. Nu luăm în considerare relațiile negative ale termenilor liberi cu coeficienții coloanei de rezoluție.

a 3-a etapă

Să verificăm dacă soluția găsită este optimă, iar pentru exemplul nostru - maximă. Pentru a face acest lucru, vom analiza funcția obiectiv F: F = 8576 + 227 X 7 + 222 X 4.

Funcția obiectiv nu conține coeficienți negativi și are cea mai mare valoareÎn ultimul tabel, am obținut soluția optimă:

X3 = 2; X2 = 10; X5 = 20; X6 = 6; X1 = 2; X7 = X4 = 0;

F max = 8576.

Vă rugăm să rețineți că rezultatele rezolvării metodei simplex și a metodei grafice sunt aceleași.

În conformitate cu secvența considerată, algoritmul metodei simplex trebuie să aibă următoarele blocuri:

1. Găsirea soluției inițiale de bază (de referință) și formarea tabelului inițial.

2. Găsirea elementului de rezolvare un ks(găsirea termenului liber negativ - b i < 0 и минимального отношенияb i / a ij; Dacă nu există coeficienți negativi în rândul termenului liber negativ, atunci problema este de nerezolvat).

3. Recalcularea masa noua conform formulelor din tabel. 1.8.

4. Verificarea prezenței unui termen liber negativ. Dacă există, treceți la pasul 2. Absența unui termen liber negativ înseamnă că a fost obținută o soluție de referință (admisibilă).

5. Similar pașilor 2 - 4, tabelul este recalculat atunci când se caută soluția optimă.

Rezolvarea problemei LP folosind metoda simplex sub formă de matrice

Necesar pentru a minimiza ,

sub restricții

la " X³ 0.

Să introducem vectorii:

C= (C 1 , ... , C n) - vector de estimări,

X= (X 1 , ... , X n) - vector de variabile,

b= (B 1 , ... , B m) - vector de restricții

și matrice

A=

dimensiune (mn) - matricea coeficienților de constrângere.

Atunci problema LP va avea următoarea interpretare:

minimiza F=CX

in conditii AX = b, X 0.

Această problemă poate fi scrisă sub formă de matrice:

Să introducem notația:

A * = - aici este matricea A* dimensiune (m+1)(n+1).

Conform metodei de mai sus, se găsește elementul de rezolvare un ks.

Urmatorul pas metoda simplex - o procedură de eliminare gaussiană care vă permite să faceți toți coeficienții în s- m coloana, cu excepția un ks, zero, un ks- egal cu unu.

Este important de reținut că pentru metoda simplex sub formă de matrice, iterația metodei simplex este echivalentă cu înmulțirea ecuației matriceale din stânga cu următorul matrice pătrată:

(1.23)

, Unde k 0; s 0.

Dacă toate coloanele matricei Aîmpărțiți în de bază Bși nebază N, atunci problema LP poate fi scrisă după cum urmează:

,

Unde CbȘi C N- componentele vectoriale corespunzătoare C, X b, X N- variabile de bază și nebaze.

Pentru a selecta variabilele de bază inițiale x b ar trebui să înmulțiți ecuația din stânga cu matricea:

Unde R= CbB-1.

Ca rezultat obținem

,

Unde eu- matrice de identitate.

Rezultă că estimări relative pentru variabile nebazice

c j = c j - C b B -1 a j = c j - Ra j .

Baza va fi admisibilă dacă termenii liberi ai variabilelor de bază sunt nenegativi, ᴛ.ᴇ. B -1 b ³ 0.

Dacă c j³ 0 pentru , atunci baza este soluție optimă sarcini. Vectorul se numește vectorul prețului curent. Fiecare rând este înmulțit cu un vector Rși se scade din linia coeficientului de cost pentru a elimina coeficienții de cost pentru variabilele de bază.

Dacă problema LP nu este specificată în formă canonică, ᴛ.ᴇ.

minimiza F=CX

in conditii AX b , X 0,

apoi, introducând variabile slabe, acestea pot fi scrise sub formă

Metoda de eliminare a rândurilor pentru o matrice este echivalentă cu înmulțirea acelei matrice din stânga cu B-1, Unde B- baza submatricelor A, Apoi

,

ᴛ.ᴇ. matrice obţinută în locul matricei identitare eu, va fi matricea inversă pentru baza curentă. Scorurile relative situate deasupra matricei de identitate vor fi

,

deoarece sunt vectori unitari.

Deoarece F= C b B -1 b = Rb, valoarea curentă a funcției obiectiv este egală cu produsul vectorului prețurilor curente al matricei A la vectorul original b.

Exemplu.
Postat pe ref.rf
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5® min

sub restricții

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10 ,

3X 2 + 3X 4 + 6X 5 = 9,

.

Pentru acest exemplu matrice A* va arăta ca

.

Lăsa X 1Și X 2- variabile de bază.

Matrice B se pare ca

.

Apoi matricea inversă B-1 Are următoarea vedere

.

Să ne amintim asta , unde matricea adjunctă compusă din complemente algebrice de elemente b ik determinant al matricei B.

Determinantul este egal cu:

= .

Prin urmare, matricea B Nimic special.

Adunări algebrice elementele determinantului au următoarele semnificații:

b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2; acestea . .

Înmulțind cu , găsim matricea inversă:

.

Vectorul preţurilor curente va fi

R = C b B -1 = = .

Să ne amintim asta Cb- componente ale vectorului de bază C:

Apoi = .

Pentru a selecta baza inițială aveți nevoie de o matrice A*înmulțiți la stânga cu matrice

=

.

Elementul de rezolvare este într-un pătrat.

O iterare a metodei simplex este echivalentă cu tabelul rezultat înmulțit din stânga cu următoarea matrice:

.

Această matrice este obținută din matricea (1.23)

Aici aks = 2;

a 11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;

a 13 = 0 ; a 21 = 0 ; a 22 = 1/ a ks = 1/2 ; a23 = 0;

a 31 = 0 ; a 32 = - a ms / a ks = -1/2 ; a 33 = 1.

Atunci noi avem

=

(1.24)

Elementul de rezolvare este plasat într-un pătrat.

Următoarea iterație a metodei simplex este echivalentă cu înmulțirea la stânga cu matrice

.

=

.

Prin urmare, Fmin =11; X 4=7/3; X 5=1/3; X 1 =X 2 =X 3=0.

Metoda simplex modificată (MSM) diferită de metoda simplex obișnuită (CM) pentru că în CM Toate elementele tabelelor simplex sunt recalculate la fiecare iterație și când se obține următorul tabel, toate tabelele anterioare, inclusiv cel original, nu sunt salvate. ÎN MSM tabelul inițial este salvat și la fiecare iterație se determină următoarele: un rând de estimări relative C introduse în bază și valoarea curentă a vectorului părților din dreapta ale constrângerilor. Pentru a determina toate elementele tabelului după j- a iterație CM, este suficient să cunoaștem matricea B-1, corespunzând acestui tabel, matricea originală și indici ai variabilelor de bază curente. Apoi vectorul curent R = C b B -1(indicii variabilelor de bază curente determină ce elemente ale vectorului estimărilor din tabelul sursă sunt incluse în vector C b); =B -1 b, Unde b este preluat din tabelul original și orice coloană a noului tabel = B-1A j , Unde A j - coloana tabelului sursă.

Să fie dat acum tabelul sursă B-1, corespunzător tabelului i a iterație. Pentru a obține matricea B-1, corespunzătoare (i+1)- a treia iterație, trebuie să definiți o coloană non-bază i tabelul care ar trebui introdus în bază. Din CM rezultă că trebuie introdusă în temei dacă Cj<0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить C j Pentru i tabelele, alegeți dintre ele<0, а затем вычислить

A S = B-1și = B -1 b (= C j - Ra j ).

După ce am găsit elementul de rezoluție și folosind elementele vectorilor și , găsim matricea B-1 pentru următorul tabel.

Exemplu. Folosind metoda simplex modificată pentru a minimiza

F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min

cu restrictii:

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

Alegerea ca variabile de bază X 1Și X 2, am primit următoarea sarcină: F = 43 - 9/2X 3 - 12X 4 - 12X 5

Agenția Federală pentru Educație

Instituție de învățământ de stat de învățământ profesional superior

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

Metoda pe bază artificială. 7

Metoda simplex modificată. 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 între ele se găsește cea optimă. 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 celor 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 ajunge la 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 a ΔF 2 este inclus în bază, adică cu cea mai mare în 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 la rezolvarea LLP depinde într-o măsură mai mare de numărul de constrângeri, mai degrabă decât de numărul de variabile. Pentru a merge la PD, este necesar ca PD să fie scris în formă canonică standard. 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

Acest curs a pus bazele metodelor matematice pentru 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.

3. Metoda simplex modificată

Acest tip de metodă simplex se bazează pe caracteristicile algebrei liniare care permit să lucrăm cu o parte din matricea de constrângeri atunci când rezolvăm o problemă. Uneori metoda se numește metoda matricei inverse.

În timpul funcționării algoritmului, matricea de constrângeri este inversată spontan în părți corespunzătoare vectorilor de bază actuali. Această abilitate face ca implementarea calculelor să fie foarte atractivă datorită economisirii de memorie pentru variabilele intermediare și a reducerii semnificative a timpului de calcul. Această capacitate este bună pentru situațiile în care numărul de variabile n depășește semnificativ numărul de constrângeri m.

În general, metoda reflectă caracteristicile tradiționale ale abordării generale a rezolvării problemelor de programare liniară, inclusiv canonizarea condițiilor problemei, calculul diferențelor simplex, verificarea condițiilor de optimitate, luarea deciziilor pe bază de corecție și eliminarea Jordan-Gauss. Caracteristicile includ prezența a două tabele - cele principale și auxiliare, ordinea în care sunt completate și o anumită specificitate a formulelor de calcul.

Cunoscând planul optim pentru această problemă, pe baza relațiilor obținem planul optim pentru problema inițială.

Astfel, procesul de găsire a unei soluții la o problemă de programare neliniară include următorii pași:

1. Problema originală se reduce la o problemă de programare liniară.

2. Găsiți o soluție la o problemă liniară

Folosind relațiile, se determină planul optim pentru problema inițială și se găsește valoarea maximă a funcției obiectiv a problemei neliniare.

Prima etapă: Primirea sarcinilor pentru cursuri

1. Toate datele numerice referitoare la procesele de producție și economice propuse sunt preluate pe baza unui cod din șase cifre:

Sub fiecare număr literele a, b, c, d, e, f sunt scrise sub următoarea formă:

din ultimul rând al tabelului sarcinilor individuale găsim coloanele corespunzătoare literelor a, b, c, d, e, f. Apoi datele numerice necesare pentru a finaliza acest lucru de curs vor fi datele situate în a - acea coloană din rândul 9, b - acea coloană din rândul 5, c - acea coloană din rândul 5, d - acea coloană din rândul 8, e - acea coloană din rândul 7 și f – acea coloană din rândul 2.

Conform tabelului sarcinilor inițiale pentru orice variantă de sarcini din coloana a, executantul primește varianta sarcinii care se execută. În cazul meu, numărul 9 corespunde opțiunii 9.

O anumită plantă produce trei tipuri de produse și consumă două tipuri de resurse. Funcția de producție a fiecărui tip de produs la întreprindere este descrisă prin egalități:

unde C i și sunt valori constante, i = 1, 2, 3;

X 1 – resurse de muncă în zile-om;

X 2 – resurse monetare şi materiale, în tenge;

Y i este produsul rezultat

X 1 = a 1 x 1 + b 1 x 2 + c 1 x 3

X 2 = a 2 x 1 + b 2 x 2 + c 2 x 3

Găsiți toate soluțiile de bază nenegative și determinați planul optim F = y 1 + y 2 + y 3.

Se știe că pentru producția de j – acel tip de produs, a ij unități de i – acea resursă sunt cheltuite. Aceste costuri sunt prezentate în tabelele 3.9.1. – 3.9.10

Datele numerice ulterioare sunt preluate numai din tabelul de date sursă al opțiunii de sarcină selectată, de exemplu. din tabelul nr 3.9.11.

2. Conform coloanei tabelului nr. 3.9.11 pentru rândul 8, tabelul inițial al costurilor unităților de resurse va fi tabelul nr. 3.9.4 i.e. următorul tabel:

Resursele produselor
eu	8	4	6
II	160	240	200

3. Folosind coloana c – pe linia 3 găsim cu 1 =6, α 1 =0,6

4. Folosind coloana d – pe linia 5 determinăm cu 2 =5, α 2 =0,5

5. Folosind coloana e – linia 4, stabilim că c 3 =8, α 3 =0,4.

6. Și în sfârșit, folosind coloana f - în linia 1 găsim T zile persoane = 1000, P tenge = 280000

Pentru producţie există resurse de muncă T man zile şi resurse monetare P tenge.

Este necesar să se găsească planul optim de producție la care produsul de ieșire va fi cel mai mare.

A doua etapă este elaborarea unui model matematic al problemei

1. Pe baza datelor inițiale obținute în prima etapă și a descrierii procesului de producție dat, se întocmește următorul tabel:

Resursele produselor
eu	8	4	6	1000
II	160	240	200	280000

Fie X 1 să desemneze resurse de primul tip.

Fie X 2 resurse de tip II.

2. Revenind la condițiile problemei, determinăm toate restricțiile posibile, combinându-le într-un sistem de restricții.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 ≤ 280000

Astfel, avem o problemă de programare neliniară. Astfel de probleme se numesc probleme de programare neliniară.

Problemele de programare neliniară sunt rezolvate prin reducerea lor la probleme de programare liniară.

Pentru rezolvarea problemei de programare liniara se foloseste metoda simplex.

A treia etapă este alegerea unei metode de rezolvare a problemei matematice rezultate

1. Pentru a rezolva probleme de programare liniară folosind metoda simplex, problema se reduce la forma canonică:

8X 1 + 4X 2 + 6X 3 + X 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

Sunt în curs de dezvoltare metode de găsire a valorilor extreme ale funcției obiectiv între setul de valori posibile ale acesteia determinate de constrângeri. Prezența restricțiilor face problemele de programare matematică fundamental diferite de problemele clasice de analiză matematică de găsire a valorilor extreme ale unei funcții. Metode de analiză matematică pentru căutarea extremului unei funcții în probleme...

Găsirea punctului Kuhn-Tucker oferă o soluție optimă pentru problema de programare neliniară. Teorema 2 poate fi folosită și pentru a demonstra optimitatea unei soluții date la o problemă de programare neliniară. Pentru a ilustra, luați în considerare din nou exemplul: Minimizarea sub constrângeri Folosind teorema 2, demonstrăm că soluția este optimă. Avem deci...

Razele care emană dintr-un punct se numesc con convex poliedric cu un vârf într-un punct dat. 1.4 Fundamente matematice pentru rezolvarea grafică a problemelor de programare liniară 1.4.1 Aparatură matematică Pentru a înțelege totul mai departe, este util să cunoaștem și să ne imaginăm interpretarea geometrică a problemelor de programare liniară, care poate fi dată pentru cazurile n = 2 și n = ...

Dacă punem variabilele de bază curente într-un astfel de tabel simplex egal cu Ai,0, iar pe cele libere egale cu zero, atunci se va obține o soluție optimă. Practica utilizării metodei simplex a arătat că numărul de iterații necesare pentru a rezolva o problemă de programare liniară variază de obicei între 2m și 3m, deși pentru unele probleme special construite, calculele conform regulilor metodei simplex se transformă în direct...