Primal to dual conversion formulation
If the primal is of the form
Maximize `Z_x=c_1x_1+c_2x_2+...+c_nx_n`
Subject to the constraints
`a_11x_1+a_12x_2+...+a_(1n)x_n<=b_1`
`a_21x_1+a_22x_2+...+a_(2n)x_n<=b_2`
:
`a_(m1)x_1+a_(m2)x_2+...+a_(mn)x_n<=b_m`
`x_1,x_2,...,x_n>=0`
Then the corresponding dual is of the form
Minimize `Z_y=b_1y_1+b_2y_2+...+b_ny_n`
Subject to the constraints
`a_11y_1+a_21y_2+...+a_(m1)y_m>=c_1`
`a_12y_1+a_22y_2+...+a_(m2)y_m>=c_2`
:
`a_(1n)y_1+a_(2n)y_2+...+a_(mn)y_m>=c_n`
`y_1,y_2,...,y_m>=0`
Rules
|
|
In Primal
|
Then in Dual
|
|
1. |
Objective function is maximum
|
Objective function is minimum
|
|
2. |
Objective function : total 3 variables (`x_1,x_2,x_3`)
and coefficient `c_1,c_2,c_3`
|
constraints : total 3 constraints
and right hand side constant `b_1,b_2,b_3`.
(`c_1` becomes `b_1`, `c_2` becomes `b_2`, `c_3` becomes `b_3`)
|
|
3. |
constraints : total 2 constraints
and right hand side constant `b_1,b_2`
|
Objective function : total 2 variables (`y_1,y_2`)
and coefficient `c_1,c_2`.
(`b_1` becomes `c_1`, `b_2` becomes `c_2`)
|
|
4. |
constraint is `<=` type
|
constraint is `>=` type
|
|
5. |
`x_i` unrestricted in sign
eg: `x_1` unrestricted in sign
|
`i^"th"` constraint is = type
eg: `1^"st"` constraint is = type
|
|
6. |
`i^"th"` constraint is = type
eg: `1^"st"` constraint is = type
|
`y_i` unrestricted in sign
eg: `y_1` unrestricted in sign
|
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
