上学期学习过系统分析课程，和运筹学大多内容是大差不差的。尽管可能考研要求更高，但对管理运筹学并没有那么恐惧和陌生。接下来的一系列专栏文章，就是来记录和整理准备运筹学初始的全部学习过程。

我认为这部分还是有必要去提一提的，虽说可能应试用不上，但没必要那么功利和心切。好好静下来看看运筹学定义和发展情况，我认为是比较有帮助的。

从历史发展来看，运筹学来源于军事、管理和经济研究三个方面。二战结束早期主要是解决军事应用问题，随着后续发展，运筹学也在工业、农业、经济等各领域有了广泛应用。从理论和应用观点看，线性规划可以说发展的最好。

运筹学还未有一个确切的定义，但许多定义都包含这类观点：应用现有科学技术，解决实际问题，为决策者提供定量依据。理想情况强调最优，但实际我们往往考虑次优、满意等概念。

人们在实际生产实践活动中，往往希望能利用有限的资源，去追求尽可能高的目标，或者花费尽可能少。因此，线性规划研究目的主要有两个：

一个规划模型三要素我们得知道：决策变量、目标函数、约束方程。以前咱高中就学过线性规划，不过一般是在理想的数学坐标系下，用一根线去平移平移，找最好的那根。现在我们需要做的是，如何把实际问题的一些变量和变量之间的关系，给它转换为一个数学模型。

这确实是需要一定训练的，不过咱们从理科过来，建立一般的线性规划模型还是比较轻松的。搞清楚目标是求什么，用哪些作为决策变量，也就是x，题目中又有哪些约束。看一下模型怎么写，书上的一些例题，相信很快能上手。

线性规划问题有三个特征：

确实，还真没怎么想过这个线性到底怎么准确表达，一般说到线性就想到是条直线，曲线就不是。还有就是线性代数。

线性规划模型有三种表达形式，一种是下面这样的一般形式，有什么都给你全写出来。

还有一种叫简化形式，就是用一些数学符号，比如累加符号等等，进行简写，比较方便。而且，写成这样数学符号的形式，我认为不仅更加优雅，对进行计算机求解也有帮助。因为用Lingo写代码的时候，就可以通过简化形式直接写出来。

最后一种叫矩阵向量形式，将各种变量写成矩阵向量。我反正看了很头疼，一般那些数学定理证明都是用这种形式。

这一章就是多练几个题目，试着把实际问题各种约束条件都用数学符号表达出来，问题应该不大。

线性规划的求解方法很多，1939年，“解乘数法”提出，1947年，美国数学家提出单纯形法。后续也有很多其他方法，但单纯形法最为普遍。

对于2维或者3维问题，图解法是一种可行的办法，也就是咱高中学那个。但没什么实用价值，我也不多说。

下面说一些线性规划模型解的术语概念。满足约束方程组的解就叫可行解，所有可行解的集合就叫可行域。使目标函数达到最优的解叫最优解。如果约束条件互相矛盾，没有公共解，则此模型无可行解。

如果目标函数值会一直变大或变小，也就是约束条件它是开放的，没办法约束在一个封闭范围内，这种状态叫无界解。如果约束条件只有一个解，比如x大于等于1，x小于等于1，x就只能取1，则此模型肯定有最优解（就它一个解嘛，只能选它），而且唯一，即唯一解。

这里还是要说一下，唯一解有几种情况，一种是上边说的，人家约束条件只有一个解，当然唯一了。还有一种是，满足约束条件的有很多，但只有一个可以满足最优，也是唯一解，这也是我们正常碰到的情况。

如果不止一个可行解，两个或两个以上，让目标函数达到最优，那么称模型有多重解。其实只要有两个及两个以上，模型肯定就有无穷多个解。因为是线性的，这两个解可以进行组合叠加。

综上，线性规划模型的解有：唯一解，无可行解，多重解和无界解四种情况。

为了方便数学问题的讨论以及相关理论的证明和利用计算机辅助计算，有必要规定一种标准形式，其有以下特点：

那么，如何将一般形式的模型转换为标准形式呢，主要方法如下：

（一）若目标函数为最小，则加一个负号求最大。 （二）若约束中有 < = = >=，可以减去一个多余变量。 （四）若存在没有非负约束的变量，将其换为两个非负变量相减。 （五）若存在决策变量 x k < 0 x_k= 0 xl​=−xk​,xl​>=0。

基本概念

首先是凸集，可以理解为某个点集，比如平面上的一块区域，如果在其中任意取两点，连接这两点的线段上所有点也在点集中，那这个点集就称为凸集。

