运筹学习题答案注释(第3章)

运筹学习题答案及注释第1页第3章运输问题注意：本章习题解法不唯一，有的题目，最优解也可能不唯一。3.8表3-32和表3-33分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。表3-32销地产地B1B2B3B4产量A141468A212508A337514销量656320解：由最小元素法求得上述运输问题的初始基可行解，其过程如下：表3.8-1销地产地B1B2B3B4产量A141468A212508A337514销量656320由于0为最小，所以，取3与8的最小值放在x24位置上，划去B4列，得表3.8-2表3.8-2销地产地B1B2B3B4产量A141468A2125053A337514销量6560在没画线的表格中，由于1最小，所以取6与5的最小值放在x21位置上，划去A2行，得表3.8-3在表3.8-3中的没画线的表格中，由于1最小，所以取8与5的最小值放在x12位置上，划去B2列，得表3.8-4运筹学习题答案及注释第2页在表3.8-4中没画线的表格中，由于3最小，所以取4与1的最小值放在x31位置上，划去B1列，得表3.8-5表3.8-3销地产地B1B2B3B4产量A141468A21250053A337514销量1560表3.8-4销地产地B1B2B3B4产量A1414635A21250053A337514销量1060表3.8-5销地产地B1B2B3B4产量A1414635A21250053A3375131销量0060在表3.8-5中没画线的表格中，由于4最小，所以取3与6的最小值放在x13位置上，划去A1行，得表3.8-6在表3.8-6中没画线的表格中，由于5最小，所以取3与3的最小值放在x33位置上，划去A3行和B3列，得表3.8-7，这样就得到了一个初始基可行解，如表3.8-8所示。在表3.8-8中，使用闭回路法计算非基变量的检验数（括弧内的数），得表3.8-9：运筹学习题答案及注释第3页σ11=c11-c13+c33-c31=4-4+5-3=2σ14=c14-c13+c33-c31+c21-c24=6-4+5-3+1-0=5得表3.8-6销地产地B1B2B3B4产量A14146353A21250053A3375131销量0030表3.8-7销地产地B1B2B3B4产量A14146053A21250053A33751013销量0000表3.8-8销地产地B1B2B3B4产量A14146853A21250853A33751413销量656320σ22=c22-c12+c13-c33+c31-c21=2-1+4-5+3-1=2σ23=c23-c33+c31-c21=5-5+3-1=2σ32=c32-c33+c13–c12=7-5+4-1=5σ34=c34-c24+c21–c13=1-0+1-3=-1在表3.8-9中，由于检验数σ34=-1≤0，所以表3.8-9中的解不是最优解。选x34运筹学习题答案及注释第4页为换入变量，找到闭回路为：x34x24x21x31，由于3与1的最小数为1，故调整量为1，选x31为换出变量，调整后的解如表3.8-10所示表3.8-9销地产地B1B2B3B4产量A141468(2)53(5)A2125085(2)(2)3A3375141(5)3(-1)销量656320表3.8-10销地产地B1B2B3B4产量A14146853A21250862A33751431销量656320在表3.8-10中，使用闭回路法计算各非基变量的检验数，得表3.8-11：表3.8-11销地产地B1B2B3B4产量A141468(3)53(6)A2125086(1)(1)2A337514(1)(5)31销量656320在表3.8-11中，由于所有检验数均大于等于0，所以表3.8-11中的解就是最优解，其最小运价为39。解：由最小元素法求得上述运输问题的初始基可行解，如下表3.8-21：在表3.8-21中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.8-22：运筹学习题答案及注释第5页在表3.8-22中，由于所有检验数均大于等于0，所以表3.8-22中的解就是最优解，其最小运价为31。表3-33销地产地B1B2B3B4产量A193873A249453A357625销量132511表3.8-21销地产地B1B2B3B4产量A1938733A24945312A357625005销量132511表3.8-22销地产地B1B2B3B4产量A193873(8)3(7)(2)A2494531(3)2(4)A35762500(1)5销量1325113.9试求表3-34给出的产销不平衡运输问题的最优解。表3-34销地产地B1B2B3B4产量A137645A224322A343856销量3322运筹学习题答案及注释第6页解：由于该运输问题的产量大于销量，产销不平衡，可增加一个假想的销地B5，其销量为:(5+2+6)-(3+3+2+2)=3,运费为0，使之变为产销平衡问题，如表3.9-1所示：表3.9-1销地产地B1B2B3B4B5产量A1376405A2243202A3438506销量3322313由最小元素法求得上述运输问题的初始基可行解，如下表3.9-2。表3.9-2销地产地B1B2B3B4B5产量A1376405302A224320202A343850633销量3322313表3.9-3销地产地B1B2B3B4B5产量A1376405302（1）（-4）A22432020（-2）（-2）2（-3）A3438506（5）3（6）（6）3销量3322313在表3.9-2中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.9-3。在表3.9-3中，由于有多个检验数均小于0，选最小的检验数σ15=-4，其位置上的变量x15为换入变量，找到闭回路为：x15x35x32x12，由于3与0的最小数为0，故调整量为0，选x12为换出变量，调整后的解如表3.9-4所示。在表3.9-4中，使用闭回路法计算各非基变量的检验数（括号内的数）。在表3.9-4中，只有检验数σ23小于0，选其位置上的变量x23为换入变量，找闭回路为：x23x13x11x21，由于2与0的最小数为0，故调整量为0，选x21为换出变量，调整后的解如表3.9-5所示，使用闭回路法计算各非基变量的检验数（括号内的数）。运筹学习题答案及注释第7页表3.9-4销地产地B1B2B3B4B5产量A13764053（4）2（1）0A22432020（2）（-2）2（1）A3438506（1）3（2）（2）3销量3322313表3.9-5销地产地B1B2B3B4B5产量A13764053（4）2（-1）0A2243202（2）（4）02（3）A3438506（1）3（2）（0）3销量3322313在表3.9-5中，由于只有检验数σ14小于0，选其位置上的变量x14为换入变量，找到闭回路为：x14x24x23x13，由于2与2的最小数为2，故调整量为2，选x13为换出变量，调整后的解如表3.9-6所示。在表3.9-6中，使用闭回路法计算各非基变量的检验数（括号内的数）。表3.9-6销地产地B1B2B3B4B5产量A13764053（4）（1）20A2243202（2）（3）20（2）A3438506（1）3（3）（1）3销量3322313在表3.9-6中，由于所有检验数均大于等于0，所以表3.9-6中的解就是最优解，其最小运价为32。3.10某市有三个面粉厂，它们供给三个面食加工厂所需面粉。各面粉厂的产量、各面食加运筹学习题答案及注释第8页工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均示于表3-35中。假定在第1，2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。表3-35食品厂面粉厂123面粉厂产量Ⅰ310220Ⅱ411830Ⅲ811420食品厂需量152520解：由题意知：该问题为产量大于需量的不平衡问题，可以假想一个虚拟的面食加工厂4，其需量为（20+30+20）-（15+25+20）=10，从而变为平衡问题。又该题求总效益最大的面粉分配方案，可以转化为下面运输问题，运往虚拟的面食加工厂4的运费为0，如下表。表3.10-1食品厂面粉厂1234面粉厂产量Ⅰ-9-6-9020Ⅱ-8-5-3030Ⅲ-4-5-7020食品厂需量1525201070则容易得知，其总效益就是总运费的相反数。由最小元素法求得上述运输问题的初始基可行解，并使用闭回路法计算非基变量的检验数（括号内），得表3.10-2。表3.10-2食品厂面粉厂1234面粉厂产量Ⅰ-9-6-90200(0)20(1)Ⅱ-8-5-30301515(5)(0)Ⅲ-4-5-7020(4)10(1)10食品厂需量1525201070在表3.10-2中，由于所有检验数均大于等于0，所以表3.10-2中的解就是最优解，其最小运费为425。即面粉分配计划为：面粉厂Ⅰ的面粉20单位运往面食加工厂3，面粉厂Ⅱ的面粉15单位运往面食加工厂1，面粉厂Ⅱ的面粉15单位运往面食加工厂2，面粉厂Ⅲ的面粉10单位运往面食加工厂2，面粉厂Ⅲ的面粉10单位不向外运输，其总效益最大，为425元。3.11在表3-36示出一个运输问题及它的一个解，试问：运筹学习题答案及注释第9页（1）表中给出的解是否为最优解？请用位势法进行检验。（2）若价值系数c24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？（4）若所有价值系数均乘以2，最优解是否改变？为什么？（5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。表3-36销地产地B1B2B3B4产量A14146853A212611082A33751431销量856322解：（1）设i行的位势ui，第i列的位势vi，则可以得到下列方程组：151141433342123121vuvuvuvuvuvu令u1=0，得：v2=1，v3=4，u3=1，v4=0，u2=1，v1=0。由公式σij=cij–(ui+vj),可以计算出各非基变量的检验数（括号内）。如表3.11-1：表3.11-1销地产地B1B2B3B4产量A141468(4)53(6)A21261108(0)(1)2A337514(2)(5)31销量856322在表3.11-1中，由于所有检验数均大于等于0，所以表3.11-1中的解是最优解，其目标函数值（最小运价）为43（2）若价值系数c24由1变为3，并使用闭回路法计算非基变量的检验数（括号内），得表3.11-2。在表3.11-2中，由于有多个检验数小于0，所以该解不是最优解。选最小的检验数运筹学习题答案及注释第10页σ22=-2，其位置上的变量x22为换入变量，找到闭回路为：x22x24x34x33x13x12，由于2、3与5的最小数为2，故调整量为2，选x24为换出变量，调整后的解如表3.11-3所示。在表3.11-3中，使用闭回路法计算各非基变量的检验数（括号内）。表3.11-3销地产地B1B2B3B4产量A141468(4)35(6)A212631082(1)(2)A337514(1)(5)13销量856322在表3.11-3中，由于所有检验数均大于等于0，所以表3.11-3中的解是最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？若所有价值系数均增加1，最优解不改变。因为若所有价值系数均增加1，使用闭回路法计算检验数时，在计算式子中，其偶数顶点增加的价值系数恰好被奇数顶点增加的价值系数抵消，因而检验数不变，故最优解不变。（4）若所有价值系数均乘以2，最优解是否改变？为什么？若所有价值系数均乘以2，最优解不改变。因为若所有价值系数均乘以2，使用闭回路法计算检验数时，在计算式子中，其偶数顶点的价值系数、奇数顶点增加的价值系数均乘以2，因而检验