Metoda simplex pentru rezolvarea problemelor de programare liniară. Rezumat: Metoda grafică și metoda simplex pentru rezolvarea problemelor de programare liniară

Metoda simplex constă în găsirea și testarea unui vârf (unghi) care este o soluție la problema LP. În fiecare etapă, metoda selectează un vârf și variabilele corespunzătoare acestuia, care asigură deplasarea la minim (maxim) cu cea mai mare viteză. Variabila selectată o înlocuiește pe cealaltă, cea mai restrictivă. Metoda simplex vă permite, de asemenea, să determinați dacă există o soluție. Algoritmul care implementează metoda simplex poate fi scris astfel:

Pasul 1. Se determină un anumit vârf în ODR, corespunzător soluțiilor (variabilelor) admisibile de bază găsite prin extragerea din matrice T- coloane liniar independente și echivalând cu zero toate celelalte variabile corespunzătoare altor coloane ale matricei.

Pasul 2. Selectat dintre toate posibilele rămase p - t muchii corespunzătoare variabilelor non-bazice, o muchie (variabilă) care, atunci când se deplasează de-a lungul ei, duce la cea mai rapidă scădere funcție obiectivă.

Pasul 3. Este ca și cum se efectuează o mișcare de la vârful inițial de-a lungul muchiei selectate la un alt vârf, ceea ce oferă o nouă soluție care are o valoare CF mai mică. Un nou vârf se formează prin înlocuirea variabilei de bază (marginea) cu o nouă variabilă de bază (marginea).

Coloanele și elementele vectorilor sunt de obicei ordonate și scrise sub forma unui tabel simplex, a cărui formare va fi prezentată mai jos.

Metoda simplex rezolvă problema LP în formă standard.

Minimizează (maximizează) funcția în condițiile x > 0; Ax = b.

Matricea A este reală și are dimensiunea T x „și rangul T.

Problema LP formulată poate fi scrisă și sub formă

Pe baza înregistrării problemei LP în forma (8Л), putem spune că matricea extinsă

dimensiuni (t + 1) (n + 2) corespunde soluțiilor[x/] t.

Să reprezentăm matricea A ca un set de coloane

Deoarece matricea A are rang T, atunci va fi T coloane liniar independente ale matricei A, de exemplu (a V1 ,...,a V/i Considerăm un vector x° > 0, astfel încât tot p - t elementele sunt 0 și Ax° = b. Să fie acestea elemente cu numere..., in m . Să presupunem, de asemenea, că locația aw a coloanelor liniar independente ale matricei A corespunde locației elementelor nenule în vectorii 0. Geometric, conform Enunțului 3 din § 7.6, aceasta înseamnă că x° este vârful (unghiul) ODR și, în plus, satisface condițiile date. Această soluție se numește soluție de bază admisibilă. Unghiurile multimii admisibile sunt soluții de bază admisibile.

Amintiți-vă că setul de soluții de bază conține toate informațiile necesare pentru soluție optimă Probleme cu LP. Pentru cazul bidimensional considerat în § 7.6, soluțiile de bază sunt toate cele 6 puncte, iar soluțiile de bază admisibile sunt punctele L, V, Si 0.

Astfel, orice vector x similar cu x° poate fi scris ca

Unde x in- un vector ale cărui elemente corespund coloanelor liniar independente ale matricei A; xF - vector cu zero elemente.

Să definim în mod similar vectorii

Variabile care sunt elemente ale unui vector x in, sunt numite variabile de bazăși variabilele care sunt elemente ale vectorului x F sunt numite gratuit (variabile nebazice).

Deoarece x°F=0, atunci valoarea funcției obiectiv pentru vectorul inițial x° va fi egală cu

unde /° este valoarea lui / în punctul x°.

Se numește soluția (8.1) de forma [x°/°]t pentru x > 0 soluție evidentă (explicită). Astfel, dacă stabilim variabile nebazice egale cu zero, obținem o soluție evidentă.

Pentru comoditate, să rearanjam T coloane liniar independente ale matricei A in partea stangași scrieți matricea în forma

Aici matricea B corespunde T coloane liniar independente are dimensiune TXT si rang T,și matricea F

este al (p - t) matrice. Deoarece matricea B constă din coloane liniar independente, are un invers B -1 și detB φ 0. Rețineți că pentru a forma matricea B puteți alege oricare T coloane liniar independente ale matricei A.

Să reprezentăm problema (8.1) ținând cont de notația introdusă

Această reprezentare corespunde matricei extinse Să presupunem că

de unde urmează

Dacă vectorul x V va fi o soluție a sistemului Bx d = b, atunci va fi soluția de bază. Dacă inegalitatea se menține V= B -1 b > O, atunci x in va fi o soluție acceptabilă.

Astfel, soluția curentă satisface următoarea ecuație:

Să considerăm matricea (8.4). Variabilele de bază vor fi prezentate în formă explicită dacă înlocuim matricea B cu matricea identitate I. Înmulțind primul rând al matricei (8.4) din stânga cu B~ 1, obținem

unde B_1 b > O, adică T Elementele de sus din coloana din dreapta sunt nenegative și reprezintă valoarea curentă a variabilelor.

Pe partea stângă a linia de sus Rezultatul este o matrice unitară: B -1 B = I. Această prezentare foarte convenabil, deoarece la înmulțirea cu un vector x in fiecare variabilă va fi pe o linie separată.

Astfel, soluția de bază, pe care o vom considera admisibilă și corespunzătoare bazei B, este x m = [x în 0], unde x în == B_1 b. Soluţia de bază rezultă din ipoteza că x F = 0. Cu toate acestea, dacă xF* 0, atunci x^ poate fi calculat ca x 5 = = B~"b - B^"Fx/r. Substituind această expresie în funcția obiectiv (funcția de cost), obținem

Deoarece este necesar să se determine dependența costului de variabilele nebaze, dintre care una este apoi inclusă în cele de bază, linia de jos din matricea I ar trebui să fie zero. Pentru a face acest lucru, în (8.7) înmulțim primul rând (al matricei) cu de la catre si adauga-l cu al doilea

unde este valoarea funcţiei obiectiv pentru secolul iniţial

torus x 0 din (8.3).

Matricea (8.8) este numită tabel simplex. Aducând-o la această specie este etapa inițială a algoritmului simplex. În timpul execuției algoritmului, se face o tranziție de la un tabel la altul până când elementul din dreapta jos al tabelului devine maxim sau minim.

Folosind un tabel simplex, este ușor să vedeți o soluție validă. Variabile X F corespund submatricei zero, variabile x in- matricea unitatilor:

Să presupunem că problema LP a fost redusă la forma standard, a fost calculat tabelul simplex și a fost selectată soluția de bază inițială corespunzătoare vârfului poliedrului de soluție.

Apoi - rezolvarea problemei (8.1). Asa de

ca b > Oh, aceasta este o soluție de bază admisibilă.

Să prezentăm matricea (8.9) într-o formă mai convenabilă, păstrând notația de bază:

Să luăm în considerare separat problemele de maximizare și minimizare.

2. Introducerea variabilelor de bază naturale. Construcția unui tabel simplex. Definiția planului zero.

Metoda simplex. Algoritmul metodei simplex.

Metoda simplex- algoritm pentru rezolvarea problemei de optimizare programare liniară prin enumerarea vârfurilor unui poliedru convex în spațiul multidimensional. Metoda a fost dezvoltată de matematicianul american George Danzig în 1947.

Ideea metodei simplex este că problema descriptivă pusă este tradusă în formă matematică. Formularea matematică a problemei conţine ecuaţia funcţiei obiectiv indicând rezultatul dorit - determinarea minimului sau maximului funcţiei obiectiv; sisteme de constrângeri liniare specificate prin egalităţi sau inegalităţi. Descrierea matematică rezultată este redusă la formă de matrice. Apoi descrierea matriceală a problemei este redusă la formă canonică. După sistem ecuatii lineare redusă la formă canonică, începem să rezolvăm problema de programare liniară. Algoritmul pentru rezolvarea acestei probleme constă dintr-o succesiune de matrice de construcție. Fiecare pas al solutiei te apropie de obtinerea rezultatului dorit.

În schema de calcul a metodei simplex se implementează un proces ordonat în care, pornind de la un punct inițial admisibil de colț (de obicei originea), se fac tranziții succesive de la un punct extrem admisibil la altul până când se ajunge la un punct corespunzător soluției optime. găsite.

Algoritmul metodei simplex

1. Aducem sistemul de restricții la formă canonică(când sistemul este limitat). Mai mult, o singură bază poate fi identificată în sistem.

2. Găsiți originalul plan de referință(soluții de bază nenegative ale sistemului de ecuații KZLP). Fiecare dintre planurile de referință este determinat de un sistem de m vectori liniar independenți conținut într-un sistem dat de n vectori A 1 , A 2 ,…, A n. Limita superioară a numărului de planuri de referință conținute într-o problemă dată este determinată de numărul de combinații Cu nm);

3. Construim tabel simplex (tabel simplex o matrice care servește ca mijloc de enumerare a soluțiilor de bază admisibile ale unei probleme de programare liniară (nedegenerată) atunci când o rezolvă folosind metoda simplex. Este format dintr-o matrice de coeficienți ai unui sistem de ecuații de programare liniară redusă la formă canonică; transformarea sa secvențială conform așa-numitului algoritm simplex permite un număr limitat de pași (iterații) pentru a obține rezultatul dorit - un plan care oferă o valoare extremă a funcţiei obiectiv).

4. B tabel simplex verificăm vectorii pentru negativitate, i.e. evaluări Zj – Сj scris pe linie trebuie să fie ≤ 0 (cel puțin), Zj – Сj ≥ 0(la maxim). Dacă estimările satisfac condițiile de optimitate, atunci problema este rezolvată.

5. Dacă pentru unii vectori sunt încălcate condițiile de optimitate, atunci este necesar să se introducă în bază un vector care să corespundă cu:

max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min, Unde x i> 0

Element vectorial θ j care corespunde θ 0 j numit permisiv; rândul și coloana în care se află se numesc ghid; vectorul din rândul ghid părăsește baza.

6. Să găsim coeficientul de expansiune pentru toți vectorii din noua bază. Să aplicăm metoda Giordano Gauss

Să verificăm planul de referință optim. Dacă estimarea îndeplinește condițiile de optimitate, atunci problema este rezolvată; dacă nu, atunci se efectuează pașii 5-7.

2. Introducerea variabilelor de bază naturale. Construcția unui tabel simplex. Definiția planului zero.

Metoda simplex este cea mai eficientă în rezolvare sarcini complexeși reprezintă un proces iterativ (pas cu pas) începând cu zero(de referință) soluție (vârf n-poliedru dimensional). Următorul în căutare varianta optima Planul presupune deplasare de-a lungul punctelor de colț (vârfurile poliedrului) până când valoarea funcției obiectiv atinge valoarea maximă (minimă). Să luăm în considerare algoritmul metodei simplex folosind exemplul unei probleme de planificare a cifrei de afaceri cu resurse limitate de materii prime.

Firma vinde n grupe de produse, având m resurse materiale şi băneşti limitate b i ≥0 (1 ≤ i≤ m). Costurile tuturor resurselor sunt cunoscute i- tipul de producție și vânzare a unei unități de mărfuri a fiecărei grupe, prezentate sub formă de matrice ( A ij) și profitul primit de întreprindere din vânzarea unei unități de mărfuri j-grup inclus in functia obiectiv Z(X). Metoda de programare liniară nu este diferită de sistemul (1) - (2):

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

a 11 X 1 + a 12 X 2 +...a 1n X n ≤ b 1,

a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)

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

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

Etapele rezolvării problemei folosind metoda simplex includ:

1) Întocmirea unui plan de referință zero. Introducem noi variabile nenegative (de bază), datorită cărora sistemul de inegalități (2) devine un sistem de ecuații:

a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1

a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

……………………………………..

a m1 X 1 + a m2 X 2 +...a mn X n + X n+m = b m,

Dacă luăm variabilele de intrare ca vectori coloană, atunci ele reprezintă singur (de bază) vectori. Rețineți că variabilele de bază au un simplu sens fizic- Acest rest resursă specifică din depozit pentru un anumit plan de producție, de aceea se numește această bază natural. Rezolvăm sistemul (3) în raport cu variabilele de bază:

X n+1 = b 1, -a 11 X 1 - a 12 X 2 -...a 1n X n

X n+2 = b 2 - a 21 X 1 - a 22 X 2 -...a 2n X n (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

Rescriem funcția obiectiv în forma

Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)

Presupunând că variabilele principale necesare X 1 = X 2 = X 3 = ... = X n = 0, obținem un plan de referință zero X = (0, 0, ...0, b 1, b 2, b 3 ... b m), la care Z(X) = 0 (toate resursele în stoc, nimic produs). Introducem planul într-un tabel simplex.

Plan	Bază	C i /C j	Sens X i	X 1	X 2	Xn	Xn+1	Xn+2	X n+ 3	Q min
	Xn+1		b 1	un 11	un 12	un 13				b 1/a 12
Xn+2		b 2	un 21	un 22	un 23				b 2 / a 22
Xn+3		b 3	un 31	un 32	un 33				b 3 / a 32
Z(X) = 0	-C 1	- C 2	- C 3				Index. linia

2) Din coeficienții negativi ai liniei index, selectați cel mai mare valoare absolută, care determină coloana principală și arată ce variabilă la următoarea iterație (pas) se va muta de la principală (liberă) la cea de bază (de fapt, este selectat grupul de produse ale cărui vânzări generează venitul maxim). Apoi împărțim rezervele de materii prime b i la coeficienții de cost corespunzători, introducem rezultatele într-un tabel și determinăm valoarea minimă Q min (este selectată resursa a cărei rezervă limitează cel mai puternic producția grupului de produse selectat). Această valoare selectează linia de început și variabila X i, care, când urmatorul pas(iterație) va părăsi baza și va deveni liber.

3) Trecerea la un nou plan se realizează ca urmare a recalculării tabelului simplex folosind metoda Jordan-Gauss. În primul rând, înlocuim X j în bază cu X i a coloanei principale. Să împărțim toate elementele liniei de conducere la elementul de rezoluție (RE), în urma căruia locul RE în linia de conducere va fi 1. Deoarece X i a devenit de bază, coeficienții săi rămași ar trebui să fie egali cu 0 Elementele noi ale acestui plan sunt găsite conform regulii dreptunghiului

NE=SE – (A*B)/RE (6)

Planul rezultat este evaluat folosind coeficienții liniei index: dacă toți sunt pozitivi, atunci planul este optim; dacă nu, atunci planul poate fi îmbunătățit prin efectuarea următoarei iterații (pasul).

Exemplu. Pentru achizitionarea de echipamente pt loc de producție Au fost alocate 20 de mii de ruble. Echipamentul poate fi amplasat pe o suprafata care nu depaseste 72 mp. Puteți comanda echipamente de două tipuri: tip A, care necesită o suprafață de producție de 6 mp și oferă 6 mii de unități. produse pe schimb (preț 5.000 de ruble) și tipul B, necesitând o suprafață de 12 mp și producând 3 mii de unități (preț 2.000 de ruble). Care este planul optim de achiziție a echipamentelor de asigurat performanță maximă complot?

Să notăm cantitatea de echipamente achiziționate de tip A și B cu X 1 și respectiv X 2.

