《运筹学》模拟试卷及答案详解

1、工商管理专业运筹学课程期末考试试卷12标准答案一、10分证明：约束条件并未改变x0，x*都为改变前后两问题的可行解。 c x0cx* 0c* x*c*x0 0将以上两个不等式左右分别相加，即可得证。二、15分解：1 对偶问题如下：max 3y16y22y32y4 y13y2 y4 8 2y1 y2 6 y2y3y4 3 y1 y2y3 6 y1 ，y2，y3， y402y（y1，y2，y3，y4），ys（y5，y6 ，y7 ，y8）；x（x1，x2 ，x3，x4）（1，1，2，0），xs（x5，x6 ，x7，x8）（0，0，0，1）。由松弛性质得：y*（y1，y2 ，y3，y4）（2，2，1，

2、0）三、10分解：假设一个销地b4，需要20（实际含义为存货）单位运价表及产销平衡表 销地产地b1b2b3b4产量a1122520a2145m38a214542a3233m27a323333销量30202020四、15分解：五、10分解：六、15分解：网络的时间参数计算如下：结点ite(i)048981215tl(i)0581281215工序abcdefgh总时差10113100正常完工工期为15天。总费用153515228（百元）可选关键工序为：b、g、h，其中g的费用梯度最小。将g工序缩短1天，各时间参数变为：结点ite(i)048981114tl(i)0481181114工序abcdef

3、gh总时差00012000可选缩短方案有：ab；bf；bgh；ch。以上各可选方案的费用梯度均大于每天的间接费用5，因此不能继续缩短工程工期。于是该工程的最低成本日成为14天。总费用1533514226（百元）七、15分解：收益矩阵如下表所示。 单位：万元 状态方案31220e（i）5509047.2525610452.745911555.15*不调查时收益期望值为55.15万元；调查时收益期望值为：50.15590.751150.1056.5万元。信息的价值为56.555.151.35万元，故该公司最多愿花1.35万元的调查费用。八、10分解：满意解为 x*（ x1，x2）（1， 0）。 d

4、2 d2 d1d1得分一、 10分用图解法求解下列线性规划问题，并说明最优解的性质。1. max z4x18x2 2. min z6x1 4x2 2x1 2x2 10 2x1 x21 x1 x2 8 3x1 4x21.5 x1 ，x20 x1 ，x20得分二、 10分假设你要安排每天12个小时的生活方式，并假设你认为同样时间内娱乐的乐趣是学习的5倍，但又认为学习的时间至少应为娱乐时间的3倍。如何安排每天的学习和娱乐时间，才可使你每天的乐趣最大？（建立线性规划数学模型，但不必求解）得分得分三、 10分应用对偶理论证明线性规划问题max zx1x2 x1 x2 x3 2 2x1 x2 x3 1 x

5、1 ，x2 ，x3 0 无最优解，并说明是无界解还是无可行解。得分四、 10分 判断下表给出的调运方案能否作为表上作业法求解时的初始调运方案？如果能，说明理由；如果不能，如何纠正？ 销地产地b1b2b3b4b5b6产量a1201030a2302050a3101050575a42020销量204030105025得分得分得分得分五、 10分已知四人完成四项工作的 产值 矩阵如下表所示。试用匈牙利法求解使产值最大的分配方案。 工作人abcd甲791012乙13121617丙15161415丁11121516得分六、 15分建立求下图所示的网络中从v1至v4的流量为4的最小费用流的线性规划数学模型，

6、图中弧旁数字为（费用，容量）。（不必求解）v3v2v4v1（2,3）（5,1）（8,2）（7,4）（10,5）（6,6）得分七、 15分 某厂研制出一种新产品。若该新产品投产后销售成功，则可获利50万元；如销售失败，则损失20万元。该厂估计新产品销售成功的概率为0.6。若不生产新产品而只生产旧产品，则可稳获利20万元。现可以对新产品的需求量进行市场调查，以往调查的准确度如下表所示。调查费用为0.2万元。试利用决策树进行决策。（画出决策树，但不必求解。）调查结果实际销售情况成功失败销售成功0.40.1没有结论0.40.5销售不成功0.20.4得分八、 20分某人拥有8千元闲置资金，可投资于三个项

7、目中。已知投资于每个项目的收入如下表所示。利用动态规划方法确定使总收入最大化的投资方案。投资额（千元）项目0123456780515408090959810005154060707374750426404550515253一、10分解：1 8 6 4 2 8 6 4 2 2 4 6为无可行解。2 1 3/8 1/2 1为唯一最优解：（x1，x2）（1/2，0），min z3。二、10分解：设每天学习的时间为x1，娱乐的时间为x2，总的乐趣为z。则：三、10分解：原问题的对偶问题如下：min 2y1y2 y1 2y2 1 y1 y2 1 y1 y2 0 y1 ，y20 其中约束条件不可能满足，因

