运筹学单纯形法（单纯形法简单例题详解）
运筹学单纯形法(单纯形法简单例子的详细说明)
该账号为华为云开发者社区官方运营账号，提供全面深入的云计算前景分析、丰富的技术干货和程序样本，分享华为云前沿信息动态。
本文分享自华为云社区《对偶理论与对偶简约定律》。原作者:井冈山_阳春。
线性规划是运筹学的一个重要分支，研究早、发展快、应用广、方法成熟。它是一种辅助人们进行科学管理的数学方法。对偶理论是研究线性规划中原始问题和对偶问题之间关系的理论。
1.提出对偶问题
二元性是指同一个问题。从两个不同的角度看，有两种准对立的表述。例如，“矩形面积和周长之间的关系”有以下两个表达式:
有一定周长且面积最大的矩形是正方形；
具有一定面积和最短周长的矩形是正方形。
另一个例子是生产计划问题。如图1所示，一个工厂要生产两个产品I和II，原材料分别是A和B，对生产设备总小时数也有限制。
那么，可以分别生产多少件产品一和二，使生产效益最大化。显然，从卖方的角度出发，利用线性规划，我们得到了优化模型M1:
X1和x2分别是计划产品I和II的数量。从另一个角度来看，从买方的角度来看，第二种是直接购买原材料而不是产品。从利润的角度来看，假设每种原材料的价格为y1、y2、y3，购买者想要购买的成本最小，那么下面的优化模型M2是可用的:
这是两个例子来说明对偶问题。下面直接给出了原问题和对偶问题的对应关系表:
这种对应关系可以通过拉格朗日对偶推导出来，这里不具体介绍。感兴趣的学生可以参考https://www.zhihu.com/question/58584814.
2.线性规划标准问题的对偶问题
标准LP问题:
二元性问题:
对原问题的解和对偶问题的解之间的关系做一些简单的推导:
其中xB和xN分别对应基变量和非基变量，b和n是对应基变量和非基变量的矩阵，cB和cN对应成本系数。从以上推导可以看出，对偶问题的解与原问题的检验数之间存在对应关系，这对理解对偶单纯形法非常重要。
3.对偶问题的本质
3.1对称性
3.2弱对偶
弱对偶表明，只要找到原问题和对偶问题的可行解，就可以确定彼此的上下界。从弱对偶可以得出两个重要的推论:
3.3强二元性
3.4最佳条件
4.双重简化法
首先，从大的概念出发，理解本原单纯形法和对偶单纯形法:
接下来，我们推导对偶单纯形法。事实上，对偶单纯形法和对偶单纯形法的主要区别在于它不同于基地进入和基地退出的策略。在这里，我们将详细介绍对偶单纯形法的基入口和基出口策略的推导。需要强调的是，对偶单纯形法推导的前提是初始解满足对偶可行性(原问题的检验数大于0)。
最后，给出了对偶单纯形法的具体步骤:
上一篇：最宝贵的话是什么成语（最宝贵的话金玉良言）