《运筹学课后习题集答案解析.doc》由会员分享，可在线阅读，更多相关《运筹学课后习题集答案解析.doc（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-/第一章 线性规划1、 由图可得：最优解为2、用图解法求解线性规划： Min z=2x1+x2 解： 由图可得：最优解x=1.6,y=6.43用图解法求解线性规划： Max z=5x1+6x2 解： 由图可得：最优解Max z=5x1+6x2, Max z= +4用图解法求解线性规划： Maxz = 2x1 +x2 由图可得：最大值 ， 所以max Z = 8.6将线性规划模型化成标准形式： Min z=x1-2x2+3x3 解：令Z=-Z,引进松弛变量x40，引入剩余变量x50，并令x3=x3-x3,其中x30,x30Max z=-x1+2x2-3x3+3x37将线性规划模型化为标准形式
2、Min Z =x1+2x2+3x3 解：令Z = -z，引进松弛变量x40,引进剩余变量x50,得到一下等价的标准形式。 x2=-x2 x3=x3-x3Z = -min Z = -x1-2x2-3x3 Cj33400iCBXBbx1x2x3x4x50X4403451080X5606430120j334004x383/54/511/5040/30x54221/58/50-3/5160/7j3/5-1/50-4/504x320 4/714/35-1/73x11018/2101/75/21j0-3/70-31/35-1/79用单纯形法求解线性规划问题：Max Z =70x1+120x2 解： Max
3、 Z =70x1+120x2 单纯形表如下 Max Z =3908.Cj43000iCBXBbx1x2x3x4x50X330002210015000X4400052.50108000X550010001500Cj-Zj43000Cj43000iCBXBbx1x2x3x4x50X320000210-20X4150002.501-50X150010001Cj-Zj0000-411.解：（1）引入松弛变量X4，X5，X6，将原问题标准化，得max Z=10X1+6X2+4X3 X1+X2+X3+X4=10010 X1+4X2+5X3+X5=6002 X1+2X2+6X3+X6=300X1,X2,X3
4、,X4,X5,X60得到初始单纯形表：Cj1064000CBXBbX1X2X3X4X5X6000X4X5X6100600300110214215610001000110060150Cj-Zj1064000（2）其中1 =C1-Z1=10-（01+010+02）=10，同理求得其他根据max =max10,6,4=10,对应的X1为换入变量，计算得到，min =min100/1,600/10,300/2=60,X5为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程Cj1064000CBXBbX1X2X3X4X5X60100X4X1X640601800103/52/56/51/21/2
5、5100-1/101/101/5001200/3150150Cj-Zj02-10-106100X2X1X6200/3100/31000101005/61/645/3-2/3-2-1/61/60001200/3150150Cj-Zj00-8/3-10/3-2/30j 0，迭代已得到最优解，X*=（100/3，200/3，0，0，0，100）T ，Z* =10100/3+6200/3+40 =2200/3。12解：（1）引入松弛变量X3，X4，X5将原问题标准化，得max Z=2X1+X25X2+X3=156X1+2X2+ X4=24X1+2X2+ X5=5X1,X2,X3,X4,X50得到初始单
6、纯形表：Cj21000CBXBbX1X2X3X4X5000X3X4X515245061521100010001-45Cj-Zj21000（2）其中1 =C1-Z1=2-（01+010+02）=2，同理求得其他根据max =max2,1,0=2,对应的X1为换入变量，计算得到，min =min-,24/6,5/1=4, X4为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程Cj106400CBXBbX1X2X3X4X5020X3X1X5154101051/32/310001/6-1/60013123/2Cj-Zj01/30-1/30021X3X1X215/217/23/2010001
7、1005/41/4-1/4-15/2-1/23/2Cj-Zj000-1/4-1/2j 0，迭代已得到最优解，X*=（7/2，3/2，0，0，0）T ，Z* =27/2+3/2 =17/2。13解：引入松弛变量X3、X4，约束条件化成等式，将原问题进行标准化，得：Max Z=2.5X1+X2 3X1+5X2+X3 =15 5X1+2X2 +X4=10 X1,X2,X3,X40（1） 确定初始可行基为单位矩阵I=P3，P4，基变量为X3，X4，X5，非基变量为X1，X2，则有：Max Z=2.5X1+3X2 X3=15-3X1-5X2s.t X4=10-5X1-2X2 Xi0，j=1，2，3，42
8、.5100 b 0 15 0 10 3 5 1 05 2 0 1522.5100 将题求解过程列成单纯形表格形式，表1 由上述可得，将替换为表2，单纯形迭代过程 2.5100 b0 9 2.5 20 19/5 1 -3/51 2/5 0 1/545/1950000.5由表2可得，将替换为2.5100 b1 2.5 0 1 1 0 000表3 最终单纯形表非基变量检验数=0,=，得到该线性规划另一最优解，=（，0,0）,=5， 该线性规划具有无穷多个解14. 用单纯形法求解线性规划问题：解：（1） 将原问题转化为标准形式，得（2）建立单纯性，并进行迭代运算Cj21000C8 XBbX1X2X3X
9、4X50X315051000X4246101040X55110015Cj-Zj210000X3150510032X1411/601/60240X5105/60-1/616/5Cj-Zj02/30-1/300X390011-62X119/51001/5-1/51X26/5010-1/56/5Cj-Zj000-1/5-4/5 （3）得到最优解X*=(,9 ,0 ,0 )T，Z*=15.用单纯形法求解线性规划问题：解：（1） 将原问题转化为标准形式，得（2）建立单纯性，并进行迭代运算Cj21000C8 XBbX1X2X3X4X50X3211210020X42-21010-0X54-11001-Cj-
10、Zj110001X121-21000X460-32100X560-1101Cj-Zj03-100本例第二个单纯形表中，非基变量X2对应的检验数0，并且对应的变量系数ai，20（i=1，2，3），根据无界解判定定理，该线性规划问题有无界解（或无最优解）。如果从方程角度看，第二个表格还原线性方程也即：令=0，则此时，若进基，则，会和基变量同时增加，同时目标函数值无限增长，所以本题无解。16解：（1）引入松弛变量X3，X4，X5将原问题标准化，得max Z=2X1+4X2+0X3+0X4+0X5X1+2X2+X3=8X1+X4=4X2+X5=3X1,X2,X3,X4,X50（1）得到初始单纯形表：C
11、j24000CBXBbX1X2X3X4X5000X3X4X58431102011000100014-3Cj-Zj24000（2）重复（1）过程得到如下迭代过程Cj106400CBXBbX1X2X3X4X5004X3X4X224311000110001000124-Cj-Zj2000-4204X1X4X22231000011-10010001Cj-Zj00-2005 = 0，3 =0增加人工变量x6,x7,得到：MaxZ=-5X1-2X2-4X3-MX6-MX73X1+X2+2X3-X4+X6=46X1+3X2+5X3-X5+X7=10X1,x2,x3,x4,x5=0大M法求解过程如下：cj-5
12、-2-400-M-MiCBXBbX1X2X3X4X5X6X7-M-MX6X7410361325-100-110014/35/3cj-zj-5+9M-2+4M-4+7M-M-M00-5-MX1X74/32101/312/31-1/320-11/3-201-1cj-zj0-1/3+M-2/3+M-5/3+2M-M5/3-3M0-50X1X45/31101/21/25/61/201-1/6-1/20-11/61/210/32cj-zj01/21/60-5/6-M5/6-M-5-2X1X22/3210011/31-121/3-11-2-1/31cj-zj00-1/3-1-1/31-M1/3-M最优解为
13、X1*=2/3,X2*=2,X3*=0最优目标函数值minZ=22/319、解：化为标准形式：maxZ=-540x1-450x2-720x33x1+5x2+9x3-x4=709x1+5x2+3x3-x5=30X1,x2,x3,x4,x5=0增加人工变量x6,x7,得到：maxZ=-540x1-450x2-720x3-Mx6-Mx73x1+5x2+9x3-x4+x6=709x1+5x2+3x3-x5+x7=30X1,x2,x3,x4,x5=0大M法求解过程如下：cj-540-450-72000-M-MiCBXBbX1X2X3X4X5X6X7-M-MX6X770303(9)5593-100-110
14、0170/330/9cj-zj12M-54010M-45012M-720-M-M00-M-540X6X16010/30110/35/9(8)1/3-101/3-1/910-1/31/92.510cj-zj0-150+10M/38M-540MM/3-600-M/3+60-720-540X3X115/25/6015/12(5/12)10-1/81/241/24-1/81/8-1/24-1/241/8182cj-zj01250135/2-475/12135/2-M75/2-M-720-450X3X220/32-112/501101/61/101/6-3/101/6-1/10-1/63/10-5700
15、-360-180-4500-720075-7515-15-7575-M-1515-M最优解为X*=(0,2,20/3,0,0)最优目标函数值minZ=570020解：先将其化成标准形式，有 max z = 3+ +0+0 + =4 （a） -2+- -=1 （b） 3+ =9 （c） ，0 这种情况可以添加两列单位向量，P7 ，连同约束条件中的向量P4构成单位矩阵 P4 P6 P7 1 0 0 0 1 0 0 0 1P6，P7是人为添加上去的，它相当于在上述问题的约束条件（b）中添加变量，约束条件（c）中添加变量，这两个变量相应称为人工变量。由于约束条件（b）（c）在添加人工变量前已是等式，为
16、使这些等式得到满足，因此在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的负数，用“-M”代表。添加人工变量后数学模型变为 max z = 3+ +0+0MM+ =4 -2+- -+ =1 3+ +=9 ，0 得到初始可行解，并列出初始单纯形表。在单纯形法迭代运算中，M可当作一个数学符号一起参加运算。检验数中含M符号的，当M的系数为正时，该检验数为正；当M的系数为负时，该检验数为负。求解过程见下表 cj -3 0 1 0 0 -M -MCB 基 b X1 X2 X3 X4 X5 X6 X70 4M 1M 91 1 1 1 0 0 0-2 1 -1 0 -1 1 00 3
17、 1 0 0 0 1cjzj-2M-3 4M 1 0 -M 0 00 30 1M 6 3 0 2 1 1 -1 0-2 1 -1 0 -1 1 06 0 4 0 3 -3 1cjzj6M-3 0 4M+1 0 3M -4M 00 00 33 10 0 0 1 -1/2 -1/2 -1/20 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6cjzj0 0 3 0 3/2 -M-3/2 -M+1/20 00 5/21 3/20 0 0 1 -1/2 1/2 -1/2-1/2 1 0 0 -1/4 1/4 1/43/2 0 1 0 3/4 -3/4 1/4cjzj-9/2
18、 0 0 0 -3/4 -M+3/4 -M-1/4最优解为（0，5/2，3/2）21、解：将原问题转化为标准型 Maxz=3x1+2x2 2x1+x2+x3=2 s.t. 3x1+4x2-x4=12 Xi0，i=1,2,3,4然后添加人工变量x5，将原线性规划问题变为 Maxz=3x1+2x2-Mx5 2x1+x2+x3=2s.t. 3x1+4x2-x4+x5=12 Xi0，i=1,2,3,4,5取基变量为x3,x5,建立单纯形表，迭代过程如下：Cj3200-Mi Cb Xb BX1X2X3X4X50X32211002-MX512340-113Cj-zj3+3M2+4M0-M0Cj3200-M
19、i Cb Xb BX1X2X3X4X50X2221100-MX54-50-4-11Cj-zj3-5M0-4M-M0在单纯形表中，非基变量的检验值都是小于0，而人工变量仍不为0，则该线性规划无最优解。22、解：假设甲、乙俩种产品产量分别为x1、x2，产品售后的最大利润为z，则根据题意可建立以下线性规划模型：Max=70x1+120x2 9x1+4x2360s.t. 4x1+6x2200 3x1+10x2300 Xi0，i=1,223 .24.27. 设生产四种产品分别为X1,X2,X3X4,则应满足的目标函数为max=2X1+3X2+X3+X4 满足的约束条件为 0.5X1+3X2+X3+0.5
20、X41800 2X1+X2+X3+ X42800 0.5X1+0.5X2+X3+X41800 3X1+X2+2X3+3X41800 X1 1000 X2600 X3500 X440028. 设X1=A出售的数量，X2=A在第二车间加工后的出售数量， X3=B的出售数量，X4=B在第三车间加工后的出售数量， X5=第一车间所用的原料数量 目标函数为maxZ=8X1+9.5X2+7X3+8X42.75X5 满足的约束条件为 X5100000 3X2+2X4+1.5X5 200000 X1+X23X5=0 X3+ X4 2X5=0 X1,X2,X3,X40 29,解: 现在我们对本问题定义三种不同形
21、式的决策变量，从而从不同的途径来构建模型.（1）设工厂第季度生产产品吨首先，考虑约束条件：第一季度末工厂需交货20吨，故应有x1=20；第一季度末交货后积余（x1-20）吨；第二季度末工厂需交货20吨，故应有x1-20+x2=20；类似地，应有；第四季度末供货后工厂不能积压产品，故应有；又考虑到工厂每个季度的生产能力，故应有. 其次，考虑目标函数：第一季度工厂的生产费用为15.0，第二季度工厂生产的费用包括生产费用14及积压产品的存贮费；类似地，第三季度费用为，第四季度费用为. 工厂一年的费用即为这四个季度费用之和. 整理后，得下列线性规划模型： min s.t. ，.（2）设第季度工厂生产的
22、产品为吨，第季度初存贮的产品为吨（显然，）.因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有：， ， ；同时，每季度的生产量不能超过生产能力：；而工厂四个季度的总费用由每季的生产费用与存贮费用组成，于是得线性规划：min s.t. ， 2，3，4.（3） 设第季度生产而用于第季度末交货的产品数量为吨.根据合同要求，必须有： ， ， ， .又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力，故应有： ， ， ， .第季度生产的用于第季度交货的每吨产品的费用，于是，有线性规划模型：min z = s.t. 1，4；1，4，
23、.30,解 设为#型飞机被派遣去#工厂执行任务的架数.甲方的目标是希望事件“至少摧毁一个工厂”的概率最大. 这相当于希望事件“不摧毁任何工厂”的概率最小. 我们有：它不是线性的，为此将上式改写为 于是，模型的目标函数为 关于燃料的约束条件为： 经过整理，即为 .飞机数量约束： ，综上所述，本问题的线性规划模型为： max z = s.t. ， 1，2；1，2，3.第二章 线性规划1. 对偶问题和对偶变量的经济意义是什么？从经济学的角度来说,对偶变量反映的是对应的原变量的边际效应,即每增加一单位的原变量使目标函数变化的值,当原变量在目标函数取得最优解时没有用完的情况下,原变量的增加不会改变目标函
24、数的值,此时原变量的边际效应为0,即对偶变量为0,这就是强对偶理论。2. 简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？计算步骤见书P-42单纯形法对偶单纯形法原理保证原问题是可行解的情况下向对偶问题可行的方向迭代保证对偶问题是可行解的情况下向原问题可行的方向迭代最优解判断看非基变量的检验数是否都小于等于零看对偶单纯形表的B-1b是否都大于等于零迭代原则最大最小比值原则最大：检验数最大的那个非基变量为换入变量；最小：B-1b/aik最小的那个对应的基变量为换出变量最小最小比值原则最小：B-1b列数字最小（负数）的那个对应的基变量为换出变量；最小：(cj-zi)/alj最小的那个对应
25、的非基变量为换入变量3. 什么是资源的影子价格？他和相应的市场价格之间有什么区别？对偶变量yi的意义代表在资源最优利用条件下对第i种资源的估价，这是根据资源在生产作用中做出的贡献而得到的估价，称为影子价格。市场价格是指实际发生的市场交易价格，它是计量财务支出和收入的直接依据；机会成本或支付意愿就是经济分析中的影子价格。4. 如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？（1）对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值（2）对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值（3）由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。（4）更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。5. (1) min w=30y1+80y2 (2) max w=30y1+80y2+50y3 y1+4y22 y1-y2+