8、此对偶问题无可行解，原问题便无最优解。四、10分 解：能。因为有数字项为mn19个，而且不存在有全由有数字项构成的闭回路。五、 10分解： 甲b、 乙c、 丙a、丁d。 总产值为56。六、15 分解：生产新产品生产旧产品生产旧产品生产旧产品成功p(n1/s2)没有结论p(s2)生产旧产品调查 -0.2不调查134成功 p(s1)失败p(s3)成功p(n1/s1)失败p(n2/s1)生产新产品58失败p(n2/s2)生产新产品69成功p(n1/s3)失败p(n2/s3)710成功 0.6失败 0.4生产新产品24-202050-202050-202050-202050七、15分解：八、20分解：

9、s3u3u3*0123456780001041204262304264034042640454504264045505604264045505167042640455051527804264045505152538s2u2u2*01234567800+0010+45+0120+265+415+0030+405+2615+440+00,340+455+4015+2640+460+0450+505+4515+4040+2660+470+0560+515+5015+4540+4060+2670+473+0470+525+5115+5040+4560+4070+2673+474+0480+535+52

10、15+5140+5060+4570+4073+2674+4755s1u1u1*01234567880+1105+10015+8640+7080+6090+4095+2698+5100+04最优决策为项目1投入4千元，项目2投入4千元，项目3不投入。总收入为140千元。得分九、 10分用图解法求解下列线性规划问题，并说明最优解的性质。2. max z x1 x2 2. min z 3x1 2x2 8x1 6x2 24 x1 x2 1 4x1 6x2 12 2x1 2x2 4 2x2 4 x1 ，x2 0x1 ，x20 得分十、 15分 列出下列运输问题的线性规划数学模型，但不必求解。销地产地产量

11、a2345150b3252200c4123250销量80100120150得分十一、 15分已知某线性规划问题的初始单纯形表和最终单纯形表如下所示，请将表中空白处填上数字。cj211000bcbxbx1x2x3x4x5x60x4311100600x5112010100x611100120j2110000x41122x101/21/21x201/21/2j得分十二、 10分应用对偶理论证明线性规划问题max z x1x2 x3 x1 x3 4 x1 x2 2x3 3 x1 ，x2 ，x3 0 无最优解，并说明是无界解还是无可行解。得分十三、 15分已知五人完成五项工作的时间矩阵如下表所示。试用匈

12、牙利法求解。 工作人abcde甲382103乙87297丙64275丁84235戊9106910得分十四、 10分某单位招收五种外文的翻译各一人，应聘的5人所懂外文的情况如下表所示。 外文应聘人员俄文英文日文德文法文甲乙丙丁戊问这5人能否全部被聘用？聘用后每人从事哪种外文的翻译任务？（说明求解方法，但不必求出结果）得分十五、 10分某商店准备在新年前订购一批挂历销售，已知每售出1百本可获利70元。如果在新年前售不出去，则每1百本损失40元。预测挂历售出数量及概率如下表所示，试确定该商店的最佳订货数量。需求量(百本)012345概率0.050.100.250.350.150.10得分十六、 15

13、分 有一种资源，数量为b，使用于n种活动。已知将y单位资源使用于活动k的收入为r(y,k)，其中使用于活动k的资源限制为0yy(k)。试建立最佳使用b单位资源的动态规划方程。一、10分解：1 x2 8 6 4 2 x1 8 6 4 2 2 4 6 2为无界解。2 2 1 1 2为无可行解。二、15分解：三、15分解：cj211000bcbxbx1x2x3x4x5x60x4311100600x5112010100x611100120j2110000x4001112102x1101/201/21/2151x201-3/201/21/25j00-3/20-3/2-1/2四、 10分解：原问题的对偶问

14、题如下：min 4y13y2 y1 y2 1 y2 1 y1 2y2 1 y1 ，y20 其中约束条件不可能满足，因此对偶问题无可行解，原问题便无最优解。五、 15分解：3 8 2 10 3 0 4 0 7 0 0 4 2 7 08 7 2 9 7 5 3 0 6 4 3 1 0 4 26 4 2 7 5 3 0 0 4 2 3 0 2 4 28 4 2 3 5 5 0 0 0 2 5 0 2 0 29 10 6 9 10 2 2 0 2 3 0 0 0 0 1甲e，乙c，丙b，丁d，戊a。总时间为21。六、10分解：转化成下面的匹配问题，求解网络的最大流，即可得出最大匹配。其中每条弧的容量为

15、1。 甲 俄 乙 英 vs vt 丙 日 丁 德 戊 法七、10分解：k70元，h40元，k/（k h）0.6364，r02时，p（r）0.40，r03时，p（r）0.75，故最佳订货数为3百本。八、15分解：设可用于第k项至第n项活动的资源量为sk，用于第k项活动的资源量为yk，则：得分十七、 10分用图解法求解下列线性规划问题，并说明最优解的性质。3. max z3x19x2 2. max z3x1 4x2 x1 3x2 22 x1 2 x2 8 x1 x2 4 x1 2x212 x2 6 2x1 x216 2x1 5x2 0 x1 ，x20 x1 ，x20 得分十八、 10分某一出版商正

16、印制一本新书，此书可能是精装本，也可能是平装本。每一精装本的利润为4元，而平装本为3元。装订一本精装本需要3分钟，而平装本需要2分钟。总共可用来装订书本的时间为800小时。根据经验，需要至少印制10000本精装本且至多印制6000本平装本。问该出版商必须印制此二种版本书各多少，方可使其获得最大利润？建立线性规划模型，但不必求解。得分十九、 10分已知线性规划问题max z3x12x2 x1 2x2 4 3x1 2x2 14 x1 x2 3 x1 ，x2 0 1 写出其对偶问题；2 应用对偶理论证明原问题和对偶问题都存在最优解。得分二十、 15分 试用分枝定界法求解下列整数规划问题，并用框图表示

17、计算过程。 min z6x1 4x2 2x1 x21 3x1 4x21.5 x1 ，x20且为整数得分二十一、 10分证明不可能存在一条折线，和下图中的每条边相交叉一次且只交叉一次。得分二十二、 10分某一决策问题的情况如下表所示。表中值为年利润。 状态 方案n1n2n3a1402002400a2360360360a31000240200当采用折衷值准则确定最优方案时，折衷系数取何值，方案a1 和a3相当？得分二十三、 15分某厂生产三种规格电视机，装配工作在同一生产线上完成。三种产品装配时的工时消耗分别为6，8和10小时，生产线每月正常工作时间为200小时。三种电视机销售后，每台可获利分别为

18、500，650和800元。每月销量预计为12，10和6台。该厂经营目标如下：p1：利润指标定为每月16000元；p2：充分利用生产能力；p3：加班时间不超过24小时；p4：产量以预计销量为标准。试建立该问题的目标规划模型。（不必求解）得分二十四、 20分某商业公司拟将5名商业管理专家派往所辖的三个销售商场，估计派往各商场不同人数的专家后，各商场当年盈利的增加额（万元）如下表所示。问公司应派往各商场各几名专家？专家数商场012345045709010512002045751101500507080100130一、10分解：1 x2 8 6 4 2 x1 4 0 4 8 12 16 20 24 2

19、为无穷多最优解。其中两个最优解如下：x1 4 x110 max z66。x2 6 x242 16 12 8 4 8 4 4 8 12为唯一最优解。 x120/3 max z92/3。 x28/3二、10分解：三、10分解：原问题的对偶问题如下：min 4y114y23y3 y1 3y2y3 3 2y1 2y2y3 2 y1 ，y2，y30 可知原问题有可行解（x1，x2）（0，0），对偶问题也有可行解（y1，y2，y3）（0，1，0）。因此原问题和对偶问题都有最优解。四、15分x11x10问题x1=0.5,x2=0z=3问题x1=0,x2=1z=4问题x1=1,x2=0z=6解：x2x1011

20、/211/2 整数规划最优解为（x1，x2）=（0，1），z = 4.五、10分证明： a b c f d e将每块区域（包括外围区域）看作一个点，区域之间有几条边相互接壤，对应点之间便连几条线。于是问题转化成为一笔画问题。容易得知：b、d、e、f四点皆为奇点，因此不可能实现一笔画问题，也就不存在符合要求的折线。六、10分解： 状态 方案n1n2n3mimiuia1402002400240040240040（1）a2360360360360360a3100024020010002001000200（1）a1和a3相当时，应有：240040（1）1000200（1）得：4/390.1026。七、

