运筹学试题及答案.docx

《运筹学试题及答案.docx》由会员分享，可在线阅读，更多相关《运筹学试题及答案.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结一、填空题：（每空格 2 分，共 16 分）运筹学试题及答案可编辑资料 - - - 欢迎下载精品名师归纳总结1、线性规划的解有唯独最优解、无穷多最优解、无界解和无可行解四种。2、在求运费最少的调度运输问题中，假如某一非基变量的检验数为4，就说明假如在该空格中增加一个运量运费将增加4。 3、“假如线性规划的原问题存在可行解，就其对偶问题肯定存在可行解”，这句话对仍是错？错4、假如某一整数规划： MaxZ=X1+X2 X1+9/14X2 51/14-2X1+X2

2、1/3X1,X 20 且均为整数所对应的线性规划（放松问题）的最优解为X1=3/2 ，X2=10/3 ，MaxZ=6/29，我们现在要对X1 进行分枝，应当分为X1 1和 X1 2。5、在用逆向解法求动态规划时，f ks k 的含义是：从第 k 个阶段到第 n 个阶段的最优解。6. 假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么 D和 B 的关系为D包含 B7. 已知下表是制订生产方案问题的一张LP 最优单纯形表（极大化问题，约束条件均为“”型不等式）其中 X3,X4,X5 为松驰变量。XBbX1X2X3X4X5X4300-213X14/310-1/302/3X2

3、10100-1Cj -Zj00-50-23可编辑资料 - - - 欢迎下载精品名师归纳总结-1问：（ 1）写出 B =211/ 3.00032 / 31可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结T2 对偶问题的最优解：Y （ 5，0，23，0，0）8. 线性规划问题假如有无穷多最优解，就单纯形运算表的终表中必定有为 0 。9. 极大化的线性规划问题为无界解时，就对偶问题_无解 。 某一个非基变量的检验数可编辑资料 - - - 欢迎下载精品名师归纳总结10. 如整数规划的松驰问题的最优解不符合整数要求，假设 Xi =bi 不符合整数要求， I

4、NT（bi ）是不超过 bi 的最大整数，就构造两个约束条件： Xi INT（ bi ） 1 和 Xi INT（ bi ） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。11. 知下表是制订生产方案问题的一张LP最优单纯形表 （极大化问题， 约束条件均为“”型不等式）其中 X4,X5,X6 为松驰变量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj -Zj000-40-9可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 8 页 - - - - - - - - -

5、 -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -T问： 1 对偶问题的最优解：Y 4,0,9,0,0,0（2）写出 B-1 =201104116二、运算题（ 60 分）1、已知线性规划（ 20 分）MaxZ=3X1+4X2 X1+X252X1 +4X2123X1 +2X28 X1,X 20其最优解为：基变量X1X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/2j000-3/4-1/21）写出该线性规划的对偶问题。2）如 C2 从 4 变成 5，最优解是否会发生转变

6、，为什么？3）如 b2 的量从 12 上升到 15，最优解是否会发生变化，为什么？T可编辑资料 - - - 欢迎下载精品名师归纳总结4）假如增加一种产品X6，其 P6=2,3,1解：1) 对偶问题为Minw=5y1+12y2+8y3y1+2y2+3y33y1+4y2+2y34 y1,y2 02) 当 C2 从 4 变成 5 时， 4 =-9/85 =-1/4， C6=4 该产品是否应当投产？为什么？可编辑资料 - - - 欢迎下载精品名师归纳总结由于非基变量的检验数仍旧都是小于0 的，所以最优解不变。 3）当如 b2 的量从 12 上升到 15X9/8 29/81/4由于基变量的值仍旧都是大于

7、0 的，所以最优解的基变量不会发生变化。 4）假如增加一种新的产品，就6P =11/8,7/8， 1/4 T6 =3/80所以对最优解有影响 , 该种产品应当生产2、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共 15 分）。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 销的产的B1B2- - - - - - - - - - - -B3产量A159215A231711A362820

8、销量181216解：初始解为B1B2B3产量/tA11515A21111A3181120销量/t181216运算检验数B1B2B3产量/tA1513015A220011A300020销量/t181216由于存在非基变量的检验数小于0，所以不是最优解，需调整调整为：B1B2B3产量/tA11515A21111A3712120销量/t181216重新运算检验数B1B2B3产量/tA1513015A202211A300020销量/t181216全部的检验数都大于等于0，所以得到最优解3、某公司要把 4 个有关能源工程项目承包给4 个互不相关的外商投标者， 规定每个承包商只能且必需承包一个项目，试在总

9、费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表 2 所示：（15 分）可编辑资料 - - - 欢迎下载精品名师归纳总结项目投标者ABCD可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -甲15182124乙19232218丙26171619丁19212317答最优解为：X=0 1

10、0 01 0 0 00 0 1 00 0 0 1总费用为 504. 考虑如下线性规划问题（24 分）Max z=-5x 1+5x2+13x3s.t.-x1+x2+3x3 20 12x1+4x2+10x3 90x1，x2， x 3 0回答以下问题：1）求最优解2）求对偶问题的最优解3）当 b1 由 20 变为 45，最优解是否发生变化。4）求新解增加一个变量x6，c6=10， a16=3， a26=5，对最优解是否有影响5）c2 有 5 变为 6，是否影响最优解。答：最优解为1Cj-551300CBXBbX1X2X3X4X50X420-1131020/30X59012410019Cj -Z j-

