Rezumat: Metoda grafică și metoda simplex pentru rezolvarea problemelor de programare liniară. Metoda simplex. Ideea principală, etapele căutării soluțiilor, algoritmul metodei

Găsirea planului optim. Această metodă este universală, vă permite să rezolvați probleme programare liniară orice dimensiune în cadrul general. Cu toate acestea, această metodă necesită o reducere problema initiala La formă 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 notați condițiile de limitare în urmatoarea forma 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 rândul suplimentar 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 linie 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 naturale și baza artificiala. 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 problemele reale dintre 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 constitui 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 un ZLP de formă canonică

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 ar trebui luați ca ea. 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 inițial, acesta este transformat, încercând să se derive 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

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

INTRODUCERE

Tema lucrării mele se referă la rezolvarea problemelor apărute în economie. Acest lucru ridică problema alegerii celei mai bune, într-un sens, opțiune de soluție. Și să caute opțiune posibilă Adesea influențat de diverși factori care restrâng aria de alegere. Cu alte cuvinte, este necesar să se rezolve problema de optimizare, care constă în necesitatea selectării cea mai bună opțiune decizii între un anumit set, de obicei limitat, de opțiuni posibile.

Problema de optimizare poate fi formulată în limbaj matematic dacă multimea Optiuni Disponibile poate fi descrisă folosind relații matematice (egalități, inegalități, ecuații), iar fiecare soluție poate fi evaluată cantitativ folosind un indicator numit criteriu de optimitate sau funcție obiectiv. Apoi cea mai bună soluție va fi cel care livrează funcție obiectivă valoarea cea mai mare sau cea mai mică, în funcție de sensul semnificativ al problemei. De exemplu, atunci când investiți o sumă limitată de fonduri în mai multe proiecte, sarcina firească este să selectați acele proiecte care pot aduce cel mai mare profit în viitor. La livrarea produselor de la diverși furnizori către magazine, apare sarcina de a minimiza costurile de transport.

Procesul de formalizare a unei probleme se numește construirea modelului ei matematic. Este format din trei etape.

1. Selectarea parametrilor problemei de care depinde rezolvarea. Acești parametri se numesc variabile de control și se notează prin formarea unui vector din ei . Luarea unei decizii înseamnă stabilirea unor valori specifice pentru variabile.

2. Construirea unui criteriu numeric prin care se poate compara diverse opțiuni deciziilor. Un astfel de criteriu se numește de obicei funcție obiectiv și este notat cu .

3. Descrierea întregului set X valori admisibile ale variabilelor - restricții asociate prezenței resurse materiale, resurse financiare, capacități tehnologice etc.

Problema de optimizare matematică este găsirea unei astfel de soluții fezabile , care dă funcției obiectiv cea mai mare sau cea mai mică valoare dintre toate soluțiile posibile.

1. Metoda geometrică de rezolvare a problemelor LP

Această metodă este adesea folosită pentru a rezolva probleme în care există doar două cantități necunoscute. Să ne uităm la el folosind următoarele exemple:

Exemplul 1.1. (Problemă legată de producția de vopsele).

O mică fabrică produce două tipuri de vopsele: INT- Pentru lucrari interioareȘi EXT- pentru munca in aer liber. În producția de vopsele se folosesc două produse inițiale AȘi ÎN. Datorită suprafeței mici de depozit, rezervele zilnice maxime posibile ale acestor produse sunt de 6 tone, respectiv 8 tone. Pentru a produce 1 tonă de vopsea INT Se consumă 1 tonă de produs Ași 2 tone de produs ÎN, și pentru producerea a 1 tonă de vopsea EXT sunt 2 tone de produs Ași 1 tonă de produs ÎN. Fabrica vinde vopsea la prețul de 3 mii. dolari pe tona de vopsea INTși 2 mii de dolari pe tonă de vopsea EXT. Este convenabil să rezumați datele inițiale într-un tabel:

Un studiu al pieței de vânzări a arătat că cererea zilnică de vopsea EXT nu depășește niciodată cererea de vopsea INT, mai mult de 1 tonă. Câtă vopsea de fiecare tip ar trebui să producă fabrica pe zi pentru a maximiza veniturile din vânzările de produse?

