AnIntroductiontoManagementScience,16e第七章、整數線性規劃章節內容7.1 整數線性規劃的分類7.2 純整數線性規劃的圖解法與計算機求解7.3 含有0-1變量的整數線性規劃的應用7.4 0-1整數變量在建模過程中的靈活性分析章節目標(1/2)完成本章后，你將能夠:LO7.1 識別一般、0-1(二進制)整數和混合整數線性模型LO7.2 用圖解法求解一個含2個整數變量的問題LO7.3 求解包含整數變量的模型的LP松弛問題LO7.4 用計算機軟件建立并求解一個一般整數線性規劃LO7.5 用計算機軟件建立并求解0-1(二進制)整數線性規劃章節目標(2/2)LO7.6 用計算機軟件建立并求解一個混合整數線性規劃LO7.7 用計算機軟件建立并求解涉及0-1(二進制)整數變量的問題，以處理特殊情況，如多項選擇、n選k約束條件和條件約束LO7.8 利用計算機軟件對整數線性規劃進行靈敏度分析介紹整數線性規劃問題可以被構建成線性規劃模型，并且其中至少有一個變量是整數。本章將對整數線性規劃的應用做詳細介紹。

首先，我們將討論整數線性規劃的不同分類。隨后，我們將介紹整數線性規劃的公式解法、圖解法以及計算機求解。在7.3節中，我們將討論5個使用0-1變量的整數線性規劃的應用實例:資金預算問題、固定成本問題、分布系統設計問題、銀行選址問題和市場份額最優化問題。在7.4節中，我們將再舉一個例子來說明使用0-1變量給規劃帶來的巨大靈活性和便利性。整數規劃提供建模靈活性的代價是:這種含有整數變量的問題通常比較難以求解。7-1整數線性規劃的分類

7-2伊斯特伯恩房地產公司投資問題伊斯特伯恩房地產公司用200萬美元購買新的租賃財產。經過篩選，公司將投資項目鎖定為聯排別墅和公寓樓。每套聯排別墅售價282000美元，現有5套空置。每幢公寓樓售價400000美元，開發商可以根據伊斯特伯恩的需要數量建房。伊斯特伯恩的財產經理每月有140小時用來處理這些新置的財產，其中，每套聯排別墅預計每月要花4小時，每幢公寓樓預計每月要花40小時。扣除抵押償還和經營成本后，年現金流量預計為:每套聯排別10000美元，每幢公寓樓15000美元。伊斯特伯恩的股東將需要在保證年現金流最大的要求下，確定購買聯排別墅和公寓樓的數量。我們先定義決策變量如下:T=購買的聯排別墅數量A=購買的公寓樓數量7-2伊斯特伯恩房地產：純整數線性規劃

7-2伊斯特伯恩房地產：LP松弛的圖解法現在我們去掉T和A為整數的條件，先來求解伊斯特伯恩房地產的LP松弛問題。運用第2章中的圖解步驟，右圖即為最優的線性規劃解法：T=2.479套聯排別墅，A=3.252幢公寓樓。目標函數的最優值為73.574。也就是說，每年的現金流量是73.574美元。但是，不幸的是，伊斯特伯恩無法購買零星數量的聯排別墅和公寓樓，所以需要進行進一步分析。7-2伊斯特伯恩房地產：近似整數解的獲得在許多情況下，可以使用舍入的方法來獲得可接受的整數解。然而，舍入并不是一個萬能的方法。假設我們把LP松弛的解舍入為T=2、A=3，目標函數值為10x2+15x3=65。而65000美元的年現金流比LP松弛的結果73574美元少很多。對其他近似方法的研究表明:整數結果T=3、A=3不可行，因為這樣資金就超過了伊斯特伯恩房地產擁有的2000000美元。同理，T=2、A=4也不可行。T=2，A=3T=3，A=3T=2，A=47-2伊斯特伯恩房地產：純整數問題的圖解法

