线性规划及单纯形法

线性规划是最优化问题的一种特殊情形，实质是从多个变量中选取一组合适的变量作为解，使得这组变量满足一组确定的线性式（约束条件），而且使一个线性函数（目标函数）达到最优

〇． 前言

不少人对线性规划问题还只有初高中“图解法”的印象。能使用图像直观明了地解题自然是一种好方法，相信很多人都认为一种好方法够解决需要解决的问题不就足矣了吗。其实我也不例外。这也是我开始接触时的疑惑。但学了一阵子后，我思索了，确实，相比较几何和组合推理，代数学确实在非数学专业的学生看来不够讨喜，尽管代数学相当强大、相当普适……单纯形法就是代数的一个小小缩影，它似乎表面上让线性规划问题变得比“图解法”要复杂得多，但是其超强的普适性着实迷人，我们用计算机来解决线性规划问题可能只要一句编程，但其背后的数学原理却如此丰富。我们光线性规划问题就学了9周（还没上完），可见它背后的数学文化还是相当值得深挖研讨的……<其实为了应试【捂嘴】>
因为单纯形法经过本人预习复习后已经有些开窍了，并成功用大M法解决了我的大作业，所以在此不过多赘述，有兴趣可以去了解【我更倾向于你没兴趣，看完你就知道了】不过鉴于这周要测验，而对偶问题还是迷迷糊糊的我决定开始摸鱼做笔记<说白了就是应试>，希望敲完这篇，我可以把线性规划的对偶理论啃下来吧……<说白了还是为了应试>

果然，第一次还是给了数学……哎嘿~~

一． 对偶问题的提出

无论从理论或是实践角度，对偶理论是线性规划中的一个最重要和有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的时候，也同时给出了另一问题的解。下面通过实际例子看待对偶问题的经济意义。
<书本上的例子实在是过于晦涩难懂，于是在网上摘了一点好理解的“栗子”……>

【例一】
某工厂用甲乙两种资源生产A、B、C、D四种产品，现有资源数、单位产品所需资源数以及单位产品可获得利润如下表所示。问如何组织生产能够使得利润最大？

根据题意列出的线性规划不等式是这样的（大家不用去推出这个公式，目的在于和下文的对偶问题公式形成对比）：

但是现在如果从另一个角度考虑问题。假设该厂不生产A、B、C、D四种产品，而是将甲、乙两种资源出租给其他单位，其原则是：识别的单位愿意租，又使本单位获利不低于原利润。问如何给甲、乙两种资源定价最合理？

根据题意列出的线性规划不等式是这样的：

可以发现，两个问题下的线性规划公式很相似（具体的如何转换会在下文予以说明）。那么两个问题具有什么样的实际意义呢？可以考虑该厂的目的现在是想要出租资源但是要保证价格不低于资源变成产品所带来的收益。也就是说第二个问题所求出来的最小(优)值应该是第一个问题求出的最大(优)值，换句话说我们可以通过原问题的对偶问题的最优值来获得原问题的最优值，但为什么要这样做呢？直接用原问题来求得最优值不可以吗？这就是我们第二个问题所涉及的了。

【例二】
① ：仔细对比上图两种式子可以发现，图一中的变量较多而且约束条件较少，相信大家都做过线性规划的问题，不难发现变量越少，约束条件越多对于我们的求解就越有利。这里也是这个道理，通过将原问题转换成为其对偶问题，可以使得更加有利于我们求解线性规划问题，并且从问题一的解答中我们了解到两种问题“本是同根生”，所以对偶问题其实是有利于我们计算复杂线性规划问题的一种"辅助"方式。但是，对偶问题一定比原问题变量要少吗？并不是这样的，但是我们可以非常容易的判断出该问题的对偶问题会不会更简单，这个方法涉及到对偶问题的转换，我们在第三个问题中进行解答。
② ：其实有时不仅仅是为了减少变量的个数，有的问题甚至必须要通过转换称为对偶问题才能够解决(博主目前的水平下，非数学专业)，比如为了将原式化成标准式时会出现(不)等式右端出现负数的情况，这时如果仅用单纯形法是不能够解决的，因此从这个角度来看，为应对考试对偶问题是必须要学习的。

【例三】
接下来我们将进入实战，直接用实例来讲解原问题的对偶问题是如何化成的。首先我们以下面这个线性规划问题为例：

1. 对偶问题的目标函数和原问题是相反的，原问题是min则对偶问题为max。并且变量的个数也会发生改变，系数是原问题不等式右端的b值(仅仅是化为对偶问题是不需要将原问题化作标准式的)。根据以上得出目标函数：
   
2. 接下来是写约束条件，约束条件的书写是最容易出错的地方。我们先写等式的左端，对偶问题等式的左端是根据原问题等式左端竖着来写的；等式的右端就是直接用原问题目标函数中的系数(先不考虑符号),也就是看如下画红框的部分：
   
3. 根据原问题竖着的系数来作为对偶问题每个等式中变量的系数；原问题目标函数的系数，可以得出如下（先仔细看下红框里的数据是如何得到的）：
   
4. 接着是最为重点的约束条件中的符号和变量的范围符号，这两点是根据如下来进行变换：
   
   解释： 根据max类型写min类型的变量符号时，要根据max的约束条件符号，并且与之相反；写min的约束条件符号时，要根据max类型的变量符号，并且与之相同。反之亦然。另外无约束对应的是‘ = ’。最终得到：
   
   至此，我们已经讲完了对偶问题的转换方法，下面再举一个max类型转换成min类型的例子，大家可以对照练习加深印象。
   
   <因为壳子比较菜又比较摸鱼还不会举“栗子”，所以第一部分的“栗子”都是从优秀博主家摘的……后面有走心原创哦~~>

