Metoda simplex pentru rezolvarea LLP. Ideea generală a metodei simplex. Metoda simplex pentru rezolvarea problemelor de programare liniară

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ă duce la formă matriceală. Apoi descrierea matriceală a problemei duce 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 circuit de calcul Metoda simplex implementează un proces ordonat în care, pornind de la un punct de colț admis inițial (de obicei originea), se fac tranziții succesive de la un punct extrem admis la altul până la găsirea unui punct corespunzător soluției optime.

Algoritmul metodei simplex

1. Aducem sistemul de restricții în 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 validelor solutii de baza Problemă de programare liniară (nedegenerată) atunci când este rezolvată folosind metoda simplex. Este format dintr-o matrice de coeficienți ai unui sistem de ecuații de programare liniară redusă la forma 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. estimă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 de ghidare părăsește baza.

6. Găsiți 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 satisface 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 rezolvarea problemelor 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 pentru resurse limitate 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 din fiecare grupă, prezentată sub forma unei 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 o semnificație fizică simplă - aceasta este rest resursă specifică din depozit pentru un plan de producție dat, 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	Qmin
	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 principala (liberă) la cea de bază (de fapt, este selectat un grup de produse ale cărui vânzări aduc 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 principală și variabila Xi, care la următorul pas (iterație) va părăsi baza și va deveni liberă.

3) Tranziția 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 . Noi elemente ale acestui plan sunt găsite conform regulii dreptunghiului

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

Planul rezultat este evaluat folosind coeficienții liniei indice: 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. 20 de mii de ruble au fost alocate pentru achiziționarea de echipamente pentru locul de producție. 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, care necesită o suprafață de 12 mp și produc 3 mii de unități (preț 2.000 de ruble). Ce plan optim achizitia de furnizare de echipamente performanță maximă complot?

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

Productivitatea site-ului ( funcție obiectivă): Z(X) =6Х 1 +3Х 2.

Principalele restricții 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 plan de referință (0-lea): 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	Qmin
	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. Selectăm a 2-a coloană drept primară și, pe baza valorii minime Q min = 5, determinăm rândul de început 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).

Prelegerea nr. 10

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

Metoda soluției simplex se bazează pe introducerea de variabile suplimentare (de bază) care fac posibilă formarea matrice de identitate. 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ă se obțină 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 dă metoda simplex O flexibilitate mai mare ș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:

1Х 1 + 1Х 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	Qmin
	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 variabilei artificiale Y 1 din bază 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 mai înainte, este selectată de cel mai mare coeficient pozitiv în valoare absolută 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	Qmin
	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. Determinarea numărului necesar de necunoscute.

2. Etapele determinării unui plan de rezolvare a unei probleme de transport.

Sa luam in considerare metoda universala rezolvarea problemei de programare liniară canonică

Cu n variabile şi m constrângeri de egalitate, cunoscute sub numele de 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ț.

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 liniar coloane independente matrice de condiție. 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 1947, J. Dantzig a propus o procedură ordonată de enumerare a punctelor de colț, în care să se găsească soluție optimă este suficient să examinăm doar o mică parte din ele. 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 dovedește că, din punct de vedere geometric, o astfel de înlocuire duce la o tranziție de la un punct de colț la unul adiacent (învecinat) asociat cu punctul anterior 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 generala Metoda simplex constă din următorii pași de bază.

· 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.

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 canonică LP are o formă specială.

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 unu, lipsă din 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).

Un lucru este imediat evident matricea de bază: cu vectori unitari de conditii.

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 sunt numite diferențe simplex sau estimări simplex.

Criteriul de optimizare pentru planul de bază. Dacă pentru un plan de bază cu o matrice de bază unitară 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.

Găsirea planului optim. Această metodă este universală, permite rezolvarea problemelor de programare liniară de orice dimensiune într-o formulare generală. Cu toate acestea, această metodă necesită reducerea problemei inițiale la forma canonică.