7-2伊斯特伯恩房地產：計算機求解純整數問題在含有最大化問題的整數線性規劃中，LP松弛后的最優解的值就是最優整數解的值的上限。在含有最小化問題的整數線性規劃中，LP松弛后的最優解的值就是最優整數解的值的下限。伊斯特伯恩房地產問題的最優整數解的值為70000美元，LP松弛后的最優解的值為73574美元。于是，我們就知道了目標函數值的上限為73574美元。計算機解決方案中該松弛變量的值表明:還有72000美元的資金閑置，經理仍有44小時的空閑時間，還有1幢聯排別墅未賣出。7-3資金預算問題整數線性規劃在構建模型上的靈活性很大程度上是由于使用了0-1變量。愛斯柯德冰箱公司正在考慮隨后4年內對幾個資金要求各不相同的項目的投資方案。面對每年有限的資金，管理者需要選擇最好的方案。每個項目的凈現值、資金需求和4年內的可用資金如下表所示。7-3資金預算：問題表達式決策變量和目標函數4個0-1決策變量如下：如果工廠擴建項目通過，P=1;如果否決，P=0。如果倉庫擴建項目通過，W=1;如果否決，W=0。如果機器更新項目通過，M=1;如果否決，M=0。如果新產品研發項目通過，R=1;如果否決，R=0。在資金預算問題中，公司的目標函數是使資金預算方案的凈現值最大化。0-1整數線性規劃

7-3資金預算：計算機求解0-1整數線性規劃問題最優解是:P=1，W=1，M=1,R=0，此時凈現值為140000美元。因此，該公司將投資于工廠擴建、倉庫擴建和機器更新。如果沒有額外的資金可用，新產品研發項目只能暫緩了。松弛變量的值表明該公司在第1年有5000美元的剩余，第2年有15000美元的剩余，第4年有11000美元的剩余。但是，該公司必須在第1年和第3年各提供10000美元的額外資金投資于新產品研發項目。7-3固定成本問題在許多應用中，產品的生產成本由兩部分構成:其一為生產準備成本，即固定成本;其二為變動成本，直接與產量相關。我們可以將RMC問題視為固定成本問題的例子。3種原料用來生產3種產品:燃料添加劑、溶劑和地板清潔劑。生產每噸燃料添加劑的利潤是40美元，生產每噸溶劑的利潤是30美元，生產每噸地板清潔劑的利潤是50美元。生產每噸燃料添加劑需要0.4噸原料1和0.6噸原料3;生產每噸溶劑需要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。已知生產準備成本和3種產品的最高產量如下:7-3固定成本：問題表達式決策變量和相關成本

RMC問題的固定成本模型

7-3固定成本：計算機求解0-1整數線性規劃問題

7-3分銷系統設計問題馬丁貝克公司在圣路易斯經營一家年產量為30000件產品的工廠。產品被運輸到位于波士頓、亞特蘭大和休斯敦的地區分銷中心。該公司的長期計劃小組對地區分銷中心的年需求量做了預測，如下表所示：最后，每件產品從各工廠到各分銷中心的運費如下表所示（單位：千美元）：7-3分銷系統設計：網絡表示（網絡圖）現在說明在該分銷系統設計問題中，如何應用0-1變量建立模型來選擇最優的廠址、確定從各工廠到各分的中心的運輸量。我們可以用以下的0-1變量來表示建立工廠的決策：如果在底特律建立工廠，則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.7-3分銷系統設計：問題表達式目標函數

約束條件

7-3分銷系統設計:完整的LP模型和解決方案完整的LP模型

解決方案與解釋最優解說明要在堪薩斯城建立一個工廠，從堪薩斯城到亞特蘭大運輸20000件產品，從堪薩斯城到休斯敦運輸20000件產品，從圣路易斯到波士頓運輸30000件產品)。注意，包括堪薩斯城工廠的固定成本500000美元在內，該解所得到的總成本為860000美元。…7-3俄亥俄州信托銀行選址問題俄亥俄州信托公司的長期計劃部正考慮在俄亥俄州東北部20個縣（右圖所示）的地區開展業務。俄亥俄州信托公司目前在這20個縣沒有主營業處（PPB）。根據亥州相關法律，如果一個銀行在任一縣建立一個主營業處，即可在該縣及所有毗鄰縣建立分行。計劃的第一步，俄亥俄州信托公司需要確定在這20個縣開展業務所需的最少主營業處數量。此選址問題可用一個0-1整數規劃模型來求解。7-3銀行選址：問題表達式

7-3銀行選址：完整的LP模型和解決方案

7-40-1整數變量在建模過程中的靈活性分析多重選擇性約束條件

n選k約束條件

7-4條件約束和并行約束條件條件約束

并行約束條件

7-4關于靈敏度分析的說明

本章小結本章介紹了線性規劃的一個很重要的擴展，即整數線性規劃。本章所研究的整數線性規劃和前幾章研究的線性規劃問題的唯一區別在于其中的一個或者幾個變量局限于取整數值。如果所有變量全部取整數，我們就得到純整數線性規劃；如果變量不全部取整數，則得到混合整數線性規劃；多數整數線性規劃軟件都含有0-1或二進制規劃的求解方案。研究整數線性規劃的兩個最重