Diverse forme de notare a ZLP (generală, canonică, simetrică). Metoda simplex pentru rezolvarea unei probleme de programare liniară

Problemă de programare liniară de forma ax = b unde a este matricea coeficienților, b este vectorul constrângerii.
Exemplu:

În fiecare problemă LP se caută valorile variabilelor cu condiția ca:

• aceste valori au satisfăcut un sistem de ecuații liniare sau inegalități;
• la aceste valori, funcția obiectiv s-ar transforma la minim sau maxim.

Instrucțiuni. Selectați numărul de variabile și numărul de rânduri (număr de constrângeri). Soluția rezultată este salvată într-un fișier Word.

Una dintre metodele universale LP este metoda simplex, care, totuși, poate fi folosită dacă problema LP are o formă canonică.

Definiție. Problema LP are o formă canonică dacă toate constrângerile sistemului constau numai din ecuații (cu excepția inegalităților care exprimă non-negativitatea variabilelor) și funcția obiectiv trebuie redusă la minimum.
Un exemplu de astfel de problemă LP în formă canonică este Problema 1 – o problemă de transport echilibrat cu un sistem de constrângeri (1) și o funcție obiectivă (2).
Cu toate acestea, în majoritatea problemelor economice, cel mai adesea sistemul de constrângeri include inițial nu numai ecuații, ci și inegalități.

Afirmație. Orice problemă generală LP poate fi redusă la formă canonică.
Reducerea problemei generale LP la forma canonică se realizează prin introducerea de noi variabile (se numesc suplimentare).
Sistemul de constrângeri (3) al acestei probleme este format din patru inegalități. Prin introducerea de variabile suplimentare y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, putem merge la sistemul de restricții:

Aceste variabile suplimentare y am o semnificație economică absolut clară, și anume, ele înseamnă cantitatea de timp de lucru neutilizat (timp de oprire a mașinii i-al-lea tip).
De exemplu, dacă mașinile de primul tip au funcționat pentru toate cele 18 ore, atunci x + y = 18, prin urmare, y 1 = 0. Dar permitem posibilitatea utilizării incomplete a timpului de funcționare al primei mașini X + y<18. В этом случае y 1 capătă o valoare pozitivă și poate fi considerată ca o limită de timp neutilizată. De exemplu, cunoscând soluția acestei probleme din paragraful 3.3.2, X = 12, y= 6, putem concluziona din sistemul de restricții (3.9) că y 1 = y 2 = y 3 = 0 și y 4 = 12 – 6 = 6. Adică, mașinile de primul, al doilea, al treilea tip își folosesc timpul de lucru complet. Dar a patra mașină este încărcată doar pe jumătate, 6 ore și, având în vedere planul optim, este inactiv. Poate că, după astfel de concluzii, șeful întreprinderii va dori să o încarce cu alte lucrări, să o închirieze pentru această perioadă etc.
Deci, prin introducerea unor variabile suplimentare, putem reduce orice constrângere de tip de inegalitate la o ecuație.

Să luăm în considerare problema amestecului. Sistemul de restricții are forma:
Inegalitățile au fost îndreptate spre „mai mult”, prin urmare, introducând variabile suplimentare y 1, y 2, y 3 ≥ 0, acestea trebuie scăzute din partea stângă pentru a o egaliza cu dreapta. Obținem un sistem de restricții în formă canonică:
Variabilele y i vor avea, de asemenea, sens economic. Dacă vă amintiți conținutul practic al problemei, atunci variabila y 1 va însemna cantitatea de substanță în exces A din amestec, y 2 va însemna cantitatea de substanță în exces ÎNîn amestec y 3 – surplus CUîn amestec.
Sarcina de a găsi valoarea maximă a funcției obiectiv poate fi redusă la găsirea minimului pentru funcția - F datorită evidenței afirmației max F = –min (– F). Privește imaginea: dacă la un moment dat X= X 0 functie y= F(X) atinge maximul, apoi funcția y= –F(X), simetric față de acesta în raport cu axa BOU, în același punct X 0 va atinge un minim și F max = – (– F min) la X = X 0 .

