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

11.1解：

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

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

（2）倉庫內(nèi)有4個工人的概率即為P4??1????4??1?0.4??0.44?0.01536（3）至少有2個工人的概率為1?P0?P1?1?0.6?0.24?0.16（4）領(lǐng)工具的工人平均數(shù)Ls??????44??0.6667人

10?46（5）排隊等待領(lǐng)工具工人的平均數(shù)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個顧客排隊等待的概率，即系統(tǒng)中有大于等于4個（或大于3個）顧客的概率，為

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

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

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

（1）倉庫內(nèi)沒有人領(lǐng)工具的概率，即為P0?1??1?0.4??0.6158 N?141??1?0.4（2）工人到達(dá)必須排隊等待的概率，即為倉庫內(nèi)有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）領(lǐng)工具的工人平均數(shù)Ls??1???N?1??N?1?1??N?10.44?0.44??? 41?0.41?0.4（5）排隊等待領(lǐng)工具工人的平均數(shù)Lq???0.4?41.6???0.2667人 ???10?46（6）平均排隊時間Wq?

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

10?46

第二篇：運籌學(xué)黃皮版課后習(xí)題答案詳解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.9 試求出表3-34給出的產(chǎn)銷不平衡運輸問題的最優(yōu)解。

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

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

試問：

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

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

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

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

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

3.12 1，2，3三個城市每年需分別供應(yīng)電力320，250和350單位，由I，Ⅱ兩個電站提供，它們的最大供電量分別為400個單位和450個單位，單位費用如表3—37所示。由于需要量大于可供量，決定城市1的供應(yīng)量可減少0～30單位，城市2的供應(yīng)量不變，城市3的供應(yīng)量不能少于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最優(yōu)解是：u1??1,u2?0,u3?0,v1?1,v2?2,v3?5,v4?1

第三篇：運籌學(xué)習(xí)題解答

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

本題沒有單純形法。

5.3 沒有答案

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

第2章

1、解：

x2 6

線性規(guī)劃的圖解法

A 1 O 0 1 B

C3 6

x1

a.可行域為 OABC。

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

c.由圖可知，最優(yōu)解為 B 點，最優(yōu)解： x1 = 69。

2、解： a

x2

1215

x2 =，最優(yōu)目標(biāo)函數(shù)值：

0.6

0.1 O

0.1

0.6

x1

x1 = 0.2

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

x2 = 3

3、解：

a 標(biāo)準(zhǔn)形式：

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 標(biāo)準(zhǔn)形式：

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 標(biāo)準(zhǔn)形式：

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、解：

標(biāo)準(zhǔn)形式： 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、解：

標(biāo)準(zhǔn)形式： 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、解：

模型：

變?yōu)?? 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 即目標(biāo)函數(shù)最優(yōu)值是 103000 b 2，4 有剩余，分別是 330，15。均為松弛變量 c 50，0，200，0額外利潤 250 d 在 [0,500] 變化，最優(yōu)解不變。e 在 400 到正無窮變化，最優(yōu)解不變。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?；貓舐剩?0000

b 模型變?yōu)椋?max z = 5 x a + 4 xb

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

推導(dǎo)出： x1 = 18000 x 2 = 3000

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

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

線性規(guī)劃問題的計算機求解

目標(biāo)函數(shù)最優(yōu)值 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 到正無窮的范圍內(nèi)變化，最優(yōu)產(chǎn)品的組合不變 f 不變 因為在 [0,500] 的范圍內(nèi)

g 所謂的上限和下限值指當(dāng)約束條件的右邊值在給定范圍內(nèi)變化時，約束條

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

i能

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

2、解：

a 4000 1000062000

b 約束條件 1：總投資額增加 1 個單位，風(fēng)險系數(shù)則降低 0.057

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

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

d 當(dāng) c 2 不變時，c1 在 3.75 到正無窮的范圍內(nèi)變化，最優(yōu)解不變

