运筹学课后习题答案__林齐宁版本__北邮出版社..pdf





《运筹学课后习题答案__林齐宁版本__北邮出版社..pdf》由会员分享,可在线阅读,更多相关《运筹学课后习题答案__林齐宁版本__北邮出版社..pdf(17页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学作业标准答案运筹学作业标准答案(教师用教师用)NoNo.1.1线性规划线性规划1 11、某织带厂生产A、B 两种纱线和 C、D 两种纱带,纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下:产品ABC项目单位产值(元)1681401050单位成本(元)4228350单位纺纱用时(h)3210单位织带用时(h)002工厂有供纺纱的总工时7200h,织带的总工时1200h。(1)列出线性规划模型,以便确定产品的数量使总利润最大;(2)如果组织这次生产具有一次性的投入20 万元,模型有什么变化?对模型的解是否有影响?解解:(1)设 A 的产量为 x1,B 的产量为 x2,C
2、 的产量为 x3,D 的产量为 x4,则有线性规划模型如下:max f(x)=(168 42)x1+(140 28)x2+(1050 350)x3+(406 140)x4=126 x1+112 x2+700 x3+266 x43x1 2x210 x3 4x4 7200s.t.2x3 0.5x41200 xi 0,i 1,2,3,4D40614040.5(2)如果组织这次生产有一次性的投入20 万元,由于与产品的生产量无关,故上述模型只需要在目标函数中减去一个常数20 万,因此可知对模型的解没有影响。2、将下列线性规划化为极大化的标准形式min f(x)2x1 3x2 5x3解解:将约束条件中的
3、第一行的右端项变为正值,x1 x2 x3 5并添加松弛变量x4,在第二行添加人工变量x5,6x1 7x2 9x316将第三行约束的绝对值号打开,变为两个不等式,s.t.|19x1 7x2 5x3|13分别添加松弛变量x6,x7,并令x,则3x3x3x1,x2 0,x3 不限有maxf(x)=2 x13 x25(x x)+0 x4M x5+0 x6+0 x733 x3 x4 5 x1 x2 x36x 7x 9x 9x x 1612335 5x3 x613s.t.19x17x25x319x 7x 5x 5x x 1312337,x3,x4,x5,x6,x7 0 x1,x2,x3运筹学作业标准答案运
4、筹学作业标准答案(教师用教师用)3、用单纯形法解下面的线性规划2 2max f(x)2x15x23x3 3x12x2 x3 610 x 6x 3x 125123s.t.2x1 x20.5x3 420 x1,x2,x3 0,解解:在约束行 1,2,3 分别添加 x4,x5,x6松弛变量,有初始基础可行解和单纯形法迭代步骤如下:253000CjCBXBbx1x2x3x4x5x6bi/aij*0 x461032100610/210 x5125(6)3010125/6*10 x642011/2001420/12OBJ=0000000zjcj-zj253000253000CjCBXBbx1x2x3x4x
5、5x6bi/aij*0 x41705/3(10/3)010170.521/35x2125/61/611/201/600 x62395/611/600011/6OBJ=625/655/205/60zj5/6cj-zj17/601/2005/6253000CjCBXBbx1x2x3x4x5x6bi/aij*2x1341/2103/53/101/1005x5197/401(2/5)1/203/200125.1250 x62847/40011/1011/207/201OBJ=2349/4zj254/517/2011/200cj-zj0011/5011/200253000CjCBXBbx1x2x3x4x
6、5x6bi/aij*2x11955/813/203/81/803x3985/805/211/83/800 x613555/16011/4011/161/161OBJ=6865/8zj221/239/811/80cj-zj0011/29/811/80答:最优解为 x1=244.375,x2=0,x3=123.125,剩余变量 x6=847.1875;最优解的目标函数值为858.125。运筹学作业标准答案运筹学作业标准答案(教师用教师用)NoNo.2.2两阶段法和大两阶段法和大MM 法法1、用两阶段法解下面问题:min f(x)4x16x2解解:将原问题变为第一阶段的标准型max f(x)0 x1
7、0 x2 x5 x63 3x12x280s.t.3x1 x2 75x,x 012CBXBx51x61OBJ=155CBXBx510 x1OBJ=55CBXB0 x20 x1OBJ=0第二阶段CBXBx26x14OBJ=254Cjb8075zjcj-zjCjb5525zjcj-zjCjb3314zjcj-zjCjb3314zjcj-zjx1 2x2 x3 x5 80s.t.3x1 x2 x4 x6 75x,x,x,x,x,x 01234560 x11(3)440 x101000 x101004x10140第一阶段单纯形表000 x2x3x4201101113311000 x2x3x4(5/3)1
8、/311/301/315/31/35/31/31000 x2x3x411/53/501/52/50000006x2106000 x3x41/53/51/52/514/52/514/52/51x510101x510101x53/51/5011x601101x61/31/31/34/31x61/52/501bi/aij*8075/3*bi/aij*553/5*253bi/aij*bi/aij*答答:最优解为 x1=14,x2=33,目标函数值为254。运筹学作业标准答案运筹学作业标准答案(教师用教师用)2、用大 M 法解下面问题,并讨论问题的解max f(x)10 x115x212x35x13x2
9、 x3 95x 6x 15x 15123s.t.2x1 x2 x3 5x1,x2,x3 0,4 4解解:第 1、2 行约束条件添加x4,x5松弛变量,第3 行添加 x6剩余变量和 x7人工变量,有如下初始单纯形表和迭代步骤:101512CjCBXBbx1x2x30 x49(5)310 x5156155x75211MOBJ=5Mzjcj-zj2M10+2MM15+MM12+M0 x4100000 x5010000 x6001MMMx7001M0CB100MXBx1x5x7Cjb9/5247/5zjcj-zj10 x110010015x23/591/56+M/59M/512x31/5(16)3/5
10、23M/50 x41/512/52+2M/50 x5010000 x6001MMMx7001M0OBJ=187M/510+3M/522M/5CB1012MOBJ=XBx1x3x733M/2Cjb3/23/21/2zjcj-zj10 x110010015x239/809/1643/8093/8+43M/8027/843M/8012x30101200 x43/101/2011/2021/8+7M/1621/87M/160 x51/103/207/205/8+3M/805/83M/800 x6001MMMx7001M0答答:最后单纯形表中检验数都小于等于0,已满足最优解判定条件,但人工变量 x7仍未
11、迭代出去,可知原问题无可行解(无解)。运筹学作业标准答案运筹学作业标准答案(教师用教师用)NoNo.3.3线性规划的对偶问题线性规划的对偶问题1、写出下列线性规划问题的对偶问题:max f(x)2x13x25x3x1 x2 x3 x4 52x x 4(1)13s.t.x2 x3 x4 6x1 0,x2,x3 0,x4不限5 5解解:对偶问题为ming(y)5y14y26y3y12y2 2y1 y3 3s.t.y1 y2 y3 5y1y3 0y1 0,y2 0,y3不限min f(x)4x13x28x3(2)2 x1 6s.t.4 x21412 x 83解解:原问题的约束条件可改写为右式max
12、g(y)6y12y214y34y48y512y6 y1 y2 4y3 y4 3s.t.y5 y6 8y1,y3,y5 0,y2,y4,y6 0 x1 6x 21x214x2 4x3 8x3 12x 不限,x 0,x 0231令改写后约束条件每行对应的对偶变量为y1,.,y6,则有对偶规划如下:运筹学作业标准答案运筹学作业标准答案(教师用教师用)2、写出下问题的对偶问题,解对偶问题,并证明原问题无可行解max f(x)4x13x2x1 x21 x2 1s.t.x 2x211x1,x2 0,6 6解解:对偶问题为min g(y)y1 y2 y3约束条件标准化为 y1y3 y4 4y1 y3 4 y
13、1 y2 2y3+y5 3s.t.y1 y2 2y3 3y1,y2,y3,y4,y5 0y,y,y 01231y111011y111101y11321入变量1y20(1)011y201101y201101y312011y3(1)2211y310100y410000y10000y412110y501000y501110y50111有对偶问题解的单纯形表如下:CB00OBJ=CB01OBJ=CB11OBJ=YBy4y50YBy4y23YBy3y27Cjb43zjzj cjCjb43zjzj cjCjb411zjzj cj答答:迭代到第三步,x1为入变量,但主列中技术系数全为负值,故对偶问题有可行解
14、但解无界,由弱对偶定理推论可知,原问题无可行解。运筹学作业标准答案运筹学作业标准答案(教师用教师用)3、用对偶单纯形法求下面问题min f(x)4x1 6x2x1 2x2 80s.t.3x1 x2 75x1,x2 07 7解:CB00OBJ=CB60OBJ=CB64OBJ=XBx3x40XBx2x4240XBx2x1254Cjb8075zjzj-cjCjb4035zjzj-cjCjb3314zjzj-cj4x113044x11/2(5/2)314x101406x2(2)1066x210606x210600 x310000 x31/21/2330 x33/51/514/514/50 x40100
15、0 x401000 x41/52/52/52/5min(zj-cj)/ai*jai*j04,3*2/5*,6答答:最优解为 x1=14,x2=33,目标函数值为254。NoNo.4.4线性规划的灵敏度分析线性规划的灵敏度分析1、下表是一线性规划最优解的单纯形表CB2109XBx1x5x2Cjb4223zjcj zj21x11002109x2001904x31/32/31/31060 x42/34/31/311110 x5010000 x61/31/32/311原问题为 max 型,x4,x5为松驰变量,x6为剩余变量,回答下列问题:(1)资源 1、2、3 的边际值各是多少?(x4,x5是资源
16、1、2 的松驰变量,x6是资源 3 的剩余变量)(2)求 C1,C2和 C3的灵敏度范围;(3)求b1,b2的灵敏度范围。解:(1)q1=11,q2=0,q3=1。(2)x1,x2为基变量,故运筹学作业标准答案运筹学作业标准答案(教师用教师用)8 86111max,C max 18,.165,3 C 3C 18 C 11111/3 2/3 1/36111maxC min,18 C 1.5 9 C 10.52221/31/3 2/3x3为非基变量,故 C 6 C 1033 4 223(3)max b min,6 b11.512/34/3 1/3同理有 2b2NoNo.5.5运输问题运输问题1、分
17、别用西北角法、最低费用法和运费差额法,求下面运输问题(见表)的初始可行解,并计算其目标函数。(可不写步骤)2、以上题中最低费用法所得的解为初始基础可性解,用表上作业法(踏石法)求出最优解。(要求列出每一步的运费矩阵和基础可行解矩阵)销地产地A1A2A3A4销量解:(1)205B16106225B296513151530B3412963530B488201445B5579330产量20304060 x14301530西北角法151025(2)最低费用法201510255OBJ955OBJ1415(2)差额法1525OBJ8505255153030运费表(检验数 zij|wij)06094 4(1
18、5)8-7 10-7 6-3 128 8565 59 920202 22 136 6171401144154-6 736993 363运筹学作业标准答案运筹学作业标准答案(教师用教师用)迭代后的分配表 xij515301525255OBJ850运费表(检验数 zij|wij)3006094 48 815010 064128 817565 59 913 20692 22 136 610 143 30444344969 9答:x13=5,x14=15,x24=30,x32=15,x33=25,x41=25,x43=5,x45=30,OBJ=850。NoNo.6.6指派问题指派问题1、有 4 个工人
19、。要指派他们分别完成4 项工作。每人做各项工作所消耗的时间(h)如下表,问如何分派工作,使总的消耗时间最少?消耗工作工人A3314B3256C5514D32610甲乙丙丁解:变换效率矩阵如下:33143256551432610逐(0)行1标0*记0*0*04223(0)0*0*056逐(0)列1标0*记0*0*(0)4223(0)0*0*0*56每行每列都有两个以上的0未找到最优解4851重0*(0)0*20*新11(0)30*0*4(0)5标0*记(0)0*20*62637(0)0*4223(0)0*0*(0)56划线过程(发现有 4 条直线)找到最优解答:容易看出,共有四个最优解:甲B,乙


- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 课后 习题 答案 _ 林齐宁 版本 出版社

限制150内