南开大学计算机与控制工程学院运筹学历考研真题汇编(含部分答案)

1、南开大学计算机与控制工程学院806运筹学历年考研真题汇编(含部分答案)最新资料，WORD格式，可编辑修改！目录说明：(1) 2013年7月，南开大学对信息技术科学学院学科进行优化整合，分别组建计算机与控制工程 学院和电子信息与光学工程学院。(2) 2004年和2015年南开大学信息技术科学学院的“运筹学”科目代码不详。第一部分南开大学806 运筹学历年考研真题2011 年南开大学信息技术科学学院813 运筹学考研真题2011年南开大学信息技术科学学院813运筹学考研真题及详解南开大学2011年硕士研究生入学考试试题学院：034信息技术科学学院考试科目：813运筹学(信息学院)专业：运筹学与控制

2、论一、(35分)已知某工厂计划生产 A、B、C三种产品，备产品均需使用甲、乙、丙这三种设 备进行加工，加工单位产品需使用各设备的时间、单位产品的利润以及各设备的工时限制数据如 下表所示。试问：(1)应如何安排三种产品的生产使得总利润最大？(2)若另有两种新产品 D、E,生产单位 D产品需用甲、乙、丙三种设备12小时、5小时、10小时，单位产品利润千元；生产单位E产品需用甲、乙、丙三种设备单位产品利润千元，请分别回答这两种新产品投产是否合算？(3)若为了增加产量，可租用其他工厂的设备甲，可租用的时间是4小时、4小时、12小时,60小时，租金万元。请Cj32000CbXbbX1X2X3X4X5X6

3、0X4304816101000X540010580100X642021310001320003X138125/41/8000X520015 9/2 5/4100X63440915/21/40104一一00所得利润最大。C7已得最优解，即只生产 A种产品,问是否合算？(4)增加设备乙的工时是否可使工厂的总利润进一步增加？答：(1)设生产A、B、C三种产品的数量分别为 X1, X2, X3单位。则可以得出数学模型:添加人工变量 X4, X5, X6利用单纯形法计算如下：C8=,约束矩阵增加两个列向量x7, X8,对应的(2)增加新变量，一 ，一 T12,5,104,412 T85411210321

4、0 ，A185-411211其检验数为:7C7CB2.1(3,0,0)3210c7Cb1.87(3,0,0)0.3711则判断出：产品 D的投产不合算，产品E投产合算。(3)即b 60,0,0 T ,其不影响检验数的结果，故最优解不变。38最终单纯形表中 b203441854146045.55532945.5zCBb(3,0,0)55136.5（千元），136.538*3 22.5 18故租用设备甲合算。（4）当增加乙的工时,zCBb(3,0,0)二、（15 分）有 A、3293820b23838344B、C、DA1 b 20344b2020b2344114 z,故利润不会增加。四种零件均可在

5、设备甲或设备乙上加工已知这两种设备上分别加工一个零件的费用如下表所示。又知设备甲或设备乙只要有零件加工就需要设备的启动费用，分别为100元和150元。现要求加工四种零件各3件，问应如何安排生产使总的费用最小？请建立该问题的线性规划模型（不需求解）。加工一个零件的费用答：设i = 1, 2 , 3, 4分别表示产品A、 B、 C、D；（单位：元）j=1, 2表示设备甲、乙。4xj表示产品i在设备j上生产的个数,1,xij0时,1,0,Xij0,则得线性规划模型如下:其中 C 50 80 90 40 30100 50 70, XX|1X21X31 x41 X12 X22 X32 x42第一项工程的

6、工期为三、（25分）某工程公司在未来 1 4月份内需完成三项工程:份，总计需劳动力 80人月；第二项工程的工期为14月份，总计需劳动力 100人月；第三项工程的工期为34月份，总计需劳动力 120人月。该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过60人。问该工程公司能否按期完成上述三项工程任务，应如何安排劳力？（请将该问题归结为网络最大流问题求解）答：可以构建如下网络图（弧上数字为最大流量）其中，结点1、2、3、4分别彳表1、2、3、4月份，结点5、6、7分别代表第一、二、三项 工程。通过标号与调整，得到的最大流如下图所示。该最大流问题有多重最优解，上图仅给出一种。所

7、以该公司能按期完成上述三项工程任务，安排劳力的方案可以为：1月份，安排60人做第一项任务、20人做第二项任务；2月份，安排60人做第二项任务；3月份，安排60人做第三项任 务、20人做第一项任务；4月份，安排60人做第四项任务、20人做第三项任务。四、（25分）某工厂设计的一种电子设备由A、B、C三种元件串联而成，已知三种元件的单价分别为2万元、3万元、1万元，单件的可靠性分别为、，要求设计中使用元件的总费用不超过10万元，问应如何设计使设备的可靠性最大？（请使用动态规划方法求解）答：该题中元件A, B, C是串联在一起的，为保证可靠性，在条件允许的情况下，我们会将多个同种元件并联在一起。如上

8、图，就是将 2件A, 1件B, 3件C先并联再串联在一起, 由于A, B, C的可靠性分别为，。设采用m个A, n个B, 1个C串联该组合整体的可靠性为1-0.3m1-0.2n1-0.4l约束条件为2m 3n l 1且m, n, 1都为正整数。由动态规划的思路，我们先从单价高的B开始分类：由于A, B, C至少都得有1件，故在10万元为限制的前提下，B最多2件选才12件B时，问题转化为 max 1-0.3m 0.96 1-0.4l2m l 4由于m与n必须都大于0,故此时必然选择1件A , 2件B ,此时可靠性为：x x =。选才11件B时，问题转化为 max 1-0.3m 0.8 1-0.4

9、l2m l 7此时可以选择 1件A, 5件C; 2件A, 3件C;或者3件A , 1件C。同理计算可靠性分别为，。故可靠性最大的组合为2件A , 1件B , 3件C,此时可靠性为。五、（25分）某公司兴建一座港口码头，只有一个装卸船只的位置。设船只到达的间隔时间和装卸时间都服从负指数分布，预计船只的平均到达率为3只/天，船只到港后如不能及时装卸，停留一日公司将损失 1500元。现需设计该港口码头的装卸能力（即每日可以装卸的船只数），已知单位装卸能力每日平均生产费用为2000元，问装卸能力为多大时，每天的总支出最少？在此装卸能力之下，求：（1）装卸码头的利用率；（2）船只到港后的平均等候时间？（

10、3）船只到港后总停留时间大于一天的概率。答：设装卸能力为，公司的支出z 20003 Lq 1500, Lq则 z 2000- 1500 2000竺00。33令 z 20004500 2 =0,解得=?,或=3（舍去）。（3） 22一 9所以二一时，每天的总支出最少。2“2 f°，21（1） 一 ，P 11 ;33 3所以码头的利用率为 1 P0= 2/ 3。Wq支天）q9/2 3 9，一，、4即船只到港后的平均等候时间是一天o9 .3的负指数分布（3）设船只到港后的总停留时间T,则T服从天23分布函数为F 1 e； ,0；P(T 1) 1 P(T 1)=1 F 1e 3/20.223

11、。六、（25分）已知A、 策值。B各自的纯策略及 A的赢得矩阵如下表所示，求双方的最优策略及对答：在A的赢得矩阵中第 4列优超于第2歹U,第1列优超于第3歹U,故可划去第 2列和第3 列，得到新的赢得矩阵对于Ai,第二行优超于第 4行，因此去掉第 4行，得到对于A2,易知无最优纯策略，用线性规划的方法求解，其相应的相互对偶的线性规划模型 如下：利用单纯形法求解第二个问题，迭代过程如下表所示11000CbYbby1y4y5y6y70y51831001/ 80y61640101/ 60y714120011/4检验数110001y11/813/81/ 8001/ 30y61/401/2-3/4101

12、/ 20y71/2021/2-1/2011/ 21检验数05/8-1/8001y13/ 28101/ 701/280y619/ 8400-61/8411/211y41/21011/2102/21检验数00-2/210-5/ 84从上表中可以得到，第二个问题的最优解为：由最终单纯形表的检验数可知，第一个问题的最优解为:于是：所以，最优混合策略为：对策的值为V 84/132005 年南开大学信息技术科学学院运筹学考研真题2004 年南开大学信息技术科学学院运筹学考研真题第二部分南开大学其他学院运筹学历年考研真题2012 年南开大学商学院915 运筹学考研真题2011 年南开大学商学院915 运筹学

