运筹与优化复习题含答案.ppt

《运筹与优化复习题含答案.ppt》由会员分享，可在线阅读，更多相关《运筹与优化复习题含答案.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、运筹与运筹与优化复化复习题含答案含答案一一.用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。并说明是唯一最优并说明是唯一最优解，无穷多最优解，无界解还是无可行解。解，无穷多最优解，无界解还是无可行解。1.1.一一.用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。并说明是唯一最优并说明是唯一最优解，无穷多最优解，无界解还是无可行解。解，无穷多最优解，无界解还是无可行解。2.2.二二.已知线性规划问题已知线性规划问题:1.1.用单纯形法求解；用单纯形法求解；2.2.写出其对偶规划；并根据对偶理论，直接写出对偶规划写出其对偶规划；并根据对偶理论，直接写出对偶规划的最优解；的最

2、优解；3.3.试做如下灵敏度分析：试做如下灵敏度分析：(1)(1)当当b b1 1由由1414变为变为1010时，最优解有何变化？时，最优解有何变化？(2)(2)最优基不变的情况下，最优基不变的情况下，b b2 2的变化范围？的变化范围？(3)(3)当当c c1 1由由1 1变为变为1010时，最优解有何变化？时，最优解有何变化？(4)(4)当当p p2 2由由 变为变为 时，最优解有何变化？时，最优解有何变化？76【】最最优优单单纯纯形形表表1.1.标准形：标准形：最优解最优解x x*=(6,0,0)=(6,0,0)T T,最优值最优值z z*=61=6=61=6 2.2.原问题原问题:对偶

3、问题对偶问题:根据对偶理论，对偶规划的最优解为根据对偶理论，对偶规划的最优解为Y Y*=(0,1)=(0,1)。3(1).3(1).当当b b1 1由由1414变为变为1010时，最优解有何变化？时，最优解有何变化？原原最最优优单单纯纯形形表表-2-2用用对对偶偶单单纯纯法法4/31/21/2【】新新最最优优单单纯纯形形表表最优解变为最优解变为x x*=(6,0,1)=(6,0,1)T T,最优值变为最优值变为z z*=5=5 原原最最优优单单纯纯形形表表(2)(2)最优基不变的情况下，最优基不变的情况下，b b2 2的变化范围？的变化范围？原原最最优优单单纯纯形形表表(3)(3)当当c c1

4、 1由由1 1变为变为2 2时，最优解有何变化？时，最优解有何变化？2 22 2-6-6-1-1-2-2仍仍是是最最优优单单纯纯形形表表所以最优解不变。所以最优解不变。(4)(4)当当p p2 2由由 变为变为 时，最优解有何变化？时，最优解有何变化？-3-34 41 11/21/2-【4 4】原原最最优优单单纯纯形形表表用用单单纯纯形形法法最优解变为最优解变为x x*=(15/2,1/2,0)=(15/2,1/2,0)T T,最优值变为最优值变为z z*=13/2.=13/2.三三.已知线性规划问题已知线性规划问题:1.1.用大用大M M法求解；法求解；2.2.写出其对偶规划；写出其对偶规划

5、；3.3.试做如下灵敏度分析：试做如下灵敏度分析：(1)(1)当当b b2 2由由2 2变为变为1111时，最优解有何变化？时，最优解有何变化？(2)(2)最优基不变的情况下，最优基不变的情况下，c c1 1的变化范围？的变化范围？(3)(3)当当p p2 2由由 变为变为 时，最优解有何变化？时，最优解有何变化？1.1.标准形：标准形：大大M M规划：规划：大大M M规划：规划：42【】4/5-【】6-【】最最优优单单纯纯形形表表最优解最优解x x*=(2,0,6)=(2,0,6)T T,最优值最优值z z*=-10.=-10.2.2.原问题原问题:对偶问题对偶问题:原问题变形为：原问题变形

6、为：3(1).3(1).当当b b2 2由由2 2变为变为1111时，最优解有何变化？时，最优解有何变化？原原最最优优单单纯纯形形表表新新最最优优单单纯纯形形表表最优解变为最优解变为x x*=(0,0,8)=(0,0,8)T T,最优值变为最优值变为z z*=-8=-8。-1-141【】用用对对偶偶单单纯纯法法9 9原原最最优优单单纯纯形形表表(2)(2)最优基不变的情况下，最优基不变的情况下，c c1 1的变化范围？的变化范围？-2+-2+c c1 1-2+-2+c c1 1(3)(3)当当p p2 2由由 变为变为 时，最优解有何变化？时，最优解有何变化？原原最最优优单单纯纯形形表表最优解

7、不变。最优解不变。2 2-3-3-1-1仍仍是是最最优优单单纯纯形形表表 四四.已知线性规划问题：已知线性规划问题：(1)(1)写出其对偶问题；写出其对偶问题；(2)(2)已知原问题的最优解为已知原问题的最优解为 ，试用对偶理论找出其对，试用对偶理论找出其对偶问题的最优解。偶问题的最优解。(1)(1)写出其对偶规划；写出其对偶规划；原问题原问题:对偶问题对偶问题:(2)(2)已知原问题的最优解已知原问题的最优解 ，试用对偶理论，试用对偶理论找出其对偶问题的最优解。找出其对偶问题的最优解。将将 代入代入 ，得得为严格不等式，为严格不等式，又又解得解得五五.写出下列线性规划的对偶问题。写出下列线性

8、规划的对偶问题。解：原问题变形为：解：原问题变形为：原问题：原问题：对偶问题：对偶问题：六六.求解下列运输问题。求解下列运输问题。解解:(1)(1)运输不平衡问题，总销量运输不平衡问题，总销量 总产量，需增加虚拟产地总产量，需增加虚拟产地A A4 4(2)(2)求出初始可行方案求出初始可行方案(最小元素法最小元素法)0 08 83 37 7-1-13 31 1-8-8(2)(2)(3)(3)(1)(1)(5)(5)(-1)(-1)(2)(2)(5)(5)(5)(5)(1)(1)(+)(+)(-)(-)(+)(+)(-)(-)(+0)(+0)(-0)(-0)(+0)(+0)(-0)(-0)(3)

9、(3)用位势法求出各非基变量检验数用位势法求出各非基变量检验数(4)(4)有负检验数，用闭回路调整，得新的运输方案。有负检验数，用闭回路调整，得新的运输方案。(0)(0)用位势法求出各非基变量检验数用位势法求出各非基变量检验数无负检验数，当前运输方案为最优运输方案。无负检验数，当前运输方案为最优运输方案。0 09 93 37 7-1-14 40 0-9-9(2)(2)(2)(2)(4)(4)(1)(1)(6)(6)(5)(5)(2)(2)(1)(1)最小运费为最小运费为440440。七七.判断下列运输方案是否最优，若不是，试求出最优方案。判断下列运输方案是否最优，若不是，试求出最优方案。0 0

10、1212161613131 12020-10-100 0(8)(8)(2)(2)(15)(15)(2)(2)(2)(2)(-1)(-1)(0)(0)(10)(10)(+)(+)(-)(-)(+)(+)(-)(-)(+)(+)(-)(-)(+20)(+20)(-20)(-20)(+20)(+20)(-20)(-20)(+20)(+20)(-20)(-20)0 01212161613130 02121-10-100 0(8)(8)(2)(2)(14)(14)(1)(1)(1)(1)(1)(1)(-1)(-1)(10)(10)0 01212161613131 12020-10-100 0(8)(8)

11、(2)(2)(2)(2)(2)(2)(-1)(-1)(0)(0)(10)(10)(+20)(+20)(-20)(-20)(-20)(-20)(+20)(+20)(-20)(-20)(+20)(+20)(15)(15)(+)(+)(+0)(+0)(-)(-)(+)(+)(-)(-)(+)(+)(-)(-)(-0)(-0)(+0)(+0)(-0)(-0)(+0)(+0)(-0)(-0)0 01313171713130 02121-11-110 0(7)(7)(1)(1)(14)(14)(0)(0)(0)(0)(1)(1)(1)(1)(11)(11)无负检验数，当前运输方案为最优运输方案。无负检验数

