1、第第7章章整數線性規劃整數線性規劃 本章，我們將討論這樣一類問題，這類問題可本章，我們將討論這樣一類問題，這類問題可 以被構建成線性規劃的模型，并且其中至少有一以被構建成線性規劃的模型，并且其中至少有一 個變量是整數。這類問題稱作整數線性規劃問題。個變量是整數。這類問題稱作整數線性規劃問題。 如果在這類問題中，既有整數變量，又有非整數如果在這類問題中，既有整數變量，又有非整數 變量，則我們將其稱為混合整數線性規劃。在應用變量，則我們將其稱為混合整數線性規劃。在應用 整數線性規劃時，經常要求變量等于整數線性規劃時，經常要求變量等于0或或1，這，這 些變量稱為些變量稱為0 - 1變量或二進制變量。

2、如果所有變量變量或二進制變量。如果所有變量 均為均為0 1變量，我們稱此類問題為變量，我們稱此類問題為0 1整數整數 線性規劃。線性規劃。 整數變量（特別是整數變量（特別是0 - 1變量）可以使建模變得變量）可以使建模變得 十分容易、靈活，從而使得線性規劃的應用得十分容易、靈活，從而使得線性規劃的應用得 到了廣泛的普及。例如，專欄到了廣泛的普及。例如，專欄8-1介紹了新西蘭航介紹了新西蘭航 空公司如何使用空公司如何使用0 1整數規劃來有效安排分配該整數規劃來有效安排分配該 公司的員工。專欄公司的員工。專欄8-2中介紹了金屬谷容器公司（中介紹了金屬谷容器公司（ vmc）如何通過混合整數規劃來安排

3、公司的啤）如何通過混合整數規劃來安排公司的啤 酒鋁質易拉罐的生產以及貝爾卡公司開發的混合整酒鋁質易拉罐的生產以及貝爾卡公司開發的混合整 數規劃模型是如何通過使用批量訂貨進而獲得折數規劃模型是如何通過使用批量訂貨進而獲得折 扣的方法替客戶節省開支的。在本章讀者還將看到扣的方法替客戶節省開支的。在本章讀者還將看到 整數規劃的其他一些應用的范例。整數規劃的其他一些應用的范例。 本章的主要內容就是對整數線性規劃的應用本章的主要內容就是對整數線性規劃的應用 做詳細介紹。首先，我們將討論整數線性規劃的做詳細介紹。首先，我們將討論整數線性規劃的 不同分類。隨后，我們將介紹整數線性的公式解不同分類。隨后，我們

4、將介紹整數線性的公式解 法、圖解法以及計算機解法。在第法、圖解法以及計算機解法。在第8.3節中，我節中，我 們將討論們將討論5個使用個使用0 1變量的整數線性規劃的應用變量的整數線性規劃的應用 實例：資金預算問題、固定成本問題、分布系實例：資金預算問題、固定成本問題、分布系 統設計問題、銀行選址問題和市場份額最優化問統設計問題、銀行選址問題和市場份額最優化問 題。在第題。在第8.4節中，我們將再舉一個例子來說明使節中，我們將再舉一個例子來說明使 用用0 1變量給規劃帶來的巨大靈活性和便利性。變量給規劃帶來的巨大靈活性和便利性。 本章的附錄將舉例說明如何使用本章的附錄將舉例說明如何使用excel

5、電子表格來電子表格來 求解整數規劃問題。求解整數規劃問題。 整數規劃提供建模靈活性的代價是：這種含整數規劃提供建模靈活性的代價是：這種含 有整數變量的問題通常比較難以求解。一盒含有有整數變量的問題通常比較難以求解。一盒含有 上千個連續變量的線性規劃問題，可以使用任何上千個連續變量的線性規劃問題，可以使用任何 一種商業線性規劃的解法進行求解。但是一個僅一種商業線性規劃的解法進行求解。但是一個僅 含有少于含有少于100個全整數變量的線性規劃問題卻極難個全整數變量的線性規劃問題卻極難 解決。經驗豐富的管理科學家能夠分辨出哪些整解決。經驗豐富的管理科學家能夠分辨出哪些整 數線性規劃時容易求解的或者至少

6、是合適去求解數線性規劃時容易求解的或者至少是合適去求解 的。商用計算機軟件包，例如的。商用計算機軟件包，例如lingo，cplex ，xpress-mp和和premium solver的商業版本都有的商業版本都有 強大的整數規劃功能，并且整數規劃的非常健全強大的整數規劃功能，并且整數規劃的非常健全 的開放資源軟件包也是容易得到的。的開放資源軟件包也是容易得到的。“管理科學管理科學 家家”和電子表格軟件，例如和電子表格軟件，例如excel，可以用來處理，可以用來處理 小型整數線性規劃。小型整數線性規劃。 7.1 整數線性規劃的分類整數線性規劃的分類 本章所研究的線性規劃問題和前幾章研究的問本章所

7、研究的線性規劃問題和前幾章研究的問 題的唯一區別是：在線性規劃問題中，至少有一個題的唯一區別是：在線性規劃問題中，至少有一個 變量是整數型的。如果所有變量均為整數就稱其變量是整數型的。如果所有變量均為整數就稱其 為全整數線性規劃。下面通過構建一個含有為全整數線性規劃。下面通過構建一個含有2個整數個整數 變量的全整型線性規劃模型來說明：變量的全整型線性規劃模型來說明： max 2x1+3x2 s. t 3x1+3x212 x1+x24 1x1+2 x26 x1，x20，且為整數，且為整數 請注意，如果去掉此模型中的請注意，如果去掉此模型中的“整數整數”一詞一詞 ，我們將得到我們所熟悉的雙變量線性