13、考研真题2011年南开大学商学院915运筹学考研真题及详解南开大学2011年硕士研究生入学考试试题 学院：140商学院考试科目：897运筹学（商学院）专业：管理科学与工程1所示.产品B无论生产批量大小，每件产品生产成本总为 70件，每件成本为 200元；从第71件开始, 厂生产产品的总利润最大。（本题共15分）答：设x1，X2为产品A、B的个数，则建立线性整数规划模型如下：二、现有一个线T规划问题（ P1）maxz1 = CX其对偶问题的最优解为 Y*= （y1，y2, maxz2 = CX其中，d= （d1，d2,，dm） To 求证： 证：问题1的对偶问题为：问题2的对偶问题为：、某厂生产

14、 A、B两种产品，需经过金工和装配两个车间加工，有关数据如表400元。产品A的生产成本分段线性：第 1件至第每件成本为 190元。试建立线性整数规划模型，使该1,当 X1 710,当 X2 70V3,，ym）。另有一线性规划（P2）:maxz2< maxz+ Y*d （南开大学 2011 年研）易见，问题1的对偶问题与问题 2的对偶问题具有相同的约束条件，从而，问题 1的对偶问 题的最优解 *Yy1，y2,L ,ym 一定是问题2的对偶问题的可行解。A 、-1一 .* r .一、.一一 一 -,.一 、»*令问题2的对偶问题的最优解为 Y2，则Y2bd Ybd YbYd。因为原

15、问题与对偶问题的最优值相等，所以：三、某工厂计划生产甲、乙、丙3种产品，各产品需要在设备a、b、C上进行加工，其所需加工小时数、设备的有效台时和单位产品的利润表2所示。请回答下面三个问题：（本题共 20分，其中第一小题 10分，后两小题各 5分）1 .如何安排生产计划，可使工厂获得最大利润？2 .若每月可租用其他工厂的A设备360台时，租金200万元，问是否租用这种设备 ？若租用.能为企业带来多少收益 ？3 .若另外有一种产品，它需要设备A、B、C的台时数分别为 2、1、4,单位产品利润为 4万元，假定各设备的有效台时数不变，投产这种产品在经济上是否合算？答：1 .设生产甲、乙、丙三种产品各为

16、Xi, x2, x3单位.，则由题意得:加入松弛变量后，利用单纯形法计算如下：Cj243000CbXbbxix2x3x4x5x60x46003421000x54002120100x68001320012430004x21503/411/21/4000x52505/403/2-1/4100x63505/401/2-3/4011011004x2200/31/3101/31/303x3500/35/601-1/62/300x6800/33/500-2/31/314/900 5/6 2/30因此已得到最优解，即不生产产品甲，乙和丙的产量分别为200/ 3,和500/ 3单位。0获得最大利润z= 2,4

17、,3 200/3766.7 （万元）500/32 .即 b 360,0,0 T ,此时，各非基变量的检验数不发生变化，故最优基B不改变。0z 2,4,3 560/31066.7 （万元）；320/3z z z 1066.7 766.7 300 （万元）；为企业带来收益 300 200= 100 （万元）。3 .设这种产品产量为 X7单位，则约束方程增加一列向量2,1,4T1/3 -1/3 0 21/ 3在最终单纯性表为 B 11/ 6 2/3 0 11/32/3 -1/3 1 47/3故投产这种产品合算。四、某科学试验可用1#、2#, 3#三套不同仪器中的任一套去完成。每做完一次试验后.如果下

18、次仍用原来的仪器，则需要对该仪器进行检查整修而中断试验：如果下次换用另外一套仪器， 则需拆装仪器。也要中断试验。假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪 器换下来隔一次再重新使用时，不会由于整修而影响试验。设i#仪器换成j#仪器所需中断试验的时间为tij,如表3所示。现要做4次试验，问应如何安排使用仪器的顺序，使总的中断试验的时间最 小？（本题共20分）答：设A、B、C分别代表三套仪器 1#、2#, 3#, Ai表示在第i次实验中用仪器 A,依此类推 Bi、Ci,并设虚拟开始 S和结束点D。则得如下网络图：Ai10A210A310A4DCiC2C3C4求总的中断试验的时间最小，

