DASE 7113 · 课程精讲

工业工程中的优化

共 53 页。按原课件顺序,左侧看原页,右侧读讲解。

逐页目录 · 共 53 页
  1. 把现实中的选择写成优化问题
  2. 工业工程:让生产和服务安排得更好
  3. 同一种数学结构可以解决不同系统的问题
  4. 物流路线:路线短,还要能执行
  5. 库存:先写数量怎样进出
  6. 把工厂推广到交通和能源系统
  7. 工厂究竟该生产多少
  8. 把原料、人工和机器分别列出来
  9. 双下标:商品i消耗资源j
  10. 售价随销量下降:先读懂分母
  11. 完整生产模型:收入减成本,再看凹凸性
  12. 投资组合:变量是各项资金比例
  13. 随机收益:期望与方差分别表示什么
  14. “近似无风险”怎样进入数学模型
  15. 组合风险取决于两项资产会不会一起波动
  16. 组合均值和方差:从定义推到矩阵式
  17. 把收益与风险合成一个目标
  18. 指定最低期望收益,再把风险降到最低
  19. 为什么投资组合模型是凸二次规划
  20. 项目管理:先区分串行和并行
  21. 活动网络:汇合点要等所有前驱
  22. 工期、关键活动和赶工分别在问什么
  23. 把房屋施工表逐行读成先后关系
  24. 用完成时刻把先后关系写成不等式
  25. 把“所有完成时间的最大值”改写成线性约束
  26. 逐项算出47天,并找出关键路径
  27. 40天完成:先读赶工成本表
  28. 缩短量进入工期后,符号怎样变化
  29. 把赶工目标、边界和期限组装起来
  30. 40天赶工的46500方案怎样核算
  31. 随机工期为什么不能只看平均数
  32. 项目管理是一个独立的专业领域
  33. 设施选址:先问这个地点怎样才算好
  34. 诊所选址:每个社区都要30分钟可达
  35. “够近”是数据,“建不建”才是变量
  36. 集合覆盖模型:把“至少一家”写出来
  37. 这里的困难来自0或1,不是乘积
  38. 餐厅分散选址:让最近的两家也尽量远
  39. 先枚举一个小例子,理解max–min的两层
  40. 先把最近点对的距离写成目标
  41. 怎样把带条件的最小值改成MILP
  42. Big-M:未选的点对加上一个大数
  43. 把“只比较选中点对”变成“比较所有e”
  44. 用一组上界替代min,得到线性模型
  45. 数学最优之前,先检查目标选得对不对
  46. 聚集也可能有好处:冲动购买与商圈效应
  47. 旅行商:把所有地点连成一条回路
  48. 边变量xij:从i直接走到j吗
  49. 先写目标和每点一进一出
  50. 两个小回路也满足一进一出
  51. 数一个三点集合内部有几条已选边
  52. 禁止所有三点集合内部出现3条边
  53. 子回路消除:任意真子集都不准自行闭合
原第 1 页

把现实中的选择写成优化问题

原课件第1页
点击原页可打开 PDF。

这一讲从“训练模型”转到“安排系统”:工厂生产多少、资金如何分配、项目如何按时完成、诊所建在哪里、送货先去哪里。它们都在做同一件事:在限制之内,找一个最好的选择。

读每个案例都按三个问题走:①能决定什么——变量;②怎样算好——目标;③哪些事必须满足——约束。先写清这三项,再判断该用线性规划、二次规划还是整数规划。

原第 2 页

工业工程:让生产和服务安排得更好

原课件第2页
点击原页可打开 PDF。

工业工程研究怎样改进产品、服务、流程和运营。图中的工厂是最早的典型场景:同样的机器、原料和工人,怎样安排才能提高效率?

“效率高”还不够具体。若关心利润,目标就是利润最大;若关心交货,目标可能是工期最短;若关心浪费,目标可能是成本最低。优化前先把“好”变成能计算的数字。

例如一件产品必须依次经过两台机器,第一台每小时做10件,第二台做20件。流水线最多每小时完成10件,因为第一台是瓶颈。两台的产能不能直接加成30件。

原第 3 页

同一种数学结构可以解决不同系统的问题

原课件第3页
点击原页可打开 PDF。

本页的箭头把数学方法连接到交通、网络、人群和城市,意思是:先发展通用的优化方法,再把它用在不同系统中。

例如“B必须等A完成”既能描述施工,也能描述软件开发;“地点选或不选”既能描述仓库,也能描述充电站。换场景以后,变量名称和数据会变,但先后约束、容量约束、二元选择这些结构可以重复使用。

做题时先把故事翻译成结构。看到“总量有限”,想到求和上限;看到“必须先完成”,想到时间不等式;看到“是否建设”,想到0或1变量。

原第 4 页

物流路线:路线短,还要能执行

原课件第4页
点击原页可打开 PDF。

地图表示客户地点和可走的道路,车辆表示运力。需要决定的通常有:哪辆车服务哪些客户、访问顺序是什么、沿哪条路开。

  1. 变量:客户分配和访问顺序。
  2. 目标:总里程、总时间或配送成本最小。
  3. 约束:每个客户都被服务,车辆载重不超限,按规定时段到达。

例如两个客户各要6箱货,车只能装10箱。即使把两个客户排在相邻位置,12箱也装不下,仍需分车或再次补货。目标负责比较方案,约束负责排除做不到的方案。

原第 5 页

库存:先写数量怎样进出

原课件第5页
点击原页可打开 PDF。

库存管理决定何时补货、补多少。订得多会占资金和仓储空间,订得少可能缺货。最基本的一步是写出库存平衡:

期末库存=期初库存+到货量−需求量.

例如期初20件,本期需求50件,期末至少留10件。令订货量为 q,并假设本期立即到货:

