建模： 运输问题

1、运输问题运输问题运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外第第3章章 运输问题运输问题第第1节节 运输问题的数学模型运输问题的数学模型第第2节节 表上作业法表上作业法第第3节节 产销不平衡的运输问题及其求解产销不平衡的运输问题及其求解方法方法第第4节节 应用举例应用举例第第5节节 Lingo程序求解运输问题程序求解运输问题引例引例某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产量产量A1646200A2655300销量销量15015020

2、0运费表引例引例解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到数学模型：0200150150300200556646min231322122111232221131211232221131211ijxxxxxxxxxxxxxxxxxxxz系数矩阵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 1m个行约束n个列约束第第1节节 运输问题的数学模型运输问题的数学模型系数矩阵系数矩阵A的特点：的特点：1、约束条件左边所有系数都是、约束条件左边所有系数都是0或或1，而且每一列中恰好只有，而

3、且每一列中恰好只有两个元素是两个元素是1，其他元素，其他元素都是都是0。列向量为：。列向量为：行第行第jmiPij11共有共有mn个个Pij。2、前、前m个每行有个每行有n个个1（其余都是（其余都是0），从第），从第m+1行到第行到第n行，行，每行有每行有m个个1（其余都是（其余都是0）。）。第第1节节 运输问题的数学模型运输问题的数学模型n已知有已知有m个生产地点个生产地点Ai,i=1,2,，m。可供应某种。可供应某种物资，其供应量物资，其供应量(产量产量)分别为分别为ai，i=1，2，m，n有有n个销地个销地Bj，j=1,2,n，其需要量分别为，其需要量分别为bj，j=1,2,n，n从从A

4、i到到Bj运输单位物资的运输单位物资的运价运价(单价单价)为为cij，这些数，这些数据可汇总于产销平衡表和单位运价表中，见表据可汇总于产销平衡表和单位运价表中，见表3-1，表表3-2。有时可把这两表合二为一。有时可把这两表合二为一。第第1节节 运输问题的数学模型运输问题的数学模型 销地销地 产地产地 12n产量产量1c11c12c1na12c21c22c2na2 mcm1cm2cmnam销量销量b1b2bn运输问题的产销表第第1节节 运输问题的数学模型运输问题的数学模型n若用若用x xijij表示从表示从A Ai i到到B Bj j的运量，那么在产销平衡的条件下，要求得的运量，那么在产销平衡的