19、即找最短路问题，利用 Dijkstra算法计算如下:（1） j = 0, So = S , P （S） = 0 Ai, Bi, Ci至ij S点距离相同，可同时标号。则 Si= （ S、Ai、Bi、Ci） ,（A1/B1/C1） =S oj = 1则 S2= （ S、A1、Bi、Ci、A2、B2、C2）则 S3= ( S、Ai、Bi、Ci、A2、(4) j = 3贝I S4= (S、Ai、Bi、Ci、A2、束。( 5)比较T( A4)、T( B4)、验的时间最小的使用顺序是：Ci82、 C2、 A3、 B3、 C3)B2、C2、A3、B3、C3、A4、B4、C4),最后标号 D,则标号结T (

20、C4),可得出，T (B4)最小，逆序追踪得使总的中断试#B2C3B4 ,即 3 2 3 2。五、某农场考虑是否提早种植某种作物的决策问题，如果提早种，又不遇霜冻则收入为45万元：即使遇霜冻受灾也轻，收入为(i)该农场的决策者认为：“以万元”二者对其来说没有差别：( 2)该农场的决策者认为：“以万元”二者对其来说没有差别：( 3)该农场的决策者认为：“以万元”二者对其来说没有差别。25 万元，遇霜冻的概率为，已知：50%的机会每50%的机会得50%的机会得454535万元万元，万元，50%的机会得50%的机会得50%的机会得i035i0-“万元”和“稳获-“万元”和“稳获-“万元”和“稳获“稳

21、获“稳获“稳获354025元：如遇霜冻，则收入仅为i0 万元遇霜冻的概率为。如不提早种，又不遇霜冻则收入为35问题如下:1 .说明该决策者对风险的态度，按期望效用最大的原则，该决策者应做何种决策2按期望收益最大的原则，该决策者又应做何种决策i0 。把最低收益值i0 万元的效用答：i.将最高收益45万元的效用定为i0,记为U 45定为0，记为U i0 0。则决策者对风险的态度可以表示为：令提早种的期望效用为3540250.50.50.54545350.50.50.5Ei ，不提早种的期望效用为i035i00.50.50.5i0i00.50.50.5 05；7.5；2.5。E2o 则:Ei0.4U

22、 (i0) 0.6U (45)0.4 0 0.6 i0 6；E2 0.2U (25) 0.8U (35)0.2 2.5 0.8 7.5 6.5；E2Ei,所以，决策者的决策应为不提早种。2令提早种的期望收益为Ei ，不提早种的期望收益为E2。E2 Ei,所以，决策者的决策应为不提早种。六、某产品从仓库 Ai (i=i, 2, 3)运往市场 Bj= (j = i, 2, 3, 4)销售，已知各仓库的可 供应量、各市场的需求量及从A i 仓库到B i 市场路径上的容量如表4 所示 (表中数字0 表示两点之间无直接通路)，请制定一个调运方案使从各仓库调运产品总量最多。答： 该问题是求最大流问题，由题

23、得网络图，其中S、 D 是虚拟开始和结束点，各路径最大容量如图所示，初始流量为0：30/WB2“ 20 A 2201CiiBB4(1)标勺过程首先给S标号(0, +8)，检查S,在弧(S, Ai)上，f 同理，A2 A2 (S, 20) , A (S, 100)任点 Ai进行检查，在弧(Ai, Bi)上，fAiBi C1 1Ai检查Bi,在弧(Bi, D)上，fBD C ,则给D标号1 BD ，链，S- Ai - Bi- D(2)调整过程由(1)知，20,得新的可行流量图：Ai (20, 30) 一 .史(20, 20) /VC10(2°，X40K iW>DSA1 csa ,则

24、给 Ai 标勺(S, 20),B1,则给B1标号(A1, 20)(Bi, 20),这样找到了一条增广20):个DAiBi20依据上述方法，重复标号及调整过程，直到不存在增广链为止，最终得最大流量图:Ai (。, 30) 一1rBi(20, 20)(20, 20)4'7 s|> D 3 5。调运方案如下表所示:B1B2B3B4实际供出量A1101020A210515A3201010545实际得到量2020202080七、某公司生产两种小型摩托车，其中甲型完全由本公司制造，而乙型是进口零件由公司装 配而成，这两种产品每辆所需的制造、装配及检验时间如下表5所示。如果公司经营目标的期望值和优先等级如下：P1:每周的总利润至少为 3000元：P2:每周甲型车至少生产 5辆；p3:尽量减少各道工序的空余时间，三工序的权系数和它们的每小时成本成比例。且不允许 加班。请建立这个问题的运筹学模型（不用求解）。答：设每周甲乙两种车生产数量分别为xi, x2,由表可知，两者每辆的生产成本是a和bo贝Ua 20 12 5 8 3 10 310元，b 7 8 6 10 1