Concluzie. Pentru a reprezenta problema LP în formă canonică este necesar:

• transforma inecuatiile incluse in sistemul de constrangeri al problemei in ecuatii prin introducerea unor variabile suplimentare;
• dacă funcţia obiectivă F→max (maximizează), se înlocuiește cu funcția – F→ min (care este minimizat).

O metodă analitică pentru rezolvarea unei probleme de programare liniară este metoda simplex. Pentru a-l aplica, problemele LP prezentate în moduri diferite trebuie reduse la formă canonică. Problema de programare liniară, scrisă în forma (2.1.1)-(2.1.3), este o formă extinsă de scriere a problemei generale de programare liniară (GLP).

Vom numi următoarea problemă o problemă de programare liniară canonică (CLPT):

sub restricții sub formă de egalități,

Dacă pentru o problemă în forma (2.3.1)-(2.3.4) condiția este îndeplinită t = n, apoi soluția sa se reduce la rezolvarea sistemului de ecuații

• (2.3.2) . În acest caz, problema nu va avea soluții dacă starea
• (2.3.3) nu este satisfăcută sau sistemul de ecuații nu are soluție.

condiție T

• 1. A merge din problema maximizării funcţie obiectiv (2.3.1) să problema de minimizare suficient luați toți coeficienții Cj funcție obiectivă cu semne inverseși rezolvați la maximum problema rezultată. După găsirea maximului, valoarea funcției obiectiv trebuie luată cu semnul opus. Soluția optimă va rămâne aceeași.
• 2. A merge de la constrângere de egalitate mai mică sau egală este necesar cu semnul plus:

3. A merge de la o constrângere „mai mare sau egală cu” la egalitate este necesar introduceți o variabilă suplimentară nenegativă cu semnul minus:

În acest caz, fiecare inegalitate își introduce propria (n +/)-a-a variabilă suplimentară.

• 4. Totul egalităţile având termeni liberi negativi se împart în-1, pentru ca condiția (2.3.4) să fie îndeplinită.
• 5. Dacă pe o variabilă Xj nu este impusă condiția de non-negativitate, Acea faceți o schimbare a variabilelor Xj=x”.- X" x"j > 0, x"> 0. În problema transformată toate variabilele sunt nenegative.

Există o afirmație că orice ZLP poate fi redus la o formă canonică.

Exemplul 2.3.1. Să transformăm problema dată în Exemplul 2.2.2 în formă canonică. Funcția obiectivă și sistemul de constrângeri arată astfel:

Să introducem o variabilă suplimentară jc 3 > 0 cu semn plus în prima inegalitate și în a doua x 4> 0 cu semnul minus și în al treilea x 5> 0, de asemenea, cu semnul plus. Ca rezultat, obținem un sistem de constrângeri probleme în formă canonică:

Având în vedere aceste restricții, trebuie să găsiți valoarea maximă a funcției:

Să luăm în considerare semnificația economică a variabilelor suplimentare în problema canonică a utilizării optime a resurselor.

