【快速入门|文末福利】运筹学|初识线性规划（一条逻辑线，只需初中数学基础）

标签：约束条件变量线性规划形式约束初识文末函数

导学问题/回忆自测

三个核心问题

“线性”为何？
何谓“标准”？
如何“化归”（把一般的线性规划问题转化为标准的线性规划问题）

提示

字面意思，在三个要素、两个关系之间
对三个要素的要求“大”、“大”、“等”
反转（乘以-1）/补齐/“分身”

逻辑线索

（逻辑线索中，发现有不熟悉的名词没关系，知识点部分会详细说；看完了知识点可以再回头看看逻辑线索辅助记忆，最后再看三个导学问题是不是都掌握了~）

我们需要解决的实际问题当中，有一类问题可以被归为规划问题

最终的目标可能是需要规划得到最好的经济效益，也可能是要规划使用最少的资源

为了解决这样的问题，我们进行数学建模

对应实际问题的需求，在数学模型中，三个关键要素是决策变量（Decision Variables）、目标函数（Objective Function）、约束条件（Constraints）

对于这三个要素而言，思考一下会发现他们之间有这样的关系：目标函数是由决策变量构成的，约束条件也是对决策变量的约束

让我们先考虑相对简单的问题：那么如果这个函数是线性的，这个约束是等式或不等式约束

这时候模型就被称为线性规划模型

为了统一讨论，我们再在其中选取大家容易接受的求最大值、等式约束、非负约束，规定这样的形式是标准形式

因此只要我们学会了求解一般形式，以后只要能把线性规划问题转化为标准形式，就能够求解相应问题

在这一课中，我们先学会如何将一个线性规划问题转化为标准形式

知识点

线性规划问题的数学表示

一般形式

我们先来看看上述逻辑当中一开始提到的线性规划问题的一般形式

数学上可以表达为：

目标函数：

$max(min) Z = c_1x_1+c_2x_2+\cdots+c_nx_n\\$

约束条件：