Ideea principală a metodei simplex este de a trece de la un vârf al ODR la altul, astfel încât cu fiecare tranziție valoarea CF să scadă. Așa puteți ajunge de la orice vârf la cel optim și obțineți planul optim.

De exemplu: să fie cunoscut planul de referință X =(x1,x2,…,xm,0,0,…,0) și sistemul asociat de vectori liniar independenți: A1,A2,…,Am, atunci pentru acest plan de referință puteți calcula valoarea CF Z=(c1x1+c2x2+…+cmxm) și scrieți condițiile de limitare în următoarea formă x1A1+x2A2+…+xmAm=b

Deoarece vectorii A1, A2,…, Am sunt liniar independenți, orice vector Aj poate fi extins în acești vectori: Aj=x1jA1+x2jA2+…+xmjAm (*) Să introducem valorile Zj Zj=x1jc1+x2jc2+…+ xmjcm, unde xij este coeficientul corespunzător lui Ai în vectorul de expansiune Aj prin vectori de bază

Teorema 1: Îmbunătățirea planului de referință

Dacă pentru un indice j este îndeplinită condiția Zj-Cj>0, atunci valoarea CF poate fi redusă și:

· dacă CF este limitat de jos, atunci este posibil să construiți un plan de referință cu o valoare CF mai mică, aceeași precedentă

· dacă TF nu este limitat de jos, atunci este posibil să se construiască un plan corespunzător unei valori arbitrar mici a TF

Teorema 2: criteriul de optimitate pentru planul de referință

Dacă pentru un indice j din planul de referință inegalitatea Zj-Cj0. Fie ca acest minim să fie atins pentru vectorul Ak, atunci acest vector trebuie să fie derivat din bază. Linia corespunzătoare acestui vector se numește ghid și se notează „à”.

4. După definirea ghidajelor de coloane și rânduri, completați un nou tabel simplex. Într-un astfel de tabel, Ai va apărea în locul liniei de ghidare. Umplere masa nouaîncepe cu o linie de ghidare. Ca componentă a planului de referință, acolo este scrisă valoarea Ө0 X'l=Ө0=Xk/Xkl, elementele rămase ale acestei linii sunt determinate de formula X'lj X'lj=Xkj/Xkl unde Xkl este elementul situat la intersecția ghidajelor de rând și coloane, în special pe acesta sunt împărțite toate fostele elemente ale liniei de ghidare, iar o unitate apare automat în locul fostului element Xkl. Regula generala pentru a recalcula linia de ghidare, o puteți scrie astfel: Ak (element nou al liniei de ghidare) = (element vechi al liniei de ghidare)/(element care se află la intersecția coloanei și rândului de ghidare)

5. Toate elementele rândurilor rămase ale tabelului sunt recalculate, inclusiv cele suplimentare linia de jos. Recalcularea se efectuează conform formulelor

· pentru componentele planului de referință X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· pentru componentele extinse pe baza X’ij=Xij-(Xkj/Xkl)*Xil

· pentru linia suplimentară Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Toate aceste formule sunt construite după o singură regulă:

(e-mail nou)=(e-mail vechi)-(e-mail nou cu direcția rândului)*(e-mail cu direcția coloanei în rândul corespunzător)

După completarea noului tabel simplex, are loc trecerea la a doua etapă a algoritmului.

Metode de bază naturală și artificială. Concepte de bază, algoritmi de metode.

Pentru majoritatea problemelor de programare liniară, apar dificultăți în rezolvarea lor asociate cu determinarea planului de referință inițial și a tabelului inițial simplex de la care încep toate iterațiile. Acest lucru se datorează faptului că în probleme reale printre vectorii Ai nu există vectori care să conțină o singură componentă diferită de zero, adică vectori de forma (0,0,0,…,0,1,0,…,0) sau numărul lor nu este suficient pentru a forma o bază . Adică nu este posibil să se formeze o bază naturală.

