Fiecare problemă de programare liniară, pe care o numim cea inițială. se poate pune împreună cu corespondența o altă problemă de programare liniară, numită dublă pentru ea. Luate împreună, aceste probleme formează o pereche de sarcini reciproc ambigue și oricare dintre ele poate fi considerată ca una inițială. Rezolvând una dintre aceste probleme, se poate obține o soluție la o altă problemă.
O problemă dublă este o problemă de programare auxiliară liniară, obținută cu ajutorul anumitor reguli direct din condițiile celei originale.
Formăm regulile pentru construirea problemelor duale:
1. Dacă funcția obiectivului f al problemei inițiale este maximizată, atunci funcția obiectivă z este dublată minim și invers.
2. Numărul constrângerilor (m) din problema inițială este egal cu numărul de variabile duale, iar numărul de variabile (n) al originalului este egal cu numărul constrângerilor duale. Indicăm variabilele problemei duale prin yi (i = 1, m).
3. Deoarece variabilele problemei originale sunt legate de constrângerile duale, fiecare variabilă xj> = 0 corespunde în problema dublă unei constrângeri a formei "<=» (z→max) или «>= »(Z → min) și invers.
4. Pentru fiecare variabilă xj. fără a se limita la semn, corespunde unei restricții a formulei "=" a problemei duble și invers.
5. Membrii Free limitează bi inițială problemă (I = 1, m) în dual sunt coeficienții yi variabile (I = 1, m) în funcția obiectiv și coeficienții cj (j = 1, n) cu xj variabile (j = 1 , n) în funcția obiectivă a problemei originale sunt termenii liberi ai constrângerilor duale.
6. Matricea A a coeficienților pentru necunoscuți în constrângerile problemei inițiale în dual este transpusă (A m).
Considerăm, în general, una dintre problemele particulare ale programării liniare, pe care o vom considera a fi una inițială:
Dualul la această problemă va avea forma:
Dacă aplicăm regulile pentru construirea de probleme duale, primim problema inițială.
Tabelul 5 prezintă tipurile particulare de probleme inițiale ale programării liniare într-o formă de matrice și problemele duale corespunzătoare. Denumim prin Y = (y1, y2, ..., ym) matricea de rang a problemelor duale necunoscute. matrice Rândul Y este multiplicat la stânga pe matricea coloanei B (în funcția obiectiv) și matricea A (constrângere), bazată pe regulile de înmulțire a două matrice, precum și reguli pentru construirea probleme duale (în special în coeficienții duale de matrice sarcină a necunoscutele în restricțiile trebuie transpus).
Articole similare
-
Mașini de franising și reguli pentru folosirea lor - stadopedia
-
Reguli generale pentru detectarea, fixarea și îndepărtarea urmele
Trimiteți-le prietenilor: