Dual problemă de programare liniară

Aceste sarcini au următoarele proprietăți:

1. Problema directă urmărește maximul funcției obiectiv (formă liniară), iar problema dublă - cel puțin.
2. Coeficienții variabilelor din funcția obiectiv a problemei primara sunt membri liberi ai constrângerilor dubla problemă a sistemului. Pe de altă parte, condițiile constante ale limitelor de sistem ale problemei directe - coeficienții variabilelor din funcția obiectiv a problemei duale.
3. În fiecare sarcină sistemul de constrângeri este dat sub formă de inegalități, cu toate de același sens, și anume atunci când maximul funcției obiectiv (problema directă) aceste inegalități sunt scrise cu un „mai mic sau egal cu“, iar când minimul (dublă sarcină) - semnul „mai mare sau egal“.
4. Coeficienții variabilelor în sistemele de matrici de restricții descrise
   
   și
   
   care sunt transpuse în raport cu celălalt.
5. Numărul inegalităților din sistem limitează problema directă coincide cu numărul de variabile ale problemei duale.
6. Condițiile de non-negativitate variabilelor sunt stocate într-o linie dreaptă. și dubla problema.

Două probleme de programare liniară care îndeplinește condițiile de mai sus, numite simetrice reciproc probleme duale.

Suntem conduși să le numim pur si simplu reciproc probleme duale.

Sarcina directă și dublă sale, luate împreună, formează o pereche de probleme reciproc duale, cu oricare dintre ele poate fi considerată ca originalul, în timp ce cealaltă ar fi dublă ei.

Așa că ne-am uitat la corespondența dintre problema de programare liniară primară și dublă, până în prezent numai pentru problemele înregistrate în forma canonică. Formulăm problema atâta timp cât regulile de elaborare dual în raport cu originalul pentru problema canonică (și mai târziu trece la sarcina scrisă în termeni generali):

1. Adu toate inegalitățile de constrângerile de sistem ale problemei inițiale la inegalitățile de același sens (adică, cu același semn): Dacă vă căutați pentru un maxim al funcției obiectiv în problema inițială (formă liniară) - acestea sunt scrise cu un „mai mic sau egal cu“, și dacă cel puțin - cu „mai mare sau egal cu“ semn. Pentru această inegalitate, în care nu este îndeplinită această cerință, înmulțită cu un minus.
2. A Coeficienții deversat matricea variabilelor problemei inițiale obținute după transformările descrise în paragraful anterior și constituie matricea A“, transpusa pentru matricea A.
3. Constitui constrângerile de sistem cu dublă problemă, luând ca coeficienții variabilelor elementelor matricei A“, iar ca membrii liberi - coeficienții variabilelor din funcția obiectiv a problemei inițiale și scrie sensul opus al inegalității (adică semn schimbare) în comparație cu inegalitățile obținute în etapa 1.
4. Constitui funcția țintă (formă liniară) la problema duală prin adoptarea pentru coeficienții variabilelor sistemului de restricție a problemelor inițiale membrii liberi obținute în etapa 1.
5. Indică faptul că este necesar să se găsească în soluția problemei dublă, și anume minimul funcției obiectiv dacă problema inițială este solicitată maximă, iar maximă dacă minimă este solicitată în problema originală.
6. Se înregistrează starea de non-negativitate a variabilelor problemei duale.

Exemplul 1: Crearea unei sarcini, dublă după cum urmează: a găsi funcția maximă sub constrângeri

Decizie. În al treilea rând, inegalitatea problema inițială a sistemului nu îndeplinește alineatul 1 la elaborarea problemei duale. Prin urmare, se înmulțește cu unul negativ:

Pentru a facilita pregătirea problemei duale este mai bine să se utilizeze un B. matrice expandat care, împreună cu coeficienții variabilelor constrângerile problemă originale ale sistemului de a scrie în jos termenii liberi și coeficienții variabilelor din funcția obiectiv, selectând în acest scop o coloană suplimentară (linie separată) și linia (evidențiată în roșu) . Transpune matricea B și utilizând matricea transpusa B“, este sarcina sursei duale. Matricele B și B „au forma

Astfel, problema duală de programare liniară reduce la minimum găsirea unei funcții sub constrângeri