Productivitatea șantierului (funcția obiectivă): Z(X) =6Х 1 +3Х 2.

Principalele limitări sunt legate

cu numerar: 5Х 1 +2Х 2 ≤ 20,

cu suprafața locului de producție: 6Х 1 +12Х 2 ≤ 72.

Introducem noi variabile de bază X 3 (restul Bani după achiziționarea echipamentului) și X 4 (zona rămasă după plasarea echipamentului) și rescrieți restricțiile sub forma unui sistem de ecuații:

5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

În acest caz, funcția obiectiv: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .

Facem un (0-lea) plan de referință: X = (0, 0, 20, 72), adică. încă nu s-a cumpărat nimic (nu s-au cheltuit bani, spațiul este gol). Realizarea unui tabel simplex

Plan	Bază	C i /C j	Sens X i	X 1	X 2	X 3	X 4	Q min
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Linie index
	→X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Linie index
	X 1					0,25	-1/24	-
→X 2					-1/8	5/48	-
Z(X) =62+35=27			9/8	1/16	Linie index

Evident, coloana principală corespunde lui X 1, deoarece are cel mai mare indice 6. Găsim valoarea minimă a lui Q min = 4 (cea mai severă constrângere de resurse) prin definirea unui rând de început care arată că X 3 este derivat din variabilele de bază. , iar X se introduce în loc 1 . Recalculăm elementele liniei de conducere, împărțindu-le la 5 și folosind formula (6) determinăm elementele celei de-a doua și liniile index. Funcția obiectiv pentru primul plan este egală cu Z(X) = 6*4+3*0 = 24.

Cu toate acestea, unul dintre coeficienții rândului index pentru coloana X 2 rămâne negativ -0,6, prin urmare acest plan nu este optim și este necesară o altă iterație (pas) pentru a-l îmbunătăți. Selectați a doua coloană ca principală și valoarea minima Q min = 5 definim linia de conducere cu variabila de bază X 4. După ce au efectuat aceleași transformări, obținem al 2-lea plan, care va fi optim, deoarece toți coeficienții indicilor sunt pozitivi.

Să analizăm rezultatele obținute. Cu o soluție optimă, funcția obiectiv are o valoare maximă de 27 de mii de ruble, în timp ce ambele resurse sunt eliminate din bază, prin urmare cheltuite complet.

Să ne asigurăm de asta: 5*2+2*5 = 20 mii de ruble, 6*2+12*5=72 mp. Soluția necesară este X = (2; 5; 0; 0). Acest lucru nu se întâmplă întotdeauna.

Prelegerea nr. 10

Subiect: Metoda simplex pentru probleme cu o bază artificială

Metoda soluției simplex se bazează pe introducerea unor variabile suplimentare (de bază) care fac posibilă formarea unei matrice unitare. Dacă constrângerile problemei sunt prezentate sub formă de inegalități:

a i1 X 1 + a i2 X 2 +...a în X n ≥ b i (1)

sau ecuații:

a i1 X 1 + a i2 X 2 +...a în X n = b i (1*),

atunci este imposibil să obțineți planul de referință în forma dorită. În acest caz, pentru a respecta egalitățile (1*), introducem baza artificiala Y i , și variabilele artificiale nu sunt direct legate de conținutul sarcinii, dar fac posibilă construirea unui plan de referință (de pornire):

a i1 X 1 + a i2 X 2 +...a în X n +Y i = b i (2)

Funcția obiectiv la rezolvarea problemei la maximum se va scrie sub forma:

Z(X) =∑C j X j +(-M)∑Y i (3),

atunci când rezolvați o problemă similară cel puțin:

Z(X)=∑C j X j +(M)∑Y i (3*),

unde M este un număr pozitiv foarte mare, un fel de penalizare pentru utilizarea variabilelor artificiale.

În cazul inegalităților (1), introducem inițial variabile suplimentare X n + i cu semnul minus. Matricea lor nu va fi unitară, prin urmare, în fiecare inegalitate a sistemului (1) introducem variabile artificiale У i:

a i1 X 1 +a i2 X 2 +…a în X n –X n+i +Y i =b i (4)

Funcția obiectiv în acest caz este Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (pentru a găsi maximul). Aplicație baza artificiala oferă metodei simplex o mai mare flexibilitate și îi permite să fie utilizată pentru o gamă largă de sarcini.

Exemplu . Determinați valorile maxime și minime ale profitului pentru producția a două tipuri de produse A și B, dacă costurile de producție și profitabilitatea din vânzările unei unități de produs sunt date în tabel. Condiția principală este angajarea deplină a lucrătorilor la întreprindere.

Din punct de vedere matematic, constrângerile de producție vor fi scrise sub forma unui sistem mixt:

1X 1 + 1X 2 ≤ 6,

2X 1 + 1X 2 =8.

Să introducem variabila de bază X 3 pentru prima inegalitate și variabila artificială Y 1 pentru a doua ecuație:

1X 1 + 1X 2 + X 3 = 6,

2X 1 + 1X 2 +Y 1 =8.

Să exprimăm X 3 și Y 1 din sistemul de ecuații rezultat și, pentru a determina maximul, să ne imaginăm funcția obiectiv:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

Pentru planul de referință - X=(0,0,6,8). Să construim un tabel simplex:

Plan	Bază	C i /C j	Sens X i	X 1	X 2	X 3	Y 1	Q min
	X 3							6/1=6
Y 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Linie index
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		M+1,5	Linie index
	→X 2						-1	-
X 1					-1		-
Z(X) =32+24=14				M+1	Linie index

De regulă, îmbunătățirea planului de referință începe cu eliminarea din bază a variabilei artificiale Y 1. Planul optim X = (2,4,0,0) a fost obținut în a doua iterație, cu un venit maxim de 14 mie. freca. , iar coeficienții rândului index sunt nenegativi. Este ușor de verificat că în această sarcină, cu un plan optim, resursele sunt utilizate pe deplin (2*1+4*1=6; 2*2+1*4=8).

