Chapter43运输问题

1、第四章运输问题第四章运输问题Transportation ProblemTransportation Problem24.3.2 4.3.2 最优解的判别最优解的判别1. 最优性检验最优性检验njmiPBCcijBijij, 2 , 1, 2 , 101 充要条件充要条件l由于基变量的检验数由于基变量的检验数ij= 0,只需确定非基变量只需确定非基变量的检验数！的检验数！l确定非基变量检验数的常用方法主要是：确定非基变量检验数的常用方法主要是：l位势法位势法利用对偶变量利用对偶变量3(2) 平衡运输问题的对偶问题平衡运输问题的对偶问题ji,xn,jbxm,iax. t . sxcZMinijm

2、ijijinjijminjijij和和对所有的对所有的021211111n,jmiv ,ucvu. t . svbuaWMaxjiijjinjjjmiii212111，无符号限制无符号限制由于由于r(A)=m+n-1，独立的约束方程独立的约束方程个数为个数为m+n-1;而变量个数为而变量个数为m+n，则其中有一个自则其中有一个自由变量由变量 njjmiiba114jiijnmijjijjBijijvucvvvuuucYPcPBcc011021211 由于对偶变量的个数为由于对偶变量的个数为m+n，而系数矩阵的秩为，而系数矩阵的秩为m+n-1，我们可以通过设定自由变量的值得到所有，我们可以通过设

3、定自由变量的值得到所有对偶变量。对偶变量。jivu ,位势位势5基变量基变量(xij)的检验数为的检验数为： ij= cij - (ui + vj)= 0得得m+n-1个方程，令某个个方程，令某个ui (或或vj)=0，可解出，可解出m+n个个ui 和和vj；由此得非基变量的检验数；由此得非基变量的检验数:非基变量非基变量(xij)的检验数为的检验数为: ij= cij - (ui + vj) 6 销销 产产B B1 1B B2 2B B3 3B B4 4产量产量A A1 1A A2 2A A3 33 36 6 4 4 1 13 33 37 74 49 9销量销量3 36 65 56 6例例4

4、.1在例在例4.1的由最小元素法得到的初始解中的由最小元素法得到的初始解中x23，x34，x21，x32，x13，x14是基变量。是基变量。最小元素法最小元素法方案方案7 基变量基变量 检验数检验数 x23 c23-(u2+v3)=0 即即 2-(u2+v3)=0 x34 c34-(u3+v4)=0 5-(u3+v4)=0 x21 c21-(u2+v1)=0 1-(u2+v1)=0 x32 c32-(u3+v2)=0 4-(u3+v2)=0 x13 c13-(u1+v3)=0 3-(u1+v3)=0 x14 c14-(u1+v4)=0 10-(u1+v4)=0 从以上从以上7个方程中个方程中,