Metoda bazei artificiale se bazează pe introducere artificialăîntr-un model matematic al problemei unor astfel de vectori.

Să fie dat ZLP canonic forme

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Apoi este convertit în formă

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

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

a1mx1+a2mx2+…+anmxn+xn+m=bm

Unde M este infinit numere mari. În problema rezultată, baza inițială este imediat vizibilă vectorii cu variabilele introduse artificial xn+1, xn+2,…, xn+m. Deoarece acești vectori vor avea forma: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Problema transformată este apoi rezolvată folosind algoritmul metodei simplex. Planul de referință inițial al problemei transformate are forma (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). Tabelul simplex original arată astfel:

Bază	coeficient CF	Plan	C1	C2	…	Cn	M	M	…	M
Bază	coeficient CF	Plan	A1	A2	…	Un	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Determinăm elementele dreptei suplimentare folosind formulele Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

Pentru a determina diferențele Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

După primirea tabelului simplex original, acesta este transformat, încercând să derivăm din vectorii de bază corespunzători variabilelor suplimentare introduse.

Din moment ce M este foarte număr mare, atunci printre diferențele Zj-Cj vor fi multe numere pozitive. Adică, vor exista mulți candidați pentru includerea în bază printre vectorii A1,A2,…,An

Dacă un vector corespunde variabilelor introduse artificial xn+1,xn+2,…,xn+m, atunci vectorul corespunzător este derivat din bază, iar coloana simplex a tabelului cu acest vector este tăiată și nu este returnată. la ea din nou. La sfârșitul transformării tabelului simplex, sunt posibile două opțiuni:

· toți vectorii corespunzători variabilelor artificiale au fost derivați de la bază, în acest caz toate coloanele din tabelul simplex corespunzătoare variabilelor suplimentare vor dispărea, iar problema inițială va fi rezolvată

· planul optim rezultat va conține în continuare o variabilă suplimentară, aceasta înseamnă că ODD-ul problemei inițiale este gol, adică restricțiile sale sunt contradictorii, prin urmare problema inițială nu are soluții deloc.

Probleme de programare liniară duală. Enunțarea problemelor, proprietățile lor.

Probleme duble simetrice:

Prima formă standard

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

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

a1mx1+a2mx2+…+anmxn>=bm

Problemă dublă

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Pereche non-septenară de probleme duale

Problema originală în formă canonică

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

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

Academia de Stat și Serviciu Municipal Kursk

Departamentul de Securitate Informațională și Tehnosferă

Eseu

prin disciplina „Metode de soluții optime”

pe subiect „Ideea metodei simplex”

Completat de: student anul II

Specialitățile „Economie”

Moskaleva O. S.

Verificat de: Ph.D., profesor asociat Pogosyan S. L.

Kursk – 2012

Introducere……………………………………………………………………………………………..3

1. Ideea metodei simplex………………………………………………………….…4

2. Implementarea metodei simplex folosind exemplul…………..……6

3. Implementarea tabelară a unei metode simplex simple……….10

Concluzie………………………………………………………………………………….15

Lista referințelor……………………………..…….16

Introducere.

Metoda Simplex este un exemplu tipic de calcule iterative folosite pentru a rezolva majoritatea probleme de optimizare.

În schema de calcul a metodei simplex este implementat 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.

Ideea metodei simplex

Să considerăm o metodă universală pentru rezolvarea problemei de programare liniară canonică, cu n variabile şi m constrângeri de egalitate, cunoscute sub numele de metoda simplex.

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 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.

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ă.

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ă: părțile din dreapta ecuațiilor; matricea de condiții conține o submatrice de dimensiunea unității.

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ă.

Implementarea metodei simplex folosind un exemplu

Să demonstrăm utilizarea metodei simplex cu un exemplu. Sa luam in considerare problema canonica LP


