Reducerea problemei generale LP la forma canonică. Forma canonică a unei probleme de programare liniară

Sarcini MP

General ZLP este numit <,=,>=)bi (i=1,n) (2) cu condiția xj>

Simetric < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Canonic amestecat.

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Interpretarea geometrică a funcției obiective și a constrângerilor ZLP. Formularea geometrică a ZLP.

Să fie dată problema f=c1x1+c2x2-max (1).

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

Planul problemei (x1,x2) este un punct din plan. Fiecare inegalitate cu-noi 2 reprezentări. este un semiplan. Un semiplan este o mulțime convexă. Convex se numeste multime in care punctele segmentului de legatura (x1 si x2) apartinand acestei multimi apartin si ele multimii. C-ma 2 reprezintă intersecția semiplanurilor. La traversare puteți obține:

1) zonă închisă poligonală convexă.

2) zonă poligonală convexă deschisă

3) un singur punct

4) set gol

5) rază și segment

Interpretarea geometrică a funcției obiectiv: Funcția 1 este o familie de drepte paralele, care se numesc linii de nivel (linii de valoare constantă a funcției obiectiv). Derivatele parțiale ale funcției în raport cu x1 și x2 arată rata de creștere a funcției obiectiv de-a lungul coordonatelor axelor. Vector gradient arată direcția celei mai rapide creșteri a funcției obiectiv Pentru problema 1-3, vectorul gradient = (c1;c2) Iese din punctul (0,0) și este direcționat către punctul cu coordonatele (c1;c2). Vectorul gradient este perpendicular pe liniile de nivel. Intersecția semiplanurilor este de obicei numită zona de soluții admisibile (ADD).

Teorema principală a LP. Schema schematică a soluției la ZLP, care rezultă din această teoremă.

Dacă ZLP are o soluție, atunci funcția obiectiv atinge o valoare extremă la cel puțin unul dintre punctele extreme ale poliedrului plan. Dacă funcția obiectiv atinge o valoare extremă în mai mult de un punct extrem, atunci atinge una și aceeași valoare, care este o combinație liniară convexă a acestora, în orice punct. Când rezolvați manual ZLP, este convenabil să utilizați o intrare tabelară.

BP		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
f	hui	bo1 bo2 bon-m

Algoritmul metodei simplex.

1. aduce modelul problemei la forma canonică;

2. găsiți planul de referință inițial;

3. scrie problema cu simplu. masa;

5. trece la un nou plan de referință, la un nou simp. masa. Pentru a trece la un nou plan de referință, este suficient să înlocuiți o variabilă de bază cu una liberă. Variabila inclusă în bază și coloana de rezoluție corespunzătoare sunt determinate de cel mai mare element negativ absolut al rândului f. Variabila care exclude din bază și linia de rezoluție corespunzătoare sunt determinate de cel mai mic raport simplex, i.e. relația elementelor coloanei de unitate cu elementul corespunzător al coloanei de rezoluție. Raportul simplex este o mărime nenegativă. La intersecția rândului de rezolvare și a coloanei de rezoluție se află un element de rezoluție, față de care transformarea simplex se realizează în felul următor. regulă: 1. elementele șirului de permis se împart în elementul de admitere; 2. elementele coloanei de rezoluție se împart în elementul de rezoluție și își schimbă semnul în sens invers; 3. elementele rămase ale tabelului sunt rearanjate conform regulii dreptunghiului:

bij bis bkj=(bkj*bis-bij*bks)/bi

A doua teoremă a dualității.

dacă una dintre problemele duale are un plan optim, atunci și cealaltă este rezolvabilă, adică. are un plan optic. În acest caz, valorile extreme ale funcțiilor obiectiv coincid (j=de la 1 la n) Σcjxj*= (i=de la 1 la m)Σbiyi* dacă în original. problema, funcția obiectiv este neconstrânsă pe setul de planuri, apoi în problema duală sistemul de constrângeri este inconsecvent.

Teorema privind rangul matricei TK.

