Site Overlay

运筹学笔记(1)

线性规划的问题实质

线性规划的模型就是:消耗资源,经过活动,产生收益 的模型,规划的目标就是使得收益在 约束条件下取得 最值

由于不同的活动对不同的资源的消耗不同,我们可以用一张表来表示这种消耗:

$$
\begin{matrix}
\ & a& b& c \
A & 1 & 3 & 2\
B & 5 & 4 & 6\
C & 2 & 1 & 1
\end{matrix}
$$

其中,$a,b,c$ 表示的是不同的活动,$A, B, C$ 表示的是不同的资源。$c$ 列与 $A$ 行的交叉点 $2$ 就表示 $c$ 活动对 $A$ 资源的消耗。

活动的进行程度,比如工厂的生产天数,可以用一个系数表示,这个量叫做 活动的级别

$$
\begin{matrix}
4(活动 a 的级别)\
6(活动 b 的级别)\
2(活动 c 的级别)\
\end{matrix}
$$

两者相乘,表示活动生产的收益(这里我们是假设消耗的资源和产生的收益是线性相关的):

$$
收益 Z = \begin{bmatrix}
1 & 3 & 2\
5 & 4 & 6\
2 & 1 & 1
\end{bmatrix} \begin{bmatrix}
4\
6\
2\
\end{bmatrix}
$$

而实际上,活动的级别是不知道的,需要我们去 寻找最合适的活动级别

$$
收益 Z = \begin{bmatrix}
1 & 3 & 2\
5 & 4 & 6\
2 & 1 & 1
\end{bmatrix} \begin{bmatrix}
x_1\
x_2\
x_3\
\end{bmatrix}
$$

而且,往往存在约束条件,比如活动的总级别是有上限的:

$$
x_1 + x_2 + x_3 \leq 12\
$$

资源是有限的:

$$
1x_1+ 3x_2+ 2x_3 \leq 123
$$

从而,我们可以抽象出:

线性规划模型的标准形式

$$
\begin{array}{c}
\operatorname{Max} Z=c{1} x{1}+c{2} x{2}+\cdots+c{n} x{n} \
\text { s. t. } \quad a{11} x{1}+a{12} x{2}+\cdots+a{1 n} x{n} \leqslant b{1} \
a
{21} x{1}+a{22} x{2}+\cdots+a{2 n} x{n} \leqslant b{2} \
\cdots \
a{m 1} x{1}+a{m 2} x{2}+\cdots+a{m a} x{n} \leqslant b{m} \
x
{1} \geqslant 0, x{2} \geqslant 0, \cdots, x{n} \geqslant 0
\end{array}
$$

目标函数:就是收益关于活动级别的函数。$ Z=c{1} x{1}+c{2} x{2}+\cdots+c{n} x{n} $

结构性约束:关于所有变量的一个约束比如 $\quad a{11} x{1}+a{12} x{2}+\cdots+a{1 n} x{n} \leqslant b_{1} $

非负约束:$x_n \leq 0$ 这样的。

可行解:满足所有约束条件的解。

不可行解:存在不满足的约束条件的解。

可行域:可行解集。

最优解:使得目标函数取得最有利值的可行解(或解集合)。

角点:约束条件边界的交点。

角点可行解(CPF解):在角点上的可行解。(最优 CPF 解一定是一个最优解)

单纯形法的实质

单纯形法就是选定一个角点,然后看周围的角点有没有更优的,如果有就走过去。重复这一过程,最后就能找到一个最优的 $CPF$ 解。

想象你爬一座凸的山,但是你被蒙上了眼镜。你可以试一下周围更凸,然后走过去,最后你就能到达山顶。

那么,会不会陷入局部最值呢?不会的,因为线性规划的约束时线性不等式,相当于在一个土豆上(空间中)用平直的刀(平面)反复切割。这样切下来,土豆(满足约束的区域)一定是凸的,凸的就不会出现局部最优。

单纯形法的操作

用两个变量的问题体会思想

【例子】

$\operatorname{Max} \quad Z=3 x{1}+5 x{2}$

$\begin{array}{ll}\text { s.t. } & x_{1} \leqslant 4\end{array}$

$2 x_{2} \leqslant 12$

$3 x{1}+2 x{2} \leq 18$

且. $x{1} \geqslant 0, x{2} \geqslant 0$

【分析与解答】

我们可以画出图形:

typora\20201017142632_611f1c10e44012ecc97a3d57645a7bd9.png