當(dāng) c1 不變時，c 2 在負(fù)無窮到 6.4 的范圍內(nèi)變化，最優(yōu)解不變

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 在負(fù)無窮到 10 的范圍內(nèi)變化，其最優(yōu)解不變 c 2 不變時，c1 在 2 到正無窮的范圍內(nèi)變化，其最優(yōu)解不變 e 約束條件 1 的右邊值在 300000 到正無窮的范圍內(nèi)變化，對偶價格仍為 0.1約束條件 2 的右邊值在 0 到 1200000 的范圍內(nèi)變化，對偶價格仍為-0.06

600000 300000

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

900000 900000

4、解：

a x1 = 8.5 x 2 = 1.5x 3 = 0 x4 = 1 最優(yōu)目標(biāo)函數(shù) 18.5

對偶價格為 2 和 3.5b 約束條件 2 和 3 c 選擇約束條件 3，最優(yōu)目標(biāo)函數(shù)值 22

d 在負(fù)無窮到 5.5 的范圍內(nèi)變化，其最優(yōu)解不變，但此時最優(yōu)目標(biāo)函數(shù)值變化

e 在 0 到正無窮的范圍內(nèi)變化，其最優(yōu)解不變，但此時最優(yōu)目標(biāo)函數(shù)值變化

5、解：

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

1565

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

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

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

方案 規(guī)格 2640 1770 1651 1440 合計 剩余

方案 規(guī)格 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

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

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

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

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最優(yōu)值為 300。

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

工的人數(shù)，則可列出下面的數(shù)學(xué)模型：

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 用管理運籌學(xué)軟件我們可以求得此問題的解為：

x1＝8，x2＝0，x3＝1，x4＝1，x5＝0，x6＝4，x7＝0，x8＝6，x9＝0，x10＝0，x11＝0 最優(yōu)值為 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

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

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

C、設(shè)在 11：00-12：00 這段時間內(nèi)有 x1 個班是 4 小時，y1 個班是 3 小時； 設(shè)在 12：00-13：00 這段時間內(nèi)有 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

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

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

3、解：設(shè)生產(chǎn) A、B、C 三種產(chǎn)品的數(shù)量分別為 x1，x2，x3，則可列出下面的數(shù)學(xué)模型：

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

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

x1＝200，x2＝250，x3＝100

最優(yōu)值為 6400。

a、在資源數(shù)量及市場容量允許的條件下，生產(chǎn) A 200 件，B 250 件，C 100

件，可使生產(chǎn)獲利最多。

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

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

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

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

不能使總利潤增加。如果要開拓市場應(yīng)當(dāng)首先開拓 C 產(chǎn)品的市場，如果

要增加資源，則應(yīng)在 975 到正無窮上增加材料數(shù)量，在 800 到正無窮上

增加機器臺時數(shù)。

4、解：設(shè)白天調(diào)查的有孩子的家庭的戶數(shù)為 x11，白天調(diào)查的無孩子的家庭的戶 數(shù)為 x12，晚上調(diào)查的有孩子的家庭的戶數(shù)為 x21，晚上調(diào)查的無孩子的家庭 的戶數(shù)為 x22，則可建立下面的數(shù)學(xué)模型： 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

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

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

最優(yōu)值為 47500。

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

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

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

化。

c、調(diào)查的總戶數(shù)在 1400－無窮之間，總調(diào)查費用不會變化；

有孩子家庭的最少調(diào)查數(shù)在 0－1000 之間，總調(diào)查費用不會變化；

無孩子家庭的最少調(diào)查數(shù)在負(fù)無窮－1300 之間，總調(diào)查費用不會變化。

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

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

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

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

最優(yōu)值為 102000。

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

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

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

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

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

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

即：生產(chǎn)雛雞飼料 50 噸，不生產(chǎn)蛋雞飼料，生產(chǎn)肉雞飼料 40 噸。

7、設(shè) Xi——第 i 個月生產(chǎn)的產(chǎn)品 I 數(shù)量

Yi——第 i 個月生產(chǎn)的產(chǎn)品 II 數(shù)量

Zi，Wi 分別為第 i 個月末產(chǎn)品 I、II 庫存數(shù)

。則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 用管理運籌學(xué)軟件我們可以求得此問題的解為： 最優(yōu)值= 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、解：設(shè)第 i 個車間生產(chǎn)第 j 種型號產(chǎn)品的數(shù)量為 xij，可建立下面的數(shù)學(xué)模型：

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用管理運籌學(xué)軟件我們可以求得此問題的解為：

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

