1、最小费用流问题最小费用流问题例、例、最小费用流问题最小费用流问题目标：从发点到收点的总的流量费用最小目标：从发点到收点的总的流量费用最小约束：约束：1）容量约束，各边流量不大于容量）容量约束，各边流量不大于容量 2）流量平衡约束，各点进出流量总和相等）流量平衡约束，各点进出流量总和相等 3）从发点到收点的总流量为）从发点到收点的总流量为sv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(括号内第一个数字是容量，第二个是单位流量费用括号内第一个数字是容量，第二个是单位流量费用w最小费用流问题的一般提法最小费用流问题的一般提法CEVG,容量网络容量网络 的
2、每边另外赋值非负的单位的每边另外赋值非负的单位流量费用流量费用 ，记为，记为 ，给，给定从定从 到到 的总流量的总流量 ，要求一个总流量等于，要求一个总流量等于 的可行流的可行流 使得总费用使得总费用达到最小，特别是，如果给定总流量等于最大流，达到最小，特别是，如果给定总流量等于最大流，所求问题称为最小费用最大流问题所求问题称为最小费用最大流问题Evvijijjixd),(wtvsvEvvdjiij),(,DCEVG,ijxX wsv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(1sx21x2sx23x13xtx1tx3下例中可行流下例中可行流 要满
3、足的流量平衡约束要满足的流量平衡约束 0 :2111131xxxxvst0 :221232sxxxv0 :231333xxxvt中间节点：中间节点：wxxvsss0 :21wxxvttt310 :发点：发点：收点：收点：ijxX 定义定义 ：从：从 发出的所有边的终节点指标集合发出的所有边的终节点指标集合 :进入进入 的所有边的始节点的指标集合的所有边的始节点的指标集合如下图：如下图：iViviVivsv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(1sx21x2sx23x13xtx1tx3 3,1,2,1,;,3,12,3;,2,1332211tt
4、ssVVVtVsVVsVtVVV 0 :2111131xxxxvst0 :221232sxxxv0 :231333xxxvtwxxvsss0 :21wxxvttt310 :再用再用 表示表示 的净发出流量，即的净发出流量，即3,2,10ixxiiVjjiVjijwxxssVjjiVjijwxxttVjjiVjij3,2,1,0iwwwwwitsiwiv流量平衡约束可统一写成流量平衡约束可统一写成iwxxiVjjiVjijii,网络网络 的最小费用流问题的最小费用流问题EvvcxVvwxxxdjiijijiiVjjiVjijEvvijijiiji),(,0,s.t.min),(DCEVG,是一种
5、特殊的线性规划问题是一种特殊的线性规划问题最小费用流问题的对偶目标函数最小费用流问题的对偶目标函数EvvcxVvwxxxdjiijijiiVjjiVjijEvvijijiiji),(,0,s.t.min),(VviVjjiVjijiEvvijijiiijiwxxzxdZXL),(),(对偶目标函数对偶目标函数),(min)(0ZXLZCX其中其中 是是 的分量，的分量，表示容量约束表示容量约束izZCX 0VviiEvvijijijVviVjjiVjijiEvvijijijiiiijiwzxzzdwxxzxdZXL),(),(),(VviiEvvijijijcxVviiEvvijijijCXC
6、XijiijijijiwzxzzdwzxzzdZXLZ),(0),(00minmin),(min)(0()min,(,)ijijijjiijijjiijijxcdzzx Zdzzxv vE0)(0)(000)(ijijijijijijijijijijijzzdcZxzzdcZxzzdZx()()ijX Zx Z(,)()(),()()()ijiiiijijiijjiiv vEv Vj Vj VZL X Z Zd x Zzx ZxZw最小费用流问题的最小费用流问题的松弛条件松弛条件00000ijijijijijijijijijijijzzdcxzzdcxzzdx),()(ZXLZ 和和 满足松弛
7、条件满足松弛条件 ijXxZ满足容量约束满足容量约束X最小费用流问题的松弛定理最小费用流问题的松弛定理：则则 是原问题最优解，是原问题最优解，是对偶问题最优解是对偶问题最优解如果可行流如果可行流 和对偶变量和对偶变量 满足松弛条件满足松弛条件XZXZ由弱对偶定理可知结论成立由弱对偶定理可知结论成立证明：证明：满足松弛条件满足松弛条件),()(ZXLZ 可行流可行流(,)(,),ijiiiijijijiijjiiv vEv Vj Vj Vijijv vEL X Zd xzxxwd x利用松弛定理解决最小费用流问题的途径利用松弛定理解决最小费用流问题的途径1）产生一对满足松弛条件和所有中间节点的流
8、）产生一对满足松弛条件和所有中间节点的流 量平衡条件的量平衡条件的 ，的总流量不大于的总流量不大于 ，例如，例如，),(ZX2）如果）如果 也满足收点和发点的流量平衡条也满足收点和发点的流量平衡条 件（总流量为件（总流量为 ），），已是原问题的最优解已是原问题的最优解X3）如果）如果 不满足发点和收点的平衡条件，不满足发点和收点的平衡条件，那么在满足那么在满足 1）的条件的前提下改进）的条件的前提下改进 ，使，使 其流量增加其流量增加),(ZXX),(ZXVvzEvvxiijiij,0,),(,0Xww如何完成如何完成 3）的任务？）的任务？如何增加流量？如何增加流量？已知条件：已知条件：X（
9、满足所有中间节点的流量平衡条件和容量约束）（满足所有中间节点的流量平衡条件和容量约束）是最大流的充要条件（增广链定理）：是最大流的充要条件（增广链定理）：不存在关于不存在关于 的可增广链的可增广链可以采用的方法：可以采用的方法：是最大流问题的一个可行流是最大流问题的一个可行流寻找关于寻找关于 的可增广链，如果找不到，的可增广链，如果找不到，已已经是最大流，原问题不可行，否则增加流量经是最大流，原问题不可行，否则增加流量XXXX如果沿该增广链如果沿该增广链 增加流量增加流量 ，由容量约束知，由容量约束知ijvvijijvvxxcjiji),(),(min,minmin由于增加后的总流量为由于增加
10、后的总流量为 ，应满足，应满足 所以最终选用的流量增加值应该为所以最终选用的流量增加值应该为WwWijvvijijvvxxcWwWwjiji),(),(min,min,min,min假设假设 是从是从 到到 关于关于 的可增广链，用的可增广链，用表示其前向边的集合，表示其前向边的集合，表示后向边的集合，用表示后向边的集合，用 表示当前的总流量表示当前的总流量svtvXW流量调整前后原目标函数的改变为流量调整前后原目标函数的改变为 是沿是沿 增加单位流量的费用，称为增加单位流量的费用，称为 的费用，显然的费用，显然应该选择费用最小的可增广链增加总流量应该选择费用最小的可增广链增加总流量Evvxx
11、vvxxvvxxjiijijjiijijjiijij),(,),(,),(,),(),(),(),(jijijijivvijvvijEvvijijEvvijijddxdxd),(),()(jijivvijvvijddd记记沿沿 对对 进行调整获得新的流量进行调整获得新的流量 ，则，则 ijxX X d根据前面的讨论可形成下面的最小费用流算法：根据前面的讨论可形成下面的最小费用流算法：1）令）令 2）如果）如果 ，停止，否则求出费用，停止，否则求出费用 最小最小 的可增广链的可增广链 （如果没有可增广链，停止）（如果没有可增广链，停止）3）令）令 4）用）用 替换替换 ，替换替换 ，回到，回到
12、2）0,),(,0,WEvvxxXjiijijwW dijvvijijvvxxcWwjiji),(),(min,min,minEvvxxvvxxvvxxjiijijjiijijjiijij),(,),(,),(,WWXX对前面的最小费用流算法要解决的问题对前面的最小费用流算法要解决的问题 d1）实现问题）实现问题 如何方便地求出费用如何方便地求出费用 最小的可增广链最小的可增广链？2）理论问题）理论问题 算法停止于算法停止于 时所产生的时所产生的 是否是最是否是最 小费用流问题的解？小费用流问题的解？wW Xsvivjvijd对第一个问题的解决方法对第一个问题的解决方法情况情况1）如果）如果
13、出现在某个可增广链出现在某个可增广链 中，中，一定属于该链的前向边，此时如果把一定属于该链的前向边，此时如果把 转换转换 成从成从 到到 的下述道路的下述道路 tvEvvji),(任取任取 ，其，其 只会是以下三种情况之一只会是以下三种情况之一ijx1），2），3）0ijxijijcx ijijcx 0),(jivv)(d那么那么 构成路长的一部分，就象构成路长的一部分，就象 构成构成 的一部分一样的一部分一样svtvijdijdsvivjvijd情况情况2）如果）如果 出现在某个可增广链出现在某个可增广链 中，中，一定属于该链的后向边，此时如果把一定属于该链的后向边，此时如果把 转换转换 成
14、从成从 到到 的下述道路的下述道路 tv),(jivv)(d那么那么 构成路长的一部分，就象构成路长的一部分，就象 构成构成 的一部分一样的一部分一样svtvijdijd情况情况3）此时既可能属于前向边，也可能属于后向）此时既可能属于前向边，也可能属于后向 边，所以上述两种可能的等价转化方式都应边，所以上述两种可能的等价转化方式都应 该保留该保留总结前面讨论，可以把容量网络的每条边按以下规总结前面讨论，可以把容量网络的每条边按以下规则等价转换成长度网络（求最短路的网络）中的边则等价转换成长度网络（求最短路的网络）中的边ivjvijxijijdc,如果如果0ijxijijcx 0ivjvijdi
15、vjvijxijijdc,如果如果ijijcx ivjvijdivjvijxijijdc,如果如果ivjvijdijd然后求长度网络的最短路确定最小费用可增广链然后求长度网络的最短路确定最小费用可增广链sv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(2550070例例长度网络长度网络sv2v3vtv1v421361241由于有小于零的权值，要用值迭代法求最短路由于有小于零的权值，要用值迭代法求最短路对长度网络的改进对长度网络的改进),(),()(jijivvijvvijrrd简化成本简化成本svtvX),(),(),(),()()()()()()(
16、jijijijivvijvvijvvijijvvijijzzzzdzzdzzddijijijzzdr定义定义从从 到到 关于关于 的可增广链的可增广链 的长度的长度ivjvkvizkz()()ijjkkizzzzzzjv增广链上任意中间节点增广链上任意中间节点 的三种可能情况的三种可能情况jzivjvkvizkz()()jijkkizzzzzzjzivjvkvizkz()()jikjkizzzzzzjz()()tsddzz(,)(,)()()ijijjijitsv vv vzzzzzzmin()min()dd可以用可以用 代替代替 生成计算最小费用的可增广链生成计算最小费用的可增广链ijdij
17、r用用 代替代替 计算最小费用的可增广链的计算最小费用的可增广链的好处好处ijdijr00000ijijijijijijijijijijijijijijzzdrcxzzdrcxzzdrx 和和 满足松弛条件满足松弛条件000ijijijijijxcrxr最短路网络无负数，可用最短路网络无负数，可用Dijkstra算法算法XZ00ijijijxcrivjv0ijxijijcx 0ivjv0ijr ivjvijijcx ivjv0ijrivjvivjv00对第二个问题的回答对第二个问题的回答那么存在对偶变量那么存在对偶变量 和和 一起满足松弛条件一起满足松弛条件ZXsvtvX定理定理 如果下述条件
18、满足：如果下述条件满足：X1）满足所有中间节点的流量平衡条件满足所有中间节点的流量平衡条件2）存在对偶变量）存在对偶变量 和和 一起满足松弛条件一起满足松弛条件3）是从是从 到到 关于关于 的最小费用可增广链的最小费用可增广链4）沿）沿 对对 按前面的算法调整获得按前面的算法调整获得XX一旦证明了上述定理，马上可以说明前面的最小费用流一旦证明了上述定理，马上可以说明前面的最小费用流算法或者能够证明没有可行解，或者能够给出最优解算法或者能够证明没有可行解，或者能够给出最优解ZX对用对用 生成的长度网络的每个生成的长度网络的每个 ，用，用 表示从表示从 到到 的最短路，如果从的最短路，如果从 到到
19、 没有道路，令没有道路，令 ，用用 表示最小费用增广链及其前向和后向边，表示最小费用增广链及其前向和后向边，由最小费用增广链的定义可知由最小费用增广链的定义可知Vvi定义定义 如下如下svividVvzZii,下面说明，这样定义的下面说明，这样定义的 和和 一起满足松弛条件，一起满足松弛条件，从而完成对前面定理的证明从而完成对前面定理的证明XZid sviv,tddijrVvddzziiii,)(,0max首先可以看出（反证）首先可以看出（反证）000ijjiijijijjiijdzzxcdzzx00000ijijijijijijijijijijijzzdcxzzdcxzzdx所以，如果能够证
20、明上面条件成立，就可完成证明所以，如果能够证明上面条件成立，就可完成证明首先考虑首先考虑 的情况，又要分别考虑两种情形的情况，又要分别考虑两种情形1）ijijcx ijijcx svjviv0ijrtv(,)ijv vijijxxijjijirdddddd),(,)(ijijjiijjijijijidrzzddzzddddzzzz)()(,0max)(,0max0ijjidzzidjd2）ijijcx（不一定在增广链上）（不一定在增广链上）0ijrsvjvivtvijijrddjdidijjijjijijjirddrddrrdddd)(,0max)(,max)(,0max)(,0maxijij
21、jijijijidrzzddddzzzz)(,0max)(,0max0ijijzzd对对 的情况可类似证明的情况可类似证明0ijx利用对偶变量的最小费用流求解算法利用对偶变量的最小费用流求解算法1）令）令2）如果）如果 ，停止，停止3）令）令 ，构造长度网络，构造长度网络4）求出从）求出从 到每个到每个 的最短路长的最短路长 ，如果到，如果到 某个某个 没有最短路，令没有最短路，令5）如果）如果 ，停止（没有可增广链），停止（没有可增广链）6）利用从）利用从 到到 的最短路和所有的的最短路和所有的 修改原修改原 变量和对偶变量，并用修改后的数值替换原变量和对偶变量，并用修改后的数值替换原 来的
22、数值，同时修改总流量，然后回到来的数值，同时修改总流量，然后回到 2）0,0,),(,0WVvzEvvxiijiijwW idididsvtvEvvzzdrjiijijij),(,svivivtd例例 求总流量为求总流量为10的的 最小费用流最小费用流sv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(令令 ，长度网络为，长度网络为jidrzxijijiij,0,0sv2v3v4tv11v13226)0(sv)1(2v)4(3v4)4(tv1)3(1v13226求得增广链（红线）和所有的求得增广链（红线）和所有的 （括号内的数）（括号内的数）ididd
23、zzitii,0max求出求出 （）izi,00,3,1,0,4321zzzzzts利用可增广链调整流量利用可增广链调整流量sv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(5053132311212Wxxxxxxxtsts第一次迭代后的信息均在下图中，其中顶点后的数第一次迭代后的信息均在下图中，其中顶点后的数是对偶变量值，容量和费用对下面的数据对是流量是对偶变量值，容量和费用对下面的数据对是流量简化成本简化成本ijijijijijcxrxr0,00ijijijzzdr可验证松弛条件可验证松弛条件4sv32v03v 1,00tv)1,7(1 1v)1
24、,8()3,10()2,5()2,4()6,2()4,10(0,50,00,55,00,52,0利用上图构造长度网络图利用上图构造长度网络图4sv32v03v 1,00tv)1,7(1 1v)1,8()3,10()2,5()2,4()6,2()4,10(0,50,00,55,00,52,0sv2v3v1tv1v00250000求得增广链（红线）和所有的求得增广链（红线）和所有的 id)0(sv)0(2v)0(3v1)1(tv)1(1v00250000iddzzitii,0max利用利用0,3,1,0,4321zzzzzts1,4,1,0,5321zzzzzts求出求出4sv32v03v 1,0
25、0tv)1,7(1 1v)1,8()3,10()2,5()2,4()6,2()4,10(0,50,00,55,00,52,0利用可增广链调整流量利用可增广链调整流量707,5,5,232312121Wxxxxxxttss5sv42v 1 3v0,20tv)1,7(1 1v)1,8()3,10()2,5()2,4()6,2()4,10(0,50,0 1,56,00,7 1,0第二次迭代后的信息第二次迭代后的信息ijijijijijcxrxr0,00可验证松弛条件可验证松弛条件利用上图构造长度网络利用上图构造长度网络5sv42v 1 3v0,20tv)1,7(1 1v)1,8()3,10()2,5
26、()2,4()6,2()4,10(0,50,0 1,56,00,7 1,0sv2v3v0tv1v00160100求得增广链（红线）和所有的求得增广链（红线）和所有的 ididdzzitii,0max利用利用2,5,2,0,6321zzzzzts求出求出)0(sv)0(2v)0(3v0)1(tv)0(1v001601001,4,1,0,5321zzzzzts利用可增广链调整流量利用可增广链调整流量103,37,5,8,232312121Wxxxxxxttss6sv52v23v0,20tv)1,7(21v)1,8()3,10()2,5()2,4()6,2()4,10(0,50,0 1,56,00,
27、7 1,0第三次迭代后的信息第三次迭代后的信息ijijijijijcxrxr0,00可验证松弛条件可验证松弛条件6sv52v23v0,20tv)1,7(21v)1,8()3,10()2,5()2,4()6,2()4,10(0,80,3 1,56,0 1,70,3由于总流量等于由于总流量等于10已经满足约束，所以是最优解已经满足约束，所以是最优解运输问题运输问题运输表描述运输表描述产地产地销地销地产量产量销量销量1AmA2AnB1B2B2ama1anb2b1b21c12x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx运输问题的图描述运输问题的图描
28、述1B2BnB1A2AmA产地产地销地销地1a2ama产量产量1b2bnb销量销量1mc2mcmnc11c12c1nc11mnijijijc x在流量平衡和非负约束下极小化总的运输费用在流量平衡和非负约束下极小化总的运输费用产销平衡运输问题的数学规划模型（线性规划问题）产销平衡运输问题的数学规划模型（线性规划问题）1111mins.t.,1,10,1,1mnijijijnijijmijjiijc xxaimxbjnximjn 产销平衡假定：产销平衡假定：Qbanjjmii11jiQbaxjiij,有可行解有可行解1111,nniijjijjmmjijijiiaxbaiQbxabjQ11,1;,
29、11nmijiijjjixaimxbjn 11111111111111111mmnnmnmninijijijijiijjijijmnmnniijjjnijijjxxxxxaxbbb 最后一个约束多余，等式约束可写成最后一个约束多余，等式约束可写成共有共有 个等式约束个等式约束1nm11,1;,11nmijiijjjixaimxbjn 11111mnmijijijnaaP xbb注意：注意：i其中其中100 1 00 1 00Tm nijPR jm列向量表示模型列向量表示模型1111mins.t.,1,110,1,11mnijijijnijijmijjiijc xxaimxbjnximjn 10
30、0 1 00Tm ninPR i例例产地产地销地销地产量产量销量销量1A3A2A4B1B2B10221648148221x1022x411x831x1212x532x1114x924x634x3B12413x323x1133x14图表示图表示1B2B4B1A2A3A16102214812143B412114210938561111x12x14x13x21x22x24x23x31x32x34x33x产生基本可行解产生基本可行解1B2B4B1A2A3A00000003B111x 141x 211x 241x如果一组变量（红线表示）形成回路如果一组变量（红线表示）形成回路11 11212114 14
31、24240P xP xP xP x在在 中令其他变量等于中令其他变量等于0110mnijijijP x1B2B4B1A2A3A00000003B11x21x24x如果一组变量（红线表示）不含回路如果一组变量（红线表示）不含回路242111000 xxx在在 中令其他变量等于中令其他变量等于0110mnijijijP x上述第一种情况的运输表上述第一种情况的运输表产地产地销地销地产量产量销量销量1A3A2A4B1B2B0000002211x 104111x 812511141x 9241x63B04311011 11212114 1424240P xP xP xP x上述第二种情况的运输表上述第
32、二种情况的运输表产地产地销地销地产量产量销量销量1A3A2A4B1B2B000000221x10411x812511924x63B043110242111000 xxx11 11212124240P xP xP x结论：运输问题一组变量的系数线性无关的充要条件是结论：运输问题一组变量的系数线性无关的充要条件是在图或表中不含有回路在图或表中不含有回路1B2B4B1A2A3A00000003B11x21x24x基本可行解的个数基本可行解的个数1nm用用最小元素法最小元素法产生基本可行解产生基本可行解基本思想：优先安排单位运输成本最小的运输方式基本思想：优先安排单位运输成本最小的运输方式产地产地销地
33、销地产量产量销量销量1A3A2A4B1B2B21022164814828104812511963B12431114产地产地销地销地产量产量销量销量1A3A2A4B1B2B222164814828104812511963B10124311142产地产地销地销地产量产量销量销量1A3A2A4B1B2B2226164814828104812511963B10431114210产地产地销地销地产量产量销量销量1A3A2A4B1B2B282264814828104812511963B1043111421014产地产地销地销地产量产量销量销量1A3A2A4B1B2B28648148281048125119
34、63B104311614210148产地产地销地销地产量产量销量销量1A3A2A4B1B2B2864814828104812511963B10431162101486最后删除两个约束最后删除两个约束1nm不会形成回路不会形成回路每次删除一个约束（节点）每次删除一个约束（节点）变量变量产生基本可行解等价于在运输图中生成一个支撑树产生基本可行解等价于在运输图中生成一个支撑树1B2B4B1A2A3A16102214812143B由流量平衡方程依次可得对应的可行流由流量平衡方程依次可得对应的可行流21231314343282106814xxxxxx计算检验数计算检验数回忆检验数计算公式回忆检验数计算公
35、式1,TijijBijcC B Pi j1TTBYC BTTBCY B令令 （对偶变量）（对偶变量）TTBCY B,TijijijcY Pi j11,1,11nijijmijjixaimxbjn ,1,11ijuimvjn 111mnuuYvv111,0ijmnijijcuu vvPx13142123323410,6,8,2,14,8xxxxxx13131313100001cuu vvuv 1413131100000cuu vvu 212123233232343cuvcuvcuvcu1142323223312123343133ucvcuucvvcuucvcu产地产地销地销地产量产量位势行位势行
36、1A3A2A4B1B2B24482104812511963B4311位势列位势列销量销量1481241488810111u622u63u1v2v3v0利用运输表解对偶变量（利用运输表解对偶变量（位势法位势法）产地产地销地销地产量产量位势行位势行1A3A2A4B1B2B24482104812511963B4311位势列位势列销量销量1481241488810111u622u63u1v12v73v0产地产地销地销地产量产量位势行位势行1A3A2A4B1B2B24482104812511963B4311位势列位势列销量销量1481241488810111u62102u63u81v12v73v0产地产
37、地销地销地产量产量位势行位势行1A3A2A4B1B2B210412511963B4311位势列位势列销量销量8111u利用对偶变量计算检验数利用对偶变量计算检验数102u63u81v12v73v40v 123123,ijijijijijcu u u v v vPcuv121110122448814812414881062（视（视 ）40v 改进基本可行解改进基本可行解产地产地销地销地产量产量销量销量1A3A2A4B1B2B83B2101486102216481481214已知以下基本可行解和负的检验数已知以下基本可行解和负的检验数241 让让 进基（取值大于零）可改进基本可行解进基（取值大于零
38、）可改进基本可行解24x由于基本可行解形成一个支撑树，加入任何非基变量一由于基本可行解形成一个支撑树，加入任何非基变量一定和某些基变量形成回路定和某些基变量形成回路1B2B4B1A2A3A16102214812143B加入加入 形成回路形成回路24x13241,A BA BA产地产地销地销地产量产量销量销量1A3A2A4B1B2B83B242x2410 x148246x10221648148121424x在在 和基变量形成的回路中，让基变量依次减少和基变量形成的回路中，让基变量依次减少或增加或增加 的增加值，可保持等式约束满足的增加值，可保持等式约束满足24x24x产地产地销地销地产量产量销量
39、销量1A3A2A4B1B2B83B1214841022164814812142取取 ，可得下面新的基本可行解，可得下面新的基本可行解24131423min,2xxxx 出基，目标函数等于原目标值加上出基，目标函数等于原目标值加上24242x 242x2410 x246x24x023x算法总结算法总结1）用最小元素法确定一个基本可行解）用最小元素法确定一个基本可行解2）用位势法计算所有非基变量的检验数）用位势法计算所有非基变量的检验数3）如果所有检验数不小于零，已得最优解，）如果所有检验数不小于零，已得最优解，否则找出最小检验数对应的非基变量以及否则找出最小检验数对应的非基变量以及 与其形成回路
40、的基变量，据此确定相应非与其形成回路的基变量，据此确定相应非 基变量的增加值以及回路基变量的新值，基变量的增加值以及回路基变量的新值，然后回到上一步继续迭代然后回到上一步继续迭代总产量大于总销量（产销不平衡）的运输问题总产量大于总销量（产销不平衡）的运输问题njmixnjbxmiaxxcijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,s.t.min1111njjmiiba11优化模型优化模型处理办法处理办法引入假想销地引入假想销地1nB1,2,1,2,1,01,2,1,2,1,s.t.min111111njmixnjbxmiaxxcijjmiijinjijminj
41、ijijnjjmiinbab111优化模型优化模型往假想销地的运量没有成本往假想销地的运量没有成本定义假想销地定义假想销地 的销量的销量1nBmicni,2,1,01指派问题指派问题例例 开办五家新商店，要五家建筑公司分别承建，各公开办五家新商店，要五家建筑公司分别承建，各公 司营造费用报价如下，如何指派使总造价最小司营造费用报价如下，如何指派使总造价最小商店商店1A46766费用报价费用报价公司公司879997141712125A2A4A3A1B5B2B4B3B1561410812101067标准指派问题的一般提法标准指派问题的一般提法有有 件事要件事要 个人完成个人完成，每人做一件事，每人
42、做一件事，已知第已知第 个人做第个人做第 件事的成本是件事的成本是 ，要确定人和事之间一对一的指派方案，使要确定人和事之间一对一的指派方案，使完成这完成这 件事的总费用最小件事的总费用最小nnijijcn称称 为指派问题的系数矩阵为指派问题的系数矩阵 nnijcC件件事事个个人人做做第第若若不不指指派派第第件件事事个个人人做做第第若若指指派派第第jijixij01定义定义整数规划模型整数规划模型jixnjxnixxcijniijnjijninjijij,1,0,2,1,1,2,1,1s.t.min1111产地产地销地销地产量产量销量销量1AmA2AnB1B2B11111121c12x22c22
43、x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx标准指派问题是一个特殊的产销平衡运输问题标准指派问题是一个特殊的产销平衡运输问题当且仅当一组变量不含回路时，其对应的系数矩阵当且仅当一组变量不含回路时，其对应的系数矩阵的列向量线性无关的列向量线性无关推论推论一组线性无关的系数向量对应的变量中，至少有一一组线性无关的系数向量对应的变量中，至少有一个变量所在行或列没有其它基变量个变量所在行或列没有其它基变量在运输问题的讨论中已得出下面的结论在运输问题的讨论中已得出下面的结论推论推论运输问题的基变量取值一定等于产量或销量或它们运输问题的基变量取值一定等于产量或销量
44、或它们的差或它们的差的差的差或它们的差的差产地产地销地销地产量产量销量销量1A3A2A4B1B2B83B210148610221648148121423x21x32x13x14x34x例例推论推论 产量和销量都是非负整数的运输问题的基本可行产量和销量都是非负整数的运输问题的基本可行 解的每个分量一定是非负整数解的每个分量一定是非负整数推论推论 下述运输问题的基本可行解满足下述运输问题的基本可行解满足0-1约束！约束！产地产地销地销地产量产量销量销量1AmA2AnB1B2B11111121c12x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx结论
45、结论不用考虑不用考虑0-1变量约束！变量约束！求解下述运输问题可得标准指派问题的解求解下述运输问题可得标准指派问题的解jixnjxnixxcijniijnjijninjijij,0,2,1,1,2,1,1s.t.min1111尽管可以用求解运输问题的算法求解标准指派尽管可以用求解运输问题的算法求解标准指派问题，由于存在大量的退化解，经常出现换基问题，由于存在大量的退化解，经常出现换基不能改进目标函数的情况，这种做法效率不高不能改进目标函数的情况，这种做法效率不高进一步挖掘标准指派问题的特点可以获得更加进一步挖掘标准指派问题的特点可以获得更加有效的算法，这就是所谓的有效的算法，这就是所谓的匈牙利
46、算法匈牙利算法标准指派问题的第一个有用的性质标准指派问题的第一个有用的性质任取任取 和任意实数和任意实数 ，用，用 和和 分别分别表示将表示将 的第的第 行或第行或第 列减去列减去 以后得到以后得到的系数矩阵，则以的系数矩阵，则以 ，或或 为系数矩阵的指为系数矩阵的指派问题的最优方案相同派问题的最优方案相同nk 1理由：理由：A1C2CC1C2CCkkAAxcxAcxcninjijijnjkjkjnkiinjijij11111AxcxAcxcninjijijniikikninkjjijij11111目标函数差一个常数，约束相同，最优解也相同目标函数差一个常数，约束相同，最优解也相同标准指派问题
47、的第二个有用的性质标准指派问题的第二个有用的性质如果如果 的所有元素中没有负数，且存在的所有元素中没有负数，且存在 个行列号都互不相同的零元素（简称为独立零元个行列号都互不相同的零元素（简称为独立零元素），那么对应的标准指派问题的最优目标值等素），那么对应的标准指派问题的最优目标值等于零，最优方案可以由独立零元素的位置确定于零，最优方案可以由独立零元素的位置确定04321405010121026600811031C例如例如最优解最优解15544312213xxxxxnnnRC算法设想（匈牙利算法）算法设想（匈牙利算法）一、利用第一个性质产生独立零元素一、利用第一个性质产生独立零元素二、对给定矩
48、阵找到最大的独立零元素组二、对给定矩阵找到最大的独立零元素组三、当最大的独立零元素组的零元素数目不够三、当最大的独立零元素组的零元素数目不够 时增加独立零元素的数目时增加独立零元素的数目通过以上步骤的迭代找到足够的独立零元素通过以上步骤的迭代找到足够的独立零元素61012961061476781296101417971215784C例例一、顺序对每行每列减去最小值产生零元素一、顺序对每行每列减去最小值产生零元素C043204050012320377108110300463040810126303710208113401）用红圈标出一些某行或某列仅有的零元素，再用红圈标出一些某行或某列仅有的零元
49、素，再通过行列交换把这些零换到左上角（后者非必须）通过行列交换把这些零换到左上角（后者非必须）行交换行交换04320405001232037710811030二、对给定矩阵找到最大数目的独立零元素组二、对给定矩阵找到最大数目的独立零元素组2012310377200430040530811020043004052012310377308110列交换列交换201231037720043004053081102）在没有红圈的右下角如果有在没有红圈的右下角如果有零，一定是新的独立零元素零，一定是新的独立零元素3）用直线覆盖红圈所在行用直线覆盖红圈所在行2012310377200430040530811
50、04）在直线未覆盖处找零，如果没有零停止，否则在直线未覆盖处找零，如果没有零停止，否则会出现以下两种情况，其中黑实圈圈住的是新零会出现以下两种情况，其中黑实圈圈住的是新零2012300377200430040530811020123103772004300405308110情况二情况二情况一情况一20123003772004300405308110201231037720043004053081102012300377200430040530811020123103772004300405308110两种情况的处理方法两种情况的处理方法10210403211180310450162600102