Ne întoarcem acum la cazul elaborării problemei dublă atunci când problema directă scrisă sub forma generală (restricții de sistem de inegalitate poate fi cu caractere diferite, precum și ecuații, variabile non-conditie negativitate nu este necesară). Pentru astfel de probleme, următoarele reguli:

1. Membrii liberi în problema directă - coeficienții funcției obiectiv în problema duală.
2. Coeficienții funcției obiectiv în problema directă - membri liberi în problema duală.
3. matrice Augmented în problema directă - matricea transpusă extins la problema dublă.
4. necunoscut j-lea în problema de proiectare directă pentru un non-negativ - j-lea inegalitatea în problema duală cu un „mai mare sau egal“.
5. necunoscut j-a în problema directă, fără a se limita la semn - j th constrângere în problema duală sub forma unei ecuații.
6. necunoscut j-lea în problema directă non-pozitiv - j-lea inegalitatea în problema duală cu un „mai mic sau egal cu“.
7. i-lea inegalitatea în problema directă, cu un „mai mic sau egal cu“ - i-lea necunoscut în problema duală este non-negativ.
8. i-lea limitare a problemei directe sub forma ecuației - i-lea necunoscut în problema duală, fără a se limita la semn.
9. i-lea inegalitatea în problema directă, cu o „mai mare sau egal cu“ - i-lea necunoscut în problema duală non-pozitive.

Exemplul 2: Crearea unei sarcini, dublă după cum urmează: a găsi un minim al funcției de sub constrângeri

Decizie. După cum puteți vedea, problema directă este scris în termeni generali. Acesta va fi luată în considerare în plasarea semnelor în ceea ce privește problema dublă. Și totuși, la fel ca în exemplul anterior, proizvedom efect universal - forma matricea B a problemei directe și matricea B „transpusă a problemei dublă:

Astfel, problema duală de programare liniară reduce la găsirea maximă a funcției de sub constrângeri

Teoria dualității în programarea liniară este construit pe două teoreme fundamentale.

Teorema 1. Pentru problemele directe și duale în puterea unul și numai unul dintre următoarele afirmații. 1. Dacă una dintre sarcinile programării liniare are un optim finit, atunci sarcina duală are de asemenea un finit optim, cu valori optime ale formelor liniare ale ambelor probleme sunt aceleași, adică. E.F max = Z min iliF min = Z max. 2. În cazul în care forma liniară a uneia dintre problemele duale nu sunt limitate la, termenii celorlalte obiective sunt contradictorii. 3. Ambele probleme au nici o soluție, deoarece constrângerile sistemului sunt contradictorii.

Înainte de a formula teorema următoare, vom stabili o corespondență între variabilele din problemele inițiale și duble. Pregătiți-vă: jocul va urma formula că prima dată nu toată lumea va înțelege, dar după ce a citit exemplul 2 trebuie să înțeleagă totul.

La rezolvarea metodei simplex a problemei inițiale pentru sistemul informațional al inegalităților la un sistem echivalent de ecuații trebuie să introduceți variabile suplimentare m non-negative (numărul de inegalități în sistemul de constrângeri) x n + 1. x n + 2. x n + i. x n + m. unde i = 1, 2. m este numărul de inegalitate, în care n i sa introdus variabila x suplimentar +.

constrângeri de sistem cu dublă problemă constă din n inegalități conținând m variabile. Dacă rezolva această problemă prin metoda simplex, este necesar să se introducă n y m + 1 variabile nenegative suplimentare. y m + 2. y m + j. y m + n. unde j = 1, 2. n este numărul sistemului de constrângeri de inegalitate ale problemei duale, care a fost introdus în plus variabilă y m + j.

Toate cele de mai sus a fost dată pentru a stabili următoarea corespondență între variabilele din problemele inițiale și duale de programare liniară:

Adică, principalele variabile ale problemei inițiale, în ordinea lor, corespund variabilei suplimentare a problemei duale, de asemenea, în ordinea în care apar. La rândul său, variabile suplimentare ale problemei inițiale, în ordinea lor, corespund principalelor variabile ale problemei duale, în ordinea în care apar.

Cu alte cuvinte, fiecare sarcină inițială variabilă x j inițială (j = 1, 2 n) este asociat suplimentar variabilă y m + j. introdusă în j th inegalitate problemă duală, și fiecare dintre suplimentar x n variabila + i problemei inițiale (i = 1, 2 m), introdus în inegalitatea i -lea a problemei inițiale; - variabila y dublă problema i original.

