运筹学 北京邮电大学.ch3-3.ppt

设平衡运输问题的数学模型为：;表上作业法也称为运输单纯形法，是直接在运价表上求最优解的一种方法，它的步骤是： ;3.3.1初始基可行解;【例3】求表3－6所示的运输问题的初始基可行解。;;【例4】求表3－7给出的运输问题的初始基本可行解。 ;【解】;初始基本可行解可用下列矩阵表示 ;2．运费差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案， ; 基于以上想法，运费差额法求初始基本可行解的步骤是：;【例5】用运费差额法求表3—9运输问题的初始基本可行解。; 销地 产地; 销地 产地; 销地 产地;基本可行解为 ;3.3.2求检验数 求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij由第一章知，求最小值的运输问题的最优判别准则是：;【解】用最小元素法得到下列一组基本可行解;矩阵中打“×”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。;同理可求出其它非基变量的检验数：;2．位势法求检验 位势法求检验数是根据对偶理论推导出来的一种方法。 ;加入松驰变量λij将约束化为等式;【例7】用位势法求例7给出的初始基本可行解的检验数。;再由公式 求出检验数，其中Cij是非基变量对应的运价。;【例8】求下表所示运输方案的检验数。;3.3.3调整运量;【例9】求下表所示的运输问题的最优解。;; ;;;;;;;;作业：P99 T3.3(1)(2) 3.4