Rangul matricei A a problemei de transport este cu unul mai mic decât numărul de ecuații: r(A)=m+n-1.

39. Algoritm pentru construirea planului de referință inițial al ZLP.

Pentru a găsi planul de referință inițial, vă putem sugera următoarele algoritm:

1. scrieți problema sub forma unui tabel Jordan, astfel încât toate elementele coloanei de termeni liberi să fie nenegative, i.e. inegalitatea aio>=0 (i=1,m) a fost satisfăcută. Acele ecuații în care termenii liberi sunt negativi sunt mai întâi înmulțite cu -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	amo	am1…..amn
f=		-c1…. -cn

Transformați tabelul utilizând pașii de eliminare Jordan, înlocuind zerourile din coloana din stânga cu x-ul corespunzător. În același timp, la fiecare pas permisiv poate fi selectat orice coloană care conține cel puțin un element pozitiv. Rândul de rezolvare este determinat de cel mai mic dintre raporturile dintre termenii liberi și elementele pozitive corespunzătoare ale coloanei de rezolvare. Dacă, în procesul de eliminare, se întâlnește un rând 0, ale cărui elemente sunt zero, iar termenul liber este diferit de zero, atunci sistemul de ecuații de constrângere nu are soluții. Dacă întâlnim un rând 0 în care, în afară de termenul liber, nu există alte elemente pozitive, atunci mulțimea ecuațiilor restrictive nu are soluții nenegative Dacă mulțimea ecuațiilor restrictive comun, apoi după un anumit număr de pași toate zerourile din coloana din stânga vor fi înlocuite cu x și, astfel, se obțin o anumită bază și, în consecință, un plan de referință corespunzător.

40. Algoritm pentru construirea planului optim de referință al ZLP.

Planul inițial de asistență al lui Ho este examinat pentru optimitate.

Dacă nu există elemente negative în rândul f (fără numărarea termenului liber), -planul este optim. Dacă, de asemenea, nu există elemente zero în rândul f, atunci există un singur plan optim; dacă printre elemente există cel puțin un zero, atunci există un număr infinit de planuri optime. Dacă există cel puțin un element negativ în rândul f și nu există elemente pozitive în coloana corespunzătoare, atunci funcția obiectiv nu este limitată în regiunea fezabilă. Problema nu este rezolvabilă. Dacă există cel puțin un element negativ în rândul f, iar în fiecare coloană cu un astfel de element există cel puțin un element pozitiv, atunci puteți trece la un nou plan de referință care este mai aproape de cel optim. Pentru a face acest lucru, coloana cu un element negativ în rândul f este luată ca permisiv; Ei determină șirul de rezoluție din relația simplex minimă și efectuează pasul de eliminare Jordan. Planul de referință rezultat este din nou examinat pentru optimitate. Aceasta se repetă până când se găsește planul de referință optim sau se stabilește imposibilitatea de rezolvare a problemei.

Algoritmul metodei Gomori.

1. Folosind metoda simplex se găsește planul optim pentru problemă. Dacă toate componentele unui plan optim sunt numere întregi, atunci este optim. În caz contrar, treceți la pasul 2

2. Dintre componentele care nu sunt întregi, ar trebui să o selectați pe cea a cărei parte fracțională este cea mai mare și, folosind linia corespunzătoare a tabelului simplex, să formulați limita corectă folosind formula

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Convertiți inegalitatea formulată într-o egalitate zero echivalentă și includeți-o într-un tabel simplex cu un plan optim non-întreg

4. Problema extinsă rezultată este rezolvată folosind metoda simplex. Dacă planul rezultat nu este întreg, treceți la pasul 2.

Dacă în timpul procesului de rezolvare apare o linie cu un termen neîntreger și alți coeficienți întregi, atunci ecuația corespunzătoare nu are o soluție în numere întregi. În acest caz, problema inițială este, de asemenea, de nerezolvat în numere întregi, metoda lui Gomori are o aplicație limitată. Cu ajutorul lui, este indicat să rezolvi micile probleme, deoarece... numărul de interacțiuni poate fi foarte mare.

