美文网首页
【数学建模算法】(2)线性规划的应用

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

作者: 热爱学习的高老板 | 来源:发表于2019-08-03 15:21 被阅读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},若分配ij工作,则取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. (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实现
    匈牙利算法

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

    相关文章

      网友评论

          本文标题:【数学建模算法】(2)线性规划的应用

          本文链接:https://www.haomeiwen.com/subject/mvaddctx.html