12、，当前运输方案为最优运输方案。八八.求解下列指派问题。求解下列指派问题。-17-17-16-16-23-23-18-18-16-16-1-1解：解：(1)(1)变换效率矩阵，使各变换效率矩阵，使各行各列均有行各列均有0 0元素。元素。(2 2)试指派试指派(3)(3)独立独立0 0元素的个数元素的个数m m4545，故画覆盖所，故画覆盖所有有0 0元素的最少直线调整矩阵。元素的最少直线调整矩阵。没被覆盖的没被覆盖的最小元素为最小元素为1 1；没覆盖元素没覆盖元素减减1 1，直线，直线交叉元素加交叉元素加1 1。(4 4)重新试指派重新试指派独立独立0 0元素的个数元素的个数m m5=5=5 5

13、，故当前指派为最优指派。，故当前指派为最优指派。总费用为总费用为:Z:Z=1717+1616+2323+1919+1717=9292九九.求求v v1 1到其它各点的最短路？到其它各点的最短路？656523101244v1v9v4v8v6v105159v3v78v5v21063112120,v18,v110,v113,v313,v314,v514,v3/v617,v619,v922,v8656523101244v1v9v4v8v6v105159v3v78v5v21063112120,v18,v110,v113,v313,v314,v514,v3/v617,v619,v922,v8v1v2v5v

14、3d(v1,v2)=14v1v3d(v1,v3)=8656523101244v1v9v4v8v6v105159v3v78v5v21063112120,v18,v110,v113,v313,v314,v514,v3/v617,v619,v922,v8v1v4d(v1,v4)=10d(v1,v5)=13v1v5v3656523101244v1v9v4v8v6v105159v3v78v5v21063112120,v18,v110,v113,v313,v314,v514,v3/v617,v619,v922,v8v1v6v3d(v1,v6)=13v1v3d(v1,v7)=14v7或 v1v6v3v765

15、6523101244v1v9v4v8v6v105159v3v78v5v21063112120,v18,v110,v113,v313,v314,v514,v3/v617,v619,v922,v8v1v6v3d(v1,v8)=19v1v3d(v1,v9)=17v6v8v9v9656523101244v1v9v4v8v6v105159v3v78v5v21063112120,v18,v110,v113,v313,v314,v514,v3/v617,v619,v922,v8v1v6v3d(v1,v10)=22v8v9v1032-14-2v2v3v1v5-4-1v4-3-26十十.求求v v1 1到到v

16、v5 5的最短路？的最短路？(2)(2)反向追踪找出最短路径：反向追踪找出最短路径：v1v2v3v4v5v1v2v3v4v5040-26-10302-10d(1)04d(2)04210d(3)042512-4-3-2d(4)04257d(5)0425732-14-2v2v3v1v5-4-1v4-3-26解解:(1)(1)逐次逼近法逐次逼近法v4v5v3v2v1d(v1,v5)=7十一十一.求下图所示网络的最大流，并写出最小截集及其截量？求下图所示网络的最大流，并写出最小截集及其截量？(2，0)(24，7)(7，7)v10(7，7)v9(7，7)(5，4)(4，4)vtvsv2v8v4v7(18

17、，0)(30，11)(6，6)v3v6(24，0)(3，0)v5v1(20，10)(22，7)(8，4)(7，0)(6，4)(20，10)(2，0)(12，0)(13，0)(19，0)(4，4)(19，7)(15，6),vs19,vs10,vs18,v11,v14,v23,v32,v52,v8(2，0)(24，7)(7，7)v10(7，7)v9(7，7)(5，4)(4，4)vtvsv2v8v4v7(18，0)(30，11)(6，6)v3v6(24，0)(3，0)v5v1(20，10)(22，7)(8，4)(7，0)(6，4)(20，10)(2，0)(12，0)(13，0)(19，0)(4，4)

18、(19，7)(15，6),vs19,vs10,vs18,v11,v14,v23,v32,v52,v8(2，0)(24，7)(7，7)v10(7，7)v9(7，7)(5，4)(4，4)vtvsv2v8v4v7(18，2)(30，13)(6，6)v3v6(24，0)(3，0)v5v1(20，10)(22，7)(8，4)(7，0)(6，6)(20，10)(2，2)(12，0)(13，0)(19，0)(4，4)(19，7)(15，6),vs17,vs10,vs16,v11,v14,v23,v3 标号不能进行，且终点标号不能进行，且终点v vt t没标号，所以当前流为最大流。最大流量为没标号，所以当前流

