资源预览内容
第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
第9页 / 共20页
第10页 / 共20页
亲,该文档总共20页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第三章习题解答,3.1 与一般线性规划的数学模型相比,运输问题的数学模型具有什么特征? 答: 1、运输问题一定有有限最优解。 2、约束系数只取0或1。 3、约束系数矩阵的每列有两个1, 而且只有两个1。前m行中有一个1,或n行中有一个1。 4、对于产销平衡的运输问题,所有的约束都取等式。,第三章习题解答,3.2 运输问题的基可行解应满足什么条件?将其填入运输表中时有什么体现?并说明在迭代计算过程中对它的要求。 解:运输问题基可行解的要求是基变量的个数等于m+n-1。填入表格时体现在数字格的个数也应该等于m+n-1。在迭代过程中,要始终保持数字格的个数不变。,第三章习题解答,3.3 试对给出运输问题初始基可行解的西北角法、最小元素法和Vogel法进行比较,分析给出的解之质量不同的原因。 解:用西北角法可以快速得到初始解,但是由于没有考虑运输价格,效果不好;最小元素法从最小的运输价格入手,一开始效果很好,但是到了最后因选择余地较少效果不好; Vogel法从产地和销地运价的级差来考虑问题,总体效果很好,但是方法较复杂。,第三章习题解答,3.4 详细说明用位势法(对偶变量法)求检验数的原理。 解:原问题的检验数也可以利用对偶变量来计算 :,其中,ui和vj就是原问题约束对应的对偶变量。由于原问题的基变量的个数等于m+n-1。所以相应的检验数就应该等于0。即有:,第三章习题解答,由于方程有m+n-1个, 而变量有m+n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解。然后再利用这个解就可以求出非基变量的检验数了。,第三章习题解答,3.5 用表上作业法求解运输问题时,在什么情况下会出现退化解?当出现退化解时应如何处理? 解:当数字格的数量小于m+n-1时,相应的解就是退化解。如果出现了退化解,首先找到同时划去的行和列,然后在同时划去的行和列中的某个空格中填入数字0。只要数字格的数量保持在m+n-1个的水平即可。,第三章习题解答,3.6 一般线性规划问题具备什么特征才能将其转化为运输问题求解,请举例说明。 解:如果线性规划问题有“供”和“需”的关系,并且有相应的“费用”,就可以考虑将线性规划问题转成运输问题求解。例如,生产满足需求的问题。,第三章习题解答,3.8 表3-32和表3-33分别给出了各产地和各销地的产量和销量,以及各产地至各销地的单位运价,试用表上作业法求最优解。,第三章习题解答,3.9 试求出表3-34给出的产销不平衡运输问题的最优解。,第三章习题解答,第三章习题解答,3.10 某市有三个面粉厂,它们供给三个面食加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价,均表示于表3-35中。假定在第1,2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元,试确定使总效益最大的面粉分配计划(假定面粉厂和面食加工厂都属于同一个主管单位)。,第三章习题解答,第三章习题解答,第三章习题解答,3.11 表3-36示出一个运输问题及它的一个解:,第三章习题解答,试问: (1)表中给出的解是否为最优解?请用位势法进行检验。 答:是最优解。 (2)如价值系数c24由1变为3,所给的解是否仍为最优解?若不是,请求出最优解。 答:原来的解不是最优解。新的最优解是: x12=3,x13=5,x21=8,x22=2,x33=1,x34=3, 其他变量为0 。 (3)若所有价值系数均增加1,最优解是否改变?为什么? 答:不会改变。因为检验数不变。,第三章习题解答,(4)若所有价值系数均乘以2,最优解是否改变?为什么? 答:最优解不变。因为检验数不变。 (5)写出该运输问题的对偶问题,并给出其对偶问题的最优解。,第三章习题解答,3.12 1,2,3三个城市每年需分别供应电力320,250和350单位,由I,两个电站提供,它们的最大供电量分别为400个单位和450个单位,单位费用如表337所示。由于需要量大于可供量,决定城市1的供应量可减少030单位,城市2的供应量不变,城市3的供应量不能少于270单位,试求总费用最低的分配方案(将可供电量用完)。,第三章习题解答,第三章习题解答,3.13 试写出本章例5转运问题的数学模型。 解:已知 a110,a240,a3 = a4 = a5 = 0 b1= b2= b30,b430,b520 Q50 下面就是相应的模型: MIN Z= 4 X(1,1)+ 5 X(1,2)+ 3 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 7-X(1,1) + X(2,1) + X(3,1) + X(4,1) + X(5,1) = 0 8 X(1,2) - X(2,2) + X(3,2) + X(4,2) + X(5,2) = 0 9 X(1,3) + X(2,3) - X(3,3) + X(4,3) + X(5,3) = 0 10X(1,4) + X(2,4) + X(3,4) - X(4,4) + X(5,4) = 30 11X(1,5) + X(2,5) + X(3,5) + X(4,5) - X(5,5) = 20,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号