4-2表上作业法ppt课件

第二节运输问题的表上作业法,由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。,1,运输问题表上作业法,单纯形法与表上作业法的关系：（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,运输问题表上作业法,最小元素法得到的初始调运方案,运输问题表上作业法,练习,某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：,3,11,1,7,4,3,2,8,5,10,10,9,运输问题表上作业法,最小元素法练习,3,1,1,0,4,4,0,3,6,3,3,3,0,0,0,0,3,0,运输问题表上作业法,初始调运方案,3,11,1,7,4,3,2,8,5,10,10,9,最小元素法缺点：会出现顾此失彼（运费差额问题）,考虑运价差,运输问题表上作业法,罚数（即差额）=次小运价-最小运价,对差额最大处，采用最小运费调运。,【2】伏格尔法思路：,第一步：确定初始基可行解最小元素法、伏格尔法,伏格尔法思路,罚数（即差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。,运输问题表上作业法,运输问题表上作业法,结合例1说明这种方法。,0,4-4=0,第一次,运输问题表上作业法,1,3-2=1,第一次,运输问题表上作业法,1,第一次,运输问题表上作业法,2,1,5,3,第一次,运输问题表上作业法,14,8,0,优先安排销地，否则运价会更高,下次不考虑该列,第一次,运输问题表上作业法,第二次,优先安排销地，否则运价会更高,8,0,6,下次不考虑该行,运输问题表上作业法,下次不考虑该列,8,0,2,第三次,运输问题表上作业法,4,12,0,下次不考虑该列,第四次,运输问题表上作业法,4,2,0,0,4,第五次,0,运输问题表上作业法,例1用伏格尔法得到的初始基可行解,目标函数值,用最小元素法求出的目标函数z=246,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,运输问题表上作业法,练习,行罚数,0,第一次,1,1,优先安排销地，否则运价会更高,6,3,0,运输问题表上作业法,行罚数,0,第二次,1,2,1,3,2,6,3,0,优先安排销地，否则运价会更高,3,0,3,运输问题表上作业法,行罚数,0,第三次,1,1,2,2,6,3,0,3,0,3,3,1,0,运输问题表上作业法,行罚数,7,第四次,6,1,2,6,3,0,3,0,3,3,1,0,5,0,2,运输问题表上作业法,行罚数,0,第五次,0,2,6,3,0,3,0,3,3,1,0,5,0,2,1,2,0,2,0,0,运输问题表上作业法,练习题用伏格尔法得到的初始基可行解,3,11,1,7,4,3,2,8,5,10,10,9,销量,产量,销地,产地,3,1,5,6,2,3,用最小元素法求出的目标函数z=86,运输问题表上作业法,第二步：解的最优性检验,思路：计算空格（非基变量）的检验数。两种方法：【1】闭回路法每一空格出发一定存在且可以找到唯一的闭回路。【2】位势法由对偶理论，得检验数为。,运输问题表上作业法,【1】闭回路法,在给出调运方案的计算表上，从每一空格出发找一条闭回路。以某空格为起点，用水平或垂直线向前划，当碰到一数字格时，可以转90度（也可以越过）后，继续前进，直到回到起始空格为止。,运输问题表上作业法,每一空格出发一定存在且可以找到唯一的闭回路。,因m+n-1个数字格（基变量）对应的系数向量是一个基。则任一空格（非基变量）对应的系数向量均可由这个基线性表示。,运输问题表上作业法,闭回路法的经济解释,若令,分析：,即增加1个单位的检验数=相应的运费增量,运输问题表上作业法,从初始表分析：,要保证产销平衡，则,称为闭回路,+1,-1,+1,-1,运输问题表上作业法,2,1,运输问题表上作业法,检验数表,2,1,1,-1,10,12,表中的解不是最优解。,运输问题表上作业法,或称对偶变量法,【2】位势法,运输问题,运输问题的对偶问题可写为,运输问题的对偶问题对偶变量与原问题检验数的关系,运输问题,线性规划问题变量的检验数为,运输问题的对偶问题对偶变量与原问题检验数的关系,变量的检验数为,运输问题,设运输问题的一组基变量为,运输问题的对偶问题对偶变量与原问题检验数的关系,运输问题,由于基变量的检验数为零，故有,运输问题的对偶问题对偶变量与原问题检验数的关系,m+n-1个方程m+n个变量,有一个自由未知量,运输问题,方程组有解，且不唯一。求出方程组的解（称为位势）,而其他变量的检验数为,运输问题的对偶问题对偶变量与原问题检验数的关系,运输问题表上作业法,最小元素法得到的初始基可行解,3,11,1,7,4,3,2,8,5,10,10,9,为基变量。则有,运输问题表上作业法,运输问题表上作业法,销地,产地,3,11,1,7,4,3,2,8,5,10,10,9,-1,10,2,12,1,1,存在负检验数，说明不是最优解。,检验数表,运输问题表上作业法,第三步：解的调整,当在表中空格处出现负检验数时，表示未得最优解。若有两个和两个以上的负检验数，一般选其中最小的负检验数，以它对应的空格为调入格。即选择最小检验数对应的非基变量为换入变量。,运输问题表上作业法,第三步：解的调整,调整位置（A2，B4）非空，回路角上的格至少为空，且保证数字的非负性。,（-）,（-）,（+）,（+）,2,2,2,2,运输问题表上作业法,调整后的解为：,此时的解为最优解。,有无穷多最优解,运输问题表上作业法,几点说明：,当检验数为负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有非基变量的检验数=0，则该运输问题有无穷多最优解；,运输问题表上作业法,几点说明：,退化一迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。,运输问题表上作业法,退化情况一：,某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：,8,8,0,0,运输问题表上作业法,几点说明：,退化二闭回路上出现两个或两个以上的具有（-）标记的相等的最小值。只能选一个作为调入格，经调整后，得退化解。则在另一数