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

目录

第一部分南开大学806运筹学历年考

研真题

2011年南开大学信息技术科学学院

813运筹学考研真题

2011年南开大学信息技术科学学院

813运筹学考研真题及详解

2005年南开大学信息技术科学学院

运筹学考研真题

2004年南开大学信息技术科学学院

运筹学考研真题

第二部分南开大学其他学院运筹学

历年考研真题

2012年南开大学商学院915运筹学考

研真题

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

研真题

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

研真题及详解

2010年南开大学商学院887运筹学考

研真题

第一部分南开大学806运筹学历年考研真题

2011年南开大学信息技术科学学院813运筹学考研真题

2011年南开大学信息技术科学学院813运筹学考研真题及详解

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

学院：034信息技术科学学院

考试科目：813运筹学（信息学院）

专业：运筹学与控制论

一、（35分）已知某工厂计划生产A、B、C三种产品，备产品均需使用

甲、乙、丙这三种设备进行加工，加工单位产品需使用各设备的时间、

单位产品的利润以及各设备的工时限制数据如下表所示。试问：

（1）应如何安排三种产品的生产使得总利润最大?

（2）若另有两种新产品D、E，生产单位D产品需用甲、乙、丙三种设

备12小时、5小时、10小时，单位产品利润2.1千元；生产单位E产品需

用甲、乙、丙三种设备4小时、4小时、12小时，单位产品利润1.87千

元，请分别回答这两种新产品投产是否合算?

（3）若为了增加产量，可租用其他工厂的设备甲，可租用的时间是60

小时，租金1.8万元。请问是否合算?

（4）增加设备乙的工时是否可使工厂的总利润进一步增加?

答：（1）设生产A、B、C三种产品的数量分别为x1，x2，x3单位。则可

以得出数学模型：

添加人工变量x4，x5，x6利用单纯形法计算如下：

cj322.9000

CBXBbx1x2x3x4x5x6

0x4304[8]1610100

0x54001058010

0x642021310001

322.9000

3x138125/41/800

0x5200－15－9/2－5/410

0x63440915/2－1/401

0－4－0.85－0.37500

已得最优解，即只生产A种产品，所得利润最大。

（2）增加新变量x7，x8，对应的c7＝2.1，c8＝1.87，约束矩阵增加两个

列向量

，

其检验数为：

，

则判断出：产品D的投产不合算，产品E投产合算。

（3）即，其不影响检验数的结果，故最优解不变。

最终单纯形表中

，

故租用设备甲合算。

（4）当增加乙的工时，

，故利润不会增加。

二、（15分）有A、B、C、D四种零件均可在设备甲或设备乙上加工。

已知这两种设备上分别加工一个零件的费用如下表所示。又知设备甲或

设备乙只要有零件加工就需要设备的启动费用，分别为100元和150元。

现要求加工四种零件各3件，问应如何安排生产使总的费用最小?请建立

该问题的线性规划模型（不需求解）。加工一个零件的费用（单位：

元）

答：设i＝1，2，3，4分别表示产品A、B、C、D；j＝1，2表示设备

甲、乙。

xij表示产品i在设备j上生产的个数，，

则得线性规划模型如下：

其中

三、（25分）某工程公司在未来1—4月份内需完成三项工程：第一项工

程的工期为1—3月份，总计需劳动力80人月；第二项工程的工期为1—4

月份，总计需劳动力100人月；第三项工程的工期为3—4月份，总计需

劳动力120人月。该公司每月可用劳力为80人，但任一项工程上投入的

劳动力任一月内不准超过60人。问该工程公司能否按期完成上述三项工

程任务，应如何安排劳力?（请将该问题归结为网络最大流问题求解）

答：可以构建如下网络图（弧上数字为最大流量）。

其中，结点1、2、3、4分别代表1、2、3、4月份，结点5、6、7分别代

表第一、二、三项工程。通过标号与调整，得到的最大流如下图所示。

该最大流问题有多重最优解，上图仅给出一种。

所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为：1

月份，安排60人做第一项任务、20人做第二项任务；2月份，安排60人

做第二项任务；3月份，安排60人做第三项任务、20人做第一项任务；4

月份，安排60人做第四项任务、20人做第三项任务。

四、（25分）某工厂设计的一种电子设备由A、B、C三种元件串联而

成，已知三种元件的单价分别为2万元、3万元、1万元，单件的可靠性

分别为0.7、0.8、0.6，要求设计中使用元件的总费用不超过10万元，问

应如何设计使设备的可靠性最大?（请使用动态规划方法求解）

答：该题中元件A，B，C是串联在一起的，为保证可靠性，在条件允许

的情况下，我们会将多个同种元件并联在一起。

如上图，就是将2件A，1件B，3件C先并联再串联在一起，

由于A，B，C的可靠性分别为0.7，0.8，0.6。

设采用m个A，n个B，1个C串联

该组合整体的可靠性为

约束条件为

且m，n，1都为正整数。

由动态规划的思路，我们先从单价高的B开始分类：

