《运筹学试题与答案11》由会员分享，可在线阅读，更多相关《运筹学试题与答案11（20页珍藏版）》请在金锄头文库上搜索。
1、运筹学试题及答案一、填空题：（每空格 2 分，共 16 分）1、 线性规划的解有唯一最优解、无穷多最优解、无界解和无可行解四种。2、 在求运费最少的调度运输问题中,如果某一非基变量的检验数为4 ,则说明如果在该空格中增加一个运量运费将增加4。3、 “如果线性规划的原问题存在可行解,则其对偶问题一定存在可行解”，这句话对还是错？错4、如果某一整数规划：MaxZ=X1+X2X+9/14X, 51/14-2X+X,1/3X1ZX20且均为整数所对应的线性规划（松弛问题）的最优解为X=3/2 , X2=10/3，MaxZ=6/29 ,我们现在要对X进行 分枝,应该分为 X1S1 和 X12。5、 在用
2、逆向解法求动态规划时，fk（sk）的含义是： 从第k个阶段到第n个阶段的最优解。6、假设某线性规划的可行解的集合为D ,而其所对应的整数规划的可行解集合为B ,那么D和B的关 系为 D包含B7、已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题,约束条件均为“V型不等式）其中X3,X4,X5为松驰变量。XBbX1X2X3X4X5X4300-213X14/310-1/302/3X210100-1Cj-Zj00-50-23-213、问：（1 ）写出 B-1= -1/3 .0 2/3INT ( bj)+ 1和XiGNT ( Q ),分别将其并入上述松驰问题中， 形成两个分支， 即两个后继问
3、题。11. 知下表是制订生产计划问题的一张LP最优单纯形表(极大化问题,约束条件均为“V型不等式) 其中 X4,X5,X6 为松驰变量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj-Zj000-40-9问：(1)对偶问题的最优解：Y二(4Q9,0Q0)T( 2 ) 写出 B-1=二、计算题（ 60 分）1、已知线性规划（ 20分）MaxZ=3X+4X122X1+4X2123X1+2X2o其最优解为：基变量%X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/26000-3/4-1/21）写出该线
4、性规划的对偶问题。2 ）若C2从4变成5 ,最优解是否会发生改变,为什么？3）若b2的量从12上升到15 ,最优解是否会发生变化,为什么？4 ）如果增加一种产品X ,其P =（2,3,1）t , C =4该产品是否应该投产？为什么？6 6 6解：1）对偶问题为Minw=5y1+12y2+8y3 y1+2y2+3y33y1+4y2 + 2y34y1,y202）当C2从4变成5时,。4=-9/8。5 = -1/4由于非基变量的检验数仍然都是小于 0 的， 所以最优解不变3）当若b2的量从12上升到15X =9/8、29/81/4由于基变量的值仍然都是大于 0 的，所以最优解的基变量不会发生变化4）
5、如果增加一种新的产品，则P6=（11/8,7/8，1/4）T 6o6=3/80所以对最优解有影响,该种产品应该生产2、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共15 分）。销地产地B1B2B3产量A159215A231711A362820销量181216解：初始解为计算检验数销量/t181216由于存在非基变量的检验数小于 0，所以不是最优解，需调整调整为：BiB2B3产量/tAi1515A21111A3712120销量/t181216重新计算检验数B1B2B3产量/tA1513015A202211A300020销量/t181216所有的检验数都大于等于 0，所以得到最优
6、解3、某公司要把 4 个有关能源工程项目承包给 4 个互不相关的外商投标者，规定每个承包商只能且必 须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表 2 所示：15 分）项目投标者、ABCD甲15182124乙19232218丙26171619丁19212317答最优解为：0 1 0 01 0 0 00 0 1 00 0 0 1总费用为 504. 考虑如下线性规划问题（24 分）Max z=-5x +5x +13x1 2 3s.t.-x+x+3x 2012312x!+4x2+10x30回答以下问题：1）求最优解2）求对偶问题的最优解3）当b1由
7、20变为45 ,最优解是否发生变化。4 ）求新解增加一个变量x , c =10 , a =3 , a=5，对最优解是否有影响6 6 16 265）c2有5变为6 ,是否影响最优解。答：最优解为1）Cj-5513000CBXbbX1X2X3X4X50X420-1131020/30X59012410019Cj-Zj-55130013X320/3-1/31/311/30200X570/346/322/30-10/3170/22Cj-Zj-2/32/30-13/3013X3185/3-34/3012/11-1/22335X235/1123/1110-5/113/22-68/300-1/11-1/113
8、最优解为 X1=185/33, X3=35/112) 对偶问题最优解为丫二(1/22,1/11,68/33,0,0 ) t3)当 b1=45 时X二45/11 -11/90由于X2的值小于0 ,所以最优解将发生变化3) P6=(3/11,-3/4)T6。6二217/200所以对最优解有影响。4) 当 C2=6o1=-137/33叮4/11吁-17/22由于O4大于0所以对最优解有影响5.求如图所示的网络的最大流和最小截集(割集),每弧旁的数字是(cij , fj )o(15分)V3 Vt(6,0)(4,1)(9,7) (8,8)VtV3(6,6)6. 考虑如下线性规划问题(20 分)Max z
9、=3x1+x2+4x3s.t.6xl+3x2+5x393xi + 4x2 + 5x30回答以下问题：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-1/301/3-1/34X37/5011-1/52/5Cj-Zj0-20-1/5-3/5最优解为
10、X1=1/3,X3=7/5,Z=33/52）对偶问题为Minw=9y1+8y26y1+3y233y1+4y215y1+5y24 yl,y20对偶问题最优解为 y1=1/5,y2=3/53) 若问题中x2列的系数变为(3 , 2)T则 P2=(1/3,1/5)To2=-4/50所以对最优解没有影响4) c2由1变为2。2 = -1 0所以对最优解没有影响7.求如图所示的网络的最大流和最小截集(割集),每弧旁的数字是(cij , fjj )o(10分)(5,3)(7,5)V2(5,4)V4解：V1 (4,4)V3VsVt(5,4) (7,7)V2 (5,5) V4最大流二118.某厂I、n、皿三种
11、产品分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表：1）建立线性规划模型，求获利最大的产品生产计划。（15 分）2）产品皿每件的利润到多大时才值得安排生产？如产品皿每件利润增加到50/6元,求最优计划 的变化。（4 分）3）产品I的利润在多大范围内变化时,原最优计划保持不变。（2分）4）设备A的能力在什么范围内变化时,最优基变量不变。（3分）5）如有一种新产品,加工一件需设备A、B、C的台时各为1、4、3h ,预期每件为8元,是否值 得生产。 （3 分）6）如合同规定该厂至少生产10件产品皿，试确定最优计划的变化。（3分）解：1)建立线性规划模型为：MaxZ=10x1+6x2+4x3x1+x2+x3s10010x1+4x2 + 5x3*002x
