这一讲从“训练模型”转到“安排系统”:工厂生产多少、资金如何分配、项目如何按时完成、诊所建在哪里、送货先去哪里。它们都在做同一件事:在限制之内,找一个最好的选择。
读每个案例都按三个问题走:①能决定什么——变量;②怎样算好——目标;③哪些事必须满足——约束。先写清这三项,再判断该用线性规划、二次规划还是整数规划。
共 53 页。按原课件顺序,左侧看原页,右侧读讲解。
每项都在允许的最早时间开始。遇到多个前驱,先取它们完成时间的最大值,再加本项工期。
| 任务 | 最早开始的计算 | 最早完成 |
|---|---|---|
| A | 0 | 8 |
| B | 8 | 18 |
| C | 18 | 27 |
| D | max(18,27)=27 | 35 |
| E | 18 | 23 |
| F | 23 | 33 |
| G | max(27,35,33)=35 | 37 |
| H | 33 | 36 |
| I | max(37,36)=37 | 47 |
最长的依赖链是 ,总长 天。链上的任务只能依次完成,所以任何方案都至少要47天;表中的排程恰好达到47天,因此它就是最短工期。
要算总时差,从第47天反推。I最迟开工是 。G、H都要在37前结束,所以它们的最迟开工分别是 和 。F要在G、H开工前完成,因此最迟开工是 。E最迟开工是 。
总时差等于最迟开始减最早开始。E、F、H的总时差分别是 、、 天。关键路径自身已占满47天,链上的其他六项都没有余量。这1天也不能由同一分支上的E、F、H分别用掉。
这套线性规划的最优方案为:A缩短2天、B缩短2天、D缩短3天、E缩短1天、F缩短1天,其他不变。
先算钱:
再算是否真的能在40天完成:
| 任务 | 新工期 | 最早完成 |
|---|---|---|
| A | 6 | 6 |
| B | 8 | 6+8=14 |
| C | 9 | 14+9=23 |
| D | 5 | max(14,23)+5=28 |
| E | 4 | 14+4=18 |
| F | 9 | 18+9=27 |
| G | 2 | max(23,28,27)+2=30 |
| H | 3 | 27+3=30 |
| I | 10 | max(30,30)+10=40 |
各活动的缩短量均在上限内,排程在第40天完成。下面用两条路径给出成本下界,可以手算验证46,500确实是最低成本。
这里为什么还花钱加快E和F?因为只压缩原47天关键路径时,另一条 会变成瓶颈。上述方案把经过G和经过H的两条收尾分支都压到了第30天,使油漆能第30天开始。
经过D、G的路径 原长47天,必须至少缩短7天。经过H的路径 原长46天,必须至少缩短6天。把两条路径上的缩短天数记为 。G不能赶工,所以
把第一条乘6000,第二条乘3500,相加得到 。这样加权后,每缩短1天,F的系数3500和实际单价相同。两条路径共有的I系数是 ,也等于实际单价。把A、B、C、D、E、H的系数调整回实际单价,得到
用缩短量上限 给出负项的下界,正项至少为0。因此 。上面的排程恰好花46,500,所以达到成本下界。
目标 是线性的,约束 也是线性的,因为 是常数。常数乘变量仍是一阶项。
但 必须取0或1。这个限制使问题成为0-1整数线性规划,属于MILP求解器处理的模型类型。
若把二元限制放宽为 ,就得到连续LP松弛。松弛后的可行集合更大,所以它的最小目标值不高于原整数问题。它可以提供一个下界,但0.5不再对应合法的“建或不建”决定。
做题检查模型类型时,分别看“表达式是否线性”和“变量是否必须取整数”。这两个判断互不替代。
三个地点中,社区1能到1、2,社区2能到2、3,社区3能到1、3。实际至少要开两家,因为任意一家只覆盖两个社区。LP若允许选半家,则 让每条覆盖约束的左边都等于1,目标只有1.5。把三条覆盖约束相加还得到 ,所以1.5正是LP的最低值,也是整数答案2的下界。
对任意至少2个点、但还没包含全部n个点的集合Q,加入:
是集合内的地点数。若Q内部自行形成回路,会用 条边,超过允许的 ;如果它只是完整大回路的一部分,至少有一条边必须离开Q,因此内部边数不超过 。
例如 时,要求 ,两条方向相反的边不能同时选。Q含3点时,右边为2,得到上一页的条件。若把全体地点也作为Q,会要求整个回路少用一条边,所以只给真子集加约束。
完整TSP模型就是:距离总和最小、每点一条入边、每点一条出边、全部真子集的子回路约束,以及边变量二元。前两组使路线分成若干回路,子回路约束再把所有非全体回路排除,最后只剩包含全部地点的一个大回路。
所有表达式都线性,而变量取0或1,所以这是整数线性规划。子集数量很多,也解释了为什么TSP比普通连续线性规划难。