Duality

Posted in Operations and Supply Chain Terms, Total Reads: 1156
Advertisements

Definition: Duality

The linear programming problem addresses resource allocation and also resource valuation. While the resource allocation is solved using the primal problem, the value of each resource is identified using the dual problem.


Every linear programming problem which has a primal problem can also be converted into a dual problem. The rules for converting a primal into a dual problem are as follows:

Primal

Dual

Decision variable: x

Decision variable:y

Max Z=cx

Min Z=by

Such that

 

Ax<=b

yA>=c

 

 

 

For any primal and dual problem all relationships between them must be symmetric.

Primal

Dual

Obj function: Max

Min

If constraint is

Variable is

<=

>=0

>=

<=0

=

 

If variable is

Constraint is

>=0

>=

<=0

<=

URS

=


Duality theorem:

Weak Duality

– If a constraint is inactive in an optimal solution of the primal problem then corresponding dual variable equal to zero .

– Or an inactive constraint in an dual problem will have its corresponding variable equal to zero in primal solution


Strong Duality:

If constraint is active then corresponding dual variable is unequal to zero. Conversely an active constraint of the dual problem will have its corresponding variable unequal to zero.


Advertisements



Looking for Similar Definitions & Concepts, Search Business Concepts