运筹学试题及答案13

运筹学试题及答案一、填空题：（每空格2分，共16分）和无可行解四种。1、线性规划的解有唯一最优解、无穷多最优解、

无界解则说明

如果在该空格中增2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为

4,

加一个运量运费将增加40

，这句话对还是错？—错

3、

“如果线性规划的原问题存在可行解，贝U其对偶问题一定存在可行解”

4、

如果某一整数规划：

MaxZ=XX2

X19/I4X2W51/14-2XiX^<1/3

X1,X2>0且均为整数

所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29,我们现在要对X进行分枝,应该分为X1<1和X1>20

5.在用逆向解法求动态规划时，fk（Sk）的含义是：

从第k个阶段到第n个阶段的最优解0

6.假设某线性规划的可行解的集合为D,而其所对应的整数规划的可行解集合为

B,那么D和B的关系为D包含B

7.已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“W”型不等式）其中X3,X4,X5为松驰变量。

XbbX茨X3XXX300-213X14/310-1/302/3X210100-1Cj-Zj00-5110-23

〔一2

问：（1）写出B-1=-1/3

；0

⑵对偶问题的最优解：_Y=

8.某一个非基变量的检验数

线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有

为0；

9.极大化的线性规划问题为无界解时，则对偶问题_无解

;

10.若整数规划的松驰问题的最优解不符合整数要求，假设X=bi不符合整数要求，INT（bi）是不超

过bi的最大整数，则构造两个约束条件：Xi^INT（bi）1和XiwINT（b），分别

将其并入上述松驰问题中，形成两个分支，即两个后继问题。11.知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“w”型不等式）其中X4,X5,X6为松驰变量。XbbX茨X3XXXX12110201X32/3001104X510-20116Cj-Zj000-40-9问：（1）对偶问题的最优解:（2）写出B-1=丫=(4,0,9,0,0,0)二、计算题（60分）1、已知线性规划（20分）MaxZ=3X4XrXiX2<52兀4心123兀2心8基变量XX2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4x1100-1/41/2Tj000-3/4-1/2<Xi,X2>0其最优解为:1）2）3）4）解：写出该线性规划的对偶问题。若C2从4变成5,最优解是否会发生改变，为什么？若b2的量从12上升到15,最优解是否会发生变化，为什么？如果增加一种产品X6,其F6=（2,3,1）T，C6=4该产品是否应该投产？为什么?1）对偶问题为Minw=5y112y28y3!12y23y3>3y14y22y3>41,y2>02）当G从4变成5时，（T4=-9/8（T5=-1/4由于非基变量的检验数仍然都是小于0的，所以最优解不变。3）当若b2的量从12上升到15x=9/8"29/81/4丄由于基变量的值仍然都是大于0的，所以最优解的基变量不会发生变化。4）如果增加一种新的产品，则Pe'=（11/8,7/8，-1/4）TT6=3/8>0所以对最优解有影响，该种产品应该生产2、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共15分）。^肖地r地BiB2Rr量Ai59215A31711A62820销量181216解：初始解为BB2B3产量/tA1515A1111A181120销量/t181216计算检验数B1B2B3产量/tA513015A-20011A00020销量/t181216由于存在非基变量的检验数小于0,所以不是最优解，需调整调整为：BB2B3产量/tA11515A1111A712120销量/t181216重新计算检验数BB2B3产量/tA1513015A02211A00020销量/t181216所有的检验数都大于等于0,所以得到最优解3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示：（15分）甲15182124乙19232218丙26171619丁19212317答最优解为：X=01100001000总费用为504.考虑如下线性规划问题（24分）Maxz=-5x15x213x3s.t.广X1X23x3<20J12X14X210X3<901X1,X2,X3>0回答以下问题：1)2)3)4)5)求最优解求对偶问题的最优解当b1由20变为45,最优解是否发生变化。最优解为X=185/33,X3=35/112)对偶问题最优解为丫=(1/22,1/11,68/33,0,0)3)当b1=45时X=求新解增加一个变量X6,C6=10,a16=3,826=5,对最优解是否有影响C2有5变为6,是否影响最优解。

答：最优解为

1)

