3-2运输问题表上作业法讲解.ppt

3.2 运输问题的表上作业法 一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。 表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。 ; 确定初始方案 ( 初 始 基本可行解); 二、 初始方案的确定 1、作业表（产销平衡表） 初始方案就是初始基本可行解。 将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。 表3-3是两个产地、三个销地的运输问题作业表。 ;调 销地 运 量 产地;其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价或运距。 2、确定初始方案的步骤： （1）选择一个xij，令xij= min{ai，bj}= ;（2）调整产销剩余数量??从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij =0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj； （3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。; 按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。 对xij的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的xij，则构成最小元素法，若每次都选择左上角格子对应的xij就形成西北角法（也称左上角法）。;3、举例 ;表3-4 例3-2有关信息表;例3-2 的数学模型; 分别使用最小元素法和西北角法求出初始方案。 最小元素法的基本思想是“就近供应” ； 西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同 ；;调 销地 运 量 产地; 得到初始调运方案为： x11=100，x13=100，x22=150，x23=100 ;最小元素法实施步骤口诀;调 销地 运 量 产地; 得到初始调运方案为： x11=100，x12=100，x22=50，x23=200 ;1、闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。; 约定作为起始顶点的非基变量为偶数次顶点，其它顶点从1开始顺次排列，那麽，该非基变量xij的检验数：;调 销地 运 量 产地;非基变量X12的检验数：;2、位势法 ;例3-2初始调运方案位势变量对应表 ;方程组的特点： ? 方程个数是m+n-1=2+3-1=4个，位势变量共有m+n=2+3=5个，通常称ui为第i行的位势，称vj为第j列的位势； ? 初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的位势变量之和等于该基变量对应的运距（或运价）：ui+vj=cij； ?方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。 ; 给定自由变量一个值，解方程组式（3-7），即可求得位势变量的一组值，根据式（3-6）结合方程组（3-7），推出计算非基变量xij检验数的公式 σij=cij-（ui+vj） （3-8）;位势法计算非基变量xij检验数的公式 σij=cij-（ui+vj） （3-8）; 四、方案调整 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。 若检验数σij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量ε：;调 销地 运 量 产地; ?计算调整量：ε=Min（100，150）=10