二． 对称形式下对偶问题的一般形式

<你们最爱的 纯数学理论来辣~~~>
定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”号，当目标函数求极小时均取“≥”号。
对称形式下线性规划原问题的一般形式为：

用yi(i=1,…,m)代替第i种资源的估价，则其对偶问题的一般形式为：

用矩阵形式表示，对称问题的线性规划问题的原问题为：

其对偶问题为：

上述对偶问题中令w’=-w，可改写为：

将上述对称形式下线性规划的原问题与对偶问题进行比较，可以列出如下表的对应关系：

如将其作为原问题，并按上表所列对应关系写出它的对偶问题则有：

再令z=-z’，则上式可改写为：

可见对偶问题的对偶即原问题。因此将表中右端的线性规划问题作为原问题，写出其左端形式的对偶问题。

三． 非对称形式的原-对偶问题关系

因为并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。考虑下面例子：
<随便举个栗子啊>
【例四】 写出下述线性规划问题的对偶问题：

解：

为了写出对偶问题，思路是先将其转化成对称形式，再按上表的对应关系来写。因例中目标函数为max，故约束条件应变换为“≤”号，所有的变量均应为≥0.为此：
<emmm…好像忘了给方程标号了…随手就标，养成好习惯>

<好了，go on…>

（1）约束条件b两端乘上“-1”；
（2）将约束条件c先等价转换为x1+x2+x3≤4和x1+x2+x3≥4，再变换为x1+x2+x3≤4和-x1-x2-x3≤-4；
（3）令x2’=-x2，所以x2’≥0；
（4）令x3=x3’-x3’’，其中x3’≥0，x3’'≥0。

由此【例四】可变换成具有如下对称形式的线性规划问题：

令对应上述4个约束条件的对偶变量分别为y_1,y_2^’,y_3’,y_3^’’，按表的对应关系写出其对偶问题为：

再令y2=y2’,y3=y3’-y3’’,将第三四个约束条件改为一个等式-5y1-6y2’+y3=3，于是有：

将上述对偶问题同【一】的原问题对比发现，无论对称或非对称的线性规划问题在写出其对偶向题时，表中前4行的对应关系都适用，区别的只是约束条件的形式与其对应变量的取值。根据本例中约束和变量的对应关系，下面将对称或不对称线性规划原问题同对偶问题的对应关系，统一归纳为下表所示形式：

<看到这里是不是感jio要吐了……而这才只到如何写线性规划的对偶问题，你还没解呢……急啥，快到性质了……>

四． 对偶问题的基本性质

<这里才是你真正应该感jio到要吐的地方…>
<还是决定手写，这里敲公式多半会哭死……>

1. 弱对偶性

·弱对偶性的推论：
（1） 原问题任一可行解的目标函数值时其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。<有点儿绕，但不是不好理解>
（2） 如原问题有可行解且目标函数值无界（具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。
（3） 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解时，其对偶问题的目标函数值无界。

2. 最优性

3. 强对偶性（或称对偶原理）

若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。

证 由于两者均有可行解，根据弱对偶性的推论（1），对原问题的目标函数值具有上界，对偶问题的目标函数值具有下界，因此两者均具有最优解。当原问题为最优解时，其对偶问题的解为可行解，且有z=w，由最优性知，这时两者的解均为最优解。

4. 互补松弛性

5.基解互补性
原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量对偶问题的剩余变量对应原问题的变量.这些互相对应的变量如果在一个问题的解中是基变量则在另一个问题的解中是非基变量；将这对互补的集解分别带入原问题和对偶问题的目标函数中有 z = w

五． 对偶问题的单纯形法描述

<听嗦考试必考……但其实我并不熟悉，慌~~>
既然是只菜狗，那就参考一下大佬的吧：
参考链接：
对偶问题的单纯形法

六． 影子价格

首先，我们先要认识到互补松弛性的作用：
① 简化求对偶问题最优解过程 : 已知一个线性规划问题的最优解 , 可以 简化求另外一个问题最优解的过程 , 避免使用两次单纯形法求解 ;
② 影子价格问题 : 使用互补松弛定理可以进行一些 经济解释 , 如影子价格问题 ;
影子价格 是 对偶问题的 经济解释 ;

影子价格是对偶问题的变量值
<懒了，不想举“栗子”了，有关边际价格的“栗子”还挺多的，有兴趣可以在*“参考”*里摘摘>

七． 利用Matlab解决线性规划问题

因为毕竟是计算机系的在读小学生，那就提一嘴实战应用咯。因为linprog这个函数比较常用，也是建模赛事中最最最基础的数学模型了，所以对于大家也不陌生。不过你想要用好它可不止单纯会敲一个linprog那么easy，至少你要知道线性规划的标准型，这样才能套对参数，合理求解线性规划问题。
所以简单截个图：<就是懒？不（shi）是（de）>

八． 参考

链接[1]: https://blog.csdn.net/qq_43539633/article/details/109150749
链接[2]: https://blog.csdn.net/PursueLuo/article/details/112251520
链接[3]: https://blog.csdn.net/weixin_43848054/article/details/105748797
链接[4]: https://blog.csdn.net/shulianghan/article/details/112096559
《运筹学教程》 胡运权 郭耀煌