20+q−50≥10⟹q≥40.

若每件采购成本为 c>0,最小化 cq 就会选择 q=40。这里“至少留10件”是约束,“买得尽量便宜”是目标。

原第 6 页

把工厂推广到交通和能源系统

原课件第6页
点击原页可打开 PDF。

标题从 Industrial Engineering 改成 System Engineering,是把研究对象从工厂扩大到一般系统。交通和电网也有输入、输出、容量和协调问题。

交通中,流入一个路口的车辆需要继续流出;电网中,发电需要满足用电。若某时段需求100单位,两台机组发电量为 g1,g2,就要满足 g1+g2=100,还要分别满足各机组的容量上限。

因此不能只看某台设备的效率。优化要把相互影响的部分放进同一个模型,检查整个系统是否满足需求。

原第 7 页

工厂究竟该生产多少

原课件第7页
点击原页可打开 PDF。

图中同一条生产线可以生产不同食品。本节的问题是:每种商品分别生产多少,工厂利润才最高?

先把产量记作 xi。这里 i 表示第几种商品。产量越多,可能卖得越多,但也会消耗资源,而且降价才能卖出更多时,每件的收入会降低。

所以需要同时考虑三件事:资源够不够、卖多少能收多少钱、生产这些要花多少钱。只比较单件利润不够,因为不同商品耗用的资源也不同。

原第 8 页

把原料、人工和机器分别列出来

原课件第8页
点击原页可打开 PDF。

公司有 n 种商品,产量向量是 x=(x1,…,xn)。原料、人工、机器是不同类型的有限资源,应分别写约束。

用两种商品A、B练习:每件A耗2小时、每件B耗1小时,总工时12小时,因此 2xA+xB≤12。若每件都耗1单位原料、原料共8单位,还要有 xA+xB≤8。产量还应满足 xA,xB≥0。

例如 (xA,xB)=(4,4):工时是 2×4+4=12,原料是 4+4=8,恰好用完。(5,3) 虽然只用8单位原料,却要13小时,因此不可行。

原第 9 页

双下标:商品i消耗资源j

原课件第9页
点击原页可打开 PDF。

aij 表示“生产1单位商品 i,要用多少单位资源 j”;rj 表示资源 j 的总量。两个下标分别回答“哪种商品”和“哪种资源”。

  1. 商品 i 生产 xi 单位,会用掉 aijxi 单位资源 j。
  2. 固定一种资源 j,把所有商品的用量加起来。
  3. 总用量不能超过 rj。
∑i=1naijxi≤rj,j=1,…,m.

若第1种资源是工时,a11=2,a21=1,A做3件、B做4件,就用掉 2×3+1×4=10 小时。换到另一种资源,固定另一个 j,重新对所有商品求和。

右下需求曲线的横轴是需求量,纵轴是单价。图中单价从10升到20时,需求量从200降到100。资源约束决定最多能做多少,价格和需求的关系决定卖出去能收入多少。

原第 10 页

售价随销量下降:先读懂分母

原课件第10页
点击原页可打开 PDF。

课件给出价格与需求量的关系:

pi=pi01+βidi.

pi 是商品 i 的单价;pi0 是需求量为0时的价格尺度;di 是需求量;βi≥0 控制价格下降速度。当 βi>0 时,di 增加使分母变大、单价下降。βi=0 对应固定单价。

例如 p0=100,β=0.1:需求为0时价格100;需求为10时价格 100/(1+1)=50。卖10件的收入是 10×50=500,还没有减成本。

接着采用“生产出来的商品全部售出”,于是销量与产量相同,即 di=xi。这样才能把收入写成产量 xi 的函数。

原第 11 页

完整生产模型:收入减成本,再看凹凸性

原课件第11页
点击原页可打开 PDF。

ci 是商品 i 的单位生产成本。生产并卖出 xi 件,收入是单价乘数量,成本是 cixi。因此:

maxxΠ(x)=∑i=1n(pi0xi1+βixi−cixi),∑i=1naijxi≤rj (j=1,…,m),xi≥0.

为什么课件称它为凸规划?看单项 ϕ(x)=p0x/(1+βx)−cx。假设 p0>0,β≥0,x≥0,逐步求导:

ϕ′(x)=p0(1+βx)−p0xβ(1+βx)2−c=p0(1+βx)2−c,ϕ″(x)=−2p0β(1+βx)3≤0.

每项都凹,合起来的利润也凹。最大化凹利润,等价于最小化凸的负利润,再配上线性约束,就是凸规划。

单商品算一遍:p0=100,β=0.1,c=25。令导数为0,得到 (1+0.1x)2=4。因 x≥0,取 1+0.1x=2,所以 x=10。价格50,利润 50×10−25×10=250。若资源只允许生产6件,最优就取边界6件,因为在0到6之间利润仍在增加。

原第 12 页

投资组合:变量是各项资金比例

原课件第12页
点击原页可打开 PDF。

本页问:把100万资金分给股票、债券、房地产等资产时,各放多少?使用比例变量 xi。例如 x1=0.2 表示20%的资金,即20万元。

全部资金都投入,比例总和为1。模型只允许持有非负份额。

∑i=1nxi=1,xi≥0.

与上一节不同,这里的收益有随机性。不能只问“平均赚多少”,还要问“上下波动多大”。接下来用期望表示平均收益,用方差表示波动。

原第 13 页

随机收益:期望与方差分别表示什么

原课件第13页
点击原页可打开 PDF。

随机收益率是一个会随情形变化的数,记作 R。期望 E[R] 表示按概率加权的平均值;方差 Var(R) 表示收益偏离均值的程度。

例如收益率一半概率为10%,另一半为−6%。先把百分数改成小数:

E[R]=12(0.10)+12(−0.06)=0.02.