11、55130013X320/3-1/31/311/30200X570/346/322/30-10/3170/22Cj-Zj-2/32/30-13/3013X3185/33-34/33012/11-1/225X235/1123/1110-5/113/22-68/3300-1/11-1/11最优解为 X1=185/33, X 3 =35/112 对偶问题最优解为Y（ 1/22,1/11,68/33,0,0）T 3当 b1=45时X=45/11-11/906由于 X2 的值小于 0，所以最优解将发生变化4）P =3/11,-3/4T6 =217/200所以对最优解有影响。5）当 C2=6可编辑资料 -

12、 - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -1 =-137/33 4 =4/11 5 =-17/22由于4 大于 0 所以对最优解有影响5. 求如下列图的网络的最大流和最小截集 割集 ，每弧旁的数字是（ cij, fij）。（15 分）V15,03,33,3VS（4,1 ）V24,09,38,4V3Vt6,0最大流为： 14V15,33,33,0V2Vs4,44,1

13、9,78,8VtV36,66. 考虑如下线性规划问题（20 分）Max z=3x1 +x2+4x3s.t.6x1+3x2+5x39 3x1+4x2+5x3 8 x1，x2， x 3 0回答以下问题：1）求最优解。2）直接写出上述问题的对偶问题及其最优解。3）如问题中 x2 列的系数变为（ 3，2）T，问最优解是否有变化。4）c2 由 1 变为 2，是否影响最优解，如有影响，将新的解求出。Cj31400CBXBbX1X2X3X4X50X49635100X5834501Cj-Zj314000X413-101-14X38/53/54/5101/5Cj-Zj3/5-11/500-4/53X11/31-

14、1/301/3-1/3可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4X37/5011-1/52/5Cj-Zj0-20-1/5-3/5最优解为 X1=1/3,X3=7/5,Z=33/52) 对偶问题为Minw=9y1+8y26y1+3y233y1+4y215y1+5y24 y1,y20对偶问题最优解为y1=1/5,y2=3/5T23) 如问题中 x2 列

15、的系数变为（ 3，2） 就 P =1/3,1/5T2 =-4/5 0所以对最优解没有影响4）c2 由 1 变为 22 =-1 0所以对最优解没有影响7. 求如下列图的网络的最大流和最小截集 割集 ，每弧旁的数字是（ cij, fij）。（10 分）V14,4 V39,56,3VS3,13,04,1Vt5,37,5V25,4V4解：V14,4V39,76,4Vs3,24,0Vt5,47,7V25,5V4最大流 118. 某厂、三种产品分别经过A、B、C 三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工才能及每件产品的预期利润见表：设备才能 台.hA111100B1045600C2

16、26300单位产品利润 元10641) 建立线性规划模型，求获利最大的产品生产方案。15 分可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -2) 产品每件的利润到多大时才值得支配生产？如产品每件利润增加到50/6 元，求最优方案的变化。 4 分3) 产品的利润在多大范畴内变化时，原最优方案保持不变。2 分4) 设备 A 的才能在什么范畴内变化时，最优基变量

17、不变。3 分5) 如有一种新产品，加工一件需设备A、B、C 的台时各为 1、4、3h，预期每件为 8 元，是否值得生产。 3 分6) 如合同规定该厂至少生产10 件产品，试确定最优方案的变化。3 分解： 1）建立线性规划模型为：MaxZ=10x1+6x2+4x3x1+x2+x3 100 10x1+4x2+5x36002x1+2x2+6x3 300xj 0,j=1,2,3获利最大的产品生产方案为：X*=x1,x2,x3,x4,x5,x6=100/3,200/3,0,0,0,100 Z*=2200/3 2）产品每件利润到20/3才值得生产。假如产品每件利润增加到50/6元，最优方案的变化为： X*

18、=x1,x2,x3,x4,x5,x6 =175/6,275/6,25,0,0,0 Z*=7753）产品的利润在 6,15变化时，原最优方案保持不变。4）设备 A 的才能在 60,150变化时，最优基变量不变。5）新产品值得生产。6）最优方案的变化为： X*=x1,x2,x3,x4,x5,x6 =190/6,350/6,10,0,0,60 Z*=706.79. 给出成性规划问题： 15 分Min z=2x 1 +3x2+6x3x1+2x2+x32-2x 1+x2+3x3 -3xj 0j=1,， 4要求：(1) 写出其对偶问题。 5 分(2) 利用图解法求解对偶问题。5 分(3) 利用2 的结果，

19、依据对偶问题性质写出原问题最优解。5 分解： 1）该问题的 LD为：MaxW=2y1-3y2 y1-2y2 2 2y1+y23 y1+3y26 y1 0,y2 02 用图解法求得LD的最优解为： Y*=y1,y2=8/5,-1/5 W*=19/53 由互补放松定理：原问题的最优解为： X*=x1,x2,x3=8/5,1/5,010. 某部门有 3 个生产同类产品的工厂 产的 ，生产的产品由4 个销售点 销的 出售，各工厂的生产量，各销售点的销售量 单位.t以及各工厂到各销售点的单位运价 元/t示于下表中，要求讨论可编辑资料 - - - 欢迎下载精品名师归纳总结产销学习资料 名师精选 - - -

20、 - - - - - - -第 7 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -产品如何调运才能使总运量最小？10 分B1B2B3B4产量A141241132A22103920A38511644销量1628282496 96解：最优调运方案为： A1-B3 和 B428t和 4t A2-B1 和 B416t和 4t A3-B2 和 B428t和 16t最小总运费为： 460 元11. 求解以下 0-1 规划问题maxz=3x1+2x2-5x 3 -2x 4+3x5 x1+x2 +x3+2x4 +x54 7x1+3x3-4x 4+3x5 811x1-6x 2 +3x4-3x 5 3xj =0 或 1j=1,， 5解：最优解为： x1=x2=1，其他为 0 ，最优目标函数值为5可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 8 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载