f(x) = X 1 + 2X 2 + 0X 3 + 0X 4 > max
-X 1 + 2X 2 + x 3 = 4,
3X 1 + 2X 2 + x 4 = 12,
x j? 0, j = 1,2,3,4.

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

Vector țintă c =(c 1, c 2, c 3, c 4) = (1, 2, 0, 0); vector al părților drepte b=(b 1 ,b 2) = (4, 12).

Pasul 0. Găsirea punctului de început de colț (linia de bază).

Problema are o formă preferabilă, deoarece părțile din dreapta ecuațiilor sunt pozitive, iar coloanele matricei de condiții A 3, A 4 formează o submatrice unitară. Aceasta înseamnă matricea de bază inițială = (A 3 ,A 4); X 3 Și X 4 - variabile de bază X 1 Și X 2 - variabile non-bazice, c B = (c 3, c 4) = = (0, 0).

Linia de bază inițială arată ca x 0 =(0, 0, X 3 , X 4) = (0, 0, 4, 12); f(x o) = 0.

Pasul 1. Verificarea planului de bază pentru optimitate.

Să calculăm estimări simplex pentru variabile non-bazice folosind formula (5.1)

? 1 = 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

Deoarece estimările sunt negative, planul X- nu 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ă prin introducerea uneia dintre variabilele non-bazice în variabilele de bază (făcând-o pozitivă) X 1 sau X 2, deoarece ambele estimări ? j x 2.

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

După introducerea variabilei în bază x 2plan nou va arăta ca

x" =(0, X 2, X 3 , X 4).

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 variabile zero (excludeți din bază) X 3 sau X 4 . Să înlocuim coordonatele planului x" =(0, X 2, X 3 ,X 4) în constrângerile problemei. Primim

2X 2 + x 3 = 4,

2X 2 + X 4 = 12.

Să exprimăm variabilele de bază de aici X 3 Și X 4 prin variabilă X 2 , intrat în bază.


X 3 = 4 - 2X 2,
X 4 = 12 - 2X 2 .

Deci variabile X 3 Și X 4 trebuie să fie nenegativ, obținem un sistem de inegalități


4 - 2X 2 ? 0,
12 - 2X 2 ? 0.

Cu cât valoarea este mai mare X 2 , cu cât funcţia obiectiv creşte. Să găsim valoarea maximă a noii variabile de bază care nu încalcă constrângerile problemei, adică să satisfacă condițiile (2.8), (2.9).

Să rescriem ultimele inegalități în formă

2X 2 ? 4,

2X 2 ? 12,

de unde vine valoarea maxima? X 2 = min ( 4/2, 12/2 ) = 2. Înlocuind această valoare în expresiile (2.6), (2.7) pentru X 3 Și X 4 , primim X 3 = 0. Prin urmare x 3 derivate de la bază .

Pasul 4. Determinarea coordonatelor noii linii de bază.

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

X" = (0, X 2, 0, X 4)

Baza acestui punct constă din coloane A 2 și A 4 , deci =( A 2, A 4). Această bază nu este unitară, deoarece vectorul A 2 = (2,2), și prin urmare problema (2.2)-(2.5) nu are o formă preferată față de noua bază. Să transformăm condițiile problemei (2.3), (2.4) astfel încât să ia forma preferată față de noile variabile de bază X 2, X 4, adică astfel încât variabila X 2 a fost inclus în prima ecuație cu un coeficient egal cu unu și nu a fost prezent în a doua ecuație. Să rescriem ecuațiile problemei

- X 1 + 2 X 2 + X 3 = 4, (p 1)

3X 1 +2 X 2 + X 4 = 12. (p 2)

Să împărțim prima ecuație la coeficientul de la X 2 . Obținem o nouă ecuație = p 1/2 echivalent cu originalul

1/2 X 1 + X 2 + 1/2 X 3 = 2. ()