最優(yōu)值為 279400

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

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

計算結(jié)果是：

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、該線性規(guī)劃的標(biāo)準(zhǔn)型為： 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、不是。因為基本可行解要求基變量的值全部非負(fù)。

3、解：a、迭代次數(shù) 基變量 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、線性規(guī)劃模型為：

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）

對應(yīng)的目標(biāo)函數(shù)值為 0。

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

，最優(yōu)值為 9。

4、解：最優(yōu)解為（2.25，0）X2

X1

，最優(yōu)值為 84。

5、解：a、最優(yōu)解為（2，5，4），最優(yōu)值為－4。b、最優(yōu)解為（0，0，4）

6、解：a、有無界解

，最優(yōu)值為－2.144。b、最優(yōu)解為（0.714，2.143，0）

7、解：a、無可行解

，最優(yōu)值為 28。b、最優(yōu)解為（4，4）c、有無界解

，最優(yōu)值為 8。d、最優(yōu)解為（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，故當(dāng) c1=2 時最優(yōu)解不變 b.根據(jù)材料的對偶價格為 1 判斷，此做法不利 c.d.0≤b2≤45

e.最優(yōu)解不變，故不需要修改生產(chǎn)計劃

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

均為唯一最優(yōu)解，根據(jù)從計算機輸出的結(jié)果看出，如果松弛或剩余變量為零且對 應(yīng)的對偶價格也為零，或者存在取值為零的決策變量并且其相差值也為零時，可 知此線性規(guī)劃有無窮多組解。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 目標(biāo)函數(shù)最優(yōu)值為: 10

最優(yōu)解: x1=6, x2=2, x3=0

第 7 章 運輸問題

1.（1）此問題為產(chǎn)銷平衡問題

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

丙 23 30 20 350 丁 25 19 22 200 產(chǎn)量 300 400 500 1200

最優(yōu)解如下

******************************************** 起至 銷點 發(fā)點12

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

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

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

此問題的另外的解如下：

起至 銷點 發(fā)點12

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

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

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

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

最優(yōu)解如下

******************************************** 起 發(fā)點

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

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

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

19050 200

（3）銷地甲的需求提高后，也變?yōu)楫a(chǎn)銷不平衡問題

最優(yōu)解如下

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

起至 銷點 發(fā)點12

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

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

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

注釋：總需求量多出總供應(yīng)量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

最優(yōu)解如下

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

起 發(fā)點--------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

最優(yōu)解如下

********************************************起至 銷點 發(fā)點1

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

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

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

8465

此問題的另外的解如下： 起至 銷點 發(fā)點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

最優(yōu)解如下

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

起 至 銷點 發(fā)點 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

最優(yōu)解如下

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

起

至 銷點

發(fā)點

------------------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.最優(yōu)解如下

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

發(fā)點1

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

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

5

145

c.該運輸問題只有一個最優(yōu)解，因為其檢驗數(shù)均不為零

最優(yōu)解如下d.******************************************** 起至 銷點

發(fā)點12

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

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

0 5

0

產(chǎn)量 0 15 5 0

0

第 8 章 整數(shù)規(guī)劃

1． 求解下列整數(shù)規(guī)劃問題

a.max z=5x1 +8x 2

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

目標(biāo)函數(shù)最優(yōu)解為 : 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為整數(shù)。

目標(biāo)函數(shù)最優(yōu)解為 : 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為整數(shù)，x 3為0-1變量。

目標(biāo)函數(shù)最優(yōu)解為 : x1*=5,x 2 *=3,x 3 *=0,z*=62。

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

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, 且為整數(shù)，i=1，。2345

目標(biāo)函數(shù)最優(yōu)解為

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

*=2500,z*=107500.3．解：設(shè) xi 為第 i 項工程，i=1,2,3,4,5,且 xi 為 0-1 變量，并規(guī)定，?1, 當(dāng)?shù)趇項工程被選定時，xi = ?

?0，當(dāng)?shù)趇項工程沒被選定時。

根據(jù)給定條件，使三年后總收入最大的目標(biāo)函數(shù)的數(shù)學(xué)模型為： 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

目標(biāo)函數(shù)最優(yōu)解為

