解：由于该运输问题的产量大于销量，产销不平衡，可增加一个假想的销地B5，其销量为: (5+2+6)-(3+3+2+2)=3,运费为0 ，使之变为产销平衡问题，如表3.9-1所示：
表3.9-1 销地 B1 B2 B3 B4 B5 产量 产地 A1 A2 A3 销量 3 2 4 3 7 4 3 3 6 3 8 2 4 2 5 2 0 0 0 3 5 2 6 13 由最小元素法求得上述运输问题的初始基可行解，如下表3.9-2 。
表3.9-2
销地 产地 B1 3 0 3 3 2 4 B2 7 4 3 3 0 3 B3 6 3 8 2 表3.9-3
2 B4 4 2 5 2 B5 0 0 0 3 产量 5 A1 A2 A3 销量 2 2 3 6 13 销地 产地 B1 3 0 3 2 4 0 B2 7 4 （-2） 3 3 2 B3 6 3 B4 4 （1） 2 5 B5 0 （-4） 0 （-3） 0 3 产量 5 A1 A2 A3 销量 （-2） 2 8 （6） 2 2 （5） 3 3 （6） 3 2 6 13 在表3.9-2中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.9-3 。 在表3.9-3中，由于有多个检验数均小于 0 ，选最小的检验数σ15 = -4 ，其位置上的变量x15为换入变量，找到闭回路为：x15 x35 x32 x12 ，由于3与0的最小数为0，故调整量为0，选x12为换出变量，调整后的解如表3.9-4所示 。在表3.9-4中，使用闭回路法计算各非基变量的检验数（括号内的数）。
在表3.9-4中，只有检验数σ23小于 0 ，选其位置上的变量x23为换入变量，找闭回路为：x23 x13 x11 x21 ，由于2与0的最小数为0，故调整量为0，选x21为换出变量，调整后的解如表3.9-5所示 ，使用闭回路法计算各非基变量的检验数（括号内的数）。
运筹学习题答案及注释 第6页
表3.9-4
销地 产地 B1 3 0 3 2 4 B2 7 （4） 2 4 （2） 3 3 B3 6 3 B4 4 （1） 0 2 5 B5 0 0 （1） 0 3 产量 5 A1 A2 A3 销量 （-2） 2 8 （2） 2 表3.9-5
2 （1） 3 3 （2） 3 2 6 13 销地 产地 B1 3 3 2 （2） 4 B2 7 （4） 2 4 B3 6 3 8 （2） 2 2 B4 4 （-1） 0 2 5 （0） 2 3 B5 0 0 （3） 0 3 产量 5 A1 A2 A3 销量 （4） 0 3 3 2 （1） 3 3 6 13 在表3.9-5中，由于只有检验数σ14小于 0 ，选其位置上的变量x14为换入变量，找到闭回路为：x14 x24 x23 x13 ，由于2与2的最小数为2，故调整量为2，选x13为换出变量，调整后的解如表3.9-6所示 。在表3.9-6中，使用闭回路法计算各非基变量的检验数（括号内的数）。
表3.9-6 销地 产地 B1 3 3 2 （2） 4 B2 7 （4） 4 B3 6 （1） 2 3 8 （3） 2 0 B4 4 2 5 （1） 2 0 3 B5 0 0 （2） 0 3 产量 5 A1 A2 A3 销量 （3） 2 3 3 2 （1） 3 3 6 13 在表3.9-6中，由于所有检验数均大于等于 0 ，所以表3.9-6中的解就是最优解，其最小运价为 32 。
3.10 某市有三个面粉厂，它们供给三个面食加工厂所需面粉。各面粉厂的产量、各面食加
运筹学习题答案及注释 第7页
工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均示于表3-35中。假定在第1，2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。
表3-35
食品厂 1 2 3 面粉厂产量 面粉厂 Ⅰ Ⅱ Ⅲ 食品厂需量 3 4 8 15 10 11 11 25 2 8 4 20 20 30 20 解：由题意知：该问题为产量大于需量的不平衡问题，可以假想一个虚拟的面食加工厂4，其需量为（20+30+20）-（15+25+20）= 10 ，从而变为平衡问题。又该题求总效益最大的面粉分配方案，可以转化为下面运输问题，运往虚拟的面食加工厂4的运费为 0 ，如下表。
表3.10-1
食品厂 面粉厂 Ⅰ Ⅱ Ⅲ 食品厂需量 1 -9 -8 -4 15 2 -6 -5 -5 25 3 -9 -3 -7 20 4 0 0 0 10 面粉厂产量 20 30 20 70 则容易得知，其总效益就是总运费的相反数。 由最小元素法求得上述运输问题的初始基可行解，并使用闭回路法计算非基变量的检验数（括号内），得表3.10-2 。
表3.10-2
食品厂 1 2 3 4 面粉厂产量 面粉厂 Ⅰ 0 15 -9 -8 -4 15 -6 -9 -3 (5) -7 0 (1) 0 (0) 0 20 (0) 20 -5 -5 Ⅱ 30 Ⅲ 食品厂需量 (4) 10 15 25 (1) 10 20 10 20 70 在表3.10-2中，由于所有检验数均大于等于 0 ，所以表3.10-2中的解就是最优解，其最小运费为 425 。即面粉分配计划为：面粉厂Ⅰ的面粉20单位运往面食加工厂3，面粉厂Ⅱ的面粉15单位运往面食加工厂1，面粉厂Ⅱ的面粉15单位运往面食加工厂2，面粉厂Ⅲ的面粉10单位运往面食加工厂2，面粉厂Ⅲ的面粉10单位不向外运输，其总效益最大，为425元 。
3.11 在表3-36示出一个运输问题及它的一个解，试问：
运筹学习题答案及注释 第8页
（1）表中给出的解是否为最优解？请用位势法进行检验。
（2）若价值系数c24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。 （3）若所有价值系数均增加1，最优解是否改变？为什么？ （4）若所有价值系数均乘以2，最优解是否改变？为什么？
（5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。
表3-36
销地 产地 B1 8 8 4 1 3 B2 1 2 7 5 5 B3 4 6 5 6 3 3 B4 6 1 1 3 产量 8 A1 A2 A3 销量 2 1 10 4 22 解：（1）设i 行的位势ui ，第i 列的位势vi ，则可以得到下列方程组：
u1?v2?1u1?v3?4u2?v1?1u2?v4?1u3?v3?5u3?v4?1令u1 = 0，得：v2 = 1 ，v3 = 4 ， u3 = 1 ，v4 = 0，u2 = 1 ，v1 = 0。 由公式σij = cij – ( ui + vj ) ,可以计算出各非基变量的检验数（括号内）。如表3.11-1 ：
表3.11-1
销地 产地
B1 8 4 (4) 5 1 3 (2) 8 B2 1 2 (0) 7 3 B3 4 6 B4 6 (6) 1 1 3 产量 8 A1 A2 A3 销量 (1) 2 5 6 1 10 (5) 3 5 4 22 在表3.11-1中，由于所有检验数均大于等于 0 ，所以表3.11-1中的解是最优解，其目标函数值（最小运价）为43
（2）若价值系数c24由1变为3，并使用闭回路法计算非基变量的检验数（括号内），得表3.11-2 。
在表3.11-2中，由于有多个检验数小于 0 ，所以该解不是最优解。选最小的检验数
运筹学习题答案及注释 第9页
σ22 = -2 ，其位置上的变量x22为换入变量，找到闭回路为：x22 x24 x34 x33 x13 x12 ，由于2、3与5的最小数为2，故调整量为2，选x24为换出变量，调整后的解如表3.11-3所示 。在表3.11-3中，使用闭回路法计算各非基变量的检验数（括号内）。
表3.11-3
销地 产量 B1 B2 B3 B4 产地 A1 A2 A3 销量 8 4 1 2 7 5 4 6 (1) 5 6 3 3 6 (6) 3 (2) 1 (4) 3 1 3 (1) 8 2 8 10 (5) 1 5 4 22 在表3.11-3中，由于所有检验数均大于等于 0 ，所以表3.11-3中的解是最优解。
（3）若所有价值系数均增加1，最优解是否改变？为什么？
若所有价值系数均增加1，最优解不改变。因为若所有价值系数均增加1，使用闭回路法计算检验数时，在计算式子中，其偶数顶点增加的价值系数恰好被奇数顶点增加的价值系数抵消，因而检验数不变，故最优解不变。
（4）若所有价值系数均乘以2，最优解是否改变？为什么？
若所有价值系数均乘以2，最优解不改变。因为若所有价值系数均乘以2，使用闭回路法计算检验数时，在计算式子中，其偶数顶点的价值系数、奇数顶点增加的价值系数均乘以2，因而检验数变为原来的2倍，但检验数的正负没有变，故最优解不变。 （5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。
该运输问题的对偶问题为：
max z??8u1?10u2?4u3?8v1?5v2?6v3?3v4
?u1?v1?4?u?v?12?1?u1?v3?4??u1?v4?6?u2?v1?1??u2?v2?2?st. ?u2?v3?6
?u?v?14?2?u3?v1?3??u3?v2?7?u3?v3?5??u3?v4?1??u1,u2,u3,v1,v2,v3,v4的符号不限其对偶问题的最优解为：（0，1，1，0，1，4，0），其目标函数值为43 。
运筹学习题答案及注释 第10页
u1+v2 = 1 u1+v3 = 4 u2+v1 = 1 u2+v4 = 1 u3+v3 = 5 u3+v4= 1
运筹学习题答案及注释第11页