均值是2%。两种情形分别偏离均值 0.08 和 −0.08,所以:

Var(R)=12(0.08)2+12(−0.08)2=0.0064,SD(R)=0.0064=0.08=8%.

均值2%描述中心位置,标准差8%描述波动大小。课件截图用很高的收益数字引出同一个问题:比较收益时,还要把风险放进模型。

对应课堂录音Week04 Part01 00:00:01–00:07:03
原第 14 页

“近似无风险”怎样进入数学模型

原课件第14页
点击原页可打开 PDF。

截图中的2.57%是30年期国债的固定票面利率。若给定的投资情形确实可以把所研究期间的收益率视为固定,就能在模型里记为 R=r。

例如假定研究期间固定收益为3%,则 E[R]=0.03。每种情形下的偏差都是 R−E[R]=0,因此 Var(R)=0。如果持有期间可能按变化的市价卖出,就要把价格变化纳入这段期间的收益。

课件提到LTCM,引出对极端情形和资产共同波动的关注。下一页用协方差描述共同波动。

对应课堂录音Week04 Part01 00:00:01–00:07:03
原第 15 页

组合风险取决于两项资产会不会一起波动

原课件第15页
点击原页可打开 PDF。

两项资产可能受共同因素影响而同时涨跌。课件用微软与苹果示意同向变化,用黄金与美元示意反向变化。数学上用协方差描述这种关系:

σij=Cov(Ri,Rj)=E[(Ri−ri)(Rj−rj)],ri=E[Ri].

先减去各自均值,再把偏差相乘:同号相乘为正,异号相乘为负。平均以后为正,表示倾向于同向;为负,表示倾向于反向。

例如两个等概率情形下,两项资产的偏差组合分别为 (0.1,0.1) 和 (−0.1,−0.1),协方差是 0.5(0.1)2+0.5(−0.1)2=0.01。若第二项的偏差改成相反符号,两种情形下的乘积都是 −0.01,协方差也为 −0.01。这个反向例子里,若等比例持有,两项偏差在每种情形下都抵消为0。

对应课堂录音Week04 Part01 00:00:01–00:07:03
原第 16 页

组合均值和方差:从定义推到矩阵式

原课件第16页
点击原页可打开 PDF。

Ri 是第 i 项资产的随机收益率,ri=E[Ri],σij=Cov(Ri,Rj)。把所有均值排成向量 r,所有协方差排成矩阵 Σ,资金比例排成向量 x。

  1. 总收益率是各项收益率的加权和:R¯=∑ixiRi=xTR。
  2. 比例 xi 是已经选定的数,能移到期望符号外面。因此 E[R¯]=∑ixiE[Ri]=xTr。
  3. 减去均值:R¯−E[R¯]=∑ixi(Ri−ri)。
  4. 平方时产生所有两两乘积,再取期望:
Var(R¯)=∑i∑jxixjE[(Ri−ri)(Rj−rj)]=∑i∑jxiσijxj=xTΣx.

两项资产时,矩阵式展开为 x12σ11+2x1x2σ12+x22σ22。中间项乘2,是因为 (i,j)=(1,2) 与 (2,1) 各出现一次。

若等比例投入,方差分别0.01、0.04,协方差0,则组合方差为 0.52×0.01+0.52×0.04=0.0125。若协方差变成0.01,还需加 2×0.5×0.5×0.01=0.005,总方差变成0.0175。

对应课堂录音Week04 Part01 00:07:04–00:11:53
原第 17 页

把收益与风险合成一个目标

原课件第17页
点击原页可打开 PDF。

希望平均收益高,也希望波动小。把两个要求合成一个最小化目标:

minx−xTr+γxTΣx,∑i=1nxi=1,xi≥0.

第一项加负号,是因为“收益越大越好”要改写成“负收益越小越好”。γ>0 是风险权重:越大,越重视压低方差。

假设方案A均值0.08、方差0.04,方案B均值0.05、方差0.01。两者目标分别是 −0.08+0.04γ 和 −0.05+0.01γ。A更好等价于:

−0.08+0.04γ<−0.05+0.01γ⟹0.03γ<0.03⟹γ<1.

所以 γ<1 选A,γ>1 选B。老师在录音中强调的问题是:决策者往往难以直接说出合适的 γ。因此下一种方法改为直接指定最低期望收益。课件非负条件的下标上界应为资产数 n。

对应课堂录音Week04 Part01 00:07:04–00:11:53Week04 Part01 00:11:56–00:19:39Week04 Part01 00:20:27–00:25:52
原第 18 页

指定最低期望收益,再把风险降到最低

原课件第18页
点击原页可打开 PDF。

如果要求平均收益至少达到 rtarget,就把它写成约束,把方差单独作为目标:

minxxTΣx,∑i=1nxi=1,xTr≥rtarget,xi≥0.

读法是:在达到最低期望收益的配置中,选波动最小的。目标收益限制的是期望值。

两项资产均值分别4%和8%,令第二项比例为 w,第一项就是 1−w。组合均值为 0.04(1−w)+0.08w=0.04+0.04w。若目标6%,则:

0.04+0.04w≥0.06⟹w≥0.5.

可行区间是 0.5≤w≤1,下一页在这个区间里找方差最小的比例。若目标改为9%,则需要 w≥1.25,超过了可投入的全部资金,模型无可行解。

对应课堂录音Week04 Part01 00:20:27–00:25:52
原第 19 页

为什么投资组合模型是凸二次规划

原课件第19页
点击原页可打开 PDF。

先求目标 V(x)=∑i,jσijxixj 的第 k 个偏导。xk 可以出现在乘积的前面或后面,用乘积法则分别计算,再用 σik=σki 合并:

∂V∂xk=∑jσkjxj+∑iσikxi=2∑jσkjxj.