$s.t.\left\{ \begin{array}{rcl} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n & \leq(= / \geq ) & b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n & \leq(= / \geq ) & b_2 \\ \cdots & & \\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n & \leq(= / \geq ) & b_m \\ x_1\geq 0, \cdots ,x_n \geq0&&\\ \end{array} \right.$

写着好多呀能不能写得简便一点？

当然，

目标函数中的 $c_1x_1+c_2x_2+\cdots+c_nx_n$

可以写成 $\sum_{j=1}^n c_{j}x_{j}$

约束条件中的 $s.t.\left\{ \begin{array}{rcl} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n & \leq(= / \geq ) & b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n & \leq(= / \geq ) & b_2 \\ \cdots & & \\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n & \leq(= / \geq ) & b_m \\ \end{array} \right.$

可以写成 $\sum_{j=1}^n a_{ij}x_{j} \leq(= / \geq ) b_i, i = 1,2,\cdots m$

对于决策变量的约束 $x_1\geq 0, \cdots ,x_n \geq0$

可以写成 $x_{j} \geq 0, j = 1,2,\cdots n$ （都是非负约束时）

于是整个模型就变成了：

$\max(\min)Z = \sum_{j=1}^n c_{j}x_{j}\\ s.t.\left\{ \begin{array}{rcl} \sum_{j=1}^n a_{ij}x_{j} \leq(= / \geq ) b_i,& i = 1,2,\cdots, m \\ x_{j} \geq 0,&j = 1,2,\cdots n\\ \end{array} \right.$

矩阵形式与向量形式

除了一般形式外，整理整理还可以写成矩阵形式和向量形式（了解即可，不影响后面理解）

向量形式：

$\max(\min)Z = CX\\ s.t.\left\{ \begin{array}{rcl} \sum_{j=1}^n P_{j}x_{j} &\leq(= / \geq ) &b_i \\ X &\geq &0\\ \end{array} \right.$

矩阵形式：

$\max(\min)Z = CX\\ s.t.\left\{ \begin{array}{rcl} AX&\leq(= / \geq ) &b \\ X &\geq &0\\ \end{array} \right.$

其中，

$C_{} = \left ( \begin{array}{ccc} c_{1} & \cdots & c_{n}\end{array} \right )$

$P_{j} = \left ( \begin{array}{c} a_{1j}\\ a_{2j} \\ \cdots \\ a_{mj} \end{array} \right )$ , $X_{j} = \left ( \begin{array}{c} x_{1}\\ x_{2} \\ \cdots \\ x_{n} \end{array} \right )$ , $b = \left ( \begin{array}{c} b_{1}\\ b_{2} \\ \cdots \\ b_{m} \end{array} \right )$

$A_{} = \left ( \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ a_{21} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots \\ a_{m1} & \cdots & a_{mn} \end{array} \right )$

记忆技巧：把向量形式的第二行改成 $AX\leq(= / \geq ) b$ 就是矩阵形式，其他都一样

（注意点：虽然其他形式一样，但是含义是有些区别的，这个区别和联系也就是矩阵和向量之间的区别与联系，只需要简单的线代入门知识。因为不影响后面的理解，这里就不再解释）

线性规划问题的标准形式

正如在逻辑梳理时提到的，“为了统一讨论，我们再在其中选取大家容易接受的求最大值、等式约束、非负约束，规定这样的形式是标准形式”

线性规划问题的标准形式：

目标函数：

$\max Z = c_1x_1+c_2x_2+\cdots+c_nx_n\\$

约束条件：

$s.t.\left\{ \begin{array}{rcl} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n & = & b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n & = & b_2 \\ \cdots & & \\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n & = & b_m \\ x_1, \cdots ,x_n \geq0&&\\ \end{array} \right.$

记忆技巧：对三个要素的要求“大”、“大”、“等”

目标函数求最“大”值
决策变量“大”于等于零
"等"式约束，而且等式右边的常数项“大”于等于零

将一般的线性规划问题转化为标准形式

原理理解

我们刚刚已经知道，线性规划问题的标准形式是对三个要素的要求“大”、“大”、“等”。

不满足其中任何一个，就不是标准形式，我们就需要想办法转化成符合标准形式要求的样子。

我们可能会遇到下面的情形：

目标函数不是求最“大”值，也就是说求最小值
决策变量不是“大”于等于零；也就是说决策变量小于零
等式右边的常数项不是“大”于等于零
不是"等"式约束，也就是说有不等式约束

所以我们需要：

（目标函数）求最小值转化成求最大值
（决策变量和/或约束条件右端的常数项）小于零变成大于零
（约束条件）不"等"式改成等式约束

实现方法

反转

对于前两点：

目标函数求最小值转化成求最大值
决策变量小于零变成大于零

很容易想到解决方法：乘以个（-1）就可以！

记忆技巧：笔者把这一类概括为“反转”，包括：目标函数min变为max、约束条件负变正

目标函数min变max

$\min Z = \sum_{j=1}^n c_{j}x_{j} \Rightarrow \max Z^{'} = -Z=- \sum_{j=1}^n c_{j}x_{j}$

约束条件负变正:

$x_{j} \leq 0 \Rightarrow x_{j}^{'}=-x_{j} ,x_{j}^{'} \geq 0$

约束条件右端的常数项：

$b_{i} \leq 0 \Rightarrow - b_{i} \geq 0$

补齐

对于第三点：

不"等"式改成等式约束

其实也不难想到解决方案：“多退少补”呗！笔者把这里一类概括为“补齐”（示意图见文末手写笔记）

如果是式子左边多了（左边大于等于右边），我们就减掉一点，来和右边相等。因为暂时不知道减掉的是多少，我们姑且用一个变量来表示。因为是多余的嘛，这个变量就叫做剩余变量好了

加入剩余变量 $x_{n+i}$ ：

$\sum a_{ij}x_{j} \geq b_{i} \Rightarrow \sum a_{ij}x_{j} - x_{n+i} = b_{i} ,x_{n+i} \geq 0$

同样的道理，如果是式子左边少了（左边小于等于右边），就是离右边还有空间，我们就加上一点，来和右边相等。因为暂时不知道加上的是多少，我们姑且用一个变量来表示。因为是补上空的一块的嘛，这个变量就叫做松弛变量好了。

加入松弛变量 $x_{n+i}$

$\sum a_{ij}x_{j} \leq b_{i} \Rightarrow \sum a_{ij}x_{j} + x_{n+i} = b_{i} ,x_{n+i} \geq 0\\$

这里需要注意的一个细节倒是下面这一点：

我们在逻辑梳理部分说过：

“对于这三个要素而言，思考一下会发现他们之间有这样的关系：目标函数是由决策变量构成的，约束条件也是对决策变量的约束”

因此，我们在补充变量时，我们也要想好，这个新增的变量，目标函数里是要有它的位置的！

你可能会问：但是这里，我们增加的松弛变量或减少的剩余变量，是“凭空”补充的呀，那他们在目标函数中的系数是多少呢？

这样问的时候，你已经找到答案了：“空”不就是“0”嘛？

系数当然都是0！

松弛变量和剩余变量引进模型后，它们在目标函数中的系数均为0

分身

目前来看，刚刚提出的三点：

最小值转化成求最大值
小于零变成大于零
不"等"式改成等式约束

都已经解决了。

那么，问题结束了吗？

还没有！

还有可能，在原来的模型中，有的决策变量没有约束呢！

这个时候，我们希望给ta来一个等式约束，我们愿意付出新增变量的代价，且希望新增的变量有非负性约束。

$x_{j} = x_{j}^{'} + x_{j}^{''}\\ x_{j}^{'} , x_{j}^{''} \geq 0$

一个变两个，笔者把这一类总结为“分身”

结语

至此，这一部分的内容就圆满结束啦！

看上去好像并不难，不过这其中蕴含的化归思想将贯穿整个运筹学后面的学习，一定要弄明白哦~

参考资料与相关课程推荐

网课推荐

中国大学MOOC：潘老师

运筹学_上海外国语大学_中国大学MOOC(慕课)

非常适合从入门到掌握，每个视频-15分钟，老师将概念和步骤条分缕析讲得很详细。本文可以配合视频1.1进行学习。

参考教材

《运筹学基础及应用》（第5版）,胡运权, 哈尔滨工业大学出版社

文末福利：手写笔记总结与对应例题

标签：约束条件,变量,线性规划,形式,约束,初识,文末,函数
From： https://blog.csdn.net/MARTRIX_BOOLE/article/details/145129994