资源描述:
《《管理运筹学》习题2解答》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、《管理运筹学》习题2解答《管理运筹学》习题2一、分别用图解法和单纯形法(用大M法和两阶段法都可以)求解下列线性规划问题:minz??2x1?4x2?4x1?2x2?6?s.t.?x1?x2?1?x?2,x自由2?1二、以下各模型目标函数都是求最大值,根据各自的最优表下结论(要判断解的类型):(1)12312求量以及每万吨煤炭的运价(千元)如表1所示。问如何调运煤炭,使得总运输费用最小?表1产销平衡表和单位运价表要求:(1)请建立该问题的线性规划模型,如果有必要再化为标准问题。(2)用表上作业法求解:用最小元素法确定初
2、始方案;用闭回路法或者位势法验证初始方案是否最优?如果非最优,请用闭回路法调整,直至求出最优方案。四、某工厂生产两种产品。甲、乙两种产品每件生产工时分别为6小时,2小时,总生产工时计划定为24小时。甲产品和乙产品每生产一件对A原料消耗量都为1单位,原料A计划购买量为5单位。乙产品每生产品一件对B原料的消耗为5单位,甲产品生产不需要B原料,该原料计划购买量为5单位。要求依次满足下列目标:(1)计划工时数尽可能充分利用但最好不要超过;(2)原料A购买量最好不超过计划规定量;(3)原料B购买量最好也不要超过计划购买量。请建
3、立该问题的线性目标规划模型并用图解法或单纯型法求解。一.分别用图解法和单纯形法求解下列线性规划问题:minz??2x1?4x2?4x1?2x2?6?s.t.?x1?x2?1?x?2,x自由2?1解:(一)用图解法求解,过程如下:1.各种约束条件如图1所示,其中线段AB为可行域。A点和B点坐标分别为(4/3,1/3)、(2,1)2.画出目标函数的一条等值线:-2x1+4x2=0,如图所示。它沿法线向下平移,目标函数值z3.当目标函数平移到A(4/3,1/3)点时,z→minz。*T所以本题有唯一最优解X=(4/3,1/
4、3),最优目标函数值z*=-2×4/3+4×1/3=-4/3。(二)用单纯形法求解(用大M法和两阶段法都可),[大M法求解]1.将原模型化为标准型(1)令y1=2-x1≥0,?2y1?y2?y3?1………③x2=y2-y3(其中y2,y3≥0)………①?则x1=2-y1………②s.t.?y1?y2?y3?1………④将①、②代入原约束条件,并化简整理得到:?(2)在③式左边加入松弛变量y4,化为:?yj?0j?1,2,32y1-y2+y3+y4=1④式不用标准化,已经是标准形式。(3)将①、②代入目标函数得:minz=
5、-4+2y1+4y2-4y3+0·y4令w=-z,则目标函数化为:maxw=4-2y1-4y2+4y3+0·y4所以,标准型即:??maxw?4?2y1?4y2?4y3?0?y4?2y1?y2?y3?y4?1?s.t.?y1?y2?y3?1??yj?0?j?1,2,3?………⑤2.在⑤式左边加入人工变量y5,并在目标函数中加入罚因子M(M为很大的正数),则标准型化为规范型,如下所示:maxw?4?2y1?4y2?4y3?0?y4?M?y5?2y1?y2?y3?y4?1?s.t.?y1?y2?y3?y5?1??yj?0
6、?j?1,2,?,5?4.结论:因为所有非基变量检验数σj≤0(j=3,4,5),且σ3=0,人工变量y5=0,所以上述规范型模型有无穷多最优解,当前基可行解(2/3,1/3,0,0,0)T为最优解(其他最优解不能通过单纯形*****法求出,∵?)。相应的x=2-yx=y-ymin1=2-2/3=4/3;1223=1/3-0=1/3;a13?0?0,a?23??1?0z=-maxw=-(-8/3+4)=-4/3。[用两阶段法求解](接大M法第2步以后)第一阶段:先列单纯形表求解如下模型:maxw??1?y5?2y1?
7、y2?y3?y4?1?s.t.?y1?y2?y3?y5?1?yj?0?j?1,2,?,5?因为所有非基变量检验数σj≤0(j=3,4,5),所以停止迭代,w=0,进入第二阶段继续求解。第二阶段,去掉人工变量y5,恢复非人工变量目标系数,在以上最后一步基础上继续求解:二.以下各模型目标函数都是求最大值,根据各自的最优表下结论(要判断解的类型):解:(1)结论:因为所有非基变量检验数σj≤0(j=3,4,5,6,7),σ3=0且a??1335?0、人工变所以,本题最优解其中一个为:X1=(4/5,9/5,0,0,0,0,
8、0);另一个最优解为:X2*=(2,3,0,0,0,0,0)T;maxz=-3×9/5-2×4/5=-1×3-2×2=-7(2)结论:因为所有非基变量检验数σj≤0(j=2,4,5,6)但人工变量x7=1/2≠0,所以此问题无可行解。(3)结论:非基变量检验数σ4=5/4>0,而ai4≤0(i=1,2,3),故此问题无有限最优解(或为无界