La găsirea profitabilității minime, formulăm diferit funcția obiectiv (+MY 1 se introduce ca termen:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

Planul de referință este același, dar coeficienții rândului index din tabelul simplex sunt diferiți. Coloana principală, ca și înainte, este selectată de cea mai mare valoare absolută coeficient pozitiv pentru X 1, rândul principal este determinat de valoarea minimă a lui Q min = 4. La prima iterație, variabila artificială Y 1 este derivată din bază.

Plan	Bază	C i /C j	Sens X i	X 1	X 2	X 3	Y 1	Q min
	X 3							6/1=6
Y 1	M						8/2=4
Z(X) = 8M	2M-3	M-2			Linie index
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-M+1,5	Linie index

Valorile negative rezultate ale coeficienților din linia de index X i indică optimitatea primului plan, în timp ce venitul minim este de 12 mii de ruble.

Este asigurată numai de producția produsului A (produsul B nu este produs), materiile prime nu sunt utilizate în totalitate (restul X 3 = 2t), în timp ce condiția principală este îndeplinită - muncitorii sunt angajați pe deplin în producție.

Prelegerea nr. 11

Subiect: Problemă de transport închis

1. Formularea matematică a închis problema de transport. Definiție cantitatea necesară necunoscut.

2. Etapele stabilirii unui plan de rezolvare a unei probleme de transport.

Metoda simplex

1. Ideea metodei simplex

Sa luam in considerare metoda universala soluții la problema canonică LP.

cunoscut sub numele de metoda simplex.

După cum a fost stabilit în capitolul 2, setul de planuri pentru o problemă canonică este o mulțime poliedrică convexă cu un număr finit de puncte de colț. Și dacă această problemă are o soluție optimă, atunci se realizează cel puțin într-un punct de colț.

Orice punct de colț este asociat cu un plan de bază al problemei, în care variabilele sunt egale cu zero, iar variabilele rămase corespund coloanelor liniar independente ale matricei de condiții. Aceste coloane liniar independente formează o matrice de bază non-singulară.

Iterarea peste toate punctele de colț este costisitoare din punct de vedere computațional și, prin urmare, ineficientă. În 1944, J. Dantzig a propus o procedură ordonată de enumerare a punctelor de colț, în care este suficient să examinăm doar o mică parte a acestora pentru a găsi soluția optimă. Această procedură se numește metoda simplex.

J. Danzig a propus înlocuirea unui singur vector în matricea de bază atunci când se trece de la un punct extrem la altul. Aceasta înseamnă că în timpul unei astfel de tranziții trebuie să excludem una dintre variabilele de bază - să o facem nebază ( egal cu zero), iar în locul ei introduceți o nouă variabilă dintre cele nebază (zero) - faceți-o de bază (pozitivă).

Se pare că din punct de vedere geometric, o astfel de înlocuire duce la o tranziție de la un punct de colț la unul adiacent, conectat la punctul anterior printr-o margine comună.

Dintre toate punctele învecinate, este selectat cel la care funcția obiectiv crește cel mai mult. Deoarece numărul de puncte de colț este finit, printr-un număr finit de tranziții vârful cu cea mai mare valoare funcția obiectivă, sau nelimitarea funcției obiectiv va fi stabilită pe un set nelimitat de planuri.

Schema generala Metoda simplex constă din următorii pași de bază.

· 0 pas. Determinarea bazei inițiale și a punctului de colț inițial corespunzător (linia de bază).

· 1 pas. Verificarea planului de referință actual pentru optimitate. Dacă criteriul de optimitate este îndeplinit, atunci planul este optim și soluția este completă. In caz contrar treceți la pasul 2.

· Pasul 2. Găsirea variabilei introduse în cele de bază. (Din condiția creșterii funcției obiective).

· Pasul 3. Găsirea unei variabile excluse din variabilele de bază (Din condiția păstrării constrângerilor problemei).

· Pasul 4. Găsirea coordonatelor noii linii de bază (punctul de colț adiacent). Treceți la pasul 1.

Pașii repetați 1-4 formează o iterație a metodei simplex.

Din această diagramă rezultă că, în primul rând, pentru a începe metoda simplex, trebuie să aveți un fel de punct de colț - un plan de bază inițial și, în al doilea rând, trebuie să puteți examina punctul de colț curent pentru optimitate fără a calcula toate adiacente. vârfuri. Aceste probleme sunt ușor de rezolvat dacă problema LP canonică are un anumit tip special.

Definiție. Vom spune că problema canonică LP are o „formă preferată” dacă

1.partea dreaptă a ecuațiilor, .

Matricea de condiții conține o submatrice unitară de dimensiune

Cu alte cuvinte, în orice ecuație există o variabilă cu un coeficient egal cu unu, lipsă din celelalte ecuații. Condiția 1 nu este oneroasă, deoarece în cazul unei părți drepte negative a unei ecuații, este suficient să o înmulțiți cu (-1). Într-o problemă de tip preferențial, găsirea liniei de bază inițiale este foarte simplă.

Exemplu .

Matricea de condiții și vectorul părților din dreapta ale constrângerilor au forma

O matrice de bază este imediat evidentă: cu vectori unitari

În consecință, sunt variabile de bază, iar x2, x4 sunt nebaze. Presupunând x2=x4 =0 în sistemul de ecuații, găsim imediat x1 =10, x3 =20, x5 =8. Vedem că valorile variabilelor de bază sunt egale cu părțile din dreapta ale constrângerilor. De aici este clară cerința ca părțile din dreapta ale lui bi să fie pozitive.

În viitor, vom combina variabilele de bază într-un vector XB.

Astfel, în problema canonicaÎn forma preferată, submatricea unitară AB =E este luată ca matrice de bază inițială, iar variabilele de bază corespunzătoare sunt egale cu părțile din dreapta ale constrângerilor: xB =b.

. Cea mai simplă implementare metoda simplex

Cea mai simplă implementare a metodei simplex („metoda C simplă”) este aplicată problemei canonice LP, care are o „formă preferată”. Fără pierderea generalității, vom presupune că submatricea de identitate este conținută în primele m coloane. Atunci problema canonică va fi scrisă după cum urmează

f(x) = c 1X 1+c 2X 2+… + c m X m +c m+1 X m+1 +… + c n X n ??max(3,1)x 1+ a 1m+1 X m+1 + … + a 1n X n = b 1(3.2)x 2+ a 2m+1 X m+1 + … + a 2n X n = b 2………………………………………………………….X m + a mm+1 X m+1 + … + a mn X n = b m X j ³ 0, j=1,2,…, n.(3.3)

Matricea de condiții

conține o submatrice unitară de dimensiunea m x m în primele m coloane, deci AB =(A1, A2,…, Am)=E.

Etapele de bază ale metodei simplex (teorie)

Deoarece matricea de bază a unității se află în primele m coloane ale matricei de condiții, primele m coordonate ale planului de bază inițial sunt de bază, iar ultimele n - m coordonate sunt nebaze, adică egale cu zero:

o = (x1, x2,…, xm, 0,…, 0).

Inlocuind coordonatele punctului xo in restrictiile (3.2) si tinand cont ca m+1 =... = xn = 0, obtinem: x1 = b1, x2 = b2,..., xm = bm, ca este, xoB = b.

Deci planul de bază inițial arată astfel:

xo = (b1,…, bm, 0,…, 0),

unde сБ = (с1,…, сm) este un vector compus din coeficienții funcției obiectiv pentru variabilele de bază.

1 pas.

Din sistemul de constrângeri (3.2), exprimăm variabilele de bază în termeni de variabile nebazice:

X 1= b 1 - A 1m+1 X m+1 - ... - A 1n X n, X 2= b 2- A 2m+1 X m+1 - ... - A 2n X n, ………………………………………… X m = b m - A mm+1 X m+1 - ... - amn X n, (3.4)

Să substituim aceste expresii în funcția obiectiv (3.1).

f(x)=c 1(b 1- A 1m+1 X m+1 - ... - A 1n X n) +c 2(b 2- A 2m+1 X m+1 - ... - a2n X n ) +

………………………………………………..

C m (b m - A mm+1 X m+1 - ... - A mn X n ) + c m+1 X m+1 +… +cn X n .

Să grupăm termenii cu aceleași variabile non-bazice:

f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1).xm+1 - …-

- (c 1 A 1n +c 2 A 2n + … + c m A mn -c n). X n. (3.5)

Rețineți că expresiile din parantezele poate fi scris sub forma

c 1 A 1m+1 +c 2 A 2m+1 + … + c m A mm+1 -c m+1 = < cB , A m+1 > - c m+1 = D m+1 ,

…………………………………………………………………………………………………………………………1 A 1n +c 2 A 2n + … + c m A mn -c n= < cB , A n > - c n= D n ,

unde cu B = (cu 1,…, Cu m ) este un vector compus din coeficienții funcției obiectiv pentru variabilele de bază, A m+1 ,…, A n - coloane ale matricei de condiţii A pentru variabilele nebazice x m+1,…, x n .

Expresii

D j = < сB , A j > - cj , j = m+1,…, n,(3.6)

sunt numite diferențe simplex sau estimări de bază simplex.

Ținând cont de (3.6), formula (3.5) pentru funcția obiectiv poate fi rescrisă sub forma

Această formulă ne permite să obținem un semn al optimității planului de bază. Dacă toate estimările simplex cu numere nebaze D j ³ 0, atunci planul de bază curent este optim.

