MBA学位课程-运筹学2(1).ppt

《MBA学位课程-运筹学2(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§2.6运输问题及其解法1-40吨，A2-40吨，A31-30吨，B2-40吨，B3-60吨，B4-20吨,B5-20吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少销地产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）30406020201解：这是一个产销平衡的运输问题，设Xij表示从Ai调运产品到Bj的数量（吨），其数学模型是：2一、产销平衡的运输问题及其解法1.产销平衡的运输问题的数学模型及其特点：特点：

2、（1）其系数矩阵的结构疏松，且每一列向量Pij=(0,…1,…1,…0)T=ei+em+j可以证明，r(A)=m+n－1。即有m+n－1个独立方程。于是，该LP问题有且仅有m+n－1个基变量。3（2）（产销平衡条件）（3）因为,故必有可行解和最优解。由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用特殊解法──表上作业法。2.表上作业法表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其计算步骤和方法，我们通过对引例的求解过程说明之。（1）用最小元素法确定初始方案（即初始基可行解）切记在产销平衡表上必须且只能填

3、写m+n－1个数字格4例18（P37）设某产品从产地A1，A2，A3运往销地B1，B2，B3，B4，B5，运量和单位运价如下表所示，问如何调运才能使总的运费最少？销地运价产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020解：用最小元素法或伏格尔法求得其初始调运方案如下：5销地运价产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020304060202000接下来我们就要判别这个调运方案是否是

4、最优调运方案？判别的方法同线性规划一样，首先求出空格的检验数，由于是最小化问题，所以当所有空格的检验数均小于0时得到的解为最优解。求运输问题的空格的检验数的方法有闭回路法和位势法。6（2）用闭回路法或位势法求空格的检验数1)用闭回路法求检验数：首先，每一个空格有且仅有一个闭回路，而圈格无闭回路。闭回路是以空格为起点，沿同一行或同一列前进，遇上圈格可转90度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。以始点为第0个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。其次，每一个空格的检验数=奇顶点运费

5、之和–偶顶点运费之和。72)用位势法求出空格的检验数并进行最优解的判别设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，故对每个基变量所在的圈格的检验数有即有方程组：共m+n个未知数s=m+n－1个方程8显然上述方程有

6、解，且由于含有一个自由变量，因此，令任一未知数为0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。如用位势法求引例初始基可行解的检验数：销地运价产地B1B2B3B4B5vjA17108646A259712612A336581110ui-7-3-50-2-8-7-70412-33040602020009第一步：将运价表中增加vj和ui列。第二步：利用圈格分别算出ui和vj，即令u1=0，然后按ui+vj=Cij(i,jJB)，相继确定ui，vj的值。第三步：按σij=(ui+vj)－Cij(i,

7、jJN)算出表中各空格（即非基变量）的检验数：由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的非基变量的检验数：σij=CBB-1Pij－Cij≤0因为σ25=+4，σ32=+1，σ34=+2均为正数，所以目前尚未得到最优解（其实只要有一个正检验数，所对应的方案就不是最优方案），尚须改进。方案的调整（即换基迭代）是在闭回路上进行103）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案）i)确定进基变量：自上而下，自左向右第一个正检验数相应的非基变量（空格）为进基变量。ii)作闭回路：以进基变量空格为出发点，用水

8、平或垂直线向前划，当碰到某一恰当数格转90后，继续前进，直至回到起始空格止。iii)确定调整量=min{奇顶点的调运量}（即闭回路上奇顶点运量的最小值为调整量）iv)在闭回路