十一套名校運籌學(xué)考研和期末試題含詳細答案可作為最后的練兵

1、附錄21234大學(xué) 2008 年管理與運籌學(xué)基礎(chǔ)（運籌學(xué)）試題與.22005 年運籌學(xué)試題與72007 年運籌學(xué)基礎(chǔ)試題與.13交通大學(xué) 2006 年運籌學(xué)與概率統(tǒng)計（運籌學(xué)部分）試題與（運籌學(xué)部分）195大連理工大學(xué) 2006 年運籌學(xué)基礎(chǔ)及應(yīng)用試題與.226哈爾濱工業(yè)大學(xué) 2008 年運籌學(xué)試題與277中國中國科學(xué)技術(shù)大學(xué) 2005 年管理綜合 A試題與（運籌學(xué)部分）.348中國中國科學(xué)技術(shù)大學(xué) 2004 年管理綜合 A試題與（運籌學(xué)部分）.389華10技大學(xué) 2007 年運籌學(xué)理工大學(xué) 2007 年運籌學(xué).43.49試題與試題與11東北財經(jīng)大學(xué) 2007-2008 學(xué)年第 1 學(xué)期運籌學(xué)

2、期末試題與.56運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢附錄1南京大學(xué) 2008 年管理與運籌學(xué)基礎(chǔ)（運籌學(xué)）考研試題與答案min 2x1 3x2 5x3 2x4 3x5x1 x2 2x3 x4 3xj4 s.t.2x1 x3 3x3 x4 x53一、（15 分）已知線性規(guī)劃問題的對偶問題的最優(yōu)解為x 0，j 1，2，5j43運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢y ，y ，請給出原問題的解。*1255max z 4 y1 3y2 y1 2 y22y y 3122 y 3y 5解：先寫出對偶問題：12s.t.y y 212 3y1 y23y1 y2043將 y 、y 代入五個約束條件可知

3、、為嚴格不等式。*1255由松弛定理得： x* x* x* 0 。因 y* 0，y* 0 為嚴格不等式，所以原問題中兩個23412約束為等式，故：x1 3x5 42x x 315可得 x* x* 1 。從而求得原問題的解為 x*=(1,0,0,0,1)T，最小值為 5。15二、（10 分）某廠組裝三種產(chǎn)品，有關(guān)數(shù)據(jù)如表附錄 1-1 所示。表附錄 1-1要求確定三種產(chǎn)品的日生產(chǎn)計劃，并滿足：（1）工廠希望裝配線盡量不超負荷生產(chǎn)；（2）每日剩余產(chǎn)品盡可能少；（3）日產(chǎn)值盡可能達到 6000 元。試建立該問題的目標規(guī)劃數(shù)學(xué)模型。解：設(shè) x1、x2、x3 分別為三種產(chǎn)品的可生產(chǎn)量，對各目標確定的優(yōu)先因

4、子為：P1：條件（1）；產(chǎn)品單件組裝工時日銷量（件）產(chǎn)值（元/件）日總裝配能力工時A B C1.11.31.57060804060803003P2：條件（2）；P3：條件（3）。則目標規(guī)劃的數(shù)學(xué)模型如下：約束（1）：1.1x 1.3x 1.5x d d 30012311約束（2）：對 A 產(chǎn)品， x 70 d d 0運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢122對 B 產(chǎn)品： x 60 d d 0233對 C 產(chǎn)品： x 80 d d 0344約束（3）： 40 x 60 x 80 x d d 60012355目標函數(shù)： min z Pd P (d d d ) Pd 1 122343 5三、

5、（20 分）某工廠要用 A、B 兩種原料來生產(chǎn)甲、乙、丙三種產(chǎn)品，生產(chǎn)單位每種產(chǎn)品的原料消耗量和利潤如表附錄 1-2 所示。表附錄 1-2若現(xiàn)有的 A、B 原料的限量分別為 45 和 30，求：（1）總利潤最大的生產(chǎn)方案；（2）甲產(chǎn)品的單位利潤在何范圍內(nèi)變化時，最優(yōu)生產(chǎn)方案不變；（3）若原料 A 除現(xiàn)有量外無法再增加，而原料 B 可以再購，單價為 0.5。請問是否應(yīng)該購進，最多可購進多少？解：設(shè)生產(chǎn)甲、乙、丙分別 x1、x2、x3，總利潤 z。max z 4x1 x2 5x3 3x 5x 456x122運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢（1）建立數(shù)學(xué)模型如下：。s.t.3x1 4x2

6、5x330 x ，x ，x 0123max z 4x1 x2 5x3 0ix1 0ix36x1 3x2 5x3 x4 45標準化：。求解如表附錄 1-3 所示。s.t. 3x 4x 5x x 301235 x 0，i 1，2，3，4，5 i表附錄 1-3所有 j0，從而 X * (5，0，3，0，0)T ，最大利潤為 35。（2）C1 對應(yīng)基變量 x1，從而 C1 變化時會到起 CB 的變化，進而引起 1 變化。要使最優(yōu)生Cj41500iCBXBbx1x2x3x4x50 x4450 x530635103450196j415000 x4155x36310113/54/5101/5510j1300

7、14x155x331/301/31/30111/52/5j08/301/32/3甲乙丙原料A原料B利潤6343415554產(chǎn)方案不變，應(yīng)保證 j 仍不大于 0。又C C C B1A C a （ j 1，2，3，4，5 ），則可得：jjB1 1ja 0 min 8/ 3，2 / 3 2C min /ajj 1j1j 1/ 3 1/ 3 j1/ 3且C1max j/a1j/a1j 0 1 ，由此可知， C1 3, 6 時最優(yōu)方案不變。1/ 3j2（3）由終表可知，原料 B 的影子價格為 0.5 ，所以應(yīng)該購進，設(shè)最多購進 x6，因 x63系數(shù)為負，則：max z 4x1 x2 5x3 0.5x66

