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

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

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

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

第三篇：運籌學習題解答

3.3寫出下列線性規劃問題的對偶問題，再寫出對偶問題的對偶，并驗證其即為原問題對偶。

本題沒有單純形法。

5.3 沒有答案

第四篇：《管理運籌學》第三版習題答案(韓伯棠教授版)

第2章

1、解：

x2 6

線性規劃的圖解法

A 1 O 0 1 B

C3 6

x1

a.可行域為 OABC。

b.等值線為圖中虛線所示。

c.由圖可知，最優解為 B 點，最優解： x1 = 69。

2、解： a

x2

1215

x2 =，最優目標函數值：

0.6

0.1 O

0.1

0.6

x1

x1 = 0.2

有唯一解 b 無可行解 c 無界解 d 無可行解 e 無窮多解 x 2 = 0.6 函數值為 3.6 20 x1 = 923 f 有唯一解函數值為

x2 = 3

3、解：

a 標準形式：

max f = 3x1 + 2 x 2 + 0s1 + 0 s 2 + 0s 3 x1 + 2 x 2 + s1 = 30 3x1 + 2 x 2 + s 2 = 13 2 x1 + 2 x 2 + s3 = 9 x1 , x 2 , s1 , s 2 , s3 ≥ 0

b 標準形式：

max f = ?4 x1 ? 6 x3 ? 0s1 ? 0s2

3x1 ? x 2 ? s1 = 6 x1 + 2 x 2 + s 2 = 10 7 x1 ? 6 x 2 = 4 x1 , x 2 , s1 , s 2 ≥ 0

c 標準形式：

max f = ? x1' + 2 x2 ? x2 ? 0s1 ? 0s2 '''

? 3x1 + 5 x 2 ? 5 x 2'

+ s1 = 70 ''2 x1' ? 5 x 2 + 5 x 2' = 50

''3x1' + 2 x 2 ? 2 x 2' ? s 2 = 30

''x1' , x 2 , x 2' , s1 , s 2 ≥ 0

''4、解：

標準形式： max z = 10 x1 + 5 x 2 + 0 s1 + 0 s 2

3x1 + 4 x 2 + s1 = 9 x1 + 2 x 2 + s 2 = 8 x1 , x 2 , s1 , s 2 ≥ 0

s1 = 2, s2 = 0 5、解：

標準形式： min f = 11x1 + 8 x 2 + 0s1 + 0s 2 + 0s3 x1 + 2 x 2 ? s1 = 20 3x1 + 3x 2 ? s 2 = 18 4 x1 + 9 x 2 ? s3 = 36

x1 , x 2 , s1 , s 2 , s3 ≥ 0

s1 = 0, s2 = 0, s3 = 13 6、解：

b 1 ≤ c1 ≤ 3 c 2 ≤ c2 ≤ 6 x1 = 6 d x2 = 4

e x1 ∈ [4,8] x 2 = 16 ? 2 x1 f 變化。原斜率從 ?

7、解：

模型：

變為 ? 1 3

max z = 500 x1 + 400 x 2 x1 ≤ 300 3x2 ≤ 540 x1 + 2 x2 ≤ 440 1.2 x1 + 1.5 x2 ≤ 300 x1 , x2 ≥ 0

a x1 = 150 x 2 = 70 即目標函數最優值是 103000 b 2，4 有剩余，分別是 330，15。均為松弛變量 c 50，0，200，0額外利潤 250 d 在 [0,500] 變化，最優解不變。e 在 400 到正無窮變化，最優解不變。f 不變 8、解：

a 模型： min f = 8 x a + 3 xb

x a + 100 xb ≤ 1200000 5 x a + 4 xb ≥ 60000 100 xb ≥ 300000 x a , xb ≥ 0

基金 a,b 分別為 4000，10000。回報率：60000

b 模型變為： max z = 5 x a + 4 xb

x a + 100 xb ≤ 1200000 100 xb ≥ 300000 x a , xb ≥ 0

推導出： x1 = 18000 x 2 = 3000

故基金 a 投資 90 萬，基金 b 投資 30 萬。第3章

1、解： a x1 = 150 x 2 = 70

線性規劃問題的計算機求解

目標函數最優值 103000

b 1，3 使用完 2，4 沒用完0，330，0，15 c 50，0，200，0

含義： 1 車間每增加 1 工時，總利潤增加 50 元車間每增加 1 工時，總利潤增加 200 元2、4 車間每增加 1 工時，總利潤不增加。d 3 車間，因為增加的利潤最大

e 在 400 到正無窮的范圍內變化，最優產品的組合不變 f 不變 因為在 [0,500] 的范圍內

g 所謂的上限和下限值指當約束條件的右邊值在給定范圍內變化時，約束條

件 1 的右邊值在 [200,440]變化，對偶價格仍為 50（同理解釋其他約束條件）h 100×50=5000 對偶價格不變

i能

j 不發生變化 允許增加的百分比與允許減少的百分比之和沒有超出 100% k 發生變化

2、解：

a 4000 1000062000

b 約束條件 1：總投資額增加 1 個單位，風險系數則降低 0.057

約束條件 2：年回報額增加 1 個單位，風險系數升高 2.167 c 約束條件 1 的松弛變量是 0，約束條件 2 的剩余變量是 0

約束條件 3 為大于等于，故其剩余變量為 700000

d 當 c 2 不變時，c1 在 3.75 到正無窮的范圍內變化，最優解不變

當 c1 不變時，c 2 在負無窮到 6.4 的范圍內變化，最優解不變

e 約束條件 1 的右邊值在 [780000,1500000] 變化，對偶價格仍為 0.057（其他

同理）

f 不能，理由見百分之一百法則二 3、解：

a 18000 3000 102000 153000

b 總投資額的松弛變量為 0 基金 b 的投資額的剩余變量為 0 c 總投資額每增加 1 個單位，回報額增加 0.1

基金 b 的投資額每增加 1 個單位，回報額下降 0.06 d c1 不變時，c 2 在負無窮到 10 的范圍內變化，其最優解不變 c 2 不變時，c1 在 2 到正無窮的范圍內變化，其最優解不變 e 約束條件 1 的右邊值在 300000 到正無窮的范圍內變化，對偶價格仍為 0.1約束條件 2 的右邊值在 0 到 1200000 的范圍內變化，對偶價格仍為-0.06

600000 300000

f+= 100% 故對偶價格不變

900000 900000

4、解：

a x1 = 8.5 x 2 = 1.5x 3 = 0 x4 = 1 最優目標函數 18.5

對偶價格為 2 和 3.5b 約束條件 2 和 3 c 選擇約束條件 3，最優目標函數值 22

d 在負無窮到 5.5 的范圍內變化，其最優解不變，但此時最優目標函數值變化

e 在 0 到正無窮的范圍內變化，其最優解不變，但此時最優目標函數值變化

5、解：

a 約束條件 2 的右邊值增加 1 個單位，目標函數值將增加 3.622 b x 2 產品的利潤提高到 0.703,才有可能大于零或生產 c 根據百分之一百法則判定，最優解不變

1565

d 因為我們不能判定+> 100 % 根據百分之一百法則二，? 9.189 111.25 ? 1

5其對偶價格是否有變化 第4章 線性規劃在工商管理中的應用

1、解：為了用最少的原材料得到 10 臺鍋爐，需要混合使用 14 種下料方案

方案 規格 2640 1770 1651 1440 合計 剩余

方案 規格 2640 1770 1651 1440 合計 剩余 1 2 0 0 0 5280 220 8 1 1 0 0 4410 1090 9 1 0 1 0 4291 1209 10 1 0 0 1 4080 1420 11 0 3 0 0 5310 190 12 0 2 1 0 5191 309 13 0 2 0 1 4980 520 14

0 1 2 0 5072 428 0 1 1 1 4861 639 0 1 0 2 4650 850 0 0 3 0 4953 547 0 0 2 1 4742 758 0 0 1 2 4531 969 0 0 0 3 4320 1180

設按 14 種方案下料的原材料的根數分別為 x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14，則可列出下面的數學模型：

min f＝x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14 s．t． 2x1＋x2＋x3＋x4 ≥ 80

x2＋3x5＋2x6＋2x7＋x8＋x9＋x10 ≥ 350 x3＋x6＋2x8＋x9＋3x11＋x12＋x13 ≥ 420 x4＋x7＋x9＋2x10＋x12＋2x13＋3x14 ≥ 10

x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14≥ 0

用管理運籌學軟件我們可以求得此問題的解為：

x1＝40，x2＝0，x3＝0，x4＝0，x5＝116.667，x6＝0，x7＝0，x8＝0，x9＝0，x10＝0，x11＝140，x12＝0，x13＝0，x14＝3.33

3最優值為 300。

2、解：從上午 11 時到下午 10 時分成 11 個班次，設 xi 表示第 i 班次安排的臨時

工的人數，則可列出下面的數學模型：

min f＝16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11）

s．t． x1＋1 ≥ 9 x1＋x2＋1 ≥ 9 x1＋x2＋x3＋2 ≥ 9 x1＋x2＋x3＋x4＋2 ≥ 3 x2＋x3＋x4＋x5＋1 ≥ 3 x3＋x4＋x5＋x6＋2 ≥ 3 x4＋x5＋x6＋x7＋1 ≥ 6 x5＋x6＋x7＋x8＋2 ≥ 12 x6＋x7＋x8＋x9＋2 ≥ 12 x7＋x8＋x9＋x10＋1 ≥ 7 x8＋x9＋x10＋x11＋1 ≥ 7

x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11≥ 0 用管理運籌學軟件我們可以求得此問題的解為：

x1＝8，x2＝0，x3＝1，x4＝1，x5＝0，x6＝4，x7＝0，x8＝6，x9＝0，x10＝0，x11＝0 最優值為 320。

a、在滿足對職工需求的條件下，在 10 時安排 8 個臨時工，12 時新安排

1個臨時工，13 時新安排 1 個臨時工，15 時新安排 4 個臨時工，17 時新

安排 6 個臨時工可使臨時工的總成本最小。

b、這時付給臨時工的工資總額為 80 元，一共需要安排 20 個臨時工的班

次。

約束-------1 2 3 4 5 6 7 8 9 10 1

1松弛/剩余變量

對偶價格

0-4 0 0 2 0 9 0 0-4 5 0 0 0 0 0 0-4 0 0 0 0

根據剩余變量的數字分析可知，可以讓 11 時安排的 8 個人工作 3 小時，13

時安排的 1 個人工作 3 小時，可使得總成本更小。

C、設在 11：00-12：00 這段時間內有 x1 個班是 4 小時，y1 個班是 3 小時； 設在 12：00-13：00 這段時間內有 x 2 個班是 4 小時，y 2 個班是 3 小時；其他時 段也類似。

則：由題意可得如下式子： 11

min z = 16∑ x1 + 12∑ y1

i =1 i =1 S．T

x1 + y1 + 1 ≥ 9

x1 + y1 + x2 + y2 + 1 ≥ 9

x1 + y1 + x2 + y2 + x3 + y3 + 1 + 1 ≥ 9 x1 + x2 + y2 + x3 + y3 + x4 + y4 + 1 + 1 ≥ 3

x2 + x3 + y3 + x4 + y4 + x5 + y5 + 1 ≥ 3 x3 + x4 + y4 + x5 + y5 + x6 + y6 + 1 + 1 ≥ 3 x4 + x5 + y5 + x6 + y6 + x7 + y7 + 1 ≥ 6 x5 + x6 + y6 + x7 + y7 + x8 + y8 + 1 + 1 ≥ 12 x6 + x7 + y7 + x8 + y8 + x9 + y9 + 1 + 1 ≥ 12 x7 + x8 + y8 + x9 + y9 + x10 + y10 + 1 ≥ 7 x8 + x9 + y9 + x10 + y10 + x11 + y11 + 1 ≥ 7 xi ≥ 0, yi ≥ 0 i=1,2,…,11

稍微變形后，用管理運籌學軟件求解可得：總成本最小為 264 元。

安排如下：y1=8（即在此時間段安排 8 個 3 小時的班）3=1，y5=1，y7=4，x8=6，y 這樣能比第一問節省：320-264=56 元。

3、解：設生產 A、B、C 三種產品的數量分別為 x1，x2，x3，則可列出下面的數學模型：

max z＝10 x1＋12 x2＋14 x

2s．t． x1＋1.5x2＋4x3 ≤ 2000 2x1＋1.2x2＋x3 ≤ 1000 x1 ≤ 200 x2 ≤ 250 x3 ≤ 100

x1，x2，x3≥ 0

用管理運籌學軟件我們可以求得此問題的解為：

x1＝200，x2＝250，x3＝100

最優值為 6400。

a、在資源數量及市場容量允許的條件下，生產 A 200 件，B 250 件，C 100

件，可使生產獲利最多。

b、A、B、C 的市場容量的對偶價格分別為 10 元，12 元，14 元。材料、臺

時的對偶價格均為 0。說明 A 的市場容量增加一件就可使總利潤增加 10

元，B 的市場容量增加一件就可使總利潤增加 12 元，C 的市場容量增加

一件就可使總利潤增加 14 元。但增加一千克的材料或增加一個臺時數都

不能使總利潤增加。如果要開拓市場應當首先開拓 C 產品的市場，如果

要增加資源，則應在 975 到正無窮上增加材料數量，在 800 到正無窮上

增加機器臺時數。

4、解：設白天調查的有孩子的家庭的戶數為 x11，白天調查的無孩子的家庭的戶 數為 x12，晚上調查的有孩子的家庭的戶數為 x21，晚上調查的無孩子的家庭 的戶數為 x22，則可建立下面的數學模型： min f＝25x11＋20x12＋30x21＋24x22 s．t． x11＋x12＋x21＋x22 ≥ 2000 x11＋x12 ＝ x21＋x2

2x11＋x21 ≥ 700 x12＋x22 ≥ 450

x11, x12, x21, x22 ≥ 0

用管理運籌學軟件我們可以求得此問題的解為：

x11＝700，x12＝300，x21＝0，x22＝1000

最優值為 47500。

白天調查的無孩子的家庭的戶a、白天調查的有孩子的家庭的戶數為 700 戶，數為 300 戶，晚上調查的有孩子的家庭的戶數為 0，晚上調查的無孩子的家庭的戶數為 1000 戶，可使總調查費用最小。

總調查費用不會變化；b、白天調查的有孩子的家庭的費用在 20－26 元之間，總調查費用不會變化；白天調查的無孩子的家庭的費用在 19－25 元之間，晚上調查的有孩子的家庭的費用在 29－無窮之間，總調查費用不會變化；

晚上調查的無孩子的家庭的費用在－20－25 元之間，總調查費用不會變

化。

c、調查的總戶數在 1400－無窮之間，總調查費用不會變化；

有孩子家庭的最少調查數在 0－1000 之間，總調查費用不會變化；

無孩子家庭的最少調查數在負無窮－1300 之間，總調查費用不會變化。

5、解：設第 i 個月簽訂的合同打算租用 j 個月的面積為 xij，則需要建立下面的數學模型：

min f＝2800（x11＋x21＋x31＋x41）＋4500（x12＋x22＋x32）＋6000（x13＋x23）

＋7300 x14

s．t．x11＋x12＋x13＋x14 ≥ 15

x12＋x13＋x14＋x21＋x22＋x23 ≥ 10 x13＋x14＋x22＋x23＋x31＋x32≥ 20 x14＋x23＋x32＋x41≥ 12

xij ≥ 0，i，j＝1，2，3，4

用管理運籌學軟件我們可以求得此問題的解為：

x11＝5，x12＝0，x13＝10，x14＝0，x21＝0，x22＝0，x23＝0，x31＝10，x32＝0，x41＝0

最優值為 102000。

即：在一月份租用 500平方米一個月，租用 1000平方米三個月；在三月

份租用 1000平方米一個月，可使所付的租借費最小。

6、解：設 xij 表示第 i 種類型的雞需要第 j 種飼料的量，可建立下面的數學模型：

max z＝9（x11＋x12＋x13）＋7（x21＋x22＋x23）＋8（x31＋x32＋x33）－5.5（x11＋x21＋x31）－4（x12＋x22＋x32）－5（x13＋x23＋x33）

s．t． x11 ≥ 0.5（x11＋x12＋x13）x12 ≤ 0.2（x11＋x12＋x13）

x21 ≥0.3（x21＋x22＋x23）

x23 ≤ 0.3（x21＋x22＋x23）

x33 ≥ 0.5（x31＋x32＋x33）

x11＋x21＋x31 ≤ 30 x12＋x22＋x32 ≤ 30 x13＋x23＋x33 ≤30

xij ≥ 0，i，j＝1，2，3

用管理運籌學軟件我們可以求得此問題的解為：

x11＝30，x12＝10，x13＝10，x21＝0，x22＝0，x23＝0，x31＝0，x32＝20，x33＝20 最優值為 365。

即：生產雛雞飼料 50 噸，不生產蛋雞飼料，生產肉雞飼料 40 噸。

7、設 Xi——第 i 個月生產的產品 I 數量

Yi——第 i 個月生產的產品 II 數量

Zi，Wi 分別為第 i 個月末產品 I、II 庫存數

。則S1i，S2i 分別為用于第（i+1）個月庫存的自有及租借的倉庫容積（立方米）

可建立如下模型：

12

min z = ∑(5 xi + 8 y i)+ ∑(4.5 xi + 7 y i)+ ∑ i =1 i =6 i =1(s1i + 1.5s 2i)5s.t.X1-10000=Z1 X2+Z1-10000=Z2 X3+Z2-10000=Z3 X4+Z3-10000=Z4 X5+Z4-30000=Z5 X6+Z5-30000=Z6 X7+Z6-30000=Z7 X8+Z7-30000=Z8 X9+Z8-30000=Z9 X10+Z9-100000=Z10 X11+Z10-100000=Z11 X12+Z11-100000=Z12 Y1-50000=W1 Y2+W1-50000=W2 Y3+W2-15000=W3 Y4+W3-15000=W4 Y5+W4-15000=W5 Y6+W5-15000=W6 Y7+W6-15000=W7 Y8+W7-15000=W8 Y9+W8-15000=W9 Y10+W9-50000=W10 Y11+W10-50000=W11 Y12+W11-50000=W12 S1i≤15000 1≤i≤12 Xi+Yi≤120000 1≤i≤12

0.2Zi+0.4Wi=S1i+S2i 1≤i≤12

Xi≥0, Yi≥0, Zi≥0, Wi≥0, S1i≥0, S2i≥0 用管理運籌學軟件我們可以求得此問題的解為： 最優值= 4910500

X1=10000, X2=10000, X3=10000, X4=10000, X5=30000, X6=30000, X7=30000, X8=45000, X9=105000, X10=70000, X11=70000, X12=70000;Y1= 50000, Y2=50000, Y3=15000, Y4=15000, Y5=15000, Y6=15000, Y7=15000, Y8=15000, Y9=15000, Y10=50000, Y11=50000, Y12=50000;Z8=15000, Z9=90000, Z10 =60000, Z1=30000;S18=3000, S19=15000, S110=12000, S111=6000;S28=3000;

其余變量都等于 0

8、解：設第 i 個車間生產第 j 種型號產品的數量為 xij，可建立下面的數學模型：

max z＝25（x11＋x21＋x31＋x41＋x51）＋20（x12＋x32＋x42＋x52）＋17（x1

3＋x23＋x43＋x53）＋11（x14＋x24＋x44）

s．t． x11＋x21＋x31＋x41＋x51 ≤ 1400 x12＋x32＋x42＋x52 ≥ 300 x12＋x32＋x42＋x52 ≤ 800 x13＋x23＋x43＋x53 ≤ 8000 x14＋x24＋x44 ≥ 700

5x11＋7x12＋6x13+5x14 ≤ 18000 6x21＋3x23＋3x24 ≤ 15000 4x31＋3x32 ≤ 14000

3x41＋2x42＋4x43＋2x44 ≤ 12000 2x51＋4x52＋5x53 ≤ 10000

xij ≥ 0，i＝1，2，3，4，5 j＝1，2，3，4用管理運籌學軟件我們可以求得此問題的解為：

x11＝0，x12＝0，x13＝1000，x14＝2400，x21＝0，x23＝5000，x24＝0，x31＝1400，x32＝800，x41＝0，x42＝0，x43＝0，x44＝6000，x51＝0，x52＝0，x53＝2000

最優值為 279400

9、解：設第一個月正常生產 x1，加班生產 x2，庫存 x3；第二個月正常生產 x4，加班生產 x5，庫存 x6；第三個月正常生產 x7，加班生產 x8，庫存 x9；第四個月正常生產 x10，加班生產 x11，可建立下面的數學模型：

min f ＝ 200（x1＋x4＋x7＋x10）＋300（x2＋x5＋x8＋x11）＋60（x3＋x6

＋x9）s．t．

x1≤4000 x4≤4000 x7≤4000 x10≤4000 x3≤1000 x6≤1000 x9≤1000 x2≤1000 x5≤1000 x8≤1000 x11≤1000

x1+ x2-x3=4500

x3+ x4+ x5-x6=3000 x6+ x7+ x8-x9=5500 x9+ x10+ x11=4500

x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11≥0

計算結果是：

minf= 3710000 元

x1＝4000 噸，x2=500 噸，x3＝0 噸，x4=4000 噸，x5＝0 噸，x6＝1000 噸，x7＝4000 噸，x8＝500 噸，x9＝0 噸，x10＝4000 噸，x11＝500 噸。

第 5 章 單純形法

1、解：表中 a、c、e、f 是可行解，a、b、f 是基本解，a、f 是基本可行解。

2、解：a、該線性規劃的標準型為： max 5 x1＋9 x2

s．t．0.5 x1＋x2＋s1＝8

x1＋x2－s2＝10

0.25 x1＋0.5 x2－s3＝6

x1，x2，s1，s2，s3 ≥0.b、有兩個變量的值取零，因為有三個基變量、兩個非基變量，非基變量 取零。

（4，6，0，0，－2）c、（0，10，－2，0，－1）d、e、不是。因為基本可行解要求基變量的值全部非負。

3、解：a、迭代次數 基變量 s1 s2 s3 xj cj－xj

cB 0 0 0 0

x1 6 3 0 2 0 6 x2 30 1 2 [1] 0 30*

x3 25 0 1 － 25

x4 0 1 0 0 0 0 x5 0 0 1 0 0 0 x6 0 0 0 1 0 0

b 40 50 20 0

b、線性規劃模型為：

max 6 x1＋30 x2＋25 x3 s．t．3 x1＋x2＋s1 = 40 2 x1＋x3＋s2= 50 2 x1＋x2－x3＋s3＝20

x1，x2，x3，s1，s2，s3 ≥0

，初始解為（0，0，0，40，50，20），c、初始解的基為（s1，s2，s3）

對應的目標函數值為 0。

d、第一次迭代時，入基變量是 x2，出基變量為 s3。

，最優值為 9。

4、解：最優解為（2.25，0）X2

X1

，最優值為 84。

5、解：a、最優解為（2，5，4），最優值為－4。b、最優解為（0，0，4）

6、解：a、有無界解

，最優值為－2.144。b、最優解為（0.714，2.143，0）

7、解：a、無可行解

，最優值為 28。b、最優解為（4，4）c、有無界解

，最優值為 8。d、最優解為（4，0，0）第6章

a． c1≤24 b． c2≥6 c． cs2≤8 2

a.c1≥-0.5 b.-2≤c3≤0 c.cs2≤0.5 3

a.b1≥150

b.0≤b2≤83.333 c.0≤b3≤150

單純形法的靈敏度分析與對偶

a.b1≥-4 b.0≤b2≤300 c.b3≥4

a.利潤變動范圍 c1≤3，故當 c1=2 時最優解不變 b.根據材料的對偶價格為 1 判斷，此做法不利 c.d.0≤b2≤45

e.最優解不變，故不需要修改生產計劃

此時生產計劃不需要修改，因為新的產品計算的檢驗數為-12 小于零，對原生 產計劃沒有影響。

均為唯一最優解，根據從計算機輸出的結果看出，如果松弛或剩余變量為零且對 應的對偶價格也為零，或者存在取值為零的決策變量并且其相差值也為零時，可 知此線性規劃有無窮多組解。7

a.min f= 10y1+20y2.s.t.y1+y2≥2,y1+5y2≥1,y1+y2≥1,y1, y2≥0.b.max z= 100 y1+200 y2.s.t.1/2 y1+4 y2≤4,y1+6 y2≤4, 2 y1+3 y2≤2, y1, y2≥0.8.a.min f=-10 y1+50 y2+20 y3-20 y4.s.t.-2 y1+3 y2+ y3-y2≥1，≥2,3 y1+ y2 y1-y2+ y3≤2,y1-2 y2-y3≤3,y1, y2, y3≥0 目標函數最優值為: 10

最優解: x1=6, x2=2, x3=0

第 7 章 運輸問題

1.（1）此問題為產銷平衡問題

甲乙 分廠2117 2 分廠1015 3 分廠2321 銷量400250

丙 23 30 20 350 丁 25 19 22 200 產量 300 400 500 1200

最優解如下

******************************************** 起至 銷點 發點12

------------------10250 24000 300

此運輸問題的成本或收益為: 19800

3-----0 0 350 4-----50 0 150

此問題的另外的解如下：

起至 銷點 發點12

------------------10250 24000 300

此運輸問題的成本或收益為: 19800

3-----50 0 300 4-----0 0 200

（2）如果 2 分廠產量提高到 600，則為產銷不平衡問題

最優解如下

******************************************** 起 發點

--------1 2 3 至 銷點

----------0250 4000 00

3-----0 0 350 4-----0 200 0 此運輸問題的成本或收益為: 注釋：總供應量多出總需求量 第 1 個產地剩余 50 第 3 個產地剩余 150

19050 200

（3）銷地甲的需求提高后，也變為產銷不平衡問題

最優解如下

********************************************

起至 銷點 發點12

------------------150250 24000 300

此運輸問題的成本或收益為: 19600

3-----0 0 350 4-----0 0 150

注釋：總需求量多出總供應量150 第 1 個銷地未被滿足，缺少 100 第 4 個銷地未被滿足，缺少 50

2． 本題運輸模型如下：

ⅰⅱ 甲0.30.4 乙0.30.1 丙0.050.05 丁-0.20.3 300250

ⅲ 0.3-0.4 0.15 0.1 350

ⅳ 0.4 0.2 0.05-0.1 200 ⅴ 0.1-0.2-0.05-0.1 250 VI 0.9 0.6 0.55 0.1 150

300 500 400 100

最優解如下

********************************************

起 發點--------1 2 3 4 5 至 銷點 1-----0 0 0 0 150 2-----0 0 50 100 0-----100 0 0 0 50-----0 0 100 0 0-----0 350 0 0 0-----200 0 0 0 0-----0 0 250 0 0-----0 150 0 0 0

此運輸問題的成本或收益為: 1.050013E+07 3． 建立的運輸模型如下：

123

1600600+60600+60

1’600+600 10% 600+600 10%+60 600+600 2700700+60

2’700+700 10%700+700 3650

3’650+650 356

最優解如下

********************************************起至 銷點 發點1

-------------2 3

12----------21 0 0 30 1 1 40 0 0 50 4 0 60 0 0 70

0 2 0 此運輸問題的成本或收益為:

8465

此問題的另外的解如下： 起至 銷點 發點1

-------------2

12----------21 0 0 30 2 0 40 0 0 50 3 1 60 0 0 70

0 2 0

此運輸問題的成本或收益為:

8465

10%+60 2 3 4 10%+602 2 10%3

4-----0 0 3 0 2 0 0

4-----0 0 3 0 2 0 0

4． 甲 乙 A B C D 甲 0 80 150 200 180 240 1100 乙 100 0 80 210 60 170 1100

A 150 80 0 70 110 90 1400

B 200 210 60 0 130 50 1300

C 180 60 110 140 0 85 1600

D 240 170 80 50 90 0 1200

1600 1700 1100 1100 1100 1100

最優解如下

********************************************

起 至 銷點 發點 1 2 3 4 5 6--------------------------------------1 1100 0 300 200 0 0 2 0 1100 0 0 600 0 3 0 0 1100 0 0 0 4 0 0 0 1100 0 0 5 0 0 0 0 1000 100 6 0 0 0

0

0

1100

此運輸問題的成本或收益為: 130000

5．建立的運輸模型如下

min f = 500x1+300 x2+550 x3+650 x4.s.t.54 x1+49 x2+52 x3+64 x4≤1100,57 x1+73 x2+69 x3+65 x4≤1000,x1, x2, x3, x4≥0.A5449 B5773 3 4 500300 52 64 69

550

650

最優解如下

********************************************

起

至 銷點

發點

------------------3 4 1 250300----------2 2500

550 0 0 650 1100 1000

5-----0 100 此運輸問題的成本或收益為: 113300

6.a.最小元素法的初始解如下：

甲 8 7

乙

丙

0 0

銷量 20

0 10 0

b.最優解如下

******************************************** 起至 銷點

發點1

-------------2 3 10----------220 0 15 30

0 此運輸問題的成本或收益為:

5

145

c.該運輸問題只有一個最優解，因為其檢驗數均不為零

最優解如下d.******************************************** 起至 銷點

發點12

------------------3 100-----2250 0

此運輸問題的成本或收益為: 135 5

0 5

0

產量 0 15 5 0

0

第 8 章 整數規劃

1． 求解下列整數規劃問題

a.max z=5x1 +8x 2

s.t.x1 +x 2 ≤ 6, 5x1 +9x 2 ≤ 45, x1 ,x 2 ≥ 0,且為整數

目標函數最優解為 : x1*=0,x 2 *=5,z*=40。

b.max z=3x1 +2x 2

s.t.2x1 +3x 2 ≤ 14, 2x1 +x 2 ≤ 9，x1,x2 ≥ 0,且x1為整數。

目標函數最優解為 : x1*=3,x 2 *=2.6667,z*=14.3334。

c.max z=7x1 +9x 2 +3x 3

s.t.-x1 +3x 2 +x 3 ≤ 7, 7x1 +x 2 +x 3 ≤ 38，x1 ,x 2 ,x 3 ≥ 0,且x1為整數，x 3為0-1變量。

目標函數最優解為 : x1*=5,x 2 *=3,x 3 *=0,z*=62。

2．解：設 xi 為裝到船上的第 i 種貨物的件數，i=1,2,3,4,5。則該船裝載的貨 物取得最大價值目標函數的數學模型可寫為：

max z=5x1 +10x 2 +15x 3 +18x 4 +25x 5 s.t.20x1 +5x 2 +10x 3 +12x 4 +25x 5 ≤ 400000, x1 +2x 2 +3x 3 +4x 4 +5x 5 ≤ 50000, x1 +4x 4 ≤ 10000

0.1x1 +0.2x 2 +0.4x 3 +0.1x 4 +0.2x 5 ≤ 750, x i ≥ 0, 且為整數，i=1，。2345

目標函數最優解為

: x1*=0,x 2 *=0,x 3 *=0,x 4 *=2500,x

*=2500,z*=107500.3．解：設 xi 為第 i 項工程，i=1,2,3,4,5,且 xi 為 0-1 變量，并規定，?1, 當第i項工程被選定時，xi = ?

?0，當第i項工程沒被選定時。

根據給定條件，使三年后總收入最大的目標函數的數學模型為： max z = 20x1 + 40x 2 + 20x 3 + 15x 4 + 30x 5

s.t.5x1 +4x 2 +3x 3 +7x 4 +8x 5 ≤ 25，x1 +7x 2 +9x 3 +4x 4 +6x 5 ≤ 25，8x1 +10x 2 +2x 3 +x 4 +10x 5 ≤ 25，x i為0-1變量，i=1，。2345

目標函數最優解為

: x1*=1,x

*=0,z*=95

*=1,x

*=1,x

*=1,x 4．解：這是一個混合整數規劃問題

設 x1、x2、x3 分別為利用 A、B、C 設備生產的產品的件數，生產準備費

只有在利用該設備時才投入，為了說明固定費用的性質，設

?1，當利用第i種設備生產時，即x i >0, yi = ?

?0，當不利用第i種設備生產時，即x i =0。故其目標函數為：

min z = 100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3

為了避免沒有投入生產準備費就使用該設備生產，必須加以下的約束條件，M 為充分大的數。

x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3 M，設 M=1000000

a.該目標函數的數學模型為： min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，0.5x1 +1.8x 2 +1.0x 3 ≤ 2000，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且為整數，y1，y 2，y3為0-1變量。

目標函數最優解為

: x1*=370,x 2

*=231,x

*=1399,y1 =1,y

=1,z*=10647

b.該目標函數的數學模型為：

min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，0.5x1 +1.8x 2 +1.0x 3 ≤ 2500，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且為整數，y1，y 2，y3為0-1變量。目標函數最優解為

: x1*=0,x 2 *=625,x

*=1375,y1 =0,y

=1,z*=8625

=1,y3

=1,y3 c.該目標函數的數學模型為：

min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，0.5x1 +1.8x 2 +1.0x 3 ≤ 2800，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且為整數，y1，y 2，y3為0-1變量。目標函數最優解為

: x1*=0,x =1,z*=7500

*=1000,x

*=1000,y1 =0,y

=1,y3 d.該目標函數的數學模型為：

min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且為整數，y1，y 2，y3為0-1變量。

目標函數最優解為 : x1*=0,x 2 *=1200,x 3 *=800,y1 =0,y 2 =1,y3 =1,z*=6900 5．解：設 xij 為從 Di 地運往 Ri 地的運輸量，i=1，2，3，4，j=1，2，3 分別 代表從北京、上海、廣州、武漢運往華北、華中、華南的貨物件數，并規定，?1，當i地被選設庫房，yi = ?

?0，當i地沒被選設庫房。該目標函數的數學模型為： min z = 45000y1 + 50000y 2 + 70000y3 + 40000y 4 + 200x11 + 400x12 + 500x13 +300x 21 + 250x 22 +400x 23 +600x 31 +350x 32 +300x 33 +350x 41 +150x 42 +350x 43 s.t.x11 +x 21 +x 31 +x 41 =500，x12 +x 22 +x 32 +x 42 =800，x13 +x 23 +x 33 +x 43 =700，x11 +x12 +x13 ≤ 1000y1，x 21 +x 22 +x 23 ≤ 1000y 2，x 31 +x 32 +x 33 ≤ 1000y3，x 41 +x 42 +x 43 ≤ 1000y 4，y2 ≤ y4，y1 +y 2 +y3 +y 4 ≤ 2，y3 +y 4 ≤ 1，x ij ≥ 0，且為整數，yi為0-1分量，i=1，。234 目標函數最優解為

x11*=500,x12 *=0,x13 *=500,x 21*=0,x 22 *=0,x 23 *=0,x 31*=0,x 32 *=0,x

: 33 *=0，x 41*=0,x 42 *=800,x 43 *=200,y1 =1,y 2 =0,y3 =0,y 4 =1,z*=625000

也就是說在北京和武漢建庫房，北京向華北和華南各發貨 500 件，武漢向華 中發貨 800 件，向華南發貨 200 件就能滿足要求，即這就是最優解。

?1，當指派第i人去完成第j項工作時，6．解：引入 0-1 變量 xij，并令 x ij = ?

?0，當不指派第i人去完成第j項工作時。a.為使總消耗時間最少的目標函數的數學模型為：

min z = 20x11 + 19x12 + 20x13 + 28x14 + 18x 21 + 24x 22 + 27x 23 + 20x 24 +26x 31

+16x 32 +15x 33 +18x 34 +17x 41 +20x 42 +24x 43 +19x 44 s.t.x11 +x12 +x13 +x14 =1，x 21 +x 22 +x 23 +x 24 =1，x 31 +x 32 +x 33 +x 34 =1，x 41 +x 42 +x 43 +x 44 =1，x11 +x 21 +x 31 +x 41 =1，x12 +x 22 +x 32 +x 42 =1，x13 +x 23 +x 33 +x 43 =1，x14 +x 24 +x 34 +x 44 =1，x ij為0-1變量，i=1，，j=1，。234234 目標函數最優解為 :

x11*=0,x12 *=1,x13 *=0,x14 *=0,x 21*=1,x 22 *=0,x 23 *=0,x 24 *=0,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=1,z*=71

或

x11*=0,x12 *=1,x13 *=0,x14 *=0,x 21*=0,x 22 *=0,x 23 *=0,x 24 *=1,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=1,x 42 *=0,x 43 *=0,x 44 *=0,z*=71

即安排甲做 B 項工作，乙做 A 項工作，丙 C 項工作，丁 D 項工作，或者是 安排甲做 B 項工作，乙做 D 項工作，丙 C 項工作，丁 A 項工作，最少時間為 71 分鐘。

b.為使總收益最大的目標函數的數學模型為： 將 a 中的目標函數改為求最大值即可。目標函數最優解為

:

x11*=0,x12 *=0,x13 *=0,x14 *=1,x 21*=0,x 22 *=1,x 23 *=0,x 24 *=0,x 31*=1,x 32 *=0,x 33 *=0，x 34 *=0,x 41*=0,x 42 *=0,x 43 *=1,x 44 *=0,z*=102

即安排甲做 D 項工作，乙做 C 項工作，丙 A 項工作，丁 B 項工作，最大收 益為 102。

c.由于工作多人少，我們假設有一個工人戊，他做各項工作的所需的時間均 為 0，該問題就變為安排 5 個人去做 5 項不同的工作的問題了，其目標函數的數 學模型為： min z = 20x11 + 19x12 + 20x13 + 28x14 + 17x15 + 18x 21 + 24x 22 + 27x 23 + 20x 24 +20x 25

+26x 31 +16x 32 +15x 33 +18x 34 +15x 35 +17x 41 +20x 42 +24x 43 +19x 44 +16x 45 s.t.x11 +x12 +x13 +x14 +x15 =1，x 21 +x 22 +x 23 +x 24 +x 25 =1，x 31 +x 32 +x 33 +x 34 +x 35 =1，x 41 +x 42 +x 43 +x 44 +x 45 =1，x 51 +x 52 +x 53 +x 54 +x 55 =1，x11 +x 21 +x 31 +x 41 +x 51 =1，x12 +x 22 +x 32 +x 42 +x 52 =1，x13 +x 23 +x 33 +x 43 +x 53 =1，x14 +x 24 +x 34 +x 44 +x 54 =1，x15 +x 25 +x 35 +x 45 +x 55 =1，x ij為0-1變量，i=1，，，j=1，。23452345

目標函數最優解為:

x11*=0,x12 *=1,x13 *=0,x14 *=0,x15 *=0,x 21*=1,x 22 *=0,x 23 *=0,x 24 *=0,x 25 *=0,x 31*=0，x 32 *=0,x 33 *=1,x 34 *=0,x 35 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=0,x 45 *=1,z*=68

即安排甲做 B 項工作，乙做 A 項工作，丙做 C 項工作，丁做 E 項工作，最 少時間為 68 分鐘。

d.該問題為人多任務少的問題，其目標函數的數學模型為： min z = 20x11 + 19x12 + 20x13 + 28x14 + 18x 21 + 24x 22 + 27x 23 + 20x 24 +26x 31 +16x 32

+15x 33 +18x 34 +17x 41 +20x 42 +24x 43 +19x 44 +16x 51 +17x 52 +20x 53 +21x 54

s.t.x11 +x12 +x13 +x14 ≤ 1，x 21 +x 22 +x 23 +x 24 ≤ 1，x 31 +x 32 +x 33 +x 34 ≤ 1，x 41 +x 42 +x 43 +x 44 ≤ 1，x 51 +x 52 +x 53 +x 54 ≤ 1，x11 +x 21 +x 31 +x 41 +x 51 =1，x12 +x 22 +x 32 +x 42 +x 52 =1，x13 +x 23 +x 33 +x 43 +x 53 =1，x14 +x 24 +x 34 +x 44 +x 54 =1，2345x ij為0-1變量，i=1，，j=1，。234

目標函數最優解為:

x11*=0,x12 *=0,x13 *=0,x14 *=0,x 21*=0,x 22 *=0,x 23 *=0,x 24 *=1,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=1,x 42 *=0,x 43 *=0,x 44 *=0,x 51*=0,x 52 *=1,x 53 *=0,x 54 *=0,z*=69 或

x11*=0,x12 *=0,x13 *=0,x14 *=0,x 21*=1,x 22 *=0,x 23 *=0,x 24 *=0,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=1,x 51*=0,x 52 *=1,x 53 *=0,x 54 *=0,z*=69 或

x11*=0,x12 *=1,x13 *=0,x14 *=0,x 21*=0,x 22 *=0,x 23 *=0,x 24 *=0,x 31*=0,x 32 *=0,x 33 *=1, x 34 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=1,x 51*=1,x 52 *=0,x 53 *=0,x 54 *=0,z*=69

即安排乙做 D 項工作，丙做 C 項工作，丁做 A 項工作，戊做 B 項工作；或 安排乙做 A 項工作，丙做 C 項工作，丁做 D 項工作，戊做 B 項工作；或安排甲 做 B 項工作，丙做 C 項工作，丁做 D 項工作，戊做 A 項工作，最少時間為 69 分鐘。

7.解：設飛機停留一小時的損失為 a 元，則停留兩小時損失為 4a 元，停留 3 小時損失為 9 元，依次類推，對 A、B、C 三個城市建立的指派問題的效率矩陣 分別如下表所示：

城市

起 到

達 飛

A

4a 361a 225a 484a 196a

9a 400a 256a 529a 225a

64a 625a 441a 16a 400a

169a 36a 4a 81a 625a

225a 64a 16a 121a 9a 106 107 108 109 110 解得最優解為：

起 到

達 飛

0 0 0 0 1

1 0 0 0 0

0 0 0 1 0

0 1 0 0 0

0 0 1 0 0 106 107 108 109 110

城市

起 到

達 飛

B

256a 225a 100a 64a 256a

529a 484a 289a 225a 529a

9a 4a 441a 361a 9a

625a 576a 361a 289a 625a

36a 25a 576a 484a 36a 101 102 103 113 114 解得最優解為：

起 到

達 飛

0 1 0 0 0

0 0 1 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1 106 107 108 109 110 或為：

起 到

達 飛

0 1 0 0 0

0 0 1 0 0

0 0 0 0 1

0 0 0 1 0

1 0 0 0 0 106 107 108 109 110

城市 C

起 到

達 飛

49a 25a 169a 64a

225a 169a 441a 256a

225a 169a 441a 256a

49a 25a 169a 64a 104 105 111 112 解得最優解為：

起 到

達 飛

0 0 1 0

1 0 0 0

0 1 0 0

0 0 0 1 104 105 111 112 或為：

起 到

達 飛

0 0 1 0

0 1 0 0

1 0 0 0

0 0 0 1 104 105 111 112 或為:

起 到

達 飛

0 0 0 1

1 0 0 0

0 1 0 0

0 0 1 0 104 105 111 112 或為：

起 到

達 飛

0 0 0 1

0 1 0 0

1 0 0 0

0 0 1 0 104 105 111 112

第 9 章 目標規劃

1.某工廠試對產品 A、B 進行生產。市場需求并不是很穩定，因此對每種產

品分別預測了在銷售良好和銷售較差時的預期利潤。這兩種產品都經過甲、乙兩 臺設備加工。已知產品 A 和 B 分別在甲和乙設備上的單位加工時間，甲、乙設備 的可用加工時間以及預期利潤如下表所示，要求首先是保證在銷售較差時，預期 利潤不少于 5 千元，其次是要求銷售良好時，預期利潤盡量達到 1 萬元。試建立 多目標規劃模型并求解。

單位加工時間 設備

產品

A 4 2 8 5

B 3 5 6 5

可用時間 45 30 100 50 甲

乙

銷售良好時的預期利潤(百元／件)

銷售較差時的預期利潤(百元／件)

1、解：設工廠生產 A 產品 x1 件，生產 B 產品 x2 件。按照生產要求，建立如下目 標規劃模型： min ?P(d1?)+ P2(d 2)1

?4 x1 + 3 x2 ≤ 45 ?

?2 x1 + 5 x2 ≤ 30

?+??5 x1 + 5 x2 ? d1 + d1 = 50 ?+8 x1 + 6 x2 ? d 2 + d 2? = 100 ?

? x1 , x2 , di+ , di? ≥ 0, i = 1, 2?

由管理運籌學軟件先求解得： x1 = 11.25, x2 = 0, d1? = 0, d 2? = 10, d1+ = 6.25, d 2 = 0

由圖解法或進一步計算可知，本題在求解結果未要求整數解的情況下，滿意解有 +無窮多個，為線段 α(135 /14,15 / 7)+(1 ? α)(45 / 4, 0), α ∈ [0,1] 上的任一點。

2、解：設食品廠商在電視上發布廣告 x1 次，在報紙上發布廣告 x2 次，在廣播中 發布廣告 x3 次。目標規劃模型為：

P(d1?)+ P2(d 2?)+ P3(d3+)+ P4(d 4)1 ? x1 ≤ 10 ? x ≤ 20 ?2

? x3 ≤ 15 ?

+??20 x1 + 10 x2 + 5 x3 ? d1 + d1 = 400 ?

?+??0.7 x1 ? 0.3x2 ? 0.3x3 ? d 2 + d 2 = 0

??0.3x ? 0.3x + 0.7 x ? d + + d ? = 012333?

?2.5 x1 + 0.5 x2 + 0.3x3 ? d 4+ + d 4? = 20

用管理運籌學軟件先求下述問題：?+?? x1 , x2 , x3 , di , d i ≥ 0, i = 1, 2,3, 4? min d1? min +? x1 ≤ 10

? x ≤ 20 ?2

? x3 ≤ 15 ?

+??20 x1 + 10 x2 + 5 x3 ? d1 + d1 = 400 ?

??0.7 x1 ? 0.3x2 ? 0.3x3 ? d 2+ + d 2 = 0 ?

??0.3x ? 0.3x + 0.7 x ? d + + d ? = 012333?

?2.5 x1 + 0.5 x2 + 0.3x3 ? d 4+ + d 4?

，將其作為約束條件求解下述問題： 得： = 20d1? = 0 ?+?? x1 , x2 , x3 , di , di ≥ 0, i = 1, 2,3, 4? min d 2? ? x1 ≤ 10

?

? x2 ≤ 20 ? x ≤ 15 ?3

?20 x1 + 10 x2 + 5 x3 ? d1+ + d1? = 400 ?

+??0.7 x1 ? 0.3x2 ? 0.3x3 ? d 2 + d 2 = 0 ?

?0.3x1 ? 0.3x2 + 0.7 x3 ? d3+ + d3? = 0 ?

?2.5 x + 0.5 x + 0.3x ? d + + d ? = 2012344? ?d1? = 0

?得最優值 d 2 = 0，將其作為約束條件計算下述問題： ?+?? x1 , x2 , x3 , di , di ≥ 0, i = 1, 2,3, 4 min d3+

? x1 ≤ 10 ? x ≤ 20 ?2

? x3 ≤ 15 ?

+??20 x1 + 10 x2 + 5 x3 ? d1 + d1 = 400

?+??0.7 x1 ? 0.3x2 ? 0.3x3 ? d 2 + d 2 = 0 ?

?0.3x1 ? 0.3x2 + 0.7 x3 ? d3+ + d3? = 0 ?

?2.5 x + 0.5 x + 0.3x ? d + + d ? = 2012344 ?

?d1? = 0 ?? ?d 2 = 0，將其作為約束條件計算下述問題： 得最優值d3+ = 0 ? x , x , x , d + , d ? ≥ 0, i = 1, 2,3, 4 min d 4+ ?1 2 3 i i

? x1 ≤ 10

?

? x2 ≤ 20 ? x ≤ 15 ?3

?20 x1 + 10 x2 + 5 x3 ? d1+ + d1? = 400 ?

+??0.7 x1 ? 0.3 x2 ? 0.3 x3 ? d 2 + d 2 = 0

?+???0.3x1 ? 0.3 x2 + 0.7 x3 ? d3 + d3 = 0 ?

2.5 x1 + 0.5 x2 + 0.3 x3 ? d 4+ + d 4? = 20 ?

?d ? = 0 ? 1?

?d 2 = 0 得： ?+

?d3 = 0

+?x1 = 9.474, x2 = 20, x3 = 2.105, d1+ = 0, ? x , x , x , d + , d ? ≥ 0, i = 1, d1? = 0, d 2 = 8.387, d 2 = 0, d3+ = 0, d3? = 7.368，2,3, 4? d 4+ = 14.316, ?1 2 3 i id 4 = 0，所以食品廠商為了依次達到 4 個活動目標，需在電視上發布廣告 9.474 次，報紙

（管理運籌學 2.0 可一次求解上述上發布廣告 20 次，廣播中發布廣告 2.105 次。問題）

（a）設該化工廠生產 x1 升粘合劑 A 和 x2 升粘合劑 B。則根據工廠要求，3、解： 建立以下目標規劃模型：

P(d1? + d 2+)+ P2(d3? + d 4)+ P3(d5?)1 5?1

x1 + x2 ? d1+ + d1? = 80 ?312 ?

? 1 x + 5 x ? d + + d ? = 10022 ? 3 1 12 2 ?

? x1 ? d3+ + d3? = 100 ?

+?? x2 ? d 4 + d 4 = 120 ??+? x1 + x2 ? d5 + d 5 = 300

? x , x , x , d + , d ? ≥ 0, i = 1, 2,3, 4,5（b）? 1 2 3 i i min ?300 d5 +

d4

200

d3

+

A

d1

+

d

2d3 d2

+

d

圖1 200

圖解法求解

300

圖解法求解如圖 1：目標 1，2 可以達到，目標 3 達不到，所以有滿意解為 A 點

。（150，120）

4、解：設該汽車裝配廠為達到目標要求生產產品 A x1 件，生產產品 B x2 件。

min

+

P(d1+ + d 2)+ P2

（a）目標規劃模型為：

(d3?)1

1?1

x1 + x2 ? d1+ + d1? = 60 ?66 ?

? 1 x + 5 x ? d + + d ? = 18022 ?3 1 6 2 ?

+??4 x1 + 3 x2 ? d3 + d3 = 1300

?+?? x1 , x2 , x3 , di , di ≥ 0, i = 1, 2,3 用圖解法求解：

500 400 300 200 100 0 d d2-+2d1-d1+

d3+

B

d3-

A

DC

200

300

400

500

600

如圖所示，所示解為區域 ABCD，有無窮多解。

（b）由上圖可知，如果不考慮目標 1 和目標 2，僅僅把它們加工時間的最大限 度分別為 60 和 180 小時作為約束條件，而以利潤最大化為目標，那么最優解為 C 點（360，0），即生產產品 A360 件，最大利潤為 1420 元。結果與（a）是不相 同的，原因是追求利潤最大化而不僅僅是要求利潤不少于 1300 元。

（c）如果設目標 3 的優先權為 P1，目標 1 和目標 2 的優先權為 P2，則由上圖可 知，滿意解的區域依然是 ABCD，有無窮多解，與（a）的解是相同的，原因是（a）和（c）所設定的目標只是優先級別不同，但都能夠依次達到。

5．在環境污染日益得到重視的今天，越來越多的企業開始注重工業廢水污

水排污。某紙張制造廠生產一般類型紙張的利潤為 300 元／噸，每噸紙產生的工 業廢水的處理費用為 30 元；生產某種特種紙張的利潤為 500 元／噸，每噸特種 紙產生的工業廢水的處理費用為 40 元。

該紙張制造廠近期目標如下：

目標 1：紙張利潤不少于 15 萬；

目標 2：工業廢水的處理費用不超過 1 萬元。

a.設目標 1 的優先權為 P1，目標 2 的優先權為 P2，P1>P2，建立目標規劃模型 并用圖解法求解。

b.若目標 2 的優先權為 P1，目標 1 的優先權為 P2，建立目標規劃模型并求解。所得的解是否與 a 中的解相同？

c.若目標 2 的罰數權重為 5，目標 1 的罰數權重為 2，建立加權目標規劃模 型求解。

5、解：設該紙張制造廠需要生產一般類型紙張 x1 噸，生產特種紙張 x2 噸。（a）、目標規劃模型為： + P2(d 2)1

?300 x1 + 500 x2 ? d1+ + d1? = 150000 ?

+??30 x1 + 40 x2 ? d 2 + d 2 = 10000 ?

x1 , x2 , di+ , di? ≥ 0, i = 1, 2 ? ?+圖解法略，求解得 x1 = 0, x2 = 300, d1? = 0, d 2 = 0, d1+ = 0, d 2 = 200(b)、目標規劃模型為： min P(d 2+)+ P2(d1?)1

?300 x1 + 500 x2 ? d1+ + d1? = 150000 ?

+??30 x1 + 40 x2 ? d 2 + d 2 = 10000

?+?? x1 , x2 , di , di ≥ 0, i = 1, 2

圖解法略，求解得 x1 = 0, x2 = 250, d1? = 250, d 2 = 0, d1+ = 0, d 2 = 0

由此可見，所得結果與(a)中的解是不相同的。(c)、加權目標規劃模型為： ?+min +P(d1?)P(5d 2 + 2d1?)1

?300 x1 + 500 x2 ? d1+ + d1? = 150000 ?

+??30 x1 + 40 x2 ? d 2 + d 2 = 10000 ?

x1 , x2 , di+ , di? ≥ 0, i = 1, 2 ?

?+求解得 x1 = 0, x2 = 300, d1? = 250, d 2 = 0, d1+ = 0, d 2 = 12000 min +

第 10 章 動態規劃

1、最優解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E

最優值：13

2、最優解：項目 A：300 萬元、項目 B：0 萬元、項目 C：100 萬元、最優值：Z=71+49+70=190 萬元

3、設每個月的產量是 Xi 百臺（i=1、2、3、4）

最優解：X1=

4、X2＝0、X3＝

4、X4＝3

即第一個月生產 4 臺，第一個月生產 0 臺，第一個月生產 4 臺，第一個月生 產 3 臺。

最優值：Z=252000 元

4、最優解：運送第一種產品 5 件

最優值：Z=500 元

5．最大利潤 2790 萬元。最優安排如下表：

年初完好設備高負荷工作設備低負荷工作設備

數數

11250125 21000100 380080 464640 532320

6．最優解（0，200，300，100）或（200，100，200，100）或者（100，100，300，100）或（200，200，0，200）。總利潤最大增長額為 134 萬。

7．在區 1 建 3 個分店，在區 2 建 2 個分店，不在區 3 建立分店。最大總利潤 22。8．最優解為：第一年繼續使用，第二年繼續使用，第三年更新，第四年繼續使 用，第五年繼續使用，總成本＝4500 元。

9．最優解為第一年購買的設備到第二、三、四年初各更新一組，用到第 5 年末，其總收入為 17 萬元。

10．最優解為第一批投產 3 臺，如果無合格品，第二批再投產 3 臺，如果仍全部 不合格，第三批投產 4 臺。總研制費用最小為 796 元。11．

月份采購量待銷數量

10200 29000 3900900 40900

最大利潤為 14000。12．

最優策略為（1,2,3）或者（2,1,3），即該廠應訂購 6 套設備，可分別分給三個廠 1,2,3 套或者 2,1,3 套。每年利潤最大為 18 萬元。

第 11 章 圖與網絡模型

習題 1

解：這是一個最短路問題，要求我們求出從 v1 到 v 7 配送的最短距離。用 Dijkstra 算法求解可得到這問題的解為 27。我們也可以用此書附帶的管理運籌學 軟件進行計算而得出最終結果為：

從節點 1 到節點 7 的最短路

************************* 起點終點距離

------------124 2312 356 575

此問題的解為:27

即：配送路線為： v1 → v 2 → v3 → v5 → v7

習題 2

解：這是一個最短路的問題，用 Dijkstra 算法求解可得到這問題的解為 4.8，即在 4 年內購買、更換及運行維修最小的總費用為：4.8 萬元。

最優更新策略為：第一年末不更新

第二年末更新

第三年末不更新

第四年末處理機器

我們也可以用此書附帶的管理運籌學軟件進行求解，結果也可以得出此問題 的解為 4.8。

習題 3

解：此題是一個求解最小生成樹的問題，根據題意可知它要求出連接 v1 到 v8 的最小生成樹。解此題可以得出結果為 18。也可以使用管理運籌學軟件，得出 如下結果：

此問題的最小生成樹如下：

*************************

起點終點距離

------------132 342 124 252 573 78 76

此問題的解為:18 3

習題 4

解：此題是一個求解最大流的問題，根據題意可知它要求出連接 v1 到 v6 的最 大流量。解此題可以得出最大流量為 22。使用管理運籌學軟件，我們也可以得 出結果為：

v1 從節點 1 到節點 6 的最大流

*************************

起點終點距離

------------126 146 1310 240 256 345 365 455 466 5611

此問題的解為:22

即從 v1 到 v6 的最大流量為：22

習題 5

解：此題是一個求解最小費用最大流的問題，根據題意可知它要求出連接 v1 到 v6 的最小費用最大流量。解此問題可以得出最大流為 5，最小費用為 39。使用 管理運籌學軟件，我們也可以得出結果如下： 從節點 1 到節點 6 的最大流 ************************* 起點終點流量費用

----------------1213 1341 2424 3211 3533 4624 5 6 3 2

此問題的最大流為:5 此問題的最小費用為:39

第 12 章 排序與統籌方法

習題 1

p1 + 5 p2 + 4 p3 + 3 p4 + 2 p5 + p1 解：各零件的平均停留時間為：6

由此公式可知，要讓停留的平均時間最短，應該讓加工時間越少的零件 排在越前面，加工時間越多的零件排在后面。所以，此題的加工順序為：3，7，6，4，1，2，5

習題 2

解：此題為兩臺機器，n 個零件模型，這種模型加工思路為：鉆床上加工時 間越短的零件越早加工，同時把在磨床上加工時間越短的零件越晚加工。根據以上思路，則加工順序為：2，3，7，5，1，6，4。

鉆床 2 1

磨床 3 1 64 8 12 16 20 24 28 32 36 40

鉆床的停工時間是：40.1。磨床的停工時間是：42.6。習題 3

解：a.工序 j 在繪制上有錯，應該加一個虛擬工序來避免 v3 和 v4 有兩個直接 相連的工序。

b.工序中出現了缺口，應在 v6 和 v7 之間加一個虛擬工序避免缺口。c.工序 v1、v2、v3 和 v4 之間存在了閉合回路。

習題 4 解：

v3

a

d

c

v4

f

v1

b

e

v5

v2

g

v6

習題 5

解：這是一個已知工序時間的關鍵路徑問題，由管理運籌學軟件可得出如下 結果：

工序安排

工序 最早開始時間

最遲開始時間

最早完成時間

最遲完成時間

時差

是否關鍵工序

-A 0 0 2 2 2---B C D E F G 0 4 4 4 9 8

0 5 4 5 10 8 9 8 7 11 12 10 8 8 12 12

0 1 0 1 1 0

YES---YES------YES

本問題關鍵路徑是：B--D--G 本工程完成時間是：12

習題 6

解：這是一個不確定工序時間的關鍵路徑問題，由管理運籌學軟件可得出如 下結果：

工序期望時間方差----------------A2.08.07 B4.17.26 C4.92.18 D4.08.18 E3.08.07 F2.17.26 G3.83.26

工序安排

工序 最早開始時間

最遲開始時間

最早完成時間

最遲完成時間 時差

是否關鍵工序--------------------A 0 0 2.08 2.08 2.08 B C D E F G 0 4.17 4.17 4.17 9.08 8.25

0 5 4.17 5.17 9.92 8.25

4.17 9.08 8.25 7.25 11.25 12.08

4.17 9.92 8.25 8.25 12.08 12.08

0.83 0 1.83 0

---YES---YES------YES

本問題關鍵路徑是：B--D--G 本工程完成時間是：12.08

這個正態分布的均值 E(T)=12.08 2 2 其方差為： σ 2 ＝ σ b ＋ σ d ＋ σ g ＝０.70 則σ ＝０.84

當以９８％的概率來保證工作如期完成時，即： φ(u)= 0.98，所以 u=2.05 此時提前開始工作的時間Ｔ滿足： 所以Ｔ＝13.8 ≈ 14

習題 7

解：最短的施工工時仍為４＋５＋６＝１５

具體的施工措施如下：

工序 最早開始時間 最遲開始時間

最早完成時間

最遲完成時間

時差

是否關鍵工序

--------------------A 0 0 1 1 B C D E F G H I J K 0 7 0 1 3 3 4 10 7 9

0 7 0 2 3 6 4 10 9 9 10 4 3 7 6 9 15 13 15 10 4 4 7 9 9 15 15 15

T ? 12.08

=2.05 0.84

0 0 0 0 1 0 3 0 0 2 0

---------YES------YES------YES

本問題關鍵路徑是：D--H--K 本工程最短完成時間是：15

經過這樣調整后，任意一時間所需要的人力數都不超過 15 人。習題 8

解：此題的網絡圖如下： v1 a

v2

c

b

v4

d

v3

設第 Vi 發生的時間為 xi，(Vi, Vj)間的工序提前完工的時間為 yij，目標函數 min f = 4.5(x4 ? x1)+ 4 y12 + y24 + 4 y23 + 2 y34

s.t.x2 ? x1 ≥ 3 ? y12

x3 ? x2 ≥ 4 ? y23 x4 ? x2 ≥ 7 ? y24 x4 ? x3 ≥ 5 ? y34 x1 = 0 y12 ≤ 2 y23 ≤ 2 y24 ≤ 4 y34 ≤ 3

xi ≥ 0, yij ≥ 0

以上 i=1，2，3，4； j=1，2，3，4

用管理運籌學軟件中的線性規劃部分求解，得到如下結果： minf=46.5

x1=0,x2=1, x3=5,x4=7, y12 = 2 y23 = 0 y24 = 1 y34 = 3

第 13 章 存貯論

1．運用經濟定購批量存貯模型，可以得到

a.經濟訂貨批量 Q* = Dc32 × 4800 × 350

=≈ 579.66 件

c140 × 25%

b.由于需要提前 5 天訂貨，因此倉庫中需要留有 5 天的余量，故再訂貨點

4800 ×

5為= 96 件

250

4800250

c.訂貨次數為≈ 8.28 次，故兩次訂貨的間隔時間為≈ 30.19 工作

579.78.28

日

1D

c3 ≈ 5796.55 元d.每年訂貨與存貯的總費用 TC = Q * c1 +

Q*2（使用管理運籌學軟件，可以得到同樣的結果。）2．運用經濟定購批量存貯模型，可以得到

a.經濟訂貨批量 Q* = Dc32 × 14400 × 1800

=≈ 1314.53 噸

c11500 × 2%

b.由于需要提前 7 天訂貨，因此倉庫中需要留有 7 天的余量，故再訂貨點

14400 × 7

為≈ 276.16 噸

365

14400365

c.訂貨次數為故兩次訂貨的間隔時間為≈ 10.95 次，≈ 33.32 天

1314.5310.95 1D

c3 ≈ 39436.02 元d.每年訂貨與存貯的總費用 TC = Q * c1 +

Q*2（使用管理運籌學軟件，可以得到同樣的結果。）3．運用經濟定購批量存貯模型，可知

a.經濟訂貨批量 Q* = Dc3

= c1

Dc3

= 8000，其中 p 為產品單價，p × 22%

變換可得 2 Dc3

= 80002 × 22%，當存貯成本率為 27％時，p

Dc3 2 Dc380002 × 22%

=≈ 7221 箱 =Q *' =

c1 '

27%p × 27% b.存貯成本率為 i 時，經濟訂貨批量 Q* =

單價，變換可得 Dc32 Dc3

，其中 p 為產品= c1p×i Dc3

= Q *2 ? i，當存貯成本率變為 i ' 時，p

Dc32 Dc3Q *2 ? i ==Q *' = c1 'p×i 'i'

4．運用經濟生產批量模型，可知

a.最優經濟生產批量 Q* =

Dc32 ×18000 × 1600

=≈ 2309.4 套

d18000

(1 ?)c1(1 ?)× 150 ×18% p30000

18000

b.每年生產次數為 ≈ 7.79 次

2309.4 250

c.兩次生產間隔時間為≈ 32.08 工作日

7.79

250 × 2309.4

d.每次生產所需時間為≈ 19.25 工作日

30000 d

e.最大存貯水平為(1 ?)Q* ≈ 923.76 套

p

1dD

c3 ≈ 24941.53 元f.生產和存貯的全年總成本為 TC =(1 ?)Q * c1 + pQ*2g.由于生產準備需要天，因此倉庫中需要留有 10 天的余量，故再訂貨

18000 × 10

點為= 720 套

250

（使用管理運籌學軟件，可以得到同樣的結果。）5．運用經濟生產批量模型，可知

a.最優經濟生產批量 Q* =

Dc32 × 30000 × 1000

=≈ 2344.04 d30000

(1 ?)c1(1 ?)×130 × 21% p50000

件

30000

b.每年生產次數為 ≈ 12.8 次

2344.04 250

c.兩次生產間隔時間為≈ 19.53 工作日

12.8 d.每次生產所需時間為

250 × 2344.04

≈ 11.72 工作日

50000

d

e.最大存貯水平為(1 ?)Q* ≈ 937.62 件

p

1dD

c3 ≈ 25596.88 元f.生產和存貯的全年總成本為 TC =(1 ?)Q * c1 + pQ*2g.由于生產準備需要天，因此倉庫中需要留有 5 天的余量，故再訂貨點

30000 × 5

為= 600 件

250

（使用管理運籌學軟件，可以得到同樣的結果。）6．運用允許缺貨的經濟定購批量模型，可以得到