Diverse forme de notare a ZLP (generală, canonică, simetrică)

Sarcini MP: determinarea planului optim, determinarea volumului optim de producție, determinarea combinației optime de culturi, formarea pachetului optim de active, maximizarea profitului băncii etc.

General ZLP este numit problema de maximizare (minimizare). funcția liniară f=Σcj*xj-max(min) (1) sub restricții liniare ∑aij *xj(=<,=,>=)bi (i=1,n) (2) cu condiția xj>=0(j=1,n1), xj-arbitrară (j=n1+1,n)(3) unde cj,aij, numere bi-constante .

Simetric Forma de scriere a ZLP se numește problema maximizării funcției (1) sub constrângeri liniare în inegalități cu semn.< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >sau = și variabile nenegative. Canonic Forma de scriere a ZLP se numește problema funcției maxime (1) sub constrângeri liniare de egalități și variabile nenegative. Orice altă formă este numită amestecat.

min f(x) = -max(-f(x))

Transformarea unei inegalități într-o ecuație și invers se realizează pe baza lemei: pentru fiecare soluție x1...xn a inegalității a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) și invers. Fiecare soluție x1…xn,xn+1 a ecuației 6 și inegalității 7 corespunde unei soluții x1…xn a inegalității 5.

Pentru a trece de la forma din spate sim la forma canonică din spate, trebuie să introduceți variabile de echilibrare (egalizare). Aceasta se bazează pe teorema inegalității: orice inegalitate poate fi reprezentată ca o ecuație sau o simplă inegalitate.

Orice problemă de programare liniară poate fi redusă la o problemă de programare liniară în formă canonică. Pentru a face acest lucru, în cazul general, trebuie să puteți reduce problema de maximizare la problema de minimizare; trece de la constrângeri de inegalitate la constrângeri de egalitate și înlocuiește variabilele care nu se supun condiției de non-negativitate. Maximizarea unei anumite funcții echivalează cu minimizarea aceleiași funcții luate cu semnul opus și invers.

Regula pentru aducerea unei probleme de programare liniară la forma canonică este următoarea:

dacă în problema inițială este necesar să se determine maximul unei funcții liniare, atunci ar trebui să schimbați semnul și să căutați minimul acestei funcții;
dacă partea dreaptă a restricțiilor este negativă, atunci această restricție trebuie înmulțită cu -1;
dacă există inegalități între restricții, atunci prin introducerea unor variabile suplimentare nenegative acestea se transformă în egalități;
dacă vreo variabilă x j nu are restricții de semn, atunci este înlocuit (în funcția obiectiv și în toate restricțiile) cu diferența dintre două variabile noi nenegative:
x 3 = x 3 + - x 3 - , Unde x 3 + , x 3 - ≥ 0 .

Exemplul 1. Reducerea problemei de programare liniară la formă canonică:

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x2 ≥ 0; x 3 ≥ 0.

Să introducem variabile de nivelare în fiecare ecuație a sistemului de constrângeri x 4 , x 5 , x 6. Sistemul va fi scris sub formă de egalități, iar în prima și a treia ecuație a sistemului de constrângeri variabilele x 4, x 6 sunt introduse în partea stângă cu semnul „+”, iar în a doua ecuație variabila x 5 este introdus cu semnul „-”.

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Termenii liberi în forma canonică trebuie să fie pozitivi pentru a face acest lucru, înmulțiți ultimele două ecuații cu -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

În forma canonică de scriere a problemelor de programare liniară, toate variabilele incluse în sistemul de constrângeri trebuie să fie negative. Să presupunem că x 1 = x 1 " - x 7 , Unde x 1 "≥ 0, x 7 ≥ 0 .

Substituind această expresie în sistemul de constrângeri și funcția obiectiv și scriind variabilele în ordine crescătoare a indicilor, obținem o problemă de programare liniară prezentată în formă canonică:

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Condiție de optimitate pentru planul de bază al problemei LP canonice. Metoda simplex și convergența acesteia.