8、x1 3x2 5x345運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢s.t.3x1 4x2 5x330 x6x 0，x 1，2，6i得 x6，加入終表，如表附錄 1-4 所示。表附錄 1-41/ 3 0 1/ 31/ 51/ 3注意到， P 。所有 0 ，從而 X 15 ，即最多購*662 /51j2 /5 進 15。四、（15 分）甲、乙兩人對策。甲手中有三張牌，兩張 K 一張 A。甲拿去一張牌后，宣稱自己手中的牌是 AK，對此，乙可以接受或提出異議。若甲所宣稱的牌與實際相符，乙接受，甲得 1 元；若甲手中是 KK，但他宣稱 AK，乙接受，甲得 2 元；若甲手中是 AK，但他宣稱 KK，乙接受

9、，甲輸 2 元；若面對甲的宣稱，乙提出異議，則輸贏相反，錢數(shù)加倍。請建立對策模型并求出最優(yōu)值和對策值。解：據(jù)題意設(shè) AK/AK 為甲明知手中為 AK，聲稱 AK 這一事件，其他類似，則：S甲 AK / AK , KK / AK , AK / KK , KK / KK ， S乙 AK , KK對策模型為：乙AK AK / AKKK / AK AK / KKKK / KKAK(1, 1)(4, 4)(2, 2)(2, 2)運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢(2, 2)(2, 2)(4, 4)(1, 1)甲Cj415001/2CBXBbx1x2x3x4x5x645x1 x35411/301/

10、31/31/30111/52/52/5j08/301/32/31/61/2 5x615310111x3106/53/511/500j1/25/201/21/205 2 214此矩為零和博弈，則甲的贏得矩陣 A ，乙贏得矩陣為 A 。 422 1y1y2A 為混合對策，利用優(yōu)超原則劃去第 1、3 行，得： x2 24 。2 x14 根據(jù)公式法得 x 1，x 2 ，即 X * (0, , 0, )3312T 為甲的對策。2433 2 1 T運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢同理得乙的對策Y * ,。 3 3 五、（15 分）某工程有 17 道工序，如表附錄 1-5 所示。表附錄 1-5繪出

11、工程網(wǎng)絡(luò)圖。確定關(guān)鍵路線及完工期。解：（1）由題意，繪出網(wǎng)絡(luò)圖如圖附錄 1-1 所示。圖附錄 1-1（2）各工序事項最早時間和事項最遲時間分別為：0,0；90,125118,135；60,60；70,70；130,130；80,118；81,98；11 1)123,140；80,118；93,110；12 145,145；613 147,147；14 152,152關(guān)鍵路線為：12 13 14 。對應(yīng)的工序為：AFINOQ。7咨詢2清華大學(xué) 2005 年運籌學(xué)考研試題與答案（回憶版）什么樣的解是線性規(guī)劃的退化解，退化為什么會引起求解過程的循環(huán)？解：單純形法計算中用 規(guī)則確定換出變量時，有時存在

12、兩個以上相同的最小比值，這樣在下一次迭代中就有一個或幾個基變量等于零，這就出現(xiàn)退化解。這時換出變量 xl 0 ，迭代后目標函數(shù)值不變。這時不同基表示為同一頂點。當出現(xiàn)退化時，進行多次迭代，而基從 B1， B2，又返回到 B1，從而形成求解過程的循環(huán)。用 EXCEL 求解線性規(guī)劃并進行敏感性分析時，在敏感性分析表中，可以找到“遞減成本”的數(shù)據(jù)，請解釋什么是遞減成本，寫出其表達式，并解釋遞減成本的經(jīng)濟含義？解：遞減成本的經(jīng)濟含義是資源對目標函數(shù)的邊際貢獻。遞減成本指的是檢驗數(shù)，在很多計算機軟件中叫做遞減成本。含義應(yīng)理解為該變量所對應(yīng)的目標函數(shù)系數(shù)應(yīng)該增加多少或減少多少該變量才有可能入基。對于一個求

13、極大化的問題來說，當線性規(guī)劃問題達到最優(yōu)時，遞減成本總是小于或等于 0 的。它的經(jīng)濟含義是增加該產(chǎn)品的單位生產(chǎn)量給目標函數(shù)帶來的貢獻；而影子價格指的的對偶解，就是 CB 乘 B 逆，它的大于 0 或者小于 0 標明的是企業(yè)購進資源后對獲得利潤的影響。簡述求解整數(shù)規(guī)劃的分支定辦法中“分支”與“定界”的含義？解：設(shè)有最大化的整數(shù)規(guī)劃問題 A，與它相應(yīng)的線性規(guī)劃為問題 B，從解問題 B 開始，若其最優(yōu)解不符合 A 的整數(shù)條件，那么 B 的最優(yōu)目標函數(shù)必是 A 的最優(yōu)目標函數(shù) z*的上界，記作 z ；而 A 的任意可行解的目標函數(shù)值將是 z*的一個下界 z （即為“定界”）。將 B 的可行域分成子區(qū)域

14、（即為“分支”），逐步減小 z 和增大 z ，最終求得 z*。簡述求最大流問題的最小割最大流定理。解：任一個網(wǎng)絡(luò) D 中，從 vs 到 vt 的最大流量等于分離 vs、vt 的最小截集的容量。某企業(yè)使用四種化工原料生產(chǎn)六種化工產(chǎn)品，生產(chǎn)每種產(chǎn)品的投入產(chǎn)出系數(shù)如表附錄2-1 所示。表附錄 2-1（表中的成本和價格的單位為萬元/噸，最大、最小需求數(shù)量和原料可用數(shù)量的單位為噸）每種產(chǎn)品的投入產(chǎn)出系數(shù)列在表中，例如生產(chǎn)一噸 A 產(chǎn)品需要 0.5 噸原料 1，0.1 噸原料 2，0.2 噸原料 3，0.4 噸原料 4，其他產(chǎn)品需要的原料數(shù)可依此類推。原料的成本和可使用數(shù)量列8運籌學(xué)，詳見：網(wǎng)學(xué)天地（）在