5、条件下，要求得总运费最小总运费最小的的调运方案，调运方案，数学模型数学模型 0)23(,2, 1)13(,2, 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxczn这就是运输问题的数学模型。这就是运输问题的数学模型。n它包含它包含mn个变量，个变量，(m+n)个约束方程。个约束方程。n其系数矩阵的结构比较松散，且特殊。其系数矩阵的结构比较松散，且特殊。第第1节节 运输问题的数学模型运输问题的数学模型行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111211第第1节节 运输问题的数学模型运输问题的

6、数学模型n系数矩阵系数矩阵A的特点：的特点：n1、约束条件左边所有系数都是、约束条件左边所有系数都是0或或1，而且，而且每一列中恰好只有每一列中恰好只有两个元素是两个元素是1，其他元素，其他元素都是都是0。列向量为：。列向量为：行第行第jmiPij.1.1.共有共有mn个个Pij。第第1节节 运输问题的数学模型运输问题的数学模型n2、前、前m个每行有个每行有n个个1（其余都是（其余都是0），从第），从第m+1行到第行到第n行，每行有行，每行有m个个1（其余都是（其余都是0）。）。行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111

7、211第第1节节 运输问题的数学模型运输问题的数学模型系数矩阵中对应于变量系数矩阵中对应于变量x xijij的的系数向量系数向量P Pijij，其分量中除其分量中除第第i i个个和第和第m+jm+j个个为为1 1以外，其余的以外，其余的都为零都为零。即。即P Pijij=(0, ,1,0,0,1,0,0)=(0, ,1,0,0,1,0,0)T T=e=ei i+e+em+jm+j对对产销平衡产销平衡的运输问题，由于有以下关系式的运输问题，由于有以下关系式存在：存在：njminjmiimiijnjijjaxxb111111第第1节节 运输问题的数学模型运输问题的数学模型njminjmiimiij

8、njijjaxxb111111所以，该模型最多只有所以，该模型最多只有m+n-1m+n-1个独立约束方程，个独立约束方程，由于有以上特征，求解运输问题时，由于有以上特征，求解运输问题时，可用比较简便的计算方法，可用比较简便的计算方法，习惯上称为习惯上称为表上作业法表上作业法。第第2 2节节 表上作业法表上作业法n表上作业法表上作业法是单纯形法在求解运输问题时的是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。一种简化方法，其实质是单纯形法。n但具体计算和术语有所不同。可归纳为：但具体计算和术语有所不同。可归纳为：n(1)(1)找出找出初始基可行解初始基可行解。即在。即在(m(mn)n

9、)产销平产销平衡表上衡表上（用用西北角法西北角法、最小元素法最小元素法，Vogel法法）给出给出m+n-1个数字，称为个数字，称为数字格数字格。n它们就是初始它们就是初始基变量基变量的取值。的取值。第第2 2节节 表上作业法表上作业法n(2) (2) 求各求各非基变量非基变量的检验数，即在表上计算的检验数，即在表上计算空格空格的的检验数检验数，判别是否达到最优解。，判别是否达到最优解。n如已是最优解，则停止计算，否则转到下一如已是最优解，则停止计算，否则转到下一步。步。n(3) (3) 确定换入变量和换出变量，找出新的基确定换入变量和换出变量，找出新的基可行解。在表上用可行解。在表上用闭回路法

10、调整闭回路法调整。n(4) 重复重复(2)，(3)直到得到最优解为止。直到得到最优解为止。第第2 2节节 表上作业法表上作业法给出初始调运方案最优性检验调整上述方案停是否相应于单纯形表的初始基本可行解第第2 2节节 表上作业法表上作业法n例1 某公司经销甲产品。它下设三个加工厂。某公司经销甲产品。它下设三个加工厂。n每日的产量分别是：每日的产量分别是：A1为为7吨，吨，A2为为4吨，吨，A3为为9吨。吨。n该公司把这些产品分别运往四个销售点。该公司把这些产品分别运往四个销售点。n各销售点每日销量为：各销售点每日销量为：B1为为3吨，吨，B2为为6吨，吨，B3为为5吨，吨，B4为为6吨。吨。n已

11、知从各工厂到各销售点的单位产品的运价为表已知从各工厂到各销售点的单位产品的运价为表3-3所示。所示。n问该公司应如何调运产品，在满足各销点的需要量问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。的前提下，使总运费为最少。第第2 2节节 表上作业法表上作业法n解 先作出这问题的先作出这问题的产销平衡表产销平衡表和和单位运价表单位运价表，见，见表表3-3，表，表3-4表表3-3 单位运价表单位运价表销地 加 工 厂 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 第第2 2节节 表上作业法表上作业法表3-4 产销平衡表 销 地

12、加工厂 B1 B2 B3 B4 产量 A1 A2 A3 7 4 9 销量 3 6 5 6 第第2 2节节 表上作业法表上作业法用线性规划法处理此问题。设由产地用线性规划法处理此问题。设由产地i到销地到销地j的运量为的运量为xij，模，模型为：型为：min z= 3x11+11x12+3x13+10 x14 +x21 +9x22 +2x23 +8x24 +7x31 +4x32+10 x33+5x34 x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14

13、+x24+x34=6 xij0 (i=1,2,3; j=1,2,3,4)n运输问题一般用表上作业法求解，需建立表格模型：运输问题一般用表上作业法求解，需建立表格模型：第第2 2节节 表上作业法表上作业法 销 地产地 B1 B2 B3 B4 产 量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9销量 3 6 5 6202.1 2.1 确定初始基可行解确定初始基可行解这与一般线性规划问题不同。产销平衡的运输问题总是存在可行解。因有minjjidba11必存在必存在x xijij00，i=1i=1，m m，j=1j=1，n n这就是这就是可行解可行解。又因又因0

14、x0 xijijmin(amin(aj j，b bj j) )故故运输问题必存在最优解。运输问题必存在最优解。2.1 2.1 确定初始基可行解确定初始基可行解n确定初始基可行解的方法很多，确定初始基可行解的方法很多，n有西北角法，最小元素法和伏格尔有西北角法，最小元素法和伏格尔(Vogel)(Vogel)法。法。n一般希望的方法是既简便，又尽可能接近最优解。一般希望的方法是既简便，又尽可能接近最优解。n下面介绍伏格尔下面介绍伏格尔(Vogel)(Vogel)法：法：1. 1. 伏格尔法伏格尔法伏格尔法考虑到，一产地的产品假如不能按最伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑

15、小运费就近供应，就考虑次小运费次小运费，这就有，这就有一个一个差额差额。差额越大，说明不能按最小运费调运时，运费差额越大，说明不能按最小运费调运时，运费增加越多。增加越多。因而对差额最大处，就应当采用因而对差额最大处，就应当采用最小运费最小运费调运。调运。伏格尔法的步骤伏格尔法的步骤n1.计算每行、列两个计算每行、列两个最小运价的差最小运价的差；n2.找出找出最大差所在的行或列最大差所在的行或列；n3.找出该行或列的最小运价，确定供求关系，找出该行或列的最小运价，确定供求关系，最大量最大量的供应的供应 ；n4.划掉已满足要求的行或划掉已满足要求的行或 (和和) 列，列，如果需要同时划去如果需要

16、同时划去行和列，必须要在行和列，必须要在该行或列的任意位置填个该行或列的任意位置填个“0”；n5.在剩余的运价表中重复在剩余的运价表中重复14步，直到得到初始基可步，直到得到初始基可行解。行解。销地销地产地产地B1B2B3B4产产量量行差行差A1311310 7007A219284116A37410 5912 销量销量3656列列差差251321263333152122 销地销地产地产地B1B2B3B4产量产量A1527A2314A3639销量销量3656运量表（vogel法）1. 1. 伏格尔法伏格尔法n伏格尔法的步骤是：伏格尔法的步骤是：n第一步第一步：在表：在表3-3中分别计算出中分别计

17、算出各行和各列各行和各列的的最小运费最小运费和和次最小运费次最小运费的的差额差额，并填入该，并填入该表的表的最右列最右列和和最下行最下行，见表，见表3-10。销 地 加工厂 B1 B2 B3 B4 行差额 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 1 列差额 2 5 1 3 1. 1. 伏格尔法伏格尔法n第二步第二步：从行或列：从行或列差额差额中中选出最大者选出最大者，选择，选择它所在行或列中的它所在行或列中的最小元素最小元素。在表。在表3-10中中B2列是最大差额所在列。列是最大差额所在列。B2列中最小元素为列中最小元素为4，可确定可确定A3的产品先供应

18、的产品先供应B2的需要。得表的需要。得表3-11销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 6 7 4 9 销量 3 6 5 6 1. 1. 伏格尔法伏格尔法n同时将运价表中的同时将运价表中的B B2 2列数字划去。列数字划去。如表如表3-123-12所示。所示。销 地 加工厂 B1 B2 B3 B4 行差额 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差额 2 1 3 1. 1. 伏格尔法伏格尔法n第三步：对表第三步：对表3-123-12中未划去的元素再分别计算出各中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，

19、并填入行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给该表的最右列和最下行。重复第一、二步。直到给出出初始解初始解为止。用此法给出例为止。用此法给出例1 1的初始解列于表的初始解列于表3-3-1313。销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 1. 1. 伏格尔法伏格尔法n由以上可见：由以上可见：n伏格尔法同最小元素法除在确定供求关系的伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。原则上不同外，其余步骤相同。n伏格尔法给出的初始解比用最小元素法给出伏格尔法

20、给出的初始解比用最小元素法给出的初始解的初始解更接近最优解更接近最优解。n本例用伏格尔法给出的初始解就是本例用伏格尔法给出的初始解就是最优解最优解。2-2 最优解的判别最优解的判别n2-2 最优解的判别最优解的判别n判别的方法是计算判别的方法是计算空格空格(非基变量非基变量)的检验数的检验数cij-CBB-1Pij，i,jN。n因运输问题的目标函数是要求因运输问题的目标函数是要求实现最小化实现最小化，故当所有的故当所有的cij-CBB-1Pij0时，为最优解。时，为最优解。2-2 最优解的判别最优解的判别ijij0 0 （因为目标函数要求最小化）（因为目标函数要求最小化） 表格中有表格中有调运

21、量调运量的地方为的地方为基变量基变量，空格处空格处为为非基变量。非基变量。基变量的基变量的检验数检验数ijij0 0，非基变量的检验数非基变量的检验数ijij00。ijij 0 0 0 表示运费增加。表示运费增加。有两种检验方法：有两种检验方法：位势法位势法和和闭合回路法闭合回路法。1.闭回路法闭回路法n1.闭回路法闭回路法销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量 3 6 5 6 1.闭回路法闭回路法n在给出调运方案的计算表上，如表在给出调运方案的计算表上，如表3-13，从每一，从每一空格出发空格出发找一条闭回路。找一条闭回路。n

22、它是以它是以某空格为起点某空格为起点。n用用水平水平或或垂直线垂直线向前划，当向前划，当碰到一数字格碰到一数字格时可以时可以转转90后，继续前进，直到回到后，继续前进，直到回到起始空格起始空格为止。为止。n闭回路如图闭回路如图3-1的的(a),(b),(c)等所示。等所示。 1.闭回路法闭回路法n从每一空格出发从每一空格出发一定存在一定存在和可以找到和可以找到唯一的唯一的闭回路。闭回路。n因因(m+n-1)(m+n-1)个数字格个数字格( (基变量基变量) )对应的系数向对应的系数向量是一个基。量是一个基。n任一任一空格空格( (非基变量非基变量) )对应的对应的系数向量系数向量是这个是这个基

23、的基的线性组合线性组合。1.闭回路法闭回路法n闭回路法计算检验数的经济解释为：闭回路法计算检验数的经济解释为：n在已给出初始解的表在已给出初始解的表3-9中，中， 可从可从任一空格任一空格出发，如出发，如(A1，B1)，若让若让A1的产品调运的产品调运1吨给吨给B1。n为了保持产销平衡，就要依次作调整：为了保持产销平衡，就要依次作调整：在在(A1，B3)处减少处减少1吨，吨，(A2，B3)处增加处增加1吨，吨，(A2，B1)处减少处减少1吨，即构成了以吨，即构成了以(A1，B1)空格为起点空格为起点，其他为，其他为数字格的闭回路数字格的闭回路。1.闭回路法闭回路法n如表如表3-14中的虚线所示

24、。在这表中闭回路各顶点中的虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价。所在格的右上角数字是单位运价。B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633B1B2B3B4产量A17A24A39销量3656313463（1）（1）（1）（1） 计算如下：空格处（计算如下：空格处（ A1 B1 ） (13) (1)3 (12)(1)11 此数即为该空格处的检验数。此数即为该空格处的检验数。121231311ccccij1.闭回路法闭回路法n可见这个调整方案使运费增加可见这个调整方案使运费增加(+1)(+1)3+(-1)3+(-1)3+

25、(+1)3+(+1)2+(-1)2+(-1)=1(=1(元元) )这表明若这样调整运量将增加运费。这表明若这样调整运量将增加运费。n将将“1”这个数填入这个数填入(A1，B1)格，这就是检验数。格，这就是检验数。n按以上所述，可找出所有空格的检验数，按以上所述，可找出所有空格的检验数，见表见表3-15。B1B2B3B4产量A17A24A39销量36563136312424510113234141212ccccB1B2B3B4产量A17A24A39销量36563136312-141103281413232424ccccB1B2B3B4产量产量A17A24A39销量销量365631363121-1

26、41451032932331413232222ccccccB1B2B3B4产量A17A24A39销量365631363121-1124125103103414133333ccccB1B2B3B4产量A17A24A39销量365631363121-11210410510321734141323212231cccccc1.闭回路法闭回路法n按以上所述，找出所有空格的检验数，按以上所述，找出所有空格的检验数，见表见表3-15。B1B2B3B4产量A17A24A39销量365600000121-112100检验数表检验数表1.闭回路法闭回路法当检验数还存在负数存在负数时，说明原方案不是最优解，要继续改

27、进。ijij 0 0 0 表示运费增加。表示运费增加。2. 位势法位势法n用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多时，这种计算很繁琐。n下面介绍较为简便的方法位势法。n设u1，u2，um;v1，v2，vn是对应运输问题的m+n个约束条件的对偶变量。nB是含有一个人工变量xa的(m+n)(m+n)初始基矩阵。n人工变量xa在目标函数中的系数ca=0，从线性规划的对偶理论可知。2. 位势法位势法),;,(21211nmBvvvuuuBCjinmijBnmBvuvvvuuuPBCvvvuuuBC11),;,(),;,(21211212112. 位势法位势法)(),.,.,.,.,

