數(shù)據(jù)、模型與決策（原書第16版）課件 第7章、整數(shù)線性規(guī)劃

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

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

7-2伊斯特伯恩房地產(chǎn)公司投資問題伊斯特伯恩房地產(chǎn)公司用200萬美元購買新的租賃財產(chǎn)。經(jīng)過篩選，公司將投資項目鎖定為聯(lián)排別墅和公寓樓。每套聯(lián)排別墅售價282000美元，現(xiàn)有5套空置。每幢公寓樓售價400000美元，開發(fā)商可以根據(jù)伊斯特伯恩的需要數(shù)量建房。伊斯特伯恩的財產(chǎn)經(jīng)理每月有140小時用來處理這些新置的財產(chǎn)，其中，每套聯(lián)排別墅預(yù)計每月要花4小時，每幢公寓樓預(yù)計每月要花40小時?？鄢盅簝斶€和經(jīng)營成本后，年現(xiàn)金流量預(yù)計為:每套聯(lián)排別10000美元，每幢公寓樓15000美元。伊斯特伯恩的股東將需要在保證年現(xiàn)金流最大的要求下，確定購買聯(lián)排別墅和公寓樓的數(shù)量。我們先定義決策變量如下:T=購買的聯(lián)排別墅數(shù)量A=購買的公寓樓數(shù)量7-2伊斯特伯恩房地產(chǎn)：純整數(shù)線性規(guī)劃

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

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

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

RMC問題的固定成本模型

7-3固定成本：計算機(jī)求解0-1整數(shù)線性規(guī)劃問題

7-3分銷系統(tǒng)設(shè)計問題馬丁貝克公司在圣路易斯經(jīng)營一家年產(chǎn)量為30000件產(chǎn)品的工廠。產(chǎn)品被運(yùn)輸?shù)轿挥诓ㄊ款D、亞特蘭大和休斯敦的地區(qū)分銷中心。該公司的長期計劃小組對地區(qū)分銷中心的年需求量做了預(yù)測，如下表所示：最后，每件產(chǎn)品從各工廠到各分銷中心的運(yùn)費(fèi)如下表所示（單位：千美元）：7-3分銷系統(tǒng)設(shè)計：網(wǎng)絡(luò)表示（網(wǎng)絡(luò)圖）現(xiàn)在說明在該分銷系統(tǒng)設(shè)計問題中，如何應(yīng)用0-1變量建立模型來選擇最優(yōu)的廠址、確定從各工廠到各分的中心的運(yùn)輸量。我們可以用以下的0-1變量來表示建立工廠的決策：如果在底特律建立工廠，則y1=1;否則，y1=0如果在托萊多建立工廠，則y2=1;否則，y2=0如果在丹佛建立工廠，則y3=1;否則，y3=0如果在堪薩斯城建立工廠，則y4=1;否則，y4=0各工廠到每個分銷中心的運(yùn)輸量的變量和運(yùn)輸問題中的相同：xij=工廠i到分銷中心j的運(yùn)輸量其中

i=1,2,3,4,5，

j=1,2,3.7-3分銷系統(tǒng)設(shè)計：問題表達(dá)式目標(biāo)函數(shù)

約束條件

7-3分銷系統(tǒng)設(shè)計:完整的LP模型和解決方案完整的LP模型

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

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

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

n選k約束條件

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

并行約束條件

7-4關(guān)于靈敏度分析的說明

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