MBA学位课程-运筹学(二)(ppt 142页)

一、产销平衡的运输问题及其解法
二、产销不平衡的运输问题及其求解方法
三、转运问题及其解法

 

     引例：某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-40吨，A2-40吨，A3-90吨。该公司把这些产品分别运往四个销售点，各销售点每日销量为：B1-30吨，B2-40吨，B3-60吨，B4-20吨, B5-20吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少
（2）用闭回路法或位势法求空格的检验数
1)    用闭回路法求检验数：
     首先，每一个空格有且仅有一个闭回路，而圈格无闭回路。
    闭回路是以空格为起点，沿同一行或同一列前进，遇上圈格可转90度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。
       以始点为第0个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。   
      其次，每一个空格的检验数=奇顶点运费之和 – 偶顶点运费之和。
     2)用位势法求出空格的检验数并进行最优解的判别
设u1,u2,…um; v1,v2,…,vn是对应运输问题m+n个约束条件的对偶变量，B为含有人工变量的初始可行基，由LP问题的对偶理论知：CBB-1=(u1,u2,…um; v1,v2,…,vn)
       而每个决策变量Xij相应的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj，   于是，检验数σij=CBB-1Pij－Cij =(ui+vj)－Cij
又各基变量的检验数为0，故对每个基变量所在的圈格的检验数有                

..............................