MBA学位课程运筹学.pptxVIP

§2.6 运输问题及其解法;解：这是一个产销平衡的运输问题， 设Xij表示从Ai调运产品到Bj的数量（吨），其数学模型是： ;一、产销平衡的运输问题及其解法;（2） （产销平衡条件） ;例18（P37）设某产品从产地A1，A2，A3运往销地B1，B2，B3，B4，B5，运量和单位运价如下表所示，问如何调运才能使总的运费最少？; 销地 运价 产地;（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，故对每个基变量所在的圈格的检验数有 ; 显然上述方程有解，且由于含有一个自由变量，因此，令任一未知数为0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。 如用位势法求引例初始基可行解的检验数：; 第一步：将运价表中增加vj和ui列。 第二步：利用圈格分别算出ui和vj，即 令u1=0，然后按ui+vj=Cij (i,j?JB)，相继确定ui，vj的值。 第三步：按σij= (ui+vj)－Cij (i,j?JN)算出表中各空格（即非基变量）的检验数： 由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的非基变量的检验数：σij=CBB-1Pij－Cij≤0 因为σ25 =+4， σ32 =+1， σ34 =+2均为正数，所以目前尚未得到最优解（其实只要有一个正检验数，所对应的方案就不是最优方案），尚须改进。; 3）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案） i) 确定进基变量：自上而下，自左向右第一个正检验数相应的非基变量（空格）为进基变量。 ii) 作闭回路：以进基变量空格为出发点，用水平或垂直线向前划，当碰到某一恰当数格转90?后，继续前进，直至回到起始空格止。 iii) 确定调整量?=min{奇顶点的调运量}（即闭回路上奇顶点运量的最小值为调整量） iv) 在闭回路上进行调整：对闭回路上每个奇顶点的调运量－?，对闭回路上每个偶顶点（含起始格）的调运量+?。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解); 销地 运价 产地;4）表上作业法须注意的问题： i) 在最终调运表中，若有某个空格（非基变量）的检验数为0时，则表明该运输问题有多重调运方案； ii) 在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列（绝对不能同时把行、列划去，否则就不满足圈格=m+n－1个的要求，即基变量的个数永远要保持为m+n－1个）； iii) 在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n－1个的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。;二、产销不平衡的运输问题及其求解方法;然后再用产销平衡的运输问题的解法进行解之。 ;例题19（P45） 三个电视机厂供应四个地区某种型号的电视机，其运价表如下，试求总运费最少的调运方案？; 销地 厂家;三、转运问题及其解法;3.求解“转运问题”的方法步骤： (1)建立扩大的产销平衡运输问题单位运价表。其中 1)对两地不能直接运输的单位运价定为M（很大的正数） ;例26（P61）已知甲、乙两处分别有100吨和85吨同种物质外运，A、B、C三处各需物质55