: x1*=1,x

*=0,z*=95

*=1,x

*=1,x

*=1,x 4．解：這是一個混合整數(shù)規(guī)劃問題

設(shè) x1、x2、x3 分別為利用 A、B、C 設(shè)備生產(chǎn)的產(chǎn)品的件數(shù)，生產(chǎn)準(zhǔn)備費

只有在利用該設(shè)備時才投入，為了說明固定費用的性質(zhì)，設(shè)

?1，當(dāng)利用第i種設(shè)備生產(chǎn)時，即x i >0, yi = ?

?0，當(dāng)不利用第i種設(shè)備生產(chǎn)時，即x i =0。故其目標(biāo)函數(shù)為：

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

為了避免沒有投入生產(chǎn)準(zhǔn)備費就使用該設(shè)備生產(chǎn)，必須加以下的約束條件，M 為充分大的數(shù)。

x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3 M，設(shè) M=1000000

a.該目標(biāo)函數(shù)的數(shù)學(xué)模型為： 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，且為整數(shù)，y1，y 2，y3為0-1變量。

目標(biāo)函數(shù)最優(yōu)解為

: x1*=370,x 2

*=231,x

*=1399,y1 =1,y

=1,z*=10647

b.該目標(biāo)函數(shù)的數(shù)學(xué)模型為：

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，且為整數(shù)，y1，y 2，y3為0-1變量。目標(biāo)函數(shù)最優(yōu)解為

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

*=1375,y1 =0,y

=1,z*=8625

=1,y3

=1,y3 c.該目標(biāo)函數(shù)的數(shù)學(xué)模型為：

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，且為整數(shù)，y1，y 2，y3為0-1變量。目標(biāo)函數(shù)最優(yōu)解為

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

*=1000,x

*=1000,y1 =0,y

=1,y3 d.該目標(biāo)函數(shù)的數(shù)學(xué)模型為：

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，且為整數(shù)，y1，y 2，y3為0-1變量。

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

?0，當(dāng)i地沒被選設(shè)庫房。該目標(biāo)函數(shù)的數(shù)學(xué)模型為： 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，且為整數(shù)，yi為0-1分量，i=1，。234 目標(biāo)函數(shù)最優(yōu)解為

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

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

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

?0，當(dāng)不指派第i人去完成第j項工作時。a.為使總消耗時間最少的目標(biāo)函數(shù)的數(shù)學(xué)模型為：

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 目標(biāo)函數(shù)最優(yōu)解為 :

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.為使總收益最大的目標(biāo)函數(shù)的數(shù)學(xué)模型為： 將 a 中的目標(biāo)函數(shù)改為求最大值即可。目標(biāo)函數(shù)最優(yōu)解為

:

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.由于工作多人少，我們假設(shè)有一個工人戊，他做各項工作的所需的時間均 為 0，該問題就變?yōu)榘才?5 個人去做 5 項不同的工作的問題了，其目標(biāo)函數(shù)的數(shù) 學(xué)模型為： 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

目標(biāo)函數(shù)最優(yōu)解為:

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.該問題為人多任務(wù)少的問題，其目標(biāo)函數(shù)的數(shù)學(xué)模型為： 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

目標(biāo)函數(shù)最優(yōu)解為:

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

城市

起 到

達(dá) 飛

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 解得最優(yōu)解為：

起 到

達(dá) 飛

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

城市

起 到

達(dá) 飛

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 解得最優(yōu)解為：

起 到

達(dá) 飛

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 或為：

起 到

達(dá) 飛

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

起 到

達(dá) 飛

49a 25a 169a 64a

225a 169a 441a 256a

225a 169a 441a 256a

49a 25a 169a 64a 104 105 111 112 解得最優(yōu)解為：

起 到

達(dá) 飛

0 0 1 0

1 0 0 0

0 1 0 0

0 0 0 1 104 105 111 112 或為：

起 到

達(dá) 飛

0 0 1 0

0 1 0 0

1 0 0 0

0 0 0 1 104 105 111 112 或為:

起 到

達(dá) 飛

0 0 0 1

1 0 0 0

0 1 0 0

0 0 1 0 104 105 111 112 或為：

起 到