8、規劃。去，我們將得到我們所熟悉的雙變量線性規劃。去 掉整數要求后得到的線性規稱做整數線性規的掉整數要求后得到的線性規稱做整數線性規的lp 松弛。松弛。 如果只有一些變量是整數而非全部都是，則如果只有一些變量是整數而非全部都是，則 稱做混合整數線性規劃。下面是一個有兩個變量稱做混合整數線性規劃。下面是一個有兩個變量 的混合整數線性規劃。的混合整數線性規劃。 max 3x1+4x2 s.t -1x1+2x28 1x1+2x212 2x1+1x216 x1，x2o，且，且x2為整數為整數 去掉去掉“x2為整數為整數”這個條件后，我們得這個條件后，我們得 到此混臺整數線性規劃的到此混臺整數線性規劃的l

9、p松弛。松弛。 在某些應用軟件中，整數變量只取在某些應用軟件中，整數變量只取0或或1 。這類規劃被稱做。這類規劃被稱做0一一1整數線性規劃。讀者整數線性規劃。讀者 可以在本章的后面部分中發現，使用可以在本章的后面部分中發現，使用0一一1變變 量可以使線性規劃很靈活、很容易求解。專量可以使線性規劃很靈活、很容易求解。專 欄欄7-2描述了如何用一個含有描述了如何用一個含有0一一1變量的混變量的混 合整數線性規劃確定啤酒易拉罐的生產進度合整數線性規劃確定啤酒易拉罐的生產進度 。生產線的換線用。生產線的換線用0一一l變量來表示，而產量變量來表示，而產量 則用連續變量來表示。則用連續變量來表示。 7.2

10、全整數線性規劃的圖解法與計算機解法 伊斯特伯恩房地產公司有伊斯特伯恩房地產公司有200萬美元可用于購買萬美元可用于購買 新的相賃財產。經過篩選公司已將投資項目的方新的相賃財產。經過篩選公司已將投資項目的方 案減少為連體別墅和公寓樓。每套連體別墅售價案減少為連體別墅和公寓樓。每套連體別墅售價 282000美元，現有美元，現有5套空置。每幢公寓樓售價套空置。每幢公寓樓售價400 000 美元，而且開發商可以根據伊斯特伯恩的需要數量美元，而且開發商可以根據伊斯特伯恩的需要數量 建房。建房。 伊斯特伯恩的財產經理每月可以有伊斯特伯恩的財產經理每月可以有140小時用來小時用來 處理這些新置的財產，其中，

11、每套連體別墅預計每處理這些新置的財產，其中，每套連體別墅預計每 月要花月要花4小時，每幢公寓樓預計每月小時，每幢公寓樓預計每月40小時。扣除抵小時。扣除抵 押償還和經營成本后，年現金流量預計為：每套連押償還和經營成本后，年現金流量預計為：每套連 體別墅體別墅10 000美元：每幢公寓幢美元：每幢公寓幢15000美元。伊斯特美元。伊斯特 伯恩的股東想知道往保證年現金流量最大的要求下伯恩的股東想知道往保證年現金流量最大的要求下 購買連體別墅和公寓樓的數量。購買連體別墅和公寓樓的數量。 我們先定義決策變量如下：我們先定義決策變量如下： t一連體別墅的數量；一連體別墅的數量； a公寓樓的數量。公寓樓的

12、數量。 現金流量現金流量(單位：單位：1000美元美元)的目標函數的目標函數 為：為： max 10t+l5a 必須滿足的必須滿足的3個約束條件是：個約束條件是： 282t+400a2 000 可用資金可用資金(單位：單位：1 000美元美元) 4t+40a 140 管理者的時間管理者的時間(小時小時) t 5 可得連體別墅可得連體別墅 變量變量t和和a必須是非負的。而且，必須是非負的。而且， 連體別墅和連體別墅和(或或)公寓樓均不可以拆公寓樓均不可以拆 開購買。因此，開購買。因此，t和和a一定是整數一定是整數 型的。伊斯特伯恩房地產問題的型的。伊斯特伯恩房地產問題的 模型即為如下全整數線性規

13、劃：模型即為如下全整數線性規劃： max 10t+15a s.t 282t+400a 2 000 4t +40a140 t 5 t，a0且為整且為整 數數 7.2.1 lp松弛的圖解法松弛的圖解法 現在我們去掉現在我們去掉t和和a為整數的條件，為整數的條件， 重新來求解伊斯特伯恩公司的重新來求解伊斯特伯恩公司的lp松弛問松弛問 題。運用第題。運用第2章中的圖解步驟圖章中的圖解步驟圖7-1即即 為最優的線性規劃解法，即為最優的線性規劃解法，即t=2.479套聯套聯 體別墅，體別墅，a=3.252幢公寓樓。目標函數的幢公寓樓。目標函數的 最優值為最優值為73.574。也就是說每年的現金。也就是說每

14、年的現金 流量是流量是73 574美元。但是，不幸的是，美元。但是，不幸的是， 伊斯特伯恩無法購買零星數量的連體別伊斯特伯恩無法購買零星數量的連體別 墅和公高樓。所以需要進行進一步分析墅和公高樓。所以需要進行進一步分析 。 2465 2 4 6 o s a 可行域可行域 管理者時間約束管理者時間約束 圖7-11 3 5 可得資金約束可得資金約束 可得連體別墅約束可得連體別墅約束 31 7.2.2近似整數解的獲得近似整數解的獲得 大多數情況下，可以通過使用本節的大多數情況下，可以通過使用本節的 方法來求得可接受的整數解。例如，某關方法來求得可接受的整數解。例如，某關 于生產進度問題求得的線性規劃

15、結果可能于生產進度問題求得的線性規劃結果可能 要求生產要求生產15132.4箱谷類食品。其近似結果箱谷類食品。其近似結果 為為15132箱，而該近似解對目標函數的值箱，而該近似解對目標函數的值 及其結果的可行性只產生極小的影響。因及其結果的可行性只產生極小的影響。因 此，近似是一個較好的方法。實際上，只此，近似是一個較好的方法。實際上，只 要近似對目標函數的約束條件只產生極小要近似對目標函數的約束條件只產生極小 的影響大多數管理者都可以接受。此時的影響大多數管理者都可以接受。此時 一個最優近似解就夠了。一個最優近似解就夠了。 然而，近似并不是一個萬能的方法。然而，近似并不是一個萬能的方法。 當

16、決第變量取很小的數值就對目標函數的當決第變量取很小的數值就對目標函數的 值和結果的可行性產生較大影響時就需值和結果的可行性產生較大影響時就需 要個最優的整數解。讓我們回到伊斯特伯要個最優的整數解。讓我們回到伊斯特伯 恩公司的問題中來，重新檢驗一下近似解恩公司的問題中來，重新檢驗一下近似解 。伊斯特伯恩房地產問題。伊斯特伯恩房地產問題ip松弛后的最優松弛后的最優 結果是，結果是，t=2.479套連體別墅，套連體別墅，a=3.252幢幢 公寓樓。由于每套連體別墅售價公寓樓。由于每套連體別墅售價282 000美美 元，每幢公寓樓售價元，每幢公寓樓售價400 000美元，如果近美元，如果近 似得到一個

17、整數解，將會對這個問題產生似得到一個整數解，將會對這個問題產生 重大經濟影響。重大經濟影響。 假設我們把假設我們把lp松弛的解近似到整數：松弛的解近似到整數：t=2， a=3。于是目標函數值為：。于是目標函數值為：l02+153=65。而。而 65 000美元的年現金流量比美元的年現金流量比lp松弛的結果松弛的結果73 754 美元少很多。那么有沒有其他可能的近似解呢？美元少很多。那么有沒有其他可能的近似解呢？ 對其他近似方法的研究表明：整數結果對其他近似方法的研究表明：整數結果t=3， a=3不可行，因為這樣資金就超過了伊斯特伯恩不可行，因為這樣資金就超過了伊斯特伯恩 公司現有的公司現有的2

18、 000 000美元；同理，美元；同理，t=2，a=4也也 不可行。在這樣的情況下，近似得到此問題的最不可行。在這樣的情況下，近似得到此問題的最 可行的整數結果：可行的整數結果：2套連體別墅套連體別墅3幢公寓樓和幢公寓樓和65 000美元的年現金流量。但是，我們并不知道這美元的年現金流量。但是，我們并不知道這 一結果是否為該問題的最優整數結果。一結果是否為該問題的最優整數結果。 近似到整數解是一個反復試驗的方法近似到整數解是一個反復試驗的方法 。每一個近似解都必須經過可行性檢查和。每一個近似解都必須經過可行性檢查和 對目標函數值影響的檢查。即使當近似解對目標函數值影響的檢查。即使當近似解 是可

19、行時，我們也無法保證我們找到了最是可行時，我們也無法保證我們找到了最 優的整數解。稍后我們就會發現近似解優的整數解。稍后我們就會發現近似解 (t=2,a=3)不是以上問題的最優解。不是以上問題的最優解。 7.2.3全整數問題的圖解法全整數問題的圖解法 圖圖70說明了用圖解法求解伊斯特伯恩說明了用圖解法求解伊斯特伯恩 房地產整數線性規劃問題中所需要做的變房地產整數線性規劃問題中所需要做的變 化。化。 2465 2 4 6 o s a 可行域可行域 管理者時間約束管理者時間約束 圖7-2 1 3 5 可得資金約束可得資金約束 可得連體別墅約束可得連體別墅約束 31 最優整數解最優整數解t=4,a=

20、2 首先首先 可行域圖幾乎和可行域圖幾乎和lp松弛問題的一樣松弛問題的一樣 。然后因為最優解一定是整散型的，我們用。然后因為最優解一定是整散型的，我們用 點標出可行的整數解。最后，不是將目標函數點標出可行的整數解。最后，不是將目標函數 線向可行域的極值點移動，而是盡量將它朝著線向可行域的極值點移動，而是盡量將它朝著 使目標函數最優的方向移動使目標函數最優的方向移動(可行整數點之一可行整數點之一) 。參看圖。參看圖7-2，我們看到當，我們看到當t=4套連體別墅，套連體別墅， a=3幢公寓樓時，得到最優整數值。目標函數幢公寓樓時，得到最優整數值。目標函數 值為值為104+152=70并得年現金流量

21、是并得年現金流量是70 000美元。這一結果要比近似得到的最優解美元。這一結果要比近似得到的最優解 t=2，a=3，年現金流量，年現金流量65 000美元好得多。美元好得多。 所以我們可以看到近似法并不是伊斯特伯恩公所以我們可以看到近似法并不是伊斯特伯恩公 司房地產問題的最好的求解方法。司房地產問題的最好的求解方法。 7.2.4應用應用lp松弛法建立約束邊界松弛法建立約束邊界 從伊斯特伯恩房地產問題的研究中我們從伊斯特伯恩房地產問題的研究中我們 可以得出一個結論：一定要處理好最優整數解可以得出一個結論：一定要處理好最優整數解 的值和的值和lp松弛后的最優解的值之間的關系。松弛后的最優解的值之間

22、的關系。 在含有最大化問題的整數線性規劃中，在含有最大化問題的整數線性規劃中， lp松弛后的最優解的值就是最優整數解的值松弛后的最優解的值就是最優整數解的值 的上限。在含有最小化問題的整數線性規劃中的上限。在含有最小化問題的整數線性規劃中 ，lp松弛后的最優解的值就是最優整數解的松弛后的最優解的值就是最優整數解的 值的下限。值的下限。 這一結論適用于伊斯特伯恩房地產問題。這一結論適用于伊斯特伯恩房地產問題。 最優整數解的值為最優整數解的值為70 000美元，美元，lp松弛后的最松弛后的最 優解的值為優解的值為73 574美元。于是，我們知道目標美元。于是，我們知道目標 函數值的上限為函數值的上