Metoda simplex este universal, deoarece vă permite să rezolvați aproape orice problemă de programare liniară scrisă formă canonică.

Ideea metodei simplex îmbunătățirea consecventă a planului, este că, pornind de la o soluție de referință inițială, miscare dirijata secvential de la soluţiile de referinţă ale problemei la cea optimă.

Valoarea functiei obiectiv nu scade in timpul acestei miscari pentru probleme la maxim.

Deoarece numărul de soluții de sprijin este finit, atunci după un număr finit de pași obținem soluția optimă de sprijin.

O soluție de referință este o soluție de bază nenegativă.

Algoritmul metodei simplex

1. Modelul matematic al problemei trebuie să fie canonic. Dacă este necanonică, atunci trebuie adusă la forma canonică.

2. Găsiți soluția de referință inițială și verificați optimitatea acesteia.
Pentru a face acest lucru, completați tabelul simplex 1.
Completem toate rândurile din tabelul primului pas conform datelor sistemului de restricții și funcției obiective.

Următoarele cazuri sunt posibile la rezolvarea problemelor pe maxim:

1. Dacă toți coeficienții ultimului rând al tabelului simplex Dj³ 0, apoi găsit

soluţie optim.

2 Dacă cel puţin un coeficient Dj £ 0, dar pentru variabila corespunzătoare nu există o singură relație evaluativă pozitivă, apoi soluția oprim sarcinile, deoarece F(X) ® ¥ , adică funcția obiectivă nu este limitată în zona soluțiilor fezabile.

Dacă cel puțin un coeficient al ultimului rând este negativ, iar pentru variabila corespunzătoare există cel puțin o atitudine evaluativă pozitivă, atunci trebuie să te miști la o altă soluție de referință.

4. E dacă sunt mai mulți coeficienți negativi în ultimul rând, atunci la coloana variabilă de bază(BP) introduceți asta variabil, care corespunde cel mai mare coeficient negativ în valoare absolută.

5. Dacă cel puţin un coeficient Dk< 0 ,Acea k - al tău coloana accept pentru prezentator.

6. Pentru linie de conducere o acceptam pe cea care corespunde minim raportul de membri liberi bi la coeficienți pozitivi conducând, k – acela coloană.

7. Se numește elementul situat la intersecția rândurilor și coloanei principale element conducător.

Completarea tabelului simplex 2 :

· umpleți coloana de bază cu zerouri și unu

· rescrieți linia principală împărțind-o la elementul principal

· dacă rândul de început are zerouri, atunci coloanele corespunzătoare pot fi mutate în următorul tabel simplex

· găsim coeficienții rămași folosind regula „dreptunghiului”.

Obținem o nouă soluție de referință, pe care o verificăm pentru optimitate:

Dacă toți coeficienții ultimului rând Dj³ 0, atunci soluția găsită maxim.

Dacă nu, atunci completați tabelul simplex al pasului 8 și așa mai departe.

Dacă funcţia obiectiv F(X) necesită găsirea valoarea minima, apoi criteriul optimitatea problemei este coeficienţi nepozitivi D j pentru toate j = 1,2,...n.

Convergența metodei simplex. Degenerarea în problemele LP. Cea mai importantă proprietate a oricărui algoritm de calcul este convergența, adică posibilitatea de a obține rezultatele dorite în timpul aplicării sale (cu o precizie dată) într-un număr finit de pași (iterații).

