运筹学(第五版)--习题答案.doc
《运筹学(第五版)--习题答案.doc》由会员分享,可在线阅读,更多相关《运筹学(第五版)--习题答案.doc(63页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上运筹学习题答案第一章(39页)1.1用图解法求解下列线性规划问题,并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。(1)max 5+1050+14,0(2)min z=+1.5+33+2,0(3)max z=2+2-1-0.5+2,0(4)max z=+-03-3,0解:(1)(图略)有唯一可行解,max z=14(2)(图略)有唯一可行解,min z=9/4(3)(图略)无界解(4)(图略)无可行解1.2将下列线性规划问题变换成标准型,并列出初始单纯形表。(1)min z=-3+4-2+54-+2-=-2+3-14-2+3-+22,0,无约束(2)ma
2、x 0 (i=1n; k=1,m)(1)解:设z=-,=-, ,0标准型:Max =3-4+2-5(-)+0+0-M-Ms. t . -4+-2+-+=2+3-+=14-2+3-+2-2-+=2,0 初始单纯形表:3-42-5500-M-Mb-M2-41-21-100012014113-11100014-M2-23-12-20-1102/3-4M3-6M4M-42-3M3M-55-3M0-M00(2)解:加入人工变量,得:Max s=(1/)-M-M-.-Ms.t. (i=1,2,3,n)0, 0, (i=1,2,3n; k=1,2.,m)M是任意正整数初始单纯形表:-M-M-Mb-M1100
3、11000-M10100000-M1001000111-snM0001.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解,并代入目标函数,确定最优解。(1)max z=2+3+4+7 2+3-4=8 -2+6-7=-3,0(2)max z=5-2+3-6+2+3+4=72+2=30(1)解:系数矩阵A是:令A=(,)与线形无关,以(,)为基,为基变量。有 2+3=8+4 -2=-3-6+7令非基变量,=0解得:=1;=2基解=(1,2,0,0为可行解=8同理,以(,)为基,基解=(45/13,0,-14/13,0是非可行解;以(,)为基,基解=(34/5,0,0,7/5是
4、可行解,=117/5;以(,)为基,基解=(0,45/16,7/16,0是可行解,=163/16;以(,)为基,基解=(0,68/29,0,-7/29是非可行解;以(,)为基,基解=(0,0,-68/31,-45/31是非可行解;最大值为=117/5;最优解=(34/5,0,0,7/5。(2)解:系数矩阵A是:令A=(,),线性无关,以(,)为基,有:+2=7-3-42+=3-2令 ,=0得=-1/3,=11/3 基解=(-1/3,11/3,0,0为非可行解;同理,以(,)为基,基解=(2/5,0,11/5,0是可行解=43/5;以(,)为基,基解=(-1/3,0,0,11/6是非可行解;以(
5、,)为基,基解=(0,2,1,0是可行解,=-1;以(,)为基,基解=(0,0,1,1是=-3;最大值为=43/5;最优解为=(2/5,0,11/5,0。1.4分别用图解法和单纯形法求解下列线性规划问题,并指出单纯形迭代每一步相当于图形的哪一点。(1)max z=2+ 3+515 6+224,0(2)max z=2+542123+218,0解:(图略)(1)max z=33/4 最优解是(15/4,3/4)单纯形法:标准型是max z=2+0+0s.t. 3+5+=15 6+2+=24 ,0单纯形表计算:2100b0153510502462014-z0210003041-1/23/42411/
6、301/612-z-801/30-1/313/4011/4-1/8215/410-1/125/24-z-33/400-1/12-7/24解为:(15/4,3/4,0,0 Max z=33/4迭代第一步表示原点;第二步代表C点(4,0,3,0;第三步代表B点(15/4,3/4,0,0 。(2)解:(图略) Max z=34 此时坐标点为(2,6)单纯形法,标准型是:Max z=2+5+0+0+0s.t. +=4 2+=12 3+2+=18,0(表略)最优解 X=(2,6,2,0,0 Max z=34迭代第一步得=(0,0,4,12,18表示原点,迭代第二步得=(0,6,4,0,6,第三步迭代得到
7、最优解的点。1.5以1.4题(1)为例,具体说明当目标函数中变量的系数怎样变动时,满足约束条件的可行域的每一个顶点,都可能使得目标函数值达到最优。解:目标函数:max z=+(1)当0时 =-(/)+z/ 其中,k=-/=-3/5,=-3l k 时, ,同号。当0时,目标函数在C点有最大值当0时,目标函数在原点最大值。l k时,同号。当0, 目标函数在B点有最大值;当0,目标函数在原点最大值。l k 0时, 同号。当0时,目标函数在A点有最大值当0时,目标函数在原点最大值。l k 0时, ,异号。当0, 0时,目标函数在A点有最大值;当0, 0时,目标函数在C点最大值。l k= 时, 同号当0
8、时,目标函数在AB线断上任一点有最大值当0,目标函数在原点最大值。l k= 时, 同号。当0时,目标函数在BC线断上任一点有最大值当0时,目标函数在原点最大值。l k=0时,=0当0时,目标函数在A点有最大值当0,目标函数在OC线断上任一点有最大值(2)当=0时,max z= l 0时,目标函数在C点有最大值l 0时,目标函数在OA线断上任一点有最大值l =0时,在可行域任何一点取最大值。1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题,并指出属于哪类解。(1)max z=2+3-5+152-5+24,0(2)min z=2+3+4+283+26,0(3)max z=10+15+125
9、+3+9-5+6+15152+5,0(4)max z=2-+2+6-2+22-0,0解:(1)解法一:大M法化为标准型:Max z=2+3-5-M+0-Ms.t. +=7 2-5+-+=10,0 M是任意大整数。单纯形表:23-5-M0-Mb-M71111007-M102-510-115-z17M3M+23-4M2M-50-M0-M207/21/211/2-1/24/7251-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-134/7011/72/71/7-1/7245/7106/75/7-1/71/7-z-102/700-50/7-M-16/
10、7-1/7-M+1/7最优解是: X=(45/7,4/7,0,0,0 目标函数最优值 max z=102/7有唯一最优解。解法二:第一阶段数学模型为 min w= + S.t. + + =72 -5 + - + =10,,,0(单纯形表略)最优解X=(45/7,4/7,0,0,0 目标函数最优值 min w=0第二阶段单纯形表为:23-50b34/7011/71/7245/7106/7-1/7-z-102/700-50/7-1/7最优解是X=(45/7,4/7,0,0,0 Max z=102/7(2)解法一:大M法=-z 有max =-min (-)=-min z化成标准形:Max =-2-3
11、-+0+0-M-MS.T. +4+2-+=4 3+2-+=6 ,,,,0(单纯性表计算略)线性规划最优解X=(4/5,9/5,0,0,0 ,0 目标函数最优值 min z=7非基变量的检验数=0,所以有无穷多最优解。两阶段法:第一阶段最优解X=(4/5,9/5,0,0,0,0 是基本可行解,min w=0第二阶段最优解(4/5,9/5,0,0,0,0 min z=7非基变量的检验数=0,所以有无穷多最优解。(3)解:大M法加入人工变量,化成标准型:Max z=10 +15 +12 +0 +0 +0 -M s.t. 5 +3 + + =9 -5 +6 +15 + =15 2 + + - + =5
12、 ,,,,0单纯形表计算略当所有非基变量为负数,人工变量=0.5,所以原问题无可行解。两阶段法(略)(4)解法一:大M法单纯形法,(表略)非基变量的检验数大于零,此线性规划问题有无界解。两阶段法略1.7求下述线性规划问题目标函数z的上界和下界;Max z=+其中:,解:l 求Z的上界Max z=3+6s.t. -+212 2+414,0加入松弛变量,化成标准型,用单纯形法解的,最优解X=(0,7/2,5,0 目标函数上界为z=21存在非基变量检验数等于零,所以有无穷多最优解。l 求z的下界线性规划模型:Max Z= +4s.t. 3+58 4+610 ,0加入松弛变量,化成标准型,解得:最优解
13、为X=(0,8/5,0,1/5 目标函数下界是z=32/51.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量,d,为待定常数,试说明这些常数分别取何值时,以下结论成立。(1)表中解为唯一最优解;(2)表中解为最优解,但存在无穷多最优解;(3)该线性规划问题具有无界解;(4)表中解非最优,对解改进,换入变量为,换出变量为。基b d4100 2-1-301-10 3-500-4100-30解:(1)有唯一最优解时,d0,0,0(2)存在无穷多最优解时,d0,0,=0或d0,=0,0.(3)有无界解时,d0,0,0且(4)此时,有d0,0并且,3/d/41.9某昼夜服务的公交线
14、路每天个时间段内所需司机和乘务员人数如下:班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班,并连续上班8小时,问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解 :设(k=1,2,3,4,5,6)为个司机和乘务人员第k班次开始上班。建立模型:Min z=+s.t. +60 +70 +60 +50 +20 +30, 01.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙,已知各种糖果中ABC含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加
15、工费用及售价如表所示:原料甲乙丙原料成本(元/千克)每月限制用量(千克)A60%15%22000B1.52500C20%60%50%11200加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克,使得获利最大?建立数学模型。解:解:设,是甲糖果中的A,B,C成分,是乙糖果的A,B,C成分,是丙糖果的A,B,C成分。线性规划模型:Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95s.t. -0.4+0.6+0.60 -0.2-0.2+0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7
16、-0.5+0.50 +2000 +2500 +1200, 01.11某厂生产三种产品I、III。每种产品经过AB两道加工程序,该厂有两种设备能完成A工序,他们以,表示;有三种设备完成B工序,分别为,;产品I可以在AB任何一种设备上加工,产品可以在任何规格的A设备上加工,但完成B工序时,只能在设备上加工;产品III只能在,上加工。已知条件如下表,要求安排最优生产计划,使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用IIIIII5106000300791210000321684000250411700078374000200原料费0.250.350.5单价1.252.002.8解:产品1,
17、设,完成A工序的产品,件;B工序时,,,完成B工序的,件,产品,设,完成A工序的产品,件;B工序时,完成B的产品为件;产品111,完成A工序的件,完成B工序的件;+ = + + + = 建立数学模型:Max z=(1.25-0.25)*( + )+(2-0.35)*( + )+(2.8-0.5) -(5 +10 )300/6000-(7 +9 +12 )321/10000-(6 +8 )250/4000-(4 +11 )783/7000-7 *200/4000s.t 5 +10 60007 +9 +12 100006 +8 40004 +11 70007 4000+ = + + + = , 0
18、最优解为X=(1200,230,0,859,571,0,500,500,324 最优值1147.试题:1. (2005年华南理工大学)设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。现有5种饲料可供选择,每种饲料每公斤营养成分的含量及单价如下表所示:试建立既满足动物生长需要,又使费用最省的选用饲料方案的线性规划模型。表 11饲料蛋白质(克)矿物质(克)维生素(毫克)价格(元/公斤)1310.50.2220.510.7310.20.20.446220.35180.50.80.8解题分析:这是一道较简单的数学规划模型问题,根据题意写出约束即可。解题过程:第二章(67页)2.1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第五 习题 答案
限制150内