28、(111jiijijnjmiijijBijijvucPvvvuuucPBCc由单纯形法得知所有由单纯形法得知所有基变量基变量的的检验数等于检验数等于0。即即 Bji, 0)(jiijvuc因为因为C CB BB B-1-1P Pijij=u=ui i+v+vj j, ,于是检验数于是检验数jijCPYX, 0则若2. 位势法位势法n因因非基变量非基变量的检验数的检验数Njivucjiijij,).(这就可以从已知的这就可以从已知的ui，vj值中求得。值中求得。这些计算可在表格中进行。这些计算可在表格中进行。 B1B2B3B4A1310u1A212u2A345u3v1v2v3v4B1B2B3B4

29、A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj) 按按ij=cij(ui+vj) 计算检验数，计算检验数，并以并以ij0 检验，或用检验，或用(ui+vj) cij 0 检验。检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中还有表中还有

30、负数负数，说明还未得到最优解，说明还未得到最优解，应继续调整。应继续调整。ij2.3 改进的方法-闭回路调整法n当在表中空格处出现当在表中空格处出现负检验数负检验数时，表明未得最优解。时，表明未得最优解。n若有两个和两个以上的负检验数时，若有两个和两个以上的负检验数时，n一般选其中一般选其中最小的负检验数最小的负检验数，以它对应的，以它对应的空格空格为为调调入格。入格。即以它对应的即以它对应的非基变量非基变量为为换入变量换入变量。n由表由表3-183-18得得(2(2，4)4)为调入格为调入格。n以此格为出发点，作一闭回路，如表以此格为出发点，作一闭回路，如表3-193-19所示。所示。2.3

