0

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?

4

1 回答 1

1

不，这是不可能的。如果原始是可行且有界的，那么对偶也必须是可行且有界的，并且它们必须具有相同的最优目标值（这源于线性规划的强对偶性）。因此，您的结论是对偶一定是错误的。

一种标准的 primal/dual 设置是 primalmin c'x s.t. Ax >= b, x >= 0具有 dual max b'y s.t. A'y <= c, y >= 0。我们可以通过以下方式轻松获得您的原始数据：

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

对应的对偶是：

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

对偶有最优解 a=7/11，b=3/11 和最优目标值 -27/11，这正是最优原始目标值。

于 2018-12-08T13:54:46.327 回答