Într-adevăr, dacă cel puțin o estimare, de exemplu, ?k, este strict negativă, atunci dând variabilei nebazice corespunzătoare xk o valoare pozitivă și stabilind variabilele nebazice rămase ale planului x egale cu zero, obținem

f(x) = f(x o ) - D k X k =f(x o ) + | D k | X k > f(x o ),(3.7)

adică în acest caz planul x o poate fi îmbunătățit.

Este ușor de verificat că estimările simplex corespunzătoare coloanelor de bază de unitate sunt întotdeauna egale cu 0.

Pasul 2. Găsirea variabilei introduse în variabilele de bază.

După cum rezultă din formula (3.7), funcția obiectiv poate fi mărită prin introducerea unei variabile nebază x în variabilele de bază (făcând-o pozitivă) j , care corespunde unui rating negativ? j < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную хLa cu cea mai mare estimare negativă absolută, adică una pentru care

unde D j =< CБ, Aj >- cj, j = m+1,…, n (număr de variabile nebazice).

În acest fel obținem plan nou

x1 = (x1,…, xm,0,…, xk,…, 0,…, 0).

Dar x1 este un plan non-bazic, deoarece numărul de coordonate pozitive este egal cu m+1, numărul de coordonate zero este egal cu n - m -1.

Pentru a obține un nou punct de colț, să setăm una dintre variabilele de bază la zero, adică eliminăm o variabilă din cele de bază.

Pasul 3.

Să substituim coordonatele punctului x1 în condițiile (3.4) și să ținem cont de faptul că variabilele xj trebuie să fie nenegative

X 1= b 1- A 1k X k ³ 0 x 2= b 2- A 2k X k ³ 0 …………………………. X m = b m - A mk xk ³ 0(3.8)

Din formula (3.7) este clar că cu cât valoarea lui x este mai mare La > 0, cu atât funcția obiectiv crește mai mult. Să încercăm să găsim valoarea maximă a lui x La , fără a încălca constrângerile problemei și îndeplinirea condițiilor de non-negativitate (3.8).

Inegalitățile (3.8) pot fi rescrise ca

A 1k X k £ b 1 A 2k X k £ b 2 ……………… A mk X k £ b m (3.9)

La rezolvarea sistemului de inegalități (3.9), sunt posibile două cazuri: dintre coeficienții pentru x La nu pozitiv: a ik £ 0, i=1,2,…, m. Din moment ce b i > 0, atunci inegalitățile (3.9) sunt satisfăcute pentru orice valoare arbitrar de mare a lui x La. Aceasta sugerează că funcția obiectiv nu este limitată la setul de planuri (max f(x) ® ¥ ) și, prin urmare, nu există o soluție la problema LP.) printre coeficienții pentru x La sunt pozitive a ik > 0. Rezolvând sistemul de inegalități (3.9) obținem:

X La £ b i /A ik , pentru tot i pentru care aik > 0.(3.10)

Cea mai mare valoare x La , care satisface toate restricțiile (3.10), este egal cu cel mai mic dintre rapoartele din partea dreaptă a acestor inegalități

X La =min(b i /A ik ) pentru toate i: aik > 0.

Fie atins minimul la i = r, adică x La ? b r /A rk . Aceasta înseamnă că variabila de bază x r în condițiile (3.8) dispare.

X r = b r - A rk X k = b r - A rk (b r /ark ) = 0, 1 ??r ??m.

Variabila x r excluse din bază. Prin urmare, am primit noua linie variabile de bază și nebaze, care diferă de cea inițială într-o coordonată de bază și una nebază.

Pasul 4

Noua linie de bază va arăta ca

1= (x 1, X 2,…, 0,…, x m , 0,…, xk ,0,…, 0),

unde în locul x r costă zero și x La > 0.acel plan de bază corespunde unei noi matrice de bază:

Pentru a găsi coordonatele unui nou punct de colț x1, problema canonică LP se reduce la o nouă formă preferată, adică la o astfel de formă încât matricea devine identitate (= E). Pentru a face acest lucru, coloana Ak trebuie convertită într-o reprezentare unitară,

R-a linie,

în care coeficient = 1, iar toate celelalte elemente =0, i ??r. Acest lucru poate fi realizat folosind operații elementare asupra ecuațiilor sistemului. Soluția se termină când pentru un moment dat toate estimările Dj ³ 0.

3. Implementarea metodei simplex folosind un exemplu

Să demonstrăm aplicarea metodei simplex folosind un exemplu din capitolul 2.

Luați în considerare problema LP canonică

f(x) = x 1+ 2x 2 +0x 3 +0 x 4max(3,11)-x 1+ 2x 2+x 3= 4,(3,12)3 x 1 +2x 2+x 4= 12,(3,13)x j? 0, j = 1,2,3,4.(3,14)

Matricea de condiții A = (A 1, A 2, A 3, A 4), Unde

Vector țintă c =(c1, c2, c3, c4)=(1, 2, 0, 0); vector al laturilor drepte b=(b1, b2) = (4, 12).

0 pas. Găsirea punctului de pornire al colțului (linia de bază).

Problema are o formă preferabilă, deoarece părțile din dreapta ecuațiilor sunt pozitive, iar coloanele matricei condițiilor A3, A4 formează o submatrice unitară. Aceasta înseamnă matricea de bază inițială = (A3, A4); x3 și x4 sunt variabile de bază, x1 și x2 sunt variabile nebazice, cB = (c3, c4) = (0, 0).

Linia de bază inițială arată ca

x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.

1 pas. Verificarea planului de bază pentru optimitate.

Să calculăm estimări simplex pentru variabile nebazice folosind formula (3.6)

D1 =< cБ, A1 >- c1 = 0 ·(-1) + 0 ·3 - 1 = -1.

D2 =< cБ, A2 >- c2 = 0 · 2 + 0 · 2 - 2 = -2.

Deoarece estimările sunt negative, planul xo nu este optim. Vom căuta o nouă linie de bază (punct de colț adiacent) cu o valoare mai mare a funcției obiectiv.

Pasul 2. Găsirea variabilei introduse în bază.

Funcția obiectiv poate fi mărită dacă una dintre variabilele nebaze x1 sau x2 este inclusă în variabilele de bază (facute pozitive), deoarece ambele estimări Dj< 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.

Pasul 3. Definiția unei variabile derivate din bază.

După introducerea variabilei x2 în bază, noul plan va avea forma1 = (0, x2, x3, x4).

Acest plan nu este unul de bază, deoarece conține doar o coordonată zero, ceea ce înseamnă că este necesar să faceți una dintre variabilele x3 sau x4 zero (excludeți din bază).

Să substituim coordonatele planului x1 = (0, x2, x3, x4) în constrângerile problemei. Primim

Să exprimăm de aici variabilele de bază x3 și x4 prin variabila x2 introdusă în bază.

X 3= 4 - 2x 2,(3,15)x 4= 12 - 2x2 .(3.16)

Deci variabilele x 3și x 4 trebuie să fie nenegativ, obținem un sistem de inegalități

4 - 2x 2 ³ 0 ,(3.17)12 - 2x 2 ³ 0 .(3.18)

Cum mai multă valoare X 2, cu atât funcția obiectiv crește mai mult. Să găsim valoarea maximă a noii variabile de bază care nu încalcă constrângerile problemei, adică să satisfacă condițiile (3.17), (3.18).

Să rescriem inegalitățile în formă

x2 £ 4,

x2 £ 12,

unde este valoarea maximă a lui x 2= min (4/2, 12/2) = 2. Înlocuind această valoare în expresiile (3.15), (3.16) pentru x 3și x 4, obținem x 3= 0. Prin urmare x 3 derivate de la bază .

Pasul 4Determinarea coordonatelor noii linii de bază.

Noua linie de bază (punctul de colț adiacent) este:

X 1= (0, x2, 0.x 4).

