Primal-Dual Pairs
For every linear programming problem we have a “dual” linear programming problem. Whereas in the original or primal linear program the variables are associated with the columns of the constraint matrix, in the dual linear program the variables are associa
- PDF / 3,563,709 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 405 Views
For every linear programming problem we have a "dual" linear programming problem. Whereas in the original or primallinear program the variables are associated with the columns of the constraint matrix, in the dual linear program the variables are associated with the rows of the constraint matrix. To bring out the symmetry of the construction of a primal-dual pair of linear programs we consider first the general case. Let A ij be an mi x nj matrix of scalars, Ci E ffi.n i be a row vector and bi E ffi.m i be a column vector for 1 ~ i ~ 3 and 1 ~ j ~ 3. Denote x E ffi.nj , y E ffi.n2 and z E ffi.n3 the column vectors corresponding to the primal variables and u E ffi.mj , V E ffi.m 2 and w E ffi.m3 the row vectors corresponding to the dual variables. The correspondence between the primal and the dual linear programs PRIMAL
min S.t.
DUAL
+ C2Y + C3 Z Allx + A 12 y + A 13 Z = bl A 21 X + A 22 y + A 23 Z 2:: b2 A 31 X + A 32 y + A 33 Z ~ b3 C1X
2::0
X
Y
0 z free ~
max ub l
+ vb 2 + wb3
S.t u
free 2::0
v uAu + VA 21 uA 12 + VA 22 UA 13 + VA 23
w
~O
+ WA 3l ~ Cl + WA 32 2:: C2 + WA 33 = C3
is summarized for a primal minimization problem as follows: • • • • •
The dual is a maximization problem. Equations of the primal give rise to "free" variables in the dual. Inequalities of the 2:: type correspond to nonnegative dual variables. Inequalities of the ~ type correspond to nonpositive dual variables. Nonnegative primal variables give rise to inequalities of the type ~ in the dual problem, nonpositive primal variables to inequalities of the type 2:: and free primal variables to equations in the dual.
The matrix notation brings out the primal-dual formalism in a different light. M. Padberg, Linear Optimization and Extensions © Springer-Verlag Berlin Heidelberg 1999
88
6. Primal-Dual Pairs
min PRIMAL
G)
(CI c, C3)
subject to
~~~ ~~:) (:) (:~) A A b 32
X ~
Z
33
0, y
~
3
0, z free
max DUAL
subject to
Exercise 6.1 Show that the dual linear program 0/ the linear program DUAL is the linear program PRIMAL. If any of the matrices A ij and/or some of the constraint sets are empty, then the formalism we have just described still applies and thus we can write down at onee the eorresponding dual problems for linear programs in the standard and/or the canonical form. If the linear program is in the standard form, then in the above notation
min{Clx:
Allx
= b1 ,
X ~
O}
and its dual linear program is given by max{ub 1 : uA ll ~ cd. Note that all dual variables u are free variables. If the linear program is in canonical form, then in the above notation max{ CIX : A 31 X ~ b3 , X ~ O} or equivalently, if the maximum exists, min{ -CIX : A 31 X ~ b3 , X ~ O} and thus the above primal-dual formalism gives the dual linear program min{wb 3 : WA 31 ~ cl, W ~ O}, where we have made the variable substitutition = -wo To summarize in our usual notation the dual linear program to the primal linear program in canonical form max{ cx : Ax ~ b, x ~ O} is given by
w
min{ub: uA
~
c, u
~
O}.
The dual to the primal in
Data Loading...
