《运输问题与指派问题第5讲课教案》由会员分享，可在线阅读，更多相关《运输问题与指派问题第5讲课教案（36页珍藏版）》请在金锄头文库上搜索。
1、OR课件,回 顾,到目前为止，针对规划问题所建立的算法有一个共同的特征：,但是： 在决策的实践中，有些问题约束条件存在一定的特殊性，按常规办法有可能出现严重退化而导致问题无法顺利求解。如：运输问题、指派问题等。,从约束条件入手,OR课件,Transportation ProblemIP 否则，xij=0,变换系数矩阵【例2】,OR课件,匈牙利算法,TP & AP,-1,-2,-3,-2,-2,(0),(0),(0),(0),Z=1+2+5+2=1+2+3+2+2=10,【例1】,OR课件,匈牙利算法,TP & AP,-7,-5,-4,-2,-1,【例2】,(0),(0),(0),-1,-1,1
2、,(0),(0),(0),(0),(0),(0),(0),(0),或：,关键：能覆盖所有0元素的最少直线数？如何画 ？,OR课件,匈牙利算法,TP & AP,Z=20,【例2】,或：,OR课件,匈牙利算法,TP & AP,【例2】,定理：能覆盖所有0元素的最少直线数等于在0元素处作出标号（0）的最多个数。,画法：,在没有（0）的行打号,对打号的行上的所有 有0元素的列打号,再对打号的列上 有（0）的行打号,有新的打号 的行列吗？,Y,N,对没有打号的行 画横线 对所有打号的列 画纵线,OR课件,指派问题,TP & AP,特殊指派问题的求解,目标为MaxZ：,令：Cij =M- Cij ，转化为MinS.,“人多于事”（mn）：,处理：加（m-n）件虚事，Ci虚0,“事多于人”（mn）：,处理：加（n - m ）个虚人，C虚j0,OR课件,本章小结,TP & AP,本章重点介绍了一类特殊线性规划问题（运输问题和指派问题）的模型与求解；,应注意到：,两问题都有最优解；,两算法思想基本相同，均从目标函数系数入手，并且直接求得整数最优解；,思考：两算法的区别？,