23、限為73 574美元。美元。 通過通過lp松弛的上下限特性，我們松弛的上下限特性，我們 可以得出結論：如果可以得出結論：如果lp松弛的解恰好是松弛的解恰好是 整數，那么，它也是該整數線性規劃的整數，那么，它也是該整數線性規劃的 最優解。這一上下限的特性也可以用來最優解。這一上下限的特性也可以用來 確定近似解是否確定近似解是否“足夠好足夠好”。如果一個。如果一個 近似的近似的lp松弛解是可行的井能使得到松弛解是可行的井能使得到 的目標函數值同的目標函數值同lp松弛的目標函數值幾松弛的目標函數值幾 乎一樣好，我們就認為該近似解是最優乎一樣好，我們就認為該近似解是最優 近似整數解。因此，我們也可以不

24、用整近似整數解。因此，我們也可以不用整 數線性規劃來求解問題數線性規劃來求解問題 7.2.5計算機解法計算機解法 正如前面所講，有很多商用軟件能夠求解整數正如前面所講，有很多商用軟件能夠求解整數 線性規劃問題。一般來說這些軟件可以求解那些線性規劃問題。一般來說這些軟件可以求解那些 含有上百個整數變量的問題，還有一些可以求解含含有上百個整數變量的問題，還有一些可以求解含 有幾千個整數變量的特殊結構的問題有幾千個整數變量的特殊結構的問題 管理科學家軟件可用來解決本章中的絕大多數管理科學家軟件可用來解決本章中的絕大多數 整數線性規劃問題若用管理科學家軟件來解決伊整數線性規劃問題若用管理科學家軟件來解

25、決伊 斯特伯思房地產問題輸入數據的工作表與一般的線斯特伯思房地產問題輸入數據的工作表與一般的線 性規劃一樣性規劃一樣(見附錄見附錄2a)。然后，在完成了計算機求。然后，在完成了計算機求 解的框架后，用戶必須指出哪些變量是整數型的。解的框架后，用戶必須指出哪些變量是整數型的。 如圖如圖73將將t和和a定義為整數型得出了最優整定義為整數型得出了最優整 數解。當數解。當t=4套連體別墅、套連體別墅、a=2幢公寓樓時所得幢公寓樓時所得 到的解的最大年現金流量為到的解的最大年現金流量為70 000美元。該松弛變美元。該松弛變 量的值表明：還有量的值表明：還有72 000美元的資金閑置，管理者美元的資金閑

26、置，管理者 仍有仍有44小時的空閑時間，有小時的空閑時間，有l幢連體別墅未賣出。幢連體別墅未賣出。 objective function value = 14.000 variable value - - t 4.000 a 2.000 constraint slack/surplus 1 72.000 2 44.000 3 1.000 圖7-3 7.3含有含有01變量的整數線性規劃的應用變量的整數線性規劃的應用 整數線性規在構建模型上的靈活性很大程整數線性規在構建模型上的靈活性很大程 度上是由于使用了度上是由于使用了0-1變量。在很多應用中，變量。在很多應用中， 如果采取相應行動，則變量值取

27、如果采取相應行動，則變量值取1，否則取，否則取0。 0-l變量因此而提供著選擇的功能。本節所講變量因此而提供著選擇的功能。本節所講 的資金預算、固定成本核算、分布系統設計、的資金預算、固定成本核算、分布系統設計、 銀行選址、產品設計和市場份額的應用問題都銀行選址、產品設計和市場份額的應用問題都 用到用到0-l變量。變量。 7.3.1資金預算資金預算 愛斯柯德冰箱公司正在考慮隨后愛斯柯德冰箱公司正在考慮隨后4年內年內 的投資方案，這方案有著不同的資金要求。的投資方案，這方案有著不同的資金要求。 而對每年有限的資金，管理者需要選擇最好而對每年有限的資金，管理者需要選擇最好 的方案。每種方案的估計凈

28、現值、資金需求的方案。每種方案的估計凈現值、資金需求 和和4年內的可用資金見表年內的可用資金見表7-l。 表表7-1 愛斯柯德冰箱公司的估計凈現值、資金需求愛斯柯德冰箱公司的估計凈現值、資金需求 和和4年內的可用資金年內的可用資金 （單位：美元）（單位：美元） 項項 目目 工廠擴建工廠擴建 倉庫擴倉庫擴 建建 機器更新機器更新新產品研發新產品研發 凈現值凈現值 第第1年資金需求年資金需求 第第2年資金需求年資金需求 第第3年資金需求年資金需求 第第4年資金需求年資金需求 90 000 15 000 20 000 20 000 15 000 40 000 10 000 15 000 20 000

29、 5 000 10 000 10 000 4 000 37 000 15 000 10 000 10 000 10 000 可用資金總額可用資金總額 40 000 50 000 40 000 35 000 4個個0-1決策變量如下：決策變量如下： 如果工廠擴建方案通過，如果工廠擴建方案通過，p=1；如果否；如果否 決，決，p取取0。 如果倉庫擴建方案通過，如果倉庫擴建方案通過，w=1：如果否：如果否 決決, w取取0。 如果機器更新方案通過，如果機器更新方案通過，m=1；如果否；如果否 決，決，m取取0。 如果新產品研發方案通過，如果新產品研發方案通過，r=1；如果；如果 否決，否決，r取取0

30、。 在資金預算問題中，公司的目標函數是在資金預算問題中，公司的目標函數是 使資金預算的掙現值最大化。此問題有使資金預算的掙現值最大化。此問題有4個個 約束條件其一為約束條件其一為4年中每年的可用資金。年中每年的可用資金。 該該0-1整數線性規劃模型整數線性規劃模型(單位：單位：l 000 美元美元)如下：如下： max 90p+40w+l0m+37r s.t. 15p+10w+10m+15r40第第1年的可用資金年的可用資金 20p+15w +10r50第第2年的可用資金年的可用資金 20p+20w +10r40第第3年的可用資金年的可用資金 15p +5w +4m+10r35第第4年的可用資