達(dá) 飛

0 0 0 1

0 1 0 0

1 0 0 0

0 0 1 0 104 105 111 112

第 9 章 目標(biāo)規(guī)劃

1.某工廠試對產(chǎn)品 A、B 進(jìn)行生產(chǎn)。市場需求并不是很穩(wěn)定，因此對每種產(chǎn)

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

單位加工時間 設(shè)備

產(chǎn)品

A 4 2 8 5

B 3 5 6 5

可用時間 45 30 100 50 甲

乙

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

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

1、解：設(shè)工廠生產(chǎn) A 產(chǎn)品 x1 件，生產(chǎn) B 產(chǎn)品 x2 件。按照生產(chǎn)要求，建立如下目 標(biāo)規(guī)劃模型： 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?

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

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

2、解：設(shè)食品廠商在電視上發(fā)布廣告 x1 次，在報紙上發(fā)布廣告 x2 次，在廣播中 發(fā)布廣告 x3 次。目標(biāo)規(guī)劃模型為：

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

用管理運籌學(xué)軟件先求下述問題：?+?? 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

?得最優(yōu)值 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，將其作為約束條件計算下述問題： 得最優(yōu)值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，所以食品廠商為了依次達(dá)到 4 個活動目標(biāo)，需在電視上發(fā)布廣告 9.474 次，報紙

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

（a）設(shè)該化工廠生產(chǎn) x1 升粘合劑 A 和 x2 升粘合劑 B。則根據(jù)工廠要求，3、解： 建立以下目標(biāo)規(guī)劃模型：

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：目標(biāo) 1，2 可以達(dá)到，目標(biāo) 3 達(dá)不到，所以有滿意解為 A 點

。（150，120）

4、解：設(shè)該汽車裝配廠為達(dá)到目標(biāo)要求生產(chǎn)產(chǎn)品 A x1 件，生產(chǎn)產(chǎn)品 B x2 件。

min

+

P(d1+ + d 2)+ P2

（a）目標(biāo)規(guī)劃模型為：

(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

如圖所示，所示解為區(qū)域 ABCD，有無窮多解。

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

（c）如果設(shè)目標(biāo) 3 的優(yōu)先權(quán)為 P1，目標(biāo) 1 和目標(biāo) 2 的優(yōu)先權(quán)為 P2，則由上圖可 知，滿意解的區(qū)域依然是 ABCD，有無窮多解，與（a）的解是相同的，原因是（a）和（c）所設(shè)定的目標(biāo)只是優(yōu)先級別不同，但都能夠依次達(dá)到。

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

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

該紙張制造廠近期目標(biāo)如下：

目標(biāo) 1：紙張利潤不少于 15 萬；

目標(biāo) 2：工業(yè)廢水的處理費用不超過 1 萬元。

a.設(shè)目標(biāo) 1 的優(yōu)先權(quán)為 P1，目標(biāo) 2 的優(yōu)先權(quán)為 P2，P1>P2，建立目標(biāo)規(guī)劃模型 并用圖解法求解。

b.若目標(biāo) 2 的優(yōu)先權(quán)為 P1，目標(biāo) 1 的優(yōu)先權(quán)為 P2，建立目標(biāo)規(guī)劃模型并求解。所得的解是否與 a 中的解相同？

c.若目標(biāo) 2 的罰數(shù)權(quán)重為 5，目標(biāo) 1 的罰數(shù)權(quán)重為 2，建立加權(quán)目標(biāo)規(guī)劃模 型求解。

5、解：設(shè)該紙張制造廠需要生產(chǎn)一般類型紙張 x1 噸，生產(chǎn)特種紙張 x2 噸。（a）、目標(biāo)規(guī)劃模型為： + 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)、目標(biāo)規(guī)劃模型為： 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

由此可見，所得結(jié)果與(a)中的解是不相同的。(c)、加權(quán)目標(biāo)規(guī)劃模型為： ?+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 章 動態(tài)規(guī)劃

1、最優(yōu)解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E

最優(yōu)值：13

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

3、設(shè)每個月的產(chǎn)量是 Xi 百臺（i=1、2、3、4）

最優(yōu)解：X1=

4、X2＝0、X3＝

4、X4＝3