再对 xℓ 求导得到 2σkℓ,因此 Hessian 是 2Σ。

取任意向量 v。按上一页的方差公式:

vTΣv=Var(vTR)=E[(vT(R−r))2]≥0.

平方非负,期望也非负,所以 Σ⪰0。其余约束全是线性等式或不等式,因此整个模型是凸二次规划。

把前面的两项例子继续算完。假设两项不相关,方差0.01、0.04:

V(w)=0.01(1−w)2+0.04w2=0.01−0.02w+0.05w2,V′(w)=−0.02+0.10w.

不加收益门槛时,令导数0得到 w=0.2。加上上一页的 w≥0.5 后,导数在可行范围内为正,最低点改成 w=0.5,方差0.0125。注意协方差矩阵一定半正定,但可能有零方向,不一定正定。

对应课堂录音Week04 Part01 00:25:53–00:36:28
原第 20 页

项目管理:先区分串行和并行

原课件第20页
点击原页可打开 PDF。

一个大项目包含许多小任务。图中的做饭流程用来说明:有些任务能同时做,有些任务必须等前面的任务完成。

例如面包准备2分钟,香肠加热5分钟,组装1分钟。若前两项可以并行,组装最早第5分钟开始,总时间 max(2,5)+1=6 分钟;若同一个人必须依次完成,总时间是 2+5+1=8 分钟。

因此读项目图的第一步是看箭头所表示的先后关系,第二步才是把持续时间放进去。下面的房屋案例先假设允许的任务都能并行,只考虑先后约束。

原第 21 页

活动网络:汇合点要等所有前驱

原课件第21页
点击原页可打开 PDF。

字母和数字写在箭头上,表示活动及其耗时。黑点表示一个事件,等所有指向它的活动结束后才能发生。看图中D和H汇合的黑点:

  1. 先做A,用6个时间单位。之后做D,结束于 6+1=7。
  2. 另一支接着做B再做H,结束于 6+4+1=11。
  3. 两支都结束后才能开始J,所以J最早在 max(7,11)=11 时开始,耗时5,到 11+5=16 结束。

从 start 的0开始顺着箭头算。每到一个汇合点,取各条进入路线的最晚到达时刻。这个规则会用在后面的施工表。

原第 22 页

工期、关键活动和赶工分别在问什么

原课件第22页
点击原页可打开 PDF。

本页列出的管理问题可以按下面的顺序理解:

  1. 最短总工期:正常进行时,最早什么时候全部完成?
  2. 最迟开始和完成时间:保证总截止日期不变,每项最晚能拖到什么时候?
  3. 关键活动:总时差为0,延误就会拖延整体。
  4. 非关键活动的余量:能容忍多少天延误?
  5. 随机工期:在指定日期前完成的概率多大?
  6. 赶工:额外花钱缩短哪些活动,整体才能更早完成?

关键活动由整个网络决定。给某个不在瓶颈上的活动增加人手,虽然这项做快了,整体项目却可能一天也没提前。

对应课堂录音Week04 Part01 00:36:33–00:45:56
原第 23 页

把房屋施工表逐行读成先后关系

原课件第23页
点击原页可打开 PDF。

Duration是本项要做几天;Predecessor是本项开始前必须完成的任务。表中的数据是:

任务内容天数前驱
A地基8无
B墙和天花板10A
C屋顶9B
D布线8B、C
E门窗5B
F外墙10E
G公用设施2C、D、F
H景观3F
I油漆10G、H

例如D行写B、C,是说D必须等B和C都完成;G则要等C、D、F全部完成。A没有前驱,最早第0天开始。要找的不是九项工期总和,而是依赖关系下的最早全部完成时间。

对应课堂录音Week04 Part01 00:36:33–00:45:56Week04 Part01 00:45:57–00:50:51Week04 Part01 00:57:33–01:00:59
原第 24 页

用完成时刻把先后关系写成不等式

原课件第24页
点击原页可打开 PDF。

令 TJ 为活动J的完成时刻,dJ 为它的持续时间。因此“开始时刻”是 TJ−dJ。若K是J的前驱,J开始不能早于K完成:

TJ−dJ≥TK.

把表中每行都代入,得到全部约束:

TA−8≥0,TB−10≥TA,TC−9≥TB,(1)TD−8≥TB,TD−8≥TC,TE−5≥TB,(2)TF−10≥TE,TG−2≥TC,TG−2≥TD,(3)TG−2≥TF,TH−3≥TF,TI−10≥TG,(4)TI−10≥TH.(5)

例如D的两个前驱对应两条约束,两条都要满足。课件写 TD−8≥TB,TC,就是这两条的简写。

项目完成时刻是最后完成的活动时刻,记 z=max(TA,…,TI)。目标是最小化 z。

对应课堂录音Week04 Part01 00:57:33–01:00:59Week04 Part01 01:00:59–01:07:06
原第 25 页

把“所有完成时间的最大值”改写成线性约束

原课件第25页
点击原页可打开 PDF。

目标是 minz,原来把 z 写成最大值。引入辅助变量后,可以改成:

minz,z≥TA, z≥TB, …, z≥TI,

再加上一页的全部先后约束。为什么这些不等式已经够用?

  1. 若 z 不小于每个 TJ,它就至少等于最大的那个完成时间。
  2. 若 z 还大于这个最大值,可以把它往下降,不会违反任何一条 z≥TJ。
  3. 目标正好要求 z 尽量小,所以最优时会自动降到 maxJTJ。

例如完成时间是8、18、27,约束要求 z≥8,18,27,最小的合法 z 就是27。这样目标与约束全是线性的,得到线性规划。

对应课堂录音Week04 Part01 01:07:11–01:07:21Week04 Part01 01:08:54–01:14:29Week09 Part01 02:09:36–02:14:56
原第 26 页

