优化就是:有许多可选方案,先规定什么叫“好”,再找一个满足规则的最好方案。比如去学校可以选不同路线,“最快”“最便宜”“少换乘”是三种不同目标,得到的最佳路线也可能不同。
这一讲先认识变量、目标和约束,再用两条路的收费问题和 Braess 悖论练习建模。学完要能回答:谁在做决定?他希望什么变小或变大?他的决定又会怎样影响别人?
共 38 页。按原课件顺序,左侧看原页,右侧读讲解。
是上路流量, 是下路流量, 是新增路线流量,满足 。边 1→2 流量为 ,边 3→4 为 。故三条路线时间:
从前两式分别减去 。上路多出 ,即 。下路同理,。只要上路仍有正流量,它就比新路贵;下路同理。因此均衡为 。
两条拥堵边各有 1 单位流量,新路时间 。其他路线也都是 ,没人有更便宜的单人改道,均衡成立。
总时间 ,增加 ,约 33.3%。这就是 Braess 悖论。
看中间过程:让原两路始终平均分担剩余需求,即 。把下列数值代回公式:
| 新路线流量 | 原上、下路各自时间 | 新路线时间 |
|---|---|---|
| 0 | 1.5 | 1 |
| 0.5 | 1.75 | 1.5 |
| 1 | 2 | 2 |
前两行中,新路线仍更快,改道还会继续;到最后一行才没有更快的路线可换。
因果顺序是:新增连接 → 出行者改道 → 两条拥堵边一起变慢 → 新均衡时间变长。关键是大家的选择发生了反馈。
管理者可以安排上路、下路各走一半,新路不用,总时间仍为 1.5。若每个人自由选路,这个分流会被打破,因为新路起初只要 1 个时间单位,大家会想转过去。
道路投资因此要比较“旧网络均衡”与“新网络均衡”,重新计算分流后再判断系统收益。
设新路流量为 ,其余两路满足 。两条拥堵边的流量是 和 ,所以 。两条拥堵边的总时间为 ,两个固定时间为 1 的边贡献 。由 ,固定 s 时让 最好。此时总时间为 ,所以 时总时间最小,为 1.5。