运筹学07-运输问题课件

1、第七章 运输问题,7.1 运输问题的数学模型 7.2 运输问题的应用 7.3 表上作业法,7.1 运输问题的数学模型,(1) 运输问题的引入,例1 有一个地区有两个产棉区A1, A2向三个纺织厂B1 B2,B3供应棉花,产棉区每年的供应量分别为70kt和50kt;纺织厂每年的需求量分别为50kt,40kt和30kt.已知各产棉区到各纺织厂的单位运价如左表,问如何安排运输方案,使总运费最小.设由Ai运往Bj的棉花的运量为xij(kt),如右表:,7.1 运输问题的数学模型,(1) 运输问题的引入,由于各个产棉区Ai运往各个纺织厂Bj的总量应该等于它的产量，所以 x11 + x12 + x13 =

2、70 x21 + x22 + x23 =50 另外,由于各个纺织厂收到各个产棉区运输的总量应该等于它的需求量 x11 + x21 =50 x12 + x22 =40 x13 + x23 =30 目标是总运费最小，即 minz=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23,7.1 运输问题的数学模型,(1) 运输问题的引入,此运输问题的数学模型为: min z=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23 x11 + x12 + x13 =70 x21 + x22 + x23 =50 x11 + x21 =50 x12 +

3、x22 =40 x13 + x23 =30 xij 0(i=1,2;j=1,2,3),7.1 运输问题的数学模型,(2) 运输问题的一般数学模型,运输问题的一般描述: m个产地Ai,I=1,2.,m,产量分别为ai个单位, n个产地Bj,j=1,2.,n,产量分别为bj个单位; Ai与Bj之间的单位运价爲Cij ,问如何安排运输方案,使总运费最少?,7.1 运输问题的数学模型,(2) 运输问题的一般数学模型,此问题的数学模型: min z= cij xij s.t xij = ai (i=1,2.m) xij = bj (j=1,2.n) xij0 (i=1,2.m ,j=1,2.n),i1,

4、j1,m,n,7.1 运输问题的数学模型,(3) 运输问题的模型变化,有时目标函数求最大。如求利润最大或营业额最大等； 当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)； 产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,7.1 运输问题的数学模型,(3) 运输问题的模型变化,例 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,增加一个虚设的销地运输费用为0,7.1 运输问题的数学模型,(3) 运输问题的模型变化,例 某公司从两个

5、产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,增加一个虚设的产地运输费用为0,7.2 运输问题的应用,(1) 产销不平衡的运输问题,例 石家庄北方研究院有三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0-300吨，二区必须满 足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。,解： 根据题意，作出产销平衡与运价表： 这里

6、 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。,7.2 运输问题的应用,(1) 产销不平衡的运输问题,例 设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。 解： 根据题意，作出产销平衡与运价表：,7.2 运输问题的应用,(2) 生产与存储问题,例 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况

7、下，使该厂全年生产总费用为最小的决策方案。,7.2 运输问题的应用,解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货： x11 = 10 生产： x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交 货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作 运费。可构造下列产

8、销平衡问题： 目标函数：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44,7.2 运输问题的应用,(3) 转运问题,在原运输问题上增加若干转运站。运输方式有：产地 转运站、转 运站 销地、产地 产地、产地 销地、销地 转运站、销地 产 地等。 例 腾飞电子仪器公司在大连和广州 有两个分厂生产同一种仪器，大连分厂 每月生产400台，广州分厂每月生产600 台。该公司在上海和天津有两个销售公 司负责对南京、济南、南昌、青岛四个

9、城市的仪器供应。另外因为大连距离青 岛较近，公司同意大连分厂向青岛直接 供货，运输费用如图，单位是百元。问应该如何调运仪器， 可使总运输费用最低？图中 1- 广州、2 - 大连、 3 - 上海、4 - 天津、5 - 南京、6 - 济南、7 - 南昌、8 - 青岛,7.2 运输问题的应用,解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件： 对产地（发点） i ：输出量 - 输入量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销