31、 改进的方法-闭回路调整法B1B2B3B4产量A17A24A39销量3656313463（1）（1）（1）（1）2.3 改进的方法-闭回路调整法n(2(2，4)4)格的格的调入量调入量是选择闭回路上具有是选择闭回路上具有n(-1)(-1)的数字格的数字格中的中的最小者最小者。即。即=min(1,3)=1=min(1,3)=1( (其原理与单纯形法中按其原理与单纯形法中按规划来确定规划来确定换出变量相同换出变量相同) )。n然后按闭回路上的正、负号，加入和减去此然后按闭回路上的正、负号，加入和减去此值，得到调整方案，如表值，得到调整方案，如表3-203-20所示。所示。B1B2B3B4产量A15

32、27A2314A3639销量6563销量9A34A27A1产量B4B3B2B1313463（1）（1）（1）（1）B1B2B3B4A10200A20210A390120经检验经检验所有所有ijij00得到最优解，得到最优解，最小运费为最小运费为8585元。元。v4v3v2v1u354A3u281A2u1103A1B4B3B2B11039355242A328171A2010393A1B4B3B2B1(ui+vj)cij2.42.4 表上作业法计算中的问题表上作业法计算中的问题n1. 1. 无穷多最优解无穷多最优解n2. 2. 退化退化2.42.4 表上作业法计算中的问题表上作业法计算中的问题n1