Baza acestui punct constă din coloanele A2 și A4, deci = (A2, A4). Rețineți că această bază nu este unitară, deoarece vectorul A2 = (2, 2) și, prin urmare, problema (3.11) - (3.14) nu are o formă preferată față de noua bază. Să transformăm condițiile problemei (3.12), (3.13) astfel încât să ia forma preferată față de noile variabile de bază x2, x4, adică astfel încât variabila x2 să fie inclusă în prima ecuație cu un coeficient egal cu unu și nu este prezent în a doua ecuație. Să rescriem ecuațiile problemei

x1+ 2x2+ x3 = 4, (p1)

x1 +2x2 + x4 = 12. (p2)

Să împărțim prima ecuație la coeficientul lui x2. Obținem o nouă ecuație = p1 / 2, echivalentă cu cea inițială

1/2 x1+ x2+ 1/2 x3 = 2. ()

Folosim această ecuație, pe care o numim rezolvare, pentru a elimina variabila x2 din a doua ecuație. Pentru a face acest lucru, trebuie să înmulțiți ecuația cu 2 și să o scădeți din p2. Obținem ecuația = p2 - 2 = p2 - p1.

x1 - x3 + x4 = 8. ()

Drept urmare, am primit o nouă reprezentare „preferată”. problema initiala(3.11) - (3.14) cu privire la noile variabile de bază x2, x4:

f(x) = x1+ 2x2 + 0 x3 + 0 x4® max

1/2 x1+ x2+ 1/2 x3 = 2. ()

x1 - x3 + x4 = 8. ()

xj ³ 0, j = 1,2,3,4.

Înlocuind aici reprezentarea noului plan de bază x1 = (0, x2,0, x4), găsim imediat coordonatele acestuia, deoarece valorile variabilelor de bază sunt egale cu laturile drepte ale ecuațiilor

x1 = (0,2,0,8); f(x1)=4.

Aceasta completează prima iterație metoda simplex. În continuare, procesul de rezolvare a problemei continuă de la pasul 1, care constă în verificarea optimității planului găsit. Soluția se termină atunci când toate estimările simplex ale planului de bază actual se dovedesc a fi nenegative.

Nu vom efectua a doua iterație conform schemei primei, deoarece este mai convenabil să efectuați toate calculele metodei simplex în formă tabelară.

variabilă simplex programare canonică

Literatură

1. Econometrie: Manual / Ed. I.I. Eliseeva. - M.: Finanţe şi Statistică, 2002. - 344 p.: ill.

Atelier de econometrie: Proc. indemnizatie / I.I. Eliseeva, S.V. Kurysheva, N.M. Gordeenko și alții; Ed. I.I. Eliseeva. - M.: Finanţe şi Statistică, 2002. - 192 p.: ill.

Kremer N.Sh., Putko B.A. Econometrie: manual pentru universități. - M.: UNITATEA-DANA, 2002. - 311 p.

Magnus Y.R., Katyshev P.K., Peresetsky A.A. Econometrie. Curs de început: manual. - M.: Delo, 2001. - 400 p.

Katyshev P.K., Magnus Y.R., Peresetsky A.A. Culegere de probleme pt curs initial econometrie. - Ed. a III-a, rev. - M.: Delo, 2003. - 208 p.

Dougherty K. Introducere în econometrie. - M.: Finanțe și Statistică, 1999.

Johnston J. Metode econometrice. - M.: Statistică, 1980.

Kane E. Statistică economică și econometrie. Introducere în analiza economică cantitativă. Vol. 1. - M.: Statistică, 1977.

Lange O. Introducere în econometrie / Trad. din poloneză - M.: Progres, 1964.

Lizer S. Metode şi probleme econometrice. - M.: Statistică, 1971.

Malenvo E. metode statistice econometrie. - M.: Statistică, 1976.

Tintner G. Introducere în econometrie. - M.: Finanțe și Statistică, 1965.

Ayvazyan S.A., Mkhitaryan V.S. Statistici aplicateși fundamentele econometriei: un manual pentru universități. - M.: UNITATEA, 1998.

Ventzel E.S. Teoria probabilității: manual pentru universități. - Ed. a VI-a. - M.: Mai sus. scoala, 1999.

Anterior, s-a arătat că dacă o problemă de programare liniară are o soluție optimă, atunci una dintre soluțiile optime este o soluție de bază admisibilă a sistemului său de constrângeri, care corespunde unui anumit punct de colț al poliedrului soluțiilor admisibile ale sistemului.
Sa arătat cum se găsește această soluție optimă folosind o căutare finită a soluțiilor de bază ale sistemului de constrângeri ale problemei. Cu toate acestea, pe măsură ce dimensiunea n a sistemului de constrângere a problemei crește, volumul calculelor pentru rezolvarea problemei prin metoda enumerarii exhaustive a soluțiilor de bază crește exponențial și devine inadecvat în practică.

Este posibil să se organizeze o enumerare numai a soluțiilor de bază fezabile și să se reducă brusc numărul de soluții enumerate dacă fiecare soluție de bază admisibilă ulterioară este aleasă astfel încât valoarea corespunzătoare a funcției obiectiv să se îmbunătățească sau cel puțin să nu se deterioreze. Această abordare vă permite să reduceți numărul de pași atunci când găsiți soluția de bază optimă. Să explicăm această idee grafic.

Fie poligonul ABCDEFGH să reprezinte mulțimea soluțiilor fezabile ale PLP cu două variabile și fie vectorul N gradient al funcției obiectiv.

Trebuie să găsim punctul acestui poligon în care funcția obiectiv ia cea mai mică valoare.
Să fie determinată soluția de bază fezabilă inițială a problemei corespunzătoare punctului de colț B.
Cu o căutare completă a tuturor soluțiilor de bază fezabile, va fi necesar să se examineze opt astfel de soluții corespunzătoare celor opt puncte de colț ale poligonului.
Totuși, din figură reiese clar că, ținând cont de direcția gradientului N, este mai rentabil să mergem la vârful vecin C, apoi la vârful vecin D, care corespunde soluției de bază optime a problemei.
Astfel, în loc de opt soluții, vor trebui luate în considerare doar trei soluții de bază fezabile.

Ideea îmbunătățirii secvențiale a soluției stă la baza metodei universale de rezolvare a problemelor de programare liniară - metoda simplex.

Sensul geometric al metodei simplex este că se efectuează o tranziție secvențială de la un vârf al poliedrului de soluții fezabile la problemă la cel învecinat, în care funcția obiectiv ia o valoare nu mai rea decât la vârful anterior. Această tranziție continuă până când se găsește o soluție optimă sau se descoperă că problema nu are una.

Metoda simplex și numele ei au fost propuse pentru prima dată de matematicianul american John Dantzig în 1947, deși ideile metodei au fost publicate de matematicianul rus L.V. Kantorovich încă din 1939, în articolul „Metode matematice de organizare și planificare a producției”.

Metoda simplex constă din trei elemente principale:

determinarea unei soluții de bază fezabile inițiale la problemă;
reguli pentru tranziția la următoarea soluție de bază neproasta admisibilă;
verificarea optimității soluției găsite.
Metoda simplex este aplicată unei probleme de programare liniară scrisă în formă canonică.

Transformări simplex ale unui sistem de ecuații liniare

Să considerăm ZLP-ul în formă canonică. Să fie dat un sistem de ecuații liniare:
Trebuie să găsim o soluție nenegativă pentru acest sistem care să minimizeze funcția liniară
Să notăm – matricea sistemului de ecuații (1),
– matrice extinsă a acestui sistem.

Vom lua în considerare cazul când rândurile matricelor A și B sunt egale: , i.e. când sistemul (1) are un număr infinit de soluții. Sarcina noastră este să aflăm dacă există soluții optime la problemă în acest caz și cum să le găsim.