Exemplul 2.3.2. Problemă de utilizare optimă a resurselor (problema covorului)[17 J.

Fabrica are la dispoziție o anumită cantitate de resurse de trei tipuri: forță de muncă (80 zile-om), materii prime (480 kg) și utilaje (130 ore mașină). Fabrica poate produce patru tipuri de covoare. Informațiile despre numărul de unități din fiecare resursă necesare pentru producerea unui covor de fiecare tip și despre veniturile primite de întreprindere dintr-o unitate din fiecare tip de produs sunt date în tabel. 2.3.1.

Este necesar să se găsească un plan de producție la care costul total să fie maxim.

Modelul economic și matematic al problemei Variabile: x x, x 2, x 3, x 4 - numărul de covoare de fiecare tip. Funcție obiectivă - este costul total de producție care trebuie maximizat:

Limitele resurselor:

Să aducem problema la forma canonică prin introducerea de variabile suplimentare x 5, x 6Și x 7:

Se va arăta mai jos că planul optim de producție este vectorul X* =(0; 30; 10; 0), valoarea funcției obiectiv este 150, i.e. Pentru a maximiza costul total de producție, este necesar să se producă 30 de covoare de al doilea tip și 10 covoare de al treilea tip. Să înlocuim valorile vectoriale optime Xîn restricțiile KZLP:

Obținem că resursele „muncă” și „echipamente” sunt utilizate pe deplin, resursa „materii prime” este disponibilă din abundență:

În acest caz x in arată că au mai rămas 200 kg de materii prime.

Deci principalele variabile x v x 2, x 3, x lînseamnă numărul de covoare de fiecare tip și variabile suplimentare x 5, x 6 lor 7 - volumul resurselor subutilizate.

Răspuns. Plan optim de producție X* = (0; 30;

10; 0).

Plan, sau solutie acceptabila, KZLP se numește vector X =(jc p X 2 ,..., x p), îndeplinind condițiile (2.3.2)-(2.3.4).

Dacă toate componentele soluției de bază a sistemului de constrângeri CLLP sunt nenegative, atunci o astfel de soluție se numește soluție de referință sau plan de referință. Numărul componentelor pozitive ale planului de referință nu poate depăși T.

Planul de referință se numește nedegenerat, dacă conţine T componente pozitive, altfel se numește degenerat.

Planul optim sau soluție optimă Un plan se numește plan care furnizează cea mai mare (cea mai mică) valoare a funcției liniare (2.3.1).

Setul tuturor planurilor PPP (dacă există) este poliedru convex. Fiecărui punct de colț (extrem) al poliedrului soluție îi corespunde plan de referință(soluții de bază nenegative ale sistemului de ecuații KZLP). Fiecare plan de referință este determinat de sistem T vectori liniar independenți conținuți într-un sistem dat de P vectorii D, D,..., A p. Dacă există un plan optim, atunci există un punct de colț al poliedrului de decizie la care funcția liniară atinge cea mai mare (cea mai mică) valoare.

Pentru a găsi planul optim, este suficient să examinăm doar planurile de referință. Limita superioară a numărului de planuri de referință conținute într-o problemă este determinată de numărul de combinații S t p (vezi paragraful 1.4).

Exemplul 2.3.3. Obțineți o soluție la problema utilizării optime a resurselor limitate (rezolvați ZL P):

Soluţie. Să aducem problema în formă canonică prin introducerea unor variabile suplimentare x 3, x 4 și x 5:

Să găsim toate planurile de sprijin ale sistemului de restricții al acestui KZLP (l? - 5; /77 - 3); numărul lor nu depășește 10:

Folosind metoda Jordan-Gauss (vezi paragraful 1.4), scriem toate soluțiile de bază ale sistemului de ecuații (Tabelul 2.3.2).

Număr bază impas solutii	Bază						Plan

Printre cele zece soluții de bază există cinci soluții de bază:

Planurile de referință indicate în Fig. 2.3.1 corespund, respectiv, următoarelor puncte de colț și valorilor CF din acestea:

Orez. 2.3.1.

Conform teoriei Soluția optimă LP este cuprinsă printre planurile de referință.

Astfel, valoarea maximă egală cu 2300 este atinsă de funcția obiectiv în punct ÎN pe planul de referință X 5 = (70; 80; 0; 60; 0).

Răspuns. Planul optim de sarcini: x ( = 70, x 2 = 80, valoarea funcției obiective f(x v x 2) = 2300.

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.
Completam toate rândurile din tabelul primului pas în funcție de datele sistemului de restricții și ale 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 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

Î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, adică. , Unde Și .

Uneori devine necesar să trecem î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ă.

D

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ă