目錄

第一部分南開大學(xué)806運籌學(xué)歷年考

研真題

2011年南開大學(xué)信息技術(shù)科學(xué)學(xué)院

813運籌學(xué)考研真題

2011年南開大學(xué)信息技術(shù)科學(xué)學(xué)院

813運籌學(xué)考研真題及詳解

2005年南開大學(xué)信息技術(shù)科學(xué)學(xué)院

運籌學(xué)考研真題

2004年南開大學(xué)信息技術(shù)科學(xué)學(xué)院

運籌學(xué)考研真題

第二部分南開大學(xué)其他學(xué)院運籌學(xué)

歷年考研真題

2012年南開大學(xué)商學(xué)院915運籌學(xué)考

研真題

2011年南開大學(xué)商學(xué)院915運籌學(xué)考

研真題

2011年南開大學(xué)商學(xué)院915運籌學(xué)考

研真題及詳解

2010年南開大學(xué)商學(xué)院887運籌學(xué)考

研真題

第一部分南開大學(xué)806運籌學(xué)歷年考研真題

2011年南開大學(xué)信息技術(shù)科學(xué)學(xué)院813運籌學(xué)考研真題

2011年南開大學(xué)信息技術(shù)科學(xué)學(xué)院813運籌學(xué)考研真題及詳解

南開大學(xué)2011年碩士研究生入學(xué)考試試題

學(xué)院：034信息技術(shù)科學(xué)學(xué)院

考試科目：813運籌學(xué)（信息學(xué)院）

專業(yè)：運籌學(xué)與控制論

一、（35分）已知某工廠計劃生產(chǎn)A、B、C三種產(chǎn)品，備產(chǎn)品均需使用

甲、乙、丙這三種設(shè)備進行加工，加工單位產(chǎn)品需使用各設(shè)備的時間、

單位產(chǎn)品的利潤以及各設(shè)備的工時限制數(shù)據(jù)如下表所示。試問：

（1）應(yīng)如何安排三種產(chǎn)品的生產(chǎn)使得總利潤最大?

（2）若另有兩種新產(chǎn)品D、E，生產(chǎn)單位D產(chǎn)品需用甲、乙、丙三種設(shè)

備12小時、5小時、10小時，單位產(chǎn)品利潤2.1千元；生產(chǎn)單位E產(chǎn)品需

用甲、乙、丙三種設(shè)備4小時、4小時、12小時，單位產(chǎn)品利潤1.87千

元，請分別回答這兩種新產(chǎn)品投產(chǎn)是否合算?

（3）若為了增加產(chǎn)量，可租用其他工廠的設(shè)備甲，可租用的時間是60

小時，租金1.8萬元。請問是否合算?

（4）增加設(shè)備乙的工時是否可使工廠的總利潤進一步增加?

答：（1）設(shè)生產(chǎn)A、B、C三種產(chǎn)品的數(shù)量分別為x1，x2，x3單位。則可

以得出數(shù)學(xué)模型：

添加人工變量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

已得最優(yōu)解，即只生產(chǎn)A種產(chǎn)品，所得利潤最大。

（2）增加新變量x7，x8，對應(yīng)的c7＝2.1，c8＝1.87，約束矩陣增加兩個

列向量

，

其檢驗數(shù)為：

，

則判斷出：產(chǎn)品D的投產(chǎn)不合算，產(chǎn)品E投產(chǎn)合算。

（3）即，其不影響檢驗數(shù)的結(jié)果，故最優(yōu)解不變。

最終單純形表中

，

故租用設(shè)備甲合算。

（4）當(dāng)增加乙的工時，

，故利潤不會增加。

二、（15分）有A、B、C、D四種零件均可在設(shè)備甲或設(shè)備乙上加工。

已知這兩種設(shè)備上分別加工一個零件的費用如下表所示。又知設(shè)備甲或

設(shè)備乙只要有零件加工就需要設(shè)備的啟動費用，分別為100元和150元。

現(xiàn)要求加工四種零件各3件，問應(yīng)如何安排生產(chǎn)使總的費用最小?請建立

該問題的線性規(guī)劃模型（不需求解）。加工一個零件的費用（單位：

元）

答：設(shè)i＝1，2，3，4分別表示產(chǎn)品A、B、C、D；j＝1，2表示設(shè)備

甲、乙。

xij表示產(chǎn)品i在設(shè)備j上生產(chǎn)的個數(shù)，，

則得線性規(guī)劃模型如下：

其中

三、（25分）某工程公司在未來1—4月份內(nèi)需完成三項工程：第一項工

程的工期為1—3月份，總計需勞動力80人月；第二項工程的工期為1—4

月份，總計需勞動力100人月；第三項工程的工期為3—4月份，總計需

勞動力120人月。該公司每月可用勞力為80人，但任一項工程上投入的

勞動力任一月內(nèi)不準(zhǔn)超過60人。問該工程公司能否按期完成上述三項工

程任務(wù)，應(yīng)如何安排勞力?（請將該問題歸結(jié)為網(wǎng)絡(luò)最大流問題求解）

答：可以構(gòu)建如下網(wǎng)絡(luò)圖（弧上數(shù)字為最大流量）。

其中，結(jié)點1、2、3、4分別代表1、2、3、4月份，結(jié)點5、6、7分別代

表第一、二、三項工程。通過標(biāo)號與調(diào)整，得到的最大流如下圖所示。

該最大流問題有多重最優(yōu)解，上圖僅給出一種。

所以該公司能按期完成上述三項工程任務(wù)，安排勞力的方案可以為：1

月份，安排60人做第一項任務(wù)、20人做第二項任務(wù)；2月份，安排60人

做第二項任務(wù)；3月份，安排60人做第三項任務(wù)、20人做第一項任務(wù)；4

月份，安排60人做第四項任務(wù)、20人做第三項任務(wù)。

四、（25分）某工廠設(shè)計的一種電子設(shè)備由A、B、C三種元件串聯(lián)而

成，已知三種元件的單價分別為2萬元、3萬元、1萬元，單件的可靠性

分別為0.7、0.8、0.6，要求設(shè)計中使用元件的總費用不超過10萬元，問

應(yīng)如何設(shè)計使設(shè)備的可靠性最大?（請使用動態(tài)規(guī)劃方法求解）

答：該題中元件A，B，C是串聯(lián)在一起的，為保證可靠性，在條件允許

的情況下，我們會將多個同種元件并聯(lián)在一起。

如上圖，就是將2件A，1件B，3件C先并聯(lián)再串聯(lián)在一起，

由于A，B，C的可靠性分別為0.7，0.8，0.6。

設(shè)采用m個A，n個B，1個C串聯(lián)

該組合整體的可靠性為

約束條件為

且m，n，1都為正整數(shù)。

由動態(tài)規(guī)劃的思路，我們先從單價高的B開始分類：

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

件。

選擇2件B時，問題轉(zhuǎn)化為

S.t

由于m與n必須都大于0，故此時必然選擇1件A，2件B，此時可靠性為：

0.7×0.96×0.84＝0.56。

選擇1件B時，問題轉(zhuǎn)化為

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分）某公司興建一座港口碼頭，只有一個裝卸船只的位置。設(shè)

船只到達的間隔時間和裝卸時間都服從負(fù)指數(shù)分布，預(yù)計船只的平均到

達率為3只/天，船只到港后如不能及時裝卸，停留一日公司將損失1500

元。現(xiàn)需設(shè)計該港口碼頭的裝卸能力（即每日可以裝卸的船只數(shù)），已

知單位裝卸能力每日平均生產(chǎn)費用為2000元，問裝卸能力為多大時，每

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

（1）裝卸碼頭的利用率；

（2）船只到港后的平均等候時間?

（3）船只到港后總停留時間大于一天的概率。

答：設(shè)裝卸能力為，公司的支出，。

則。

令。

所以時，每天的總支出最少。

（1），；

所以碼頭的利用率為1－P0＝2/3。

（2）

即船只到港后的平均等候時間是。

（3）設(shè)船只到港后的總停留時間T，則T服從的負(fù)指數(shù)分

布。

分布函數(shù)為；

。

六、（25分）已知A、B各自的純策略及A的贏得矩陣如下表所示，求雙

方的最優(yōu)策略及對策值。

答：在A的贏得矩陣中第4列優(yōu)超于第2列，第1列優(yōu)超于第3列，故可劃

去第2列和第3列，得到新的贏得矩陣

對于，第二行優(yōu)超于第4行，因此去掉第4行，得到

對于，易知無最優(yōu)純策略，用線性規(guī)劃的方法求解，其相應(yīng)的相互對

偶的線性規(guī)劃模型如下：

利用單純形法求解第二個問題，迭代過程如下表所示。

11000

CBYBby1y4y5y6y7

0y51[8]31001/8

0y61640101/6

0y714120011/4

檢驗數(shù)11000

1y11/813/81/8001/3

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

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

檢驗數(shù)05/8－1/800

1y13/28101/70－1/28

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

1y41/2101－1/2102/21

檢驗數(shù)00－2/210－5/84

從上表中可以得到，第二個問題的最優(yōu)解為：

由最終單純形表的檢驗數(shù)可知，第一個問題的最優(yōu)解為：

于是：

所以，最優(yōu)混合策略為：

對策的值為。

2005年南開大學(xué)信息技術(shù)科學(xué)學(xué)院運籌學(xué)考研真題

