Duality in LP: Construct the Dual, Solve a Worked Example, and Apply Key Properties

Forming an LP dual is easy to get almost right. One missed transpose, reversed inequality, or wrong sign restriction changes the entire problem, even when the algebra still looks tidy.

The reliable route is matrix-first: transpose A, exchange b and c, then assign inequality senses and sign restrictions from the primal form. In the worked pair, x* = (2,3) and y* = (9/4,1/4) both give 21; weak duality, strong duality, and complementary slackness independently certify the optimum.

Duality in LP: read the primal and dual as one matrix pair

Start with the canonical primal

P: maximise c^T x subject to Ax <= b, x >= 0.

Its dual is

D: minimise b^T y subject to A^T y >= c, y >= 0.

If A is an m x n matrix, the primal has n variables and m constraints. The dual has m variables and n constraints. Each primal constraint creates a dual variable, while each primal variable creates a dual constraint. The vector b supplies the dual objective coefficients, c becomes the dual right-hand side, and A is transposed, not copied.

For any feasible x and y, the bound follows in one line:

c^T x <= x^T A^T y = y^T Ax <= y^T b.

This topic belongs within broader GATE CS Exam Preparation, but the construction itself is pure linear algebra and inequalities.

Construct the dual coefficient by coefficient

Use this running primal:

Maximise z = 3x1 + 5x2
subject to
    x1 + 2x2 <= 8
   3x1 + 2x2 <= 12
    x1, x2 >= 0

Create y1 for the first constraint and y2 for the second. A maximisation primal with <= constraints gives y1, y2 >= 0. Move the right-hand sides into the objective: minimise w = 8y1 + 12y2.

Now read down each column. The x1 column is (1,3), and its primal objective coefficient is 3, so y1 + 3y2 >= 3. The x2 column is (2,2), and its coefficient is 5, so 2y1 + 2y2 >= 5.

The completed dual is:

Minimise w = 8y1 + 12y2
subject to
    y1 + 3y2 >= 3
   2y1 + 2y2 >= 5
    y1, y2 >= 0

Dual construction with mixed inequalities, equalities, and free variables

For a primal maximisation problem, use this rule table:

The mirrored canonical form, minimise c^T x subject to Ax >= b, x >= 0, has dual maximise b^T y subject to A^T y <= c, y >= 0. Always identify the canonical form before applying memorised arrows.

The sign of yi comes from the corresponding constraint sense, not the right-hand-side sign. A free variable is unrestricted in sign, not zero.

Solve the primal LP at every corner

The two boundaries meet where

x1 + 2x2 = 8 and 3x1 + 2x2 = 12.

Subtracting gives 2x1 = 4, hence x1 = 2. Substitution gives 2 + 2x2 = 8, hence x2 = 3.

A linear objective over this bounded feasible polygon reaches its optimum at a vertex, so evaluating every feasible corner is sufficient.

Therefore, x* = (2,3) and z* = 21.

For the graph, x1 + 2x2 = 8 crosses at (8,0) and (0,4). The line 3x1 + 2x2 = 12 crosses at (4,0) and (0,6). The feasible region is in the first quadrant below both.

A non-optimal feasible point is x = (1,2). At x = (1,2), the left sides are 1 + 4 = 5 <= 8 and 3 + 4 = 7 <= 12. Its objective is z = 3 + 10 = 13.

Solve the dual and verify weak and strong duality

At the intersection of the active dual boundaries,

y1 + 3y2 = 3 and 2y1 + 2y2 = 5.

Divide the second equation by 2 to obtain y1 + y2 = 5/2. Subtracting this from the first gives 2y2 = 1/2, so y2 = 1/4 and y1 = 9/4.

Thus y* = (9/4,1/4) and w* = 21. Weak duality is visible using the earlier feasible points: primal x = (1,2) gives 13, while dual y = (3,0) gives 24, so 13 <= 24. Strong duality appears at the optima: c^T x* = 21 = b^T y*.

This equality is an optimality certificate. If feasible primal and dual points have equal objectives, weak duality leaves no space to improve.

Complementary slackness and shadow values from the same optimum

For this pair, complementary slackness requires

yi(bi - (Ax)i) = 0 and xj((A^T y)j - cj) = 0.

At x* = (2,3), both primal slacks vanish:

• 8 - (2 + 6) = 0

• 12 - (6 + 6) = 0

At y* = (9/4,1/4), both dual surpluses also vanish:

• (9/4 + 3/4) - 3 = 0

• (18/4 + 2/4) - 5 = 0

A positive yi forces its corresponding primal constraint to bind. A positive xj forces its corresponding dual constraint to bind. A zero variable alone does not prove that the opposite constraint is slack.

The values y1* = 9/4 and y2* = 1/4 are local shadow values. Raise the first right-hand side from 8 to 9. The same active basis gives (x1,x2) = (3/2,15/4), with objective 3(3/2) + 5(15/4) = 18/4 + 75/4 = 93/4 = 23.25, an increase of 9/4.

Raise the second right-hand side from 12 to 13. The active equations give (5/2,11/4), and the objective is 3(5/2) + 5(11/4) = 30/4 + 55/4 = 85/4 = 21.25, an increase of 1/4. This interpretation holds only while the optimal basis remains unchanged.

LP duality properties, exam patterns, and traps

A primal unbounded above makes the dual infeasible, as any feasible dual gives a finite upper bound. A dual unbounded below makes the primal infeasible. Do not reverse blindly: an infeasible primal may pair with an infeasible dual.

Rapid checks: y = (9/4,1/4) gives dual sides 3 and 5, while x = (2,3) uses resources 8 and 12.

Minimum Spanning Tree for GATE covers graph optimisation, and Dynamic Programming Explained: 0/1 Knapsack builds answers from overlapping subproblems. Both are useful next stops once dual construction feels routine.

Duality in LP: the short version and next step

Use five steps: identify the canonical form, swap max and min, exchange b and c, transpose A, then check every sign and inequality sense. Remember the certificate x* = (2,3), y* = (9/4,1/4), and z* = w* = 21.

For the full GATE CS teaching sequence, use GATE Guidance by Sanchit Sir. For mixed timed practice, move to the GATE Test Series: Mocks and Topic-wise Tests.