文档介绍：运筹学教程(第二版)习题解答
第三章习题解答
与一般线性规划的数学模型相比,运输问题的数学模型具有什么特征?
答:
1、运输问题一定有有限最优解。
2、约束系数只取0或1。
3、约束系数矩阵的每列有两个1, 而且只有两个1。前m行中有一个1,或n行中有一个1。
4、对于产销平衡的运输问题,所有的约束都取等式。
运输问题的基可行解应满足什么条件?将其填入运输表中时有什么体现?并说明在迭代计算过程中对它的要求。
解:运输问题基可行解的要求是基变量的个数等于m+n-1。填入表格时体现在数字格的个数也应该等于m+n-1。在迭代过程中,要始终保持数字格的个数不变。
第三章习题解答
试对给出运输问题初始基可行解的西北角法、最小元素法和Vogel法进行比较,分析给出的解之质量不同的原因。
解:用西北角法可以快速得到初始解,但是由于没有考虑运输价格,效果不好;最小元素法从最小的运输价格入手,一开始效果很好,但是到了最后因选择余地较少效果不好; Vogel法从产地和销地运价的级差来考虑问题,总体效果很好,但是方法较复杂。
第三章习题解答
详细说明用位势法(对偶变量法)求检验数的原理。
解:原问题的检验数也可以利用对偶变量来计算:
第三章习题解答
其中,ui和vj就是原问题约束对应的对偶变量。由于原问题的基变量的个数等于m+n-1。所以相应的检验数就应该等于0。即有:
由于方程有m+n-1个, 而变量有m+n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解。然后再利用这个解就可以求出非基变量的检验数了。
第三章习题解答
用表上作业法求解运输问题时,在什么情况下会出现退化解?当出现退化解时应如何处理?
解:当数字格的数量小于m+n-1时,相应的解就是退化解。如果出现了退化解,首先找到同时划去的行和列,然后在同时划去的行和列中的某个空格中填入数字0。只要数字格的数量保持在m+n-1个的水平即可。
第三章习题解答
一般线性规划问题具备什么特征才能将其转化为运输问题求解,请举例说明。
解:如果线性规划问题有“供”和“需”的关系,并且有相应的“费用”,就可以考虑将线性规划问题转成运输问题求解。例如,生产满足需求的问题。
第三章习题解答
试判断表3-30和表3-31中给出的调运方案可否作为表上作业法迭代时的基可行解?为什么?
答:都不是。数字格的数量不等于m+n-1。
表3-30
销地
产地
B1
B2
B3
B4
产量
A1
0
15
15
A2
15
10
25
A3
5
5
销量
5
15
15
10
第三章习题解答
表3-31
销地
产地
B1
B2
B3
B4
B5
产量
A1
150
250
400
A2
200
300
500
A3
250
50
300
A4
90
210
300
A5
80
20
100
销量
240
410
550
330
70
第三章习题解答