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

上一部分我们了解了线性规划的定义，基本形式和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实现
匈牙利算法

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,233评论 6赞 495
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,357评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,831评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,313评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,417评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,470评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,482评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,265评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,708评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,997评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,176评论 1赞 342
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,827评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,503评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,150评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,391评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,034评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,063评论 2赞 352