运筹学第三章运输问题

1、第三章第三章 运输问题运输问题n运输问题与有关概念n运输问题的求解表上作业法n运输问题应用建模本章内容重点 运输问题模型及有关概念运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 运输问题模型及有关概念运输问题模型及有关概念 例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ B1 B2 B3 产产量量

2、A1 6 4 6 200 A2 6 5 5 300 销销量量 150 150 200 解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： B1 B2 B3 产产量量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 销销量量 150 150 200 运输问题模型及有关概念运输问题模型及有关概念 Min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22

3、= 150 x13 + x23 = 200 xij0(i=1,2；j=1,2,3）运输问题模型及有关概念运输问题模型及有关概念 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系数矩阵运输问题模型及有关概念运输问题模型及有关概念 模型系数矩阵特征 1.共有m+n行，分别表示各产地和销地；m列，分别表示各变量； 2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。运输问题模型及有关概念运输问题模型及有关概念 一般运输问题的线性规划模型及求解思路 一般运输问题的提法： A1, A2,Am 表示某物资的m个产

4、地；B1,B2,Bn 表示某物资的n个销地； si 表示产地 Ai 的产量； dj 表示销地 Bj 的销量； cij 表示把物资为从产地 Ai 运往销地 Bj 的单位运价。 如果s1 + s2 + + sm = d1 + d2 + + dn ，则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论产销平衡问题。运输问题模型及有关概念运输问题模型及有关概念表1 运输问题数据表 销地产地B1 B2 Bn产量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销量d1 d2 dn 设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个

5、运输问题的要求，可以建立运输变量表。运输问题模型及有关概念运输问题模型及有关概念表2 运输问题变量表 销地产地B1 B2 Bn产量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量d1 d2 dn运输问题模型及有关概念运输问题模型及有关概念 m n Min f = cij xij （1） i=1 j=1 n s.t. xij si i = 1,2,m （2） j=1 m xij dj j = 1,2,n （3） i=1 xij0(i=1,2,m;j=1,2,n)（4） 于是得到下列一般运输问题的模型： 在模型（1）（4）中，式（2）为 m

6、个产地的产量约束；式（3）为 n 个销地的销量约束。 运输问题模型及有关概念运输问题模型及有关概念 m n Min f = cij xij i=1 j=1 n s.t. xij = si i = 1,2,m (5) j=1 m xij = dj j = 1,2,n (6) i=1 xij0(i=1,2,m;j=1,2,n) 对于产销平衡问题，可得到下列运输问题的模型：运输问题模型及有关概念运输问题模型及有关概念 在产销平衡问题中，约束条件成 为等式。 在实际问题建模时，还会出现如下一 些变化： （1）有时目标函数求最大，如求利润最 大或营业额最大等； （2）当某些运输线路上的能力有限制时， 模

7、型中可直接加入（等式或不等式）约束； 运输问题模型及有关概念运输问题模型及有关概念 (3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（2）每一式中加上 1 个松弛变量，共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（3）每一式中加上 1 个松弛变量，共 n 个。运输问题模型及有关概念运输问题模型及有关概念 运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题

8、的表上作业法。在这里需要讨论基本可行解、检验数以基的转换等问题。运输问题模型及有关概念运输问题模型及有关概念 求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解运输问题模型及有关概念运输问题模型及有关概念运输问题有关概念jiijijxcZ,minnjmixnjbxmiaxtsijmijijnjiij1,1, 011. .11njjmiiba11产销平衡的运输问题约束方程系数矩阵结构111111111111111111行行nmmnmmnnxxxxxxxxx212222111211njiijax1mijijbx1约束方程系数矩阵结构111111111111

9、111111行行nmmnmmnnxxxxxxxxx212222111211行行jmipij01010约束方程系数矩阵结构行行jmipij01010行iei00100jmiijeep基变量个数m+n-1nmbbbaaanm1111111111111111112121行行bxxxxxxxxxmnmmnn212222111211miiminjijax111njjnjmiijbx111A 的增广矩阵的秩小于m+n基变量个数m+n-11111111111行行nm1312111211mnxxxxxxA 的增广矩阵的秩等于m+n-1 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。

10、运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 重要概念: 闭回路、闭回路的顶点特点 运输问题基变量运输问题基变量闭回路 132222111,jijijijijijisssxxxxxxsssjijijijijijixxxxxx123221211,其中，i1i2,.,is互不相同，j1j2,.,js互不相同）上述形式的变量的集合称为一个闭回路 其中的变量称为闭回路的顶点闭回路的特点：封闭、每行每列至多两个顶点例如，x13, x16, x36, x34, x24, x21 ； x23, x53, x55, x45, x41, x12 ； x11, x14, x34, x

11、31等都是闭回路。 若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：运输问题基变量运输问题基变量 闭回路示意图基变量的构成闭回路 4144343323221211,jijijijijijijijixxxxxxxx11jix12jix22jix23jix33jix34jix44jix41jix 闭回路的一些明显特点： (1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； (2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。 基变量的构成基变量的构成对于闭回路对于闭回路 132222111,jijijijijijissspppppp132222

12、111,jijijijijijisssxxxxxx线性相关其对应的列向量其对应的列向量 0,132222111132222111jmijmijmijmijmijmijijijijijijieeeeeeeeeeeeppppppssssss若变量组中有一部分构成闭回路，则变量组线性相关。基变量的构成孤立点 是其所在行和所在列中包含在该变量组中的唯一向量。*11jix12jix22jix23jix33jix34jix44jix41jix定理定理：r个变量对应的系数列向量线性无关的充要条件是变量组不包含闭回路。推论推论：m+n-1个变量构成基变量的充要条件是不含闭回路。基变量的构成运输问题求解表上作业

13、法初始基本可行解的确定在供需表中任选一个单元xij，尽量匹配产销，使一个约束方程得以满足，填入相应位置；调整Ai的拥有量及Bj的需求量，分别减去xij ，得到调整后的拥有量ai和需求量bj ；若ai=0，则划去对应的行（拥有的量全部运走），若bj=0则划去对应的列（需求的量全部运来），且每次只划去一行或一列（每次只去掉一个约束）；若平衡表中所有的行或列均被划去，则结束。否则，在剩下的平衡表中选下一个变量，转运输问题求解表上作业法B1BjBnA1:Aixijaiai:Ambjbjb j= b j- x ij a i= a i- x ij运输问题求解表上作业法按照上述方法所产生的一组变量的取值将满

14、足下面条件：a所得的变量均为非负，且变量总数恰好为m+n-1个；b所有的约束条件均得到满足；c所得的变量不构成闭回路。因此所得的解一定是运输问题的基本可行解。在上面的方法中： xij的选取方法并没有加以限定，如果采取一定的规则来选取，则会产生不同的方法西北角法运输问题某地区有两个煤矿A1 A2 ，所产的煤要运往三个城市B1 B2 B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案B1B2B3产量A1907095200A2806575230销量100150180若每次在调整后的供需表中选取最左上角的元素，则称为左上角方法（或称西北角法）西北角法B1B2B3

15、产量A1x11x12x13200A2x21x22x23230销量100150180调整量100100调整量0调整量1000调整量050调整量50180调整量00调整量1800调整量0最小费用法B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180调整量15080调整量0调整量800调整量100调整量100100调整量0调整量1000调整量0907095806575缺点：为了节省一出的费用，有时造成在其它处缺点：为了节省一出的费用，有时造成在其它处要多花几倍的运费。要多花几倍的运费。若每次在调整后的供需表中选取对应单位运费最小的元素，则称为最小费用法。伏格

16、尔(Vogel)法 伏格尔法的思想:一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大的地方，说明不能按最小运费调运时，运费增加就越多，因而对差额最大处，就应当采用最小运费法B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180907095806575B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180差额 150差额差额2010差额10520907095806575差额55差额1020差额 180差额差额差额10差额 50 差额差额50差额伏格尔(Vogel)法练习：求初始运输方案

17、（分别用最小费用法和伏格尔法）1234产量192537销量3846产销平衡表单位运价表 B1 B2 B3 B4 A1 2 9 10 7A2 1 3 4 2 A3 3 4 2 5 B1 B2 B3 B4 aiA1 5 4 9 A2 3 2 5A3 3 4 7 bj 3 8 4 6 B1 B2 B3 B4 aiA1 3 5 1 9 A2 5 5 A3 3 4 7 bj 3 8 4 6 AiBjxij 最优性检验就是检查所得到的方案是不是最优方案。 检查的方法与单纯形方法中的原理相同，即计算检验数。计算检验数。 由于目标要求极小极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就

18、不是最优，需要进行调整。基本可行解的最优性检验 运输问题求解表上作业法 + - + - B1B2B3产量A1x11x12x13200A2x21x22x23230销量10015018090709580657510010050180最优性检验21=C21- C11+ C12- C22=80-90+70-65=-513=C13- C23+ C22- C12=95-75+65-70=15以非基变量 x22 为起始顶点的闭回路销地产地B1B2B3B4产量3 11 3 10 71 9 2 8 47 4 10 5 9销量365620(产销平衡)A1A2A3销地产地B1B2B3B4产量3 11 3 410 3

19、71 39 2 18 47 4 610 5 39销量365620(产销平衡)A1A2A3运输费用发生的变化为 92+310+541 中为 ij 以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 2 + 3 10 + 5 4 1 即总的运费增加 1 个单位，这就说明这个调整不能改善目标值。 当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。运输问题求解表上作业法 这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。 故也称这个综合影响为该非基变量 对应的检验数。 闭回路方法原理就是通过寻找闭回路

20、来找到非基变量的检验数。 运输问题求解表上作业法 可以证明，如果对闭回路的方向不加区别，可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。量为其它顶点的闭回路就存在而且唯一。 如果规定作为起始顶点的非基变量为第 1 个顶点，闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点，那么就有 ij = (闭回路上的奇数次顶点单位运费之和) - (闭回路上的偶数次顶点单位运费之和) 其中 ij 为非基变量的下角指标。运输问题求解表上作业法 按上述作法，计算出表的所有非基变量的检验数，把它们填入相应位置的

21、方括号内，如图所示。表4-11 初始基本可行解及检验数 销地产地B1B2B3B4产量A13 111 23 410 37A21 39 12 18-14A37 104 610125 39销量365620(产销平衡) 销地产地B1B2B3B4产量A13 11 3 4 410 3 37A21 3 39 12 1 184A37 4 6 6105 3 39销量365620(产销平衡) 中为 ij 显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。 闭回路法的主要缺点是： 当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。运

22、输问题求解表上作业法最优性检验：位势法位势法 其原理是利用约束条件的特殊性来找到非基变量的检验数。 从约束条件中解出基变量（用非基变量表示基变量），代入目标后消去目标中的基变量，得到的非基变量的系数就是检验数。 这一过程若用消元的方法加以实现，则会产生位势法。若所有非基变量检验数0，则最优。B1B2B3产量A1x11x12x13200A2x21x22x23230销量10015018090709580657510010050180用位势法求检验数用位势法求检验数对偶问题最优解为对偶问题最优解为y=(u1,u2,v1, v2,v3)最优性检验：位势法位势法01131211axxx02232221a

23、xxx012111bxx022212bxx032313bxx0)(322133bxxv0)(11312111axxxu0)(22322212axxxu0)(112111bxxv0)(222122bxxv232221131211756580957090 xxxxxxc约束等式约束等式互补松弛性互补松弛性最优性检验：位势法位势法位势法232221131211756580957090 xxxxxxc23322222211213311221111133221222113231332222121121112232221211312111232221131211)75()65()80()95()70()9

24、0()()()()()(756580957090 xvuxvuxvuxvuxvuxvubvbvbvauaubxxvbxxvbxxvaxxxuaxxxuxxxxxx最优性检验：位势法2332222221121331122111113322122211)75()65()80()95()70()90(xvuxvuxvuxvuxvuxvubvbvbvauauC12213113322221118095075065070090vuvuvuvuvuvu5801595807059001221311332211vuvuvvuvu 由于原问题约束条件任一个方程都可以看成多余的方程，由对偶问题的定义可知，从运输问题

25、的约束方程组中删去一个方程，相应的对偶问题中应删除一个变量，也就是说，对偶问题中有一个变量可自由定值。12213113322221118095075065070090vuvuvuvuvuvu5801595807059001221311332211vuvuvvuvuB1B2B3A1x11x12x13u1 =0A2x21x22x23u2 =-5v1 =90v2 =70v3 =80最优性检验：位势法90（0）70（0）95(15）80（-5）65（0）75（0） 例 ，已得初始运输方案换成运价表，求检验数 B1 B2 B3 B4 A1 2 9 10 7A2 1 3 4 2 A3 3 4 2 5 B1

26、 B2 B3 B4 aiA1 5 4 9 A2 3 2 5A3 3 4 7 bj 3 8 4 6（）中为 ij B1 B2 B3 B4 ui A1 (-4) 9 (3) 7 0 A2 1 (-1) (2) 2 5 A3 (2) 4 2 (3) 5 vj 6 9 7 7Aiui+vjBj由于11， 22 0，所以此方案不是最优解。运输问题 求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解90709580657510010050180 + - + - B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180调整流量X

27、21进基， = minx 11, x22=min100,50=50X22出基调整流量调运量的调整步骤：调运量的调整步骤：闭回路上的奇数次顶点的调运量减去闭回路上的奇数次顶点的调运量减去；闭回路上的偶数次顶点（包括起始变量）闭回路上的偶数次顶点（包括起始变量）的调运量加上的调运量加上；非闭回路顶点的其他变量调运量不变；非闭回路顶点的其他变量调运量不变； 奇数点上被修改为奇数点上被修改为0的变量为出基变量，的变量为出基变量，在新的方案中不再标出其值。但若有两个在新的方案中不再标出其值。但若有两个为零的变量，则只取其一作为出基变量。为零的变量，则只取其一作为出基变量。 B1B2B3产量A1x11x1

28、2x13200A2x21x22x23230销量1001501809070958065755015050180调整流量22=C22- C21+ C11- C12=65-80+90-70=513=C13- C23+ C21- C11=95-75+80-90=10B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）10(0)5（0） B1 B2 B3 B4 ai A1 3 5 1 9 A2 5 5 A3 3 4 7 bj 3 8 4 6BjxijAi换成运价表，求检验数练习 B1 B2 B3 B4 A1 2 9 10 7A2 1

29、 3 4 2 A3 3 4 2 5（）中为 ij B1 B2 B3 B4 ui A1 2 9 (3) 7 0 A2 (4) (-1) (2) 2 -5 A3 (6) 4 2 (3) -5 vj 2 9 7 7ui+vjAiBj检验数检验数 B1 B2 B3 B4 aiA1 3 6 9A2 5 0 5 A3 3 4 7 bj 3 8 4 6换成运价表，求检验数 B1 B2 B3 B4 ai A1 3 5 1 9 A2 5 5 A3 3 4 7 bj 3 8 4 6调整方案 B1 B2 B3 B4 uiA1 2 (1) (4) 7 0A2 (4) 3 (3) 2 -5A3 (5) 4 2 (2)

30、-4 vj 2 8 6 7Aiui+vjBj由于所有检验数都不为负，所以上述方案为最优方案。表上作业法计算中的问题表上作业法计算中的问题n无穷多最优解n退化B1B2B3产量A1907095280A2806575150销量100150180退化情况之一确定初始方案B1B2B3产量A1280A2150150销量100150180B1B2B3产量A1280A20150150销量100150180 B1 B2 B3 B4 aiA1 3 6 9A2 5 0 5 A3 3 4 7 bj 3 8 4 6换成运价表，求检验数 B1 B2 B3 B4 ai A1 3 5 1 9 A2 5 5 A3 3 4 7

31、bj 3 8 4 6调整方案退化情况2产大于销的运输问题njjmiiba11njmixnjbxmiaxtsijjmiijinjij, 1, 10, 2 , 1, 2 , 1. .11njiinijmiaxx11, 2 , 1njjmiinbab111虚拟销地虚拟销地n+1，销量销量miCin, 1, 01产大于销的运输问题B1B2B3B4需求量A1569440A2948560A31075350拥有量25204045B1B2B3B4B5需求量A15694040A29485060A310753050拥有量2520404520例产大于销的运输问题B1B2B3B4B5需求量A1250015040A20

32、200202060A3004010050拥有量2520404520销大于产的运输问题njmixnjbxmiaxtsijjmiijinjij, 1, 10, 2 , 1, 2 , 1. .11没有可行解njjmiiba11销大于产的运输问题njjmiiba11njmixnjbxmiaxtsijjmiijinjij, 1, 10, 2 , 1, 2 , 1. .11miinjjnaba111虚拟产地虚拟产地n+1，产量产量miCin, 1, 01允许缺货销大于产的运输问题njjmiiba111njmixnjbxmiaxtsijjmiijinjij, 1, 10, 2 , 11, 2 , 1. .1

33、11 B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 250 200 200 B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销量 250 200 200 1、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。2、当我们用图解法求解线性规划问题时，也必须首先把线性规划模型化为标准型。3、如果一个线性规划问题无可行解，则它必然没有最优解。4、如果线性规划问题的可行域是无界的，则该问题一定无有限最优解。5、线性规划问题的基是一个非奇异方阵。6、线性规划问题的可行域是个凸集。7、我们用单纯型

34、法来求解线性规划问题，一般首先要把这个线性规划模型化为标准型。8、在极小化线性规划问题中，对于某个基本可行解，如果所有检验数均不小于零，且人工变量为0，则这个基本可行解是最优解。9、对一对对偶的线性规划问题而言，若其中一个有有限的最优解，则另一个也有最优解，且相应的目标函数值相等。判断题10、在运输问题中，只要给出一组含（m + n 1）个非零的 xij ,且满足 =ai ， =bj,就可以作为一个初始基可行解。 n1 xijjn1 xiji11、对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为个 。12、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

35、 13. 已知yi为线性规划的对偶问题的最优解，若yi0，说明在最优生产计划中第i种资源已完全耗尽 14. 已知yi为线性规划的对偶问题的最优解，若Yi=0，说明在最优生产计划中第i种资源一定有剩余 。cmn15。若某种资源的影子价格等于k，在其他条件不变的情况下，当该资源增加5个单位，相应的目标函数值将增加5k.16.表上作业法实质上就是求解运输问题的单纯形法。17。如果某线性规划的对偶问题有可行解，那么该线性规划一定也有可行解。 在运输方案中出现退化现象，是指数字格的数目（A） 等于m+n （B） 大于m+n-1（C） 小于m+n-1（D） 等于m+n-1 下列线性规划问题的对偶形式是什么

36、？请写 出。 Min Z = 2 X1 + 2 X2 +4 X3s.t. 2 X1 + 3 X2 + 5 X3 2 3 X1 + X2 + 7 X3 3 X1 + 4 X2 + 6 X3 5 X1 0 ，X2 0 ，X3 0 某农户年初承包了40亩土地，并备有生产专用资金2500元。该户劳动力情况为：春夏季4000工时，秋冬季3500工时。若有闲余工时则将为别的农户帮工，其收入为：春夏季0.50元/工时,秋冬季0.40元/工时。该户承包的地块只适宜种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养奶牛和鸡。每年每头奶牛需投资400元，每只鸡需投资3元。每头奶牛需

37、用地1.5亩种植饲草,并占用劳动力:春夏季50工时及秋冬季100工时，每年净收入400元。每只鸡只占用劳动力：春夏季0.3工时和秋冬季0.6工时,每年净收入10元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需要的劳动力及收入情况如下表所示。问该农户应如何拟订经营方案才能使当年净收入最大？（只需建立该问题的线性规划模型。） 大豆玉米小麦春夏季需工时/亩203510秋冬季需工时/亩507540净收入（元/亩）508040 某厂拟生产甲、乙两种适销产品，每件利润分别为3，5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产

38、能力1，2工时；两种产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3，4工时。A、B、C三个车间每天可用于生产这两种产品的工时分别为8，12，36，应如何安排生产这两种产品才能获利最多？1建立线性规划模型。2用单纯形法求出最优解。3试着确定C车间每天拥有的工时总量在什么范围变化，最优基不变。 BjCijAiB1B2B3aiA141210A234312bj8105 求解下表所示运输问题 例1:石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000t，运价如下表。由于需

39、大于供，经院研究决定一区需要量可减少0200t，二区必须满足需求量，三区供应量不少于1700t，试求总费用为最低的调运方案。 一区 二区 三区 产量 山西盂县 1.65 1.70 1.75 4000 河北临城 1.60 1.65 1.70 1500 需要量 3000 1000 2000 运输问题的应用运输问题的应用 解:根据题意，作出产销平衡与运价表： 取 M 代表一个很大的正数，其作用是强迫相应的 x31、x33、x34取值为0。 一区 一区 二区 三区 三区 产量 山西盂县 1.65 1.65 1.70 1.75 1.75 4000 河北临城 1.60 1.60 1.65 1.70 1.7

40、0 1500 假想生产点 M 0 M M 0 500 需要量 2800 200 1000 1700 300 运输问题的应用运输问题的应用 例2:设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。 1 2 3 4 产量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 运输问题的应用运输问题的应用 1 2 3 4 产量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 2

41、3 - 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 解：解：根据题意，作出产销平衡与运价表:最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 1 1” 2 3 4 4” 产 量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 销 量 30 20 70 30 10 50 生产

42、与储存问题生产与储存问题 例例3:3:某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。生产能力（台） 单位成本（万元）一季度2510.8二季度3511.1三季度3011.0四季度1011.33.3.运输问题的应用运输问题的应用生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23

43、 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10交货：x11 = 10 解：解： 设设 x xijij为第为第 i i 季度生产的第季度生产的第 j j 季度交货的柴油机数目，那么应满足：季度交货的柴油机数目，那么应满足：3.3.运输问题的应用运输问题的应用 目标函数：目标函数：Min f = 10.8 xMin f = 10.8 x11 11 +10.95 x+10.95 x12 12 +11.1 x+11.1 x13 13 +11.25 x+11.25 x1414 +11.1 x +11.1 x22 22 +11.25 x

44、+11.25 x23 23 +11.4 x+11.4 x24 24 +11.0 x +11.0 x33 33 +11.15 x+11.15 x34 34 +11.3 x +11.3 x4444 第 一 季 度 第 二 季 度 第 三 季 度 第 四 季 度 D 产 量 第 一 季 度 10.80 10.95 11.10 11.2 0 25 第 二 季 度 M 11.10 11.25 11.40 0 35 第 三 季 度 M M 11.00 11.15 0 30 第 四 季 度 M M M 11.30 0 10 销 量 10 15 25 20 30 3.运输问题的应用把第把第 i i 季度生产的

45、柴油机数目看作第季度生产的柴油机数目看作第 i i 个生产厂的产个生产厂的产量；把第量；把第 j j 季度交货的柴油机数目看作第季度交货的柴油机数目看作第 j j 个销售点个销售点的销量；成本加储存、维护等费用看作运费。可构造下的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：列产销平衡问题：生产能力（台） 单位成本（万元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3Min f = 10.8 xMin f = 10.8 x11 11 +10.95 x+10.95 x12 12 +11.1 x+11.1 x13 13 +11.25 x+11.25 x14

46、14 +11.1 x+11.1 x22 22 +11.25 x+11.25 x23 23 +11.4 x+11.4 x24 24 +11.0 x +11.0 x33 33 +11.15 x+11.15 x34 34 +11.3 x+11.3 x44 44 第 一 季 度 第 二 季 度 第 三 季 度 第 四 季 度 D 产 量 第 一 季 度 10.80 10.95 11.10 11.2 0 25 第 二 季 度 M 11.10 11.25 11.40 0 35 第 三 季 度 M M 11.00 11.15 0 30 第 四 季 度 M M M 11.30 0 10 销 量 10 15 2

47、5 20 30 生产与储存问题 例4:光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表： 正常生产能力（台） 加班生产能力（台） 销量（台） 单台费用（万元）1月份6010104152月份501075143月份902011513.54月份10040160135月份10040103136月份80407013.53.3.运输问题的应用运输问题的应用n已知上年末库存103台绣花机，n如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,n每台机器每月的平均仓储费、维护费为0.2万。n在7-8月份销售淡季，全厂停

48、产1个月，因此在6月份完成销售合同后还要留出库存80台。n加班生产机器每台增加成本1万元。n问应如何安排1-6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？3 3 运输问题的应用运输问题的应用 解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地。 1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，把它列为第0行； 3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台； 4）1-6表示1-6月份正常生产情况， 16表示1-6月份加班生产

49、情况。3.3.运输问题的应用运输问题的应用产销平衡与运价表： 1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5 16.7 6.9 17.1 0 10 2 M 14 14.3 14.5 14.7 14.9 0 50 2 M 15 15.3 15.5 15.7 15.9 0 10 3 M M 13.5 13.8 14.0 14.2 0 90 3 M M 14.5 14.8 15.0 15.2 0 20 4 M

50、M M 13.0 13.3 13.5 0 100 4 M M M 14.0 14.3 14.5 0 40 5 M M M M 13.0 13.3 0 100 5 M M M M 14.0 14.3 0 40 6 M M M M M 13.5 0 80 6 M M M M M 14.5 0 40 销量 104 75 115 160 103 150 36 - 3.3.运输问题的应用运输问题的应用 例5:腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产450台,广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连

51、距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？ 三、转运问题三、转运问题: :原运输问题上增加若干转运站。运输方式有：产地 转运站、转运站 销地、产地 产地、产地 销地、销地 转运站、销地 产地等。3.3.运输问题的应用运输问题的应用图中 1广州、2大连、3上海、4天津 5南京、6济南、7南昌、8青岛3.3.运输问题的应用运输问题的应用 解：解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件：对产地（发点） i ：输入量 - 输出量 = 产量 对转运站（中转点）： 输入量 - 输出量 = 0 对销地（收点） j ： 输入量 - 输出量 = 销量3.3.运输问题的应用运输问题的应用约束条件： s.t. x13+x14 600 (广州分厂供应量限制） x23+x24+x28 450 (