运筹学答案熊伟上汇总.docx
《运筹学答案熊伟上汇总.docx》由会员分享，可在线阅读，更多相关《运筹学答案熊伟上汇总.docx（31页珍藏版）》请在冰点文库上搜索。
运筹学答案熊伟上汇总
教材习题答案
部分有图形的答案附在各章PPT文档的后面，请留意。
第1章线性规划
第2章线性规划的对偶理论第3章整数规划第4章目标规划
第5章运输与指派问题第6章网络模型第7章网络计划第8章动态规划第9章排队论第10章存储论第11章决策论第12章对策论
习题一
1.1讨论下列问题：
（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化．
（2）在例1.2中，如果设xj（j=1，2，…，7为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．
（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．
（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．
（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．
1.2工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－22所示．
310和130.试建立该问题的数学模型,使每月利润最大．
【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为
maxZ=10x1+14x2+12x3⎧1.5x1+1.2x2+4x3≤2500⎪3x+1.6x+1.2x≤1400
23⎪1
⎪⎪150≤x1≤250⎨
⎪260≤x2≤310⎪120≤x3≤130⎪⎪⎩x1,x2,x3≥0
1.3建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格
及数量如表1－23所示：
【解】
设xj（j=1,2,…，14）为第j种方案使用原材料的根数，则
（1）用料最少数学模型为
minZ=∑xj
j=1
14
⎧2x1+x2+x3+x4≥300⎪
⎪x2+3x5+2x6+2x7+x8+x9+x10≥450
⎪
⎨x3+x6+2x8+x9+3x11+2x12+x13≥400
⎪x+x+2x+x+x+3x+2x+3x+4x≥600
47910121314
⎪23⎪⎩xj≥0,j=1,2,,14
用单纯形法求解得到两个基本最优解
X（1=（50,200,0,0,84,0,0,0,0,0,0,200,0,0;Z=534X（2=（0,200,100,0,84,0,0,0,0,0,0,150,0,0;Z=534
（2）余料最少数学模型为
minZ=0.6x1+0.3x3+0.7x4++0.4x13+0.8x14⎧2x1+x2+x3+x4≥300⎪
⎪x2+3x5+2x6+2x7+x8+x9+x10≥450⎪
⎨x3+x6+2x8+x9+3x11+2x12+x13≥400
⎪x+x+2x+x+x+3x+2x+3x+4x≥600
47910121314
⎪23⎪⎩xj≥0,j=1,2,,14
用单纯形法求解得到两个基本最优解
X（1=（0,300,0,0,50,0,0,0,0,0,0,200,0,0;Z=0，用料550根X（2=（0,450,0,0,0,0,0,0,0,0,0,200,0,0;Z=0，用料650根显然用料最少的方案最优。
1.4A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时．可供利用的前道工序有11小时，后道工序有17小时．
每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售赢利，其余的只能加以销毁．
出售单位产品A、B、C的利润分别为3、7、2元，每单位产品C的销毁费为1元．预测表明，产品C最多只能售出13个单位．试建立总利润最大的生产计划数学模型．
【解】设x1,x2分别为产品A、B的产量，x3为副产品C的销售量,x4为副产品C的销毁量，有x3+x4=2x2,Z为总利润，则数学模型为
maxZ=3x1+7x2+2x3-x4⎧x1+2x2≤11⎪2x+3x≤1712⎪⎪
⎨-2x2+x3+x4=0⎪x≤13⎪3⎪⎩xj≥0,j=1,2,,4
1.5某投资人现有下列四种投资机会,三年内每年年初都有3万元（不计利息）可供投资：
方案一：
在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；
方案二：
在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；
方案三：
在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；
方案四：
在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．
投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.【解】是设x
为第i年投入第j项目的资金数，变量表如下
数学模型为
maxZ=0.2x11+0.2x21+0.2x31+0.5x12+0.6x23+0.3x34⎧x11+x12≤30000⎪
⎪-1.2x11+x21+x23≤30000
⎪-1.5x12-1.2x21+x31+x34≤30000⎪⎪
⎨x12≤20000⎪x≤15000⎪23
⎪x34≤10000⎪⎪⎩xij≥0,i=1,,3;j=1,4
最优解X=（30000，0，66000，0，109200，0；Z＝84720
1.6IV发展公司是商务房地产开发项目的投资商．公司有机会在三个建设项目中投资：
高层办公楼、宾馆及购物中心，各项目不同年份所需资金和净现值见表1－24．三个项目的投资方案是：
投资公司现在预付项目所需资金的百分比数，那么以后三年每年必须按此比例追加项目所需资金，也获得同样比例的净现值．例如，公司按10％投资项目1，现在必须支付400万，今后三年分别投入600万、900万和100万，获得净现值450万．
公司目前和预计今后三年可用于三个项目的投资金额是：
现有2500万，一年后2000万，两年后2000万，三年后1500万．当年没有用完的资金可以转入下一年继续使用．
IV公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分比，使其投资获得的净现值最大．
【解】以1％为单位，计算累计投资比例和可用累计投资额，见表
（2）。
表
（2）
设xj为j项目投资比例，则数学模型：
maxZ=45x1+70x2+50x3⎧40x1+80x2+900x3≤2500
⎪
⎪100x1+160x2+140x3≤4500⎪
⎨190x1+240x2+160x3≤6500⎪200x+310x+220x≤8000
123
⎪⎪⎩xj≥0,j=1,2,3
最优解X＝（0，16.5049，13.1067）；Z=1810.68万元
1.7图解下列线性规划并指出解的形式：
maxZ=-2x1+x2
⎧x1+x2≥1（1⎪
⎨x1-3x2≥-1⎪x,x≥0⎩12
【解】最优解X＝（1/2，1/2）；最优值Z=－1/2
minZ=-x1-3x2
（2⎪
⎧2x1-x2≥-2
⎨2x1+3x2≤12⎪x≥0,x≥0
2⎩1
【解】最优解X＝（3/4，7/2）；最优值Z=－45/4
minZ=-3x1+2x2
⎧x1+2x2≤11⎪-x+4x≤1012（3⎪⎪⎨2x1-x2≤7⎪x-3x≤12⎪1
⎪⎩x1,x2≥0
【解】最优解X＝（4，1）；最优值Z=－
10
maxZ=x1+x2
⎧3x1+8x2≤12⎪（4⎪x1+x2≤2⎨⎪2x1≤3
⎪⎩x1,x2≥0
【解】最优解X＝（3/2，1/4）；最优值Z=7/4
minZ=x1+2x2
⎧x1-x2≥2⎪（5⎪x1≥3⎨⎪x2≤6
⎪⎩x1,x2≥0【解】最优解X＝（3，0）；最优值Z=3
maxZ=x1+2x2
⎧x1-x2≥2⎪（6⎪x1≥3⎨⎪x2≤6
⎪⎩x1,x2≥0
【解】无界解。
minZ=2x1-5x2
⎧x1+2x2≥6（7⎪⎨x1+x2≤2
⎪x,x≥0⎩12
【解】无可行解。
maxZ=2.5x1+2x2
⎧2x1+x2≤8⎪（8⎪0.5x1≤1.5⎨⎪x1+2x2≤10
⎪⎩x1,x2≥0
【解】最优解X＝（2，4）；最优值
Z=13
1.8将下列线性规划化为标准形式maxZ=x1+4x2-x3
⎧2x1+x2+3x3≤20（1⎪⎪5x1-7x2+4x3≥3⎨⎪10x1+3x2+6x3≥-5
⎪⎩x1≥0,x2≥0,x3无限制
'''【解】
（1）令x3=x3-x3,x4,x5,x6为松驰变量，则标准形式为'''maxZ=x1-4x2-x3+x3
'''⎧2x1+x2+3x3-3x3+x4=20⎪'''⎪5x1-7x2+4x3-4x3-x5=3⎨'''⎪-10x1-3x2-6x3+6x3+x6=5
'''⎪⎩x1,x2,x3,x3,x4,x5,x6≥0
minZ=9x1-3x2+5x3
⎧|6x1+7x2-4x3|≤20⎪（2⎪x1≥5⎨⎪x1+8x2=-8
⎪⎩x1≥0,x2≥0,x3≥0
【解】
（2）将绝对值化为两个不等式，则标准形式为
maxZ'=-9x1+3x2-5x3⎧6x1+7x2-4x3+x4=20⎪-6x-7x+4x+x=20
1235⎪⎪x-x=5⎨16
⎪-x-8x=8
2
⎪1⎪⎩x1,x2,x3,x4,x5,x6≥0
maxZ=2x1+3x2⎧1≤x1≤5
（3⎪
⎨-x1+x2=-1⎪x≥0,x≥0
2⎩1
【解】方法1：
maxZ=2x1+3x2
⎧x1-x3=1
⎪x+x=5
⎪14
⎨
⎪x1-x2=1⎪⎩x1,x2,x3,x4≥0
'=x1-1,有x1＝x1'+1,x1'≤5-1=4方法2：
令x1
'+1+3x2maxZ=2（x1
'≤4⎧x1
⎪
'+1+x2=-1⎨-（x1
⎪x,x≥0⎩12
则标准型为
'+3x2maxZ=2+2x1'+x3=4⎧x1
⎪
'+x2=0⎨-x1
⎪x',x,x≥0⎩123
maxZ=min（3x1+4x2,x1+x2+x3
⎧x1+2x2+x3≤30⎪
（4⎪4x1-x2+2x3≥15
⎨
⎪9x1+x2+6x3≥-5⎪x1无约束,x2、x3≥0⎩
【解】令y≤3x1+4x2,y≤x1+x2+x3,x1=x1'-x1''，线性规划模型变为
maxZ=y
'-x1''+4x2⎧y≤3（x1
⎪y≤x'-x''+x+x
1123⎪⎪'-x1''+2x2+x3≤30⎪x1⎨
'-x1''-x2+2x3≥15⎪4（x1
⎪9（x1'-x1''+x2+6x3≥-5⎪',x1'',x2、x3≥0⎪⎩x1
标准型为
maxZ=y
'+3x1''-4x2+x4=0⎧y-3x1
⎪y-x'+x''-x-x+x=0
11235⎪⎪'-x1''+2x2+x3+x6=30⎪x1⎨
'-4x1''-x2+2x3-x7=15⎪4x1⎪-9x1'+9x1''-x2-6x3+x8=5⎪',x1'',x2,x3,x4,x5,x6,x7,x8≥0⎪⎩x1
1.9设线性规划
maxZ=5x1+2x2⎧2x1+3x2+x3=50
⎪
4x-2x+x=60⎨124
⎪x≥0,j=1,,4⎩j
⎡21⎤⎡20⎤
取基B1=（P1，P3=⎢分别指出B1和B2对应的基变量和非基变量，⎥、B2＝⎢41⎥，40⎣⎦⎣⎦求出基本解，并说明B1、B2是不是可行基．
【解】B1：
x1，x3为基变量，x2，x4为非基变量,基本解为X=（15，0，20，0）T，B1是可行基。
B2：
x1,x4是基变量，x2,x3为非基变量，基本解X=（25，0，0，－40）T，B2不是可行基。
1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．
maxZ=x1+3x2⎧-2x1+x2≤2（1⎪
2x+3x≤12⎨12⎪x,x≥0⎩12
【解】图解法
最优解X=（,,Z=
424
minZ=-3x1-5x2
⎧x1+2x2≤6⎪（2⎪x1+4x2≤10⎨
⎪x1+x2≤4⎪⎩x1≥0,x2≥0
【解】图解法
该题是退化基本可行解，5个基本可行解对应4个极点。
1.11用单纯形法求解下列线性规划
maxZ=3x1+4x2+x3
⎧2x1+3x2+x3≤1（1⎪
⎨x1+2x2+2x3≤3⎪x≥0,j=1,2,3⎩j
maxZ=2x1+x2-3x3+5x4
⎧x1+5x2+3x3-7x4≤30⎪
（2⎪3x1-x2+x3+x4≤10
⎨
⎪2x1-6x2-x3+4x4≤20⎪xj≥0,j=1,,4⎩
【解】单纯形表：
因为λ7＝3>0并且ai7<0（i=1,2,3，故原问题具有无界解，即无最优解。
maxZ=3x1+2x2-18x3⎧-x1+2x2+3x3≤4⎪（3⎪4x1-2x3≤12⎨
⎪3x1+8x2+4x3≤10⎪⎩x1,x2,x3≥0
原问题具有多重解。
基本最优解X
（1
1273427237=（3,,0,,0及X（2=（,0,,,0T;Z=,最优解的通解可表
841111114
示为X=aX（1+（1-aX（2即
X=（
3411227272
-a,a,-a,-a,0T,（0≤a≤11111811111111
minZ=-2x1-x2-4x3+x4
⎧x1+2x2+x3-3x4≤8⎪
（4⎪-x2+x3+2x4≤10
⎨
⎪2x1+7x2-5x3-10x4≤20⎪xj≥0,j=1,,4⎩
maxZ=3x1+2x2+x3
⎧5x1+4x2+6x3≤25（5）⎪
8x+6x+3x≤24⎨123⎪x≥0,j=1,2,3⎩j
maxZ=5x1+6x2+8x3
（6⎪
⎧x1+3x2+2x3≤50⎨x1+4x2+3x3≤80⎪x≥0,x≥0,x≥0
23⎩1
【解】单纯形表：
1.12分别用大M法和两阶段法求解下列线性规划：
maxZ=10x1-5x2+x3
（1⎪
⎧5x1+3x2+x3=10⎨-5x1+x2-10x3≤15⎪x≥0,j=1,2,3⎩j
【解】大M法。
数学模型为
maxZ=10x1-5x2+x3-Mx5⎧5x1+3x2+x3+x5=10⎪
⎨-5x1+x2-10x3+x4=15⎪x≥0,j=1,2,,5j
两阶段法。
第一阶段：
数学模型为
minw=x5
⎧5x1+3x2+x3+x5=10
⎪
-5x+x-10x+x=15⎨1234⎪x≥0,j=
1,2,,5j
最优解X=（2,0,0；Z=20
minZ=5x1-6x2-7x3
⎧x1+5x2-3x3
≥15⎪
（2⎪5x1-6x2+10x3≤20
⎨
⎪x1+x2+x3=5⎪xj≥0,j=1,2,3⎩
【解】大M法。
数学模型为
minZ=5x1-6x2-7x3+MA1+MA3⎧x1+5x2-3x3-S1+A1=15⎪5x-6x+10x+S=20⎪1232⎨
⎪x1+x2+x3+A3=5⎪所有变量非负
第一阶段：
数学模型为
minw=A1+A3
⎧x1+5x2-3x3-S1+A1=15⎪5x-6x+10x+S=20
⎪1232
⎨
⎪x1+x2+x3+A3=5⎪
所有变量非负
最优解：
X=（0，3.75，1.25；Z=－31.25即X=（0,
155T125,,Z=-444
maxZ=10x1+15x2⎧5x1+3x2≤9
⎪（3⎪-5x1+6x2≤15⎨
⎪2x1+x2≥5⎪⎩x1、x2、x3≥0
【解】大M法。
数学模型为
maxZ=10x1+15x2-Mx7⎧5x1+3x2+x4=9
⎪-5x+6x+x=15⎪125⎨
⎪2x1+x2-x6+x7=5⎪xj≥0,j=
1,2,,7
因为两阶段法
第一阶段：
数学模型为
minZ=x7
⎧5x1+3x2+x4=9⎪-5x+6x+x=15
⎪125
⎨
⎪2x1+x2-x6+x7=5⎪xj≥0,j=1,2,,7
因为maxZ=2x1+3x2-x3+x4
⎧x1-x2+2x3+x4≥9⎪
2x2+x3-x4≤5（4⎪⎪
⎨-2x1+x2-3x3+x4≤-1⎪x+x≥3⎪13⎪⎩xj≥0,j=1,,4
【解】大M法。
数学模型为
maxZ=2x1+3x2-x3+x4-Mx9-Mx10-Mx11⎧x1-x2+2x3+x4-x5+x9=9
⎪
⎪2x2+x3-x4+x6=5⎪
⎨2x1-x2+3x3-x4-x7+x10=1⎪x+x3-x8+x11=3⎪1⎪xj≥0,j=
1,2,,11
⎡21⎤
1.13在第1.9题中，对于基B=⎢⎥,求所有变量的检验数λj（j=1,,4,并判断B是不
40⎣⎦
是最优基．
1⎤⎡0⎢4⎥-1
【解】B=-4,B=⎢⎥,
1⎢1-⎥⎢⎣2⎥⎦
λ=C-CBB-1A
1⎤⎡0⎢⎥⎡2310⎤4
=（5,2,0,0-（5,0⎢⎥⎢⎥
14-201⎦⎢1-⎥⎣⎢⎣2⎥⎦=（5,2,0,0-（5,-5595
2,0,4=（0,2,0,-4
λ=（0,9
0,-524
B不是最优基，可以证明B是可行基。
1.14已知线性规划
maxz=5x1+8x2+7x3+4x4⎧⎪
2x1+3x2+3x3+2x4≤20
⎨3x+5x+4x+2x≤30⎪1234⎩xj
≥0,j=1,,4的最优基为B=⎡23⎢⎤
⎣25⎥，试用矩阵公式求
（1）最优解；⎦
（31及3；（4λ1和λ3。
【解】
⎡-3⎤
B-1=⎢5⎢
44
⎥⎢1⎥,CB=（c4,c2=（4,8,,则⎢⎥⎣-122⎥⎦
（1XT
-1
5
T
5T
B=（x4,x2=Bb=（2
5,最优解X=（0,5,0,2
Z=50（2π=C1BB-=（1,1（3
⎡N1=B-1
P⎢54-3⎤⎡1⎤4⎥⎡2⎤⎢4⎥1=⎢
⎢⎥⎢⎥=⎢⎥⎢-11⎥⎣3⎦⎢1⎥⎣22⎥⎦⎢⎣2⎥⎦
⎡N⎢53⎤⎡3⎤
3=B-1
P4-4⎥⎡3⎤⎢4⎥2=⎢⎢⎥⎢⎥=⎢⎢⎣-11⎥⎣5⎦⎢1⎥
⎥22⎥⎦⎢⎣2⎥⎦
（4
（2单纯形乘子；
升级会员 