文章目录
  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,其中这些值在440920的范围内。现在有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,现在我们要求出st的最短路径。

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. 例子:最短路径问题