表上作业法课件

第二节运输问题的表上作业法由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。.单纯形法与表上作业法的关系：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同.换基:（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否.举例说明表上作业法某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地.第一步：确定初始基可行解

——最小元素法、伏格尔法【1】最小元素法思路：

就近供应，从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。

.最小元素法举例4122854396111110销量产量销地产地822010100614868000060.最小元素法得到的初始调运方案4122854396111110销量产量销地产地82101468.练习某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：311174328510109销量产量销地产地.最小元素法练习311174328510109销量产量销地产地311044036333000030.初始调运方案311174328510109销量产量销地产地314633最小元素法缺点：会出现顾此失彼（运费差额问题）考虑运价差.罚数（即差额）=次小运价-最小运价对差额最大处，采用最小运费调运。【2】伏格尔法思路：第一步：确定初始基可行解

——最小元素法、伏格尔法.伏格尔法思路罚数（即差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。.结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①04-4=0第一次.4122854396111110销量产量销地产地行罚数①013-2=1第一次.4122854396111110销量产量销地产地行罚数①011第一次.4122854396111110销量产量销地产地行罚数①011列罚数2153①第一次.4122854396111110销量产量销地产地行罚数①011列罚数2153①1480优先安排销地，否则运价会更高下次不考虑该列第一次.第二次行罚数②012列罚数213②优先安排销地，否则运价会更高84122854396111110销量产量销地产地148006下次不考虑该行.行罚数③01列罚数212③84122854396111110销量产量销地产地148006下次不考虑该列802第三次.行罚数④76列罚数12④84122854396111110销量产量销地产地1480068024120下次不考虑该列第四次.行罚数⑤00列罚数2⑤4284122854396111110销量产量销地产地1480068024120004第五次0.例1用伏格尔法得到的初始基可行解4122854396111110销量产量销地产地48148122目标函数值用最小元素法求出的目标函数z=246一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。.列罚数1352①311174328510109销量产量销地产地练习行罚数①0第一次11优先安排销地，否则运价会更高630.311174328510109销量产量销地产地行罚数②0第二次12列罚数132630优先安排销地，否则运价会更高303②.311174328510109销量产量销地产地行罚数③0第三次1列罚数122630303③310.311174328510109销量产量销地产地行罚数④7第四次6列罚数12630303④310502.311174328510109销量产量销地产地行罚数⑤0第五次0列罚数2630303⑤310502120200.练习题用伏格尔法得到的初始基可行解311174328510109销量产量销地产地31

5

623用最小元素法求出的目标函数z=86.第二步：解的最优性检验思路：计算空格（非基变量）的检验数。两种方法：【1】闭回路法每一空格出发一定存在且可以找到唯一的闭回路。【2】位势法由对偶理论，得检验数为。.【1】闭回路法在给出调运方案的计算表上，从每一空格出发找一条闭回路。

以某空格为起点，用水平或垂直线向前划，当碰到一数字格时，可以转90度（也可以越过）后，继续前进，直到回到起始空格为止。.每一空格出发一定存在且可以找到唯一的闭回路。因m+n-1个数字格（基变量）对应的系数向量是一个基。则任一空格（非基变量）对应的系数向量均可由这个基线性表示。.闭回路法的经济解释若令分析：——运费的增量即增加1个单位的检验数=相应的运费增量.4122854396111110销量产量销地产地82101468从初始表分析：要保证产销平衡，则称为闭回路+1-1+1-1.4122854396111110销量产量销地产地8210146821.检验数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。.或称对偶变量法【2】位势法.运输问题的对偶问题可写为运输问题的对偶问题

——对偶变量与原问题检验数的关系.线性规划问题变量的检验数为运输问题的对偶问题

——对偶变量与原问题检验数的关系变量的检验数为.设运输问题的一组基变量为运输问题的对偶问题

——对偶变量与原问题检验数的关系.由于基变量的检验数为零，故有运输问题的对偶问题

——对偶变量与原问题检验数的关系m+n-1个方程m+n个变量有一个自由未知量.方程组有解，且不唯一。求出方程组的解（称为位势）而其他变量的检验数为运输问题的对偶问题

——对偶变量与原问题检验数的关系求运输问题检验数的一种方法.最小元素法得到的初始基可行解311174328510109销量产量销地产地314633为基变量。则有..销地产地000000311174328510109-11021211存在负检验数，说明不是最优解。检验数表.第三步：解的调整当在表中空格处出现负检验数时，表示未得最优解。若有两个和两个以上的负检验数，一般选其中最小的负检验数，以它对应的空格为调入格。即选择最小检验数对应的非基变量为换入变量。.第三步：解的调整调整位置（A2，B4）非空，回路角上的格至少为空，且保证数字的非负性。4122854396111110销量产量销地产地82101468-1（-）（-）（+）（+）2222.调整后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解。有无穷多最优解.几点说明：当检验数为负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有非基变量的检验数=0，则该运输问题有无穷多最优解；.几点说明：退化一

迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。.退化情况一：某部门三个工厂生产同一产品的产量,四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地8800.几点说明：退化二闭回路上出现两个或两个以上的具有（-）标记的相等的最小值。只能选一个作为调入格，经调整后，得退化解。则在另一数字格上填入0。.退化情况二：

闭回路法调整，