即第一個月生產(chǎn) 4 臺，第一個月生產(chǎn) 0 臺，第一個月生產(chǎn) 4 臺，第一個月生 產(chǎn) 3 臺。

最優(yōu)值：Z=252000 元

4、最優(yōu)解：運送第一種產(chǎn)品 5 件

最優(yōu)值：Z=500 元

5．最大利潤 2790 萬元。最優(yōu)安排如下表：

年初完好設(shè)備高負(fù)荷工作設(shè)備低負(fù)荷工作設(shè)備

數(shù)數(shù)

11250125 21000100 380080 464640 532320

6．最優(yōu)解（0，200，300，100）或（200，100，200，100）或者（100，100，300，100）或（200，200，0，200）?？偫麧欁畲笤鲩L額為 134 萬。

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

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

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

月份采購量待銷數(shù)量

10200 29000 3900900 40900

最大利潤為 14000。12．

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

第 11 章 圖與網(wǎng)絡(luò)模型

習(xí)題 1

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

從節(jié)點 1 到節(jié)點 7 的最短路

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

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

此問題的解為:27

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

習(xí)題 2

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

最優(yōu)更新策略為：第一年末不更新

第二年末更新

第三年末不更新

第四年末處理機器

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

習(xí)題 3

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

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

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

起點終點距離

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

此問題的解為:18 3

習(xí)題 4

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

v1 從節(jié)點 1 到節(jié)點 6 的最大流

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

起點終點距離

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

此問題的解為:22

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

習(xí)題 5

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

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

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

第 12 章 排序與統(tǒng)籌方法

習(xí)題 1

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

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

習(xí)題 2

解：此題為兩臺機器，n 個零件模型，這種模型加工思路為：鉆床上加工時 間越短的零件越早加工，同時把在磨床上加工時間越短的零件越晚加工。根據(jù)以上思路，則加工順序為：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。習(xí)題 3

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

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

習(xí)題 4 解：

v3

a

d

c

v4

f

v1

b

e

v5

v2

g

v6

習(xí)題 5

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

工序安排

工序 最早開始時間

最遲開始時間

最早完成時間

最遲完成時間

時差

是否關(guān)鍵工序

-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

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

習(xí)題 6

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

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

工序安排

工序 最早開始時間

最遲開始時間

最早完成時間

最遲完成時間 時差

是否關(guān)鍵工序--------------------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

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

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

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

習(xí)題 7

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

具體的施工措施如下：

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

最早完成時間

最遲完成時間

時差

是否關(guān)鍵工序

--------------------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

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

經(jīng)過這樣調(diào)整后，任意一時間所需要的人力數(shù)都不超過 15 人。習(xí)題 8

解：此題的網(wǎng)絡(luò)圖如下： v1 a

v2

c

b

v4

d

v3

設(shè)第 Vi 發(fā)生的時間為 xi，(Vi, Vj)間的工序提前完工的時間為 yij，目標(biāo)函數(shù) 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

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

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

第 13 章 存貯論

1．運用經(jīng)濟定購批量存貯模型，可以得到

a.經(jīng)濟訂貨批量 Q* = Dc32 × 4800 × 350

=≈ 579.66 件

c140 × 25%

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

4800 ×

5為= 96 件

250

4800250

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

579.78.28

日

1D

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

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

a.經(jīng)濟訂貨批量 Q* = Dc32 × 14400 × 1800

=≈ 1314.53 噸

c11500 × 2%

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

14400 × 7

為≈ 276.16 噸

365

14400365

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

1314.5310.95 1D

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

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

a.經(jīng)濟訂貨批量 Q* = Dc3

= c1

Dc3

= 8000，其中 p 為產(chǎn)品單價，p × 22%

變換可得 2 Dc3

= 80002 × 22%，當(dāng)存貯成本率為 27％時，p

Dc3 2 Dc380002 × 22%

=≈ 7221 箱 =Q *' =

c1 '

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

單價，變換可得 Dc32 Dc3

，其中 p 為產(chǎn)品= c1p×i Dc3

= Q *2 ? i，當(dāng)存貯成本率變?yōu)?i ' 時，p

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

4．運用經(jīng)濟生產(chǎn)批量模型，可知