31、金年的可用資金 p，w，m，r=0，1 圖圖7-4為管理科學家軟件的整數規劃解為管理科學家軟件的整數規劃解 。最優解是：。最優解是：p=1w=l，m=l，r=0，此時，此時 凈現值為凈現值為140 000美元。因此，該公司將投美元。因此，該公司將投 資于工廠擴建，倉庫擴建和機器更新。如果資于工廠擴建，倉庫擴建和機器更新。如果 沒有額外的資金可用，研發新產品方案只能沒有額外的資金可用，研發新產品方案只能 暫緩了暫緩了-。松弛變量的值。松弛變量的值(見圖見圖74)表明該公表明該公 司在第司在第1年有年有5 000美元的剩余，第美元的剩余，第2年有年有15 000美元的剩余，第美元的剩余，第4年有年

32、有11 000美元剩余。美元剩余。 對照研發新產品力案的資金需求，可知在第對照研發新產品力案的資金需求，可知在第 2年和第年和第4年又有足夠的資金可用于此方案。年又有足夠的資金可用于此方案。 但是，該公司必須在第但是，該公司必須在第1年和第年和第3年各提供年各提供10 000美元的額外資金投資于新產品研發方案美元的額外資金投資于新產品研發方案 。 objective function value = 140.000 variable value - - p 1.000 w 1.000 m 1.000 r 0.000 constraint slack/surplus - - 1 5.000 2

33、15.000 3 0.000 4 11.000 圖7-4 愛斯柯德冰箱公司問題的管理科學家軟件解決方案愛斯柯德冰箱公司問題的管理科學家軟件解決方案 7.3.2 固定成本核算固定成本核算 在許多應用中，產品的成本由兩部分構在許多應用中，產品的成本由兩部分構 成：其一為配置成本；其二為可變成本，直成：其一為配置成本；其二為可變成本，直 接與產量相關。接與產量相關。0-1變量的應用，使得在生變量的應用，使得在生 產應用軟件包中考慮配置成本成為可能。產應用軟件包中考慮配置成本成為可能。 我們可以將我們可以將rmc問題視為固定成本問題的問題視為固定成本問題的 例子。例子。3種原料用來生產種原料用來生產3

34、種產品；一種燃料種產品；一種燃料 添加劑、一種溶劑、一種地板清潔劑。使用添加劑、一種溶劑、一種地板清潔劑。使用 以下決策變量：以下決策變量： f-生產的燃料添加劑的噸數；生產的燃料添加劑的噸數； s-生產的溶劑的噸數；生產的溶劑的噸數； c-生產的地板清潔劑的噸數。生產的地板清潔劑的噸數。 生產每噸燃料添加劑的利潤是生產每噸燃料添加劑的利潤是40美元，美元， 生產每頓溶劑的利潤是生產每頓溶劑的利潤是30美元，生產每噸地美元，生產每噸地 板清潔劑的利潤是板清潔劑的利潤是50美元。生產每噸燃料添美元。生產每噸燃料添 加劑需要加劑需要0.4噸原料噸原料1和和0.6噸原料噸原料3；生產每；生產每 噸溶

35、劑需要噸溶劑需要0.5噸原料噸原料1、0.2噸原料噸原料2和和0.3噸噸 原料原料3；生產每噸地板清潔劑需要；生產每噸地板清潔劑需要0.6噸原料噸原料 1、0.1噸原料噸原料2和和0.3噸原料噸原料3。rmc共有共有20 噸原料噸原料1、5噸原料噸原料2和和21噸原料噸原料3。我們需要。我們需要 決定下一計劃期內的最優生產量。決定下一計劃期內的最優生產量。 rmc問題的一個線性規劃模型如下：問題的一個線性規劃模型如下： max 40f+30s+50c s.t. 0.4f+0.5s+0.6c20 原料原料1 0.2s+0.1c5 原料原料2 0.6f+0.3s+0.3c21 原料原料3 f, s

36、, c 0 運用管理科學家軟件的規劃模型，我們得到運用管理科學家軟件的規劃模型，我們得到 一個最優解；一個最優解；27.5噸燃料添加劑、噸燃料添加劑、0噸溶劑噸溶劑 和和15噸地板清潔劑，總價值為噸地板清潔劑，總價值為1 850美元，美元， 見圖見圖7-5。 objective function value = 1850.00 variable value reduced costs - - - f f 27.500 27.500 0.000 0.000 s s 0.000 0.000 12.500 12.500 c c 15.000 15.000 0.000 0.000 rmc問題的這一線性

37、規劃問題并不問題的這一線性規劃問題并不 包含這些產品的配置成本。假設已知配包含這些產品的配置成本。假設已知配 置成本和置成本和3種產品的最高生產量如下：種產品的最高生產量如下： 產品分類產品分類 配置成本（美元）配置成本（美元） 最大生產量（噸）最大生產量（噸） 燃料添加劑燃料添加劑 200200 50 50 溶劑溶劑 50 2550 25 地板清潔劑地板清潔劑 400 40 400 40 我們現在可以利用我們現在可以利用0-1變量帶來的建模靈活性，變量帶來的建模靈活性， 把固定的配置成本加入到生產模型中。把固定的配置成本加入到生產模型中。0-1變量定義變量定義 如下：如下： 如果生產燃料添加

