Dual problemă pentru sarcini standard, - studopediya
Fiecare problemă de programare liniară poate fi asociată cu așa-numita problemă dublă sau Adjoint în ceea ce privește problema originală. Teoria Aparatură dualitate poate fi utilizată în mod eficient pentru efectuarea de studii calitative ale proprietăților problemei programării liniare.
Luați în considerare problema alegerii programului optim de producție. Fie numărul de companie 1 are rezerve de resurse materiale și materii prime în volume (bi), în cazul în care m - numărul de tipuri de resurse. Ca și înainte, presupunem că AIJ - este cantitatea de materii prime de forma i materiale și. necesară pentru a produce o unitate de tip de ieșire j, cj - profit din emiterea și vânzarea de unități de tip de produs j ().
Mai mult decât atât, presupunem că numărul de companie 2 a decis să cumpere toate materialele și prime resursele materiale în numărul 1 întreprindere pe unele dintre cele mai bune preturi de pe aceste resurse, care sunt notate cu y1. ¼, ym. În mod firesc, numărul 2, compania este interesată de faptul că costurile pentru achiziționarea de resurse materiale și materiale prime au fost minime, adică,
Pe de altă parte, compania numărul 1, care vinde resursele de materii prime, este interesat de faptul că veniturile rezultate nu a fost mai mică decât suma pe care compania poate obține utilizarea resurselor în producția de produse finite.
Pentru a produce o unitate de ieșire de tip 1 A11 resurselor consumate de primul tip, A21 resursa de al doilea tip, ¼, AI1 i -lea tip de resursă. Prin urmare, în scopul de a îndeplini cerințele vânzătorului (numărul de companie 1), costul resurselor utilizate pentru producerea de o unitate de ieșire din primul tip, nu ar trebui să fie mai mică decât c1 preț. Cu alte cuvinte, este necesar pentru a satisface inegalitatea de forma următoare:
În mod similar, se poate introduce restricții pentru toate celelalte tipuri de produse 2, 3, ¼, n. Modelul economic-matematic și o interpretare semnificativă a modului în care problema este prezentată în partea dreaptă a tabelului. 6.1.
Studiul de condiții inițiale (directe) problema (I)
Dubla problema (II)
(6.1) sub constrângerea (6.2) și starea non-negativitate (6.3) pentru a face ieșire plan. în cazul în care veniturile (venituri) din vânzarea produselor este maxim, cu condiția ca consumul de resurse al fiecărui produs trebuie să depășească rezervele disponibile
(6.4) sub constrângerea (6.5) și starea de non-negativitate (6.6) pentru a găsi un set de prețuri de resurse. în cazul în care costul total al resurselor vor fi minime, cu condiția ca costul de resurse în producția fiecărui produs nu va fi mai mică decât profitul (venituri) din vânzarea produselor
prețurile de resurse y1. ¼, ym în literatura economică le-am primit diverse nume: de înregistrare, implicit, umbra. Semnificația numelor lor este că, în contrast cu prețul produsului rezultat, care poate fi prezis cu exactitate destul, prețurile de resurse y1. ¼, ym sunt interne, astfel cum acestea sunt definite nu din exterior, ci sunt determinate prin rezolvarea problemei, astfel încât acestea sunt adesea numite estimările de resurse.
Sursa și problema duală au următoarele caracteristici.
1. Prima problemă este determinată de funcția liniară maximă obiectiv, al doilea - minim.
2. Coeficienții variabilelor funcției obiectiv în prima sarcină sunt părți potrivite în constrângerile de sistem în a doua problemă.
3. Fiecare dintre sarcinile specificate în formularul standard, problema maximizare în toate inegalitățile de forma „este mai mic sau egal cu“, iar problema minimizării tot felul de inegalitate „este mai mare sau egal cu.“
4. coeficienții de matrice ale variabilelor din constrângerile pe ambele sisteme de sarcini sunt transpuse una de alta.
5. Numărul de inegalități în limitările de sistem ale unei probleme coincide cu numărul variabilelor într-o sarcină diferită.
6. Condiția de bază non-negativitate variabilelor disponibile in ambele probleme.
Sarcini (I și II) de programare liniară, având caracteristicile de mai sus, nazyvayutsyasimmetrichnymi vzaimodvoystvennymi sarcini. În continuare, le vom numi problema dublă. Problema (I) este, de asemenea, numit în original sau directă o pereche de probleme duale. Pe baza caracteristicilor sarcinilor duale descrise pot fi formulate, în general, după formarea problemei duale.
1. Aduceți toate sistemele de inegalitate la aceeași specie: în cazul în care problema inițială urmărește maximul funcției obiectiv, toate restricțiile de inegalitate ale sistemului sunt aduse în minte „este mai mic sau egal cu“, iar în cazul în care cel puțin - să însemne „mai mare sau egal cu.“ Care nu îndeplinesc cerințele pentru această inegalitate este multiplicată cu (-1).
2. Crearea unui A1 de matrice. care includ coeficienții matrice ale variabilelor A, din dreapta coloană ale sistemului original de constrângeri și linia coeficienții variabilelor din funcția obiectiv.
3. Forma o matrice A1 ¢, transpusa A1 matrice.
4. Pentru a forma problema duală pe baza matricei obținute A1 ¢ condițiile nonnegativeness și variabile.
Un exemplu de formare a problemei duale. Să problema inițială sau directă a programării liniare (PZLP) este de a determina maximul funcției obiectiv
1. Având în vedere că problema inițială la maxim, atunci ambele părți ale primei și a patra inegalitatea înmulțim cu (-1). obținem:
2. Noi forma matricea Augmented a sistemului:
3. Găsiți matricea A1 ¢, transpusa A1 matrice: