DASE 7113 · 课程精讲

优化导论

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

逐页目录 · 共 38 页
  1. 这一讲:把实际选择写成优化问题
  2. 老师的研究背景
  3. 课程与答疑信息
  4. 小组项目要做成什么样
  5. 优化的三个组成部分
  6. 怎样读一个数学规划
  7. 高中线性规划就是几何版本
  8. 应用、理论、算法各自回答什么
  9. 不同领域共享同一套建模语言
  10. 神经网络训练也是优化
  11. 交通灯与配送路线:两种不同的决定
  12. 地铁图:目标不同,最佳路线就可能不同
  13. 库存:少订怕缺货,多订怕积压
  14. 充电调度:把电量放到合适时段
  15. 结构设计:在性能要求下选材料与厚度
  16. 医疗排程:资源不能同时被两件事占用
  17. 收入管理:单价提高,销量可能下降
  18. 交通系统里有两层决定
  19. 两条路线与流量守恒
  20. 每人时间与总旅行时间
  21. 总需求只有半个 c:大家为什么都走 A
  22. 总需求等于 c:无收费均衡
  23. 全走 B:总时间相同,选择却不稳定
  24. 道路被使用,不一定带来系统收益
  25. 收费怎样改变个人选路
  26. 社会最优收费模型如何建立
  27. 最优收费为 1/2,怎样一步步算出来
  28. 为什么收费能改善系统效率
  29. 私人经营者会选出什么收费
  30. 收入模型:单价乘使用人数
  31. 私人最优恰好与社会最优相同
  32. “失灵”具体指哪种低效
  33. Braess 原网络:两条路线各用 1.5
  34. 增加免费连接,为什么旧分流不稳定
  35. 新均衡:总时间由 1.5 变成 2
  36. 多一条路为什么可能更拥堵
  37. 容量设计与拥堵收费的区别
  38. 全课程的建模与求解路线
原第 1 页

这一讲:把实际选择写成优化问题

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

优化就是:有许多可选方案,先规定什么叫“好”,再找一个满足规则的最好方案。比如去学校可以选不同路线,“最快”“最便宜”“少换乘”是三种不同目标,得到的最佳路线也可能不同。

这一讲先认识变量、目标和约束,再用两条路的收费问题和 Braess 悖论练习建模。学完要能回答:谁在做决定?他希望什么变小或变大?他的决定又会怎样影响别人?

原第 2 页

老师的研究背景

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

老师本科在清华学习数学,博士在 Northwestern University 学习土木与环境工程,之后在港大数据与系统工程学部任教。

这解释了课件的两条线:用数学描述问题,用交通系统说明数学为什么有用。交通只是入门案例,同样的建模方法还可以用于机器学习、机器人、生产和排班。

原第 3 页

课程与答疑信息

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

这份课件写的上课地点是 K.K. Leung Building 202,时间为周一 19:00–21:50;授课教师是 Prof. Jiayang Li,邮箱为 jiayangl@hku.hk,Office Hour 需要预约。

原第 4 页

小组项目要做成什么样

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

课件规定每组 3–4 人,要完成约 4000 词报告与展示。选一个实际优化问题,报告先说明问题动机和建模过程,再用 1–2 种算法求解至少一个数值案例。

  1. 讲问题:例如一家店如何安排员工,才能少缺人又少付加班费。
  2. 写模型:决定每个人在哪些时段上班;目标是总成本小;约束是每个时段人数够、每人工作时间不超限。
  3. 求解:把实际人数、工时和工资放入模型,算出一张班表。
  4. 解释:检查班表是否遵守规则,成本是多少,算法为什么适用。

项目的主线是“实际问题 → 模型 → 算法 → 计算结果”,每一部分都要接得上。

原第 5 页

优化的三个组成部分

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

变量是你能决定的事,目标是判断好坏的尺子,约束是必须遵守的规则。

  • 决策变量 x:例如生产多少件产品;若同时决定多种产量,用向量 x=(x1,x2,…)。
  • 目标函数 f(x):输入一个决定,输出一个分数,例如成本、时间或利润。
  • 约束函数 gi(x),hi(x):用不等式或等式表达限制;i 是第几条约束的编号。

例如每件利润 5 元,最多做 10 件:变量是产量 x,目标是最大化 5x,规则是 0≤x≤10。因此做 10 件最好,利润为 50 元。

本页写 gi(x)≥0,后面采用 gi(x)≤0。换约定时把整个函数乘以 −1:x≥0 就写成 −x≤0。

原第 6 页

怎样读一个数学规划

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

课件把三部分排成标准形式:

minxf(x)s.t. gi(x)≤0 (i=1,…,m),hj(x)=0 (j=1,…,p).

读法是:“选择 x,让 f(x) 尽可能小,同时满足全部 m 条不等式和 p 条等式。”min 表示最小化,s.t. 是 subject to,意思是“受以下条件限制”。mathematical program 是数学规划,即这个数学问题。

用一个具体问题走一遍:

minx(x−3)2,x≤2,x≥0.
  1. 先看规则:合法范围是 [0,2]。
  2. 平方表示 x 到 3 的距离的平方,越接近 3 越好。
  3. 合法范围里离 3 最近的是 2,所以 x*=2。
  4. 最优目标值为 f(x*)=(2−3)2=1。

x* 是最好方案,f(x*) 是这个方案的得分。

原第 7 页

高中线性规划就是几何版本

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

图中横、纵坐标代表两个决策变量;红色直线代表约束边界;绿色区域是所有约束同时允许的地方,叫可行域。一个点对应一组选择 (x,y)。

  1. 每条不等式先画成边界直线。
  2. 选一个测试点,代入判断应保留哪一侧。
  3. 保留所有允许区域的交集,即绿色部分。
  4. 平移目标函数的等值线,寻找仍能接触可行域的最好位置。

例如最大化 x+y,条件为 x≥0,y≥0,x+y≤4。目标线为 x+y=k,k 越大越好;最大只能到 4,所以边 x+y=4 上的每个可行点都是最优解。最好方案可以有多个。

原第 8 页

应用、理论、算法各自回答什么

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

图中三个层次是 Theory、Algorithms、Applications,即理论、算法、应用。理论研究解的性质,算法研究怎样算,应用决定要解决什么现实问题。

本课从应用出发。先弄明白每个变量对应现实中的什么决定,再研究模型有没有好用的结构,最后选择计算方法。比如先明白“收费改变选路”,才会理解为什么需要均衡约束。

原第 9 页

不同领域共享同一套建模语言

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

本页列出机器学习、供应链、交通、生产、金融、库存、通信、机器人、医疗、能源、环保、营销、资源调度、结构设计、生物信息、博弈、项目管理、定价和风险管理等应用。

学习时在每个场景中找三件事:

场景变量目标约束
机器人走路路径和速度时间或能耗小不撞障碍、关节不过限
仓库订货订货时间与数量库存和缺货成本小仓容、交货时间
机器学习模型参数预测误差小可能有参数或复杂度限制

能把场景翻译成这三栏,就开始掌握优化建模了。

原第 10 页

神经网络训练也是优化

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

图中圆点是神经元,左边输入数据,中间逐层计算,右边给出预测。连线上的权重可以调整;训练就是调整它们,让预测接近正确答案。

先看只有一个权重的版本:y^=wx,已知样本 x=2,y=6。x、y 是数据,w 是要调整的变量。平方损失为:

L(w)=(y^−y)2=(2w−6)2.

求导:L′(w)=2(2w−6)·2=4(2w−6)。令导数为 0,得 2w−6=0,所以 w=3。代回预测 y^=3×2=6,损失为 0。平方损失不可能小于 0,所以这就是全局最小值。

复杂网络沿用同样的“参数 → 预测 → 损失 → 调整参数”主线,只是参数更多、函数更复杂。

原第 11 页

交通灯与配送路线:两种不同的决定

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

左图是交通灯,右图是配送网络。交通灯决定各方向绿灯多久;配送决定先去哪一站、后去哪一站。场景相关,变量性质却不同。

例如周期 60 秒,两个方向绿灯为 g1,g2,暂不计转换时间。约束可写为 g1+g2=60、g1,g2≥10,目标是总等候时间最小。绿灯时长可以连续调整。

配送中的访问顺序是离散选择。读右图先找客户点,再沿彩色路线检查经过顺序;路线需要满足每个客户的服务要求。

原第 12 页

地铁图:目标不同,最佳路线就可能不同

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

车站是节点,站间连接是边,颜色区分线路;交会站提示可以换乘。先找起终点,再沿实际连接走,图上的直线距离不是乘车时间。

假设路线 A 用 20 分钟、换乘 2 次;路线 B 用 24 分钟、不换乘。只看时间选 A;若每次换乘额外计 5 分钟不便成本,A 的广义成本为 20+2×5=30,B 为 24,此时选 B。

这说明“最优”一定对应一个明确的目标函数。少用时与少换乘可以通过权重合成一个指标,也可以分别比较。

原第 13 页

库存:少订怕缺货,多订怕积压

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

图中是货架与库存管理。变量是何时订货、订多少;两类主要损失是积压成本和缺货损失。

设需求 100 件,订货量 q。剩余库存为 max(q−100,0),缺货为 max(100−q,0)。max 表示取较大的数,确保数量非负。

若每剩一件成本 1 元、每缺一件损失 4 元:

C(q)=max(q−100,0)+4max(100−q,0).

订 80 件的成本为 4×20=80;订 120 件成本为 20;订 100 件成本为 0。因此需求已知时,100 件最好。需求不确定时,需要同时考虑不同可能需求及其概率。

原第 14 页

充电调度:把电量放到合适时段

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

变量可以是每个时段的功率 pt,t 是时段编号。功率乘时长等于电量:2 千瓦充 3 小时得到 6 千瓦时。

假设需充 6 千瓦时,有三个各 1 小时的时段,每时段最多充 3 千瓦时,电价依次 1、2、4 元/千瓦时。令电量为 e1,e2,e3:

mine1+2e2+4e3,e1+e2+e3=6,0≤et≤3.

只要较贵时段正在用电,而较便宜时段还有余量,把一部分电量移过去就能降成本,总电量仍是 6。因此最便宜时段充 3,第二时段充 3,第三时段为 0。总成本 3×1+3×2=9 元。车辆到离时间、电网功率限制等,都可继续加入约束。

原第 15 页

结构设计:在性能要求下选材料与厚度

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

图中比较不同道路结构,从路面向下为不同材料层。可以调整各层材料、厚度,但必须达到承载力、变形和寿命要求。

最简单的模型:厚度为 h,成本 100h,性能要求 h≥0.2。因为 h 越大成本越高,最低可行厚度 0.2 最好,成本为 20。

复杂结构也是同样逻辑:先用工程关系把厚度与性能联系起来,再寻找满足性能要求的低成本设计。图中的层次用于辨认组成,性能约束来自结构计算。

原第 16 页

医疗排程:资源不能同时被两件事占用

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

左边是手术场景,右边是时间安排表。病人、医生、手术室和设备都需要配合;同一资源不能同时分给两台手术。

一间手术室里有两台各需 2 小时的手术,开始时刻为 s1,s2,都不能早于上午 8 点。不重叠意味着:

s1+2≤s2或s2+2≤s1.

第一条是先做 1,第二条是先做 2。最早可安排 8–10 点与 10–12 点,全部完成时间 12 点。“或”表达顺序选择,常需整数变量处理。

原第 17 页

收入管理:单价提高,销量可能下降

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

酒店与机票等场景要决定价格、预订数量和容量分配。收入是单价乘实际销量,而销量会随价格改变。

设价格 p,需求 q(p)=100−p,范围 0≤p≤100。则收入:

R(p)=p(100−p)=100p−p2.
  1. 求导 R′(p)=100−2p。
  2. 令导数为 0,得 p=50。
  3. 二阶导 R″(p)=−2<0,所以是最大值。
  4. 销量为 50,收入为 50×50=2500。

若酒店只有30间房,实际销量为 min{100−p,30}。把两个区间分别算清:

  1. 0≤p≤70 时,需求至少30,实际只能卖30间,收入 R=30p,价格越高收入越多。
  2. 70≤p≤100 时,需求不超过30,收入 R=p(100−p),导数 100−2p<0,价格越高收入越少。

所以两段在 p=70 接上时最好:卖30间,收入 70×30=2100。容量限制使最优价格从50变为70。

原第 18 页

交通系统里有两层决定

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

老师研究怎样改善交通系统表现。管理者决定容量、信号、收费;出行者决定走哪条路。

两层决定相互影响:收费使人改道,改道改变拥堵,拥堵又改变路线吸引力。评价政策需要算出人们改变选择以后的结果。

两路模型把这个反馈简化为一条容易拥堵的路与一条时间固定的路,用少量符号就能把选择机制说清楚。

原第 19 页

两条路线与流量守恒

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

Home 是起点,Work 是终点,A、B 是替代路线。每天共有 n 人。设 xA 人走 A、xB 人走 B:

xA+xB=n,xA,xB≥0.

第一式叫流量守恒:每个人恰好选一条,人数合计就是总需求。只要知道 xA,就能算 xB=n−xA。

A 在人少时快,但流量增加会变拥堵;B 较稳定。给出时间与流量的函数后,就可以计算各条路线吸引多少人。

原第 20 页

每人时间与总旅行时间

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

课件给的每人旅行时间为:

tA(xA)=xAc,tB(xB)=1,c>0.

c 是 A 的容量尺度:当 xA=c 时 A 时间为 1。若 c=100,50 人在 A 时每人 0.5,100 人时每人 1。B 按固定时间 1 计算。

总旅行时间是“每路人数 × 每人时间”相加:

T=xAtA+xBtB=xA2c+xB=xA2c+n−xA.

例如 A 上 50 人、每人 0.5,贡献 25;B 上 50 人、每人 1,贡献 50,总时间 75。某个人的时间和所有人的总时间要区分。

这100人的平均旅行时间为 75/100=0.75。先把每条路的“人数×每人时间”相加,再除以总人数,就能从总时间换成平均时间。

原第 21 页

总需求只有半个 c:大家为什么都走 A

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

令 n=0.5c。全部走 A 时,xA=0.5c,xB=0,有:

tA=0.5cc=0.5<1=tB.

A 明显更快,所以有人走 B 就会想改到 A;全部走 A 时,没人愿意换到较慢的 B。个人没有动力改道的稳定状态叫用户均衡。

求均衡时要比较路线成本,而不是机械地把人平均分到两路。这里全走 A 也不拥堵到比 B 慢,所以全走 A 合理。

原第 22 页

总需求等于 c:无收费均衡

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

令 n=c,全部走 A,则 xA=c,xB=0,A 每人时间 c/c=1,与 B 相等。总时间:

T=c×1=c.

这个状态下没有更便宜的单人改道,因而是均衡。模型把交通看成连续流量,单个出行者对总流量的改变可忽略。

如果一部分人去 B,使 xA<c,A 就比固定时间为 1 的 B 快,于是 B 上的人会想回来。因此无收费选择会把流量推向 A。

原第 23 页

全走 B:总时间相同,选择却不稳定

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

若全部 c 人改走 B,xA=0,xB=c,则:

T=0+c×1=c.

总时间与全走 A 一样,但这不是均衡。A 此时空着,tA(0)=0,有人去 A 能明显节省时间,于是大家不会一直自愿留在 B。

一个分流的系统总时间,与它是否符合每个人的选择动机,是两种不同的检查。两者都需要计算。

原第 24 页

道路被使用,不一定带来系统收益

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

图中说 A “被使用”,但“没有发挥作用”。它指无收费均衡总时间为 c,和只有 B 时一样。A 被挤得太满,原先“人少时快”的优势消失了。

试着平均分流:A、B 各 c/2 人。A 每人 0.5,B 每人 1,总时间为:

T=c2·12+c2·1=3c4.

它比 c 小,但 B 上的人会想改去较快的 A。于是需要一种方法,让系统更好的分流也能符合个人动机。

原第 25 页

收费怎样改变个人选路

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

用希腊字母 π 表示 A 路的可调收费。先把费用换成与行驶时间一致的成本单位:例如1小时价值20元,10元收费便折算为0.5小时。出行者比较:

CA=xAc+π,CB=1.

这是广义成本,包含行驶时间和费用。收费不直接改变物理行驶时间,而是使 A 的吸引力下降,促使一部分人选 B。

两路都有人使用时,均衡要求广义成本相等:

xAc+π=1.

若一边更贵,那边的人还会改道。这个等式把管理者的收费与使用者的分流联系起来。

心算一次:设 n=c=100、π=0.2。由 xA/100+0.2=1,得到 xA=80、xB=20。A的实际时间为0.8,加收费后成本为1;B的时间与成本都是1,所以没人能靠换路省成本。

原第 26 页

社会最优收费模型如何建立

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

仍令总人数 c。管理者选择收费,使全部人的实际旅行时间最小:

minT=xA2c+c−xA,xAc+π=1.
  1. 从均衡式得到 xA/c=1−π,故 xA=c(1−π)。
  2. 流量守恒给 xB=c−xA=cπ。
  3. 在这段均衡关系中,xA≥0 给出 π≤1,而 xB≥0 给出 π≥0。端点 π=0,1 各对应一条路没有流量,广义成本仍相等。
  4. 代回目标:
T(π)=[c(1−π)]2c+cπ=c(1−2π+π2)+cπ=c(1−π+π2).

目标只统计实际旅行时间。收费是使用者交给经营者的钱,在此社会目标中按转移处理。若 π≥1,A 无流量,总时间为 c,要按这个边界情形计算。

原第 27 页

最优收费为 1/2,怎样一步步算出来

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

对 T(π)=c(π2−π+1) 求导:

T′(π)=c(2π−1).

令导数为 0,2π−1=0,所以 π*=1/2。二阶导 T″=2c>0,曲线向上弯,且该点在可行范围内,因此是最小点。

代回分流:xA=xB=c/2。A 每人时间 1/2,B 为 1,总时间:

T*=c2·12+c2·1=3c4.

相比 c 减少 (c−3c/4)/c=25%。若 c=100,总时间由 100 降为 75。两路广义成本都为 1,但实际行驶时间分别是 0.5 和 1。

动手试 · 调收费,看车流和总时间

取总流量 c=100。先试收费 0、0.5、1,比较分流与实际总时间。

原第 28 页

为什么收费能改善系统效率

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

A 上新增一名使用者,除了占用自己的时间,还会让原有使用者变慢。个人选路时只比较自己的成本,没有计入全部外部延误。

把 A 路的总时间 xAtA(xA) 用乘积法则对人数和每人时间分别求导。

ddxA[xAtA(xA)]=tA(xA)+xAtA′(xA)=xAc+xAc.

第一项是每单位新增流量本身的时间。第二项把已有流量和每人的边际延误相乘,得到每单位新增流量给他人带来的外部延误。

社会最优时 xA=c/2,这个外部成本等于 1/2。收取相同的 1/2,就让个人在选路时承担这部分影响,这就是拥堵收费的依据。

用人数看这件事:设 c=100,A原有50人。流量增加1后,每个原有使用者多花 1/100=0.01 单位时间;这50人合计多花 50×0.01=0.5。这0.5就是新来者造成的外部延误,新来者自己的时间另算。

原第 29 页

私人经营者会选出什么收费

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

Knight 的论点是:如果 A 路私人经营,经营者为了赚钱而收费,也可能纠正低效分流。

社会管理者最小化总时间,经营者最大化“每人收费 × 使用人数”。提高收费会增加单车收入,同时减少需求,必须把两者放入同一个收入函数。

本模型里,两种目标最后恰好得到相同收费;理解这个结果需要算收入随收费如何变化。

原第 30 页

收入模型:单价乘使用人数

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

收费为 π,使用人数为 xA,收费收入为 R=πxA。沿用均衡需求 xA=c(1−π),得:

R(π)=cπ(1−π)=cπ−cπ2,0≤π≤1.

当 π=0,人多但不收钱,收入为 0;当 π=1,没人走 A,收入也为 0。中间需要平衡单价与需求。

课件称为利润最大化,公式没有列运营成本项,因此这里具体最大化的是收费收入。若收费超过 1,需求仍为 0。

原第 31 页

私人最优恰好与社会最优相同

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

对收入 R=cπ−cπ2 求导:

R′(π)=c(1−2π).

令导数为 0 得 π*=1/2。二阶导 R″=−2c<0,所以是最大值。两端收入为 0,中间收入:

R(1/2)=c·12·12=c4.

此时 A、B 各 c/2 人,总旅行时间 3c/4,与社会最优分流一致。

收费 1/2、收入 c/4、总时间 3c/4 是三个不同的量:一致的是两种目标选出的收费与分流。

原第 32 页

“失灵”具体指哪种低效

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

课件把免费道路下的低效分流称为 market failure 或 government failure。具体差别是:个人自由选路的总时间为 c,而系统可实现的最优值为 3c/4。

相差的 c/4 来自个人没有计入全部拥堵影响。在这个模型里,收费把个人选择引导到系统最优,私人经营者追求收入也恰好得到同样结果。

这页的核心是:每个人都不愿改道,只说明个人均衡;要判断系统是否最好,还得比较总成本。

原第 33 页

Braess 原网络:两条路线各用 1.5

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

节点 1 为起点、4 为终点,2、3 为中间节点。道路与时间分别为:1→2 的时间 t1=x1;1→3 的时间 t2=1;2→4 的时间 t3=1;3→4 的时间 t4=x4。x 是对应道路的流量。

总需求为 1。设上路 1→2→4 的流量为 f1,下路 1→3→4 的流量为 f2,有 f1+f2=1。两条路线时间为:

c1=f1+1,c2=1+f2.

如果所有流量走上路,上路时间为 2,空着的下路只需 1,就会有人改道。全走下路也一样。因此均衡时两路都有流量,而且时间相等。由 f1+1=1+f2 得 f1=f2,与总量联立得各 0.5。每路用时 0.5+1=1.5,总时间为 0.5×1.5+0.5×1.5=1.5。

原第 34 页

增加免费连接,为什么旧分流不稳定

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

新增道路 2→3,时间 t5=0。第三条路线变为 1→2→3→4。

暂时保留旧流量:f1=f2=0.5,f3=0。两条会拥堵的边仍各有 0.5,于是:

c1=0.5+1=1.5,c2=1+0.5=1.5,c3=0.5+0+0.5=1.

新路线更快,原两路上的人都会想改过去。从原上路改道会增加3→4的流量,从原下路改道会增加1→2的流量;随着两边的人转入,两条拥堵边都逐渐变拥堵,因此不能把新路线最初的时间 1 当成最终时间。

原第 35 页

新均衡:总时间由 1.5 变成 2

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

f1 是上路流量,f2 是下路流量,f3 是新增路线流量,满足 f1+f2+f3=1。边 1→2 流量为 f1+f3,边 3→4 为 f2+f3。故三条路线时间:

c1=f1+f3+1,c2=1+f2+f3,c3=f1+f2+2f3=1+f3.

从前两式分别减去 c3=1+f3。上路多出 f1,即 c1−c3=(f1+f3+1)−(1+f3)=f1。下路同理,c2−c3=f2。只要上路仍有正流量,它就比新路贵;下路同理。因此均衡为 f1=f2=0,f3=1。

两条拥堵边各有 1 单位流量,新路时间 1+0+1=2。其他路线也都是 1+1=2,没人有更便宜的单人改道,均衡成立。

总时间 1×2=2>1.5,增加 (2−1.5)/1.5=1/3,约 33.3%。这就是 Braess 悖论。

看中间过程:让原两路始终平均分担剩余需求,即 f1=f2=(1−f3)/2。把下列数值代回公式:

新路线流量 f3原上、下路各自时间新路线时间
01.51
0.51.751.5
122

前两行中,新路线仍更快,改道还会继续;到最后一行才没有更快的路线可换。

原第 36 页

多一条路为什么可能更拥堵

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

因果顺序是:新增连接 → 出行者改道 → 两条拥堵边一起变慢 → 新均衡时间变长。关键是大家的选择发生了反馈。

管理者可以安排上路、下路各走一半,新路不用,总时间仍为 1.5。若每个人自由选路,这个分流会被打破,因为新路起初只要 1 个时间单位,大家会想转过去。

道路投资因此要比较“旧网络均衡”与“新网络均衡”,重新计算分流后再判断系统收益。

继续推一步,算出新路网的系统最优总时间

设新路流量为 s=f3,其余两路满足 f1+f2=1−s。两条拥堵边的流量是 a=f1+s 和 b=f2+s,所以 a+b=1+s。两条拥堵边的总时间为 a2+b2,两个固定时间为 1 的边贡献 1−s。由 a2+b2=12(a+b)2+12(a−b)2,固定 s 时让 a=b 最好。此时总时间为 12(1+s)2+1−s=32+12s2,所以 s=0 时总时间最小,为 1.5。

原第 37 页

容量设计与拥堵收费的区别

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

图中交通管理者可以选择两种控制手段:

手段改变什么两路模型中的例子
容量扩展道路实际性能增大 c,使同一流量下 x_A/c 降低
拥堵收费个人感知的广义成本增加 π,使 A 的成本 x_A/c+π 上升

固定总需求 n=100,从 c=100 扩容到 c=300。扩容后的免费均衡中,即使全走 A,每人时间也只有 100/300=1/3,比走 B 快,总旅行时间是 100/3。容量若保持 c=100,改收 π=1/2 则会形成 50 人走 A、50 人走 B 的均衡,总旅行时间是 75。比较两种方案时,还要在旅行时间之外计入建设成本。

原第 38 页

全课程的建模与求解路线

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

第一条主线是建模:把数据科学与系统工程问题写成变量、目标、约束。第二条主线是求解:检查模型结构,再选方法。

  • 无约束凸优化:变量可连续自由调整,目标凸。
  • 有约束凸优化:还要同时遵守等式和不等式。
  • 整数规划:表达选择、数量必须为整数等决定。
  • 元启发式:通过搜索策略探索复杂问题的较好方案。

本讲应能自己复现三件事:解释变量、目标和约束;从均衡式算出收费 1/2;逐边算出 Braess 网络加路前的 1.5、加路后的 2。

对应课堂录音Week07 Part01 00:12:56–00:18:19