Folosim această ecuație, pe care o numim rezolvare, pentru a elimina variabila X 2 din a doua ecuație. Pentru a face acest lucru, trebuie să înmulțiți ecuația cu 2 și să scădeți din p 2 . Primim = p 2 - 2= p 2 -p 1:

4 X 1 - X 3 + X 4 = 8. ()

Ca rezultat, am obținut o nouă reprezentare „preferată” a problemei inițiale în raport cu noile variabile de bază X 2 , X 4:

f(X) = X 1 + 2 X 2 + 0 X 3 + 0 X 4 ? max

1/2 X 1 + x 2 + 1/2 X 3 = 2 ()

4 X 1 - X 3 + X 4 = 8 ()

x j? 0, j = 1,2,3,4

Înlocuind aici reprezentarea noii linii de bază X 1 = (0, X 2, 0, X 4), vom găsi imediat coordonatele sale, deoarece valorile variabilelor de bază sunt egale cu părțile drepte ale ecuațiilor

X" = (0, 2, 0, 8); f(X 1)=4.

Aceasta completează prima iterație a metodei 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ă.

Implementarea tabelară a unei metode simplex simple

Vom demonstra implementarea tabelară folosind același exemplu (2.2)-(2.5).

Pasul 0. Soluția începe prin construirea unui tabel simplex inițial. Completat primul partea dreaptă tabele din a treia coloană. In doi liniile de sus sunt scrise numele variabilelor sarcinii ( X 1, ...,X 4) și coeficienții funcției obiectiv pentru aceste variabile. Mai jos sunt coeficienții ecuațiilor - elemente ale matricei de condiții A, deci sub variabila X 1 situat coloană A 1, sub variabilă X 2 - coloană A 2 etc. Părțile din dreapta ale constrângerilor (numerele) sunt introduse în coloana din dreapta b i > 0).

Apoi găsim coloanele matricei de condiții care formează baza unității - în exemplul nostru aceasta este A 3 și A 4 - și variabilele lor de bază corespunzătoare X 3, X 4 scrie in a doua coloana. În final, în prima coloană scriem coeficienții funcției obiectiv pentru variabilele de bază.

tabelul 1- Tabel inițial simplex

	Variabile de bază					Valorile variabilelor de bază ( x B =b)
		*x 1*	*x 2*	*x 3*	*x 4*
	*x 3*	a 11 =-1
	*x 4*
Linia de evaluare ? j	? 1 = -1	? 2 = -2

Deoarece problema are o formă preferată, valorile variabilelor de bază sunt egale cu părțile din dreapta ale ecuațiilor situate în ultima coloană. Deoarece variabilele care nu sunt de bază sunt zero, linia de bază inițială este

X o = (0, 0, X 3 , X 4) = (0, 0, 4, 12).

Pasul 1. Pentru a verifica planul X o pentru optimitate calculăm estimări simplex pentru variabile nebazice X 1 Și X 2 conform formulei

? j = B, A j > - c j .

? 1 = B, A 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

Cu o implementare tabelară pentru calcularea scorului ? 1 trebuie să găsim suma produselor elementelor primei coloane ( c B) la elementele coloanei corespunzătoare A 1 pentru o variabilă nebază X 1 . Scorul se calculează în același mod ? 2 , ca produs scalar al primei coloane ( c B) pe coloană la variabilă x 2.

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

Estimările simplex sunt scrise în ultimul rând al tabelului simplex, care se numește rând delta. În acest caz, nu sunt completate doar celulele pentru variabilele nebaze, ci și celulele de bază. Este ușor de verificat că pentru coloanele unităților de bază ale matricei de condiții estimările simplex sunt egale cu zero. În ultima celulă a liniei de evaluare scriem valoarea funcției obiectiv în punct xo. Rețineți că, deoarece coordonatele non-baze ale planului de bază sunt egale cu zero, este convenabil să se calculeze funcția obiectiv folosind formula

f(X)= c B, x B >,

înmulțind scalar prima și ultima coloană a tabelului.