Să construim un model matematic al problemei. Pentru a face acest lucru, este necesar să se determine variabilele problemei, funcția obiectiv și constrângerile pe care variabilele le satisfac. Să notăm prin x 1- volumul zilnic planificat de producție de vopsea INT și după x 2- volumul zilnic de producție de vopsea EXT. Funcție obiectivă f(x) va exprima venitul zilnic din vânzarea vopselei egal cu 3x 1 + 2x 2(o mie de dolari). Acest venit trebuie maximizat

f( x)= 3 x 1 + 2 x 2 ® max.

Să construim constrângerile problemei asociate cu ofertele limitate de produse AȘi ÎN. Pentru producția de vopsea INTîn cantitate x 1(t) va fi utilizat 1x 1(t) de produs A, și pentru producția de vopsea EXTîn volum x 2(t) va fi cheltuită 2x2(t) de produs A. De la furnizarea zilnică a produsului A este de 6 tone, apoi consumul de produs A pentru producția a două tipuri de vopsele nu poate depăși această cantitate pe zi: 1x 1 + 2x 2 £6. În mod similar, obținem constrângerea asociată stocului de produse ÎN : 2x 1 +1x 2 8 GBP. Constrângerea raportului dintre cererea de vopsele poate fi descrisă de inegalitatea: x 2 - x 1 £1. Ținând cont de condițiile naturale de nenegativitate a volumelor de producție, obținem în final următoarea problemă de programare liniară

f(x) = 3 x 1 + 2 x 2 ® max (1.1)

1 x 1 + 2 x 2 £ 6 , (1.2)

2 x 1 + 1 x 2 £ 8 , (1.3)

- x 1 + x 2 £1 , (1.4)

x 1 ³ 0, x 2 ³ 0 . (1.5)

Să construim un set de planuri de probleme descrise de constrângerile (1.2)-(1.5). Să luăm în considerare prima inegalitate. Specifică un anumit semiplan situat pe o parte a liniei de delimitare

p 1 : 1x 1 +2x 2 =6

Să construim această linie dreaptă pe un plan cu axe de coordonate x 1Și x 2. Pentru a trage o linie, este suficient să cunoști cele două puncte ale ei. Cel mai simplu mod este să găsiți punctele de intersecție ale unei linii drepte cu axele de coordonate. crezând x 1 = 0, din ecuația dreptei obținem x 2 = 3, și atunci când x 2 = 0 vom găsi x 1 = 6. Astfel drept p 1 va trece prin puncte (0,3) Și ( 6,0) . Pentru a determina pe ce parte a dreptei se află semiplanul dorit, este suficient să înlocuiți coordonatele oricărui punct al planului în inegalitatea (1.2). Dacă linia dreaptă nu trece prin origine, atunci este cel mai convenabil să luați punctul (0, 0) . Evident, în acest moment inegalitatea (1.2) este strict satisfăcută (1* 0 + 2* 0 < 6) , ceea ce înseamnă că semiplanul definit de această inegalitate se află sub linia dreaptă p1, inclusiv originea. Marcam semiplanul dorit cu umbrire ( Fig.1.1).

Să construim în mod similar semiplanul definit de inegalitatea (1.3) . Pentru a face acest lucru, trageți o linie de limită pe planul de coordonate

p2 : 2x 1 +x 2 =8 ,

găsirea punctelor sale de intersecție cu axele de coordonate: (0,8) Și (4,0) .

Înlocuirea coordonatelor punctului (0,0) în inegalitate (2.3), vedem că originea coordonatelor se află în semiplanul dorit (2* 0 + 1* 0 < 8) , ceea ce înseamnă că toate punctele care satisfac inegalitatea (2.3) sunt situate la stânga dreptei p2. Să marchem această zonă cu umbrire ( Fig.1.1).

Puncte definite de constrângere ( 4 ), sunt sub linia dreaptă

p 3 : -x 1 +x 2 =1,

trecând prin puncte (0, 1) Și (-1, 0) .

În sfârșit, condițiile de non-negativitate: x 1 ³ 0, x 2³0 a stabilit toate punctele primului sfert, pe care le notăm și cu umbrire.

