第四版运筹学部分课后习题解答

运筹学部分课后习题解答P471.1用图解法求解线性规划问题a）12121212minz=23466..424,0xxxxstxxxx解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为min3z=23032P471.3用图解法和单纯形法求解线性规划问题a）12121212maxz=10x5x349..528,0xxstxxxx解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即112122134935282xxxxxx，即最优解为*31,2Tx这时的最优值为max335z=101522单纯形法：原问题化成标准型为121231241234maxz=10x5x349..528,,,0xxxstxxxxxxxjc10500BCBXb1x2x3x4x03x9341004x8[5]201jjCZ1050003x21/50[14/5]1-3/5101x8/512/501/5jjCZ010-252x3/2015/14-3/14101x110-1/72/7jjCZ00-5/14-25/14所以有*max33351,,1015222TxzP782.4已知线性规划问题：1234124122341231234max24382669,,,0zxxxxxxxxxxxxxxxxxxx求:(1)写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*X，试根据对偶理论，直接求出对偶问题的最优解。解：（1）该线性规划问题的对偶问题为：1234124123434131234min8669223411,,,0wyyyyyyyyyyyyyyyyyyy（2）由原问题最优解为)0,4,2,2(*X，根据互补松弛性得：12412343422341yyyyyyyyy把)0,4,2,2(*X代入原线性规划问题的约束中得第四个约束取严格不等号，即4224890y从而有12123322341yyyyyy得123443,,1,055yyyy所以对偶问题的最优解为*43(,,1,0)55Ty，最优值为min16wP792.7考虑如下线性规划问题：123123123123123min6040803224342223,,0zxxxxxxxxxxxxxxx（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为：123123123123123max2433426022403280,,0wyyyyyyyyyyyyyyy（2）在原问题加入三个松弛变量456,,xxx把该线性规划问题化为标准型：123123412351236max60408032243422230,1,,6jzxxxxxxxxxxxxxxxxjjc-60-40-80000BCBXb1x2x3x4x5x6x04x-2-3-2-110005x-4[-4]-1-301006x-3-2-2-2001jjCZ-60-40-8000004x10-5/45/41-1/120801x111/43/40-1/4006x-10[-3/2]-1/20-1/21jjCZ0-25-350-15004x11/6005/311/3-5/6801x5/6102/30-1/31/6402x2/3011/301/3-2/3jjCZ00-80/30-20/3-50/3*max5252230(,,0),604080063633TxzP812.12某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？（d）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。ABC可用量（单位）劳动力材料6353454530产品利润（元/件）314解：由已知可得，设jx表示第j种产品，从而模型为：123123123123max3463545..34530,,0zxxxxxxstxxxxxxa)用单纯形法求解上述模型为：产品资源消耗定额jc31400BCBXb1x2x3x4x5x04x456351005x3034[5]01jjCZ3140004x15[3]-101-143x63/54/5101/5jjCZ3/5-11/500-4/531x51-1/301/3-1/343x3011-1/52/5jjCZ0-20-1/5-3/5得到最优解为*(5,0,3)Tx；最优值为max354327zb）设产品A的利润为3，则上述模型中目标函数1x的系数用3替代并求解得：jc31400BCBXb1x2x3x4x5x31x51-1/301/3-1/343x3011-1/52/5jjCZ-20-1/5-3/5jjCZ0-2+/30-1/5-/3-3/5+/3要最优计划不变，要求有如下的不等式方程组成立20310533053解得：3955从而产品A的利润变化范围为：393,355,即242,455C）设产品D用6x表示，从已知可得16661/5BccBP'1661128334122555PBP把6x加入上述模型中求解得：jc314003BCBXb1x2x3x4x5x6x31x51-1/301/3-1/3[2]43x3011-1/52/5-4/5jjCZ0-20-1/5-3/51/536x5/21/2-1/601/6-1/6143x52/513/151-1/154/150jjCZ-1/10-59/300-7/30-17/300从而得最优解*(0,0,5,0,0,5/2)Tx；最优值为max545327.5272z所以产品D值得生产。P1013.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表3-35B1B2B3B4产量A1A2A31012227142091611201815255销量5151510产地销地解：因为4131jjiiba，即产销平衡.所以由已知和最小元素法可得初始方案为B1B2B3B4产量A1A2A351501501015255销量5151510检验：由于有两个检验数小于零，所以需调整，调整一：B1B2B3B4产量A1A2A351501510015255销量5151510检验：由于还有检验数小于零，所以需调整，调整二：产地销地产地销地B1B2B3B4产量A1A2A355101510015255销量5151510检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min25257109151110180335z表3-36B1B2B3B4产量A1A2A386549314427372526销量10102015解：因为34115855ijijab，即产大于销，所以需添加一个假想的销地，销量为3，构成产销平衡问题，其对应各销地的单位运费都为0。B1B2B3B4B5产量A1A2A386549314427300072526销量101020153由上表和最小元素法可得初始方案为产地销地产地销地产地销地B1B2B3B4B5产量A1A2A3911071315372526销量101020153检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min69513101741331503193z表3-37B1B2B3B4B5产量A1A2A38566M3389746578203030销量2525201020解：因为351180100ijijab，即销大于产，所以需添加一个假想的产地，产量为20，构成产销平衡问题，其对应各销地的单位运费都为0。B1B2B3B4B5产量A1A2A3A485606M3038907460578020303020销量2525201020产地销地产地销地产地销地由上表和最小元素法可得初始方案为B1B2B3B4B5产量A1A2A3A4520252001015520303020销量2525201020检验：由于有两个检验数小于零，所以需调整，调整一：B1B2B3B4B5产量A1A2A3A4205252001051520303020销量2525201020检验：产地销地产地销地由于还有检验数小于零，所以需调整，调整二：B1B2B3B4B5产量A1A2A3A4205252001002020303020销量2525201020检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min320520410653258002000305zP1274.8用割平面法求解整数规划问题。a）12121212max7936735,0,zxxxxxxxx且为整数解：该问题的松弛问题为：12121212max7936735,0zxxxxxxxx则单纯形法求解该松弛问题得最后一单纯形表为：产地销地jc7900BCBXb1x2x3x4x92x7/2017/221/2271x9/210-1/223/22jjCZ00-28/11-15/11割平面1为：234(31/2)(07/22)(01/22)xxx3421713022222xxx34571122222xxx从而有jc79000BCBXb1x2x3x4x5x92x7/2017/221/22071x9/210-1/223/22005x-1/200-7/22-1/221jjCZ00-28/11-15/11092x30100171x32/71001/7-1/703x11/70011/7-22/7jjCZ000-1-8割平面2为：145(44/7)(01/7)(16/7)xxx451541640777xxxx456164777xxxjc790003BCBXb1x2x3x4x5x6x92x301001071x32/71001/7-1/7003x11/70011/7-22/7006x-4/7000-1/7-6/71jjCZ000-1-8092x301001071x41000-1103x10010-4104x400016-7jjCZ0000-2-7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即*4,3Tx，最优值为max749355zP1445.3用图解分析法求目标规划模型c）解:由下图可知，满足mind1-的满意解为区域X2CDX1；满足mind2+的满意解为闭区域BCDEB；满足min2d3-的满意解为图中的A点,满足mind4-的满意解为图中的A点，所以该问题的满意解为图中的点A（24，x1+x2+d1--d1+=40x1+x2+d2--d2+=40+10=50x1+d3--d3+=24x2+d4--d4+=30minZ=P1d1-+P2d2++P3（2d3-+1d4-）