15、表的最后兩列；產(chǎn)品的在表的最后一行。產(chǎn)品的產(chǎn)量應(yīng)該大于最小需求量，同時也要小于最大需求量。構(gòu)造的求銷售利潤最大的線性規(guī)劃模型用 EXCEL 求解后的敏感性分析報告如表附錄 2-2 所示。表附錄 2-2 可變單元格表附錄 2-2 約束（1）該問題的最優(yōu)解中應(yīng)該有幾個基變量（提示：應(yīng)包括松弛變量中的基變量），根據(jù)敏感性分析表中提供的信息，判斷那些變量是基變量？（2）從表中可知：產(chǎn)品 D 的利潤最高（34 萬元/噸），但它對目標函數(shù)的邊際貢獻卻最?。ㄟf減成本為-0.1 萬元/噸）；產(chǎn)品 C 的利潤最低（21 萬元/噸），但它對目標函數(shù)的邊際貢獻卻最大（遞減成本為 12.3 萬元/噸），為什么會有這樣

16、的現(xiàn)象，請解釋其中的原因？（3）四種原料中哪種原料的業(yè)可以出的最高價格是多少？價格最高，如果企業(yè)還可以從市場上獲得這種原料，企在保持最優(yōu)基不變的前提下，你建議該企業(yè)應(yīng)繼續(xù)采購哪種原材料，采購多少可以使企業(yè)獲得最大的收益？產(chǎn)品 C 價格在什么范圍內(nèi)變化時該問題的最優(yōu)基保持不變？該企業(yè)正考慮生產(chǎn)一種新產(chǎn)品 E，該產(chǎn)品計劃售價為 60 萬元/噸，需要 0.7 噸原料 1，0.1 噸原料 2，0.2 噸原料 3 和 0.3 噸原料 4，是否應(yīng)該生產(chǎn)這種新產(chǎn)品？解：（1）由遞減成本和束 3 的松弛變量。價格的值可知，該問題應(yīng)該有 4 個基變量，分別是 B、E、F 和約利用會計方法計算的從表中可以出的價格

17、價格計算的成本即遞減成本，與會計成本會有很大的不同，因此會出現(xiàn)用產(chǎn)品價格和用，原料 4 的價格計算的成本的差別。價格最高。如果企業(yè)可以從市場上獲得這種原料，企業(yè)過其價格，故最高價格為 27.7。（4）比較原料的價格與其市場價格，企業(yè)應(yīng)采購原材料 2，又因為原料 2 允許的增量為 12 噸，故企業(yè)最多采購 12 噸，則利潤可增加 264 萬元。9運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢（5）C 的原價為 PC 45 元，若保持原最優(yōu)基不變，從表中可以得到12.3PC ，故 C 的價格取值范圍為：32.7,+。（6）原料 1 的影子價格為 43.8，原料 2 的影子價格為 40，原料 3 的影子

18、價格為 32；原料 4 的影子價格為 52.7。成本=56.87m1，甲贏（m1+1）；若 n2m2，甲贏（m2+1）；若 n1m1，甲輸（n1+1）；若 n21 時， 1/ 7 / 7 0 故應(yīng)選 x4 為換入變量，繼續(xù)迭代，如表附錄 7-6 所示。表附錄 7-6此時最優(yōu)解為(x , x , x , x )T = (7,0, 0, 2)T ，對應(yīng) X * (x , x , x , x )T = (7,1/ 7, 0, 4)T 。12341234綜 上 所 述 可 知 ： 25 / 3時，X * (3, 29/7, 0,0)T ； 25 / 31時 ，X * (45 / 7,1/ 7, 4 /

19、 7, 0)T ； 1時，X * (7,1/ 7,0, 4)T 。（4）由原最優(yōu)表可知，資源 y 、y 的影子價格分別為：y* M 1/ 7 ，y* M 16 / 7 。1112因為 y1 y2 ，故資源 y2 相對更緊缺，應(yīng)優(yōu)先擴大第二個約束條件。3證明：若線性規(guī)劃問題的可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點處達到最優(yōu)。證明：設(shè) X (1) ， X (2) ， X (k) 是可行域的頂點，若 X (0) 不是頂點，且目標函數(shù)在 X (0)處達到最優(yōu)，Z * CX (0) （標準型是 Z * max Z ）。因 X (0) 不是頂點，則它可以用 D 的頂點kk線性表示為：

20、X i X， i20 ， i 1。因此：i 1運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢(0)(i)i 1kk i iCX C X CX(0)(i )(i )i 1i 1在所有的頂點中，必然能找到某一個頂點 X (m) ，使CX (m) 是所有CX (i) 中最大者，并且kk i i將 X代替式中的所有 X，這就得到 CX CX(m)(i) (1)(m)(m)CX，由此得到，i 1i 1CX (0)CX (m) 。根據(jù)假設(shè)CX (0) 是最大值，所以只能有CX (0) CX (m) ，即目標函數(shù)在頂點CX (m) 處也達到最大值。針對標準型 Z * min Z ，同理可證。綜上可知，目標函數(shù)一

21、定可以在其可行域的頂點處達到最優(yōu)。C2+530MMCBXBbx1x2x3x4x5x62+x145/716/701/71/75/73x34/701/711/7*1/72/7z102/7+45/7050/75/701/7+/7M+1/71/7M-16/7-5/72+x171110010 x44017112z14+70071MM2C2+530MMCBXBbx1x2x3x4x5x62+x145/716/701/71/75/73x34/701/7*11/71/72/7z102/7+45/7050/76/701/7+/7M+1/71/7M16/75/72+x131061115x24017112z14+30

