Funcția obiectiv în formă canonică are forma. Forma canonică a unei probleme de programare liniară

Orice sarcină programare liniară poate fi redusă la o problemă de programare liniară în formă canonică. Pentru a face asta în caz 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 initiala este necesar să se determine maximul funcție liniară, atunci ar trebui să schimbați semnul și să căutați minimul acestei funcții;
dacă există restricții partea dreaptă este negativ, atunci această limită 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; x 2 ≥ 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 intrate în partea stanga 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ă problema canonica LP. 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. Model matematic sarcinile ar trebui 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 tabel simplex 1.
Completam toate rândurile din tabelul primului pas în funcție de datele sistemului de restricții și ale funcției obiective.

Posibil următoarele cazuri la rezolvarea problemelor pe maxim:

1. Dacă toţi coeficienţii ultima linie tabele 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 în valoare absolută coeficient negativ.

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 Orice algoritm de calcul este convergență, 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 același valori minime relaţie

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.

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ă prin faptul că 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ă.

Când se transformă un 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ă.

Nici unul caracteristici suplimentare forma canonică a problemelor nu se adaugă la schema de calcul luată î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. Altfel nimic specificatii suplimentare forma canonică a sarcinii nu adaugă.

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ă 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, acest lucru crește dimensiunea. matricea de bază A [ /, J ], care determină în principal complexitatea unui shat. 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 probleme de programare liniară.

Pagini: 1

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

Unul dintre metode 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 doar 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 funcția țintă (2).
Cu toate acestea, în majoritatea sarcini 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ă.
Aducând sarcină comună 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 lucrat 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).

Forma canonică a ZLP- problema de programare liniară de forma ax = b unde a este matricea coeficienților, b este vectorul constrângerii.

Scopul serviciului. Calculatorul online este conceput pentru tranziția unui PPP la un KZLP. Aducerea problemei la forma canonică înseamnă că toate constrângerile vor avea forma de egalități prin introducerea de variabile suplimentare.
Dacă nu se impune o constrângere nici unei variabile x j, atunci ea este înlocuită cu diferența de variabile suplimentare, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

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.

Cum se reduce o problemă de programare liniară la formă canonică

Se numește modelul matematic al ZLP de bază, dacă constrângerile din acesta sunt prezentate sub formă de ecuații cu condiția ca variabilele să fie nenegative.

Modelul matematic se numește canonic, dacă sistemul său de constrângeri este prezentat sub forma unui sistem de m ecuații liniar independente (rangul sistemului r=m), sistemul este alocat baza de unitate, se definesc variabilele libere iar functia obiectiv este exprimata in termeni de variabile libere. În acest caz, părțile din dreapta ecuațiilor sunt nenegative (b i ≥ 0).

Variabilele incluse într-una dintre ecuațiile sistemului cu un coeficient de unu și absente în alte ecuații se numesc necunoscute de bază, și toate celelalte - gratuit.

Soluția sistemului se numește de bază, dacă variabilele libere din acesta sunt egale cu 0 și are forma:
X baze = (0, 0; b 1 , …, b m), f(X baze) = c 0

Soluție de bază este punctul de colț al mulțimii de soluții ale sistemului, adică definește vârful poligonului soluție al modelului. Printre astfel de soluții se numără și cea în care ia funcția obiectiv valoare optimă.

O soluție de bază se numește soluție de referință dacă este admisibilă, adică. toate părțile din dreapta ale ecuațiilor sistemului (sau inegalităților) sunt pozitive b i ≥ 0.

Forma compactă a modelului canonic este:
AX = b
X ≥ 0
Z = CX(max)

Conceptul de soluție admisibilă, o regiune de soluții admisibile, o soluție optimă a unei probleme de programare liniară.
Definiția 1. Un vector X care satisface sistemul de constrângeri ZLP, inclusiv condițiile de non-negativitate, dacă există, este numit o soluție admisibilă pentru ZLP.
Definiția 2. Setul tuturor soluțiilor admisibile formează regiunea soluțiilor admisibile (ADA) a PLP.
Definiția 3. O soluție fezabilă pentru care funcția obiectiv atinge un maxim (sau un minim) se numește soluție optimă.

Exemplul nr. 1. Reduceți următoarea problemă LP la forma canonică: F(X) = 5x 1 + 3x 2 → max sub restricțiile:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Modelul este scris în formă standard. Să introducem variabile nenegative de echilibru x 3 , x 4 , x 5 , x 6 , pe care le adăugăm la părțile din stânga constrângerilor de inegalitate. Introducem toate variabilele suplimentare în funcția obiectiv cu coeficienți egali cu zero:
În prima inegalitate de sens (≤), introducem variabila de bază x 3 . În a 2-a inegalitate de sens (≤) introducem variabila de bază x 4 . În a treia inegalitate introducem variabila de bază x 5 . În a 4-a inegalitate - variabila de bază x 6. Obținem forma canonică a modelului:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Exemplul nr. 2. Găsiți două soluții de referință ale sistemului
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2