运筹学部分课后习题解答.doc_第1页
运筹学部分课后习题解答.doc_第2页
运筹学部分课后习题解答.doc_第3页
运筹学部分课后习题解答.doc_第4页
运筹学部分课后习题解答.doc_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a) 解:由图1可知,该问题的可行域为凸集MABCN,且可知线段BA上的点都为最优解,即该问题有无穷多最优解,这时的最优值为P47 1.3 用图解法和单纯形法求解线性规划问题 a) 解:由图1可知,该问题的可行域为凸集OABCO,且可知B点为最优值点,即,即最优解为这时的最优值为单纯形法:原问题化成标准型为10500b09341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14所以有P78 2.4 已知线性规划问题:求: (1) 写出其对偶问题;(2)已知原问题最优解为,试根据对偶理论,直接求出对偶问题的最优解。解:(1)该线性规划问题的对偶问题为:(2)由原问题最优解为,根据互补松弛性得:把代入原线性规划问题的约束中得第四个约束取严格不等号,即 从而有 得所以对偶问题的最优解为,最优值为P79 2.7 考虑如下线性规划问题:(1) 写出其对偶问题;(2)用对偶单纯形法求解原问题;解:(1)该线性规划问题的对偶问题为:(2)在原问题加入三个松弛变量把该线性规划问题化为标准型:-60-40-80000b0-2-3-2-11000-4-4-1-30100-3-2-2-2001-60-40-80000010-5/45/41-1/12080111/43/40-1/400-10-3/2-1/20-1/210-25-350-150011/6005/311/3-5/6805/6102/30-1/31/6402/3011/301/3-2/300-80/30-20/3-50/3 P81 2.12 某厂生产A、B、C三种产品,其所需劳动力、材料等有关数据见下表。要求:(a)确定获利最大的产品生产计划;(b)产品A的利润在什么范围内变动时,上述最优计划不变;(c)如果设计一种新产品D,单件劳动力消耗为8单位,材料消耗为2单位,每件可获利3元,问该种产品是否值得生产? (d) 如果劳动力数量不增,材料不足时可从市场购买,每单位0.4 元。问该厂要不要购进原材料扩大生产,以购多少为宜。消耗定额产品资源AB C可用量(单位)劳动力材料6 3 53 4 54530产品利润(元/件)3 1 4解:由已知可得,设表示第种产品,从而模型为:a) 用单纯形法求解上述模型为:31400b0456351003034501314000153-101-1463/54/5101/53/5-11/500-4/5351-1/301/3-1/343011-1/52/50-20-1/5-3/5得到最优解为;最优值为 b)设产品A的利润为,则上述模型中目标函数的系数用替代并求解得:1400b351-1/301/3-1/343011-1/52/5-20-1/5-3/50-2+/30-1/5-/3-3/5+/3要最优计划不变,要求有如下的不等式方程组成立解得:从而产品A的利润变化范围为:,即C)设产品D用表示,从已知可得把加入上述模型中求解得:314003b351-1/301/3-1/3243011-1/52/5-4/50-20-1/5-3/51/535/21/2-1/601/6-1/61452/513/151-1/154/150-1/10-59/300-7/30-17/300从而得最优解;最优值为所以产品D值得生产。d)P101 3.1已知运输问题的产销量与单位运价如下表所示,用表上作业法求各题的最优解及最小运费。表3-35产地销地B1B2B3B4产量A1A2A31012227142091611201815255销量5151510解:由已知和最小元素法可得初始方案为产地销地B1B2B3B4产量A1A2A351501501015255销量5151510检验:由于有两个检验数小于零,所以需调整,调整一: 产地销地B1B2B3B4产量A1A2A351501510015255销量5151510 检验:由于还有检验数小于零,所以需调整,调整二:产地销地B1B2B3B4产量A1A2A355101510015255销量5151510检验:从上表可以看出所有的检验数都大于零,即为最优方案最小运费为:表3-36产地销地B1B2B3B4产量A1A2A386549314427372526销量10102015解:因为,即产大于销,所以需添加一个假想的销地,销量为3,构成产销平衡问题,其对应各销地的单位运费都为0。产地销地B1B2B3B4B5产量A1A2A386549314427300072526销量101020153由上表和最小元素法可得初始方案为产地销地B1B2B3B4B5产量A1A2A3911071315372526销量101020153检验: 从上表可以看出所有的检验数都大于零,即为最优方案最小运费为:表3-37 产地销地B1B2B3B4B5产量A1A2A38566M3389746578203030销量2525201020解:因为,即销大于产,所以需添加一个假想的产地,产量为20,构成产销平衡问题,其对应各销地的单位运费都为0。产地销地B1B2B3B4B5产量A1A2A3A485606M3038907460578020303020销量2525201020由上表和最小元素法可得初始方案为产地销地B1B2B3B4B5产量A1A2A3A4520252001015520303020销量2525201020检验: 由于有两个检验数小于零,所以需调整,调整一:产地销地B1B2B3B4B5产量A1A2A3A4205252001051520303020销量2525201020 检验:由于还有检验数小于零,所以需调整,调整二:产地销地B1B2B3B4B5产量A1A2A3A4205252001002020303020销量2525201020检验:从上表可以看出所有的检验数都大于零,即为最优方案最小运费为:P127 4.8 用割平面法求解整数规划问题。a) 解:该问题的松弛问题为:则单纯形法求解该松弛问题得最后一单纯形表为:7900b97/2017/221/2279/210-1/223/2200-28/11-15/11割平面1为:从而有79000b97/2017/221/22079/210-1/223/2200-1/200-7/22-1/22100-28/11-15/1109301001732/71001/7-1/7011/70011/7-22/7000-1-8割平面2为:790003b93010010732/71001/7-1/70011/70011/7-22/700-4/7000-1/7-6/71000-1-8093010010741000-11010010-410400016-70000-2-7由上表可知该问题已经达到整数解了,所以该整数解就是原问题的最优解,即,最优值为P144 5.3 用图解分析法求目标规划模型x1 + x2 + d1- - d1+= 40 x1 + x2 + d2- - d2+= 40+10=50x1 + d3- - d3+= 24 x2 + d4- - d4+= 30min Z = P1 d1-+ P2 d2+ P3(2d3- +1d4-)s.t.x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 c) 解:由下图可知,满足目标函数的满意解为图中的A 点。 用图解分析法求目标规划模型的满意解。解:由下图可知,满足的满意解为区域CDOA; 满足的满意解为闭区域MCDOM; 满足的满意解为图中的阴影部分,即为图中的凸多边形OABCDO 。P170 6.4 求下图中的最小树解:避圈法为:得到最小树为:P171 6.7 用标号法求下图中点到各点的最短路。解:如下图所示:P 173 6.14 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从到的最大流,并标出其最小割集。图中各弧旁数字为容量,括弧中为流量.B) 解:对上有向图进行2F标号得到由于所有点都被标号了,即可以找到增广链,所以流量还可以调整,调整量为1,得由图可知,标号中断,所以已经是最大流了,最大流量等于最小割的容量,最小割为与直线KK相交的弧的集合,即为所以从到的最大流为: C) 解:对上有向图进行2F标号得到由于所有点都被标号了,即可以找到增广链,所以流量还可以调整,调整量为1,得由图可知,标号中断,所以已经是最大流了,最大流量等于最小割的容量,最小割为与直线KK相交的弧的集合,即为,所以从到的最大流为: P193 7.1 根据下表给定的条件,绘制PERT网络图。表7-8作业代号 a1 a2 a3 b1 b2 b3 c1 c2 c3紧前作业无 a1 a2 无 b1 b2 a1,b1 a2,b2,c1 a3,b3,c

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论