19、为最大流。最大流量为13+10=2313+10=23。(2，0)(24，7)(7，7)v10(7，7)v9(7，7)(5，4)(4，4)vtvsv2v8v4v7(18，2)(30，13)(6，6)v3v6(24，0)(3，0)v5v1(20，10)(22，7)(8，4)(7，0)(6，6)(20，10)(2，2)(12，0)(13，0)(19，0)(4，4)(19，7)(15，6),vs17,vs10,vs16,v11,v14,v23,v3 最小截集为最小截集为(v(v3 3,v,v8 8),(v),(v5 5,v,v8 8),(v),(v5 5,v,v9 9),(v),(v4 4,v,v10

20、10),(v),(v2 2,v,v6 6,最小截量为最小截量为4+2+7+4+6=234+2+7+4+6=23。十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(1)(1)到电话间就能打电话的概率；到电话间就能打电话的概率；(2)(2)电话间至少有电话间至少有1 1人的概率；人的概率；(3)(3)电话间内平均顾客数；电话间内平均顾客数；(4)(4)每人在电话间的平均逗留时间；每人在电话间的平均逗留时间；(5)(5)电话间内等待打电话的平

21、均人数；电话间内等待打电话的平均人数；(6)(6)每人的平均等待时间；每人的平均等待时间；(7)(7)顾客在电话间至少逗留顾客在电话间至少逗留1010分钟的概率。分钟的概率。解：解：这是一个这是一个M/M/1/M/M/1/模型问题模型问题十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(1)(1)到电话间就能打电话的概率；到电话间就能打电话的概率；解：解：这是一个这是一个M/M/1/M/M/1/模型问题模型问题十二十二.某电话间来打电话

22、的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(2)(2)电话间至少有电话间至少有1 1人的概率；人的概率；解：解：这是一个这是一个M/M/1/M/M/1/模型问题模型问题十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(3)(3)电话间内平均顾客数；电话间内平均顾客数；解：解：这是一个这是一个M/M/

23、1/M/M/1/模型问题模型问题十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(4)(4)每人在电话间的平均逗留时间；每人在电话间的平均逗留时间；解：解：这是一个这是一个M/M/1/M/M/1/模型问题模型问题十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(5)(5)电话间内

24、等待打电话的平均人数；电话间内等待打电话的平均人数；解：解：这是一个这是一个M/M/1/M/M/1/模型问题模型问题十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指数分布,平均每次平均每次2 2分钟分钟,求：求：(6)(6)每人的平均等待时间；每人的平均等待时间；解：解：这是一个这是一个M/M/1/M/M/1/模型问题模型问题十二十二.某电话间来打电话的人数服从泊松分布某电话间来打电话的人数服从泊松分布,平均每小时平均每小时2525人人,每次通话时间服从负指数分布每次通话时间服从负指

25、数分布,平均每次平均每次2 2分钟分钟,求：求：(7)(7)顾客在电话间至少逗留顾客在电话间至少逗留1010分钟的概率。分钟的概率。十三十三.某私人某私人诊诊所，候所，候诊诊室容室容纳纳的病人不能超的病人不能超过过6 6个个,病人按病人按PoissonPoisson过过程到达程到达诊诊所所,平均平均间间隔隔时间为时间为3 3分分钟钟，每个病人，每个病人诊诊断断时间时间服从（服从（负负）指数分布，平均每小）指数分布，平均每小时时3030人人,求求:(1)(1)病人看病不必等待的概率；病人看病不必等待的概率；(2)(2)有效到达率；有效到达率；(3)(3)诊诊所的平均病人数；所的平均病人数；(4)

26、(4)病人到达能找到空位的概率。病人到达能找到空位的概率。十三十三.某私人某私人诊诊所，候所，候诊诊室容室容纳纳的病人不能超的病人不能超过过6 6个个,病人按病人按PoissonPoisson过过程到达程到达诊诊所所,平均平均间间隔隔时间为时间为3 3分分钟钟，每个病人，每个病人诊诊断断时间时间服从（服从（负负）指数分布，平均每小）指数分布，平均每小时时3030人人,求求:解：解：这是一个这是一个M/M/1/M/M/1/N/模型问题模型问题(1)(1)病人看病不必等待的概率；病人看病不必等待的概率；(2)(2)有效到达率；有效到达率；十三十三.某私人某私人诊诊所，候所，候诊诊室容室容纳纳的病人

27、不能超的病人不能超过过6 6个个,病人按病人按PoissonPoisson过过程到达程到达诊诊所所,平均平均间间隔隔时间为时间为3 3分分钟钟，每个病人，每个病人诊诊断断时间时间服从（服从（负负）指数分布，平均每小）指数分布，平均每小时时3030人人,求求:解：解：这是一个这是一个M/M/1/M/M/1/N/模型问题模型问题(3)(3)诊诊所的平均病人数；所的平均病人数；十三十三.某私人某私人诊诊所，候所，候诊诊室容室容纳纳的病人不能超的病人不能超过过6 6个个,病人按病人按PoissonPoisson过过程到达程到达诊诊所所,平均平均间间隔隔时间为时间为3 3分分钟钟，每个病人，每个病人诊诊

28、断断时间时间服从（服从（负负）指数分布，平均每小）指数分布，平均每小时时3030人人,求求:解：解：这是一个这是一个M/M/1/M/M/1/N/模型问题模型问题(4)(4)病人到达能找到空位的概率。病人到达能找到空位的概率。十三十三.某私人某私人诊诊所，候所，候诊诊室容室容纳纳的病人不能超的病人不能超过过6 6个个,病人按病人按PoissonPoisson过过程到达程到达诊诊所所,平均平均间间隔隔时间为时间为3 3分分钟钟，每个病人，每个病人诊诊断断时间时间服从（服从（负负）指数分布，平均每小）指数分布，平均每小时时3030人人,求求:解：解：这是一个这是一个M/M/1/M/M/1/N/模型问

29、题模型问题十四十四.用图解法求解下列矩阵对策。用图解法求解下列矩阵对策。A=-55614-44-5614-45-510a2a1a3且且x x4 4*=0=0IIII取混合策略取混合策略(y,1-y)(y,1-y)，I I分别取纯策略分别取纯策略a a1,1,a a2 2,a a3 3时，时，IIII的的支付支付分别为：分别为：V=-5y+5(1-y)V=-5y+5(1-y)V=1y+4(1-y)V=1y+4(1-y)V=6y-4(1-y)V=6y-4(1-y)yvA=-55614-44-5y1-yy*V=1y+4(1-y)V=1y+4(1-y)V=6y-4(1-y)V=6y-4(1-y)y y

30、*=8=81313 V VG G=28/13=28/13Y Y*(8/13,28/138/13,28/13)T T614-45-510a2a1a3且且x x4 4*=0=0yvA=-55614-44-5y1-yy*局中人局中人I I的最优混合策的最优混合策略只由略只由a a2 2和和a a3 3组成。组成。x x2 2*+6x+6x3 3*=28/13=28/13，4x4x2 2*-4x-4x3 3*=28/13=28/13，x x2 2*+x+x3 3*=1=1 x x2 2*=10/1310/13，x x3 3*=3/33/3，X X*(0,10/13,3/13,00,10/13,3/13

31、,0)T T十五十五.用图解法求解下列矩阵对策。用图解法求解下列矩阵对策。A=126470357146120且且y y4 4*=0=0I I取混合策略取混合策略(x,1-x)(x,1-x)，IIII分别取纯策略分别取纯策略 1,1,2 2,3 3时，时，I I的的赢得赢得分别为：分别为：V=x+6(1-x)V=x+6(1-x)V=2x+4(1-x)V=2x+4(1-x)V=7x+0(1-x)V=7x+0(1-x)xv1-xxx*V=2x+4(1-x)V=2x+4(1-x)V=7x+0(1-x)V=7x+0(1-x)x x*=4/11=4/11 V VG G=28/11=28/11X X*(4/11,7/114/11,7/11)T TA=12647035 1 1 2 2 3 37146120 2 2 1 1 3 3且且y y4 4*=0=0 xv1-xxx*A=12647035 局中人局中人IIII的最优混合策的最优混合策略只由略只由 2 2和和 3 3组成。组成。2y 2y2 2*+7y+7y3 3*=28/11=28/11，4y4y2 2*+0y+0y3 3*=28/11=28/11，y y2 2*+y+y3 3*=1=1 y y2 2*=7/97/9，y y3 3*=2/92/9，Y Y*(0,7/9,2/9,00,7/9,2/9,0)T T谢谢观赏谢谢观赏