33、. 1. 无穷多最优解无穷多最优解n在本章在本章2.12.1节中提到，产销平衡的运输问题必定存节中提到，产销平衡的运输问题必定存在最优解。在最优解。n那么有唯一最优解还是无穷多最优解那么有唯一最优解还是无穷多最优解? ?n判别依据与第判别依据与第1 1章章3.33.3节讲述的相同。节讲述的相同。n即某个即某个非基变量非基变量( (空格空格) )的检验数为的检验数为0 0时时，该问题有，该问题有无穷多最优解。无穷多最优解。n表表3-213-21空格空格(1(1，1)1)的的检验数是检验数是0 0，n表明例表明例1 1有无穷多最优解。有无穷多最优解。2.42.4 表上作业法计算中的问题表上作业法计

34、算中的问题B1B2B3B4A10200A20210A390120n空格空格(1(1，1)1)的检验数是的检验数是0 0，表明有无穷多最优解。，表明有无穷多最优解。2.42.4 表上作业法计算中的问题表上作业法计算中的问题n可在表可在表3-203-20中以中以(1(1，1)1)为调入格为调入格，作闭回路，作闭回路(1(1，1)1)+ +-(1-(1，4)4)- -(2-(2，4)4)+ +-(2-(2，1)1)- -(1-(1，1)1)+ +。确定确定=min(2,3)=2=min(2,3)=2。经调整后得到经调整后得到另一最优解另一最优解，见表，见表3-223-22。B1B2B3B4产量A15

35、27A2314A3639销量3656+2+2+2+2-2-2-2-22.42.4 表上作业法计算中的问题表上作业法计算中的问题n表表3-223-22销地 加 工 厂 B1 B2 B3 B4 产量 A1 A2 A3 2 1 6 5 3 3 7 4 9 销 量 3 6 5 6 2.42.4 表上作业法计算中的问题表上作业法计算中的问题n2. 2. 退化退化用表上作业法求解运输问题当出现退化时，用表上作业法求解运输问题当出现退化时，在相应的格中一定要在相应的格中一定要填一个填一个0，以表示此格，以表示此格为数字格。有以下为数字格。有以下两种情况两种情况：2.42.4 表上作业法计算中的问题表上作业法