直观上就是这个区域没有凹下去的地方。如果用数学语言表达：设K是n维欧式空间上的一个点集，若任意两点 X 1 , X 2 X_1,X_2 X1​,X2​都在K上，且点 α X 1 + ( 1 − α ) X 2 \alpha X_1+(1-\alpha )X_2 αX1​+(1−α)X2​ 也在 K 上，则称 K 为凸集。顶点就不多说，严格点是说不能被两个点线性组合表示。

我们可以发现，两点连线上的点可以用这两个端点来表示。

书上关于基的部分感觉写的有点难看下去，我就不按照书上写了。基是指系数矩阵的一个满秩子矩阵，一般几个不等式就几维矩阵。可以任意选取一个，但是为了利用单纯形法，我们选单位阵。基向量是基中各个列分量，一列就代表一个基向量。基变量是指基向量所对应的决策变量，剩余的决策变量就叫非基变量。如果让非基变量为0，得到的一组解叫作基解。如果这个基解满足非负条件，那这个解叫作基可行解。这组解对应的系数矩阵就是可行基。

基本定理

这部分讲实话我觉得让我证明我不会，虽然不影响后面做题，但我感觉能看懂最好。

定理2.1 约束条件 A X = b , X > = 0 AX=b,X>= 0 AX=b,X>=0 的线性规划问题的可行解集合是凸集。

定理2.2 线性规划问题的可行解X是基本可行解的充要条件是X的非零分量所对应的系数列向量线性无关。

定理2.3 线性规划问题的基本可行解X对应于可行域的顶点。

2.3结合2.1我感觉有点豁然开朗，这样就能直接去顶点上找最优了。

定理2.4 线性规划问题若有可行解必有基本可行解。

定理2.5 线性规划问题若有最优解，则一定可以在可行域的顶点上找。

我一来看这个的时候完全看不下去，不知道为什么要弄这一套。我就说说我自己的理解。这个典式就是在解释为什么单纯形法可以那样求出来最优解。典式的基本特征是约束条件中基变量对应的系数列向量构成了单位矩阵。而如果构成了单位矩阵的话，这个解就是顶点，而顶点一般是可行解。

好了，有了上面的一些理论基础，来说说单纯形法的求解步骤吧。

第一步：将模型化为标准型，基于约束条件方程组的系数矩阵，寻找单位阵，确定基向量。编制初始单纯性表。

单位阵一般找不到，如果单纯为了求解，没有经济意义的话，可以在保证非负的情况下，进行增广矩阵初等行变换，否则老老实实加人工变量。

第二步：计算检验数，判断是否达到最优，方法如下：

（1）如果所有检验数小于等于0，说明已经达到最优，计算停止。 （2）如果存在检验数大于0，但是所有检验数大于0的列中的系数都小于等于0，那么说明没有最优解，计算停止。

可以理解为找不到换出的变量，一般为约束条件不封闭，可以一直取往上取。

（3）如果至少存在一个检验数大于0，且所对应的列中系数至少有一个大于等于0，说明没有达到最优，继续迭代。

第三步：继续迭代，迭代过程如下： （1）确定换入变量，原则上选最大检验数对应的变量换入。 （2）确定换出变量： x j ∗ = m i n ( b i a i j , i = 1 , 2 , . . . , m ) x_j^* =min(\frac{b_i} {a_{ij}},i=1,2,...,m) xj∗​=min(aij​bi​​,i=1,2,...,m) （3）换入换出后，对增广矩阵进行初等行变换，构造新单位阵。 （4）计算机会费用 z j z_j zj​和检验数，返回第二步。

为了解决找不到单位阵的问题，可以构造人工变量，目标函数最大时，其目标函数系数为-M（目标函数最小则目标系数为M），M为充分大的数，可以保证进入最优解概率很小。

之后正常进行单纯形法。需要注意的是，最后的基变量中不能含有人工变量，如果含有，说明原问题就无可行解。

两阶段法其实和大M差不太多，两阶段法的第一阶段是构造人工变量，目标函数系数取-1（求最大，求最小取1），其余全为0。然后迭代到最优，如果此时基变量中没有人工变量，进入下一阶段。把人工变量的列去掉，恢复原本的目标函数系数，重新检验迭代。

这一节主要是如何根据单纯形法表判断解的情况。

1.无可行解 基变量中包含一个或多个非0的人工变量。 2.多重解 在最优单纯形法表中，如果存在检验数为0的非基变量，那么线形规划模型就有多重解。因为把这个检验数为0的非基变量换进去的话，同样可以得到最优目标函数值。 3.无界解 所有能作为换入变量所对应的系数列向量均不存在大于等于0. 4.退化现象 如果出现基变量等于零，就会造成基本可行解中非零变量的个数小于约束条件方程的个数。表现为换出变量同时有两个或两个以上。