通信网络理论基础-对偶与整数规划-2010-FINAL-Yu.pptx

通信网络理论基础;对偶与整数规划;拉格朗日乘子法;LP标准型的对偶(1/2);LP标准型的对偶(2/2);关于对偶的第一个印象;例子：一般的LP(1/4);例子：一般的LP(2/4);例子：一般的LP(3/4);例子：一般的LP(4/4);关于对偶的第二个印象;另一个例子(1/4);另一个例子(2/4);另一个例子(3/4);另一个例子(4/4);关于对偶的第三个印象;弱对偶定理;两个推论;强对偶定理(1/2);强对偶定理(2/2);关于对偶的第四个印象;互补松弛定理(1/2);互补松弛定理(2/2);关于对偶的第五个印象;对偶与整数规划;最短路的对偶(1/2);最短路的对偶(2/2);绳球模型;Bellman-Ford算法;对偶的用途：设计新算法;最大流的对偶(1/3);最大流的对偶(2/3);最大流的对偶(3/3);对偶的用途：发现新关系;最佳路由的对偶(1/4);最佳路由的对偶(2/4);最佳路由的对偶(3/4);最佳路由的对偶(4/4);最佳路由=最短路！;权重设置;对偶的用途：Insight;对偶与整数规划;基本思路;换基方法;???1(1/2);例1(2/2);对偶单纯形法的应用;场景1：b?b’;场景1的第一个例子;场景1的第二个例子(1/2);场景1的第二个例子(2/2);场景2：增加不等式约束(1/2);场景2：增加不等式约束(2/2);场景2的第一个例子;场景2的第二个例子;变量的上下界;具有上下界的单纯形法;对偶与整数规划;整数规划的类型;求解方法：分支定界法;要点1：松弛;要点2：分支;要点3：下界;要点4：上界;要点5：剪枝;上界 vs. 下界;分支定界法的基本步骤;课堂练习;课堂练习;对偶与整数规划;小结;End of Part 09