2004年南開大學(xué)信息技術(shù)科學(xué)學(xué)院運籌學(xué)考研真題

第二部分南開大學(xué)其他學(xué)院運籌學(xué)歷年考研真題

2012年南開大學(xué)商學(xué)院915運籌學(xué)考研真題

2011年南開大學(xué)商學(xué)院915運籌學(xué)考研真題

2011年南開大學(xué)商學(xué)院915運籌學(xué)考研真題及詳解

南開大學(xué)2011年碩士研究生入學(xué)考試試題

學(xué)院：140商學(xué)院

考試科目：897運籌學(xué)（商學(xué)院）

專業(yè)：管理科學(xué)與工程

一、某廠生產(chǎn)A、B兩種產(chǎn)品，需經(jīng)過金工和裝配兩個車間加工，有關(guān)

數(shù)據(jù)如表1所示．產(chǎn)品B無論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總為400

元。產(chǎn)品A的生產(chǎn)成本分段線性：第1件至第70件，每件成本為200元；

從第71件開始，每件成本為190元。試建立線性整數(shù)規(guī)劃模型，使該廠

生產(chǎn)產(chǎn)品的總利潤最大。（本題共15分）

答：設(shè)x1，x2為產(chǎn)品A、B的個數(shù)，

則建立線性整數(shù)規(guī)劃模型如下：

二、現(xiàn)有一個線性規(guī)劃問題（p1）

maxz1＝CX

其對偶問題的最優(yōu)解為Y*＝（y1，y2，y3，…，ym）。另有一線性規(guī)劃

（p2）：

maxz2＝CX

T

其中，d＝（d1，d2，…，dm）。求證：maxz2≤maxz1＋Y*d（南開大學(xué)

2011年研）

證：問題1的對偶問題為：

問題2的對偶問題為：

易見，問題1的對偶問題與問題2的對偶問題具有相同的約束條件，從

而，問題1的對偶問題的最優(yōu)解

一定是問題2的對偶問題的可行解。

令問題2的對偶問題的最優(yōu)解為，則。

因為原問題與對偶問題的最優(yōu)值相等，所以：

三、某工廠計劃生產(chǎn)甲、乙、丙3種產(chǎn)品，各產(chǎn)品需要在設(shè)備A、B、C

上進行加工，其所需加工小時數(shù)、設(shè)備的有效臺時和單位產(chǎn)品的利潤表

2所示。

請回答下面三個問題：（本題共20分，其中第一小題10分，后兩小題各

5分）

1．如何安排生產(chǎn)計劃，可使工廠獲得最大利潤?

2．若每月可租用其他工廠的A設(shè)備360臺時，租金200萬元，問是否租

用這種設(shè)備?若租用．能為企業(yè)帶來多少收益?

3．若另外有一種產(chǎn)品，它需要設(shè)備A、B、C的臺時數(shù)分別為2、1、4，

單位產(chǎn)品利潤為4萬元，假定各設(shè)備的有效臺時數(shù)不變，投產(chǎn)這種產(chǎn)品

在經(jīng)濟上是否合算?

答：1．設(shè)生產(chǎn)甲、乙、丙三種產(chǎn)品各為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

因此已得到最優(yōu)解，即不生產(chǎn)產(chǎn)品甲，乙和丙的產(chǎn)量分別為200/3，和

500/3單位。

獲得最大利潤（萬元）

2．即，此時，各非基變量的檢驗數(shù)不發(fā)生變化，故最優(yōu)基

B不改變。

（萬元）；

（萬元）；

為企業(yè)帶來收益300－200＝100（萬元）。

3．設(shè)這種產(chǎn)品產(chǎn)量為x7單位，則約束方程增加一列向量

在最終單純性表為

故投產(chǎn)這種產(chǎn)品合算。

四、某科學(xué)試驗可用1#、2#，3#三套不同儀器中的任一套去完成。每做

完一次試驗后．如果下次仍用原來的儀器，則需要對該儀器進行檢查整

修而中斷試驗：如果下次換用另外一套儀器，則需拆裝儀器。也要中斷

試驗。假定一次試驗時間比任何一套儀器的整修時間都長，因此一套儀

器換下來隔一次再重新使用時，不會由于整修而影響試驗。設(shè)i#儀器換

#

成j儀器所需中斷試驗的時間為tij，如表3所示?，F(xiàn)要做4次試驗，問應(yīng)

如何安排使用儀器的順序，使總的中斷試驗的時間最小?（本題共20

分）

###

答：設(shè)A、B、C分別代表三套儀器1、2，3，Ai表示在第i次實驗中用

儀器A，依此類推Bi、Ci，并設(shè)虛擬開始S和結(jié)束點D。則得如下網(wǎng)絡(luò)

