解析对偶理论与对偶单纯性法
摘要:对偶理论(Duality theory)就是研究线性规划中原始问题与对偶问题之间关系的理论。
本文分享自华为云社区《对偶理论与对偶单纯性法》,原文作者:井冈山_阳春 。
线性规划(Linear Programming,简称LP)是运筹学中研究较早、发展较快、应用广泛、方法较为成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。对偶理论(Duality theory)就是研究线性规划中原始问题与对偶问题之间关系的理论。
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)。
最后,给出对偶单纯形法的具体步骤:
相关文章
- 一张图系列——为什么在DllMain里面创建了线程并Wait会卡死
- 华为云物联网高级攻城狮的4年配置中心实践分享
- 组合式应用新利器?SaaS新时代事件网格如何解决集成标准化问题
- 梳理数仓FI manager节点健康检查逻辑
- 一次简单易懂的多态重构实践,让你理解条件逻辑
- 三问三答,解传统企业敏捷转型担忧
- 云图说丨叮咚,您有一份短信通关攻略待查收
- 教你用ab命令进行并发与压力测试
- STM32+华为云IoTDA,带你设计一个属于自己的动态密码锁
- 独家下载!突破开源Redis,华为云十年自研内核修炼之路《企业级Redis技术与应用解读》重磅发布
- CVE-2022-22965 漏洞分析,安全问题早发现
- 解构华为云HE2E项目中的容器技术应用
- 华为云NFT云宝限量开抢,区块链技术为你的数字资产保驾护航
- SimpleDateFormat类的安全问题,这6个方案总有一个适合你
- 上海理工大学:巧用数字技术打响智慧抗疫信息战
- 要想推荐系统做的好,图技术少不了
- 坐实大数据资源调度框架之王,Yarn为何这么牛
- 云图说丨不同区块链之间如何跨链交互?
- 如何使用参数化查询提高Cypher查询的性能
- 从趋势到必选项,探讨企业数字化转型方式方法