我有一个线性规划问题,它有一个原始形式的最优解,但我似乎找不到它的对偶问题的最优解或一般解。这有可能吗?
最基本的是:
min -4x + y
subject to
5x - 2y <= 3
3x + y <= 2
x,y >= 0这给出了最优解x=7/11,y=1/11。
双重问题是:
max 3x' + 2y'
subject to
5x' + 3y' <= -4
-2x' + y' <= -1
x',y' <= 0这没有解决方案。我计算对偶是错的,还是这是可能的?
发布于 2018-12-08 21:54:46
不,这不可能。如果原始是可行和有界的,那么对偶也必须是可行和有界的,并且它们必须具有相同的最优目标值(这源于线性规划的强对偶性)。因此,在您的案例中得出的结论是,双重肯定被错误地表述了。
一种标准的原始/双设置是原始min c'x s.t. Ax >= b, x >= 0具有双max b'y s.t. A'y <= c, y >= 0。我们可以通过以下方式轻松获取此表单中的原始数据:
min -4x + y
s.t. -5x + 2y >= -3
-3x - y >= -2
x,y >= 0相应的dual是:
max -3a - 2b
s.t. -5a - 3b <= -4
2a - b <= 1
a, b >= 0对偶有最优解a=7/11,b=3/11,最优目标值-27/11,这正是最优原始目标值。
https://stackoverflow.com/questions/53680049
复制相似问题