表上作业法ppt课件

.,4.3运输问题的表上作业法,由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。,.,表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解,.,换基：,（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。,停止,.,举例说明表上作业法,例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：,.,第一步：确定初始基可行解最小元素法、伏格尔法,最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。,.,最小元素法举例,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,.,最小元素法举例,最小元素法缺点：会出现顾此失彼（运费差额问题）,考虑运价差,.,罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。,对差额最大处，采用最小运费调运。,伏格尔法思路：,.,结合例1说明这种方法。,0,4-4=0,第一次,.,结合例1说明这种方法。,1,3-2=1,第一次,.,结合例1说明这种方法。,1,第一次,.,结合例1说明这种方法。,4-2=2,2,1,5,3,第一次,.,结合例1说明这种方法。,14,8,0,优先安排销地，否则运价会更高,下次不考虑该列,第一次,.,第二次,结合例1说明这种方法。,优先安排销地，否则运价会更高,8,0,6,下次不考虑该行,.,结合例1说明这种方法。,下次不考虑该列,8,0,2,第三次,.,结合例1说明这种方法。,4,12,0,下次不考虑该列,第四次,.,结合例1说明这种方法。,4,2,0,0,0,第五次,.,例1用伏格尔法得到的初始基可行解,目标函数值,用最小元素法求出的目标函数z=246,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,.,第二步：解的最优性检验,闭回路法思路：计算空格（非基变量）的检验数,若令则,如何求检验数？,分析：,即增加1个单位的检验数=相应的运费增量,.,从初始表分析：,要保证产销平衡，则,称为闭回路,+1,-1,+1,-1,.,2,1,.,检验数表,2,1,1,-1,10,12,表中的解不是最优解。,.,第三步：解的调整,调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。,（-2）,（-2）,（+2）,（+2）,.,调整后的解为：,此时的解为最优解。,有无穷多最优解,.,几点说明：,当检验数为的负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。,.,讨论内容：,初始调运方案（