36、计算中的问题n(1) 当确定初始解的各供需关系时，若出现当确定初始解的各供需关系时，若出现Ai处的余量处的余量等于等于Bj处的需量处的需量。n需在单位运价表上相应地要划去一行和一列。需在单位运价表上相应地要划去一行和一列。n为了使在产销平衡表上有为了使在产销平衡表上有(m+n-1)个数字格。个数字格。这时需要添一个这时需要添一个“0”。2.42.4 表上作业法计算中的问题表上作业法计算中的问题n(2) (2) 在用闭回路法调整时，在闭回路上出现两个和在用闭回路法调整时，在闭回路上出现两个和两个以上的具有两个以上的具有(-1)(-1)标记标记的的相等的最小值相等的最小值。n这时只能选择这时只能选

37、择其中一个其中一个作为作为调入格调入格。n经调整后，得到经调整后，得到退化解退化解。n另一个数字格必须填入一个另一个数字格必须填入一个0 0，表明它是，表明它是基变量基变量。n当出现退化解后，并作改进调整时，可能在某闭回当出现退化解后，并作改进调整时，可能在某闭回路上有标记为路上有标记为(-1)(-1)的取值为的取值为0 0的数字格，这时应取的数字格，这时应取调整量调整量=0=0。第第3节节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法n但是实际问题中产销往往是不平衡的。但是实际问题中产销往往是不平衡的。n就需要把产销不平衡的问题化成产销平衡的问题。就需要把产销不平衡的问题

38、化成产销平衡的问题。n当产大于销，当产大于销，就要考虑多余的物资在哪一个产地就就要考虑多余的物资在哪一个产地就地储存的问题。地储存的问题。n这就需要增加一个假想的销地这就需要增加一个假想的销地j=n+1(j=n+1(实际上是储存实际上是储存) )n该销地总需要量为该销地总需要量为njjmiiba11产量销量在单位运价表中从各产地到假想销地的在单位运价表中从各产地到假想销地的单位运价为单位运价为0 0，这就转化成一个产销平衡的运输问题这就转化成一个产销平衡的运输问题第第3节节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法当销大于产时，可以在产销平衡表中增加一个假想当销大于产时

39、，可以在产销平衡表中增加一个假想的的产地产地i=m+1i=m+1，该地产量为，该地产量为njmijjab11在单位运价表上令从该假想产地到各销地的在单位运价表上令从该假想产地到各销地的运价运价为为0 0，就可以转化为一个产销平衡的运输问题。，就可以转化为一个产销平衡的运输问题。 销地销地产地产地B1B2B3B4产量产量A17A25A37销量销量2346 销地销地产地产地B1B2B3B4A121134A210359A37812表表3-33产销平衡表产销平衡表表表3-34单位运价表单位运价表例例2：求下面问题最优调运方案：求下面问题最优调运方案举例举例 销地销地产地产地B1B2B3B4产量产量A1

40、211347A2103595A378127销量销量2346举例举例解：首先化为产销平衡的运输问题。假设一个解：首先化为产销平衡的运输问题。假设一个库存地库存地B5，产销平衡表如表，产销平衡表如表3-35，其中，其中b5=19-15=4 销地销地产地产地B1B2B3B4B5产量产量A12113407A21035905A3781207销量销量23464 B1B2B3B4B5产量产量A12113407A21035905A3781207销量销量23464432533323222最小元素法最小元素法举例举例n由由Vogel法求初始调运方案法求初始调运方案 销地销地产地产地B1B2B3B4B5产量产量行差

41、行差 A12113407 2331A21035905 335A37812071111销量销量23464列列差差5522022023222245 333表3-37 Vogel法得运量表 销地销地产地产地B1B2B3B4B5产量产量A12327A2325A3437销量销量23464用位势法求表3-37是否为最优调运方案。其位势表与检验数表如表3-38和3-39表3-38 位势表 销地销地产地产地B1B2B3B4B5uiA1240A230A312vjV1=2v2=3V3=3V4=4V5=0u1=0u2=0u3=-2ijij=c=cijij(u(ui i+v+vj j)=0)=0u1+v1=2 u1+