Este ușor de observat că problemele cu convergența metodei simplex pot apărea potențial în etapa de alegere a valorii lui r (secțiunea 2") în cazul în care aceleași valori minime ale raportului

se va realiza pentru mai multe rânduri din tabelul T (q) simultan. Apoi, la următoarea iterație, coloana b(β(q+1)) va conține zero elemente.

Înregistrarea funcției obiectiv și a sistemului de constrângeri în diverse probleme de programare liniară nu este aceeași: în unele probleme se solicită găsirea minimului funcției obiectiv, iar în altele - maximul; în unele cazuri variabilele căutate depind de un indice, iar în altele de doi; în unele probleme constrângerile sunt specificate sub forma unui sistem de inegalități liniare, iar în altele - sub forma unui sistem de ecuații liniare. În practică, este posibil să existe și probleme în care unele dintre constrângeri sunt sub formă de inegalități liniare, iar unele sunt sub formă de ecuații liniare. De asemenea, nu toate problemele pot necesita non-negativitatea variabilelor.

Luarea în considerare a unei astfel de varietăți de probleme de programare liniară necesită dezvoltarea unor metode speciale pentru rezolvarea claselor individuale ale acestora. Ne vom concentra atenția asupra studierii proprietăților și metodelor generale ale programării liniare, scrise în așa-numita formă canonică.

Dacă într-o problemă de programare liniară sistemul de constrângeri inițiale ia forma unor ecuații ca

și trebuie să găsiți maximul funcției obiectiv liniar

atunci se consideră că problema de programare liniară este scrisă în formă canonică.

Orice problemă de programare liniară poate fi ușor redusă la formă canonică. În cazul general, pentru aceasta este suficient să putem, în primul rând, să reducem problema minimizării funcției obiectiv la problema maximizării acesteia, în al doilea rând, să trecem de la constrângerile de inegalitate la constrângerile de egalitate și, în al treilea rând, să schimbăm acele variabile care sunt nesupus condiției de non-negativitate.

În cazul în care trebuie să găsiți minimul unei funcții , putem trece la găsirea maximului funcției , deoarece următoarea afirmație este adevărată:
.

Constrângerea de inegalitate a problemei inițiale, care are forma „ ", poate fi transformat într-o constrângere de ecuație prin adăugarea unei variabile suplimentare nenegative în partea stângă și a unei constrângeri de inegalitate de forma " ” – prin scăderea unei variabile suplimentare nenegative din partea stângă.

Rețineți că numărul de variabile suplimentare nenegative introduse este întotdeauna egal cu numărul de inegalități din sistemul original de constrângeri.

Variabilele suplimentare introduse au o semnificație economică foarte specifică. Astfel, dacă constrângerile problemei de programare liniară inițială reflectă costurile și disponibilitatea resurselor de producție, atunci valoarea numerică a variabilei suplimentare arată cantitatea de resursă neutilizată corespunzătoare.

Rețineți, de asemenea, că dacă unele variabile nu respectă condiția de non-negativitate, atunci trebuie înlocuită cu două variabile nenegative Și , după ce a acceptat
.

Exemplu. Scrieți următoarea problemă de optimizare liniară în formă canonică: găsiți minimul funcției
sub restricții

Soluţie

În această problemă, trebuie să găsiți minimul funcției obiectiv, iar sistemul de constrângeri include patru inegalități. Pentru a o scrie în formă canonică, trebuie să treceți de la constrângeri de inegalitate la constrângeri de ecuație și, de asemenea, să transformați funcția obiectiv.

Deoarece numărul de inegalități incluse în sistemul de constrângeri al problemei este egal cu patru, această tranziție trebuie efectuată cu introducerea a patru variabile suplimentare nenegative. Mai mult, în a doua și a patra inegalități există un semn „ „, așa că adăugăm variabile suplimentare în partea stângă. În prima și a treia inegalități există un semn „ „, ceea ce înseamnă că scădem variabile suplimentare din partea stângă.

De asemenea, transformăm funcția obiectiv, schimbând toate semnele la opus și găsim maximul acesteia.

Astfel, această problemă de programare liniară va fi scrisă în următoarea formă canonică:

găsiți maximul unei funcții

sub restricții

Pagina 1

Forma canonică a problemei se caracterizează prin următoarele trei trăsături: 1) un sistem omogen de constrângeri sub forma unui sistem de ecuaţii; 2) condiții omogene de non-negativitate care se aplică tuturor variabilelor implicate în problemă și 3) maximizarea unei funcții liniare. În această problemă, toate aceste trei caracteristici sunt încălcate.

Forma canonică a problemei de programare liniară este convenabilă deoarece este ușor de găsit vârful inițial al regiunii fezabile.