逐项算出47天,并找出关键路径

原课件第26页
点击原页可打开 PDF。

每项都在允许的最早时间开始。遇到多个前驱,先取它们完成时间的最大值,再加本项工期。

任务最早开始的计算最早完成
A08
B818
C1827
Dmax(18,27)=2735
E1823
F2333
Gmax(27,35,33)=3537
H3336
Imax(37,36)=3747

最长的依赖链是 A→B→C→D→G→I,总长 8+10+9+8+2+10=47 天。链上的任务只能依次完成,所以任何方案都至少要47天;表中的排程恰好达到47天,因此它就是最短工期。

要算总时差,从第47天反推。I最迟开工是 47−10=37。G、H都要在37前结束,所以它们的最迟开工分别是 37−2=35 和 37−3=34。F要在G、H开工前完成,因此最迟开工是 min(35,34)−10=24。E最迟开工是 24−5=19。

总时差等于最迟开始减最早开始。E、F、H的总时差分别是 19−18=1、24−23=1、34−33=1 天。关键路径自身已占满47天,链上的其他六项都没有余量。这1天也不能由同一分支上的E、F、H分别用掉。

对应课堂录音Week04 Part01 00:50:56–00:52:52Week04 Part01 01:08:54–01:14:29
原第 27 页

40天完成:先读赶工成本表

原课件第27页
点击原页可打开 PDF。

正常最短工期47天,现在要求40天。表中的Cost表示“缩短该活动1天要额外花多少钱”,Maximum表示“最多可缩短几天”。

任务每缩短1天成本最多缩短天数
A50002
B90002
C70004
D45003
E15001
F35003
G不能缩短0
H45001
I95003

整体要缩短7天,不能直接买最便宜的7个“任务天”。例如E最便宜,但正常情况下E所在分支不是47天的关键路径,单独加快E并不会改变总工期。压短一条瓶颈后,其他分支也可能变成新瓶颈。

对应课堂录音Week04 Part01 01:08:54–01:14:29Week09 Part01 02:26:36–02:30:43
原第 28 页

缩短量进入工期后,符号怎样变化

原课件第28页
点击原页可打开 PDF。

令 xJ 表示活动J缩短的天数。原工期 dJ 变为 dJ−xJ,完成时刻仍为 TJ。所以新开始时刻是:

TJ−(dJ−xJ)=TJ−dJ+xJ.

把这个式子用于每条前驱关系:

TA−(8−xA)≥0,(1)TB−(10−xB)≥TA,(2)TD−(8−xD)≥TB,TD−(8−xD)≥TC,(3)TG−(2−xG)≥TC,TD,TF.(4)

展开括号后,xJ 前面是加号。例如G行的 TG−(2−xG) 展开为 TG−2+xG。本题G不能赶工,所以 xG=0。

40天内完成就是每个 TJ≤40。这样不必再写最大值:所有活动都在40以前结束,最后完成的活动自然也不晚于40。

对应课堂录音Week04 Part01 01:21:11–01:26:25Week09 Part01 02:30:46–02:36:32
原第 29 页

把赶工目标、边界和期限组装起来

原课件第29页
点击原页可打开 PDF。

赶工成本是“每缩短1天的价格×缩短天数”,再对所有活动求和:

minC=5000xA+9000xB+7000xC+4500xD+1500xE+3500xF+4500xH+9500xI.

每项缩短量有上限:

0≤xA≤2,0≤xB≤2,0≤xC≤4,(1)0≤xD≤3,0≤xE≤1,0≤xF≤3,(2)xG=0,0≤xH≤1,0≤xI≤3.(3)

再加入上一页全部“完成时刻−新工期≥前驱完成时刻”,以及 TA,…,TI≤40。现在一共两组决策:x 决定花钱压缩多少,T 决定各项何时完成。

本模型允许连续天数,所有式子线性,因此是LP。若题目额外要求缩短量必须是整数天,就需要再给 xJ 加整数条件。

对应课堂录音Week04 Part01 01:14:31–01:17:06Week04 Part01 01:21:11–01:26:25Week04 Part01 01:30:03–01:36:47Week09 Part01 02:09:36–02:14:56Week09 Part01 02:26:36–02:30:43Week09 Part01 02:30:46–02:36:32Week09 Part01 02:38:15–02:41:54
原第 30 页

40天赶工的46500方案怎样核算

原课件第30页
点击原页可打开 PDF。

这套线性规划的最优方案为:A缩短2天、B缩短2天、D缩短3天、E缩短1天、F缩短1天,其他不变。

先算钱:

C=2(5000)+2(9000)+3(4500)+1(1500)+1(3500)=46500.

再算是否真的能在40天完成:

任务新工期最早完成
A66
B86+8=14
C914+9=23
D5max(14,23)+5=28
E414+4=18
F918+9=27
G2max(23,28,27)+2=30
H327+3=30
I10max(30,30)+10=40

各活动的缩短量均在上限内,排程在第40天完成。下面用两条路径给出成本下界,可以手算验证46,500确实是最低成本。

这里为什么还花钱加快E和F?因为只压缩原47天关键路径时,另一条 A→B→E→F→H→I 会变成瓶颈。上述方案把经过G和经过H的两条收尾分支都压到了第30天,使油漆能第30天开始。

展开推导:为什么没法花得更少?

经过D、G的路径 A→B→C→D→G→I 原长47天,必须至少缩短7天。经过H的路径 A→B→E→F→H→I 原长46天,必须至少缩短6天。把两条路径上的缩短天数记为 r1,r2。G不能赶工,所以

r1=xA+xB+xC+xD+xI≥7,(1)r2=xA+xB+xE+xF+xH+xI≥6.(2)

把第一条乘6000,第二条乘3500,相加得到 6000r1+3500r2≥63000。这样加权后,每缩短1天,F的系数3500和实际单价相同。两条路径共有的I系数是 6000+3500=9500,也等于实际单价。把A、B、C、D、E、H的系数调整回实际单价,得到

C=6000r1+3500r2−4500xA−500xB(1)+1000xC−1500xD−2000xE+1000xH.(2)

用缩短量上限 xA≤2,xB≤2,xD≤3,xE≤1 给出负项的下界,正项至少为0。因此 C≥63000−9000−1000−4500−2000=46500。上面的排程恰好花46,500,所以达到成本下界。

对应课堂录音Week09 Part01 02:26:36–02:30:43Week09 Part01 02:30:46–02:36:32
原第 31 页

随机工期为什么不能只看平均数

原课件第31页
点击原页可打开 PDF。

前面的工期表把每项持续时间当成确定值。现实中天气、缺料、返工会让工期随机变化,这时问题从“最早哪天完成”变成“某天以前完成的概率是多少”。

例如一个关键任务有一半概率4天完成,另一半概率8天完成,平均值是6天。但承诺“6天内完成”,成功概率只有50%。平均6天与必定6天是两回事。

多个随机工期叠加时,还要考虑相关性:一场大雨可能同时拖慢多项户外任务。另一个扩展是资源限制:即使任务依赖允许并行,同一组工人也不能同时出现在两处。这些条件需要在基础模型上继续增加。

对应课堂录音Week04 Part01 01:26:25–01:29:49
原第 32 页

项目管理是一个独立的专业领域

原课件第32页
点击原页可打开 PDF。

截图展示了几所大学的项目管理课程。课件中的两个施工模型分别回答了这个领域的两个基本问题:工期固定时怎样排出最早完工的计划,以及期限固定时怎样以最低成本缩短工期。

原第 33 页

设施选址:先问这个地点怎样才算好

原课件第33页
点击原页可打开 PDF。

选址问题决定商店、仓库、工厂、医院等设施建在哪里。图片中的零售设施和医疗设施服务的目的不同,评价地点的标准也不同。

仓库可能希望运输距离短;诊所可能希望居民30分钟内可达;连锁店可能希望避免两家店挤在一起。因此选址没有唯一通用的目标。

接下来两个例子分别回答:①覆盖所有居民,诊所最少要几家?②固定开店数量,怎样让门店尽量分散?两题都用0或1表示“选不选”,但目标与约束不同。

对应课堂录音Week04 Part01 01:36:51–01:43:44
原第 34 页

诊所选址:每个社区都要30分钟可达

原课件第34页
点击原页可打开 PDF。

有 n 个农村社区,每个社区都是候选诊所地点。tij 表示从需求社区 i 开车到候选社区 j 的时间。

  1. 要选出一些社区建设诊所。
  2. 每个社区至少能在30分钟内到达一家已建诊所。
  3. 在满足覆盖的前提下,诊所数量尽量少。

图上40、50分钟的连线超过30分钟,不能用来覆盖相应社区。判断的是“从需求地 i 到设施地 j”的时间。选址范围是给定社区集合,因此变量只需说明哪些社区被选中。

对应课堂录音Week04 Part01 01:36:51–01:43:44
原第 35 页

“够近”是数据,“建不建”才是变量

原课件第35页
点击原页可打开 PDF。

先把行驶时间转成0或1的覆盖系数:

