CODEWITHSUNDEEP
linear-programmingsimplex
gahhh
gahhh

Reputation: 1

Feasible, bounded primal but infeasible dual in linear programming

I have a linear programming problem that has an optimal solution in its primal form, but I can't seem to find an optimal solution, or a solution in general, to its dual problem. Is that possible?

The primal is:

min -4x + y
subject to 
5x - 2y <= 3
3x + y <= 2
x,y >= 0

This gives optimal solution x=7/11, y=1/11.

The dual problem is:

max 3x' + 2y'
subject to
5x' + 3y' <= -4
-2x' + y' <= -1
x',y' <= 0

This has no solution. Did I calculate the dual wrong or is this possible?

Upvotes: 0

Views: 1500

Answers (1)

josliber
josliber

Reputation: 44330

No, this is not possible. If the primal is feasible and bounded, then the dual must also be feasible and bounded and they must have the same optimal objective value (this follows from strong duality for linear programming). So the conclusion in your case is that the dual must have been misformulated.

One standard primal/dual setup is that primal min c'x s.t. Ax >= b, x >= 0 has dual max b'y s.t. A'y <= c, y >= 0. We can easily get your primal in this form with:

min  -4x + y
s.t. -5x + 2y >= -3
     -3x - y >= -2
      x,y >= 0

The corresponding dual is:

max  -3a - 2b
s.t. -5a - 3b <= -4
     2a - b <= 1
     a, b >= 0

The dual has optimal solution a=7/11, b=3/11 and optimal objective value -27/11, which is exactly the optimal primal objective value.

Upvotes: 1

Related Questions