对偶理论与对偶单纯性法

举报
井冈山_阳春 发表于 2021/06/26 15:05:53 2021/06/26
【摘要】 对偶理论与对偶单纯性法1. 对偶问题的提出对偶是对同一问题,从两种不同角度观察,有两种拟似对立的表述。例如“矩形面积与周长的关系”有如下两种表述:周长一定,面积最大的矩形是正方形;面积一定,周长最短的矩形是正方形。再比如,生产计划问题,如图一所示,某工厂要生产两种产品I和II,生产原料分别是A和B,且对总的生产设备台时也有限制,那么,分别生产多少件产品I和II,才能使生产的利益最大化,很显然...

对偶理论与对偶单纯性法

1. 对偶问题的提出

对偶是对同一问题,从两种不同角度观察,有两种拟似对立的表述。例如“矩形面积与周长的关系”有如下两种表述:

  • 周长一定,面积最大的矩形是正方形;

  • 面积一定,周长最短的矩形是正方形。

再比如,生产计划问题,如图一所示,某工厂要生产两种产品I和II,生产原料分别是A和B,且对总的生产设备台时也有限制,

那么,分别生产多少件产品I和II,才能使生产的利益最大化,很显然,从卖家的角度,利用线性规划,得到的优化模型M1:

其中x1和x2分别是计划生产产品I和II的件数。换一个角度,从买家的角度,不买产品二是直接买生产原料,从盈利的角度出发假设每件生产原料的价格跟别是y1、y2和y3,买家希望购买的成本是最小的,于是有了下面的优化模型M2:

以上是两个说明对偶问题的例子。下面直接给出原问题和对偶问题的对应关系表:

这种对应关系是可以通过拉格朗日对偶推导得到的,这里不作具体介绍,感兴趣的同学可以参考https://www.zhihu.com/question/58584814

2. LP标准问题的对偶问题

标准LP问题:

对偶问题:

对原问题与对偶问题解的关系做一些简单的推导:

其中xB和xN分别对应基变量和非基变量,B和N是基变量和非基变量对应的矩阵,cB和cN对应代价系数。由以上的推导可以看出,对偶问题的解与原问题的检验数有对应关系,这个关系对于理解对偶单纯形法非常重要。

3.对偶问题的性质

3.1 对称性

3.2 弱对偶性

弱对偶性表明,只要找到原问题和对偶问题的一个可行解,则能够确定彼此的上下界。由弱对偶性可以得到两个重要的推论:


3.3 强对偶性

3.4 最优性条件

4. 对偶单纯性法

首先从大的概念上,对原始单纯形法和对偶单纯形法做一下理解:

接下来推导对偶单纯形法,实际上对偶单纯形法和单纯形法主要的区别就在与进基和出基的策略不一样,下面具体介绍对偶单纯形法进基和出基策略的推导,需要强调的是,对偶单纯形法推导的前提是初始解满足对偶可行性(原问题的检验数都大于0)。

最后,给出对偶单纯形法的具体步骤:

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200