圖：

求總的中斷試驗的時間最小，即找最短路問題，利用Dijkstra算法計算

如下：

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

∵A1，B1，C1到S點距離相同，∴可同時標(biāo)號。

則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），最后標(biāo)號D，則標(biāo)號結(jié)束。

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

追蹤得使總的中斷試驗的時間最小的使用順序是：，即

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

五、某農(nóng)場考慮是否提早種植某種作物的決策問題，如果提早種，又不

遇霜凍．則收入為45元：如遇霜凍，則收入僅為10萬元．遇霜凍的概率

為0.4。如不提早種，又不遇霜凍．則收入為35萬元：即使遇霜凍．受

災(zāi)也輕，收入為25萬元，遇霜凍的概率為0.2，已知：

（1）該農(nóng)場的決策者認(rèn)為：“以50%的機會每45萬元．50%的機會得10

萬元”和“穩(wěn)獲35萬元”二者對其來說沒有差別：

（2）該農(nóng)場的決策者認(rèn)為：“以50%的機會得45萬元，50%的機會得35

萬元”和“穩(wěn)獲40萬元”二者對其來說沒有差別：

（3）該農(nóng)場的決策者認(rèn)為：“以50%的機會得35萬元，50%的機會得10

萬元”和“穩(wěn)獲25萬元”二者對其來說沒有差別。

問題如下：

1．說明該決策者對風(fēng)險的態(tài)度，按期望效用最大的原則，該決策者應(yīng)

做何種決策?

2．按期望收益最大的原則，該決策者又應(yīng)做何種決策?

答：1．將最高收益45萬元的效用定為10，記為。把最低收益

值10萬元的效用定為0，記為

。

則決策者對風(fēng)險的態(tài)度可以表示為：

；

；

。

令提早種的期望效用為，不提早種的期望效用為。則：

；

；

，所以，決策者的決策應(yīng)為不提早種。

2．令提早種的期望收益為，不提早種的期望收益為。

，所以，決策者的決策應(yīng)為不提早種。

六、某產(chǎn)品從倉庫Ai（i＝1，2，3）運往市場Bj＝（j＝1，2，3，4）銷

售，已知各倉庫的可供應(yīng)量、各市場的需求量及從A1倉庫到B1市場路徑

上的容量如表4所示（表中數(shù)字0表示兩點之間無直接通路），請制定一

個調(diào)運方案使從各倉庫調(diào)運產(chǎn)品總量最多。

答：該問題是求最大流問題，由題得網(wǎng)絡(luò)圖，其中S、D是虛擬開始和

結(jié)束點，各路徑最大容量如圖所示，初始流量為0：

（1）標(biāo)號過程

①首先給S標(biāo)號（0，＋∞），檢查S，在?。⊿，A1）上，，則

給A1標(biāo)號（S，20），同理，標(biāo)號A2（S，20），A3（S，100）

②任選一點A1進行檢查，在?。ˋ1，B1）上，，則給B1標(biāo)號

（A1，20）

③檢查B1，在?。˙1，D）上，，則給D標(biāo)號（B1，20），這樣

找到了一條增廣鏈，S－A1－B1－D

（2）調(diào)整過程

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

依據(jù)上述方法，重復(fù)標(biāo)號及調(diào)整過程，直到不存在增廣鏈為止，最終得

最大流量圖：

調(diào)運方案如下表所示：

B1B2B3B4實際供出量

A1101020

A210515

A3201010545

實際得到量2020202080

七、某公司生產(chǎn)兩種小型摩托車，其中甲型完全由本公司制造，而乙型

是進口零件由公司裝配而成，這兩種產(chǎn)品每輛所需的制造、裝配及檢驗

時間如下表5所示。

如果公司經(jīng)營目標(biāo)的期望值和優(yōu)先等級如下：

P1：每周的總利潤至少為3000元：

P2：每周甲型車至少生產(chǎn)5輛；

p3：盡量減少各道工序的空余時間，三工序的權(quán)系數(shù)和它們的每小時成

本成比例。且不允許加班。請建立這個問題的運籌學(xué)模型（不用求

解）。

答：設(shè)每周甲乙兩種車生產(chǎn)數(shù)量分別為x1，x2，由表可知，兩者每輛的

生產(chǎn)成本是a和b。

則。

按決策者所要求的，這個問題的數(shù)學(xué)模型為：

八、案例分析：需要多少個服務(wù)人員?

某商科技公司的MIS中心處理本公司信息系統(tǒng)的維護服務(wù)。公司其他部

門職員打電話到信息中心進行咨詢和服務(wù)請求，不過如果恰巧所有服務(wù)

人員都在忙的時候，該職員就必須等待。該中心每小時平均接受到40個

服務(wù)請求，