Selectând acum punctele planului care satisfac toate constrângerile problemei (1.1)-(1.5), adică situate simultan în toate semiplanurile umbrite, obținem un set de planuri X. Este un poligon (în această problemă, un pentagon). Laturile sale se află pe linii drepte, ale căror ecuații sunt obținute din sistem original inegalități (1.2)-(1.5) prin înlocuirea semnelor de inegalitate cu egalități stricte.

Pentru reprezentare grafică a funcției obiectiv, introducem conceptul de linie de nivel (funcție izolinie).

Definiție. Linie de nivel de funcție (izolină) f(x) se numește un set de puncte x = (x 1, x2), în care ia aceeași valoare constantă f(x) = h, Unde h- un număr. Pentru funcție liniară două variabile f(x) = c 1 x 1 + c 2 x 2 linie de nivel corespunzătoare numărului h, va reprezenta o linie dreaptă cu ecuația

c 1 x 1 + c 2 x 2 = h (1.6)

Când numărul se schimbă h vom obţine o familie de drepte de nivel (drepte paralele) cu acelaşi vector de direcţie c = =(c 1 , c 2), perpendicular pe toate liniile. Se știe că vectorul c = (c 1 , c 2) pentru funcția liniară f(x) = c 1 x 1 +c 2 x 2 indică direcția creșterii sale. Din punct de vedere geometric, aceasta înseamnă că atunci când mișcarea paralelă a dreptei (1.6) în direcția vectorului țintă c valoarea funcţiei obiectiv creşte.

Să construim liniile de nivel ale funcției obiectiv f(x) = 3x 1 + 2 x 2în sarcina noastră. Ecuațiile lor vor arăta ca 3x 1 + 2 x 2 = h. Ele definesc o familie de linii paralele în funcție de parametru h. Toate liniile sunt perpendiculare pe vectorul țintă c = (3, 2), compus din coeficienții funcției obiectiv, așadar, pentru a construi o familie de linii de nivelul funcției obiectiv, este suficient să construim vectorul său țintă și să trasăm mai multe drepte perpendiculare pe acest vector. Vom trasa linii de nivel pe multe planuri X, amintindu-ne că atunci când se deplasează linii paralele în direcția vectorului țintă c = (3, 2) valoarea functiei f(x)= 3x 1 + 2x 2 va creste. Deoarece în problemă planul optim trebuie să livreze valoarea maximă posibilă funcției obiectiv, atunci pentru a rezolva problema grafic este necesar între toate punctele x = (x 1, x2) multe planuri X găsi un astfel de punct x* = (x 1 * , x 2 *), prin care ultima linie de nivel va trece în direcția vectorului țintă c = (3,2). Din Figura 1.2 este clar că punctul dorit va fi punctul situat în partea de sus a setului X, formată prin intersecția unor linii p 1Și p2. Rezolvând sistemul de ecuații care descriu aceste drepte găsim plan optim x 1 * = 3 1/3, x 2 * = 1 1/3. În acest caz, valoarea maximă a funcției obiectiv va fi egală cu f(x*) = 12 2 / 3 . Astfel, în fiecare zi fabrica trebuie să producă 3 1 / 3 tone de vopsea INTȘi 1 1 / 3 tone de vopsea EXTîn timp ce primea venituri 12 2 / 3 o mie de dolari.

x 1 + 2 x 2 = 6,

2 x 1 + x 2 = 8,

Exemplul 1.2.Întreprinderea medicală achiziționează două tipuri de complexe multivitamine „Sănătate” și „Longevitate” care conțin trei tipuri de vitamine. Numărul de unități ale acestor vitamine într-un gram de multicomplex, norma necesară pentru utilizare preventivă și costul unui gram de complexe „Sănătate” și „Longevitate” sunt reflectate în tabel.

Câte grame de complexe multivitaminice de fiecare tip sunt necesare pentru o doză preventivă, astfel încât toate vitaminele să fie primite cel puțin așa cum este necesar și, în același timp, costul lor total să fie minim.

Să creăm un model matematic al problemei. Pentru a face acest lucru, introducem variabile: x 1– cantitatea complexului „Sănătate”. (gr.) , x 2– cantitatea complexului „Longevitate”. (gr.) necesare utilizării profilactice. Funcția obiectivă exprimă costul total al complexelor de vitamine, care ar trebui să fie cât mai mic posibil

f( x)= 5 x 1 + 4 x 2 ® min (1.7)

