南开大学计算机与控制 工程学院 运筹学历年考研真题汇编 含部分答案 下载本文

内容发布更新时间 : 2024/12/25 23:32:09星期一 下面是文章的全部内容请认真阅读。

第二部分 南开大学其他学院运筹学历年考研真题 2012年南开大学商学院915运筹学考研真题

2011年南开大学商学院915运筹学考研真题

2011年南开大学商学院915运筹学考研真题及详解

南开大学2011年硕士研究生入学考试试题

学 院:140商学院 考试科目:897运筹学(商学院)

专业:管理科学与工程

一、某厂生产A、B两种产品,需经过金工和装配两个车间加工,有关数据如表1所示.产品B无论生产批量大小,每件产品生产成本总为400元。产品A的生产成本分段线性:第1件至第70件,每件成本为200元;从第71件开始,每件成本为190元。试建立线性整数规划模型,使该厂生产产品的总利润最大。(本题共15分)

?1,当x1?71答:设x1,x2为产品A、B的个数,???

?0,当x2?70则建立线性整数规划模型如下: 二、现有一个线性规划问题(p1) maxz1=CX

其对偶问题的最优解为Y*=(y1,y2,y3,…,ym)。另有一线性规划(p2): maxz2=CX

其中,d=(d1,d2,…,dm)T。求证:maxz2≤maxz1+Y*d(南开大学2011年研)

证:问题1的对偶问题为: 问题2的对偶问题为:

易见,问题1的对偶问题与问题2的对偶问题具有相同的约束条件,从而,问题1的对偶问题的最优解

***Y*??y1,y2,L,ym?一定是问题2的对偶问题的可行解。

令问题2的对偶问题的最优解为Y2*,则Y2*?b?d??Y*?b?d??Y*b?Y*d。 因为原问题与对偶问题的最优值相等,所以:

三、某工厂计划生产甲、乙、丙3种产品,各产品需要在设备A、B、C上进行加工,其所需加工小时数、设备的有效台时和单位产品的利润表2所示。

请回答下面三个问题:(本题共20分,其中第一小题10分,后两小题各5分)

1.如何安排生产计划,可使工厂获得最大利润?

2.若每月可租用其他工厂的A设备360台时,租金200万元,问是否租用这种设备?若租用.能为企业带来多少收益?

3.若另外有一种产品,它需要设备A、B、C的台时数分别为2、1、4,单位产品利润为4万元,假定各设备的有效台时数不变,投产这种产品在经济上是否合算?

答:1.设生产甲、乙、丙三种产品各为x1,x2,x3单位.,则由题意得: 加入松弛变量后,利用单纯形法计算如下: cj CB 0 0 0 4 0 0 4 3 0 单位。

?0?获得最大利润z=?2,4,3??200/3??766.7(万元)

????500/3??2 b 600 400 800 150 250 350 200/3 500/3 x1 3 2 1 2 3/4 5/4 -5/4 -1 1/3 5/6 -4/9 4 x2 [4] 1 3 4 1 0 0 0 1 0 0 0 3 x3 2 2 2 3 1/2 [3/2] 1/2 1 0 1 0 0 0 x4 1 0 0 0 1/4 -1/4 -3/4 -1 1/3 -1/6 -2/3 -5/6 0 x5 0 1 0 0 0 1 0 0 -1/3 2/3 -1/3 -2/3 0 x6 0 0 1 0 0 0 1 0 0 0 1 0 XB x4 x5 x6 x2 x5 x6 x2 x3 x6 800/3 -3/5 因此已得到最优解,即不生产产品甲,乙和丙的产量分别为200/3,和500/32.即?b??360,0,0?,此时,各非基变量的检验数不发生变化,故最优基B

T不改变。

?0?z???2,4,3??560/3??1066.7(万元);

????320/3???z?z??z?1066.7?766.7?300(万元); 为企业带来收益300-200=100(万元)。

3.设这种产品产量为x7单位,则约束方程增加一列向量???2,1,4?

T? 1/3 -1/3 0??2??1/3???1???1/3? ?1/6 2/3 0在最终单纯性表为???B?1????????????2/3 -1/3 1????4????7/3??故投产这种产品合算。

四、某科学试验可用1#、2#,3#三套不同仪器中的任一套去完成。每做完一次试验后.如果下次仍用原来的仪器,则需要对该仪器进行检查整修而中断试验:如果下次换用另外一套仪器,则需拆装仪器。也要中断试验。假定一次试验时间比任何一套仪器的整修时间都长,因此一套仪器换下来隔一次再重新使用时,不会由于整修而影响试验。设i#仪器换成j#仪器所需中断试验的时间为tij,如表3所示。现要做4次试验,问应如何安排使用仪器的顺序,使总的中断试验的时间最小?(本题共20分)

答:设A、B、C分别代表三套仪器1#、2#,3#,Ai表示在第i次实验中用仪器A,依此类推Bi、Ci,并设虚拟开始S和结束点D。则得如下网络图:

A1

9 14 0 B9 S 0 1 10 0 6 5 8 C1

10 12 A2

10 A3

C2

14 9 B2 9 12 10 6 5 8

C3

14 B3 9 12 10 6 5 8

10 9 A4

0

B4 0 0

C4

D

求总的中断试验的时间最小,即找最短路问题,利用Dijkstra算法计算如下: (1)j=0,S0={S},P(S)=0

∵A1,B1,C1到S点距离相同,∴可同时标号。

(A1/B1/C1)=S。 则S1=(S、A1、B1、C1),?(2)j=1

则S2=(S、A1、B1、C1、A2、B2、C2)