0-1整数规划问题.ppt

§8.5 案例分析：L公司的战略重组问题 西部： 东北: 要想使他们的平均运输时间不大于1.6天，就是要满足下面的约束： 对于总的平均运输时间不能超过1.2天这一约束表示如下： §8.5 案例分析：L公司的战略重组问题 还有一点是，假如在某地没有建服务中心，那么客户就不能得到这个中心的服务，也就是说如果yj =0，那么Xij=0 ，用数学语言表达就是： 最后，根据李先生的设想，服务中心的数量不能超过3个，最好是2个，这个要求用数学语言表示为： 因为yj 是0-1变量， 表示0到1之间的数字，所以当yj =0 时，上式使Xij=0 , ( )，但当 时，上式对 根本就没有约束，不会影响 的取值。 §8.5 案例分析：L公司的战略重组问题 将这个问题用电子表格来求解（如图8.15） §8.5 案例分析：L公司的战略重组问题 §8.5 案例分析：L公司的战略重组问题 §8.5 案例分析：L公司的战略重组问题 通过以上过程求得y1=0 、y2=0 、y3=0 、y4=1 、y5=0 、y6=1 ，也就是在武汉和沈阳建服务中心，年运营成本是31（百万元），另外，我们还能从表格中知道华北和华东区的客户是由建在沈阳的服务中心服务；华南和华中地区的客户由建在武汉的服务中心服务；西部地区客户95%的服务由武汉服务中心提供，另外5%的服务由沈阳的服务中心提供；东北地区客户71.4%的服务由武汉服务中心提供，另外28.6%的服务由沈阳的服务中心提供。各个地区的平均运输时间分别是：t1=1 、t2=1.5 、t3=1 、t4=0.5 、t5=1.6 、t6=1.57 。这里E-16表示 (可以认为是0), 总的平均运输时间是1.2天。  §8.5 案例分析：L公司的战略重组问题 图8.16 L公司战略重组问题规划求解（总平均运输时间最大为1天时） §8.5 案例分析：L公司的战略重组问题 将总平均运输时间降为1天时，总的运营成本并未发生变化，因为服务中心的数量和地点都没有变，只是各区客户接受服务的服务中心不同（图8.16），说明在不增加成本的前提下，合理地安排服务中心和客户也可以缩短运输时间，提高客户满意水平。 §8.5 案例分析：L公司的战略重组问题 图8.17 L公司战略重组问题规划求解（总平均运输时间最大为0.9天时） §8.5 案例分析：L公司的战略重组问题 将总平均运输时间继续降为0.9天时，总的运营成本增加为33百万元，虽然服务中心的数量没有改变，但选址发生了变化，将原来设在武汉的服务中心设在广州（图8.17）。也就是说如果李先生每年愿意再多花2百万元就可以将总的平均运输时间降为0.848天，进一步提高客户满意水平。但是如果想在此基础上再缩短运输时间（比如0.8天）就要花多得多的运营成本（图8.18），年总运营成本为52百万元，因为要多建一个服务中心。 §8.5 案例分析：L公司的战略重组问题 §8.4.3 N个约束中选K个约束的问题 . i = 甲、乙、丙、丁 §8.4.3 N个约束中选K个约束的问题 用Excel规划求解工具来解这个问题图示如下: §8.4.3 N个约束中选K个约束的问题 §8.4.3 N个约束中选K个约束的问题 §8.4.4 约束方程有N种可能值的问题 有时候资源的数量是可以选择的，这就导致了约束方程的右端项可能会有多个值。这种情况的一般表达式为： 或 或 §8.4.4 约束方程有N种可能值的问题 与其等价的0-1规划模型是： 其中, 在这个模型中有 个是非判断问题，其中只能有一个是非判断问题的回答是“是”，所以约束方程右端的值等于 对应的 的值。当然，当资源数也可以是右端任意 个资源之和，这时只需将上式改为： §8.4.4 约束方程有N种可能值的问