由于A，B，C至少都得有1件，故在10万元为限制的前提下，B最多2

件。

选择2件B时，问题转化为

S.t

由于m与n必须都大于0，故此时必然选择1件A，2件B，此时可靠性为：

0.7×0.96×0.84＝0.56。

选择1件B时，问题转化为

S.t

此时可以选择1件A，5件C；2件A，3件C；或者3件A，1件C。

同理计算可靠性分别为0.55，0.68，0.47。

故可靠性最大的组合为2件A，1件B，3件C，此时可靠性为0.68。

五、（25分）某公司兴建一座港口码头，只有一个装卸船只的位置。设

船只到达的间隔时间和装卸时间都服从负指数分布，预计船只的平均到

达率为3只/天，船只到港后如不能及时装卸，停留一日公司将损失1500

元。现需设计该港口码头的装卸能力（即每日可以装卸的船只数），已

知单位装卸能力每日平均生产费用为2000元，问装卸能力为多大时，每

天的总支出最少?在此装卸能力之下，求：

（1）装卸码头的利用率；

（2）船只到港后的平均等候时间?

（3）船只到港后总停留时间大于一天的概率。

答：设装卸能力为，公司的支出，。

则。

令。

所以时，每天的总支出最少。

（1），；

所以码头的利用率为1－P0＝2/3。

（2）

即船只到港后的平均等候时间是。

（3）设船只到港后的总停留时间T，则T服从的负指数分

布。

分布函数为；

。

六、（25分）已知A、B各自的纯策略及A的赢得矩阵如下表所示，求双

方的最优策略及对策值。

答：在A的赢得矩阵中第4列优超于第2列，第1列优超于第3列，故可划

去第2列和第3列，得到新的赢得矩阵

对于，第二行优超于第4行，因此去掉第4行，得到

对于，易知无最优纯策略，用线性规划的方法求解，其相应的相互对

偶的线性规划模型如下：

利用单纯形法求解第二个问题，迭代过程如下表所示。

11000

CBYBby1y4y5y6y7

0y51[8]31001/8

0y61640101/6

0y714120011/4

检验数11000

1y11/813/81/8001/3

0y61/401/2－3/4101/2

0y71/20[21/2]－1/2011/21

检验数05/8－1/800

1y13/28101/70－1/28

0y619/8400－61/841－1/21

1y41/2101－1/2102/21

检验数00－2/210－5/84

从上表中可以得到，第二个问题的最优解为：

由最终单纯形表的检验数可知，第一个问题的最优解为：

于是：

所以，最优混合策略为：

对策的值为。

2005年南开大学信息技术科学学院运筹学考研真题

2004年南开大学信息技术科学学院运筹学考研真题

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

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

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

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

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

学院：140商学院

考试科目：897运筹学（商学院）

专业：管理科学与工程

一、某厂生产A、B两种产品，需经过金工和装配两个车间加工，有关

数据如表1所示．产品B无论生产批量大小，每件产品生产成本总为400

元。产品A的生产成本分段线性：第1件至第70件，每件成本为200元；

从第71件开始，每件成本为190元。试建立线性整数规划模型，使该厂

生产产品的总利润最大。（本题共15分）

答：设x1，x2为产品A、B的个数，

则建立线性整数规划模型如下：

二、现有一个线性规划问题（p1）

maxz1＝CX

其对偶问题的最优解为Y*＝（y1，y2，y3，…，ym）。另有一线性规划

（p2）：

maxz2＝CX

T

其中，d＝（d1，d2，…，dm）。求证：maxz2≤maxz1＋Y*d（南开大学

2011年研）

证：问题1的对偶问题为：

问题2的对偶问题为：

易见，问题1的对偶问题与问题2的对偶问题具有相同的约束条件，从

而，问题1的对偶问题的最优解

一定是问题2的对偶问题的可行解。

令问题2的对偶问题的最优解为，则。

因为原问题与对偶问题的最优值相等，所以：

三、某工厂计划生产甲、乙、丙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单位.，则由题意

得：

加入松弛变量后，利用单纯形法计算如下：

cj243000

CBXBbx1x2x3x4x5x6

0x46003[4]2100

0x5400212010

0x6800132001

243000

4x21503/411/21/400

0x52505/40[3/2]－1/410

0x6350－5/401/2－3/401

－101－100

4x2200/31/3101/3－1/30

3x3500/35/601－1/62/30

0x6800/3－3/500－2/3－1/31

－4/900－5/6－2/30

因此已得到最优解，即不生产产品甲，乙和丙的产量分别为200/3，和

500/3单位。

获得最大利润（万元）

2．即，此时，各非基变量的检验数不发生变化，故最优基

B不改变。

（万元）；

（万元）；

为企业带来收益300－200＝100（万元）。

3．设这种产品产量为x7单位，则约束方程增加一列向量

在最终单纯性表为

故投产这种产品合算。

四、某科学试验可用1#、2#，3#三套不同仪器中的任一套去完成。每做