22、050+67+M7M+10+37運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢4一個公司要分派 5 個推銷員去 5 個地區(qū)推銷某種產(chǎn)品，5 個推銷員在各個地區(qū)推銷這種產(chǎn)品的預(yù)期利潤如表附錄 7-7 所示。問應(yīng)如何分派這 5 個推銷員才能使得公司的利潤最大。表附錄 7-7解：用匈牙利法求解：108811101181111101871220179999用最大數(shù)20減去7 各行各列減去各行各列元素其最小元素991323111011778至此，由以上過程及結(jié)果可知，最優(yōu)指派計劃為：甲C，乙E，丙B，丁A，戊D，總利潤 Z 18 20 12 13 9 72 。ABCDE甲1510121012乙1112999

23、丙1020丁9戊38運籌學(xué)考研全套教程，詳見： 網(wǎng)學(xué)天地（）咨詢8中國科學(xué)院中國科學(xué)技術(shù)大學(xué) 2004 年管理綜合 A考研試題與答案（運籌學(xué)部分）一、某廠在計劃期內(nèi)擬生產(chǎn)甲、乙、丙三種產(chǎn)品，產(chǎn)品甲依次經(jīng) A、B 設(shè)備加工，產(chǎn)品乙經(jīng) A、C 設(shè)備加工，產(chǎn)品丙經(jīng) C、B 設(shè)備加工，已知有關(guān)數(shù)據(jù)如表附錄 8-1 所示，請為該廠制訂一個最優(yōu)的生產(chǎn)計劃。（建模并求解）表附錄 8-1解：設(shè)生產(chǎn)甲 x1 件，乙 x2 件，兩 x3 件，設(shè)該廠追求利潤最大化，建模如下：max z (50 15)x1 (100 25)x2 (45 10)x3 200 x1 100 200 x2x1x xx332 1020 20

24、10 520 x1x20運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢40s.t. 2010400 520整理可得：max z 10 x1 25x3x1 x 4x x 120023x ，x ，x 0 123用單純形法求解，過程如表附錄 8-2 所示。表附錄 8-2C102515000CBXBbx1x2x3x4x5x60 x410002101000 x58001020100 x61200041001z0102515000機器產(chǎn)品機器生產(chǎn)率（件/小時）原料成本（元）產(chǎn)品價格（元）ABC甲10201550乙20525100丙10201045機器成本（元/小時）200100200每周可用小時數(shù)504060

25、39由以上最優(yōu)表可知，最優(yōu)生產(chǎn)計劃為：甲 6400/17 件，乙 4200/17 件，丙 3600/17 件。二、已知線性規(guī)劃問題：min z 2x1 x2 2x3運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢x1 x2 x3 4s.t.x x kx 6123x 0，x 0，x 無約束 123其是優(yōu)解為： x1 5 ； x2 0 ； x3 1 。寫出該問題的對偶問題，并求出對偶問題的最優(yōu)解；求出 k 的值。解：原問題的對偶問題：maxW 4 y 16 y 2 y1 y22 y y 112 y y 212 y 無約束，y 0 12（2）因為原最優(yōu)解中 X * 5 0 ， X * 1 0 ，故對偶問題

26、的、兩式為等式，13即： y1 y2 2 y y 2 12又由強對偶性可知： min z* maxW * 12 ，故4 y1 6 y2 12 y1 0運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢聯(lián)立上述各式解得： y 22k 1即對偶問題的是優(yōu)解為Y * (0, z)* ，k=1。三、分配甲、乙、丙、丁四個人去完成五項任務(wù)，各人完成各項任務(wù)的時間如表附錄 8-3所示。由于任務(wù)數(shù)多于人數(shù)，故決定其中有一個人可能完成兩項任務(wù)，其余三人每人完成一塊。0 x4700201/4101/40 x580010201025x2300011/4001/4z750010035/40025/410 x1350101/

27、81/201/80 x54500017/81/211/825x2300011/4001/4z11000001050510 x16400/171001/171/172/1715x33600/170014/178/171/1725x24200/170101/172/174/17z223000/1700015/1730/1795/1740運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢試確定總花費時間為最少的指定方案。表附錄 8-3解：這是不平衡分配問題，依題意可增加一人“戊”，令其完成 AE 項任務(wù)均用時最少，以下用匈牙利法解：35494434343948375237413638463652305033

28、30474342 5542046171204047601247507由以上分析可知，最優(yōu)指派方案是：甲B，乙C、D，丙E，丁A。最少時間為：T=39+36+30+42+34=181。四、證明：線性規(guī)劃問題的可行域 D 是個凸域。證明：設(shè)其可行域 D 為：n Pj x jD X x1，x2，xn T b，xj0，j 1，2，nj 0n為了證明滿足線性規(guī)劃問題的約束條件 Pj xj b，x j0，j 1，2，n 的所有 j 1點（可行解）組成的集合是凸集，只要證明 D 中任意連接上的點必然成 D 內(nèi)即可。任務(wù)人ABCDE甲3539415247乙4948363043丙4447385042丁34524

29、6335541 (x(1)，x(1)，x(1) )T ，X (1) (x(2)，x(2)，x(2) )T 是 D 內(nèi)的任意兩點，且設(shè) X (1)12n12n X (2) ，則有：X (1)n j jP x b ， x(1)0 ，j=1，2，n(1)j運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢j 1nP x b(2)(2)， x 0 ，j=1，2，nj jjj 1令 X (x , x , x )T 為 X (1) 、 X (2) 連線上的任意一點，即：12nX X (1) (1 ) X (2)(01)X 的每一個分量是 x x (1 )x(1)(2)j，將它代入約束條件，得：jjnnnnnj 1