Pentru certitudine, presupunem că primele r coloane ale matricei A sunt liniar independente, apoi sistemul (1) poate fi transformat, folosind metoda eliminării gaussiene, la forma:
Acest sistem este echivalent cu sistemul de ecuații (1). Coloane de cote
formează baza sistemului de coloane al matricei sistemului (2) și, prin urmare, variabilele sunt de bază, iar mulțimea este o mulțime de bază.
Pentru concizie, vom numi și setul de variabile bază, adică baza corespunzătoare a coloanelor de coeficienți. Variabilele rămase sunt libere.

Să exprimăm variabilele de bază din sistemul (3) în termeni de cele libere și să obținem sistemul (4):

(4)
Se obișnuiește să spunem că (4) este o soluție generală a sistemului de ecuații (1). Prin atribuirea de valori zero variabilelor libere, determinăm valorile variabilelor de bază și construim o soluție de bază corespunzătoare setului de bază construit de variabile.
Deci, soluția de bază a sistemului (1).
În cele ce urmează se va arăta că dacă sistemul (1) are soluții admisibile, atunci el poate fi transformat în forma (3) astfel încât condiția (5) să fie îndeplinită
Prin urmare, vom presupune că condiția (5) este îndeplinită. Atunci soluția de bază este o soluție de bază fezabilă.

Folosind egalitățile (4), putem exprima funcția f în termeni de variabile libere: (6) Acum putem calcula valoarea funcției f corespunzătoare soluției de bază

Implementând ideea metodei simplex, vom învăța să trecem de la o soluție de bază fezabilă la alta. Pentru a face acest lucru, una dintre variabilele de bază xi este eliminată din bază și înlocuită cu o variabilă liberă xj.
Cu această modificare a bazei, sistemul de ecuații (4) și funcția liniară (6) sunt transformate. Pentru a face acest lucru, a i-a ecuație a sistemului (3) trebuie rezolvată cu privire la xj.
Ecuația rezultată este:
Înlocuind în loc de xj expresia sa din (7) în ecuațiile rămase ale sistemului (4) și în funcția (6), obținem un nou sistem echivalent cu sistemul (1), care va fi rezolvat în raport cu noua bază.

Coeficientul aij, care indică faptul că în baza xi este înlocuit cu o variabilă liberă xj, se numește elementul de rezoluție al tabelului simplex. Din egalitatea (7) rezultă că

Deoarece noua soluție de bază trebuie să fie admisibilă (nenegativă),
atunci condiția trebuie îndeplinită, ceea ce înseamnă . Cu alte cuvinte, elementul de rezoluție aij (xi este o variabilă liberă) din coloana j trebuie să fie ales pozitiv. Vom numi transformarea descrisă simplex dacă elementul de rezolvare aij este ales după următoarea regulă:
1. Element aij alegeți din a j-a coloană care conține elemente pozitive.
2. Dacă în această coloană sunt mai multe elemente pozitive, atunci vom compune raporturile termenilor liberi bk la coeficienții akj>0.
Dintre toate rapoartele, îl alegem pe cel mai mic. Lăsați-l să fie :
(8)
Alegem numitorul acestei fracții ca element de rezolvare. Dacă mai multe dintre aceste rapoarte sunt minime (egale), atunci vom alege oricare dintre acești numitori.

Teorema. Dacă în sistemul de ecuații liniare (4) toți termenii liberi sunt nenegativi, atunci după aplicarea transformării simplex ei vor rămâne nenegativi.

Dovada. Să notăm noii termeni liberi după transformarea simplex din (4) prin
Apoi la
Dacă akj>0, atunci din (8) rezultă că
Dacă akj
Dacă akj =0, atunci
Consecinţă. Folosind o transformare simplex, puteți trece de la o soluție de bază admisibilă a ZLP la o altă soluție de bază admisibilă a acestei probleme.

Să considerăm o metodă universală pentru rezolvarea problemei de programare liniară canonică

Cu n variabile şi m constrângeri de egalitate, cunoscute ca metoda simplex.

Setul de planuri pentru o problemă canonică este o mulțime poliedrică convexă cu un număr finit de puncte de colț. Și dacă această problemă are o soluție optimă, atunci se realizează cel puțin într-un punct de colț.

Iterarea peste toate punctele de colț este costisitoare din punct de vedere computațional și, prin urmare, ineficientă. În 1947, J. Danzig a propus o procedură ordonată de enumerare a punctelor de colț, în care este suficient să examinăm doar o mică parte a acestora pentru a găsi soluția optimă. Această procedură se numește metoda simplex.

J. Danzig a propus înlocuirea unui singur vector în matricea de bază atunci când se trece de la un punct extrem la altul. Aceasta înseamnă că în timpul unei astfel de tranziții trebuie să excludem una dintre variabilele de bază - să o facem nebază (egale cu zero), iar în locul ei să introducem o nouă variabilă dintre cele nebazice (zero) - să o facem de bază (pozitivă). ).

Se pare că din punct de vedere geometric, o astfel de înlocuire duce la o tranziție de la un punct de colț la unul adiacent, conectat la punctul anterior printr-o margine comună.

Dintre toate punctele învecinate, este selectat cel la care funcția obiectiv crește cel mai mult. Întrucât numărul de puncte de colț este finit, printr-un număr finit de tranziții se va găsi vârful cu cea mai mare valoare a funcției obiectiv, sau se va stabili nelimitarea funcției obiectiv pe un set nelimitat de planuri.

Schema generală a metodei simplex constă din următorii pași principali.

· pasul 0. Determinarea bazei inițiale și a punctului de colț inițial corespunzător (linia de bază).

· pasul 1. Verificarea liniei de bază curente pentru optimitate . Dacă criteriul de optimitate este îndeplinit, Acea planul este optim și soluția este completă. In caz contrar treceți la pasul 2.

· pasul 2. Găsirea variabilei introduse în cele de bază. (Din condiția creșterii funcției obiective).

· pasul 3. Găsirea unei variabile excluse din variabilele de bază (Din condiția păstrării constrângerilor problemei).

· Etapa 4 . Găsirea coordonatelor noii linii de bază (punctul de colț adiacent). Treceți la pasul 1.

Pașii repetați 1-4 formează o iterație a metodei simplex.

Definiție. Vom spune că problema canonică LP are o „formă preferată” dacă

1. partea dreaptă a ecuațiilor, .

2. matricea de condiții conține o submatrice unitară de dimensiune

Cu alte cuvinte, în orice ecuație există o variabilă cu un coeficient egal cu unul, care este absentă în celelalte ecuații. Prima condiție nu este împovărătoare, deoarece în cazul unei părți drepte negative a unei ecuații, este suficient să o înmulțiți cu (-1). Într-o problemă de tip preferențial, găsirea liniei de bază inițiale este foarte simplă.

Exemplul 2.1.

Matricea de condiții Ași vectorul părților din dreapta ale constrângerilor b arată ca

și vectorul țintă c = (1, -3, 0, 4, 2).

O matrice de bază este imediat evidentă: cu vectori unitari de condiții.

Prin urmare, alegând ca variabile de bază X 1 , X 3 ,X 5 , și introducerea în sistemul de ecuații X 2 = x 4 = 0 (variabile non-bazice) , îl găsim imediat X 1 = 10,X 3 = 20,X 5 = 8, deci linia de bază inițială X 0 = (10, 0, 20, 0, 8). Vedem că valorile variabilelor de bază sunt egale cu părțile din dreapta ale constrângerilor. Din aceasta, este clar că părțile din dreapta trebuie să fie pozitive b i .

În viitor, vom combina variabilele de bază într-un vector X B.

Astfel, în problema canonică a formei preferate, submatricea de identitate este luată ca matrice de bază inițială A B = E, iar variabilele de bază corespunzătoare sunt egale cu părțile din dreapta ale constrângerilor:

