3运输问题268487 811.pptVIP

（1，7）闭回路。 （1，7）闭回路。 （1，7）闭回路。 （1，7）闭回路。 （1，7）闭回路。 （1，7）闭回路。 总运费=480000（元） 计算检验数。 最优方案如下， 最小运费=480000元 有非基变量的检验数=0，有无穷多组解，另外一个解如下： 非平衡的运输问题： Min S=? ? cijxij i j ? xij =ai (i=1,2…..m) j ? xij =bj (j=1,2……n) i ? ai ≠ ? bj i j xij ? 0(i=1,2…..m; j=1,2……n) 非平衡运输问题可以具体的分成两类，即总产量大于总销量；总产量小于总销量。而这两类问题都可以通过添加变量的方式化为平衡运输问题。具体的方法是： 总产量大于总销量的，添加一个虚拟的销售点， 其销售量等于总产量与总销量的差。各个产地到该销售点的运价均为零。 总产量小于总销量的，添加一个虚拟的产地，其产量等于总销量与总产量的差。该产地到各个销售点的运价均为零。 例3-2 总产量大于总销量的一个运输问题： 运输价格 收点 B1 B2 B3 发量 发点 A1 6 5 3 4 A2 4 4 7 6 A3 7 6 5 3 收量 2 4 3 添加一个虚拟的收货点B4，该问题变成平衡的运输问题。（注意B4所在列的运价） 运输价格 收点 B1 B2 B3 B4 发量 发点 A1 6 5 3 0 4 A2 4 4 7 0 6 A3 7 6 5 0 3 收量 2 4 3 4 13 按平衡运输问题的计算方法，可以计算出最优方案： 运输价格 收点 B1 B2 B3 B4 发量 发点 A1 3 1 4 A2 2 4 0 6 A3 3 3 收量 2 4 3 4 13 2 4 1 2 2 3 请自行写出求解过程 退化的运输问题： 对一个有m个产地和n个销地的运输问题，若存在一组初始方案，运量不为零的位置小于m+n-1，则称之为退化的。 例如： B1 B2 B3 发量 A1 5 3 6 4 A2 4 7 4 6 A3 6 5 2 3 4 2 7 13 该问题有一组可行解如下，其运量不为零的位置只有4个。这在后面求检验数的过程中将遇到麻烦。（试求检验数） B1 B2 B3 发量 A1 4 4 A2 2 4 6 A3 3 3 4 2 7 13 但只要在某些格子中填入运量0，使填写运量的位置数=m+n-1，就可以求出检验数了。例如： B1 B2 B3 发量 A1 4 [-5] [1] 4 A2 0 2 4 6 A3 [4] [0] 3 3 4 2 7 13 之后可以做出最优解。如下： B1 B2 B3 发量 A1 2 2 [1] 4 A2 2 [5] 4 6 A3 [4] [5] 3 3 4 2 7 13 注意：运输问题在求初始方案时，以及求出检验数后调整过程中，均可能出现退化现象。 练习： P123 5.3 5.4(1)(2)(都求目标函数最小值） * 2。对偶变量法(位势法) 非基变量xij的检验数cij-zij—对偶变量法(1) （1）计算基变量位势 令: v4=0 对偶变量法(2) u3+v4=c34 u3=6 c34 对偶变量法(3) u3+v3=c33 v3=4 c33 对偶变量法(4) u2+v3=c23 u2=-2 c23 对偶变量法(5) u2+v2=c22 v2=6 c22 对偶变量法(6) u2+v1=c21 v1=10 c21 对偶变量法(7) u1+v1=c11 u1=-4 c11 （1）计算非基变量位势（检验数） 对偶变量法(8) c12-z12= c12–(u1+v2)=7-(-4)-6=5 5 对偶变量法(9) 5 5 c13-z13= c13–(u1+v3)=5-(-4)-4=5 对偶变量法(10) 7 5 5 对偶变量法(11) 9 5 5 7 对偶变量法(12) -11 5 5 7 9 对偶变量法(13) -3 5 5 7 9 -11 调整运量，优化方案 1。确定进基变量，确定离基变量 3。调整运量 选择进基变量,确定离基变量 x31进基,（检验数负的最小者） min{x21,x33}=min{8,6}=6, x33离基（小步前进） -3 5 5 7 9 -11 调整运量,重新计算检验数,确定进基、离基变量 x14进基（检验数正的最大者） min{x11,x34}=min{14,13}=13, x34离基 11 5 5 -4 -2 8 调整运量, 重新计算检验数 所有cij -