Din moment ce printre estimări ? j Există negativ , apoi planul X o nu este optimă, și este necesar să se găsească un nou plan de bază prin înlocuirea uneia dintre variabilele de bază cu una nouă dintre cele nede bază.

Pasul 2. Din moment ce ambele estimări ? 1 Și ? 2 atunci oricare dintre variabile poate fi inclusă în bază X 1, X 2 . Să introducem în bază variabila cu cea mai mare estimare negativă absolută, adică X 2 .

Coloana tabelului simplex în care se află variabila introdusă în bază se numește coloana principală.

În exemplu, coloana principală va fi la x 2 .

Pasul 3. Dacă toate elementele din coloana principală sunt negative, atunci nu există o soluție la problemă și max f(X) ???. În exemplu, toate elementele coloanei principale sunt pozitive, prin urmare, putem găsi valoarea maximă X 2 , la care una dintre vechile variabile de bază ajunge la zero. Amintiți-vă că valoarea maximă x 2 = min(4/2, 12/2)=2.

Conform tabelului, această valoare este calculată ca cea mai mică dintre rapoartele componentelor liniei de bază (de la ultima coloană) la cea corespunzătoare pozitiv elemente ale coloanei conducătoare.

Cel mai mic raport este în rândul cu variabila de bază x 3. Deci variabila x 3 excluse din variabilele de bază ( X 3 = 0).

Linia care conține variabila care trebuie exclusă din bază se numește linie de conducere.

În exemplu, linia principală va fi prima linie.

Elementul situat la intersecția rândului principal și coloanei de început se numește element de conducere.

În cazul nostru, elementul conducător A 12 = 2.

Masa 2- Tabel inițial simplex cu rând și coloană de început


	Schimbări de bază.					Valorile variabilelor de bază	Ecuații
			*x 2*
*c 3 =0*	*x 3*	-1	2	1	0	4
			2
Linia de evaluare ? j	? 1 = -1	? 2 = -2

Pasul 4. Pentru a obține un nou plan de bază, reducem problema la o nouă formă preferată în raport cu noile variabile de bază.

Pentru a face acest lucru, vom construi un nou tabel simplex, în a doua coloană a căruia în loc de variabila exclusă x 3 să scriem o nouă variabilă de bază x 2, iar în prima coloană ( cu B) în loc de de la 3 Să notăm coeficientul funcției obiectiv la x 2: c 2 =2. În noul tabel simplex, coloana la x 2 trebuie sa devin unul (elementul conducător trebuie să fie egal cu unu, iar toate celelalte elemente trebuie să devină zero). Acest lucru se realizează prin următoarele transformări de rând de tabel.

A.Împărțim toate elementele liniei de conducere la elementul de conducere și le scriem în aceeași linie ca una nouă tabele simplex.

Șirul rezultat p 1" Să-i spunem permisiv.

b. La a doua linie rămasă adăugăm linia de rezolvare, înmulțită cu un astfel de număr încât elementul din coloana principală devine zero.

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

c. Să completăm ultimul rând calculând estimările ? j " = - - c j, Unde c B ", A j " - coloanele corespunzătoare ale noului tabel simplex și valoarea funcției obiectiv f(x)= .

Obținem un al doilea tabel simplex cu o nouă bază.

Tabelul 3- Rezultatul primei iterații


	Schimbări de bază.					Valorile variabilelor de bază	Ecuații

		-*1/2*
	*x 4*	4	0	-1	1	8	p 2 " =p 2 - p 1
estimări ? j"	-2

Linie de bază nouă X " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ). De la evaluare ? 1 = -2 apoi planifică X " nu optim. Pentru a trece la un nou plan de bază (al punctului de colț vecin), vom efectua o altă iterație a metodei simplex.

Deoarece? 1 apoi se introduce o variabilă în bază x 1. Prima coloană care conține x 1 - conducere.

