运筹学 运输问题.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第四章 运输问题,Transportation Problem,第四章 运输问题,第,1,节 运输问题及其数学模型,第,2,节 表上作业法,第,3,节 产销不平衡的运输问题及其求解方法,第,4,节 应用问题举例,第,1,节 运输问题及其数学模型,一、运输问题,运输问题属于线性规划问题，因为其约束方程组的系数矩阵,A,具有特殊的结构，所以专门介绍一种比单纯形法更简便的求解方法，以节约计算时间和费用。,第,1,节 运输问题及其数学模型,例,1,：某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为,A,1,7t,（吨）；,A,2,4t,；,A,3,9t,。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为,B,1,3t,（吨）；,B,2,6t,；,B,3,5t,；,B,4,6t,。已知从每个加工厂到各销售门市部每吨糖果的运价，如下表所示。试问该食品公司应如何,调运,，在满足各门市部销售需要的情况下，使总的运费支出最少。,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,7,4,9,销量,3 6 5 6,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,3 11 3 10,1 9 2 8,7 4 10 5,第,1,节 运输问题及其数学模型,二、运输问题的数学模型,已知有,m,个生产地点（简称产地）可供应某种物资，其供应量（产量）分别为 ；有,n,个销售地点（简称销地），其需要量（销量）分别为,，从 到 运输单位物资的运价（单位运价）为 ，将这些数据表示在如下页的两个表中。问应如何调运，在满足各销地销量的情况下，使总的运费支出最少？,第,1,节 运输问题及其数学模型,产销平衡表,两个,表,合二为一,销地,产地,B,1,B,2,B,n,产量,A,1,A,2,A,m,a,1,a,2,a,m,销量,b,1,b,2,b,n,销地,产地,B,1,B,2,B,n,A,1,A,2,A,m,c,11,c,12,c1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,销地,产地,B,1,B,2,B,n,产量,A,1,A,2,A,m,c,11,c,12,c,1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,单位运价表,第,1,节 运输问题及其数学模型,例,1,：,解：,设,x,ij,为第,i,加工厂向第,j,门市部的糖果的供应量，,c,ij,表示第,i,加工厂向第,j,门市部供应糖果的单位运费,第,1,节 运输问题及其数学模型,产销平衡 运输问题的数学模型：,设,x,ij,表示从产地,A,i,运往销地,B,j,的产品数量,第,1,节 运输问题及其数学模型,特征,（,1,）决策变量：,mn,（,2,）约束方程：,m,n,；都是等式约束,（,3,）目标函数：最小化,（,4,）约束方程组系数矩阵,A,A,中只有数字,0,或,1,A,的每一列只有两个非零元素,1,（,5,）各产地产量之和等于各销地销量之和,（,6,）,基变量,：,m,n,1,（,7,）对于,产销平衡的运输问题,，必有可行解和最优解,第,1,节 运输问题及其数学模型,第,2,节 表上作业法,一、表上作业法的解题思路,表上作业法的实质是单纯形法在求解运输问题时的一种简化方法，属于单纯形法，又称为运输单纯形法。,基可行解,最优否,结束,换基,是,否,第,2,节 表上作业法,二、表上作业法的特点,表上作业法是一种迭代法,用表上作业法求解运输问题，直接在表上进行，不必写出数学模型,第,2,节 表上作业法,三、表上作业法的解题步骤,（一）找出初始基可行解：在产销平衡表上找出,(m+n-1),个数字格，形成初始产销平衡表,方法,（二）求非基变量检验数：计算初始产销平衡表中空格的检验数，判别是否达到最优解，如果已达到，停止计算；否则转入,3,方法,（三）确定换入变量和换出变量，找出新的基可行解,方法：闭回路调整法,（四）重复（二）（三），直到求出最优解,第,2,节 表上作业法,（一）确定初始基可行解,方法一：最小元素法,1,、基本思路,从运费上考虑，优先安排单位运价最小的产地和销地之间的运输业务，最大限度地满足其产销量，从而实现“就近供应”。,第,2,节 表上作业法,2,、求解步骤,第一，从单位运价表中找出最小运价，（有两个或两个以上的最小单位运价，则任选其一），比较产量和销量：产量销量，则划去该运价所在列；产量销量，则划去该运价所在行。并在初始产销平衡表上填上相应的数字。,第二，从单位运价表中未被划去的运价中再找最小运价，重复第一第二，直到单位运价表中所有运价都被划去，并找出,(m+n-1),个数字格。,第,2,节 表上作业法,例,2,：用最小元素法找出,例,1,的初始基可行解。,产销平衡表和单位运价表合二为一，如下所示：,门市部,加工厂,B1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3 11 3 10,1 9 2 8,7 4 10 5,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,2,：,解：初始产销平衡表,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,4 3,3 1,6 3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,3,、小结,（,1,）,在初始产销平衡表上每填入一个数字，在单位运价表上就划去一行或一列（当表中只剩一个元素时，在初始产销平衡表上填数字时，在单位运价表上同时划去一行和一列）,（,2,）在单位运价表上共划去（,m,n,）条直线，（相当于单位运价表上所有,c,ij,都被划去两次）,（,3,）,在初始产销平衡表上填了（,m,n,1,）个数字格，每行数字之和该行产量，每列数字之和该列销量,第,2,节 表上作业法,例,3,：用最小元素法求出下述运输问题的初始基可行解。,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3 11 4 5,7 7 3 8,1 2 10 6,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,3,：,解：初始基可行解,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,0,1 6,0,4,3 6,0,0,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,4,：判断下表给出的运输方案能否作为用最小元素法 求解出的初始基可行解？,销地,产地,1 2 3 4,产量,1,2,3,0 15,15 10,5,15,25,5,销量,5 15,15,10,第,2,节 表上作业法,（一）确定初始基可行解,方法二：伏格尔法,1,、,基本思路,按某一最小单位运价优先安排物品调运时，可能导致其他产销点不得不采用很高的单位运价进行运输，从而使整个运输费用增加。对每一个产地或销地，找出最小单位运价和次小单位运价，求二者之差。若差值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，若二者之差很大，不按最小单位运价组织运输就会造成很大损失所以应尽量按最小单位运价安排运输。,第,2,节 表上作业法,2,、求解步骤,第一，在单位运价表中分别计算各行和各列的最小运价与次小运价的差额，并填在该表的最右列和最下行。,第二，从行或列差额中选出最大者，（有两个或两个以上的最大差额，则选择差额所在行（或列）中的最小单位运价），选择它所在行或列中的最小运价，按照最小元素法确定初始基可行解。,第三，对单位运价表中未被划去的运价再计算各行和各列的最小运价与次小运价的差额，并仍填入该表的最右列和最下行，重复第二、三，直至给出初始基可行解为止，即找出（,m+n-1,）个数字格。,第,2,节 表上作业法,例,5,：用伏格尔法找出,例,1,的初始基可行解门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,3 11 3 10,1 9 2 8,7 4 10 5,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,5,：,解：初始产销平衡表,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,5 2,3 1,6 3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,3,、小结,（,1,）伏格尔法和最小元素法仅在确定产销关系的原则上不同，其余步骤都相同（伏格尔法是在最小元素法的基础上改进的一种方法）,（,2伏格尔法给出的初始基可行解比用最小元素法给出的初始基可行解更接近最优解（伏格尔法给出的解的目标函数值比最小元素法给出的解的目标函数值小）,（,3,）伏格尔法得出的初始基可行解常作为运输问题最优解的近似解,作业,10,作业,10,：,1,、用最小元素法找出下述,运输问题的初始基可行解。,2,、找出下述运输问题的近,似最优解。,（其中,M,为任意大正数，,表示含义为从,A,4,到,B,4,不存在,运输路线）,销地,产地,1 2 3,产量,1,2,3,5 1 8,2 4 1,3 6 7,12,14,4,销量,9 10 11,销地,产地,1 2 3 4 5,产量,1,2,3,4,10 2 3 15 9,5 10 15 2 4,15 5 14 7 15,20 15 13 M 8,25,30,20,30,销量,20 20 30 10 25,作业,10,答案,1,、,2,、,销地,产地,1 2 3,产量,1,2,3,2 10,3 11,4,12,14,4,销量,9 10 11,销地,产地,1 2 3 4 5,产量,1,2,3,4,0,25,0,20,0 0,10,0,0,20,0 0 0,5,0,25,25,30,20,30,销量,20 20 30 10 25,第,2,节 表上作业法,（二）求检验数，判别最优解,基本思路,计算空格（非基变量）的检验数，（运输问题的目标函数要求实现最小化）当所有检验数,0,时，所得的解是最优解，否则要进行解的改进。,第,2,节 表上作业法,（二）求检验数，判别最优解,方法一：闭回路法,1,、求解步骤,第一，在初始产销平衡表上，从每一空格出发找一条闭回路：以某空格为起点，用水平或垂直线向前画，碰到一数字格转,90,（有些情况下也可以不改变方向），然后继续前进，直到回到起始空格为止。,第二，在一闭回路上，令某空格取值为,+1,，表示增加的运量，然后变化相应数字格的值，并计算该闭回路上运费的变化值，即为该空格的检验数，填入检验数表。,第,2,节 表上作业法,2,、检验数的含义,检验数表示变化的运费。即：若某空格（,A,i,，,B,j,）的检验数,0,，表示将该空格变为数字格使运输费用减少，则当前这个解不是最优解；反之，若所有空格的检验数都,0,，表示不管怎样变换，都使运输费用增加，则目标函数已无法改进，当前这个解就是最优解,第,2,节 表上作业法,例,6,：用闭回路法求,例,5,所得的初始基可行解的检验数。,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,5 2,3 1,6 3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,6,：,解：检验数表,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,0 2,2 1,9 12,第,2,节 表上作业法,例,7,：用闭回路法求,例,2,所得的初始基可行解的检验数。,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,4 3,3 1,6 3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,7,：,解：检验数表,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,1 2,1 -1,10 12,第,2,节 表上作业法,3,、小结,（,1,）闭回路的顶点，除出发点为空格外，其他均为数字格,（,2,）每个空格唯一存在一条闭回路,（,3,）对于产销点过多的运输问题，空格的数目很大，计算检验数很繁琐,第,2,节 表上作业法,（二）求检验数，判别最优解,方法二：位势法,1,、求解步骤,第一，仿照初始产销平衡表做一个表，在对应的数字格处填入单位运价,c,ij,。,第二，在表的最右列和最下行分别增加一列,u,i,和一行,v,j,，使表中的单位运价等于它所在行和列的,u,i,与,v,j,之和，求出所有的,u,i,和,v,j,，并填写在表中。,第三，计算各空格的检验数，填入检验数表。,第,2,节 表上作业法,例,8,：用位势法求,例,2,所得的初始基可行解的检验数。,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,4 3,3 1,6 3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,8,：,解：检验数表,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,1 2,1 -1,10 12,第,2,节 表上作业法,例,9,：用位势法求,例,5,所得的初始基可行解的检验数。,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,5 2,3 1,6 3,7,4,9,销量,3 6 5 6,第,2,节 表上作业法,例,9,：,解：检验数表,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,0 2,2 1,9 12,第,2,节 表上作业法,2,、小结,当运输问题的产地和销地很多时，空格的数目很大，采用位势法计算检验数简便,第,2,节 表上作业法,（三）确定换入和换出变量，找出新的基可行解，直至求出最优解,方法：闭回路调整法,1,、基本思想,在初始产销平衡表中，选取检验数为负的所有空格中的最小者作为换入格，以对应空格为出发点画出闭回路，在经过的数字格中选择（,-1,）的最小者，对应的数字格为换出格，然后对闭回路上各顶点的数据进行调整，得到另一个更好的基可行解。,第,2,节 表上作业法,2,、求解步骤,第一，确定换入格。在初始产销平衡表上，最小的负检验数所在的空格为换入格，（有两个或两个以上的最小者，则任选其一），并以此空格为出发点，作一闭回路。,第二，确定换出格：选择闭回路上标记为,-1,的数字格中的最小者，记做,，则该数字格为换出格。,第三，调整：将闭回路上标记为,+1,的数字格加,，标记为,-1,的数字格减,，得到新的基可行解。,第四，采用闭回路法或位势法求空格的检验数，若所有检验数都,0,，则获得最优解；否则重复第一第三，直至求出最优解。,第,2,节 表上作业法,例,10,：以,例,8,所求的检验数为依据，求,例,1,的最优解。,检验数表 初始产销平衡表,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,4 3,3 1,6 3,7,4,9,销量,3 6 5 6,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,1 2,1 -1,10 12,第,2,节 表上作业法,例,10,：,解：最优解 检验数表,z,*,=85,门市部,加工厂,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,5 2,3,1,6 3,7,4,9,销量,3 6 5 6,门市部,加工厂,B,1,B,2,B,3,B,4,A,1,A,2,A,3,0 2,2 1,9 12,第,2,节 表上作业法,四、表上作业法的解,1,、,无穷多（多重）最优解,某个空格（非基变量）的检验数为,0,时，该运输问题有无穷多（多重）最优解。在已求得一个最优解的表中，以这样的空格出发做闭回路重新进行调整，得到另一个最优解。,第,2,节 表上作业法,2,、退化解,某个数字格（基变量）为,0,时，该运输问题为退化解。,退化解出现的情况：,确定,初始解,的各供需关系时，若在某格填入某数字后，出现该处的供应量与需求量相等。,用,闭回路调整法,调整时，在闭回路上出现两个或两个以上的具有（,-1,）标记的相等的最小值。,第,2,节 表上作业法,例,11,：已知某初始产销平衡表，如下表：,空格,A,2,B,4,格的检验数,0,，其余空格的检验数均,0,，试确定换入、换出格，求出新的基可行解。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,4 1,3 1,6 3,5,4,9,销量,3 6 5 4,第,2,节 表上作业法,例,11,：,解：下一个基可行解,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A2,A,3,5 0,3,1,6 3,5,4,9,销量,3 6 5 4,第,2,节 表上作业法,例,11,：,解：再下一个基可行解,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,0,5,3,1,6 3,5,4,9,销量,3 6 5 4,第,2,节 表上作业法,五、表上作业法计算步骤框图,分析实际问题,列出产销平衡表及单位运价表,确定初始调运方案,（最小元素法或伏格尔法）,求检验数,（闭回路法或位势法）,所有检验数,0,唯一最优解,算出总的运价,找出最小的负检验数,用闭回路调整，得出新的调运方案,是,否,某空格检验数,0,是,否,无穷多最优解,第,2,节 表上作业法,例,12,：已知三个产地,A,1,，,A,2,，,A,3,，四个销地,B,1,，,B,2,，,B,3,，,B,4,的产销量即单位运价如下表所示，求使总运费最少的调运方案。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,2 2 3 7,4 3 5 9,1 6 7 8,500,600,300,销量,300 200 500 400,第,2,节 表上作业法,例,12,：,解：无穷多最优解、退化解,z,*,=6000,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,0 500,200 0 400,300,500,600,300,销量,300 200 500 400,作业,11,作业,11,：用表上作业法求解下列运输问题的最优解。（要求采用伏格尔法、闭回路法求解）,1,、,2,、,销地,产地,甲 乙 丙 丁,产量,1,2,3,3 7 6 4,2 4 3 2,4 3 8 5,5,2,3,销量,3 3 2 2,销地,产地,甲 乙 丙 丁,产量,1,2,3,10 6 7 12,16 10 5 9,5 4 10 10,4,9,4,销量,5 2 4 6,作业,11,答案,1,、,2,、,销地,产地,甲 乙 丙 丁,产量,1,2,3,3,0,2,0,2,3,5,2,3,销量,3 3 2 2,销地,产地,甲 乙 丙 丁,产量,1,2,3,1 2 1,3 6,4,4,9,4,销量,5 2 4 6,第,3,节 产销不平衡的运输问题及其求解方法,一、求解思路,总产量不等于总销量，为使用表上作业法求解，将产销不平衡运输问题转化为产销平衡运输问题。,第,3,节 产销不平衡的运输问题及其求解方法,二、求解方法,1,、总产量总销量（）,销地,产地,B,1,B,2,B,n,产量,A,1,A,2,A,m,c,11,c,12,c,1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,第,3,节 产销不平衡的运输问题及其求解方法,数学模型：,第,3,节 产销不平衡的运输问题及其求解方法,销地,产地,B,1,B,2,B,n,B,n+1,产量,A,1,A,2,A,m,c,11,c,12,c,1n,0,c,21,c,22,c,2n,0,c,m1,c,m2,c,mn,0,a,1,a,2,a,m,销量,b,1,b,2,b,n,b,n+1,第,3,节 产销不平衡的运输问题及其求解方法,解题思路：,为借助于产销平衡的表上作业法求解，增加一个假想的销地,B,n+1,，由于实际上它不存在，因而由产地,A,i,（,i=1,，,2,，,，,m,）调运到这个假想销地的物品数量,x,i,n+1,，就是就地存贮在,A,i,的物品数量。就地存贮的物品未经运输，所以其单位运价,c,i,n+1,=0,（,i=1,，,2,m,）。,第,3,节 产销不平衡的运输问题及其求解方法,数学模型：,第,3,节 产销不平衡的运输问题及其求解方法,数学模型变化：,第,3,节 产销不平衡的运输问题及其求解方法,2,、总产量总销量（）,销地,产地,B,1,B,2,B,n,产量,A,1,A,2,A,m,c,11,c,12,c,1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,第,3,节 产销不平衡的运输问题及其求解方法,数学模型：,第,3,节 产销不平衡的运输问题及其求解方法,销地,产地,B,1,B,2,B,n,产量,A,1,A,2,A,m,A,m+1,c,11,c,12,c,1n,c,21,c,22,c,2n,c,m1,c,m2,c,mn,0,0,0,a,1,a,2,a,m,a,m+1,销量,b,1,b,2,b,n,第,3,节 产销不平衡的运输问题及其求解方法,解题思路：,为借助于产销平衡的表上作业法求解，增加一个假想的产地,A,m+1,，由于实际上它不存在，因而由它发往各个销地的物品数量,x,m+1,j,（,j=1,，,2,，,，,n,），就是各销地,B,j,所需物品的欠缺额。欠缺的物品未经运输，所以其单位运价,c,m+1,j,=0,（,j=1,，,2,，,，,n,）。,第,3,节 产销不平衡的运输问题及其求解方法,数学模型：,第,3,节 产销不平衡的运输问题及其求解方法,数学模型变化：,第,3,节 产销不平衡的运输问题及其求解方法,例,13,：用表上作业法求解下述运输问题的最优解。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,2 11 3 4,10 3 5 9,7 8 1 2,7,5,7,销量,2 3 4 6,第,3,节 产销不平衡的运输问题及其求解方法,例,13,：,解：不产销平衡,产销平衡,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,A,1,A,2,A,3,2 11 3 4,0,10 3 5 9,0,7 8 1 2,0,7,5,7,销量,2 3 4 6,4,19,15+4,第,3,节 产销不平衡的运输问题及其求解方法,无穷多最优解,z,*,=35,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,A,1,A,2,A,3,2 3 2,3 2,4 3,7,5,7,销量,2 3 4 6,4,19,15+4,第,3,节 产销不平衡的运输问题及其求解方法,小结,采用最小元素法或伏格尔法求初始基可行解时，由于虚拟产地或销地不存在，所以尽管二者的单位运价,c,i,n+1,=0,或,c,m+1,j,=0,，但不能作为最小运价（元素）优先使用。应从有实际运输任务的产地或销地之间安排运量，最后再考虑虚拟产、销地的,0,运价。,作业,12,作业,12,：用表上作业法求解下列运输问题的最优调运方案和最小总运费。（要求采用最小元素法、位势法求解）,1,、,2,、,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3 5 9 4,7 4 8 5,9 7 5 2,300,500,600,销量,150 100 400 450,销地,产地,B,1,B,2,B,3,产量,A,1,A,2,6 5 4,3 7 2,15,25,销量,20 10 15,作业,12,答案,1,、,2,、,销地,产地,B,1,B,2,B,3,B,4,B,5,产量,A,1,A,2,A,3,150,150,100,100,300,400 200,300,500,600,销量,150 100 400 450,300,1400,1100+300,销地,产地,B,1,B,2,B,3,产量,A,1,A,2,A,3,10 5,15 10,5,15,25,5,销量,20 10 15,40+5,45,第,4,节 应用问题举例,例,14,：设有三个化肥厂（,A,，,B,，,C,）供应四个地区,1,，,2,，,3,，,4,的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调运方案。,需求地区,化肥厂,1 2 3 4,产量,（万吨）,A,B,C,16 13 22 17,14 13 19 15,19 20 23,50,60,50,最低需求（万吨）,最高需求（万吨）,30 70 0 10,50 70 30,不限,第,4,节 应用问题举例,例,14,：,解：不产销平衡产销平衡,需求地区,化肥厂,1,1,2,2,3,3,4,4,产量,（万吨）,A,B,C,D,16,16,13,13,22,22,17,17,14,14,13,13,19,19,15,15,19 19 20,20,23,23,M M,M 0 M 0(M)M(0)0 M 0,50,60,50,50,需求量（万吨）,30,20,70 0 0,30,10,50,160+50,210,第,4,节 应用问题举例,简化表格,需求地区,化肥厂1,1,2,3,4,4,产量,（万吨）,A,B,C,D,16,16,13 22 17,17,14,14,13 19 15,15,19 19 20 23 M M,M 0 M 0 M 0,50,60,50,50,需求量（万吨）,30,20,70,30,10,50,160+50,210,第,4,节 应用问题举例,退化最优解,z,*,=2460,需求地区,化肥厂,1,1,2,3,4,4,产量,（万吨）,A,B,C,D,50,20 10 30,30 20 0,30,20,50,60,50,50,需求量（万吨）,30,20,70,30,10,50,160+50,210,第,4,节 应用问题举例,例,15某工厂有,B,1,，,B,2,，,B,3,三个分厂，在生产中需要用的热水分别由,A,1,，,A,2,两个锅炉房供应。每月各分厂的需求量、锅炉房的供应量及输送热水的单位费用见下表。由于需求量大于供应量，工厂正在建设新的锅炉房。但是在新锅炉房投入使用之前，经总厂协调后决定：保证,B,1,分厂的需求量，,B,2,分厂的供应量最多可减少,90t,（吨），,B,3,分厂的供应量不能少于,180t,。应如何安排给三个分厂的供热水方案，在保证各分厂基本需求的情况下，使输送总费用最低。,销地,产地,B,1,B,2,B,3,供应量,/t,A,1,A,2,7 6 8,8 5 9,280,270,需求量,/t,100 320 260,第,4,节 应用问题举例,例,15,：,解：不产销平衡产销平衡,销地,产地,B,11,B,12,B,21,B,22,B,31,B,32,供应量,/t,A,1,A,2,A,3,7 7 6 6 8 8,8 8 5 5 9 9,M 0(M)M 0 M 0,280,270,130,需求量,/t,100,0,230,90,180,80,550+130,680,第,4,节 应用问题举例,简化表格,销地,产地,B,11,B,21,B,22,B,31,B,32,供应量,/t,A,1,A,2,A,3,7 6 6 8 8,8 5 5 9 9,M M 0 M 0,280,270,130,需求量,/t,100,230,90,180,80,550+130,680,第,4,节 应用问题举例,无穷多、退化最优解,z,*,=3490,销地,产地,B,11,B,21,B,22,B,31,B,32,供应量,/t,A,1,A,2,A,3,100 0 180,230 40,50 80,280,270,130,需求量,/t,100,230,90,180,80,550+130,680,