完一次试验后．如果下次仍用原来的仪器，则需要对该仪器进行检查整

修而中断试验：如果下次换用另外一套仪器，则需拆装仪器。也要中断

试验。假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪

器换下来隔一次再重新使用时，不会由于整修而影响试验。设i#仪器换

#

成j仪器所需中断试验的时间为tij，如表3所示。现要做4次试验，问应

如何安排使用仪器的顺序，使总的中断试验的时间最小?（本题共20

分）

###

答：设A、B、C分别代表三套仪器1、2，3，Ai表示在第i次实验中用

仪器A，依此类推Bi、Ci，并设虚拟开始S和结束点D。则得如下网络

图：

求总的中断试验的时间最小，即找最短路问题，利用Dijkstra算法计算

如下：

（1）j＝0，S0＝{S}，P（S）＝0

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

则S1＝（S、A1、B1、C1），。

（2）j＝1

则S2＝（S、A1、B1、C1、A2、B2、C2）

（3）j＝2

则S3＝（S、A1、B1、C1、A2、B2、C2、A3、B3、C3）

（4）j＝3

则S4＝（S、A1、B1、C1、A2、B2、C2、A3、B3、C3、A4、B4、

C4），最后标号D，则标号结束。

（5）比较T（A4）、T（B4）、T（C4），可得出，T（B4）最小，逆序

追踪得使总的中断试验的时间最小的使用顺序是：，即

3#－2#－3#－2#。

五、某农场考虑是否提早种植某种作物的决策问题，如果提早种，又不

遇霜冻．则收入为45元：如遇霜冻，则收入仅为10万元．遇霜冻的概率

为0.4。如不提早种，又不遇霜冻．则收入为35万元：即使遇霜冻．受

灾也轻，收入为25万元，遇霜冻的概率为0.2，已知：

（1）该农场的决策者认为：“以50%的机会每45万元．50%的机会得10

万元”和“稳获35万元”二者对其来说没有差别：

（2）该农场的决策者认为：“以50%的机会得45万元，50%的机会得35

万元”和“稳获40万元”二者对其来说没有差别：

（3）该农场的决策者认为：“以50%的机会得35万元，50%的机会得10

万元”和“稳获25万元”二者对其来说没有差别。

问题如下：

1．说明该决策者对风险的态度，按期望效用最大的原则，该决策者应

做何种决策?

2．按期望收益最大的原则，该决策者又应做何种决策?

答：1．将最高收益45万元的效用定为10，记为。把最低收益

值10万元的效用定为0，记为

。

则决策者对风险的态度可以表示为：

；

；

。

令提早种的期望效用为，不提早种的期望效用为。则：

；

；

，所以，决策者的决策应为不提早种。

2．令提早种的期望收益为，不提早种的期望收益为。

，所以，决策者的决策应为不提早种。

六、某产品从仓库Ai（i＝1，2，3）运往市场Bj＝（j＝1，2，3，4）销

售，已知各仓库的可供应量、各市场的需求量及从A1仓库到B1市场路径

上的容量如表4所示（表中数字0表示两点之间无直接通路），请制定一

个调运方案使从各仓库调运产品总量最多。

答：该问题是求最大流问题，由题得网络图，其中S、D是虚拟开始和

结束点，各路径最大容量如图所示，初始流量为0：

（1）标号过程

①首先给S标号（0，＋∞），检查S，在弧（S，A1）上，，则

给A1标号（S，20），同理，标号A2（S，20），A3（S，100）

②任选一点A1进行检查，在弧（A1，B1）上，，则给B1标号

（A1，20）

③检查B1，在弧（B1，D）上，，则给D标号（B1，20），这样

找到了一条增广链，S－A1－B1－D

（2）调整过程

由（1）知，，得新的可行流量图：

依据上述方法，重复标号及调整过程，直到不存在增广链为止，最终得

最大流量图：

调运方案如下表所示：

B1B2B3B4实际供出量

A1101020

A210515

A3201010545

实际得到量2020202080

七、某公司生产两种小型摩托车，其中甲型完全由本公司制造，而乙型

是进口零件由公司装配而成，这两种产品每辆所需的制造、装配及检验

时间如下表5所示。

如果公司经营目标的期望值和优先等级如下：

P1：每周的总利润至少为3000元：

P2：每周甲型车至少生产5辆；

p3：尽量减少各道工序的空余时间，三工序的权系数和它们的每小时成

本成比例。且不允许加班。请建立这个问题的运筹学模型（不用求

解）。

答：设每周甲乙两种车生产数量分别为x1，x2，由表可知，两者每辆的

生产成本是a和b。

则。

按决策者所要求的，这个问题的数学模型为：

八、案例分析：需要多少个服务人员?

某商科技公司的MIS中心处理本公司信息系统的维护服务。公司其他部

门职员打电话到信息中心进行咨询和服务请求，不过如果恰巧所有服务

人员都在忙的时候，该职员就必须等待。该中心每小时平均接受到40个

服务请求，