dij={1,tij≤30,0,tij>30.xj={1,在社区 j 建诊所,0,不建.

dij 已由道路时间确定,是已知数据;xj 是优化要决定的变量。对社区 i 而言,一家诊所能服务它,必须同时满足“地点够近”和“那里已建”。这由乘积 dijxj 表示。

例如某社区的覆盖行是 (1,0,1),选址为 (0,1,1):第1处够近但没建,贡献0;第2处建了但太远,贡献0;第3处既近又建,贡献1。总和 0+0+1=1,表示它可达1家已建诊所。

对应课堂录音Week04 Part01 02:01:54–02:07:36Week04 Part01 02:07:39–02:12:31
原第 36 页

集合覆盖模型:把“至少一家”写出来

原课件第36页
点击原页可打开 PDF。

xj 是是否在候选地点j建诊所,dij 是地点j是否能覆盖需求社区i。完整模型是:

minx∑j=1nxj,∑j=1ndijxj≥1(i=1,…,n),xj∈{0,1}.

目标数诊所总量;每条约束数某个社区可达的已建诊所。右边1表示至少一家。用 ≥1 而非 =1,因为被两家同时覆盖也满足服务要求。

三社区例子:

D=(110111011).

选 x=(0,1,0)T,相乘得到 Dx=(1,1,1)T,每个社区都被覆盖,只要1家。若0家,x=0 让每行都为0,违反约束。因此最少恰好1家。

对应课堂录音Week04 Part01 02:01:54–02:07:36Week04 Part01 02:07:39–02:12:31
原第 37 页

这里的困难来自0或1,不是乘积

原课件第37页
点击原页可打开 PDF。

目标 ∑jxj 是线性的,约束 ∑jdijxj≥1 也是线性的,因为 dij 是常数。常数乘变量仍是一阶项。

但 xj 必须取0或1。这个限制使问题成为0-1整数线性规划,属于MILP求解器处理的模型类型。

若把二元限制放宽为 0≤xj≤1,就得到连续LP松弛。松弛后的可行集合更大,所以它的最小目标值不高于原整数问题。它可以提供一个下界,但0.5不再对应合法的“建或不建”决定。

做题检查模型类型时,分别看“表达式是否线性”和“变量是否必须取整数”。这两个判断互不替代。

自测:LP允许选半家店,会低估到什么程度?

三个地点中,社区1能到1、2,社区2能到2、3,社区3能到1、3。实际至少要开两家,因为任意一家只覆盖两个社区。LP若允许选半家,则 x=(0.5,0.5,0.5) 让每条覆盖约束的左边都等于1,目标只有1.5。把三条覆盖约束相加还得到 2(x1+x2+x3)≥3,所以1.5正是LP的最低值,也是整数答案2的下界。

对应课堂录音Week04 Part01 02:07:39–02:12:31Week04 Part01 02:12:31–02:17:44Week04 Part01 02:21:12–02:26:37
原第 38 页

餐厅分散选址:让最近的两家也尽量远

原课件第38页
点击原页可打开 PDF。

从 m 个候选地点选出 n 家餐厅,m≥n。dij 现在表示地点i与j之间的距离。希望门店分散,采用的指标是:选中门店之间,最小的两两距离。

先对一个方案找“最挤的一对”,再让这对也尽量远。这叫最大化最小距离,即 max–min。它和最大化所有距离之和不同:总距离很大,仍可能有两家紧挨着。

例如方案A的三条店间距离是2、9、10,最小距离2;方案B是5、6、7,最小距离5。按本题目标选B,因为它避免了距离只有2的近邻门店。

对应课堂录音Week04 Part01 02:12:31–02:17:44
原第 39 页

先枚举一个小例子,理解max–min的两层

原课件第39页
点击原页可打开 PDF。

四个候选地点在直线的0、3、7、12处,要开3家店。逐个枚举三点组合,先算两两距离,再取其中最小值。

选择三条距离最小距离
0、3、73、7、43
0、3、123、12、93
0、7、127、12、55
3、7、124、9、54

比如选0、7、12时,最小距离是 12−7=5。对最后一列取最大值,得到该组最优。候选地点多时,逐个列出组合会变慢,后面改用二元变量表达同一个选择。

原第 40 页

先把最近点对的距离写成目标

原课件第40页
点击原页可打开 PDF。

令 xi∈{0,1} 表示地点i是否开店,w 表示选中门店之间的最小距离。选满n家店的条件是 ∑i=1mxi=n。这里求和上界是候选点数m,课件写成n,应改为m。

maxw,w=min{dij:xi=xj=1, i≠j},∑i=1mxi=n,xi∈{0,1}.

读目标时分两层:固定一组开店地点,先找其中距离最近的两家,得到w;再在不同选址组合之间,挑w最大的那组。假设至少开2家,才能形成要比较的点对。

上页选在0、7、12处时,这三个位置的变量取1,位置3的变量取0,满足“选满3家”。将最小距离5代入目标得到该组合的评分。

对应课堂录音Week04 Part01 02:12:31–02:17:44Week04 Part01 02:21:12–02:26:37
原第 41 页

怎样把带条件的最小值改成MILP

原课件第41页
点击原页可打开 PDF。

本页要求把上一页改写成混合整数线性规划。困难在 w=min{dij:xi=xj=1}:比较哪些距离,取决于哪些地点被选中。

先明确所需效果:两个地点都选中,就让它们的距离限制w;至少一个没选中,就让这对地点不影响w。我们需要一个能由0或1控制的“开关”。

不要直接写 min(dijxixj)。若一个地点没选中,乘积变0,这个0会错误地成为最小值。正确思路相反:未选中的点对应该被抬到足够大,退出最小值竞争。下一页用一个大常数M做到这一点。

原第 42 页

Big-M:未选的点对加上一个大数

原课件第42页
点击原页可打开 PDF。

选一个大于所有距离的正数M,定义调整后的距离:

eij=dij+M(2−xi−xj).

把二元变量的情况逐个代进去:

选址状态开关项调整后距离
两地都选2−1−1=0eij=dij
只有一地选2−1−0=1eij=dij+M
两地都没选2−0−0=2eij=dij+2M

原图中1、2都开店,所以是 e12=d12;1开而3不开,所以是 e13=d13+M;3、5都不开,所以是 e35=d35+2M。因为M大于所有原距离,任何未选点对的e都比选中点对大,不会成为最小值。

原第 43 页

把“只比较选中点对”变成“比较所有e”

原课件第43页
点击原页可打开 PDF。

上一页已经把未选点对的数值抬高。因此只对选中点对求最小距离,等价于对全部调整后距离求最小值:

min{dij:xi=xj=1, i≠j}=mini≠j{dij+M(2−xi−xj)}.

两地都选时保留真实距离;其他点对的数值都大于任何真实距离。只要至少选2家,就存在至少一个真实的选中点对,最小值必然从这些点对中产生。

所以模型现在变成最大化w,并满足 w=mini≠jeij、∑i=1mxi=n、xi∈{0,1}。点对的比较范围已经固定,剩下最后一步是去掉min。

原第 44 页

用一组上界替代min,得到线性模型

原课件第44页
点击原页可打开 PDF。

把 w=mini≠jeij 改成对每个点对都写 w≤eij。完整形式为:

maxx,ww,(1)s.t.w≤dij+M(2−xi−xj)(i<j),(2)∑i=1mxi=n,xi∈{0,1}.(3)

为什么只写“≤”也能取到正确值?所有约束把w压在每个e下面,所以w最多等于最小e;而目标要把w推高,就会恰好推到最小e。与前面“最小化最大完成时间”的做法对称。

这里 dij 和M都是常数,右边只含 −Mxi−Mxj 这样的线性项,因此是MILP。对称距离只需写 i<j,避免同一对重复。M选得超过最大距离即可,没必要无限取大。

代入第39页的选址,核对 Big-M 约束

四个候选点的最远距离是12,取 M=13。选0、7、12时,三个已选点对给出 w≤7,12,5。地点3未选,它与另外三个地点的约束右端分别变为 3+13=16、4+13=17、9+13=22。把六条上界放在一起,w 最大只能取5,恰好等于枚举算出的最近距离。

原第 45 页

数学最优之前,先检查目标选得对不对

原课件第45页
点击原页可打开 PDF。

最大化最小距离把附近门店争夺同一批顾客的问题简化成了距离。这个指标适合用来避免门店太接近。若真正要优化的是总利润,还需要知道各处的租金、客流和门店之间如何分流。有了这些数据,才能给每个选址方案计算利润。

原第 46 页

聚集也可能有好处:冲动购买与商圈效应

原课件第46页
点击原页可打开 PDF。

地图上几家茶饮店集中在同一片商圈。课件提出另一种可能:人们在逛街时反复路过门店,更容易临时决定买一杯。相邻门店可能分摊已有顾客,也可能通过提高品牌曝光吸引额外顾客。判断哪种效应占主导,需要观察门店距离变化时的总销售变化。

原第 47 页

旅行商:把所有地点连成一条回路

原课件第47页
点击原页可打开 PDF。

配送、自行车路线、校车和快递图片引出访问顺序问题。最基本的旅行商问题是:给定若干地点,每个地点恰好访问一次,最后回到起点,总路程最短。

这里的决定不是“地点选不选”,而是“从地点i接着去哪个地点”。例如A、B、C三个地点,一条回路是 A→B→C→A。地点多以后,顺序组合迅速增多,需要用变量和约束统一表示。

原第 48 页

边变量xij:从i直接走到j吗

原课件第48页
点击原页可打开 PDF。

给定n个地点,cij 是从地点i到j的距离。定义:

xij={1,路线从 i 直接走到 j,0,不走这条边.i≠j.

例如 x13=1 表示访问地点1以后,下一站就是地点3,这段贡献距离 c13。若 x13=0,这段不计入总路程。

目标把全部被选择的有向边距离相加。每个地点都恰好访问一次,需要恰好一条入边、一条出边,并且最终所有边应连成同一个大回路。

原第 49 页

先写目标和每点一进一出

原课件第49页
点击原页可打开 PDF。

总路程是所有边的“距离×选没选”,于是先写:

minx∑i=1n∑j≠icijxij,(1)s.t.∑j≠ixij=1(i=1,…,n),(2)∑j≠ixji=1(i=1,…,n),(3)xij∈{0,1}(i≠j).(4)

第一组求和固定起点i,数从i离开的边,必须正好1条。第二组固定终点i,数进入i的边,也必须正好1条。没有 xii,防止“留在原地”冒充访问。

这些条件保证每点的局部连接数量正确。接下来要检查:局部正确是否已经保证整个路线连通?

原第 50 页

两个小回路也满足一进一出

原课件第50页
点击原页可打开 PDF。

原图把六个点分成两个三点回路。每个点都有且只有一条入边和一条出边,所以它完全满足上一页的两组等式。

但它不能让旅行商沿同一条连续路线访问全部地点:走完左边三个点就回到起点,根本到不了右边三个点。这样的小回路叫 subtour(子回路)。

用编号写清:1→2→3→1 与 4→5→6→4。每点一进一出全部成立,却不符合一个六点大回路的要求。因此需要额外约束排除子回路。

原第 51 页

数一个三点集合内部有几条已选边

原课件第51页
点击原页可打开 PDF。

选一个恰好包含3个地点的集合Q,计算:

∑i∈Q∑j∈Qj≠ixij.

两个求和都限制在Q内部,因此只数“起点和终点都在Q里”的已选边,跨出Q或从外部进入Q的边都不算。

原图左边的大回路中,虚线框住的三个点构成一段连续路径。内部只有2条已选边,第三个点的下一条边离开框,所以计数2。右边若取刚好形成三点小回路的那三个点,内部有3条边,计数3。

于是出现区别:三个点形成完整小回路时,内部边数等于3;三个点只是大回路的一部分时,不会在内部闭合,最多只有2条。

原第 52 页

禁止所有三点集合内部出现3条边

原课件第52页
点击原页可打开 PDF。

在每点一进一出的条件下,一个三点子回路会用3条内部边。要排除它,可以要求对每个三点集合Q:

∑i∈Q∑j∈Qj≠ixij<3.

因为每个 xij 都是0或1,左边为整数,所以“小于3”等价于“不超过2”:

∑i∈Q∑j∈Qj≠ixij≤2.

一定要检查所有三点集合,而不是只检查图上圈出的一个。否则小回路可能出现在另一个三点组合里。

这能排除长度3的子回路,但还需要处理长度2、4、5等其他情况。把3推广成任意子集的大小,就得到最后一页的完整条件。

原第 53 页

子回路消除:任意真子集都不准自行闭合

原课件第53页
点击原页可打开 PDF。

对任意至少2个点、但还没包含全部n个点的集合Q,加入:

∑i∈Q∑j∈Qj≠ixij≤|Q|−1,2≤|Q|≤n−1.

|Q| 是集合内的地点数。若Q内部自行形成回路,会用 |Q| 条边,超过允许的 |Q|−1;如果它只是完整大回路的一部分,至少有一条边必须离开Q,因此内部边数不超过 |Q|−1。

例如 Q={1,2} 时,要求 x12+x21≤1,两条方向相反的边不能同时选。Q含3点时,右边为2,得到上一页的条件。若把全体地点也作为Q,会要求整个回路少用一条边,所以只给真子集加约束。

完整TSP模型就是:距离总和最小、每点一条入边、每点一条出边、全部真子集的子回路约束,以及边变量二元。前两组使路线分成若干回路,子回路约束再把所有非全体回路排除,最后只剩包含全部地点的一个大回路。

所有表达式都线性,而变量取0或1,所以这是整数线性规划。子集数量很多,也解释了为什么TSP比普通连续线性规划难。