10、量 例8（续） 目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 约束条件： s.t. x13+ x14 600 (广州分厂供应量限制） x23+ x24+ x28 400 (大连分厂供应量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站） x35+ x45 = 200 （南京的销量） x36+ x46 = 1

11、50 （济南的销量） x37+ x47 = 350 （南昌的销量） x38+ x48 + x28 = 300 （青岛的销量） xij 0 , i,j = 1,2,3,4,5,6,7,8,7.3 表上作业法,模型的矩阵表述 表上作业法的计算步骤 确定初始基可行解 最优解的判别 闭回路调整法,对于平衡运输问题化成矩阵形式: min z=CX ; AX=b ;X0 其中C=(c11, c12 ,. , C1n ,., cm1 , cm2 , , cmn)， b=(a1, a2, am, b1, b2 , bn)T, X=(x11, x12, x1n, , xm1, xm2, xmn) T 。 1 1

12、 1 1 1 1 A= 1 1 1 1 1 1 1 1 1 1 1 1 R(A)=m+n-1,7.3.1 模型的矩阵表示,该系数矩阵中对应于变量xij的系数向量Pij ，其分量中除第i个和第m+j个为1外，其余的都为零。即 Pij (0, 0, 0,1,0, ,0,1,0 , 0)T ei + em+j 对产销平衡的运输问题，由于有以下关系式存在： bj = ( xij )= ( xij )=ai 所以模型最多只有m+n-1个独立约束方程。即 系数矩阵的秩m+n-1。,7.3.1 模型的矩阵表示,表上作业法是运输问题的特殊求解方法，实质是单纯形法。 运输问题都存在最优解。 其计算步骤为： （1

13、）找出初始基可行解。即在（mn）产销平衡表上给出（m+n-1）个数字格。 （2）求各非基变量的检验数。在表上即是空格的检验数。判别是否达到最优解。如果已经是最优解，则停止计算，否则转到下一步。 （3）确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。 （4）重复（2），（3）直到得到最优解(肯定存在)为止。 以上运算都可以在表上进行。,7.3.2 表上作业法的矩阵表示,例 喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为

14、百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？ 这是一个产销平衡的运输问题，因此不需要再假想产地和销地。,7.3.3 表上作业法的计算步骤,一、确定初始基本可行解 为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始基本可行解（调运量）。 1.西北角法：先从表的左上角（即西北角）的变量x11开始分配运输量，并使x11取尽可能大的值，即x11=min(7,3)=3,则x21与x31必为零。同时把B1的销量与A1的产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。,3,11,3,10,8,5,10,2,9,4

15、,7,1,7.3.3 表上作业法的计算步骤,2.最小元素法 西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的33矩阵中再找最小运价，同理可得其他的基本可行解。 一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。,3,11,3,10,8,5,10,2,9,4,7,1,7.3.3 表上作业法的计算步骤,在求初始基本

16、可行解时要注意的两个问题： 1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。 2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。,7.3.3 表上作业法的计算步骤,二、最优解的判别 1.闭回路法 所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然

17、也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。 所谓闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。,7.3.3 表上作业法的计算步骤,从非基变量x11出发，找到一个闭回路如上表所示。回路有四个顶点，除x11外，其余都为基变量。现在把x11的调运量从零增

18、加为1吨，运费也增加了3元，为了使A1产量平衡，x13必须减少1吨，运费减少3元。为了B3的销量平衡，x23必须增加1吨，运费增加2元。同理把x21减少1吨，运费减少1元。调整后，总运费增加了3-3+2-1=1元。说明如果让x11为基变量，运费就会增加，其增加值1作为x11的检验数，为了区别调整量，我们把1加圈。 用同样的方法可以找出所有空格（即非基变量）的检验数。,3,11,3,10,8,5,10,2,9,4,7,1,7.3.3 表上作业法的计算步骤,2.位势法 所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋 予一个数值vj，它们的数值是由基变量xij的检验数 所决定的，则非基变量xij的检验数就可以用公式