然后,选择任何解作为起点。比如 $(0, 0)$,这时候 $Z = 0 + 0 = 0$。

$(0,0)$ 的旁边有两个点 $(0, 6), (4,0)$

对于 $(0, 6)$,$Z = 30$,对于 $(4, 0)$,$Z = 12$。要求最大的嘛,所以我们选择 $(0,6)$ 作为新的起点。它的旁边有 $(2,6)$,对应 $Z = 36$ 。

$(2,6)$ 的下一个点是 $(4,3)$,对应 $Z = 27$,已经小于 $36$ 了,所以可以确定 $(2,6)$ 是一个最优解。

引入松弛变量的方法

由于实际中可能有很多很多的变量,如果我们都画图来解决,将会十分困难。所以人们发明了引入松弛变量的方法。

对于问题:

$$
\operatorname{Max} \quad Z=3 x{1}+5 x{2}\
\begin{array}{ll}\text { s.t. } & x{1} \leqslant 4\end{array}\
2 x
{2} \leqslant 12\
3 x{1}+2 x{2} \leq 18\
且. x{1} \geqslant 0, x{2} \geqslant 0
$$

引入松弛变量后的扩展形式如下:

$$
\operatorname{Max} \quad Z=3 x{1}+5 x{2}\
\begin{array}{ll}\text { s.t. } & x_{1} {\color{red}{+x3}} = 4\end{array}\
2 x
{2} {\color{red}{+x4}}= 12\
3 x
{1}+2 x_{2} {\color{red}{+x5}}= 18\
且. x
{1} \geqslant 0, x_{2} \geqslant 0
$$

其中,为每个不等式引入的新变量,称为 松弛变量,从而使得表达式变成线性方程组。

扩展解:原来的解,加上带入这个解得到的解,叫做扩展解。例如前面的最优解是 $(2,6)$,带入后得到 $[x_1,x_2, x_3,x_4, x_5] = [2,6,2,0,0]$ ,这一组解就是扩展解。

基解:角点解的扩展解。

基可行解(BF解):CPF 解的扩展解。

基变量:上面原有的 $x_1, x_2$ 这样子的变量。

非基变量:引入的 $x_3,x_4, x_5$ 这样子的变量。

由于方程的个数是三,有五个变量,所以只要任意两个变量确定,剩余的三个变量一定可以确定。

下面,我们一步步解决问题。

对于 $Z = 3x_1 + 5x_2$,$x_1, x_2$:

$\dfrac{\mathrm{d}Z}{\mathrm{d}x_1} = 3$

$\dfrac{\mathrm{d}Z}{\mathrm{d}x_2} = 5$

考虑增长最快的,因此我们选择 $x_2$ 增加。这样的 $x_2$ 叫做迭代 1 的进基变量

好了,现在已经知道需要增加 $x_2$,那么增加多少比较合适呢?

当 $x_1 = 0$ 时(置 $0$ 是单纯形法起始步骤的一般操作),可以得到其它变量的关系如下:

$$
\begin{array}{l}
x{3}=4 \
x
{4}=12-2 x{2} \
x
{5}=18-2 x_{2}
\end{array}
$$

由于约束条件希望所有的变量都非负,我们有:

$$
\begin{array}{l}
x{3}=4 \geq 0 \
x
{4}=12-2 x{2} \geq 0 \
x
{5}=18-2 x_{2} \geq 0
\end{array}
$$

三个约束条件求交集,可以解出 $0 \leq x_2 \leq 6$。

因此 $x_2$ 最多增加到 $6$,$x_4$ 从而减小到 $0$。 这些计算是 最小比检测,用于确定进基变量增加时谁先减到 $0$。

$x_4$ 减小到了 $0$,这样减小到 $0$ 的变量叫做 出基变量,在下一个 BF 解中,它成为了 非基变量

现在,新 BF 解的非基变量是 $x_1 = 0, x_4 = 0$,基变量是 $x_3 = ?, x_2 = 6, x_5 = ?$

对该线性方程组进行高斯消元,得到 $[x_1,x_2, x_3,x_4, x_5] = [0,6,4,0,6]$

同时通过代入法可以求出 $Z$ 关于 新的非基变量 $x_1, x_4$ 的函数:

$$
Z = 30 + 3x_1 - \dfrac{5}{2}x_4
$$

然后往后就是重复迭代了。不赘述。

发表评论

电子邮件地址不会被公开。 必填项已用*标注