30、Px P x (1 )x P xP x P x(1)(2)(1)(2)(2)jjijjjj jj jjj 1j lj 1j 1 b b b b01 0 ，所以，x 0 ，j=1，2，n。由此可見 X D ，(1)(2)又因 x、x 0 ，jD 是凸集。jj五、設(shè)有如下均非線性規(guī)劃規(guī)劃問題：min f ( X ) (x 3)2 (x 2)212s.t.g ( X ) x x20121g( X ) 2 x x 0212用圖解法求上述問題的最優(yōu)解；簡述庫恩塔克條件，并用（1）的結(jié)果說明其幾何意義。解：（1）如圖附錄 8-1 所示，原非線性規(guī)劃問題的最優(yōu)解為：X * (1,1)T ， min f (

31、X *) (1 3)2 (1 2)2 5運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢圖附錄 8-1（2）因為f ( X ) 2(x1 3), 2(x2 2) ， g1 ( X ) 2x1,1， g2 ( X ) 1, 1 。所以，庫恩塔克條件為：422(x1 3) 2x1 y1 y2 0運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）2(x 2) y y 0212咨詢K.T. y (x x2 ) 0121Y (2 x x ) 0212 y1，y20將最優(yōu)解 X * (1,1)T 代入 K-T 條件中，可得： y 2 ， y 8 。1233所以， f ( X ) 2 g( X ) 8 g ( X ) 0 。

32、又 g ( X *) 2,1與 g ( X *) 1, 1 ，21233故f ( X ) 為g1( X )和g2 ( X ) 的非負線性組合，所以其幾何意義為： f ( X ) 的最優(yōu)值在g1 ( X )與g2 ( X ) 的公共區(qū)域內(nèi)取值。43運籌學(xué)考研全套教程，詳見： 網(wǎng)學(xué)天地（）咨詢9華中科技大學(xué) 2007 年運籌學(xué)考研試題與答案一、（20 分）已經(jīng)知一個線性規(guī)劃問題的靈敏度分析報告如表附錄 9-1 所示。表附錄 9-1 變動單元格表附錄 9-1 約束條件當 X1 的目標系數(shù)增加 2 單位，同時 X2 的目標系數(shù)減少 5 單位時最優(yōu)解是否改變？2解：X1 的目標系數(shù)增加 2 個單位時，

33、40% ；X2 的目標系數(shù)減少 5 個單位時，5514 35.7% 。因為40% 35.7% 75.7% 100% ，所以最優(yōu)解不變。二、（20 分）已知線性規(guī)劃：max z 3x1 C2 x2 C3 x3x1 3x2 3x3 x4 20運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢6x 2x 5x x 40s.t.12353x 6x 5x x 601236x ，x ，x ，x ，x ，x 0 123456最優(yōu)單純形表如表附錄 9-2 所示。表附錄 9-2填空完成上面單純形表，并求其對偶問題的最優(yōu)解。求出 C2 和 C3 的值，并確定 C3 增加多少時，線性規(guī)劃有無窮多個最優(yōu)解。解：0 1/ 30

34、（1）x5、x6 為基變量，則 B1 2/3 10 。1 20CBXBbx1xx3x4x5x6x211/30 x50/30 x60CBB-1b0/301/200單元格名稱最終值影子價格右端值允許增加值允許減少值E4第一約束66266IE+3013.33333E5第二約束32321265E6第三約束47.4203611.42IE+30單元格變量名最終值減少成本目標系數(shù)允許增加值允許減少值B9X10535IE+30C9X218.5702714D9X35.1406IE+303.544運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）0 20 1/ 30咨詢由(C ,0, 0) 2 / 310 40 40 得：

35、C 2 。2231 60 200 31/ 30 C (2,0, 0) 2 / 310 5 C 2 1 得： C 3 。由 C CB1P 33B3333221 520 0 11/ 3010 C C B1P 3 (2, 0, 0) 2 / 30 6 711B131 3 2 2同理， C CB1P44B43完成單純形表，如表附錄 9-3 所示。表附錄 9-3 240由單純形表可得對偶問題的最優(yōu)解為Y ，*0 0 ，最優(yōu)值為。 33（2） C 2，C 3 ，設(shè) C 增加C 時，有無窮多解，則 0332332 3 C 2 0 得： C 1 。由 (C C ) CB1P 23 333B332三、（15 分

36、）求解線性規(guī)劃：max z 4x1 6x2 3x3 6x4運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢x1 2x2 2x3 x4 2x53s.t.3x1 x x x 3x 62345x ，x ，x ，x ，x 0 12345解：化為標準形如下：max z 4x1 bx2 3x3 6x4 0 x5 0 x6 0 x7 Mx8x1 2x2 2x3 x4 2x5 x6 3s.t.3x x x x 3x x x 61234578x 0，i 1，2，8 i采用單純形法求解，如表附錄 9-4 所示。Cj323/2000CBXBbx1x2x3x4x5x62x220/31/3111/3000 x540/320/

37、3032/3100 x620501201CBB-1b40/37/301/22/30045表附錄 9-4T 33此時檢驗均小于等于 0，故已達最優(yōu)，最優(yōu)解為 X * , 0, 0, 0, 0, 0, 0 ，最優(yōu)值為 22max z 4 3 6 3 15 。22四、（10 分）某人求解某平衡運輸問題，得到該問題的最優(yōu)運輸方案和最優(yōu)運費，然后將某一產(chǎn)地的產(chǎn)量增加 20 單位，同時將另一銷地銷量增加 20 單位，其它數(shù)據(jù)不變，重新求最優(yōu)運輸方案，結(jié)果發(fā)現(xiàn)最優(yōu)運費在運量增加后反而下降，請解釋為什么會發(fā)生這類現(xiàn)象？解：運輸問題數(shù)學(xué)模型如下：min z CX運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢m xi

38、j ai j 1s.t.x bn iji i 1xij0，i 1，2，n；j 1，2，m當 ai 與 bj 同時變化時， ai 20，bj 20 。運輸問題仍保持平衡，由于分配方案將會隨著供需量的變化而變化，原來以高價運送到需求點的貨物，可能會由于另一個運費更低的供求點貨物的增加，而轉(zhuǎn)變?yōu)閺倪@一低運價處供貨，這樣一調(diào)整，就有可能出現(xiàn)即使供需增加，總運費反而減少的現(xiàn)象。五、（15 分）某人需要在近 K 周內(nèi)購買一種產(chǎn)品，估計未來第 k（k=1，2，K）周價格浮動的概率如表附錄 9-5 所示，試建立數(shù)學(xué)規(guī)劃模型求在哪一周以什么價格購買，使采購價格的數(shù)學(xué)期望值最小。表附錄 9-5單價第 k 周概率3

39、00P1k400P2k500P3kCj4636000MCBXBbx1x2x3x4x5x6x7x80 x63122121003Mx86311130112CjZj4+3M6+M3+M6+M3M0M00 x6105/35/32/3111/31/33/54x1211/31/31/3101/31/36CjZj014/35/314/3404/3M4/36x23/50112/53/51/51/53/24x14/51001/54/51/52/52/59CjZj00314/534/514/52/5M2/56x43/205/25/213/23/21/21/24x13/211/21/201/21/21/21/2Cj

40、Zj071001177M+1461，表示在第k周購買解：設(shè)階段變量 k=1，2，K 表示 k 個星期； tk ； skE 表示0，否則第 k 周等待，第 k+1 周購買的的期望值； fk (sk ) 表示第 k 周至第 K 周的最優(yōu)期望值。狀態(tài)轉(zhuǎn)移方程如下： fk (sk ) minsk , skE 1，skskEt運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢0，s s kkkE3skE xk fk+1 (sk+1 )Piki 1 300P1k 400P2k 500P3ksk 1,E六、（15 分）用動態(tài)規(guī)劃方法求解：max Z 4x 3x 2x2123x1 2x2 3x3 10s.t.x 0，

41、j 1，2，3 j解：設(shè)階段變量 k=1，2，3 表示 3 個階段；xk 表示第 k 階段的決策；Sk 表示第 k 階段至第3 階段的剩余量； fk (Sk ) 表示第 k 階段至第 3 階段的最大值。狀態(tài)轉(zhuǎn)移方程： fk (Sk ) maxvk (xk ) fk 1 (Sk 1 )f (S ) 0運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）44S S a xk 1kk k咨詢2（1）當 k=2 時， f2 (S2 ) max 3x2 (S2 2x2 ) 。290 x2 S2 / 2令 (x ) 3x 2 (S 2x ) x S88222 3 x2 S22 9 2222222999(x ) 16 x

42、 3 8 S ， (x ) 16 0 。222222999 S22故 f (S ) 在 x 0 或 x處取最大值。2222 2 S 227S 2 92234f2 (S2 ) maxS2 ,S2 max20 x2 S2 / 2 920 x2 S2 / 2 3 S 27 0S 222447 2 S 2 92 （2）當 k=1 時， f1 (S1 ) max 4x1 2 運籌學(xué)考研全套教程，詳見： 3 S0 x2 S1/ 4 網(wǎng)學(xué)天地（咨詢） 2因為 S1 10 ，則： 13 2 (10 4x )20 x 916 11f1 (S1 ) max 4x1 3 (10 4x )13 x 5 0 x1 5/

43、 2 22 111632 x2 144 x 200，0 x 13 200，x 0 916 1111999max0 x15/max 16 ，2 111168 10 2102009所以， x1 0，S1 10，S2 10，x2 0，x3 ， max z 2 。3七、（20 分）有網(wǎng)絡(luò)圖如圖附錄 9-1 所示（弧旁數(shù)字為容量 C）。3圖附錄 9-1求網(wǎng)絡(luò)中由發(fā)點集（vs1 和 vs2）到收點集（vt1 和 vt2）的最大流與最小截集。若?。╲1，v3）的容量改變量為C13，試討論對最大流量的影響。解：（1）增加始點 vs 和重點 vt，最終結(jié)果如圖附錄 9-2 所示。運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天

44、地（）咨詢圖附錄 9-248最大流為 8+3+3+4=18，最小截集為(v1 , v1 ) (v1, v3 ), (v1, v4 ), (v2 , v3 ), (v2 , v4 ) 。（2）當C3 0 時，最大流增大；當C3 0 時，最大流減小。八、（20 分）某公司計劃新建幾個工廠生產(chǎn)某種產(chǎn)品，可供選擇的地點有 B1、B2， Bm，已知第 i 個地點的建設(shè)費用為 hi，最大生產(chǎn)能力為 bi（i1，2，m）。又有 n 個地點 A1、A2，An 需要這種產(chǎn)品，其需求量分別為 a1、a2，an，又知由 Bi 到 Aj 的單位運費為 Cij。試建立數(shù)學(xué)規(guī)劃模型來決定在哪些地方建廠，使得滿足需求，又使

45、總費用最少，且滿足下列要求：若地點 B1 處建廠，地點 B3 處必須建廠。地點 B4 處必須建廠，其產(chǎn)量只能是 t1 或 t2 單位。地點 B2 若建廠，其最低產(chǎn)量為。運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢1，在Bi處建廠解：設(shè) xi ，yij 表示由 Bi 向Aj 處的運輸量，建立模型如下：0，否則mm mmin z xi hi yijciji 1i 1 j 1mi 1x y aj 12 ，n從所有Bi到A j的量i ijjnY x bi 12 ，mBi向所有A j的運量總和不超過產(chǎn)量iji ij 11，在B 處建廠運籌學(xué)考研全套教程，詳見： x i網(wǎng)學(xué)天地（咨詢）i0，否則1，B 產(chǎn)量

46、為ts.t. z 410，B 產(chǎn)量為t42x x要求（1）31x4 1要求（2）n x zt (1 z)t2 4j1j 1nLx y要求（3）2ijj 1九、（15 分）某商店每周需訂購某種商品，售價和進價分別為 p 和 c，單位存儲費和單位缺貨費分別為 h 和 b。商品每周需求量 x 是隨機的，概率密度函數(shù)為 f(x)，分布函數(shù)為 F(x)。試確定每周訂貨量 Q，使期望利潤最大？Cn，F(xiàn) (Q) c b p c b ，因此有：Q解：利用f (x)dx c b c hp b hCo Cn0Q F 1 p c b p b h 49運籌學(xué)考研全套教程，詳見： 網(wǎng)學(xué)天地（）咨詢10北京理工大學(xué) 20

47、07 年運籌學(xué)考研試題與答案一、（20 分）考慮下列線性規(guī)劃問題：min z x1 x2 4x3x1 x2 2x3 9x x x 2s.t.123x x x 4123x ，x ，x 0 123用單純形法計算此問題，并寫出最優(yōu)解、最優(yōu)值與最優(yōu)基。寫出此線性規(guī)劃問題的對偶問題，并求出對偶問題的解。解：（1）為獲得初始基可行解，將約束條件改寫為等價形式：運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢直接按目標函數(shù)極小型求解，如表附錄 10-1 所示。表附錄 10-1第一次迭代，如表附錄 10-2 所示。表附錄 10-2得到最優(yōu)解為，最優(yōu)值為17，最優(yōu)基為。104x1 x4 x31001/3 22/300

48、10102/3 01/31/3613/3j040021711400biiCBXBx1x2x3x4x5100 x1 x4 x510012220(3)01000196134.513/3j00500950（3）對偶問題為：運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢對偶問題的解為：。二、（25 分）某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，各種產(chǎn)品每件所需原料 A 分別為 2、4、 2kg；每件所需原料 B 為 4、6、5kg；消耗工時為 6、3、8 小時；各產(chǎn)品的利潤分別為每件 160、180、120 元。每周企業(yè)可用于這些產(chǎn)品的工時為 900 小時，可提供的原料 A、B 分別為 480kg和 800kg。以總

49、利潤最大為目標考慮各產(chǎn)品的生產(chǎn)生產(chǎn)計劃。通過計算，得到下列最優(yōu)單純形表如表附錄 10-3 所示。表附錄 10-3請解答下列問題：寫出此問題的線性規(guī)劃模型及其最優(yōu)解、最優(yōu)基和最優(yōu)基的逆；把最優(yōu)單純型表中“*”的格中數(shù)字補充完整；若產(chǎn)品乙的利潤從 180 變?yōu)?250 而其它參數(shù)均不變時，問題的最優(yōu)解和最優(yōu)值是什么？解：設(shè)每周分別生產(chǎn)甲、乙、丙三種產(chǎn)品（1）此問題的線性規(guī)劃模型為：件，z 表示一周企業(yè)的總利潤。，最大利潤為 29000 元。此問題的最優(yōu)解為最優(yōu)基為，最優(yōu)基的逆為（2）用左乘約束條件系數(shù)矩陣各列向量即得最優(yōu)表對應(yīng)的列向量，并計算待定的檢驗數(shù)，如表附錄 10-4 所示。0CBXBRHS

50、x1x2x3x4x5x6180 x250*01/41/6160 x1125*01/81/40 x430*13/41/6z29000*0251051運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢表附錄 10-4（3）當產(chǎn)品乙的利潤從 180 變?yōu)?250 而其他參數(shù)均不變時，原最優(yōu)表變?yōu)楸砀戒?10-5。表附錄 10-5最優(yōu)解改變，繼續(xù)迭代，如表附錄 10-6 所示。表附錄 10-最優(yōu)解為，最大利潤為 32800 元。三、（15 分）甲、乙兩個企業(yè)生產(chǎn)同一種產(chǎn)品，價格、質(zhì)量都相同。現(xiàn)需供應(yīng) A、B、C、 D 四個地區(qū)。單位運輸費用、各企業(yè)的產(chǎn)量、各地區(qū)的需求如表附錄 10-7 所示。表附錄 10-7

51、由于某種原因，企業(yè)乙必須滿額生產(chǎn)。試用表上作業(yè)法求解以上使總運輸費用最低的運輸問題。解：對于產(chǎn)銷不平衡運輸問題，增加虛擬銷地，如表附錄 10-8 所示。運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢0CBXBRHSx1x2x3x4x5x6250 x280010.510.50160 x1801021.5100 x6180002.564.51z328000075103500CBXBRHSx1x2x3x4x5x6250 x250011/1201/41/6160 x11251011/801/81/40 x430005/1213/41/6z2900000475/6042.55/30CBXBRHSx1x2x3

52、x4x5x6180 x250011/1201/41/6160 x11251011/801/81/40 x430005/1213/41/6z2900000850251052運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）表附錄 10-8咨詢用最小元素法確定初始調(diào)動方案，如附錄 10-8 所示。用位勢法進行檢驗，如表附錄 10-9 所示。表附錄 10-9空格處檢驗數(shù)： ij cij ui v j 。各空格檢驗數(shù)如表中方括號內(nèi)示。（3）調(diào)整：ij 0 處進行調(diào)整。x12 20 20 x22 15 20 x14 0 20 x24 30 20運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢調(diào)整后運輸方案如表附錄 10-

