上一部分我们了解了线性规划的定义,基本形式和Matlab实现,那么这一部分我们介绍一些线性规划的应用。
可转化为线性规划的数学问题
例1 设有规划问题:
请将其变为一般形式的线性规划问题。
注意到,对于任意的,存在满足
这个条件很好实现,只需满足:
即可实现。
于是可以将此问题转化为一般的线性规划问题。
s.t.
线性规划的实际应用
运输问题(产销平衡问题)
例2 某商品有m个产地,n个销地,各产地的产量分别为,各销地的需求分别为,假设商品从产地运到销地的单位运价为,该如何调运才能使总运费最省?
引入变量,其取值为产地运到销地的商品数量,数学模型为
这是一个单纯的线性规划问题,而且是标准型,可以直接解决。
但是其实这类问题的约束条件矩阵系数十分特殊,如果没有计算机的话,使用另一种解决这类问题的方法——表上作业法更为快捷,表上作业法由于要制表,其实是更方便了手算,算法较为复杂,此处不再赘述,有兴趣的同学可自行查阅。
提供一个表上作业法教程的链接。
表上作业法
指派问题
例3 拟分配人去做项工作,每人干且仅干一项工作,若分配第人去干第项工作需要单位时间,问如何分配工作才能使工人花费总时间最少?
形如上面的一个问题称为一个指派问题。
引入变量,若分配干工作,则取,否则取,上述指派问题得上数学模型为:
上述问题不是标准线性规划问题,不能用标准方法解决,因为自变量是离散的,非0即1,这种自变量非0即1的问题称为0-1规划问题,0-1规划问题本身是非常难以解决的,但指派问题比较特殊,有专用算法,匈牙利算法来解决。
匈牙利算法
匈牙利算法是由匈牙利数学家Edmonds在1965年提出的一种算法,专用来解决分配问题。
例4 求解指派问题
其系数阵为:
1.将矩阵每一行减去其每一行的最小元素,得:
2.发现此时第3列没有0,于是将第三列减去其列中最小元素1.
3.对应上图矩阵标的位置得到指派方案。
下面矩阵代表指派方案,上一行代表完成工作的人,第二行代表其要完成的工作,也是指派问题输出的标准形式。
匈牙利算法的特殊情况
上述情况是匈牙利算法的简单情况,并不是所有时候都这么理想。
例5 求解指派问题
1.每一行减去其最小元素
这一步做完之后发现,没法进行下去了,因为不存在没有0的列了,第5个标的0找不到了。
这个时候换用另一条思路进行:
- (1)对未选出0元素的行打
(2)对行中0元素所在列打
(3)对列中选中的0元素所在行打
重复(2),(3)直到无法打为止
标记
3.对所有没有打的行和打的列进行划线,这样可以用最少的线覆盖所有含0的行列。在剩下的元素中找到最小的。
划线,找出最小元素
4.令打的行减去这个元素,打的列加这个元素,这样未覆盖的区域至少有一个元素变为0,上述过程可反复进行,直到选出合适的0元素。
5.得到最优指派
Matlab实现
匈牙利算法
下一次将解析一个线性规划的建模实例。
网友评论