Skip to content
Advertisements

QT/U3 Topic 5 Duality: Concepts, Significance

The Duality in Linear Programming states that every linear programming problem has another linear programming problem related to it and thus can be derived from it. The original linear programming problem is called “Primal,” while the derived linear problem is called “Dual”.

Before solving for the duality, the original linear programming problem is to be formulated in its standard form. Standard form means, all the variables in the problem should be non-negative and “≥,” ”≤” sign is used in the minimization case and the maximization case respectively.

The concept of Duality can be well understood through a problem given below:

Maximize

Z = 50×1+30×2

Subject to:

4×1 + 3×2 ≤ 100

3×1 + 5×2 ≤ 150

X1, x2 ≥ 0

The duality can be applied to the above original linear programming problem as:

Minimize

G = 100y1+150y2

Subject to:

4y1 + 3y1 ≥ 50

3y1 +5y2 ≥ 30

Y1, y2 ≥ 0

The following observations were made while forming the dual linear programming problem:

  1. The primal or original linear programming problem is of the maximization type while the dual problem is of minimization type.
  2. The constraint values 100 and 150 of the primal problem have become the coefficient of dual variables y1and y2 in the objective function of a dual problem and while the coefficient of the variables in the objective function of a primal problem has become the constraint value in the dual problem.
  3. The first column in the constraint inequality of primal problem has become the first row in a dual problem and similarly the second column of constraint has become the second row in the dual problem.
  4. The directions of inequalities have also changed, i.e. in the dual problem, the sign is the reverse of a primal problem. Such that in the primal problem, the inequality sign was “≤” but in the dual problem, the sign of inequality becomes “≥”.
Advertisements
Advertisements
Advertisements

1 Comment »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: