第一篇：管理運籌學課后答案——謝家平

管理運籌學

——管理科學方法 謝家平

第一章

第一章

1.建立線性規劃問題要具備三要素：決策變量、約束條件、目標函數。決策變量（Decision Variable）是決策問題待

定的量值，取值一般為非負；約束條件（Constraint Conditions）是指決策變量取值時受到的各種資源條件的限制，保障決策方案的可行性；目標函數（Objective Function）是決策者希望實現的目標，為決策變量的線性函數表達式，有的目標要實現極大值，有的則要求極小值。

2.（1）設立決策變量；

（2）確定極值化的單一線性目標函數；

（3）線性的約束條件：考慮到能力制約，保證能力需求量不能突破有效供給量；

（4）非負約束。

3.（1）唯一最優解：只有一個最優點

（2）多重最優解：無窮多個最優解

（3）無界解：可行域無界，目標值無限增大

（4）沒有可行解：線性規劃問題的可行域是空集

無界解和沒有可行解時，可能是建模時有錯。

4.線性規劃的標準形式為：目標函數極大化，約束條件為等式，右端常數項bi≥0 , 決策變量滿足非負性。

如果加入的這個非負變量取值為非零的話，則說明該約束限定沒有約束力，對企業來說不是緊缺資源，所以稱為松弛變 量；剩余變量取值為非零的話，則說明“≥”型約束的左邊取值大于右邊規劃值，出現剩余量。

5.可行解：滿足約束條件AX =b,X≥0 的解，稱為可行解。

基可行解：滿足非負性約束的基解，稱為基可行解。

可行基：對應于基可行解的基，稱為可行基。

最優解：使目標函數最優的可行解，稱為最優解。

最優基：最優解對應的基矩陣，稱為最優基。

6.計算步驟：

第一步，確定初始基可行解。

第二步，最優性檢驗與解的判別。

第三步，進行基變換。

第四步，進行函數迭代。

判斷方式：

唯一最優解：所有非基變量的檢驗數為負數，即σj< 0

無窮多最優解：若所有非基變量的檢驗數 σj≤ 0，且存在某個非基變量 xNk 的檢驗數 σk= 0，讓其進基，目標函數

的值仍然保持原值。如果同時存在最小θ值，說明有離基變量，則該問題在兩個頂點上同時達到最優，為無窮多最優解。

無界解：若某個非基變量 xNk 的檢驗數 σk> 0，但其對應的系數列向量 Pk' 中，每一個元素 aik'(i=1,2,3,…,m)均非正數，即有進基變量但找不到離基變量。

無可行解：當引入人工變量，最末單純型發表中的基變量含有非零的人工變量，即人工變量不能全出基，則無可行解。

7.單純形法需要有一個單位矩陣作為初始基。當約束條件都是“≤”時，加入松弛變量就形成了初始基，但實際問題中往 往出現“≥”或“＝”型的約束，這就沒有現成的單位矩陣。需要采用人造基的辦法，無單位列向量的等式中加入人工變量，從而得到一個初始基。人工變量只有取 0 時，原來的約束條件才是它本來的意義。為保證人工變量取值為 0，令其價值 系數為-M（M 為無限大的正數，這是一個懲罰項）。如果人工變量不為零，則目標函數就不能實現最優，因此必須將其

逐步從基變量中替換出。對最小化問題，在目標函數中人工變量的系數取 M。

8.9.10.（1）C1<0，C2<0，且 d≥0

（2）C1=0，C2<0 或 C2=0，C1<0，a1>0（3）C1> 0，d>0，a2>0，d/4>3/a

2（4）C2>0，a1≤ 0

（5）x1為人工變量，且 C1為包含 M 的大于 0 數，d/4>3/a2；或者 x 數，a1>0，d>0。11.為人工變量，且 C 2 為包含 M 的大于 0

12.設 xij為電站向某城市分配的電量，建立模型如下：

13.設 x1 為產品 A 的產量，x2 為產品 B 的產量，x3 為副產品 C 的銷售量，x4 為副產品 C 的銷毀量，問題模型如下：

第二章

1.（2）甲生產 20 件，乙生產 60 件，材料和設備 C 充分利用，設備 D 剩余 600 單位

（3）甲上升到 13800 需要調整，乙下降 60 不用調整。

（4）非緊缺資源設備 D 最多可以減少到 300，而緊缺資源—材料最多可以增加到 300，緊缺資源—設備 C 最多可 以增加到 360。

2.設第一次投資項目i為xi，第二次投資項目i 設為xi'，第三次投資項目 i設為xi′。

3.設每種家具的產量為

4.設每種產品生產xi

5．（1）設 xi為三種產品生產量

通過 Lindo 計算得 x1= 33, x2= 67, x3= 0, Z = 733

（2）產品丙每件的利潤增加到大于6.67時才值得安排生產；如產品丙每件的利潤增加到 50/6，通過Lindo計算最優

生產計劃為：x1=29，x2= 46，x3= 25，Z = 774.9。

（3）產品甲的利潤在[6,15]范圍內變化時，原最優計劃保持不變。

（4）確定保持原最優基不變的q 的變化范圍為[-4,5]。

（5）通過 Lindo 計算，得到 x1= 32, x2= 58, x3= 10, Z = 707

第三章

1.原問題和對偶問題從不同的角度來分析同一個問題，前者從產品產量的角度來考察利潤，后者則從形成產品本身所需要的各種資源的角度來考察利潤，即利潤是產品生產帶來的，同 時又是資源消耗帶來的。

對偶變量的值 yi

表示第 i種資源的邊際價值，稱為影子價值。可以把對偶問題的解 Y定義 為每增加一個單位的資源引起的目標函數值的增量。?

2.若以產值為目標，則 yi是增加單位資源 i 對產值的貢獻，稱為資源的影子價格（Shad ow Price）。即有“影子價格=資源成本+影子利潤”。因為它并不是資源的實際價格，而是

企業內部資源的配比價格，是由企業內部資源的配置狀況來決定的，并不是由市場來決定，所以叫影子價格。可以將資源的市場價格與影子價格進行比較，當市場價格小于影子價格時，企業可以購進相應資源，儲備或者投入生產；當市場價格大于影子價格時，企業可以考慮暫 不購進資源，減少不必要的損失。

3.（1）最優性定理：設，分別為原問題和對偶問題的可行解，且 C

= b

，則

T，a 分別為各自的最優解。

（2）對偶性定理：若原問題有最優解，那么對偶問題也有最優解，而且兩者的目標函數值 相等。

*

*

（3）互補松弛性：原問題和對偶問題的可行解 X、Y 為最優解的充分必要條件是 ,。

（4）對偶問題的最優解對應于原問題最優單純形法表中，初始基變量的檢驗數的負值。若 ?YS對應原問題決策變量 x 的檢驗數； ? Y 則對應原問題松弛變量xS 的檢驗數。4.表示三種資源的影子利潤分別為 0.89、4.89 和 0，應優先增加設備 C 臺時以及增加材 料可獲利更多；14.89>12，所以設備 C 可以進行外協加工，200.89<210，所以暫不外

購材料。

5.(1)求出該問題的最優解和最優值；

x1= x2= x4= 0, x3= 2, x5= 6, Z = 4

(2)該問題的對偶問題的最優解和最優值：y1= 2，y2== 0，w = 4

(3)分別為 2、0，對產值貢獻的大小；第一種資源限量由 2 變為 4，最優解不會改變。

(4)代加工產品丁的價格不低于 2×2+0×3=4。4

6.(1)設四種產品產量為xi,i= 1,2,3,4

(2)

影子價格分別為 2、1.25、2.5。對比市場價格和影子價格，當市場價低于影子價格時購 進。

(3)原料丙可利用量在[900,1100] 范圍內變化，原最優生產方案中生產產品的品種不變（即最優基不變）。

(4)若產品 B 的價格下降了 0.5 元，生產計劃不需要調整。

第四章

1.純整數規劃、0-1 規劃、混合整數規劃。

2.(1)首先不考慮整數條件，求解整數規劃相應的線性規劃問題。若相應的線性規劃問 題

沒有可行解，停止計算，這時原整數規劃也沒有可行解。

(2)定界過程。對于極大化的整數規劃問題，當前所有未分枝子問題中最大的目標函數 值

為整數規劃問題上界；在滿足整數約束的子問題的解中，最大的目標函數值為整數規劃問

題的下界。當上下界相同時，則已得最優解；否則，轉入剪枝過程。

(3)剪枝過程。在下述情況下剪除這些分枝：①若某一子問題相應的線性規劃問題無可行解； ②在分枝過程中，求解某一線性規劃所得到的目標函數值 Z 不優于現有下界。

(4)分枝過程。當有多個待求分枝時，應先選取目標函數值最優的分枝繼續進行分枝。選

取一個不符合整數條件的變量 xi作為分枝變量，若 xi 的值是 bi*，構造兩個新的約束條

*

件：xi≤[bi ] 或 xi≥[bi ]+1,分別并入相應的數學模型中，構成兩個子問題。對任一個子 *

問題，轉步驟(1)。

最整數解為： x1=4, x2=2, z = 340

4.解：設 ,tij 為個人對于個任務的時間耗費矩陣，則目標函

數為：

約束條件為：

解之得： x = 1，x = 1，x = 1，x = 1，其余均為0，z=70，即任務A由

213

4乙完成，任務B由甲完成，任務C由丙完成，任務D由丁完成。

5.解：設在第 i天應聘的雇員人數為xi。數學模型為：

解得：x1=0，x2=4，x3=32，x4=10，x5=34，x6=10，x7=4，Z=94。

第五章

1.解：建立目標約束。

（1）裝配線正常生產

? 設生產A, B,C型號的電腦為 x1, x2 , x3（臺），d 1 為裝配線正常生產時間未利用數，d1 為裝配線加班時間，希望裝配線正常生產，避免開工不足，因此裝配線目標約束為

（2）銷售目標

優先滿足老客戶的需求，并根據三種電腦的純利潤分配不同的權因子，A, B,C三種型號的 +

電腦每小時的利潤是，，因此，老客戶的銷售目標約束為

再考慮一般銷售。類似上面的討論，得到

（3）加班限制

首先是限制裝配線加班時間，不允許超過200h，因此得到

其次裝配線的加班時間盡可能少，即

寫出目標規劃的數學模型

經過Lingo計算得到x1 = 100，x2= 55，x3=80。裝配線生產時間為1900h，滿足裝 配線加班不超過200h的要求。能夠滿足老客戶的需求，但未能達到銷售目標。銷售總利

潤為100×1000+55×1440+80×2520=380800（元）。

2.解：假設三個工廠對應的生產量分別為300，200，400。

（1）求解原運輸問題

由于總生產量小于總需求量，虛設工廠4，生產量為 100個單位，到各個用戶間的運費單

價為0。用 LINGO軟件求解，得到總運費是2950元，運輸方案如下表所示。

（2）下面按照目標的重要性的等級列出目標規劃的約束和目標函數。

設xij工廠i(i =1,2,3)調配給用戶j(j = 1,2,3,4)的運量，cij 表示從工廠i 到用戶j的 單位產品的運輸費用，aj(j = 1,2,3,4)表示第j個用戶的需求量，bi(i =1,2,3)表示第i 個工廠的生產量。

i）供應約束應嚴格滿足，即

ii）供應用戶1 的產品中，工廠3的產品不少于100個單位，即

;

iii）需求約束。各用戶的滿足率不低于80％，即

應盡量滿足各用戶的需求，即

iv）新方案的總運費不超過原方案的10％（原運輸方案的運費為2950 元），即

v）工廠2到用戶4 的路線應盡量避免運輸任務，即

vi）用戶1和用戶3 的滿足率應盡量保持平衡，即

vii）力求總運費最少，即

目標函數為

經8次運算，得到最終的計算結果，見下表。總運費為3360 元，高于原運費 410元，超 過原方案10％的上限115 元。

3.設分別生產 A 機器 x1 臺，B 機器 x2 臺。目標函數為：

Lingo 計算結果為：生產 A 機器 15 臺，B 機器 21 臺，利潤增加 4129 元，工序Ⅱ 加班 22.5 小時。

第六章

1.原有問題的求解就化為逐個求解幾個簡單的階段子問題，當每一個階段的決策子問題確定后，就組成了一個決策序列，每個階段的決策一旦確定，整個決策過程也隨之確定，此類把一個問題看作是一個前后關聯具有明顯階段性的決策過程

就稱為多階段決策問題。

2.動態規劃最優性原理導出了它的解題思路，即將決策問題劃分為若干個階段，將全過程的優化問題分解為子過程的優 化問題；逆著階段順序的方向，由后向前逐步倒推；各階段求解都是在后部子過程最優策略基礎上，再考慮本階段的指

標函數，求出本階段的最優策略；由后向前推算直到第一階段為止，最優化的子過程逐漸成為最優化的全過程。

3.（1）模型建立

將三個營業區看作是三個階段，即階段變量 k =1,2,3；

第 k 階段初尚未被分配出去的銷售點是其決策的起點，則狀態變量 Sk表示第 k 階段初可分配的銷售區數，Sk≥ 0，且初始狀態已知 S1= 6 ；

決策變量xk表示第 k階段分配給區A，B，C的銷售店，允許決策集合

狀態轉移方程為Sk+1=Sk-k

階段指標Vk(Sk,xk)表示第k階段從Sk銷售點中分配給第k區 xk個的階段效益；

最優指數函數 fk(Sk)表示第 k 階段從 Sk開始到最后階段采用最優分配策略取得的最大收益，遞推方程函數式

（2）逆序求解

當 k =3 時

當k=2時

當 k =1 時

順序遞推，得出結論：第 A 小組建 3 個,第 B 區建 2 個，第 C 區建 1 個，4.（1）模型建立

多階段性的月度生產決策，可以按月劃分階段，即階段變量 k = 1, 2,3, 4 分別表示這四個 月。

上期未需求的產品將會進入倉庫存放，供下期需求消費；下期生產與否，視期初庫存數 量和當期需求量而定，第 k 月 的期初庫存反映出其狀態特征。因此，狀態變量 Sk表示第 k 月 期初的產品庫存量，0≤ Sk≤4。

決策變量 xk表示第 k 月的實際生產量，允許決策集合 Xk(Sk){0 ≤ xk≤ 4}。

第 k 月的訂貨量記為 dk，而供給量為 Sk+ xk，則狀態轉移方程為 Sk+1=Sk+ xk-dk。

階段指標vk(Sk ,xk)k表示第 k 月的費用。本月若不安排生產，則僅需支出存貨費；若安排 生產，則需支出生產成本 和固定運營費，同時還需存貨費。為了將存儲問題簡化，忽略本月 生產和需求產品的短期存貨費。因此當 xk=0 時，v k(Sk ,xk)= H Sk= 1500Sk；當 xk＞0 時，最優指數函數 fkSk()表示第 k 階段從期初庫存 Sk 開始到最后階段采用最優生產策略實現的最低生產費用。

（2）逆序求解

k =4 時，因為 4 月末交貨后的計劃存貨 0 件，則 S5=0；第 4 月的訂單需求 d4=1 萬件，則由狀態轉移方程 S 5 = S4+ x4-d4知，S4+ x4= 1。

k=3 時，第3 月的訂單需求d3=5萬件，則滿足需求有 S3+ x3≥ 5 ；而倉庫的最大存貨能力為 4 萬件，則由狀態轉 移方程 S4= S3+-x3d3有 S3+ x3≤ 6。

k=2 時，第 2 月的訂單需求d2=3 萬件，則滿足需求有 S2+ x2≥ 3 ；而倉庫的最大存貨能力為 4 萬件，則由狀態 轉移方程 S3= S2+ x2-d2有 S2+ x2≤ 7。

k=1 時，企業現有存貨0 件，即S1= 0，第1月的訂單需求d1=2 萬件，而倉庫的最大存貨能力為4 萬件，則有 x ≤ 6。

1順序遞推，得出結論：第1 月生產5萬件；由狀態轉移方程 S2= S1+x1-d 1 知，S2= 3，則第2月生產0 件；再由狀 態轉移方程S3= S2+ x2d2?知，S3= 0，則第 3 月生產 6 萬件；再由狀態轉移方程 S4= S3+x3-d3 知，S4= 1，則第4月生產0 件。

5.每年為一個階段，即階段變量 k = 1, 2,3, 4,5 ；

狀態變量 Sk 表示第 k 年初所擁有的完好機器臺數，已知 S1=200；決策變量 xk 表示第 k 年投入超負荷生產的設備 數，則剩余設備 Sk? xk 投入低負荷的生產作業，允許決策集合 0≤ xk≤ Sk；

狀態轉移方程為S =(1-α)x +(1-β)(S-x)=0.85S-0.3x ；

k+1 k

k

k

k

k

階段指標vk(sk,xk)表示第k年的收益，即 vk(sk,xk)=12xk+ 8(Sk-xk)=8Sk+4xk；

最優指數函數 fk(Sk)表示第 k 年從 Sk開始到 5 年末采用最優分配策略實現的最收益； 基本遞推方程

邊界條件：f6(s6)=0 k=5，最大，f5(s5)=12sk=4，由于 f4(s4)是關于 x4 的單增函數，故 x 4=S4 時，f4(s4)最大，f4(s4)=17.5S4，k=3，由于 f(s)是關于 x

5的單增函數，故 x * =s 時，f(s)

*

由于 f3(s3)是關于 x3 的單減函數，故x3 =0時，f3(s3)最大，f3(s3)=22.875s3。

* k=2，由于 f2(s2)是關于 x2 的單減函數，故 x 2=0 時，f2(s2)最大，f s2()2=27.44375 s1。

最優作業安排策略是前三年將低負荷，后兩年全部重負荷。s1=200，而 x1 =0，則S2=0.85S1-0.3x1=170臺；同 理，由x2 =0，則 S3=0.85S2-0.3x2=144臺；由x

*

*

*

*

S5=0.85S4-0.3x4=67臺；由 x5 =0，則S4=0.85S3-0.3x3=122 臺；由 x4

*

*

=S4=122 臺，則

=S5=36 臺。

第七章

1.求得的最小樹如下圖：

2.（1）給網絡始點v s 標號(vs,0)，并在標號下面畫橫線表示為永久標號；并給從 vs出發的各弧的點vj賦予臨時標號(ws,v sj)，不能一步到達的點賦予臨時標號(vs, ∞)。

（2）在所有臨時標號中選擇路權最小者，即結點 v1，將v1 的臨時標號變為永久標號，在 標 號 下 畫 橫 線。然

后，考 察 從 1 出 發 的 各 弧 的 點 vj的 臨 時 標 號 ： 結 點 5 的 路 權 d5= min{∞,d1+w 15 } = min v v {∞,4+5}=9，則將v5 的臨時標號變為(v1,9)，并劃去其原有較大的臨時標號(vs, ∞)；同理，對于結點 v4，臨時標 號變為(v1,8)；對于結點 v2，臨時標號變為(v1,11)；其他結點標號不變。

（3）依此類推，重復上述標號過程。當所有標號都是永久標號，即每一個標號下都畫上橫線時，則標號過程結束。vt 的后一個標號為vs到vt的最短路權，即14；根據vt的另一個標號反向追蹤求得 vs到vt的最短路徑為{vs,v3,v2,v6, vt} 3.（1）網絡的中心

從表中可得出：各列之和的最小值為 22，對應的點 D 即是網絡的中心；也可以根據各行選擇最大值，再從中選擇最小

值為 5，同樣對應的點 D 是網絡的中心。因此，倉庫應建在位于網絡中心的銷售點 D。

（2）網絡的重心

各列加權之和的最小值為 9000，對應的點 D 是網絡的重心位置。因此，倉庫應建在位于網絡重心的銷售點 D。

（3）企業在自建倉庫時，一般采用中心法，因為企業自營的倉庫不能搬動；而企業選擇租賃倉庫時，一般采用重心法，因為租賃的倉庫由于合同期限等原因可以變動位置。另外，如果企業生產的產品多為創新型產品，這類產品的邊際貢獻 率高，產品更新速度快，顧客群變動較大，銷售區域也有可能發生變化，則選擇租賃倉庫時宜使用重心法。

4.先根據圖寫出結點之間的弧權矩陣，如下表所示。

取上表的v 行數據即為 1 = w

d ；第一次迭代是 d 列的元素與下表中第1-6列對應元素 相加取最小，得到 d 2

列；其余函數迭代過程以此類推。11j1j

1j

1j

由于 d 1j = d 1j，則迭代結束，此時 d 1j 列的各元素，即為 v1 到其余各點的最短路權。再根據 d 1j 列各元素的來源，3 4 3

可以追蹤最短路徑。例如，追蹤 v 到v 的最短路徑，對于d =6，d +w =4+2=6 計算而得，則 v 的前一個點 3 1 6 16 14 46 6 1 1

是v ；再根據 d =4進行追蹤，這是由d +w =1+3=4計算而得，則 v 的前一個點是 v ；再看 d =1,這是 14 24 24 4 2 12 由w =1 而得的，所以最短路徑為v →v →v →v。1 2 4 6 5.（1）將問題轉換成最短路問題，如 3

（2）給網絡始點v 1 標號(v1,0)，并在標號下面畫橫線表示為永久標號；并給從v1 出發的各弧的點 vj賦予臨時標號(v 1,v1j)。

在所有臨時標號中選擇路權最小者，即結點v2，將v2 的臨時標號變為永久標號，在標號下畫橫線。然后，考察從v 2 出 發的各弧的點v 的 臨 時 標 號 ： 結 點 v 的路權 d = min{22,d +w } = min{22,16 +17} = 22，則v

j

臨時標號不變；同理，對于結點v4、v5 臨時標號均不變。

依此類推，重復上述標號過程。當所有標號都是永久標號，即每一個標號下都畫上橫線時，則標號過程結束。v5 的后一 個標號為v1 到v5的最短路權，即41；根據v5的另一個標號反向追蹤求得v1到 v5的最短路徑為{v1,v5}。

費用最小的方案為：第一年購置設備，此后四年不再更新。

6.根據題意，可以畫出如下的網絡圖。

從表中可以看出，方案路線v →v →v →v

2

410

→v 與 v →v →v →v

212

1→v 最短，對應的費用均為130。

7.（1）首先設置初始流量，如下圖：

逐步增加流量，如下圖：

弧(v4,v7)、(v6,v7)、(v5,v7)均為飽和流，不能再增加流量，因此得到 v1

（2）由 于 弧(v 到 v7 的最大流。

4,v7)、(v6,v7)、(v5,v7)都 是 飽 和 弧，所 以 從 此 截 開，S ={v1,v2,v3,v4,v5,v6}，*

={v7 }，得

到最小截集(S* ,)= {(v4,v7)、(v6,v7)、(v5,v7)}，其截量為 2+3+2=7。

8.（1）所給流是否是可行流。即

①容量限制：對每條弧(vi, vj)∈ A，都有 0 ≤ xij≤ bij；

②平衡條件：中間各點的流出量等于其流入量。

（2）畫出賦權有向圖，如下：

存在負回路v1→v2→v3，總權數為 2-6-3=-7。則目前的網絡流需要調整。,進行流量調整，弧(v1, v2)存在負回路方向一致與負回路方向一致，則其流量調整為 x12+θ=2+1=3；而弧(v3,v2)與負回路方向相反，則其流量調整為 x32? θ =1-1=0；弧(v1,v3)與負回路方向相反，則其流量調整為 x13-θ =4-1=3。調整后的網絡為：

再畫出賦權有向圖：

上圖中找不到負回路，因此，調整后的可行流就是最小費用流。最小費用為各弧上流量和單位費用的乘積之和，從左向 右依次為 2×4+6×1+3×2+3×3+0×6+5×1+3×2=40。

第八章

1.（a）結點②到結點⑤之間出現兩條線，分別為工序 d、e，而兩個結點之間只能有一 條箭線相連，否則會造成邏輯錯誤，因此應該引入虛工序，如下圖所示。

（b）結點⑤到結點⑥之間的虛工序是不需要的；網絡圖中出現兩個終結點⑦、⑧，因此修

改后如下圖所示。

（c）網絡圖中 a、b、d 三道工序出現循環回路，違背了繪制網絡圖的規則。

2.（1）（2）

3.4.5.（1）

（2）

（3）首先考慮縮短非關鍵作業 E 或 D 的時間。

6.（1）首先根據表中數據畫出網絡圖，并標出各結點時間參數，圖中粗線表示關鍵路線。

（2）畫出初始進度

7.首先計算費率：

方案 I：各道作業正常完工

關鍵工序為：①→②→③→④→⑥→⑧。費用 C(I)=正常完工直接費用+間接費用=131

0+15×27=1715 元。方案 II：關鍵路線上趕進度在關鍵線路上趕工，費率最小的為工序 ①→②，最多可趕工 2 天。非關鍵工序總時差為： R(4 → 7)= 5，R(3 → 5)=。所以工序①→②趕工 2 天。

關鍵工序仍為：①→②→③→④→⑥→⑧。費用 C(II)=正常完工直接費用+趕進度增加 的直接費用+間接費用=1310+10×2+15× 25=1705 元。比較兩個方案，方案 II 比

方案 I 的周期縮短 2 天，同時工程費用降低 10 元。方案 III：關鍵路線上趕進度確定

趕進度作業：再繼續看關鍵路線①→②→③→④→⑥→⑧，費率最小的為工序②→③和⑥→ ⑧，分別最多可趕工 4 天和 1 天。所以工序⑥→⑧趕工 1 天。

關鍵工序仍為：①→②→③→④→⑥→⑧。費用 C(III)=正常完工直接費用+趕進度增加 的直接費用+間接費用=1310+10×2+20× 1+15×24=1710 元。方案 III 比方案 II 的工期縮短 1 天，但費用卻增加了 5 元。如果繼續壓縮，工程總費用將急劇增加，因此

認為方案 II 為最優方案，對應的最低成本日程為 25 天。

8.首先計算平均作業時間：

關鍵工序為：c→d→f→i→j 和 c→d→g→i→j。Ⅰ工程工期的期望為關鍵作業期望時間之

和，即 μE= μc+ μd+ μf+ μi+ μj= 59，工程工期的方差為關鍵作業時間的方差之和，即

反查標準正態分布表知α=58.71%。即現有技術方案，對

。已知合同工期 T = 60，則

于工期 60 天，完工的概率為 58.71%。

Ⅱ工程工期的期望為關鍵作業期望時間之和，即 μE= μc+ μd+ μg+ μi+ μj= 59，工

程工期的方差為關鍵作業時間的方差之和，即

合同工期 T = 60，則

。已知，反查標準正態分布表知α = 59.48%。即現有技術方案，對于工期 60 天，完工的概率為 59.48%。

第九章

1．2．計算出損益值矩陣：

3．由于展銷期間有雨的概率為 0.75，沒雨的概率為 0.25，則認為展銷期間的天氣狀況

將是“有雨”。按照最大可能準則，在有雨的狀態下進行決策。顯然，決策者會選擇S2 方案，此時損失最小，為 10 萬元。

4．最大可能性準則：由于銷售量為 180 本銷售比例為 40%，可能性最大，在銷量為 1

本的狀態下進行決策，決策者會選擇訂購 180 本。

收益期望值：計算各訂購量的期望收益值如下

最大收益期望值為 344 萬元，決策者會選擇訂購 180 本。

5．畫出決策樹：

結點 2 E(2)=0.5×80+0.4×40+0.1×10=57 萬元；

結點 3 E(3)= 0.5×60+0.4×40+0.1×20=48 萬元；

結點 1 是決策結點，需要進行抉擇，結點 2 的期望值為最大，故應選擇擴建電站。

6.可根據自己的實際情況畫出決策樹：

7．（1）建大廠的期望收益為：

E(S1)=[100×0.5+60×0.3+(-20)×0.2]×10-280=360 萬

建小廠的期望收益為

E(S2)=[25×0.5+45×0.3+55×0.2]×10?140=230 萬

因為 E(S1)>E(S2),所以應該選擇建大廠。

（2）將收益 720 萬元的效用值定為1，記U(720)=1，最低收益值-480 萬元的效用值

定為0，記 U(480)=0.U(-120)=0.5×U(720)+0.5×U(-480)=0.5×1+0.5×0=0.5 U(180)=0.5×U(720)+0.5×U(-120)=0.5×1+0.5×0.5=0.75 U(-340)=0.5×U(480)+0.5×U(-120)=0.5×0+0.5×0.5=0.25 根據已知的幾個收益值點的效用值，畫出效用曲線：

從該效用曲線可以看出，該經理是風險厭惡者。如果采用建大廠的方案，一旦出現市場需求 量低的狀況，會虧損 20 萬元，風險太大；而采用建小廠的方案，不會出現虧損。因此，經理決定建小廠。

第十章

1．1）建立層次模型

2）構造判斷矩陣

3）一致性檢驗

4）層次單排序

5）層次總排序

2.一個因素被分解為若干個與之相關的下層因素，通過各下層因素對該因素的重要程度兩兩 相比較，構成一個判斷矩陣。

通常我們很難馬上說出所有 A1，A2，…，An之間相對重要程度，但可以對 Ak與 Aj間兩 兩比較確定，取一些相對數值為標度來量化判斷語言，如表所示。

3.一致性是指判斷矩陣中各要素的重要性判斷是否一致，不能出現邏輯矛盾。當判斷矩陣中 的元素都符合一致性特性時，則說明該判斷矩陣具有完全一致性。

引入判斷矩陣的一致性指標 C.I.，來檢驗人們思維判斷的一致程度。C.I.值越大，表明判 斷矩陣偏離完全一致性的程度越大；C.I.值越小（越接近于 0），表明判斷矩陣的一致性越

好。

對于不同階的判斷矩陣，其 C.I.值的要求也不同。為度量不同階判斷矩陣是否具有滿意的 一致性，再引入平均隨機一致性系數指標 R.I。

C.I.與 R.I.之比稱為隨機一致性比值記作 C.R。當 C.R.<0.1 時，即認為判斷矩陣具有滿 意的一致性；否則，C.R.≥0.1 時，認為判斷矩陣不一致

4.層次單排序就是把本層所有要素針對上一層某要素來說，排出評比的優劣次序所謂層次總 排序就是針對最高層目標而言，本層次各要素重要程度的次序排列。

5.將各指標值無量綱化和無極性化，可以使各指標的評價尺度統—，然后才能對各方案的價 值進行分析和評價。

6.計算 O-U 判斷矩陣的相對權重向量：

即準則層的相對權重向量WU =(0.1634,0.2970,0.5396)。近似計算最大特征根 λ

T

ma

x

進行一致性檢驗

可見，隨機一致性指標 C.R.<0.1，判斷矩陣 O-U 具有滿意的一致性。同理，可以計算 其它各判斷矩陣的層次單排序如下：

(U1,U2，U3)的相對權重也就是其絕對權重(0.1634, 0.2970, 0.5396)。A1、A2、A3

相對于各個指標的權重就是各型號相對于各個指標的得分，將兩者對應相乘，可以得到各個

方案的分數，如下表所示：

可以看出，A1型號的得分最高，A3型號其次，A2型號最低。因此，應優先選擇 A1 型號。

7.指標值無極性化處理：利潤，成本和投資指標中，投資、成本是極小值極性，用各行的

最小值與該行的每個元素之比，去掉指標極性；利潤是極大值極性，用各行的每個元素與該 行的最大值之比，去掉指標極性。

再用指標的權重向量進行綜合權衡，即用指標的權重與對應列的對應元素相乘求和：

從上表可以得出按個方案的得分，各個方案的次序為 A3、A1、A2。

8．（1）先計算 O-U 判斷矩陣的權重向量，得到 WU =(0.4832,0.2717,0.1569,0.0882)T

進行一致性檢驗

可見，隨機一致性指標 C.R.<0.1，判斷矩陣 O-U 具有滿意的一致性。

（2）指標值無極性化處理

價格低廉性、交貨提前期是極小化指標。質量合格率、按時交貨率是極大化指標。

（3）指標值無量綱化處理

采用均值化法處理，用各行的每個元素與該行的平均值之比

a294

按照綜合評價值的大小，確定供貨商履約的順序為供應商 Co.4、Co.3、Co.1、Co.5、C

o.2。

第十一章

1.解：根據經濟訂貨批量公式和已知條件，經濟訂貨批量 Q

*

最優訂貨次數

年總費用為

2.解：根據經濟訂貨批量公式和已知條件，經濟訂貨批量 Q

*

單位時間總費用為

3.解：根據經濟訂貨批量公式和已知條件，經濟訂貨批量 Q

*

經濟訂貨批量 Q *

最大庫存量

最大缺貨量

單位時間總費用為

或者：

4.解：根據經濟生產批量公式和已知條件，經濟生產批量 Q

*

5.解：根據訂貨點公式和已知條件

由于沒有告訴需求的方差，則 σD = 0，不需要安全庫存，即有 訂

貨點

6.解：根據經濟訂貨批量公式和已知條件

希望存貯量達到最低限度應取 27 件

7.解：根據經濟批量公式和已知條件，顯然，總費用最低的生產批量為 25298 個，此時的總費用為 87589 元。

8.解：由已知條件可知 v =2，u =8，臨界值

由表中的數據可知 F(25)=0.1, F(26)=0.4，于是最優進貨量為 26 筐

9.解：由已知條件可知 K=5000 元，c=4000 元，H=60 元，因缺貨而緊急調貨，單

價 4300 元，可知缺貨費用 L=4300 元。

電子產品的銷售量服從在區間［75，100］內的均勻分布

s 的值應滿足：

經積分和整理后，方程為 87.2s ?13380s + 508258 = 0，解方程得： s = 69.14

和 s = 84.292，由于 84.292> S = 76.7，應舍去，所以取 s = 69.147。

因此，這個問題的足有策略應是：商店的電子產品需訂購 S ? x = 76.7 ? 0 ≈ 77 臺。

第十二章

1.（1）在t=30 時系統內有 20 個顧客的概率等于在t=30?15=15 時間內到達 n=20 ?10=10個顧客的概率。

在t=15至t=30這段時間內到達的平均數為λt=20×15=300個。

在t=30時系統中有 20個顧客的概率：

（2）系統中顧客的平均數為λt，因此，當t=10時，λt=20×10=200 個，當t=20時，λt=20×20=400個。

2.3.4.這是M/M/1與 M/M/2，隊長無限系統的混合情況，λ=30 人/小時，μ=40 人 /小時；

μ′=60 人/小時。

5.6.這里 為正在服務臺接受被服務顧客的平均數，則平均被服務顧客數為

。所以，在多服務臺情況下，7.（1）服務時間服從負指數分布：

服 務 時 間 服 從 定 長 分 布 ：，根 據 PK公式，當服務時間服從負指數分布情況下每個顧客在隊伍中的期望等待時間大于服務時間服從定 長分布情況。

（2）服務時間服從負指數分布：

服務時間服從定長分布：

第二篇：運籌學黃皮版課后習題答案詳解

ij?cij?(ui?vj)i?1,2,?m;j?1,2,?,ncij?(ui?vj)?0i?1,2,?m;j?1,2,?,n

4、對于產銷平衡的運輸問題，所有的約束都取等式。

3.2 運輸問題的基可行解應滿足什么條件？將其填入運輸表中時有什么體現？并說明在迭代計算過程中對它的要求。

解：運輸問題基可行解的要求是基變量的個數等于m+n-1。填入表格時體現在數字格的個數也應該等于m+n-1。在迭代過程中，要始終保持數字格的個數不變。

3.3 試對給出運輸問題初始基可行解的西北角法、最小元素法和Vogel法進行比較，分析給出的解之質量不同的原因。

解：用西北角法可以快速得到初始解，但是由于沒有考慮運輸價格，效果不好；最小元素法從最小的運輸價格入手，一開始效果很好，但是到了最后因選擇余地較少效果不好； Vogel法從產地和銷地運價的級差來考慮問題，總體效果很好，但是方法較復雜。

3.4 詳細說明用位勢法(對偶變量法)求檢驗數的原理。

解：原問題的檢驗數也可以利用對偶變量來計算 ：

其中，ui和vj就是原問題約束對應的對偶變量。由于原問題的基變量的個數等于m+n-1。所以相應的檢驗數就應該等于0。即有：

由于方程有m+n-1個，而變量有m+n個。所以上面的方程有無窮多個解。任意確定一個變量的值都可以通過方程求出一個解。然后再利用這個解就可以求出非基變量的檢驗數了。

3.5 用表上作業法求解運輸問題時，在什么情況下會出現退化解？當出現退化解時應如何處理？ 解：當數字格的數量小于m+n-1時，相應的解就是退化解。如果出現了退化解，首先找到同時劃去的行和列，然后在同時劃去的行和列中的某個空格中填入數字0。只要數字格的數量保持在m+n-1個的水平即可。

3.6 一般線性規劃問題具備什么特征才能將其轉化為運輸問題求解，請舉例說明。

解：如果線性規劃問題有“供”和“需”的關系，并且有相應的“費用”，就可以考慮將線性規劃問題轉成運輸問題求解。例如，生產滿足需求的問題。3.7 試判斷表3-30和表3-31中給出的調運方案可否作為表上作業法迭代時的基可行解?為什么?

答：都不是。數字格的數量不等于m+n-1。

3.8 表3-32和表3-33分別給出了各產地和各銷地的產量和銷量，以及各產地至各銷地的單位運價，試用表上作業法求最優解。

3.9 試求出表3-34給出的產銷不平衡運輸問題的最優解。

3.10 某市有三個面粉廠，它們供給三個面食加工廠所需的面粉。各面粉廠的產量、各面食加工廠加工面粉的能力、各面食加工廠和各面粉廠之間的單位運價，均表示于表3-35中。假定在第1，2和3面食加工廠制作單位面粉食品的利潤分別為12元、16元和11元，試確定使總效益最大的面粉分配計劃(假定面粉廠和面食加工廠都屬于同一個主管單位)。

3.11 表3-36示出一個運輸問題及它的一個解：

試問：

(1)表中給出的解是否為最優解？請用位勢法進行檢驗。答：是最優解。(2)如價值系數c24由1變為3，所給的解是否仍為最優解？若不是，請求出最優解。答：

原來的解不是最優解。新的最優解是： x12=3,x13=5,x21=8,x22=2,x33=1,x34=3，其他變量為0。

(3)若所有價值系數均增加1，最優解是否改變？為什么? 答：不會改變。因為檢驗數不變。

(4)若所有價值系數均乘以2，最優解是否改變？為什么? 答：最優解不變。因為檢驗數不變。

(5)寫出該運輸問題的對偶問題，并給出其對偶問題的最優解。

3.12 1，2，3三個城市每年需分別供應電力320，250和350單位，由I，Ⅱ兩個電站提供，它們的最大供電量分別為400個單位和450個單位，單位費用如表3—37所示。由于需要量大于可供量，決定城市1的供應量可減少0～30單位，城市2的供應量不變，城市3的供應量不能少于270單位，試求總費用最低的分配方案(將可供電量用完)。

解：對偶問題如下：maxZ??aiui??bjvji?1j?1mn??ui?vj?ciji?1,2,?m;j?1,2,?,n???ui,vj無約束,i?1,2,?m;j?1,2,?,n最優解是：u1??1,u2?0,u3?0,v1?1,v2?2,v3?5,v4?1

第三篇：川大《管理運籌學》第二次作業答案

川大《管理運籌學》第二次作業答案 歡迎你，你的得分： 100.0 完成日期：2014年08月19日 09點43分

說明： 每道小題括號里的答案是您最高分那次所選的答案，而選項旁的標識是標準答案。

一、單項選擇題。本大題共20個小題，每小題 2.0 分，共40.0分。在每小題給出的選項中，只有一項是符合題目要求的。1.規劃的目的是（）

(C)A.合理利用和調配人力、物力，以取得最大收益。

B.合理利用和調配人力、物力，使得消耗的資源最少。

C.合理利用和調配現有的人力、物力，消耗的資源最少，收益最大。

D.合理利用和調配人力、物力，消耗的資源最少，收益最大。

2.線性規劃問題標準型中bi（ｉ＝１，２，??ｎ）必須是（）。

(B)A.正數

B.非負數

C.無約束

D.非零

3.線性規劃問題的基本可行解Ｘ對應于可行域Ｄ的（）。

(D)A.外點

B.所有點

C.內點

D.極點

4.滿足線性規劃問題全部約束條件的解稱為（）。

(C)A.最優解

B.基本解

C.可行解

D.多重解

5.當滿足最優解，且檢驗數為零的變量的個數大于基變量的個數時，可求得（）。

(A)A.多重解

B.無解

C.正則解

D.退化解

6.原問題與對偶問題的最優（）相同。

(B)A.解

B.目標值

C.解結構

D.解的分量個數

7.原問題的第ｉ個約束方程是“＝”型，則對偶問題的變量yi 是（）。

(B)A.多余變量

B.自由變量

C.松弛變量

D.非負變量

8.運輸問題中，m+n-1個變量構成基本可行解的充要條件是他不含（）。

(C)A.松弛變量

B.多余變量

C.閉回路

D.圈

9.樹Ｔ的任意兩個頂點間恰好有一條（）。

(B)A.邊

B.初等鏈

C.歐拉圈

D.回路

10.若Ｇ中不存在流f增流鏈，則f為Ｇ的（）。

(B)A.最小流

B.最大流

C.最小費用流

D.無法確定

11.對偶單純型法與標準單純型法的主要區別是每次迭代的基變量都滿足最優檢驗但不完全滿足（）

(D)A.等式約束

B.“≤”型約束

C.“≥”型約束

D.非負約束

12.當線性規劃問題的一個基解滿足下列哪項要求時稱之為一個可行基解（）

(C)A.大于0 B.小于0 C..非負

D.非正

13.在運輸方案中出現退化現象，是指數字格的數目()

(C)A.等于m＋n B..大于m＋n－1 C..小于m＋n－1

D.等于m＋n－1 14.在線性規劃模型中，沒有非負約束的變量稱為（）

(C)A.多余變量 B.松弛變量 C.自由變量

D.人工變量

15.約束條件為AX=b，X≥0的線性規劃問題的可行解集是

(B)A.補集 B.凸集

C.交集 D.凹集）（16.線性規劃問題若有最優解，則一定可以在可行域的（）上達到。

(C)A.內點 B.外點 C.極點

D.幾何點

17.對偶問題的對偶是（）

(D)A.基本問題 B.解的問題 C.其它問題 D.原問題

18.若原問題是一標準型，則對偶問題的最優解值就等于原問題最優表中松弛變量的（）

(D)A.值 B.個數 C.機會費用 D.檢驗數

19.若運輸問題已求得最優解，此時所求出的檢驗數一定是全部（）(A)A.大于或等于零

B.大于零 C.小于零

D.小于或等于零

20.若f*為滿足下列條件的流：Valf*=max{Valf |f為G的一個流}，則稱f*為G的（）

(C)A.最小值 B.最大值 C.最大流

D.最小流

二、多項選擇題。本大題共10個小題，每小題 4.0 分，共40.0分。在每小題給出的選項中，有一項或多項是符合題目要求的。

1.求運輸問題表上作業法中求初始基本可行解的方法一般有（）

(ABD)A.西北角法

B.最小元素法

C.單純型法 D.伏格爾法

E.位勢法

2.建立線性規劃問題數學模型的主要過程有（）

(ABC)A.確定決策變量

B.確定目標函數

C.確定約束方程

D.解法 E.結果

3.化一般規劃模型為標準型時，可能引入的變量有

(ABC)A.松弛變量

B.剩余變量）（C.自由變量

D.非正變量 E.非負變量

4.表上作業法中確定換出變量的過程有（）

(ACD)A.判斷檢驗數是否都非負

B.選最大檢驗數 C.確定換出變量

D.選最小檢驗數

E.確定換入變量

5.一般情況下，目標函數系數為零的變量有

(CD)A.自由變量 B.人工變量 C.松弛變量

D.多余變量）（E.自變量

6.解線性規劃時，加入人工變量的主要作用是（）

(AD)A.求初始基本可行解

B.化等式約束 C.求可行域

D.構造基本矩陣

E.求凸集

7.求解約束條件為“≥”型的線性規劃、構造基本矩陣時，可用的變量有（）

(AC)A.人工變量

B.松弛變量 C..剩余變量

D.負變量 E.穩態變量

8.就課本范圍內，解有“≥”型約束方程線性規劃問題的方法有（）

(ABE)A.大M法

B.兩階段法

C.標號法 D.統籌法 E.對偶單純型法

9.線性規劃問題的一般模型中可以出現下面幾種約束

(ABC)A.=

B.≥

C.≤）

（D.⊕ E.∝

10.線性規劃問題的主要特征有（）

(AB)A.目標是線性的

B.約束是線性的

C.求目標最大值 D.求目標最小值 E.非線性

三、判斷題。本大題共10個小題，每小題 2.0 分，共20.0分。

1.線性規劃問題的一般模型中不能有等式約束。(錯誤)2.線性規劃問題的每一個基本可行解對應可行域上的一個頂點。確)3.線性規劃問題的基本解就是基本可行解。(錯誤)4.同一問題的線性規劃模型是唯一。(錯誤)5.對偶問題的對偶一定是原問題。(正確)

正(6.7.產地數與銷地數相等的運輸問題是產銷平衡運輸問題。(錯誤)

對于一個動態規劃問題，應用順推或逆解法可能會得出不同的最優解。(錯誤)8.在任一圖G中，當點集V確定后，樹圖是G中邊數最少的連通圖。(正確)9.若在網絡圖中不存在關于可行流f的增流鏈時，f即為最大流。(正確)10.無圈且連通簡單圖G是樹圖。(正確)

第四篇：管理運籌學(第四版)第十一章習題答案

11.1解：

??4人/小時，??60?4?10人/小時，????0.4，屬于M/M/1排隊模型。6?10

（1）倉庫管理員空閑的概率，即為P0?1???1?0.4?0.6

（2）倉庫內有4個工人的概率即為P4??1????4??1?0.4??0.44?0.01536（3）至少有2個工人的概率為1?P0?P1?1?0.6?0.24?0.16（4）領工具的工人平均數Ls??????44??0.6667人

10?46（5）排隊等待領工具工人的平均數Lq???0.4?41.6???0.2667人 ???10?46（6）平均排隊時間Wq?（7）待定

11.2解：

?????0.40.4??0.0667小時?4分鐘

10?46??6060?3?3人/小時，???4人/小時，????0.75，屬于M/M/1排隊模型。2015?4

（1）不必等待概率，即為P0?1???1?0.75?0.25

（2）不少于3個顧客排隊等待的概率，即系統中有大于等于4個（或大于3個）顧客的概率，為

1?P0?P1?P2?P3?1?0.25?0.1875?0.1406?0.1055?0.3164

（3）顧客平均數Ls??????33??3人 4?31（4）平均逗留時間Ws?11??1小時 ???4?3（5）1.5小時?Ws?11人/小時。平均到達率超過3.333人?，即??3.333???4??時，店主才會考慮增加設備或理發員。

11.3解： ??4人/小時，??60?4?10人/小時，????0.4，屬于M/M/1/3排隊模型。6?10

（1）倉庫內沒有人領工具的概率，即為P0?1??1?0.4??0.6158 N?141??1?0.4（2）工人到達必須排隊等待的概率，即為倉庫內有1個、2個和3個工人的概率和

P1?P2?P3????2??3??1??1?0.423?0.4?0.4?0.4??0.3842

1??N?11?0.44??（3）新到工人離去的概率為P3??31??1?0.43?0.4??0.0394 N?141??1?0.4（4）領工具的工人平均數Ls??1???N?1??N?1?1??N?10.44?0.44??? 41?0.41?0.4（5）排隊等待領工具工人的平均數Lq???0.4?41.6???0.2667人 ???10?46（6）平均排隊時間Wq?

?????0.40.4??0.0667小時?4分鐘

10?46

第五篇：川大《管理運籌學》第一次作業答案..

川大《管理運籌學》第一次作業答案 歡迎你，你的得分： 100.0 完成日期：2013年08月19日 09點39分

說明： 每道小題括號里的答案是您最高分那次所選的答案，而選項旁的標識是標準答案。

一、單項選擇題。本大題共20個小題，每小題 2.0 分，共40.0分。在每小題給出的選項中，只有一項是符合題目要求的。1.規劃的目的是（）

(C)A.合理利用和調配人力、物力，以取得最大收益。

B.合理利用和調配人力、物力，使得消耗的資源最少。

C.合理利用和調配現有的人力、物力，消耗的資源最少，收益最大。

D.合理利用和調配人力、物力，消耗的資源最少，收益最大。

2.當線性規劃問題的一個基解滿足下列哪項要求時稱之為一個可行基解。（）

(C)A.非負 B..小于0 C.大于0

D.非正

3.在運輸方案中出現退化現象，是指數字格的數目()

(C)A.等于m+n B.大于m+n-1 C..小于m+n-1

D.等于m+n-1 4.在線性規劃模型中，沒有非負約束的變量稱為（）

(C)A.多余變量 B.松弛變量 C.自由變量

D.人工變量

5.約束條件為AX=b，X≥0的線性規劃問題的可行解集是

(B)A.補集 B.凸集

C.交集 D.凹集

6.線性規劃問題若有最優解，則一定可以在可行域的（(C)A.內點 B.外點））上達到。

（C.極點

D.幾何點

7.若原問題是一標準型，則對偶問題的最優解值就等于原問題最優表中松弛變量的（）

(D)A.值 B.個數

C.機會費用 D.檢驗數

8.若運輸問題已求得最優解，此時所求出的檢驗數一定是全部

(A)A.大于或等于零

B.大于零 C.小于零

D.小于或等于零

9.若鏈中頂點都不相同，則稱Q為（）

(B)A.基本鏈 B.初等鏈）

（C.簡單鏈 D.飽和鏈

10.若f 是G的一個流，K為G的一個割，且Valf=CapK，則K一定是（）

(A)A.最小割

B.最大割 C.最小流 D.最大流

11.若f*為滿足下列條件的流：Valf*=max{Valf |f為G的一個流}，則稱f*為G的（）

(C)A.最小值 B.最大值 C.最大流

D.最小流

12.線性規劃標準型中bi（i=1，2，……m）必須是（）

(B)A.正數 B.非負數

C.無約束 D.非零的 13.基本可行解中的非零變量的個數小于約束條件數時，該問題可求得()

(C)A.基本解 B.退化解 C.多重解

D.無解

14.原問題的第i個約束方程是“=”型，則對偶問題的變量q i是（）

(B)A.多余變量 B.自由變量

C.松弛變量 D.非負變量

15.．對偶單純型法與標準單純型法的主要區別是每次迭代的基變量都滿足最優檢驗但不完全滿足（）

(D)A.等式約束 B.“≤”型約束 C.“≥”約束 D.非負約束

16.若原問題是求目標最小，則對偶問題的最優解值就等于原問題最優表中剩余變量的（）

(C)A.機會費用 B.個數 C.值

D.機會費用的相反數

17.若一個閉鏈C除了第一個頂點和最后一個頂點相同外，沒有相同的頂點和相同的邊，則該閉鏈C稱為（）

(B)A.初等鏈 B.圈

C.回路 D.飽和鏈

18.若G中不存在流f增流鏈，則f為G的（）

(B)A.最小流 B.最大流

C.最小費用流 D.無法確定

19.若f 是G的一個流，K為G的一個割，且Valf=CapK，則K一定是（）

(A)A.最小割

B.最大割 C.最小流 D.最大流

20.若樹T有n個頂點，那么它的邊數一定是（）

(D)A.n＋2 B.n C.n+1 D.n-1

二、多項選擇題。本大題共10個小題，每小題 4.0 分，共40.0分。在每小題給出的選項中，有一項或多項是符合題目要求的。

1.求運輸問題表上作業法中求初始基本可行解的方法一般有（）

(AB)A.西北角法

B.單純型法

C.最小元素法 D.閉回路法 E.位勢法 2.建立線性規劃問題數學模型的主要過程有（）

(ABD)A.確定決策變量

B.確定目標函數

C.解法

D.確定約束方程

E.建立線性規劃問題數學模型的主要過程有 結果

3.化一般規劃模型為標準型時，可能引入的變量有

(ABE)A.松弛變量

B.剩余變量

C.非負變量 D.非正變量））（（E.自由變量

4.表上作業法中確定換出變量的過程有（）

(ACD)A.判斷檢驗數是否都非負

B.選最大檢驗數 C.確定換出變量

D.選最小檢驗數

E.確定換入變量

5.一般情況下，目標函數系數為零的變量有

(BD)A.自由變量 B.松弛變量

C.人工變量 D.剩余變量）（E.自變量

6.解線性規劃時，加入人工變量的主要作用是（）

(AD)A.求初始基本可行解

B.化等式約束

C.求可行域 D.構造基本矩陣

E.求凸集

7.求解約束條件為“≥”型的線性規劃、構造基本矩陣時，可用的變量有（）

(AD)A.人工變量

B.松弛變量 C.負變量 D.剩余變量

E.穩態變量

8.圖解法求解線性規劃問題的主要過程有（）

(ABE)A.畫出可行域

B.求出頂點坐標

C.求最優目標值

D.選基本解 E.選最優解

9.線性規劃問題的一般模型中可以出現下面幾種約束

(ABC)A.=

B.≥

C.≤

D.⊕ E.∝

10.線性規劃問題的主要特征有（）

(AB)）（A.目標是線性的

B.約束是線性的

C.求目標最大值

D.求目標最小值 E.非線性

三、判斷題。本大題共10個小題，每小題 2.0 分，共20.0分。

1.線性規劃問題的一般模型中一定有不等式約束。

(錯誤)2.線性規劃問題的每一個基本解對應可行域上的一個頂點。(錯誤)3.線性規劃問題的基本解就是基本可行解。(錯誤)4.若原問題可行，對偶問題不可行，則原問題無界。(正確)5.若最優解中沒有松弛變量Xj，表明第 i種資源已用完。(正確)6.產地產量與銷地銷量相等的運輸問題是產銷平衡運輸問題。(正確)7.對于一個動態規劃問題，應用順推或逆解法可能會得出相同的最優解。(正確)8.在任一圖G中，當點集V確定后，樹圖是G中邊數最少的連通圖。(正確)9.若在網絡圖中不存在關于可行流f的增流鏈時，f即為最大流。(正確)10.無圈且連通簡單圖G是樹圖。(正確)