第八次问,线性规划对偶的问题
  • 板块学术版
  • 楼主FLY_lai
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/9/2 19:10
  • 上次更新2024/9/2 23:50:01
查看原帖
第八次问,线性规划对偶的问题
488052
FLY_lai楼主2024/9/2 19:10

论文:http://www.nfls.com.cn:10611/up/paper/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2021%E8%AE%BA%E6%96%87%E9%9B%86.pdf

丁晓漫《再探线性规划对偶》

下面的问题都是关于文中的 "最小费用流模型" 的。

最小费用流模型有一个标准式子 min⁡{∑ubupu+∑uvcuvmax⁡(0,pv−pu−wuv)}\min\{\sum_ub_up_u+\sum_{uv}c_{uv}\max(0,p_v-p_u-w_{uv})\},论文说只要问题能写成这个形式就能用最小费用流解。

问题一:如果 bub_u 的含义就是建立超级源汇点,并根据正负和源汇点连边,如果 bub_u 全部都是正/负数,或者 bi=0b_i=0,应该怎么处理?源汇点是什么?

问题二:如果 cuv=+∞c_{uv}=+\infty,wuv<0w_{uv}<0,形成了容量无穷大的负环,怎么处理?

问题三:じょうしょうツリー 这题中,"引入变量 p0=0p_0=0" 这一句话是否矛盾,p0p_0 既是变量又是常量。

问题四:じょうしょうツリー 的具体建图方式是怎么样的?

问题五:min⁡{∑ubupu+∑uvcuvmax⁡(0,pv−pu−wuv)}\min\{\sum_ub_up_u+\sum_{uv}c_{uv}\max(0,p_v-p_u-w_{uv})\} 这个式子里面有没有体现出哪个点是源点哪个是汇点?

能解答任何一个都好,感激不尽。

2024/9/2 19:10
加载中...