关于模型:解析对偶理论与对偶单纯性法

摘要： 对偶实践（Duality theory）就是钻研线性规划中原始问题与对偶问题之间关系的实践。

本文分享自华为云社区《对偶实践与对偶单纯性法》，原文作者：井冈山_阳春。

线性规划（Linear Programming, 简称 LP）是运筹学中钻研较早、倒退较快、利用宽泛、办法较为成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。对偶实践（Duality theory）就是钻研线性规划中原始问题与对偶问题之间关系的实践。

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

再比方，生产打算问题，如图一所示，某工厂要生产两种产品 I 和 II，生产原料别离是 A 和 B，且对总的生产设施台时也有限度，

那么，别离生产多少件产品 I 和 II，能力使生产的利益最大化，很显然，从卖家的角度，利用线性规划，失去的优化模型 M1：

其中 x1 和 x2 别离是打算生产产品 I 和 II 的件数。换一个角度，从买家的角度，不买产品二是间接买生产原料，从盈利的角度登程假如每件生产原料的价格跟别是 y1、y2 和 y3，买家心愿购买的老本是最小的，于是有了上面的优化模型 M2：

以上是两个阐明对偶问题的例子。上面间接给出原问题和对偶问题的对应关系表：

这种对应关系是能够通过拉格朗日对偶推导失去的，这里不作具体介绍，感兴趣的同学能够参考 https://www.zhihu.com/questio…。

规范 LP 问题：

对偶问题：

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

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

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

首先从大的概念上，对原始单纯形法和对偶单纯形法做一下了解：

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

最初，给出对偶单纯形法的具体步骤：

点击关注，第一工夫理解华为云陈腐技术~

1. 对偶问题的提出