Să luăm în considerare forma canonică a problemei de programare liniară și metoda de eliminare Jordan-Gauss.

Forma canonică a unei probleme de programare liniară este adesea convenabilă.

La transformarea unui sistem de constrângeri în forma canonică a unei probleme de programare liniară, inegalitățile (12) și (13) trebuie înlocuite cu egalități. Pentru a face acest lucru, sunt introduse variabile suplimentare nenegative.

Demonstrați că matricele reale de comutație în perechi sunt simultan reduse la forma canonică a Problemei 1128 printr-o transformare de similaritate folosind o matrice ortogonală.

În esență (4) - (5) poate fi considerată ca forma canonică a problemei de programare neliniară, întrucât metodele prezentate în Cap. De obicei, în problemele de programare neliniară nu există nicio cerință ca variabilele să fie întregi.

Tipuri de restricții și metode de transformare a acestora.

Forma canonică a problemei se caracterizează prin omogenitatea sistemului de constrângeri sub forma unui sistem de ecuații; maximizarea funcției obiectiv; condiţia de non-negativitate a tuturor variabilelor implicate în problemă.

Forma canonică a problemelor nu adaugă nicio caracteristică suplimentară schemei de calcul luate în considerare.

Să considerăm mai întâi a doua formă canonică a problemei minime.

Algoritmul simplex-mete poate fi împărțit în două etape. În prima etapă se găsește o soluție de bază prin eliminarea variabilelor. Dacă se găsește, atunci avem forma canonică a problemei pentru a trece la a doua etapă. Al doilea pas este de a verifica dacă există un optim mărginit. Dacă există, atunci se determină soluții de bază admisibile și din care se selectează cea optimă.

Dacă problema este rezolvată în formă canonică, atunci se utilizează doar o parte din operațiunile introduse în al doilea paragraf. Astfel, pentru problema minimului canonic se realizează doar cazul paragrafului 3.4.1, fiind necesare doar operațiunile de rearanjare ciclică a stâlpilor, trecerea stâlpului prin zona de frontieră verticală, corectarea încălcărilor structurale și o parte din operația de trunchiere. Simetric, la rezolvarea problemei maxime canonice, se realizează doar cazul de la paragraful 3.4.2, iar operațiunile de rearanjare ciclică a șirurilor, trecerea unui șir prin zona de frontieră orizontală, corectarea încălcărilor structurale și o altă parte a operației de trunchiere. Necesar. În caz contrar, forma canonică a problemei nu adaugă nicio specificitate suplimentară.

Primul paragraf al introducerii a arătat cum o problemă generală de programare liniară poate fi redusă la una dintre formele canonice. Pentru problemele canonice, descrierea metodei de îmbunătățire secvențială este simplificată în mod formal, deoarece nu este nevoie să se ia în considerare două opțiuni pentru încălcarea condițiilor de optimitate și două opțiuni pentru a ajunge la următorul vârf. Cu toate acestea, aceasta crește dimensiunea matricei de bază A [. /, J ], care determină în principal complexitatea Cu toate acestea, în multe cazuri, aplicarea metodei la formele canonice ale problemei se dovedește a fi de preferat, iar în această secțiune ne vom opri asupra variantelor metodei obținute pentru anumite liniare. probleme de programare.

Pagini: 1

În cazul general, o problemă de programare liniară este scrisă în așa fel încât constrângerile să fie atât ecuații, cât și inegalități, iar variabilele pot fi fie nenegative, fie variabile în mod arbitrar. În cazul în care toate constrângerile sunt ecuații și toate variabilele satisfac condiția de non-negativitate, problema de programare liniară se numește canonică. Poate fi reprezentat în notație de coordonate, vector sau matrice.

1. Problema de programare liniară canonică în notație de coordonate are forma

Într-o formă mai compactă, această problemă poate fi scrisă folosind semnul de însumare,

(1.7)

2. Problema de programare liniară canonică în notație vectorială are forma

(1.8)

Unde ,