42、v4=4 u1+v5=0 u2+v2=3 u2+v5=0 u3+v3=1 u3+v4=2 令：令： u10表3-39 销地销地产地产地B1B2B3B4B5A108000A280250A377002所有检验数都大于等于所有检验数都大于等于0，所以是最优方案。，所以是最优方案。最优值最优值fmin=22+ 43 + 33 + 41 + 23=35举例举例n例例2 2 设有三个化肥厂设有三个化肥厂(A(A，B B，C)C)供应四个地区供应四个地区(，)的农用化肥。的农用化肥。n假定等量的化肥在这些地区使用效果相同。假定等量的化肥在这些地区使用效果相同。n各化肥厂年产量，各地区年需要量及从各化肥厂到各

43、化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表各地区运送单位化肥的运价如表3-253-25所示。所示。n试求出总的运费试求出总的运费最节省的化肥调拨方案。最节省的化肥调拨方案。第第3节节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法 需求地需求地化肥厂化肥厂B1B2B3B4产量（万吨）产量（万吨）A11613221750A21413191560A319202350最低需求（万吨）最低需求（万吨）3070010最高需求（万吨）最高需求（万吨）507030不限不限表表3-253-25第第3节节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解

44、方法n解解n分析：已知总产量为分析：已知总产量为160吨，最低需求为吨，最低需求为110万吨万吨（30+70+10=110），最高需求为无限。），最高需求为无限。nB4地区最多分配地区最多分配60万吨（万吨（160-30-70=60）n最高需求为最高需求为210万吨（万吨（50+70+30+60），大于），大于产量。产量。n为了求得平衡，在产销平衡表中增加一个假想的化为了求得平衡，在产销平衡表中增加一个假想的化肥厂肥厂D，其年产量为，其年产量为50万吨（万吨（210-160）。）。第第3节节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法n对凡是需求分两种情况的地区，实际可按

45、照对凡是需求分两种情况的地区，实际可按照两个地两个地区区看待。看待。n如地区如地区，其中，其中3030万吨是最低需求，故不能由假想万吨是最低需求，故不能由假想化肥厂化肥厂D D供给，令供给，令相应运价为相应运价为M M( (任意大正数任意大正数) )，n另一部分另一部分2020万吨满足或不满足均可以，因此可以由万吨满足或不满足均可以，因此可以由假想化肥厂假想化肥厂D D供给，按前面讲的，令供给，按前面讲的，令相应运价为相应运价为0 0。n这样可以写出这个问题的产销平衡表这样可以写出这个问题的产销平衡表( (表表3-26)3-26)和单和单位运价表位运价表( (表表3-27)3-27)。第第3节

46、节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法n产销平衡表产销平衡表( (表表3-26),3-26),需 求 地 区 化工厂 产量 （万吨） A B C D 50 60 50 50 销量(万吨) 30 20 70 30 10 50 第第3节节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法需求地区 化工厂 A B C D 16 14 19 M 16 14 19 0 13 13 20 M 22 19 23 0 17 15 M M 17 15 M 0 单位运价表单位运价表( (表表3-27)3-27)由于各地区的需要量包含两部分，由于各地区的需要量包含两部分

47、，最低需求不能由假想化肥厂供给，最低需求不能由假想化肥厂供给，其余部分可以，并令运价为其余部分可以，并令运价为0。举例举例n表表3-43 最优分配表最优分配表 需求地需求地化肥厂化肥厂B1B1B2B3B4B4产量产量A116161322171750A214141319151560A319192023MM50DM0M0M050销量（万吨）销量（万吨） 3020703010502140192153100302031002030220225020557M-15M-15105030202030200举例举例n最优方案如表最优方案如表3-28所示所示需 求 地 区 化工厂 产量 （万吨） A B C D

48、 30 20 50 20 0 30 10 30 20 50 60 50 50 销量(万吨) 30 20 70 30 10 50 210 第4节 应 用 举 例n由于在变量个数相等的情况下，表上作业法由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。的计算远比单纯形法简单得多。n所以在解决实际问题时，人们常常尽可能把所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模某些线性规划的问题化为运输问题的数学模型。型。n下面介绍几个典型的例子。下面介绍几个典型的例子。第4节 应 用 举 例n例例3 某厂按合同规定须于当年每个季度末分别提某厂按合同规定须于当年每个

49、季度末分别提供供10，15，25，20台同一规格的柴油机。台同一规格的柴油机。n已知该厂各季度的生产能力及生产每台柴油机的成已知该厂各季度的生产能力及生产每台柴油机的成本如表本如表3-29所示。所示。n又如果生产出来的柴油机当季不交货的，每台每积又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用压一个季度需储存、维护等费用0.15万元。要求万元。要求在完成合同的情况下，作出使该厂全年生产在完成合同的情况下，作出使该厂全年生产(包括包括储存、维护储存、维护)费用最小的决策费用最小的决策 第4节 应 用 举 例n表表3-293-29季度 生产能力(台) 单位成本(万元) 25