38、劑，則如果生產燃料添加劑，則sf=1,否則，否則，sf=0； 如果生產溶劑，則如果生產溶劑，則ss=1,否則，否則，ss=0； 如果生產地板清潔劑，則如果生產地板清潔劑，則sc=1，否則，否則，sc=0。 利用這些變量，總的配置成本為：利用這些變量，總的配置成本為： 200sf +50ss + 400sc 現在我們可以重新寫出包括配置成本的目標函數。于現在我們可以重新寫出包括配置成本的目標函數。于 是，凈利潤目標函數變為：是，凈利潤目標函數變為： max 40f +30s + 50c - 200sf -50ss -400sc 接下來，我們需要寫出生產能力的約束條件接下來，我們需要寫出生產能力的

39、約束條件 ，使得：當配置變量等于，使得：當配置變量等于0時，不允許生產相應的時，不允許生產相應的 產品；當配置變量等于產品；當配置變量等于1時，可以大量生產該產品時，可以大量生產該產品 。對于燃料添加劑，我們加入如下條件：。對于燃料添加劑，我們加入如下條件： f50sf 注意，在此條件下：注意，在此條件下：sf=0時，不生產燃料添時，不生產燃料添 加劑；加劑；sf=1時，燃料添加劑可最多生產時，燃料添加劑可最多生產50噸。我噸。我 們可以把配置變量看成一個開關。當它關著，就們可以把配置變量看成一個開關。當它關著，就 不允許生產；當它開著才允許生產。不允許生產；當它開著才允許生產。 利用利用0-

40、1變量，為溶劑和地板清潔劑增加類似的生變量，為溶劑和地板清潔劑增加類似的生 產能力約束條件，如下：產能力約束條件，如下： s25ss c40sc 把所有的變量移到約束條件的左邊，得到把所有的變量移到約束條件的左邊，得到 rmc問題的固定成本模型：問題的固定成本模型： max 40f +30s +50c - 200sf -50ss -400sc s.t. 0.4f + 0.5s + 0.6c 20 原料原料 1 0.2s + 0.1c 5 原料原料2 0.6f + 0.3s + 0.3c 21 原料原料3 f -50sf 0 f的最大值的最大值 s -25ss 0 s的最大值的最大值 c -40

41、sc 0 c的最大值的最大值 f, s, c0；sf,ss,sc=0,1 我們用管理科學家軟件求解含有配置我們用管理科學家軟件求解含有配置 成本的成本的rmc問題。如圖問題。如圖7-6所示，最優解所示，最優解 為為25噸燃料添加劑和噸燃料添加劑和20噸溶劑。扣除配置噸溶劑。扣除配置 成本后的目標函數值為成本后的目標函數值為1 350美元。燃料添美元。燃料添 加劑和溶劑的配置成本為加劑和溶劑的配置成本為200美元美元 +50美元美元 =250美元。最優解的結果為美元。最優解的結果為sc=0，表示應，表示應 取消昂貴的取消昂貴的400美元的地板清潔劑配置成美元的地板清潔劑配置成 本，因此不應生產地

42、板清潔劑。本，因此不應生產地板清潔劑。 構建一個固定成本模型的關鍵是各個構建一個固定成本模型的關鍵是各個 固定成本固定成本0-1變量的引入，以及相應的生產變量的引入，以及相應的生產 變量上下限的設置。對于一個產量為變量上下限的設置。對于一個產量為x的的 產品，限制條件產品，限制條件xmy的作用為，當配置的作用為，當配置 變量變量y=0時不允許生產，而在時不允許生產，而在y=1時允許生時允許生 產。最大生產量產。最大生產量m的值需要足夠大，以滿的值需要足夠大，以滿 足所有正常生產的水平。但是，研究顯示足所有正常生產的水平。但是，研究顯示 ，選擇過大的變量，選擇過大的變量m值會降低求解問題的值會降

43、低求解問題的 速度。速度。 objective function value =140.000 variable value - - f f 25.000 25.000 s s 20.000 20.000 c c 0.000 0.000 sf sf 1.000 1.000 ss ss 1.000 1.000 sc sc 0.000 0.000 圖圖7-6 使用管理科學家軟件對使用管理科學家軟件對rmc問題的求解問題的求解 7.3.3分布系統設計分布系統設計 馬丁貝克公司在圣路易斯經營一家年產量馬丁貝克公司在圣路易斯經營一家年產量 為為30 000建產品的工廠。產品被運輸到位于波建產品的工廠。產

44、品被運輸到位于波 士頓、亞特蘭大和休斯敦的地區分銷中心。由士頓、亞特蘭大和休斯敦的地區分銷中心。由 于預期將有需要的增長，馬丁貝克公司計劃在于預期將有需要的增長，馬丁貝克公司計劃在 底特律、托萊多、丹佛和堪薩斯城中的一個或底特律、托萊多、丹佛和堪薩斯城中的一個或 多個城市建立新工廠以增加生產力。在上述多個城市建立新工廠以增加生產力。在上述4 個城市中建立工廠的年固定成本和年生產能力個城市中建立工廠的年固定成本和年生產能力 如下表。如下表。 目標工廠目標工廠 年固定成本（美元）年固定成本（美元） 年生產能力（件）年生產能力（件） 底特律底特律 175 000 10 000 托萊多托萊多 300

45、000 20 000 丹佛丹佛 375 000 30 000 堪薩斯城堪薩斯城 500 000 40 000 該公司的長期計劃小組對該公司的長期計劃小組對3個地區分個地區分 銷中心的年需求量做出了如下表所示的預銷中心的年需求量做出了如下表所示的預 測。測。 分銷中心分銷中心 年需求量（件）年需求量（件） 波士頓波士頓 30 000 亞特蘭大亞特蘭大 20 000 休斯敦休斯敦 20 000 每件產品從各工廠到各分銷中心的運營每件產品從各工廠到各分銷中心的運營 見表見表7-2。 圖圖7-7描述了馬丁貝殼公司可能描述了馬丁貝殼公司可能 的分銷系統網絡圖，其中包含了每一個可能的分銷系統網絡圖，其中包