3. Problema de programare liniară canonică în notație matriceală are forma

(1.9)

, .

Aici A– matricea de coeficienți ai sistemului de ecuații, X– matrice-coloană a variabilelor sarcinii, – matrice-coloană a părților din dreapta ale sistemului de constrângeri.

Problemele de programare liniară sunt adesea folosite, numite simetric, care în notație matriceală au forma

(1.10)

(1.11)

1.4. Reducerea unei probleme generale de programare liniară
la forma canonică

În majoritatea metodelor de rezolvare a problemelor de programare liniară, se presupune că sistemul de constrângeri este format din ecuații și condiții naturale pentru non-negativitatea variabilelor. Cu toate acestea, la compilarea modelelor matematice ale problemelor economice, constrângerile se formează în principal în sisteme de inegalități, deci este necesar să se poată trece de la un sistem de inegalități la un sistem de ecuații. În acest scop, demonstrăm următoarea teoremă.

Teorema 1.1. La înlocuirea unei inegalități cu o ecuație. Fiecare decizie inegalităților

corespunde unei soluții unice a ecuației

și inegalități

, (1.14)

și, invers, fiecare soluție a ecuației (1.13) și inegalității (1.14) corespunde unei soluții unice a inegalității (1.12).

Dovada. Lăsa este soluția inegalității (1.12), atunci . Să notăm diferența dintre părțile din dreapta și din stânga acestei inegalități cu , i.e.

Evident . Să substituim în ecuația (1.13) în loc de variabile valorile , primim

Astfel, satisface ecuația (1.13) și inegalitatea (1.14). Aceasta înseamnă că prima parte a teoremei a fost dovedită.

Să satisfacem acum ecuația (1.13) și inegalitatea (1.14), adică avem

ȘI

Renunțând la valoarea nenegativă din partea stângă a ultimei egalități, obținem

adică satisface inegalitatea (1.12). Teorema este demonstrată.

Dacă inegalitatea este , atunci o variabilă suplimentară nenegativă trebuie introdusă în partea stângă cu semnul minus, i.e.

Se numesc variabile nenegative introduse în constrângerile de inegalitate pentru a le transforma în ecuații variabile suplimentare. Variabilele suplimentare sunt introduse în funcția obiectiv cu coeficienți zero și, prin urmare, nu afectează valoarea acesteia.

În cazul în care problema are variabile care se schimbă în mod arbitrar, atunci orice astfel de variabilă este înlocuită cu diferența a două variabile nenegative, i.e. , Unde Și .

Uneori devine necesar să treceți într-o problemă de la găsirea minimului la găsirea maximului sau invers. Pentru a face acest lucru, este suficient să schimbați semnele tuturor coeficienților funcției obiectiv cu cele opuse și, în caz contrar, lăsați problema neschimbată. Soluțiile optime ale problemelor maxime și minime obținute în acest fel coincid, iar valorile funcțiilor obiectiv pentru soluțiile optime diferă doar în semn.

Exemplul 1.1. Aduceți problema de programare liniară la forma canonică.

Soluţie. Să trecem la problema găsirii maximului funcției obiectiv. Pentru a face acest lucru, schimbăm semnele coeficienților funcției obiectiv. Pentru a transforma a doua și a treia inegalități ale sistemului de constrângeri în ecuații, introducem variabile suplimentare nenegative (în modelul matematic această operație este marcată cu litera D). Variabila este introdusă în partea stângă a celei de-a doua inegalități cu semnul „+”, deoarece inegalitatea are forma . Variabila este introdusă în partea stângă a celei de-a treia inegalități cu semnul „-”, deoarece inegalitatea are forma . Variabilele sunt introduse în funcția obiectiv cu un coeficient egal cu zero. Variabila căreia nu se impune condiția de non-negativitate se înlocuiește cu diferența , . Scriem problema în formă canonică

În unele cazuri, devine necesară reducerea problemei canonice la o problemă simetrică. Să ne uităm la un exemplu.

Exemplul 1.2. Aduceți o problemă de programare liniară într-o formă simetrică