运筹学习题答案(第三章)

1、 3.1 与一般线性规划的数学模型相比，运输问题与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征的数学模型具有什么特征? 答：答： 1、运输问题一定有有限最优解。、运输问题一定有有限最优解。 2、约束系数只取、约束系数只取0或或1。 3、约束系数矩阵的每列有两个、约束系数矩阵的每列有两个1， 而且只有两个而且只有两个1。前。前m行中有一个行中有一个1，或，或n行中有一个行中有一个1。 4、对于产销平衡的运输问题，所有的约束都取、对于产销平衡的运输问题，所有的约束都取等式。等式。 3.2 运输问题的基可行解应满足什么条件？将其运输问题的基可行解应满足什么条件？将其填入运输表中时有什么

2、体现？并说明在迭代计算过程填入运输表中时有什么体现？并说明在迭代计算过程中对它的要求。中对它的要求。 解：运输问题基可行解的要求是基变量的个数等解：运输问题基可行解的要求是基变量的个数等于于m+n-1。填入表格时体现在数字格的个数也应该等。填入表格时体现在数字格的个数也应该等于于m+n-1。在迭代过程中，要始终保持数字格的个数。在迭代过程中，要始终保持数字格的个数不变不变。 3.3 试对给出运输问题初始基可行解的西北角法、试对给出运输问题初始基可行解的西北角法、最小元素法和最小元素法和Vogel法进行比较，分析给出的解之质量法进行比较，分析给出的解之质量不同的原因。不同的原因。 解：用西北角法

3、可以快速得到初始解，但是由于解：用西北角法可以快速得到初始解，但是由于没有考虑运输价格，效果不好；最小元素法从最小的没有考虑运输价格，效果不好；最小元素法从最小的运输价格入手，一开始效果很好，但是到了最后因选运输价格入手，一开始效果很好，但是到了最后因选择余地较少效果不好；择余地较少效果不好； Vogel法从产地和销地运价的法从产地和销地运价的级差来考虑问题，总体效果很好，但是方法较复杂。级差来考虑问题，总体效果很好，但是方法较复杂。 3.4 详细说明用位势法详细说明用位势法(对偶变量法对偶变量法)求检验数的原求检验数的原理。理。 解：原问题的检验数也可以利用对偶变量来计解：原问题的检验数也可