46、含了每一個可能 的工廠地點、生產能力和需求量，均以的工廠地點、生產能力和需求量，均以1 000 單位。這一網絡演示圖針對的是圣路易斯一單位。這一網絡演示圖針對的是圣路易斯一 個工廠和個工廠和4個擬議工廠的選址的運輸問題。個擬議工廠的選址的運輸問題。 但是，將建立一個或哪些工廠，還未最后決但是，將建立一個或哪些工廠，還未最后決 定。定。 現在說明在該分布系統設計問題中，如現在說明在該分布系統設計問題中，如 何應用何應用0-1變量建立模型來選擇最優的廠址、變量建立模型來選擇最優的廠址、 確定從各工廠到分銷中心的運輸量。我們可確定從各工廠到分銷中心的運輸量。我們可 以用以下的以用以下的0-1變量來表

47、示建立工廠的決策。變量來表示建立工廠的決策。 工廠地點工廠地點 分銷中心分銷中心 波士頓波士頓 亞特蘭大亞特蘭大 休斯敦休斯敦 底特律底特律 托萊多托萊多 丹佛丹佛 堪薩斯城堪薩斯城 圣路易斯圣路易斯 5 2 3 4 3 4 9 7 5 10 4 2 8 4 3 表表7-2 馬丁貝克分布系統的單位運輸成本馬丁貝克分布系統的單位運輸成本 1 底特律底特律 2 托萊多托萊多 3 丹佛丹佛 1 波士頓波士頓 2 亞特蘭大亞特蘭大 3 休斯頓休斯頓 4 堪薩斯城堪薩斯城 工廠工廠 分銷中心分銷中心 單位運輸成本單位運輸成本 10 20 30 30 20 20 1500圖圖7-7 3 2 5 4 7 9

48、 3 5 4 5 圣路易斯圣路易斯 30 40 3 4 10 8 4 2 如果在底特律建廠，如果在底特律建廠，y1=1,否則，否則，y1=0； 如果在托萊多建廠，如果在托萊多建廠，y2=1,否則，否則，y2=0； 如果在丹佛建廠，如果在丹佛建廠，y3=1,否則，否則，y3=0； 如果在堪薩斯城建廠，如果在堪薩斯城建廠，y4=1,否則，否則，y4=0； 對各工廠到每個各中心的運輸量變量的定對各工廠到每個各中心的運輸量變量的定 義和運輸問題中的相同。義和運輸問題中的相同。 xij工廠工廠i到分銷中心到分銷中心j的運輸量。的運輸量。 其中，其中，i=1，2，3，4，5且且j=1，2，3。 利用表利用

49、表7-2中的運輸數據，年運輸成本（單位：中的運輸數據，年運輸成本（單位：1 000美元）為美元）為: 5x11 +2x12 +3x13 +4x21 +3x22 +4x23 +9x31 +7x32 +5x33 +10 x41 +4x42 +2x43 +8x51 +4x52 +3x53 經營新工廠的年固定成本（單位：經營新工廠的年固定成本（單位：1 000美元）為：美元）為： 175y1 +300y 2+375y 3+500y4 注意，根據注意，根據0-1變量的定義，只有當建立某個工廠變量的定義，只有當建立某個工廠 （如（如yi=1）時，才計算經營該新工廠的固定成本；）時，才計算經營該新工廠的固定

50、成本； 而如果沒有建立該工廠（即而如果沒有建立該工廠（即yi=0），則相應的年固），則相應的年固 定成本為定成本為0。 馬丁貝克公司的目標函數為：年運輸成本與經馬丁貝克公司的目標函數為：年運輸成本與經 營新建立的工廠的年固定成本之和最小化。營新建立的工廠的年固定成本之和最小化。 現在我們考慮一下現在我們考慮一下4個擬議工廠的生產能力約個擬議工廠的生產能力約 束條件。以底特律為例，可以得出如下約束條件：束條件。以底特律為例，可以得出如下約束條件： x11 +x12 +x1310y1 如果底特律的工廠建立了，即如果底特律的工廠建立了，即y1=1，那么從，那么從 底特律運到底特律運到3個分銷中心的總

51、量必須小于或等于底個分銷中心的總量必須小于或等于底 特律的生產能力，即特律的生產能力，即10 000件。如果底特律的工廠件。如果底特律的工廠 沒有建立，即沒有建立，即y1=0，則意味著底特律的生產能力，則意味著底特律的生產能力 為為0.這樣，相應得出自底特律的運輸量均等于這樣，相應得出自底特律的運輸量均等于0。 把所有的變量都置于約束條件的左邊，得到如下所把所有的變量都置于約束條件的左邊，得到如下所 示的底特律生產能力約束條件：示的底特律生產能力約束條件： x11 +x12 +x13-10y10 底特律的生產能力底特律的生產能力 以類似的方式，可以求出托萊多工廠的生產能力約以類似的方式，可以求

52、出托萊多工廠的生產能力約 束條件如下：束條件如下： x21 +x22 +x23 -20y20 托萊多的生產能力托萊多的生產能力 丹佛和堪薩斯域的也是完全類似的。考慮到圣路易丹佛和堪薩斯域的也是完全類似的。考慮到圣路易 斯易經已經存在工廠，我們把其定義為斯易經已經存在工廠，我們把其定義為0-1變量。其變量。其 生產能力約束條件可寫為：生產能力約束條件可寫為： x51 +x52 +x5330 圣路易斯工廠的生產能力圣路易斯工廠的生產能力 還需要為還需要為3個分銷中心的需求量各自設定一個約束個分銷中心的需求量各自設定一個約束 條件，波士頓分銷中心的需求量（單位：條件，波士頓分銷中心的需求量（單位：1