Toate cele de mai sus, după cum sa menționat, va fi mai bine înțeleasă din exemplul 2, care va fi la scurt timp după Teoremelor 2.

Teorema 2.Komponenty soluții optime una dintre sarcinile (directă sau dublă) sunt valorile absolute ale coeficienților variabilelor respective în ceea ce privește funcția obiectiv (formă liniară) la o altă sarcină (sau linie dublă) atunci când ajunge optim și cu condiția că soluția rezultată nu este optimă degenerată.

Teoremele 1 și 2 că, dacă pentru a rezolva una dintre problemele reciproc duale de programare liniară, adică să găsească soluția optimă sa și funcția obiectiv optim, putem scrie cea mai bună soluție și optime funcția obiectiv alte sarcini. Acum, un exemplu care va pune toate cele de mai sus pe rafturi.

Exemplul 3. Pe baza deciziilor directe și probleme duale de programare liniară din exemplul 1 pentru a verifica validitatea Teoremelor 1 și 2.

In exemplul 1, sarcina inițială a fost dat: găsiți funcția maximă sub constrângeri

Am făcut-o dublă misiune: de a găsi minimul funcției sub constrângeri

Pentru soluția sistemului directă simplex problemă metoda de constrângeri inegalităților reduse la un sistem de ecuații prin introducerea variabilelor nonnegative suplimentare x 3 x 4 x 5 x 6:

Cititorul poate verifica, rezolvarea problemei prin metoda simplex. că are următoarele soluții:

iar maximul funcției obiectiv F max = 13,

în timp ce ea însăși funcția obiectiv este exprimat ca

sistem dual problemă constrângere este redusă la un sistem de ecuații prin introducerea unor variabile suplimentare y 5. y 6:

Soluția de dublă metoda problemei simplex dă următorul răspuns:

și minimul obiectivului funcției Z min = 13

în timp ce ea însăși funcția obiectiv este exprimat ca

Decide problema duală, observăm că prima parte a teoremei 1: dublă problemă, de asemenea, are un finit optim, cu Z = min F max = 13.

Să ne asigurăm că este, de asemenea, valabil Teorema 2. Pentru a face acest lucru, vom scrie variabilele problemei pricipal duale, observând corespondența lor:

După cum puteți vedea, principalele variabile ale problemei inițiale, în ordinea lor, corespund variabilei suplimentare a problemei duale, de asemenea, în ordinea în care apar. La rândul său, variabile suplimentare ale problemei inițiale, în ordinea lor, corespund principalelor variabile ale problemei duale, în ordinea în care apar.

Funcția obiectiv obținut în ultima etapă a soluției problemei duale, exprimată în termeni de variabile ale acestei probleme:

Având în vedere coeficienții variabilelor y j în funcția obiectiv și luând în considerare conformitatea acestora cu coeficienții variabilelor x i. Obținem o soluție (4; 1; 0; 5; 4; 0). coincide cu soluția problemei directe.

Notă. După ce a rezolvat problema directă, puteți obține imediat o soluție la problema duală a programării liniare. Dacă ne exprimăm funcția obiectiv obținut prin rezolvarea problemei directe, prin toate variabilele problemei, obținem

Prin Teorema 2, având în vedere corespondența dintre variabilele din problemele primare și duale și luând valoarea absolută a coeficienților variabilelor, vom găsi soluția optimă pentru problema duală (2/3, 0, 0, 7/3, 0, 0). Z = min unde F max = 13.

Exemplul 4. Asigurați-vă că sistemul limitează problema directă

și dublă problema

Decizie. Scăzând a doua constrângeri ale sistemului ecuație problema directă ecuație a aceluiași sistem. Obținem. Această ecuație nu are nici o soluție, deoarece. Astfel, sistemul limitează problema directă este incompatibil.

Punerea în primele două inegalități ale restricțiilor impuse de sistem ale problemei duale. Considerăm că este imposibil. Astfel, sistemul de restricții și directe, iar problema duală sunt inconsistente. În conformitate cu partea 3 din Teorema 1 din dualitate, ambele probleme nu au soluții.

Să ne uităm din nou la problema de programare liniară liniară și problema duală acolo.

problemă directă.
funcţia maximiza