a.最優訂貨批量 Q* = Dc3(c1 + c2)2 × 4800 × 350(10 + 25)

=≈ 685.86 件

c1c210 × 25

Dc3c12 × 4800 × 350 ×10

b.最大缺貨量 S * =

=≈ 195.96 件，另外由于

c2(c1 + c2)25 ×(10 + 25)

需要提前 5 天訂貨，因此倉庫中需要留有 5 天的余量，即在習題 1 中所

求出的 96 件，故再訂貨點為－195.96 + 96 = －99.96 件

4800250

c.訂貨次數為≈ 7.0 次，故兩次訂貨的間隔時間為≈ 35.7 工作日

685.867

d.每 年 訂 貨、存 貯 與 缺 貨 的 總 費 用

(Q * ? S *)2DS *2 TC =c1 +c3 +c2 ≈ 4898.98 元

2Q *2Q *Q*

e.顯然，在允許缺貨的情況下，總花費最小。因為在允許缺貨時，企業可

以利用這個寬松條件，支付一些缺貨費，少付一些存貯費和訂貨費，從

而可以在總費用上有所節省。

（使用管理運籌學軟件，可以得到同樣的結果。）

7．運用允許缺貨的經濟生產批量模型，可知 Dc3(c1 + c2)2 × 30000 × 1000(27.3 + 30)a.最 優 經 濟 生 產 批 量 Q* =

=≈

d30000

(1 ?)c1c2(1 ?)× 27.3 × 30 p50000

3239.52 件 d

300002 Dc3c1(1 ?)2 × 30000 × 27.3 ×1000 ×(1 ?)p

50000 617.37 ≈=b.最 大 件，另外由于需要缺 貨 量 S * =天來準備生產，因此要留有 5 天的余量，即 c2(c1 + c2)30 ×(27.3 + 30)

第五篇：運籌學期末試卷及答案

一、判斷題（21分）

1、可行解是基本可行解的充要條件是它的正分量所對應的A中列向量線性無關（）；

2、如果一個LP問題有最優解，則它的對偶問題也有最優解，且它們的最優解相等（）；

3、若線性規劃問題有最優解，則一定有唯一的最優解（）；

4、若一個原始線性規劃問題無界，則它的對偶問題也無界（）；

5、設f:Rn?R1在點x??Rn處的Hesse矩陣?2f(x?)存在，若?2f(x?)?0，并且?2f(x?)正定，則x?是（UMP）的嚴格局部最優解（）；

6、若f:Rn?R1是S上的凸函數，任意實數??0則?f是S上的凸函數（）；

7、設S?Rn是非空開凸集，f:Rn?R1二階連續可導，則f是S上的嚴格凸函數的充要條件是f的Hesse矩陣?2f(x)在 S上是正定的（）.二、1.將下面的線性規劃問題化成標準形（7分）

2，寫出下面線性規劃的對偶規劃（7分）

maxz?4x1?5x2?6x3

minz?x1?4x2?3x3

?2x1?3x2?4x3?10?5x?2x?8x?20?123 s.t?

?x1?2x2?5x3?9??x1,x3?0,x2無約束.?2x1?3x2?5x3?2?x?x?x?4?123 s.t??3x1?x2?6x3?1??x1?0,x3?0,x2為自由變量.三、證明題（10分）

設f:Rn?R1在點x??Rn處可微.若x?是（UMP）的局部最優解，則?f(x?)?0.四、用對偶單純形法求解下列線性規劃問題（10分）

minz?15x1?24x2?5x3 ?6x2?x3?2s.t??5x?2x?x?123?1

?xj?0,j?1,2,3

五、把線性規劃問題（18分）

minZ??2x1?x2?x3 ?x1?x2?x3?6s.t???x?2x?4 記為（P）

?12?x1,x2,x3?0求（1）用單純形算法解（p）；（2）c2由1變為(?3)； 由??6??4??變為??3???4?? ???

六、用分枝定界法解下述ILP問題（10分）

maxz?x1?x2

?2x1?x2?5s.t??4x1?x2?2 ??x1,x2?0,且為整數

七、求以下無約束非線性規劃問題的最優解（8分）

minf(xx221,2)?x1?x2?6x1?x1x2?4x2?7

八、驗證下列非線性規劃為凸規劃（9分）

minf(x)?x221?4x2?9x1?3x1x2?11 s.t??g1(x)?5x1?7x2?9?0?gx)?2x2?2x22(12?x1x2?4x2?7?0

一、判斷題（20分）

1.V;

2.X;

3.X;

4.X;

5.X ；

6.V 。

3）b

7.X（二、1.解：對自由變量x2用x4?x5代替;對第一個不等式約束添加松弛變量x6,對第二個不等式約束添加剩余變量x7,再用z??z代替原來的目標函數,便得到了標準形式的LP問題（2分）

minz??4x1?5(x4?x5)?6x3

（4分）

s.t

?2x1?3(x4?x5)?4x3?10?5x?2(x?x)?8x?x?20?14536 ?x?2(x?x)?5x?x?94537?1?xj?0,j?1,3,4,5,6,7?（8分）

2．解：這里c?(1,4,3)T,b?(?2,4,1)T,根據定義，其對偶問題是

（2分）

max(?2?1?4?2??3)

（4分）

s.t

??2?1???2?3?3?1??3??????4?123 ?5????6??323?1???1?0,?3?0,?2無約束（7分）

三、證明題（10分）

證：用反證法，若 ?f(x?)?0，現令P???f(x?)，則有

（2分）

?f(x)P???f(x)??f(x)???f(x)?0（5分）

由定理，必存在??0，使當t?(0,?)時，有

f(x??tP)?f(x?)（8分）?T???2

成立

但這與假設矛盾.因此必有

?f(x?)?0

（10分）

四、解：引進非負的剩余變量x4?0,x5?0,將不等式約束化為等式約束 ?6x2?x3?x4?2? ?5x1?2x2?x3?x5?1

?x?0,j?1,?,5j?將等式兩端同乘以（-1），就直接得到原問題一個基本（不可行）解和對偶問題的一個可行解（檢驗數向量??0）其對應的單純形標如下

1?r161r2?r13r0?4r13?r221r1?r243r0?r22zx4x5?15?24?500?0?5?6??20z?1500?5?110??2????x2?101??1x5?1116?20?3?40?811?0?????6311?1??33（6分）

15731700???22225111x2?10??444415131x301??2222（8分）z?

1117此時，b?0,故原問題的最優解為x?(0，)T，其最優值為。

422（10分）

五、解：（1）在約束條件中加入松弛變量x4,x5得

minz??2x1?x2?x3

?x1?x2?x3?x4?6? s.t??x1?2x2?x5?它的初始表

?x?1,?,5j?（2分）

z2?11000x4x51?121106????0014r2?r1rz?2r1

?1zx1x50?3?1?20?1210131111016（5分）100)其,最優值為z0??12。

此時檢驗數向量??0,故最優解為x?(6,0,T（6分）

(2)x1是非基變量?1???1?(c1?c1?)?1（8分）

zx1x50111?1?20?12111101101r231r1?r231rz?r23

zx200?4/3?7/3?1/3?46/310012/31/32/31/3?1/31/38/310/36????x1

03?（10分）,此時檢驗數向量??0,故最優解為x?(8/3,10/3,T0)其最優值為z0??46。（12分）3T(3)原問題的最優解為x?(6,0,0),所對應的可行基B=?A1?10? B?1???, ?11?

?10?A5?=??，?11????10??3??3??1???ccb???6 ? 故 b?Bb?? z?15??????01147??????（16分）

從而新問題對應的單純形表為

z x1x50?3?1?20?610131111013 7T,其0最優值為z0??6。由于b?0，故最優解為x?(3,0（18分）

六、解：用圖解法解求ILP問題的松弛問題的最優解為(,)T,最優值為z0?（2分）

它的最優解不符合整數的要求,可任選一個變量,如選擇x1?7[]?1,（4分）6786323。67進行分枝.由于6引進兩個約束x1?1和x1?2生成兩個子問題

maxz?x1?x2 maxz?x1?x2

s.t

?2x1?x2?5?4x?x?2?12??x1?1??x1,x2?0,且整數

(p1)

和

?2x1?x2?5?4x?x?2?12s.t?(p2)（6分）

x?21???x1,x2?0,且整數ILP問題(p1)的松弛LP問題的最優解x1?(1,2)T,最優值z?3。(p2)的松弛LP問題的最優解

x2?(2,1)T,最優值z?3。

（8分）

由于3?3,故ILP問題的最優解x1?(1,2)T,x2?(2,1)T,最優值z?3。

（10分）

?2x1?x2?6?

七、解：目標函數的梯度向量為 ?f(x)???，x?2x?4?12?（2分）

令?f(x)?0，求得f的駐點

x??(8/T3。

（4分）

?21?，?2f?x?的一、二階順序主子式分別為 f的Hesse矩陣為?f?x?????12?2 2?0，2112?3?0（6分）

對?x?Rn,?2f?x?為正定矩陣，因而f是Rn上的凸函數。故（8分）x??(8/3,2T/為它的整體最優解。3

八、解：

f的Hesse矩陣為

?23??2f?x?????38?，（2分）

?2f?x?的一、二階順序主子式本別為

2?0，2338?7?0，因而?2f?x?為正定矩陣，f是嚴格凸函數.（4分）

?4－1?而?g2?x?=??，它也是一個正定矩陣，因而g2?x?也是嚴格凸函數，－14??2（7分）

其它的不等是約束為線性的。由定理知，該非線性規劃是一個凸規劃。

（9分）