Găsim relațiile dintre componentele planului de bază și cele corespunzătoare pozitiv elemente ale coloanei principale și luați rândul cu cel mai mic raport ca rând principal. În tabelul 2, în coloana principală doar al doilea element este mai mare decât zero (= 4), prin urmare a doua linie va fi cea de conducere, și baza situată în acesta variabil x 4 sub rezerva excluderii din temei.

Selectăm coloana principală și rândul principal și la intersecția lor găsim element conducător (= 4).

Construim un nou (al treilea) tabel simplex, înlocuind variabila de bază din acesta x 4 pe x 1 , și transformând din nou rândurile tabelului, astfel încât elementul principal să devină egal cu unu, iar elementele rămase ale coloanei principale devin zero. Pentru a face acest lucru, împărțim linia principală (a doua) cu 4, iar la prima linie adăugăm a doua linie rezultată, împărțită la 2. Calculăm ultima linie folosind formulele pentru estimări simplex. ? j"" = "", A j""> - c j, Unde c B"", A j"" - coloanele corespunzătoare ale noului tabel simplex. Valoarea funcției obiectiv pe noua linie de bază este găsită folosind formula f(x"")= "", x B"" >.

Tabelul 4- Rezultatul celei de-a doua iterații


	De bază Schimbare.		Valorile variabilelor de bază	ecuații

				p 1 "" = p 1 "+p 2 ""/2
				p 2 "" = p 2 "/4
estimări ? j ""		f(x"")= 8

Linie de bază nouă X "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Deoarece toate estimările sunt nenegative, atunci planul X ""- plan optim.

Prin urmare, X* = (2, 3, 0, 0 ), f(x*) = 8.

CONCLUZIE

Metodele luate în considerare pentru rezolvarea problemelor de programare liniară sunt utilizate pe scară largă în practică. Cu toate acestea, trebuie remarcat faptul că

model matematicîntotdeauna mai sărac decât real sistem economic. Descrie acest sistem doar aproximativ, evidențiind unele proprietăți și neglijând altele. Pentru a compensa acest neajuns în economia matematică, sunt dezvoltate mai multe tipuri de modele, fiecare dintre ele fiind conceput pentru a reflecta un aspect specific al realității economice, astfel încât atunci când se rezolvă o anumită problemă economică, să fie posibilă selectarea modelului care i se potrivește cel mai bine. .

LISTA REFERINȚELOR UTILIZATE

1. Ashmanov S.A. Programare liniară. - M.: Nauka, 1981.

Metoda simplex

1. Ideea metodei simplex

Să luăm în considerare o metodă universală de rezolvare a problemei canonice LP.

cunoscut sub numele de metoda simplex.

După cum sa 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ț.

Iterarea peste toate punctele de colț este costisitoare din punct de vedere computațional și, prin urmare, ineficientă. În 1944, 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.

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ă.

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

· 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.

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 unul, care este absentă în 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țim 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 canonică a formei preferate, 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 a metodei 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, se obtine: 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 paranteze pot fi scrise ca

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 se atribuie o valoare pozitivă variabilei nebază corespunzătoare xk și punând variabilele nebazice rămase ale planului x egal cu zero, primim

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 vom obține un nou plan

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ă vom elimina 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. 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 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 ca minimul să fie realizat 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ă. În consecință, am obținut o nouă alcătuire de variabile de bază și non-bazice, 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 anumit punct toate estimările Dj ³ 0.

3. Implementarea metodei simplex folosind un exemplu

Să demonstrăm utilizarea 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 început de colț (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 non-bazice 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)

Cu cât valoarea x este mai mare 2, cu atât funcția obiectiv crește. 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. ()

Ca rezultat, am obținut o nouă reprezentare „preferată” a problemei inițiale (3.11) - (3.14) în raport cu 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.

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 ale econometriei. - M.: Statistică, 1976.

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

Ayvazyan S.A., Mkhitaryan V.S. Statistica aplicată ș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.