53、 000件）件） 的約束條件可寫為：的約束條件可寫為： x11 +x21 +x31 +x41 +x51 =30 波士頓的需求波士頓的需求 亞特蘭大和休斯敦分銷中心的是相同的。亞特蘭大和休斯敦分銷中心的是相同的。 于是，我們得到了馬丁貝克公司的分布系統設計于是，我們得到了馬丁貝克公司的分布系統設計 問題的完整模型：問題的完整模型： min 5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32 +5x33+10 x41+4x42+2x43+8x51+4x52+3x53+175y1+ 300y2+375y3+500y4 s.t. x11+x12+x13 -10y1 0 底特

54、律的生產能力底特律的生產能力 x21+x22+x23 -20y2 0 托萊多的生產能力托萊多的生產能力 x31+x32+x33 -30y3 0 丹佛的生產能力丹佛的生產能力 x41+x42+x43 -40y4 0 堪薩斯城的生產能力堪薩斯城的生產能力 x51+x52+x53 30 圣路易斯的生產能力圣路易斯的生產能力 x11+x21+x31+x41+x51 =30 波士頓的需求波士頓的需求 x12+x22+x32+x42+x52 =20 亞特蘭大的需求亞特蘭大的需求 x13+x23+x33+x43+x53 =20 休斯敦的需求休斯敦的需求 對所有的對所有的i,j,有有xij0；y1 ，y2，y

55、3，y4=0，1。 利用管理科學家軟件的整數線性規劃利用管理科學家軟件的整數線性規劃 模型，我們得出如圖模型，我們得出如圖7-8所示的結果。最優所示的結果。最優 解說明要在堪薩斯城建立一個工廠（解說明要在堪薩斯城建立一個工廠（y4=1 ）；從堪薩斯城到亞特蘭大運輸）；從堪薩斯城到亞特蘭大運輸20 000件件 產品（產品（x42=20）；從堪薩斯城到休斯敦運）；從堪薩斯城到休斯敦運 輸輸20 000件產品（件產品（x43=20）；從圣路易斯）；從圣路易斯 到波士頓運輸到波士頓運輸30 000件產品（件產品（x51=30）。）。 注意，包括堪薩斯城工廠的固定成本注意，包括堪薩斯城工廠的固定成本50

56、0 000美元在內，該解所得到的總成本為美元在內，該解所得到的總成本為860 000美元。美元。 optimal solution objective function value = 860.000 variable value - - x11 0.000 x12 0.000 x13 0.000 x21 0.000 x22 0.000 x23 0.000 x31 0.000 x32 0.000 x33 0.000 x41 0.000 x42 20.000 x43 20.000 x51 30.000 x52 0.000 x53 0.000 y1 0.000 y2 0.000 y3 0.000

57、y4 1.000 constraint slack/surplus - - 1 0.000 2 0.000 3 0.000 4 0.000 5 0.000 6 0.000 7 0.000 8 0.000 圖圖78 上述基本模型可以進行擴展，從而可以適用上述基本模型可以進行擴展，從而可以適用 于含有工廠與倉庫、工廠與零售店面之間的直接于含有工廠與倉庫、工廠與零售店面之間的直接 運輸和多種產品的分布系統。利用運輸和多種產品的分布系統。利用0-1變量的特變量的特 殊性質，該模型還可以進行擴展，從而可以為廠殊性質，該模型還可以進行擴展，從而可以為廠 址配置問題增加多個約束條件。例如，假設在其址配置問題

58、增加多個約束條件。例如，假設在其 他問題中，選址他問題中，選址1為達拉斯，而選址為達拉斯，而選址2為沃斯堡，為沃斯堡， 因為這兩個城市相距太近，公司也許不希望同時因為這兩個城市相距太近，公司也許不希望同時 在這兩地建廠。為避免此情況發生，模型中可加在這兩地建廠。為避免此情況發生，模型中可加 入下面約束條件：入下面約束條件： y1 + y 2 1 在上述約束條件下，在上述約束條件下， y1 與與y 2 中最多只有中最多只有 一個可能等于一個可能等于1。而如果把約束條件寫成等式，。而如果把約束條件寫成等式， 就使得必須在達拉斯與沃斯堡中選擇一個。就使得必須在達拉斯與沃斯堡中選擇一個。 7.3.4

59、銀行選址銀行選址 俄亥俄州信托公司的長期計劃部正考慮在俄俄亥俄州信托公司的長期計劃部正考慮在俄 亥俄東北部亥俄東北部20個郡的地區開展業務（見圖個郡的地區開展業務（見圖7-9） 。俄亥俄州信托公司目前在這。俄亥俄州信托公司目前在這20個郡沒有一個主個郡沒有一個主 營業處。根據該州相關法律，如果一個銀行在任營業處。根據該州相關法律，如果一個銀行在任 一郡建立一個主營業處，即可在該郡及所有毗鄰一郡建立一個主營業處，即可在該郡及所有毗鄰 郡建立分行。但是，為了建立一個主營處，俄亥郡建立分行。但是，為了建立一個主營處，俄亥 俄州信托公司必須獲得本州銀行管理者的批準，俄州信托公司必須獲得本州銀行管理者的

60、批準， 或者購買一家當地現存的銀行。或者購買一家當地現存的銀行。 表表7-3列出了這一地區的列出了這一地區的20個郡及其鄰郡。個郡及其鄰郡。 例如，阿什特比拉與萊克、吉奧特、特蘭博爾毗例如，阿什特比拉與萊克、吉奧特、特蘭博爾毗 鄰；萊克郡與阿什特比拉、凱霍加、吉奧特毗鄰鄰；萊克郡與阿什特比拉、凱霍加、吉奧特毗鄰 ；等等。；等等。 考慮的部考慮的部臨近的郡臨近的郡(圖圖7-9中的數字代號中的數字代號) 1阿什特比拉阿什特比拉2,12,16 2萊克萊克1,3,12 3凱霍啦凱霍啦2,4,9,10,12,13 4格雷恩格雷恩3,5,7,9 5休倫休倫4,6,7 6里奇蘭里奇蘭5,7,17 7阿什蘭阿