X B = b.

Pentru un plan de bază de acest tip se poate formula un criteriu de optimitate suficient de simplu de testat. Să introducem cantitățile

? j = < с B , A j > - c j , j = 1,...,n,(2.1)

Unde Cu B- vector de coeficienţi ai funcţiei obiectiv pentru variabile de bază X B , A j -j- th coloana matricei de condiții, c j -j- al-lea coeficient al funcției obiectiv. Diferențele ? j se numesc diferenţe simplex sau estimări simplex.

Criteriul de optimizare pentru planul de bază. Dacă pentru un plan de bază cu o unitate matricea de bază toate estimările simplex sunt nenegative, atunci acest plan este optim.

Să aplicăm acest criteriu pentru a verifica optimitatea planului de bază X 0 = (10, 0, 20, 0, 8) din exemplul 2.1.

Întrucât în acest sens vectorul variabilelor de bază X B =(X 1 , X 3 ,X 5 ), Acea Cu B = (c 1 , c 3 ,c 5 ) = (1, 0, 2).

Prin urmare,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

De la evaluare ? 4 < 0, то базисный план X 0 nu optim. Rețineți că estimările simplex corespunzătoare variabilelor de bază sunt întotdeauna egale cu zero, deci este suficient să verificați doar estimările non-bazice.

Metoda simplex pentru rezolvarea problemelor de programare liniară. Rezumat: Metoda grafică și metoda simplex pentru rezolvarea problemelor de programare liniară

Anterior, s-a arătat că dacă o problemă de programare liniară are o soluție optimă, atunci una dintre soluțiile optime este o soluție de bază admisibilă a sistemului său de constrângeri, care corespunde unui anumit punct de colț al poliedrului soluțiilor admisibile ale sistemului.

Fie poligonul ABCDEFGH să reprezinte mulțimea soluțiilor fezabile ale PLP cu două variabile și fie vectorul N gradient al funcției obiectiv.

Trebuie să găsim punctul acestui poligon în care funcția obiectiv ia cea mai mică valoare.

Să fie determinată soluția de bază fezabilă inițială a problemei corespunzătoare punctului de colț B.

Cu o căutare completă a tuturor soluțiilor de bază fezabile, va fi necesar să se examineze opt astfel de soluții corespunzătoare celor opt puncte de colț ale poligonului.

Totuși, din figură reiese clar că, ținând cont de direcția gradientului N, este mai rentabil să mergem la vârful vecin C, apoi la vârful vecin D, care corespunde soluției de bază optime a problemei.

Astfel, în loc de opt soluții, vor trebui luate în considerare doar trei soluții de bază fezabile.

Ideea îmbunătățirii secvențiale a soluției stă la baza metodei universale de rezolvare a problemelor de programare liniară - metoda simplex.

Metoda simplex și numele ei au fost propuse pentru prima dată de matematicianul american John Dantzig în 1947, deși ideile metodei au fost publicate de matematicianul rus L.V. Kantorovich încă din 1939, în articolul „Metode matematice de organizare și planificare a producției”.

Metoda simplex constă din trei elemente principale:

determinarea unei soluții de bază fezabile inițiale la problemă;

reguli pentru tranziția la următoarea soluție de bază neproasta admisibilă;

verificarea optimității soluției găsite.

Metoda simplex este aplicată unei probleme de programare liniară scrisă în formă canonică.

Transformări simplex ale unui sistem de ecuații liniare

Să considerăm ZLP-ul în formă canonică. Să fie dat un sistem de ecuații liniare:

Trebuie să găsim o soluție nenegativă pentru acest sistem care să minimizeze funcția liniară

Să notăm – matricea sistemului de ecuații (1),

– matrice extinsă a acestui sistem.

Vom lua în considerare cazul când rândurile matricelor A și B sunt egale: , i.e. când sistemul (1) are un număr infinit de soluții. Sarcina noastră este să aflăm dacă există soluții optime la problemă în acest caz și cum să le găsim.

Pentru certitudine, presupunem că primele r coloane ale matricei A sunt liniar independente, apoi sistemul (1) poate fi transformat, folosind metoda eliminării gaussiene, la forma:

Acest sistem este echivalent cu sistemul de ecuații (1). Coloane de cote

formează baza sistemului de coloane al matricei sistemului (2) și, prin urmare, variabilele sunt de bază, iar mulțimea este o mulțime de bază.

Pentru concizie, vom numi și setul de variabile bază, adică baza corespunzătoare a coloanelor de coeficienți. Variabilele rămase sunt libere.

Să exprimăm variabilele de bază din sistemul (3) în termeni de cele libere și să obținem sistemul (4):

(4)

Se obișnuiește să spunem că (4) este o soluție generală a sistemului de ecuații (1). Prin atribuirea de valori zero variabilelor libere, determinăm valorile variabilelor de bază și construim o soluție de bază corespunzătoare setului de bază construit de variabile.

Deci, soluția de bază a sistemului (1).

În cele ce urmează se va arăta că dacă sistemul (1) are soluții admisibile, atunci el poate fi transformat în forma (3) astfel încât condiția (5) să fie îndeplinită

Prin urmare, vom presupune că condiția (5) este îndeplinită. Atunci soluția de bază este o soluție de bază fezabilă.

Folosind egalitățile (4), putem exprima funcția f în termeni de variabile libere: (6) Acum putem calcula valoarea funcției f corespunzătoare soluției de bază

Implementând ideea metodei simplex, vom învăța să trecem de la o soluție de bază fezabilă la alta. Pentru a face acest lucru, una dintre variabilele de bază xi este eliminată din bază și înlocuită cu o variabilă liberă xj.

Cu această modificare a bazei, sistemul de ecuații (4) și funcția liniară (6) sunt transformate. Pentru a face acest lucru, a i-a ecuație a sistemului (3) trebuie rezolvată cu privire la xj.

Ecuația rezultată este:

Înlocuind în loc de xj expresia sa din (7) în ecuațiile rămase ale sistemului (4) și în funcția (6), obținem un nou sistem echivalent cu sistemul (1), care va fi rezolvat în raport cu noua bază.

Coeficientul aij, care indică faptul că în baza xi este înlocuit cu o variabilă liberă xj, se numește elementul de rezoluție al tabelului simplex. Din egalitatea (7) rezultă că

Deoarece noua soluție de bază trebuie să fie admisibilă (nenegativă),

atunci condiția trebuie îndeplinită, ceea ce înseamnă . Cu alte cuvinte, elementul de rezoluție aij (xi este o variabilă liberă) din coloana j trebuie să fie ales pozitiv. Vom numi transformarea descrisă simplex dacă elementul de rezolvare aij este ales după următoarea regulă:

1. Element aij alegeți din a j-a coloană care conține elemente pozitive.

2. Dacă în această coloană sunt mai multe elemente pozitive, atunci vom compune raporturile termenilor liberi bk la coeficienții akj>0.

Dintre toate rapoartele, îl alegem pe cel mai mic. Lăsați-l să fie :

(8)

Alegem numitorul acestei fracții ca element de rezolvare. Dacă mai multe dintre aceste rapoarte sunt minime (egale), atunci vom alege oricare dintre acești numitori.

Teorema. Dacă în sistemul de ecuații liniare (4) toți termenii liberi sunt nenegativi, atunci după aplicarea transformării simplex ei vor rămâne nenegativi.

Dovada. Să notăm noii termeni liberi după transformarea simplex din (4) prin

Apoi la

Dacă akj>0, atunci din (8) rezultă că

Dacă akj

Dacă akj =0, atunci

Consecinţă. Folosind o transformare simplex, puteți trece de la o soluție de bază admisibilă a ZLP la o altă soluție de bază admisibilă a acestei probleme.