5、由由u1=0可求得可求得 u2= -1, u3= -5, v1=2, v2=9, v3=3, v4=10因非基变量的检验数因非基变量的检验数 )(jiijijvuc 这就可以从已知的这就可以从已知的ui，vj值中求得。这些值中求得。这些计算可在表格计算可在表格中进行中进行。 8销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633（2）位势法）位势法 令令v1=0, 由由c21=1= u2 +v1，得，得 u2=19B1B2B3B4ui311310A11928A274105A3v

6、j 0 1 1 2最小元素法最小元素法（2）位势法）位势法基变量基变量10 0 1 1 28-3 7位势表位势表)(jiijijvuc 检验数检验数(空格中数字为空格中数字为ui + vj )11B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7检验数表检验数表121-1101224= -10，当前方案，当前方案 不是最优方案。不是最优方案。12举例举例 位势法位势法v1v26857495210376ABCu1u2u3v3v4123414813136613选择含基变量最多的行或列，令相应的选择含基变量最多的行或列，令相应的u或或v为零。为零。v1v26

7、857495210376ABCu1u2=0u3v3v41234148131366(2) (2) 位势法位势法(1)14v1=c21- u2=8-0=8, v2=c22- u2=4-0=4, v3=c23- u2=2-0=2(2) (2) 位势法位势法(2)15u1=c11-v1=6-8=-2, u3 =c33- v3=10-2=8(2) (2) 位势法位势法(3)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4123414813136616v4=c34-u3=6-8=-2(2) (2) 位势法位势法(4)v1=8v2=46857495210376ABCu1

8、=-2u2=0u3=8v3=2v4=-2123414813136617(2) (2) 位势法位势法(5)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366512 =c12-(u1+ v2) =7-(-2+4)=5185(2) (2) 位势法位势法(6)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366513 =c13-(u1+ v3) =5-(-2+2)=519(2) (2) 位势法位势法(7)75v1=8v2=46857495210376ABCu1=-2u2

9、=0u3=8v3=2v4=-21234148131366514 =c14-(u1+ v4) =3-(-2-2)=720(2) (2) 位势法位势法(8)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366524 =c24-(u2+ v4) =7-(0-2)=9921(2) (2) 位势法位势法(9)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-212341481313665931 =c31-(u3+ v1) =5-(8+8)=-11-1122(2) (2) 位势法位势法(10)

10、75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-2123414813136659-1132 =c32-(u3+ v2) =9-(8+4)=-3-3234.3.3 运输问题的基变换运输问题的基变换闭回路调整法闭回路调整法l选择检验数绝对值最大的非基变量选择检验数绝对值最大的非基变量为进基变量为进基变量( (存在多个时任选一个存在多个时任选一个) )确定进基变量确定进基变量确定出基变量确定出基变量l选择包含进基变量的闭回路上距进选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基基变量奇次的变量中运量最小的基变量为出基变量。变量为出基变量。运量

11、调整运量调整 奇次的基变量奇次的基变量闭回路上距进基变量为闭回路上距进基变量为:xxminxttl 奇奇次次的的基基变变量量闭闭回回路路上上距距进进基基变变量量为为偶偶次次的的基基变变量量闭闭回回路路上上距距进进基基变变量量为为：离离基基变变量量：进进基基变变量量；lktlktktljljxxxxxxxxx重复上述步骤直至所有检验数大于零，即获得最优解。重复上述步骤直至所有检验数大于零，即获得最优解。24B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7检验数表检验数表121-1101224= -10，当前方案，当前方案 不是最优方案。不是最优方案。例

12、例325闭回路调整法改进方案（基可行解）闭回路调整法改进方案（基可行解）j , i)(minpq ij= 0, 方案最优方案最优28表中带括号的数字是非基变量的检验数，表中带括号的数字是非基变量的检验数，可知可知所有检验数都大于等于零（基变量的检所有检验数都大于等于零（基变量的检验数都等于零），此解是最优解验数都等于零），此解是最优解，这时最小，这时最小总运费为总运费为85元，具体的运输方案如下：元，具体的运输方案如下：A1分分厂运厂运5吨到销售公司吨到销售公司B3，运，运2吨给销售公司吨给销售公司B4；A2分厂运分厂运3吨给销售公司吨给销售公司B1，运，运1吨给销售吨给销售公司公司B4；A3

13、分厂运分厂运6吨给销售公司吨给销售公司B2，运，运3吨吨给销售公司给销售公司B4。运输问题举例说明表上作业法举例说明表上作业法例例4.4、某部门三个工厂生产同一产品的产量、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表：四个销售点的销量及单位运价如下表：41228543961111104814121482210163214321AAABBBB销量产量销地产地3034333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4 , 3 , 2 , 1; 3 , 2, 1, 01412148221016

14、342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij解：该运输问题的数学模型为：解：该运输问题的数学模型为：运输问题第一步：确定初始基可行解第一步：确定初始基可行解 最小元素法、伏格尔法最小元素法、伏格尔法 最小元素法思路：最小元素法思路： 从单价中最小运价确定供应从单价中最小运价确定供应量，逐步次小，直至得到量，逐步次小，直至得到m+n-1个数字格。个数字格。运输问题最小元素法举例41228543961111104814121482210163214321AAABBBB销量产量销地产地822

15、010100614868000060运输问题 例例1用伏格尔法得到的初始基可行解用伏格尔法得到的初始基可行解4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地48148122244685149228114412 z目标函数值目标函数值用最小元素法用最小元素法求出的目标函求出的目标函数数z=246运输问题第三步：解的调整第三步：解的调整41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468-1（-2）（-2）（+2）（+2）运输问题 调整后的解为：调整后的解为：41

16、228543961111104814121482210163214321AAABBBB销量产量销地产地8212144822091122246244689211441251428, 0zij此时的解为最优解。此时的解为最优解。有无穷多有无穷多最优解最优解运输问题几点说明： 当检验数为负的变量超过两个，选择最小者当检验数为负的变量超过两个，选择最小者对应的变量换入；对应的变量换入； 在最优解的表中，若有检验数在最优解的表中，若有检验数=0，则该运输，则该运输问题有无穷多最优解；问题有无穷多最优解； 迭代过程中，若某一格填数时需同时划去一迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。

17、为保证行和一列，此时出现退化。为保证m+n-1个个非空格，需在上述的行或列中填入数字非空格，需在上述的行或列中填入数字0。37已知已知 运输问题供需表和运价表如下，求最优调运输问题供需表和运价表如下，求最优调运方案。运方案。课堂练习课堂练习销销 产产 B1 B2 B3 B4 产产量量 2 11 3 4 A1 7 10 3 5 9 A2 5 7 8 1 2 A3 7 销销量量 2 3 4 6 3822136857495210376ABC142719121312341481313669755-11-3确定进基变量确定进基变量选择检验数绝对值最大的非基变量为进基变量选择检验数绝对值最大的非基变量为进

18、基变量3922136857495210376ABC142719121312341481313669755-11-3确定闭回路确定闭回路4022136857495210376ABC142719121312341481313669755-11-366 , 8min,min3321xxxl确定离基变量确定离基变量4122136857495210376ABC1427191213123414213131209755-3调整运量调整运量6x31=6, x21=8-6=2, x23=6+6=124222136857495210376ABC142719121312341421313126-2-4558进一步优

19、化进一步优化(0)114322136857495210376ABC142719121312341421313126-2-4558进一步优化进一步优化(1)11x13 进基，进基， x34离基。离基。4422136857495210376ABC14271912131234121313121924558进一步优化进一步优化(2)11所有非基变量的检验数均大于零，即为最优解。所有非基变量的检验数均大于零，即为最优解。454.4 产销不平衡的运输问题及其求产销不平衡的运输问题及其求解方法解方法 在很多运输问题中，总产量不等于在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作总销量。这时，为

20、了使用前述表上作业法求解，就需将产销不平衡运输问业法求解，就需将产销不平衡运输问题化为产销平衡运输问题。题化为产销平衡运输问题。 运输问题4.4.1 产大于销的运输问题产大于销的运输问题 若总产量大于总销量，即若总产量大于总销量，即njjmiiba11minjjinbab111令假象销地的销量为：令假象销地的销量为：运输问题 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111原产大于销平衡问题的数学模型原产大于销平衡问题的数学模型运输问题修改后产大于销平衡问题的数学模型修改后产大于销平衡问题的数学模型 1,2,1,2,1

21、,01,2,1,2,1,min111111nnjmixnnjbxmiaxxczijjmiijinjijminjijij运输问题 这里，这里，松弛变量松弛变量 xi n+1 可以视为从可以视为从产地产地 A i 运往销地运往销地 Bn+1 的运输量，由的运输量，由于实际并不运送，它们的于实际并不运送，它们的运费为运费为 ci n+1=0 i= 1,2,m。于是，这个运输问题就转化成了一个于是，这个运输问题就转化成了一个产销平衡的问题产销平衡的问题。运输问题决策变量 表示由 到 的物品数量。iAiBijx1211211222221211112111121nnmnmnmmmnnnnnnbbbbxxx

22、xAxxxxAxxxxABBBB销地产地销量产量maaa2112c11cnc121c22cnc21mc2mcmnc000注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。运输问题例例4.5 某公司从两个产地某公司从两个产地A1、A2将物品将物品运往三个销地运往三个销地B1、B2、B3，各产地的产，各产地的产量、各销地的销量和各产地运往各销地量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？何调运可使总运输费用最小？ B1 B2 B3 产产量量 A1 6 4 6 300 A2 6 5 5 300 销销量量

23、150 150 200 运输问题 解：增加一个虚设的销地运输费用为解：增加一个虚设的销地运输费用为0 0 B1 B2 B3 B4 产量 A1 6 4 6 0 300 A2 6 5 5 0 300 销量 150 150 200 100 运输问题 若总销量大于总产量，即若总销量大于总产量，即njjmiiba11miinjjmaba111令假象产地的销量为：令假象产地的销量为：4.4.2 销大于产的运输问题销大于产的运输问题仿照上述类似处理。仿照上述类似处理。运输问题 这里，这里，松弛变量松弛变量 x m+1,j 可以视为从可以视为从产地产地 A m+1 运往销地运往销地 B j 的运输量，由的运输

24、量，由于实际并不运送，它们的于实际并不运送，它们的运费为运费为 c m+1,j = 0 j = 1,2,n。于是，这个运于是，这个运输问题就转化成了一个产销平衡的问输问题就转化成了一个产销平衡的问题。题。运输问题 例例4.6:某公司从两个产地某公司从两个产地A1、A2将物品将物品运往三个销地运往三个销地B1、B2、B3，各产地的产，各产地的产量、各销地的销量和各产地运往各销地量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？何调运可使总运输费用最小？ B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5

25、 300 销量 250 200 200 运输问题 解：增加一个虚设的产地运输费用为解：增加一个虚设的产地运输费用为0 0 B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销量 250 200 200 57例例4.74.7：有三个化肥厂供应四个地区的农用化肥。等量有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。分析总运费最节省的化肥调运方案。 需求地区需求地区化肥厂化肥厂B1B2B3B4产量（万吨）产量（万吨）A11613221

26、750A21413191560A3192023-50最低需求（万吨）最低需求（万吨）最高需求（万吨）最高需求（万吨）3050707003010不限不限运价：万元运价：万元/ /万吨万吨58分析：分析： 这是一个产销不平衡的运输问题，总产量为这是一个产销不平衡的运输问题，总产量为160万吨，万吨，四个地区的最低需求为四个地区的最低需求为110万吨，最高需求为无限。根据现万吨，最高需求为无限。根据现有产量，地区有产量，地区B4每年最多能分配到每年最多能分配到60万吨，这样最高总需万吨，这样最高总需求为求为210万吨，大于产量。为了求得平衡，在产销平衡表中万吨，大于产量。为了求得平衡，在产销平衡表中

27、增加一个虚拟的化肥厂增加一个虚拟的化肥厂D ，其年产量为，其年产量为50万吨。由于各个万吨。由于各个地区的需要量包含两部分，如地区地区的需要量包含两部分，如地区B1，其中，其中30万吨是最低万吨是最低需求，故不能由虚拟的化肥厂需求，故不能由虚拟的化肥厂D供给，令其相应的运输价供给，令其相应的运输价格为格为M（任意大正数），而另一部分（任意大正数），而另一部分20万吨满足或不满足万吨满足或不满足均可，因此可以由虚拟的化肥厂均可，因此可以由虚拟的化肥厂D供给，并令其相应的运供给，并令其相应的运输价格为输价格为0（没有发生的运输）。对凡是需求分两种情况的（没有发生的运输）。对凡是需求分两种情况的地区

28、，实际上可按照两个地区看待。这样可以建立这个问地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表题的产销平衡表59产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 产量产量销量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M60产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj13501430132019015102330M200200300130141

29、9154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M1603020203061产销平衡表产销平衡表 A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M1662产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+