21、15分解：设每月生产三种规格电视机分别为x1，x2，x3台，则目标规划模型为：min zp1d1p2d2p3d3p4（d4d4d5d5d6d6） 500 x1650 x2800 x3d1d116000 6 x18 x210 x3d2d2200 6 x18 x210 x3d3d3224 x1 d4d412 x2 d5d510 x3d6d66 x1，x2，x30，di，di0 （i1，6）八、20分解：s3u3u3*012345000105012050702305070803405070801004505070801001305s2u2u2*01234500+0010+5020+0020+7020

22、+5045+00,130+8020+7045+5075+0240+10020+8045+7075+50110+0350+13020+10045+8075+70110+501504s1u1u1*01234550+16045+12570+9590+70105+50120+01最优决策为：商场1分配1名专家，商场2分配3名专家，商场3分配1名专家。盈利总增加额为170万元。得分二十五、 10分用图解法求解下列线性规划问题，并说明最优解的性质。4. max zx13x2 2. min zx1 1.5x2 5x1 10x2 50 x1 3 x2 3 x1 x2 1 x1 x2 2 x2 4 x1 ，x2

23、 0 x1 ，x20 得分二十六、 10分甲、乙两煤矿供给a，b，c三个城市的用煤。各煤矿的产量和各城市的需求量以及各煤矿与各城市之间的运输价格如下表所示。问应如何调运，才能满足城市的用煤需求，又使运输总费用最小？（建立线性规划数学模型，但不必求解）城市煤矿abc日产量（吨）甲9070100200乙806580250日需求量（吨）100150200得分二十七、 10分已知线性规划问题max z4x17x22x3 x1 2x2 x3 10 2x1 3x2 3x3 10 x1 ，x2 ，x30 应用对偶理论证明原问题的最优解的目标函数值不大于25。得分二十八、 10分 试用分枝定界法求解下列整数规

24、划问题，并用框图表示出计算过程。 max zx1x2 x1 x2 1 3x1 x2 4 x1 ，x20且为整数得分二十九、 20分某商店拟将6箱商品分给所辖四个门市部销售。预计各门市部销售盈利额如下表所示。问商店应如何分配该商品？箱数门市部0123456010020028033030025009015020017010020010020030038546554009516521018512040得分三十、 15分求下图所示的网络中从vs到vt的最大流量。弧旁数字为容量。713455451069101410v6v2vtv5v3v1vsv4得分三十一、 15分某书店预定新书，已知新书的订购价格为4

25、元，销售价格为6元，剩书处理价格为2元。根据以往经验，新书的销售量及发生的概率情况如下表所示。要求：销售量(本)50100150200概率0.200.400.300.101 试用期望值准则确定最优订书量？2 如通过调查，可得到销售量的确切数字，问该书店愿意付出多大的调查费用？得分三十二、 10分一广播电台考虑如何最好地安排节目。根据规定，每天允许广播12小时，其中商业节目每分钟可收入250美元，新闻节目每分钟需支出40美元，音乐节目每分钟需支出17.50美元。规定正常情况下商业节目只能占广播时间的20%，每小时至少安排5分钟的新闻节目。考虑的优先级如下：p1：满足规定要求；p2：每天的纯收入最

26、大。试建立该问题的目标规划模型。(不必求解)一、10分解： x21 5 4 3 2 1 x1 0 2 4 6 8 10 为唯一最优解。 x1 2 max z14。 x2 4 2 x2 2 1 1 2 3 x1为唯一最优解。 x13/2 max z9/4。 x21/2二、10分解：三、10分证明：原问题的对偶问题如下：min 10y110y2 y12y24 2y13y2 7 y13y2 2 y1 ，y20 可知对偶问题有可行解（y1，y2）（1/2，2），目标函数值等于25。因此原问题最优解的目标函数值不大于25。四、 10分解：问题x1=0.75,x2=1.75z=2.5x2x10x114问题

27、x1=1,x2=1z=2问题x1=0,x2=1z=121/2x11-10整数规划最优解为（x1，x2）=（1，1），z=2。五、20分解：s4u4u4*012345600010951209516523095165210340951652101853509516521018512036095165210185120403s3u3u3*012345600+0010+95100+0120+165100+95200+0230+210100+165200+95300+0340+210100+210200+165300+95385+0350+210100+210200+210300+165385+9546

28、5+0460+210100+210200+210300+210385+165465+955405s2u2u2*012345600+0010+10090+0020+20090+100150+0030+30090+200150+100200+0040+39590+300150+200200+100170+0050+48090+395150+300200+200170+100100+0160+56090+480150+395200+300170+200100+10020+01s1u1u1*012345660+570100+485200+395280+300330+200300+100250+02最优决策为门市部1分2箱，门市部2分0箱，门市部3分3箱，门市部4分1箱，总盈利额为595。六、 15分