表上作业法ppt课件

1、整理课件4.3 运输问题的运输问题的 表上作业法表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。整理课件n表上作业法是单纯形法在求解运输问题的一种简便方法。n单纯形法与表上作业法的关系：（1）找出初始基可行解 （2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同整理课件换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否整理课件举例说明表上作业法例1、某

2、部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表：41228543961111104814121482210163214321AAABBBB销量产量销地产地整理课件第一步：确定初始基可行解 最小元素法、伏格尔法n最小元素法思路： 从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。整理课件最小元素法举例41228543961111104814121482210163214321AAABBBB销量产量销地产地822010100614868000060整理课件最小元素法举例41228543961111104814121482210163214321AAABBBB销量

3、产量销地产地821014682466811632410514280z最小元素法缺点：会出现顾此失彼 （运费差额问题）考虑运价差整理课件 罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：;差额大，则不按最小运费调运，运费增加大。差额大，则不按最小运费调运，运费增加大。;差额小，则不按最小运费调运，运费增加不大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。伏格尔法思路：整理课件n结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数04-4=0第一次第一

4、次整理课件n结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数013-2=1第一次第一次整理课件n结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数011第一次第一次整理课件n结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数4-2=22153第

5、一次第一次整理课件n结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数21531480优先安排销地 ，否则运价会更高2B下次不考虑该列第一次第一次整理课件第二次第二次n结合例结合例1说明这种方法。说明这种方法。行罚数012 列 罚 数213优先安排销地 ，否则运价会更高4B84814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地148006下次不考虑该行整理课件n结合例结合例1说明这种方法。说明这种方法。行

6、罚数01 列 罚 数21284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地148006下次不考虑该列802第三次第三次整理课件n结合例结合例1说明这种方法。说明这种方法。行罚数76 列 罚 数1284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地1480068024120下次不考虑该列第四次第四次整理课件n结合例结合例1说明这种方法。说明这种方法。行罚数00 列 罚 数24284814121482210163214321AAABBBB41228543961111

7、10销量产量销地销地产地产地1480068024120000第五次第五次整理课件n例1用伏格尔法得到的初始基可行解4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地48148122244685149228114412 z目标函数值目标函数值用最小元素法求出的目标函数z=246整理课件第二步：解的最优性检验n闭回路法 思路：计算空格（非基变量）的检验数 24242121121211110 xxxxzz0112412110, 1zzxxx若令则如何求检验数？分析：运费的增量即 增加1个单位 的检验数=相应的运费增量11x11x整理课件

8、41228543961111104814121482210163214321AAABBBB销量产量销地产地821014682460z从初始表分析：要保证产销平衡，则1, 12344110zz111121231311xxxx 称为闭回路 21231311xxxx+1-1+1-1整理课件41228543961111104814121482210163214321AAABBBB销量产量销地产地821014682561112121561143102221整理课件检验数表41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468211-11

9、012,0124表中的解不是最优解。整理课件第三步：解的调整 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468-1（-2）（-2）（+2）（+2）整理课件n调整后的解为：41228543961111104814121482210163214321AAABBBB销量产量销地产地8212144822091122246244689211441251428, 0zij此时的解为最优解。有无穷多最优解整理课件几点说明：n当检验数为的负的变量超过两个，选择最小者对应的变量换入；n在最优解的表中，若有检验数