欢迎来到天天文库
浏览记录
ID:13115821
大小:630.00 KB
页数:12页
时间:2018-07-20
《运筹学习题答案注释(第2章)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、运筹学习题答案及注释2.3已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-32所示,求表中各括弧内未知数的值。cj322000CB基bx1x2x3x4x5x60x4(b)1111000x515(a)120100x6202(c)1001cj-zj3220000x45/400(d)(l)-1/4-1/43x125/410(e)03/4(i)2x25/201(f)0(h)1/2cj-zj0(k)(g)0-5/4(j)解:最后结果如下:cj322000CB基bx1x2x3x4x5x60x4(10)1111000x515(2)12010
2、0x6202(3)1001cj-zj3220000x45/400(1/4)(1)-1/4-1/43x125/410(5/4)03/4(-1/4)2x25/201(-1/2)0(-1/2)1/2cj-zj0(0)(-3/4)0-5/4(-1/4)注释:由题中初始单纯形表及、最终单纯形表,我们可以看出:在初始单纯形表中,先选x1进基,选x5出基,做变换;然后再选x2进基,选x6出基,做变换,则得到最终单纯形表。2.7给出线性规划问题。maxst.要求:(1)写出其对偶问题;(2)已知原问题最优解为X*=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优
3、解。解:(1)其对偶问题为:min运筹学习题答案及注释第12页st.(2)用单纯形法解原问题,将原问题化成标准形式如下:maxst.因此,可得如下单纯形表:cj24110000CB基bx1x2x3x4x5x6x7x80x58130110000x66210001000x76011100100x8911100001cj-zj24110000因4≥2≥1,所以选x2进基,因8/3≤6≤9,故选x5出基,则得cj24110000CB基bx1x2x3x4x5x6x7x84x28/31/3101/31/30000x610/35/300-1/3-1/31000x710/
4、3-1/3012/3-1/30100x819/32/301-1/3-1/3001cj-zj2/301-1/3-4/3000因1≥2/3,所以选x3进基,因10/3≤19/3,故选x7出基,则得cj24110000CB基bx1x2x3x4x5x6x7x84x28/31/3101/31/30000x610/35/300-1/3-1/31001x310/3-1/3012/3-1/30100x83100-100-11cj-zj100-1-10-10因1≥0,所以选x1进基,因(10/3)/(5/3)≤3/1≤(8/3)/(1/3),故选x6出基,则得cj24110
5、000CB基bx1x2x3x4x5x6x7x84x220102/52/5-1/5002x12100-1/5-1/53/500运筹学习题答案及注释第12页1x340013/5-2/51/5100x81000-4/51/5-3/5-11cj-zj000-4/5-4/5-3/5-10所以,最优解为:X*=(2,2,4,0,0,0,0,1),代入目标函数得z=16。其对偶问题得最优解为:X*=(4/5,3/5,1,0,0,0,0,4/5),代入目标函数得w=16。2.9用对偶单纯形法求解下列线性规划问题。(2)minst.解:先将问题改写为:maxst.约束条件两
6、端乘“-1”得maxst.列出单纯行表,并用对偶单纯形法求解步骤进行计算,其过程如下:cj-5-2-400CB基bx1x2x3x4x50x4-4-3-1-2100x5-10-6-3-501cj-zj-5-2-400因-10≤-4,所以选x5出基,因2/3≤4/5≤5/6,故选x2进基,则得cj-5-2-400CB基bx1x2x3x4x50x4-2/3-10-1/31-1/3-2x210/3215/30-1/3cj-zj-10-2/30-2/3选x4出基,因1≤2,故选x1进基,则得cj-5-2-400CB基bx1x2x3x4x5-5x12/3101/3-1
7、1/3-2x220112-1cj-zj00-1/3-1-1/3运筹学习题答案及注释第12页将最优解代入目标函数,得目标值:min2.10考虑如下线性规划问题:minst.要求:(1)写出其对偶问题;(2)用对偶单纯形法求解原问题;(3)用单纯形法求解其对偶问题;(4)对比(2)与(3)中每步计算得到的结果。解:(1)其对偶问题为:maxst.(2)将原问题改写为:maxst.约束条件两端乘“-1”得maxst.因此,可得如下初始单纯形表:cj-60-40-80000CB基bx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x
8、6-3-2-2-2001cj-zj-60-40-80000因-4≤
此文档下载收益归作者所有