Cj-5513000CbXbbXX>X3XX0为20-1131020/30X9012410019Cj-乙-5513001320/3-1/31/311/30200%70/346/322/30-10/3170/22Cj-Zj-2/32/30-13/3013%185/33-34/33012/11-1/22535/1123/1110-5/113/22-68/3300-1/11-1/1125/11、

-11/90」

由于X2的值小于0,所以最优解将发生变化

4）

P6'=（3/11,-3/4）T

（T6=217/20>0

所以对最优解有影响。

5）

当06

（T1=-137/33

（T4=4/11

(T5一

（T5=-17/22

由于（T4大于0所以对最优解有影响

6.考虑如下线性规划问题（20分）Maxz=3xiX24x3s.t.j6xi3x25x3<9彳3xi4x25x3<81)2)3)4)LXi,X2,X3>0回答以下问题：求最优解；直接写出上述问题的对偶问题及其最优解；若问题中X2列的系数变为（3,2）T，问最优解是否有变化;C2由1变为2,是否影响最优解，如有影响，将新的解求出。Cj31400CBbX1X2X3X4X50X49635100X5834501Cj-Zj314000X413-101-14X38/53/54/5101/5Cj-Zj3/5-11/500-4/53X11/31-1/301/3-1/341X37/5011-1/52/5Cj-Zj0-20-1/5-3/5最优解为X1=1/3,X3=7/5,Z=33/52）对偶问题为Minw=9y18y26yi3y2>3I3y14y2>1）5y15y2>4y1,y2>0对偶问题最优解为y1=1/5,y2=3/53）若问题中X2列的系数变为（3,2）则R'=（1/3,1/5）T（T2=-4/5<0所以对最优解没有影响4）

C2由1变为2（T2=-1<0

所以对最优解没有影响In设备能力（台.h）A111100B1045600C226300单位产品利润（元）1064A、8.某厂I、n、m三种产品分别经过备台时，设备的现有加工能力及每件产品的预期利润见表:B、C三种设备加工。已知生产单位各种产品所需的设2）产品m每件的利润到多大时才值得安排生产？如产品m每件利润增加到

50/6元，求最优计划的变化。（4分）（2分）（3分）3）产品I的利润在多大范围内变化时，原最优计划保持不变。4）设备A的能力在什么范围内变化时，最优基变量不变。5）如有一种新产品，加工一件需设备A、B、C的台时各为1、4、3h，预期每件为8元，是否值得生产。（3分）6）如合同规定该厂至少生产10件产品m,试确定最优计划的变化。（3分）解：1）建立线性规划模型为：MaxZ=10x16x24x3x1x2x3<10010x14x25x3=6002x12x26x3<300xj>0,j=1,2,3获利最大的产品生产计划为：

X*=（x1,x2,x3,x4,x5,x6）'=（100/3,200/3,0,0,0,100）'Z*=2200/3'=（175/6,275/6,25,0,0,0）'产品I的利润在［6,15］变化时，原最优计划保持不变。设备A的能力在［60,150］变化时，最优基变量不变。新产品值得生产。最优计划的变化为：X*=（x1,x2,x3,x4,x5,x6）'=（190/6,350/6,10,0,0,60）'Z*=706.72）产品m每件利润到20/3才值得生产。如果产品m每件利润增加到

50/6元，最优计划的变化为：

X*=（x1,x2,x3,x4,x5,x6）'=（175/6,275/6,25,0,0,0）'Z*=775

3）4）5）6）9.给出成性规划问题：（15分）Minz=2x13x26x31X12X2X3》2-2x1X23X3W-3xj>0j=1,…，4要求：（1）写出其对偶问题。（5分）⑵利用图解法求解对偶问题。（5分）（3）利用（2）的结果，根据对偶问题性质写出原问题最优解。（5分）解：1）该问题的LD为：MaxW=2y1-3y2y1-2y2<22y1y2<3y13y2<6y1>0,y2<02）用图解法求得LD的最优解为：丫*=（y1,y2）'=（8/5,-1/5）'

W*=19/53）由互补松弛定理：原问题的最优解为：X*=（x1,x2,x3）'=（8/5,1/5,0）'10.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量，各销售点的销售量（单位.t）以及各工厂到各销售点的单位运价（元/t）示于下表中，要求研究BB2BbB4曰.产量A41241132A2103920A8511644销量1628