Restricțiile care descriu respectarea standardelor de vitamine sunt următoarele:

Prin vitamina V 1 : 3x 1 + x 2 ³ 9 , (1.8)

Prin vitamina V 2 : x 1 + 2x 2 ³ 8, (1.9)

Prin vitamina V 3 : x 1 + 6x 2 ³ 12 . (1.10)

În acest caz, variabilele trebuie să fie nenegative: x j ³ 0, j = 1, 2.

Să începem din nou soluția prin construirea mai multor planuri X, pentru care trasăm linii drepte de frontieră, ale căror ecuații se obțin prin înlocuirea semnelor de inegalitate din restricții cu egalități

p 1 : 3 x 1 + x 2 = 9,

p2 : x 1 + 2 x 2 = 8,

p 3 : x 1 + 6 x 2 = 12.

Înlocuirea coordonatelor punctului (0,0) în inegalitățile (1.8)-(1.10) vedem că originea coordonatelor nu le satisface și, prin urmare, nu este inclusă în setul de planuri X. Prin urmare, hașurile sunt îndreptate deasupra și în dreapta liniilor de delimitare. Prin identificarea punctelor care satisfac toate inegalitățile și condițiile de non-negativitate, obținem setul de planuri prezentat în Fig. 1.2. ÎN în acest exemplu nu este limitat.

Să descriem funcția obiectiv (1.7) folosind linii de nivel. Pentru a face acest lucru, este suficient să construiți vectorul țintă c = (5, 4)și trageți mai multe linii perpendiculare pe acesta pe set X. Deoarece vectorul țintă indică direcția de creștere a funcției țintă, iar în problema dietei este necesar să se găsească minimul acestuia, apoi să se găsească soluție optimă vom muta linia de nivel paralel cu sine de-a lungul ansamblului Xîn direcția opusă vectorului țintă.

Ultimul punct al setului de planuri prin care mai trece linia de nivel va fi punctul de intersecție al liniilor p 1Și p2. Rezolvarea sistemului de uraniu (Fig. 1.3).

3 x 1 + x 2 = 9

x 1 + 2 x 2 = 8

obținem planul optim x 1 * = 2, x 2 * = 3. Valoarea minimă a funcției obiectiv va fi egală cu

f(x*) = 5∙2 + 4∙3 = 22.

Prin urmare, cea mai ieftină trusă profilactică constă în 2 g. complexul A şi 3 g. complex ÎN, iar costul său este 22 freca.

Acum este ușor să formulezi o soluție geometrică sarcini standard LP cu două variabile:

· este reprezentat un poligon admisibil - intersecția semiplanurilor care sunt soluții ale inegalităților corespunzătoare;

· este reprezentat vectorul țintă;

· se trasează o perpendiculară pe vectorul țintă prin mulțimea admisibilă - aceasta este linia de nivel a funcției țintă;

· prin deplasarea liniei de nivel paralel cu ea însăși în direcția vectorului țintă până când aceasta se află pe o parte a dreptei deplasate, se determină vizual punctul (sau punctele) maxim;

· se calculează coordonatele punctului maxim (prin rezolvarea sistemului corespunzător de ecuaţii care definesc drepte, al cărui punct de intersecţie este punctul dorit) şi valoarea maximă a funcţiei obiectiv.

Cometariu. Pentru a determina punctul minim, mutați izolinia împotriva direcției vectorului țintă.

În exemplele analizate, planul optim a fost situat la singurul vârf al poligonului de planuri fezabile. Cu toate acestea, la rezolvarea problemelor LP, pot apărea și alte cazuri.

Un număr infinit de planuri optime. Pe Fig.1.4 funcția obiectiv ia aceeași valoare maximă în orice punct al segmentului AB conectând două vârfuri ale unui set de planuri X. Această situație apare dacă liniile de nivel sunt paralele cu linia de delimitare.

Nicio soluție limitată. Pe Fig.1.5 Cazul este descris când funcția obiectiv nu este mărginită de sus pe setul de planuri și nu există o soluție la problema maximă. În acest caz, poate exista o soluție la problema minimă (ca și în problema vitaminelor).