53、10 所示。表附錄 10-10可知所有 ij 0 ，最優(yōu)方案為：甲A：20甲D：10乙B：35乙C：25總運費：Z=320+520+635+525+910=585.乙D：10四、（25 分）某企業(yè)根據(jù)市場需求預(yù)測今后 3 個月月底的交貨任務(wù)分別是 2 千件、3 千件、3 千件。該廠的生產(chǎn)能力為每月 6 千件，該廠倉庫的存貨能力為 3 千件，每生產(chǎn) 1 千件產(chǎn)品的費用為 1 千元。在進行生產(chǎn)的月份，工廠要固定支出 3 千元開工費。倉庫保管費用為每 1 千件0.5 千元。假定開始時和計劃期末庫存量都是零。試問應(yīng)在各個月生產(chǎn)多少件產(chǎn)品，才能既滿足交貨任務(wù)又使總費用最少？53運籌學(xué)考研全套教程，詳見：

54、 網(wǎng)學(xué)天地（）咨詢解：設(shè) sk 為 k 月初倉庫的庫存量； xk 為 k 月生產(chǎn)產(chǎn)品的數(shù)量；uk 為 k 月需求量； fk (sk )為 k 月底到 3 月底所支付的最小費用。狀態(tài)轉(zhuǎn)移方程為： sk 1 xkuk(k 1,2,3)sks x x x 8 0s 0 41231) min fk (sk ) xk 0.5sk 1 3，xk 0f(s fk fk 1(s ) 0.5s，x 0 kkk 1k當 k=3 時，如表附錄 10-11 所示。表附錄 10-11當 k=2 時，如表附錄 10-12 所示。表附錄 10-12當 k=1 時，如表附錄 10-13 所示。表附錄 10-13可知最優(yōu)生產(chǎn)方

55、案為： x1 5 ， x2 0 ， x3 3 ；最少費用為 15.5 千元。s1x1r1 (s1, x1 )s2f2 (s2 )f1 (s1)x13 x10.5s1合計0250501215.55*3606110470729.5580837.5s2x2r2 (s2 , x2 )s2 s2 x2 3f3 (s3 )f2 (s2 )x23 x20.5s2合計0360606123470715.5580825690931.51250.55.506105360.56.515.5470.57.525580.58.531.529.545.5361725471831.53001.51.5067.50*141.5

56、5.515.5251.56.525361.57.531.5s3x3r3(s3, x3)f2(s3)x33+ x30.5 s3合計0360663*1250.55.55.5221415513001.51.51.5054運籌學(xué)考研全套教程，詳見： 網(wǎng)學(xué)天地（）咨詢五、（20 分）考慮一種由 4 種不同部件 A1、A2、A3、A4 組成的系統(tǒng)，各部件都運行時系統(tǒng)才能運行。系統(tǒng)的可靠性可以通過一個或幾個部件占并聯(lián)若干個單元而得到提高。并聯(lián) n個單元后部件的可靠性（概率）R 和費用 C（單位為千元）如表附錄 10-14 所示，現(xiàn)有資金 15千元。在 4 個部件中各并聯(lián)多少單元才使系統(tǒng)運行的可靠性最高？表附

57、錄 10-14解：由于各系統(tǒng)至少有 1 個單元并聯(lián)，此時所用資金為：C11 C21 C31 C41 4 2 3 3 12總資金 15，此時有 3 千元剩余。該 3 千元有 3 種分配方案，如表表附錄 10-15、表附錄10-16、表附錄 10-17 所示表附錄 10-15R1 0.85 0.6 0.9 0.8 0.3672表附錄 10-16R2 0.75 0.8 0.9 0.8 0.432表附錄 10-17R3 0.75 0.6 0.9 0.82 0.3321綜上分析可知， max R R2 0.432 ，所以分配方案如表（b）所示。六、（25 分）高速公路某出口只有一個收費通道，假設(shè)到達該出

58、口的汽車流為泊松流，平均每小時為 30 輛，收費員的服務(wù)時間服從負指數(shù)分布，平均每小時可服務(wù) 40 輛汽車。計算這個排隊系統(tǒng)的數(shù)量指標 P0、Lq、Ls、Wq、Ws?？紤]到車主的抱怨，該出口考慮在該出口多安排一外員工，這樣，每小時可服務(wù) 50輛汽車，計算這個排隊系統(tǒng)的數(shù)量指標 P0、Lq、Ls、Wq、Ws。另外，該出口也可考慮多安排一個收費通道，每個收費通道的服務(wù)率仍為 40 輛汽車。運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢（4）請對（2）、（3）這兩個方案進行評價。3解：由題意可知， 30 ， 40 ， P 41P（1） P0 1 P 4 ， Ls 1 P 3 ， Lq Ls P 2.25

59、A1A2A3A4N2112C5235A1A2A3A4N2211C5433A1A2A3A4N3111C7233NA1A2A3A4RCRCRCRC10.740.620.930.820.7550.840.82330.857555 11W L / 0.1小時 6分鐘，W W 0.1 0.075小時 4.5分鐘 40ssqs32（2） 1 50 ， P1 5 ， P0 1 P1 5運籌學(xué)考研全套教程，詳見：網(wǎng)學(xué)天地（）咨詢P1 3 ， L L P 11L sqs11 P2101 Ls 3 2 3分鐘，W W1 3 1.2 1.8分鐘Ws2qs1（3） M / M / 21Pn2P2P2P 15127P

60、， L 0 n!2!(1 P) 110q2!2(1 P)2220n 0 Lq分鐘，W W 96 分鐘271Wq110sq55 192 30 48 分鐘Ls1106055（4）從（2）（3）計算中可知，（3）比（2）更有效。七、（20 分）某航空公司售票處開展電話訂票業(yè)務(wù)。據(jù)統(tǒng)計分析，電話到達過程服從泊松分布，平均到達率為每小時 20 個，平均每個業(yè)務(wù)員每小時可以處理 10 個電話訂票業(yè)務(wù)。請問該公司應(yīng)該安裝多少臺電話，才能使因電話占線而損失的概率小于 10%。解： M / M / C ，設(shè) C 為電話臺數(shù)1C 1 1 kC11 0電話空閑概率： P iC！1 P k ! k 0s 運籌學(xué)考研全