By Zhang, Cheng

更新日期:

文章目录
  1. 1. 算法（6）线性规划介绍
    1. 1.1. 线性规划
    2. 1.2. 最优结果
    3. 1.3. 线性规划的求解
    4. 1.4. 更多的产品
    5. 1.5. 例子：产品规划
    6. 1.6. 标准线性规划
    7. 1.7. 例子：最短路径问题

算法（6）线性规划介绍

线性规划

在线性规划的问题中，给定一组变量，我们希望能够给这些变量赋值使得它们可以满足下面两个条件：1. 变量满足一组线性等式或者线性不等式； 2. 对线性目标函数（linear objective function）得到它的最大值或者最小值。

这样讲比较抽象，我们来举个例子，比如有家巧克力公司要生产巧克力，它有两种产品，分别是P巧克力，单价为1和N巧克力，单价为6。每天对巧克力P的需求是最多200盒，对巧克力N的需求是最多300盒。这家公司一天最多生产400盒巧克力。现在要求这家公司销售额的最大值。

那么根据上面的条件可以列出下面的目标函数和条件限制：

1
2
3
4
5
6
令x1，x2分别表示巧克力P的生产量和巧克力N的生产量。
目标函数：max x1 + 6x2
限制条件：x1 <= 200
        x2 <= 300
        x1 + x2 <= 400
        x1,x2 >= 0

因为有两个未知变量，所以上面的限制条件可以转化成二维平面。那么这两个变量的5个不等式可以确定一个可取范围。这个范围是一个凸多边形（convex polygon）。

我们可以将目标函数x1+6x2等于某个值C，那么这个函数就变成了斜率为-1/6，截距在x2轴上的斜线。在可取的范围内最大的截距就是我们目标函数的最大值。

最优结果

一般情况下，线性规划的最优解可以在可取范围的节点上取到，只有两种例外情况是取不到最优值的，分别是

  1. 限制条件并不能够得到可取范围，比如x<=1,x>=2
  2. 限制条件没有边界，比如max x1+x2, x1,x2>=0

线性规划的求解

线性规划可以使用单程行法（simplex）来解决。这个算法由节点开始，反复地寻找更好结果的邻近节点，当找不到更好的邻居节点时，单程行法就停止了。

更多的产品

我们接着继续更改问题，巧克力公司需要生产另一品种的巧克力L，单价为13，原来一天公司生产的巧克力总数的条件不变，仍然是400。现在因为机器包装的问题，巧克力N和巧克力L需要符合x2 + 3x3 <= 600的条件。那么原来的线性规划变为

1
2
3
4
5
6
7
令x1，x2，x3分别表示巧克力P的生产量，巧克力N和巧克力L的生产量。
目标函数：max x1 + 6x2 + 13x3
限制条件：x1 <= 200
        x2 <= 300
        x1 + x2 + x3 <= 400
        x2 + 3X3 <= 600
        x1,x2,x3 >= 0

那么现在这个问题的可取范围变成了三维空间，我们仍然可以将目标函数设为一个值，这样目标函数的取值就是一个平面。

当节点符合（0,300,100）时，将得到最优的销售额。根据单程行法，我们可以得到这样的轨迹：

例子：产品规划

一家公司做手工地毯，这个产品的需求是季节性的。分析师分析第二年每月的需求量分别是d1,d2,...d12，其中这些值在440到920的范围内。现在有30个员工，他们每人每月可以生产20个毛毯，每人的月薪是$2000。

现在有个问题，我们如何处理需求的波动呢？这里有三种情况：

  1. 加班，如果工人加班，需要多支付额外的80%常规费用。当然工人只能加班30%的额外时间。
  2. 雇佣和解雇，雇佣每个额外的工人需要支付$320，解雇支付$400。
  3. 储存多余的产品，每个毛毯每月花费$8。

我们可以这样来设置变量：

1
2
3
4
5
wi 表示在第i月里的工人数量 w0 = 30;
xi 表示在第i月里生产的毛毯数
oi 表示月份i里额外生产毛毯数
hi,fi 表示月份i雇佣和解雇的工人数
si 表示i月底储存的毛毯数

首先，上面的变量都大于等于0，对i=1,2,…,12

i月生产的毛毯数为常规毛毯数加上额外生产的毛毯数： xi = 20wi + oi

当月工人数为上个月的工人数加上这个月的工人变动： wi = wi-1 + hi - fi

毛毯数为上个月的毛毯数加上这个月的毛毯数变动： si = si-1 + xi - di;

加班时间的约束条件： oi <= 6wi

标准线性规划

一般，线性规划可以有3种维度的不同，我们可以将这些不同进行互相规约：

  1. 目标函数可以求最大值或者最小值
  2. 限制条件可以是等式或者不等式
  3. 这些变量一般都是非负数

对第一类进行求最大值或最小值之间的转化，可以对目标函数乘以-1便可以进行转化了。

对第二类的转化，不等式转化为等式可以通过引入一个松弛变量（slack variable），比如原不等式为ax <= b，引入松弛变量后，ax + s = b，其中s>=0；等式转化为不等式，比如ax = b转化为ax<=b和ax>=b。

左边一般称为通用型（Generic），右边称为标准型。

例子：最短路径问题

现在我们有图G(V,E)，有源节点s和目标节点t，现在我们要求出s到t的最短路径。

1
2
3
4
5
设di表示源点s到节点i的最短路径
max dt
dv <= du + w(u,v) (u,v)属于边
ds = 0
di >= 0

这里为什么是求最大值呢？我们可以这样理解，如果是求最小值，那么符合题设的情况下，dt可以直接取0。这显然不符合我们最短路径的题目要求。所以就是求最大值。

另一种从割的角度来理解的话是

令S为图中所有s-t的割,we表示该边e的权值，xe表示该边e是否选入最短路径中。

文章目录
  1. 1. 算法（6）线性规划介绍
    1. 1.1. 线性规划
    2. 1.2. 最优结果
    3. 1.3. 线性规划的求解
    4. 1.4. 更多的产品
    5. 1.5. 例子：产品规划
    6. 1.6. 标准线性规划
    7. 1.7. 例子：最短路径问题