Lipsa planurilor valabile. Pe Fig.1.6 Zonele permise sub fiecare dintre restricții nu au puncte comune. În acest caz, ei spun că constrângerile sunt inconsecvente, setul de planuri este gol, iar problema LP nu are soluție.

Orez. 1.4 Fig. 1.5 Fig. 1.6

2. Metoda simplex

2.1 Ideea metodei simplex

Sa luam in considerare metoda universala 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ț.

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 .

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

· 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, 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 obiectiv).

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

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

O matrice de bază este imediat evidentă: 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 =< с Б, 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- 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 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 = < с Б, A 1 >– de la 1 =1∙1 + 0∙0 + 2∙0 – 1= 0,

∆ 2 = < с Б, A 2 >– c 2 =1∙3 + 0∙1 + 2∙2 – (-3) = 10,

∆ 3 = < с Б, A 3 >– c 3 =1∙0 + 0∙1 + 2∙0 – 0= 0,

∆ 4 = < с Б, A 4 >– c 4 =1∙(-1) + 0∙5 + 2∙1 – 4= -3,

∆ 5 = < с Б, A 5 >– de la 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.

2.2 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	(2.2)
–X 1 + 2X 2 +x 3 = 4,	(2.3)
3X 1 + 2X 2 +x 4 = 12,	(2.4)
x j ≥ 0, j = 1,2,3,4.	(2.5)

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

Vector țintă c =(c 1, c2, 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 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 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 = < c B, A 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1 .

 2 = < c B, A 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 < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную X 2.

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

După introducerea variabilei în bază x 2 noul plan 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ă.

Cum mai multă valoare 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. Să 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 aceasta avem nevoie de ecuație se inmulteste cu 2 si se scade 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 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ă.

2.3 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 numele sunt înregistrate variabilele problemei (X 1, ...,X 4) și coeficienții funcției obiectiv pentru aceste variabile. Mai jos sunt coeficienții ecuațiilor - elemente ale matricei condițiilor A, deci sub variabila X 1 este situată coloana 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 de bază corespunzătoare X 3, X 4 este scris în a doua coloană. În final, în prima coloană scriem coeficienții funcției obiectiv pentru variabilele de bază.

Tabelul 1 - Tabelul inițial simplex

S B	Variabile de bază	cu 1 =1	cu 2 =2	cu 3 =0	cu 4 =0	Valorile variabilelor de bază ( X B = b)
S B	Variabile de bază	*x 1*	*x 2*	*x 3*	*x 4*	Valorile variabilelor de bază ( X B = b)
c 3 =0	*x 3*	a 11 =-1	a 12 =2	a 13 =1	a 14 =0	b 1 =4
c 4 =0	*x 4*	a 21 =3	a 22 =2	a 23 =0	a 24 =1	b 2 =12
Linia de evaluare  j		 1 = -1	 2 = -2	 3 = 0	 4 = 0	f(x)= 0

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 non-baze 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 prin formula

 j =< c Б , A j > – c j .

 1 = < c Б , 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 variabila 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 = < c B, A 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 sunt negative , 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 < 0,то в базис можно включить любую из переменных 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

c B	Schimbări de bază.	cu 1 =1	cu 2 =2	cu 3 =0	C4 =0	Valorile variabilelor de bază	Ecuații
c B	Schimbări de bază.	x 1	*x 2*	x 3	x 4	Valorile variabilelor de bază	Ecuații
*c 3 =0*	X 3	–1	2	1	0	4	p 1
c 4 =0	x 4	3	2	0	1	12	p2
Linia de evaluare  j		 1 = –1	 2 = –2	 3 = 0	 4 = 0	f(x)= 0

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 să 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 rândului principal la elementul principal și le scriem în același rând al noului tabel 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 Б ", A j " >- - c j,Unde c B ", A j " - coloanele corespunzătoare ale noului tabel simplex și valoarea funcției obiectiv f(x)=< c Б ", x Б " >.

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

Tabelul 3 - Rezultatul primei iterații

c B"	Schimbări de bază.	cu 1 =1	cu 2 =2	cu 3 =0	cu 4 =0	Valorile variabilelor de bază	Ecuații
c B"	Schimbări de bază.	x 1	x 2	x 3	x 4	Valorile variabilelor de bază	Ecuații
c 2 =2	X 2	*–1/2*	1	1/2	0	2	p 1 " =p 1 /2
c 4 =0	*x 4*	4	0	-1	1	8	p 2 " =p 2 - p 1
evaluări  j "		–2	0	1	0	f(x")=4

