首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >线性规划中的可行、有界原始但不可行的对偶

问线性规划中的可行、有界原始但不可行的对偶
EN

Stack Overflow用户
提问于 2018-12-08 14:09:07
回答 1查看 502关注 0票数 0

我有一个线性规划问题,它有一个原始形式的最优解,但我似乎找不到它的对偶问题的最优解或一般解。这有可能吗?

最基本的是:

代码语言:javascript
复制
min -4x + y
subject to 
5x - 2y <= 3
3x + y <= 2
x,y >= 0

这给出了最优解x=7/11,y=1/11。

双重问题是:

代码语言:javascript
复制
max 3x' + 2y'
subject to
5x' + 3y' <= -4
-2x' + y' <= -1
x',y' <= 0

这没有解决方案。我计算对偶是错的,还是这是可能的?

EN

回答 1

Stack Overflow用户

发布于 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。我们可以通过以下方式轻松获取此表单中的原始数据:

代码语言:javascript
复制
min  -4x + y
s.t. -5x + 2y >= -3
     -3x - y >= -2
      x,y >= 0

相应的dual是:

代码语言:javascript
复制
max  -3a - 2b
s.t. -5a - 3b <= -4
     2a - b <= 1
     a, b >= 0

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

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/53680049

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档