50、 35 30 10 10.8 11.1 11.0 11.3 第4节 应 用 举 例n解 由于每个季度生产出来的柴油机不一定由于每个季度生产出来的柴油机不一定当季交货，所以设当季交货，所以设x xijij为第为第i i季度生产的用于季度生产的用于第第j j季度交货的柴油机数。根据合同要求，季度交货的柴油机数。根据合同要求，必须满足必须满足2025151044342414332313221211xxxxxxxxxx第4节 应 用 举 例n又每季度生产的用于当季和以后各季交货的又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故柴油机数不可能超过该季度的生产能力，故又有：又有

51、：1030352544343324232214131211xxxxxxxxxx第4节 应 用 举 例n第第i i季度生产的用于季度生产的用于j j季度交货的每台柴油机的实际季度交货的每台柴油机的实际成本成本c cijij应该是该季度应该是该季度单位成本单位成本加上加上储存、维护储存、维护等费等费用。用。c cijij的具体数值见表的具体数值见表3-303-30j i 11 10.8 10.95 11.10 11.10 11.25 11.00 11.25 11.40 11.15 11.30 第4节 应 用 举 例n设用设用a ai i表示该厂第表示该厂第i i季度的生产能力，季度的生产能力，b

52、bj j表示表示第第i i季度的合同供应量，则问题可写成：季度的合同供应量，则问题可写成：n目标函数：目标函数：n满足满足4141minijijijxcz04141ijijijjiijxbxax第4节 应 用 举 例n显然，这是一个产大于销的运输问题模型。显然，这是一个产大于销的运输问题模型。n注意到这个问题中当注意到这个问题中当ij时，时，xij=0，所以应令对应，所以应令对应的的cij=M，再加上一个假想的需求，再加上一个假想的需求D，就可以把这，就可以把这个问题变成产销平衡的运输模型，个问题变成产销平衡的运输模型，n并写出产销平衡表和单位运价表并写出产销平衡表和单位运价表(合在一起，见表

53、合在一起，见表3-31)。第4节 应 用 举 例季度销量 季度生产能力 D 生产能力 11 10.8 M M M 10.95 11.10 M M 11.10 11.25 11.00 M 11.25 11.40 11.15 11.30 0 0 0 0 25 35 30 10 销量 10 15 25 20 30 100 表表3-31第4节 应 用 举 例n经用表上作业法求解，可得多个最优方案，表经用表上作业法求解，可得多个最优方案，表3-323-32中列出最优方案之一。中列出最优方案之一。n即第即第季度生产季度生产2525台，台，1010台当季交货，台当季交货，1515台台季度季度交货；交货；季度

54、生产季度生产5 5台，用于台，用于季度交货；季度交货；季度季度生产生产3030台，其中台，其中2020台于当季交货，台于当季交货，1010台于台于季度交季度交货。货。季度生产季度生产1010台，于当季交货。台，于当季交货。n按此方案生产，该厂总的生产按此方案生产，该厂总的生产( (包括储存、维护包括储存、维护) )的的费用为费用为773773万元。万元。第4节 应 用 举 例销售季度 生产季度 D 产量 11 10 15 0 5 20 10 10 10 25 35 30 10 销量 10 15 25 20 30 100 5、用、用Lingo解运输问题解运输问题例例1. 设有三个产地的产品要销往

55、四个销地，各产地的设有三个产地的产品要销往四个销地，各产地的产量、各销地的销量及各产地运往各销地的单位运费产量、各销地的销量及各产地运往各销地的单位运费如下表，问如何调运使得总的运费最少。如下表，问如何调运使得总的运费最少。B1B2B3B4产量产量A1626730A2495325A3881521销量销量15172212解：编写Lingo程序(命名exam1.lg4)：min=6min=6* *x11+2x11+2* *x12+6x12+6* *x13+7x13+7* *x14+4x14+4* *x21+9x21+9* *x22+5x22+5* *x23+3x23+3* *x23+3x23+3* *x24+8x24+8* *x31+8x31+8* *x32+x3x32+x33+53+5* *x34;x34;x11+x12+x13+x14=30; x21+x22+x23+x24=25; x31+x32+x33+x34=21;x11+x12+x13+x14=30; x21+x22+x23+x24=25; x31+x32+x33+x34=15; x12+x22+x32=17; x13+x23+x33=