4、以利用对偶变量来计算算 ：njmivucjiijij,2, 1;,2, 1)( 其中，其中，ui和和vj就是原问题约束对应的对偶变量。由于就是原问题约束对应的对偶变量。由于原问题的基变量的个数等于原问题的基变量的个数等于m+n-1。所以相应的检验。所以相应的检验数就应该等于数就应该等于0。即有：。即有：njmivucjiij,2, 1;,2, 10)( 由于方程有由于方程有m+n-1个，个， 而变量有而变量有m+n个。所以上个。所以上面的方程有无穷多个解。任意确定一个变量的值都可面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解。然后再利用这个解就可以求以通过方程求出一个解。然

5、后再利用这个解就可以求出非基变量的检验数了。出非基变量的检验数了。 3.5 用表上作业法求解运输问题时，在什么情况用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解时应如何处理？下会出现退化解？当出现退化解时应如何处理？ 解：当数字格的数量小于解：当数字格的数量小于m+n-1时，相应的解就时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的是退化解。如果出现了退化解，首先找到同时划去的行和列，然后在同时划去的行和列中的某个空格中填行和列，然后在同时划去的行和列中的某个空格中填入数字入数字0。只要数字格的数量保持在。只要数字格的数量保持在m+n-1个的水平即个的水平即可。

6、可。 3.6 一般线性规划问题具备什么特征才能将其转一般线性规划问题具备什么特征才能将其转化为运输问题求解，请举例说明。化为运输问题求解，请举例说明。 解：如果线性规划问题有解：如果线性规划问题有“供供”和和“需需”的关系，的关系，并且有相应的并且有相应的“费用费用”，就可以考虑将线性规划问题，就可以考虑将线性规划问题转成运输问题求解。例如，生产满足需求的问题。转成运输问题求解。例如，生产满足需求的问题。 3.7 试判断表试判断表3-30和表和表3-31中给出的调运方案可中给出的调运方案可否作为表上作业法迭代时的基可行解否作为表上作业法迭代时的基可行解?为什么为什么? 答：都不是。数字格的数量

7、不等于答：都不是。数字格的数量不等于m+n-1。表表3-30销地销地产地产地B1B2B3B4产量产量A1015 15A2 151025A35 5销量销量5151510 表表3-31销地销地产地产地B1B2B3B4B5产量产量A1150 250 400A2 200300 500A3 250 50300A490210 300A5 8020100销量销量24041055033070 3.8 表表3-32和表和表3-33分别给出了各产地和各销地分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。用表上作业法求最优解。

8、表表3-32销地销地产地产地B1B2B3B4产量A145 13 468A26 1252 08A3373 51 14销量销量656320表表3-33销地销地产地产地B1B2B3B4产量A193 3873A21 492 453A35765 25销量销量132511 3.9 试求出表试求出表3-34给出的产销不平衡运输问题的给出的产销不平衡运输问题的最优解。最优解。 表表3-34销地销地产地产地B1B2B3B4产量A137645A224322A343856销量销量3322 习题习题3.9的解答的解答销地销地产地产地B1B2B3B4B5产量A13 3762 405A2242 3202A343 3853

9、 06销量销量33223 3.10 某市有三个面粉厂，它们供给三个面食加工某市有三个面粉厂，它们供给三个面食加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均表示于表价，均表示于表3-35中。假定在第中。假定在第1，2和和3面食加工厂面食加工厂制作单位面粉食品的利润分别为制作单位面粉食品的利润分别为12元、元、16元和元和11元，元，试确定使总效益最大的面粉分配计划试确定使总效益最大的面粉分配计划(假定面粉厂和面假定面粉厂和面食加工厂都属于同一个主管单

10、位食加工厂都属于同一个主管单位)。 表表3-35食品厂食品厂面粉厂面粉厂123产量产量310220411830811420销量销量152520 习题习题3.10的解答的解答食品厂食品厂面粉厂面粉厂1234产量31020 202015 45 11810 030820 114020销量销量15252010 3.11 表表3-36示出一个运输问题及它的一个解：示出一个运输问题及它的一个解：表表3-36销地销地产地产地B1B2B3B4产量A145 13 468A2 8 1262 110A317351 14销量销量8 56322 试问：试问： (1)表中给出的解是否为最优解？请用位势法进行表中给出的解是

11、否为最优解？请用位势法进行检验。检验。 答：是最优解。答：是最优解。 (2)如价值系数如价值系数c24由由1变为变为3，所给的解是否仍为最，所给的解是否仍为最优解？若不是，请求出最优解。优解？若不是，请求出最优解。 答：原来的解不是最优解。新的最优解是：答：原来的解不是最优解。新的最优解是： x12=3,x13=5,x21=8,x22=2,x33=1,x34=3， 其他变量为其他变量为0 。 (3)若所有价值系数均增加若所有价值系数均增加1，最优解是否改变？，最优解是否改变？为什么为什么? 答：不会改变。因为检验数不变。答：不会改变。因为检验数不变。 (4)若所有价值系数均乘以若所有价值系数均

12、乘以2，最优解是否改变？，最优解是否改变？为什么为什么? 答：最优解不变。因为检验数不变。答：最优解不变。因为检验数不变。 (5)写出该运输问题的对偶问题，并给出其对偶问写出该运输问题的对偶问题，并给出其对偶问题的最优解。题的最优解。1,5,2, 1,0,0, 1,2, 1;,2, 1,2, 1;,2, 1max432132111vvvvuuunjmivunjmicvuvbuaZjiijjinjjjmiii最优解是：无约束解：对偶问题如下： 3.12 1，2，3三个城市每年需分别供应电力三个城市每年需分别供应电力320，250和和350单位，由单位，由I，两个电站提供，它们的最大供两个电站提供

13、，它们的最大供电量分别为电量分别为400个单位和个单位和450个单位，单位费用如表个单位，单位费用如表337所示。由于需要量大于可供量，决定城市所示。由于需要量大于可供量，决定城市1的供应量的供应量可减少可减少030单位，城市单位，城市2的供应量不变，城市的供应量不变，城市3的供应的供应量不能少于量不能少于270单位，试求总费用最低的分配方案单位，试求总费用最低的分配方案(将将可供电量用完可供电量用完)。表表3-37 城市城市电站电站123151822212516 习题习题3.123.12的解答的解答 城市城市电站电站城市城市1-11-1城市城市1-21-2城市城市2 2城市城市3-13-1城

14、市城市3-23-2产量产量150 1515250 182222400140 212125270 1640 16450M30 0MM40 070销量销量2903025027080 3.13 试写出本章例试写出本章例5转运问题的数学模型。转运问题的数学模型。 解：已知解：已知 a a1 11010，a a2 24040，a a3 3 = a= a4 4 = a= a5 5 = 0= 0 b b1 1= b= b2 2= b= b3 30 0，b b4 43030，b b5 520 Q20 Q5050 下面就是相应的模型：下面就是相应的模型： MIN Z= 4 X(1,1)+ 5 X(1,2)+ 3

15、 X(1,3)+ 2 X(1,4)+ 100X(1, 5) + 5 X(2,1)+ X(2,2)+2 X(2,3)+100 X(2,4) + 4 X(2, 5) + 3 X(3,1)+2X(3,2)+3 X(3,3)+5 X(3, 4) + 5 X( 3, 5) + 2 X(4,1)+100X(4,2)+5 X(4,3)+ 3 X(4,4)+6 X( 4, 5) + 100X(5,1)+4X(5,2)+5X(5,3)+6 X( 5, 4) +5 X( 5, 5) 2-X(1,1) + X(1,2) + X(1,3) + X(1,4) + X(1,5) = 10 3 X(2,1) - X(2,2) + X(2,3) + X(2,4) + X(2,5) = 40 4 X(3,1) + X(3,2) - X(3,3) + X(3,4) + X(3,5) = 0 5 X(4,1) + X(4,2) + X(4,3) - X(4,4) + X(4,5) = 0 6 X(5,1) + X(5,2) + X(5,3) + X(5,4) - X(5,5) = 0