a.最優(yōu)經(jīng)濟生產(chǎn)批量 Q* =

Dc32 ×18000 × 1600

=≈ 2309.4 套

d18000

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

18000

b.每年生產(chǎn)次數(shù)為 ≈ 7.79 次

2309.4 250

c.兩次生產(chǎn)間隔時間為≈ 32.08 工作日

7.79

250 × 2309.4

d.每次生產(chǎn)所需時間為≈ 19.25 工作日

30000 d

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

p

1dD

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

18000 × 10

點為= 720 套

250

（使用管理運籌學(xué)軟件，可以得到同樣的結(jié)果。）5．運用經(jīng)濟生產(chǎn)批量模型，可知

a.最優(yōu)經(jīng)濟生產(chǎn)批量 Q* =

Dc32 × 30000 × 1000

=≈ 2344.04 d30000

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

件

30000

b.每年生產(chǎn)次數(shù)為 ≈ 12.8 次

2344.04 250

c.兩次生產(chǎn)間隔時間為≈ 19.53 工作日

12.8 d.每次生產(chǎn)所需時間為

250 × 2344.04

≈ 11.72 工作日

50000

d

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

p

1dD

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

30000 × 5

為= 600 件

250

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

a.最優(yōu)訂貨批量 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 天的余量，即在習(xí)題 1 中所

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

4800250

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

685.867

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

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

2Q *2Q *Q*

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

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

而可以在總費用上有所節(jié)省。

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

7．運用允許缺貨的經(jīng)濟生產(chǎn)批量模型，可知 Dc3(c1 + c2)2 × 30000 × 1000(27.3 + 30)a.最 優(yōu) 經(jīng) 濟 生 產(chǎn) 批 量 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 * =天來準(zhǔn)備生產(chǎn)，因此要留有 5 天的余量，即 c2(c1 + c2)30 ×(27.3 + 30)

第五篇：運籌學(xué)期末試卷及答案

一、判斷題（21分）

1、可行解是基本可行解的充要條件是它的正分量所對應(yīng)的A中列向量線性無關(guān)（）；

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

3、若線性規(guī)劃問題有最優(yōu)解，則一定有唯一的最優(yōu)解（）；

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

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

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

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

2，寫出下面線性規(guī)劃的對偶規(guī)劃（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分）

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

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

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

五、把線性規(guī)劃問題（18分）

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

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

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

maxz?x1?x2

?2x1?x2?5s.t??4x1?x2?2 ??x1,x2?0,且為整數(shù)

七、求以下無約束非線性規(guī)劃問題的最優(yōu)解（8分）

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

八、驗證下列非線性規(guī)劃為凸規(guī)劃（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代替原來的目標(biāo)函數(shù),便得到了標(biāo)準(zhǔn)形式的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,根據(jù)定義，其對偶問題是

（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，現(xiàn)令P???f(x?)，則有

（2分）

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

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

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

成立

但這與假設(shè)矛盾.因此必有

?f(x?)?0

（10分）

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

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

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,故原問題的最優(yōu)解為x?(0，)T，其最優(yōu)值為。

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)其,最優(yōu)值為z0??12。

此時檢驗數(shù)向量??0,故最優(yōu)解為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分）,此時檢驗數(shù)向量??0,故最優(yōu)解為x?(8/3,10/3,T0)其最優(yōu)值為z0??46。（12分）3T(3)原問題的最優(yōu)解為x?(6,0,0),所對應(yīng)的可行基B=?A1?10? B?1???, ?11?

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

從而新問題對應(yīng)的單純形表為

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

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

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

maxz?x1?x2 maxz?x1?x2

s.t

?2x1?x2?5?4x?x?2?12??x1?1??x1,x2?0,且整數(shù)

(p1)

和

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

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

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

（8分）

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

（10分）

?2x1?x2?6?

七、解：目標(biāo)函數(shù)的梯度向量為 ?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上的凸函數(shù)。故（8分）x??(8/3,2T/為它的整體最優(yōu)解。3

八、解：

f的Hesse矩陣為

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

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

2?0，2338?7?0，因而?2f?x?為正定矩陣，f是嚴(yán)格凸函數(shù).（4分）

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

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

（9分）