运筹学教学|十分钟快速掌握单纯形法（附C++代码及算例）
运筹学教学|十分钟快速掌握单纯形法（附C++代码及算例）
不如今儿咱就来讨论一下去哪玩耍吧！
南京？丽江？西安？……
众人（汗）：一个月前就没票了。。。
哦……那么，就只能……学习了……
好巧不巧，运筹学似乎没学完吧？
前几日有童鞋跟小编说，
深夜看了咱公众号运筹学最大流、最短路算法的教学，
在修仙的道路上又有了质的飞跃！
戳此了解或复习：
运筹学教学 | 十分钟快速掌握最大流算法（附C++代码及算例）
运筹学教学 | 十分钟快速掌握最短路算法（附C++代码及算例）
但就是……
信息量太大，
学完后有点虚，
快学不动了……
古语云：持之以恒，有朝一日，必可成仙。
这位同学再坚持一下……
（好吧前面那句话其实是我说的）
毕竟运筹学是一门博大精深的学问。
但小编非常体谅大家要亲亲抱抱举高高的心情，所以今天要教给大家的知识着实单纯小清新。怎么样，是不是开心到质壁分离？
那就快来看看今天的内容吧！
运筹学·教学笔记 第三弹 —— 单纯形法 （Simplex Algorithm）解 线性规划 问题。包你一学就会！怎么样，内容是不是真的很单纯？
内容提要：
＊什么是线性规划
＊线性规划的标准式和矩阵式
＊单纯形法的算法步骤
1
1
1
什么是线性规划
线性规划（Linear programming, 简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它辅助人们进行科学管理、寻找线性约束条件下线性目标函数的极值。它广泛应用于军事作战、经济分析、经营管理和工程技术等领域，为合理地利用有限的人力、物力、财力等资源做出最优决策，提供科学依据。
1
2
1
标准式VS矩阵式
标准式
由于目标函数和约束条件在内容和形式上存在多种差别，线性规划问题也存在着多种表达式。因此，为了便于讨论，在应用单纯形法时，规定线性规划问题必须有一个标准形式，主要包括以下三个特征：
1）目标函数统一为求极大值(或极小值)；
2）所有约束条件（除变量的非负条件外）必须都是等式，约束条件右端常数项(right-hand-side)b_i必须全为非负值；
3）所有变量的取值必须全为非负值。
下面的模型即为线性规划问题的标准形式：
s.t.括号内的内容是约束条件和变量的非负约束条件，字母代表的含义分别是：
下面模型即为标准形式的展开型：
可行解与 最优解
若找到(x_1, x_2 ,..., x_n)的值满足所有约束条件，且每个变量的值非负，则(x_1, x_2 ,..., x_n)称为线性规划问题的可行解。使目标函数值达到最大值（或最小值）的可行解即为该问题最优解，求解线性规划问题的目标就是要找出目标函数的最优解。
如何将目标函数转化为标准型
如下所示，线性规划问题往往并非标准形式。
因此，在用单纯形法求解前，需要将模型转化为标准形式。
这个过程包括四个部分的转换：
1. 目标函数的转换：
统一求极大值，若是求极小值，则可将下面的式子乘以（-1）。即：
转化为：
2. 变量的转换：
（1）对于已经是大于等于零的变量 x_j ≥ 0 不做变化；
（2）对于小于等于零的变量 x_j，取负号令其变为大于等于零的变量，即若 x_j ≤ 0，则 定义新变量x_j' = -x_j，x_j' ≥ 0；
（3）若 x_j 取值无约束，可令两个新的非负变量x_j', x_j'', 然后用x_j = x_j' - x_j''替换原问题中的x_j。
3. 约束条件的右端项常数的转换：
b_i < 0 时，只需将等式或不等式两端同乘（-1）；
4. 约束条件的转换：
将所有不等式全部转换为等式：
对于“≤ ”型约束加入一个变量 x_s，x_s ≥ 0；
对于“≥ ”型约束则减去一个变量 x_s，x_s ≥ 0。
加到原约束条件中的变量，称为松弛变量，在实际问题中它表示未被充分利用的资源或缺少的资源，所以在引入模型后它们在目标函数中的系数均为零。
给定线性模型的标准形式，为了构造出初始基变量，约束条件还可能需要加上人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
【Tips: 若原约束条件中已有线性无关的基向量，可以不需要再加入人工变量】
学完了以上的转化规则，让我们来实战一下！将上述的线性规划问题转化为标准形式，其结果应如下：
注：x_4, x_5是将自由变量x_3转化为非负变量而引入的新变量，x_6, x_7是松弛变量，x_8, x_9是人工变量。
对于聪明的你来说是不是很简单？
矩阵式
说完标准形式，再来说说为了运算简洁而生的矩阵式。因为表达方式简单，单纯形法的表示与定理的说明往往使用矩阵形式。上述标准形式的矩阵形式表示如下：
矩阵A如下式：
A为m×n矩阵。假设A的秩为m，即假设不存在冗余的约束条件，则m>n时，因为方程数量比变量数目多，必定有多个可行解，即可利用单纯形法来计算最优解。
1
3
1
单纯形法的算法步骤
使用单纯形算法求解线性规划，求解时只需输入线性规划问题的标准式 ——
一个大矩阵：
第一行为目标函数的系数，最后一个数字为当前基变量下的 z 值。
首行以下的每一行代表一个约束条件，数字代表系数，每行最后一个数字代表 b 值。
单纯形法解题步骤
1. 确定初始可行基和初始基可行解，
建立初始单纯形表；
2. 最优性检验 若在当前表的目标函数对应的行中，所有非基变量的系数非正，则可判断得到最优解，可停止计算。否则转入下一步；
3. 若单纯形表中1至m列构成单位矩阵，在j=m+1至n列中，若有某个对应x_k的系数列向量 P_k ≤ 0，则此问题是无界，停止计算。否则，转入下一步；
4. 挑选目标函数对应行中系数最大的非基变量作为进基变量。假设x_k为进基变量，按θ规则[1]计算，可确定x_l为出基变量，转下一步；
5. 以a_lk为主元素进行迭代（即用高斯消去法或称为旋转运算），把x_k所对应的列向量进行变换[2]；
6. 重复2-5步，直到所有检验数非正后终止，得到最优解。
[1] θ规则
其中b_i是当前表中的右手项，a_ik即为在第i个约束中变量k的系数。
[2] x_k列变换
单纯形法举例
对于线性规划问题：
加入松弛变量，转化为标准形式得：
于是我们可以构造单纯形表，其中最后一行有星号的列为基变量。初始基可行解为(x_4, x_5, x_6, x_7)。
在单纯形表中，我们发现非基变量x的系数大于零，因此可以通过增加这些x的值，来使目标函数增加。
上表中c_2最大，因此我们选择x_2作为新的基变量。按照θ规则，x_7出基。通过高斯变换得到的新的单纯形表为：
继续计算，我们得到：
此时我们发现，所有非基变量的系数全部非正，即增大任何基变量的值并不能使得目标函数增大。于是我们可以断定该问题的最优解是z = 32, X = (0, 1, 3, 0, 2, 0, 0).
恭~喜~大~家~，到这里单纯形法的原理就
搞！定！啦！
如约而至的，仍旧是我们的代码(C++版)，若想获得代码.txt文件，可以直接滑到本文最后，点击“阅读原文”下载哦~下载只需复制黏贴即可，so easy~
代码展示
下面的代码仅仅是实现了教科书中的单纯形法的流程，线性规划商业软件在实际单纯形法的时候，会考虑约束条件的合理性以及可能出现退化等诸多复杂情况，因此，商业软件中实现的单纯形法肯定比下面展示的算法要复杂的多。
1
END
编辑：唐清清（华中科技大学管理学院本科三年级，15295970390@163.com）
孙嘉轩（华中科技大学管理学院本科二年级，1143747930@qq.com）
代码：孙嘉轩、贺兴（华中科技大学管理学院本科三年级，hexing15@gmail.com）
指导老师：秦时明岳（professor.qin@qq.com）