Linie de bază nouă X " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ).

De la evaluare  1 = -2 < 0, apoi planul 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 < 0, 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țiți linia principală (a doua) cu 4 și adăugați a doua linie rezultată împărțită la 2 la prima linie. Ultima linie calculați folosind formule pentru estimări simplex  j "" = < c Б "", 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 "")= < c Б "", x B "" >.

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

c B ""	De bază Schimbare.	cu 1 =1	cu 2 =2	cu 3 =0	cu 4 =0	Valorile variabilelor de bază	ecuații
c B ""	De bază Schimbare.	x 1	x 2	x 3	x 4	Valorile variabilelor de bază	ecuații
c 2 =2	x 2	0	1	3/8	1/8	3	p 1 "" = p 1 "+p 2 ""/2
c 1 =1	x 1	1	0	-1/4	1/4	2	p 2 "" = p 2 "/4
evaluări  j ""		0	0	1/2	1/2	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 menționat că modelul matematic este întotdeauna mai sărac decât cel 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ă un anumit problema economica s-a putut alege un model care i se potrivește cel mai bine.

LISTA DE REFERINȚE UTILIZATE

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

2. Kuznetsov Yu.N., Kuzubov V.I., Voloshchenko A.B. Programare matematică. – M.: facultate, 1980.

3. Kalikhman I.L. Algebră liniară și programare. – M.: Liceu, 1967.

4. Nit I.V. Programare liniară. – M.: Editura Universității de Stat din Moscova, 1978.

5. Yudin D.B., Golshtein E.G. Programare liniară. Teorie și metode finale. – M.: Fizmatiz, 1963.

6. Tarasenko N.V. Matematică-2. Programare liniară: un curs de prelegeri. – Irkutsk: editura BGUEP, 2003.

7. Programare matematică în exemple și probleme: Proc. indemnizatie. – Ed. a II-a, rev. si suplimentare – M.: Mai sus. şcoală, 1993. – 336 p.

8. www.yandex.ru

9. www.mathematica.ru

Ideea metodei simplex

Metoda simplex

În secțiunea anterioară s-a arătat că dacă o problemă de programare liniară are o soluție optimă, atunci una dintre soluțiile optime este cea admisibilă. solutie de baza sistemul său de restricții, 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 admisibile ale PLP cu două variabile și vectorul – gradient al funcției obiectiv.

Trebuie să găsim punctul acestui poligon în care funcția obiectiv ia cea mai mică valoare. Să se determine soluția de bază admisibilă inițială a problemei corespunzătoare punctului de colț B. După o căutare completă a tuturor soluțiilor de bază admisibile, 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, este mai profitabil să mergi 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 formează 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 în 1939 în articolul „ Metode matematice organizarea și planificarea producției”.

Metoda simplex constă din trei elemente principale.

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.

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

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

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 literaturii utilizate……………………………..…….16

Introducere.

Metoda Simplex este un exemplu tipic de calcule iterative utilizate în rezolvarea majorității problemelor de optimizare.

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

Ideea metodei simplex

Să considerăm o metodă universală de rezolvare a problemei de programare liniară canonică, cu n variabile şi m constrângeri de egalitate, cunoscute ca 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ă.

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

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.

Implementarea metodei simplex folosind un exemplu

Să demonstrăm utilizarea metodei simplex cu un exemplu. Luați în considerare problema LP canonică


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 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 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 2 noul plan 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. În primul rând, partea dreaptă a tabelului este completată din a treia coloană. Primele două rânduri conțin 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ți în a doua coloană. În final, în prima coloană scriem coeficienții funcției obiectiv pentru variabilele de bază.

tabelul 1- Tabel simplex inițial

	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

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 .

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.

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 rândului principal la elementul principal și le scriem în același rând al noului tabel 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
evaluă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.

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țiți linia principală (a doua) cu 4 și la prima linie adăugați 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
evaluă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ă

un model matematic este întotdeauna mai sărac decât un sistem economic real. 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 să se selecteze modelul care i se potrivește cel mai bine. .

LISTA DE REFERINȚE UTILIZATE

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