网络优化7最小费用流问题上课讲义.ppt

网络优化定义7.2（容量-费用网络中的流(flow)的定义同前一章）
流x的（总）费用定义为7.1.2最小费用流模型的特例及扩展7.1.2最小费用流模型的特例及扩展设x0为不同于的可行流，但费用低于x的费用，即
N(x)中找负圈可用最短路算法(如Bellman-Ford算法，O(mn))
则该算法的复杂度为O(nm2CU),不是多项式时间算法.略略7.3.1对偶问题及互补松弛条件N(x)=N

7.3.2原始-对偶算法,例7.3.2原始-对偶算法,例布置作业网络优化(Out-Of-KilterAlgorithm)(Out-Of-KilterAlgorithm)-Kilter条件-Kilter图;Kilter数-残量网络-残量网络-步骤-正确性-正确性-正确性-正确性-复杂度分析-算法思想-算法思想-算法思想-算法思想-算法思想松弛算法–步骤（Bertsekas，1980’s)松弛算法–复杂度分析-例布置作业（第2讲）网络优化
引理7.8关联矩阵B的列构成一组基的充要条件是它所对应的弧为支撑树(不考虑方向时).把B1所对应的弧集合(支撑树)用T表示，则：
所有非树弧（非基弧）对应于非基变量,其上的流量为0;
只有T中的弧（树弧，或称基弧）对应于基变量.
给定支撑树后,如何确定树弧上的流量并使之满足可行条件？-势的计算7.6.1算法的一般思路–旋转变换STEP0.获得一个初始的可行树T及对应的基本可行解x略计算测试表明，网络单纯形法中往往90%以上的旋转是退化的.
能否要求每次所操作的可行树“都不相同”？引理7.9如果网络单纯形算法中生成的所有可行树都是强可行树，则这些树互不相同.首先，初始的基本可行解是对应于一棵强可行树；
其次，我们要求旋转变换只生成强可行树. 一般可以采用大-M方法（Big-MMethod）构造初始的强可行树.由于M是一个充分大的正数,因此当算法终止时,有三种情况:基可以用所有弧的一个划分(T,L,U)来表示,其中T是一棵支撑树,L是非树弧中流量等于下界的弧的集合,U是非树弧中流量等于上界的弧的集合.三元组(T,L,U)可以称为基结构(有时也直接简称为基),或支撑树结构.初始的强可行树结构：仍然可以构造人工网络,采用大-M方法.6.5最高标号预流推进算法布置作业Thankyouverymuchforyourattendance!