【数学建模算法】（2）线性规划的应用

2019-08-03 本文已影响0人热爱学习的高老板

上一部分我们了解了线性规划的定义，基本形式和Matlab实现，那么这一部分我们介绍一些线性规划的应用。

可转化为线性规划的数学问题

例1 设有规划问题：
$\min \quad \left|x_{1}\right|+\left|x_{2}\right|+\cdots+\left|x_{n}\right|$
$\text { s.t. } \quad A x \leq b$
请将其变为一般形式的线性规划问题。

注意到，对于任意的 $x_{i}$ ,存在 $u_{i}, v_{i}>0$ 满足

$x_{i}=u_{i}-v_{i}, \quad\left|x_{i}\right|=u_{i}+v_{i}$

这个条件很好实现，只需满足：

$u_{i}=\frac{x_{i}+\left|x_{i}\right|}{2}, \quad v_{i}=\frac{\left|x_{i}\right|-x_{i}}{2}$

即可实现。
于是可以将此问题转化为一般的线性规划问题。

$\min \quad \sum_{i=1}^{n}\left(u_{i}+v_{i}\right)$
s.t. $\left\{\begin{array}{l}{A(u-v) \leq b} \\ {u, v \geq 0}\end{array}\right.$

线性规划的实际应用

运输问题（产销平衡问题）

例2 某商品有m个产地，n个销地，各产地的产量分别为 $a_{1}, \cdots, a_{m}$ ,各销地的需求分别为 $b_{1}, \cdots, b_{n}$ ，假设商品从 $i$ 产地运到 $j$ 销地的单位运价为 $c_{i j}$ ，该如何调运才能使总运费最省？

引入变量 $x_{i j}$ ,其取值为 $i$ 产地运到 $j$ 销地的商品数量，数学模型为

$\min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} x_{i j}$
$\text { s.t. }\left\{\begin{array}{ll}{\sum_{j=1}^{n} x_{i j}=a_{i},} & {i=1, \cdots, m} \\ {\sum_{i=1}^{m} x_{i j}=b_{j},} & {j=1,2, \cdots, n} \\ {x_{i j} \geq 0}\end{array}\right.$

这是一个单纯的线性规划问题，而且是标准型，可以直接解决。

但是其实这类问题的约束条件矩阵系数十分特殊，如果没有计算机的话，使用另一种解决这类问题的方法——表上作业法更为快捷，表上作业法由于要制表，其实是更方便了手算，算法较为复杂，此处不再赘述，有兴趣的同学可自行查阅。

提供一个表上作业法教程的链接。
表上作业法

指派问题

例3 拟分配 $n$ 人去做 $n$ 项工作，每人干且仅干一项工作，若分配第 $i$ 人去干第 $j$ 项工作需要 $c_{i j}$ 单位时间，问如何分配工作才能使工人花费总时间最少？

形如上面的一个问题称为一个指派问题。
引入变量 $x_{i j}$ ，若分配 $i$ 干 $j$ 工作，则取 $x_{i j}=1$ ，否则取 $x_{i j}=0$ ，上述指派问题得上数学模型为：

$\min \sum_{i=1}^{n} \sum_{j=1}^{n} c_{i j} x_{i j}$
$s.t\quad \sum_{j=1}^{n} x_{i j}=1$
$\sum_{i=1}^{n} x_{i}=1$
$x_{i j}=0或1$

上述问题不是标准线性规划问题，不能用标准方法解决，因为自变量 $x_{i j}$ 是离散的，非0即1，这种自变量非0即1的问题称为0-1规划问题，0-1规划问题本身是非常难以解决的，但指派问题比较特殊，有专用算法，匈牙利算法来解决。

匈牙利算法

匈牙利算法是由匈牙利数学家Edmonds在1965年提出的一种算法，专用来解决分配问题。

例4 求解指派问题
其系数阵为：
$C=\left[\begin{array}{cccc}{16} & {15} & {19} & {22} \\ {17} & {21} & {19} & {18} \\ {24} & {22} & {18} & {17} \\ {17} & {19} & {22} & {16}\end{array}\right]$

1.将矩阵每一行减去其每一行的最小元素，得：
$B_{1}=\left[\begin{array}{cccc}{1} & {0} & {4} & {7} \\ {0} & {4} & {2} & {1} \\ {7} & {5} & {1} & {0} \\ {1} & {3} & {6} & {0}\end{array}\right]$

2.发现此时第3列没有0，于是将第三列减去其列中最小元素1.
$B_{2}=\left[\begin{array}{cccc}{1} & {0^{*}} & {3} & {7} \\ {0^{*}} & {4} & {1} & {1} \\ {7} & {5} & {0^{*}} & {0} \\ {1} & {3} & {5} & {0^{*}}\end{array}\right]$

3.对应上图矩阵标 $0^{*}$ 的位置得到指派方案。
下面矩阵代表指派方案，上一行代表完成工作的人，第二行代表其要完成的工作，也是指派问题输出的标准形式。
$\left(\begin{array}{llll}{1} & {2} & {3} & {4} \\ {2} & {1} & {3} & {4}\end{array}\right)$

匈牙利算法的特殊情况

上述情况是匈牙利算法的简单情况，并不是所有时候都这么理想。

例5 求解指派问题
$C=\left[\begin{array}{ccccc}{12} & {7} & {9} & {7} & {9} \\ {8} & {9} & {6} & {6} & {6} \\ {7} & {17} & {12} & {14} & {12} \\ {15} & {14} & {6} & {6} & {10} \\ {4} & {10} & {7} & {10} & {6}\end{array}\right]$

1.每一行减去其最小元素
$\left[\begin{array}{ccccc}{5} & {0^{*}} & {2} & {0} & {2} \\ {2} & {3} & {0} & {0^{*}} & {0} \\ {0^{*}} & {10} & {5} & {7} & {5} \\ {9} & {8} & {0^{*}} & {0} & {4} \\ {0} & {6} & {3} & {6} & {2}\end{array}\right]$

这一步做完之后发现，没法进行下去了，因为不存在没有0的列了，第5个标 $*$ 的0找不到了。

这个时候换用另一条思路进行：

(1)对未选出0元素的行打 $\vee$
(2)对 $\vee$ 行中0元素所在列打 $\vee$
(3)对 $\vee$ 列中选中的0元素所在行打 $\vee$
重复(2),(3)直到无法打 $\vee$ 为止
标记

3.对所有没有打 $\vee$ 的行和打 $\vee$ 的列进行划线，这样可以用最少的线覆盖所有含0的行列。在剩下的元素中找到最小的。
划线，找出最小元素

4.令打 $\vee$ 的行减去这个元素，打 $\vee$ 的列加这个元素，这样未覆盖的区域至少有一个元素变为0，上述过程可反复进行，直到选出合适的0元素。
$\left[\begin{array}{11111}{7} & {0^{*}} & {2} & {0} & {2} \\ {4} & {3} & {0} & {0^{*}} & {0} \\ {0^{*}} & {8} & {3} & {5} & {3} \\ {11} & {8} & {0^{*}} & {0} & {4} \\ {0} & {4} & {1} & {4} & {0^{*}}\end{array}\right]$

5.得到最优指派
$\left(\begin{array}{lllll}{1} & {2} & {3} & {4} & {5} \\ {2} & {4} & {1} & {3} & {5}\end{array}\right)$

Matlab实现
匈牙利算法

下一次将解析一个线性规划的建模实例。