第6章 整數(shù)規(guī)劃教材

第6章整數(shù)規(guī)劃6.1整數(shù)規(guī)劃問題及其數(shù)學(xué)模型6.1.1問題的提出6.1.2整數(shù)規(guī)劃的圖解法6.1.3整數(shù)規(guī)劃的幾個(gè)典型問題及其模型6.2整數(shù)規(guī)劃的一般解法6.4指派問題及其解法6.1整數(shù)規(guī)劃問題及其數(shù)學(xué)模型6.1.1問題的提出【案例】某廠在一計(jì)劃期內(nèi)擬生產(chǎn)甲、乙兩種大型設(shè)備。該廠有足夠的生產(chǎn)能力來加工制造這兩種設(shè)備的全部零部件，所需原材料和能源也可滿足供應(yīng)，不過有A、B兩種緊缺物資的供應(yīng)量受到嚴(yán)格控制，相關(guān)數(shù)據(jù)見下表。設(shè)備原料單臺(tái)設(shè)備所需原料數(shù)量可供應(yīng)量甲乙A（噸）219B（千克）5735單臺(tái)利潤（萬元）65問：該廠在本計(jì)劃期內(nèi)應(yīng)安排生產(chǎn)甲、乙設(shè)備各多少臺(tái)，才能使利潤達(dá)到最大？建立該問題的模型如下：解：設(shè)該廠在本計(jì)劃期內(nèi)應(yīng)分別安排生產(chǎn)甲、乙兩種大型設(shè)備x1,x2臺(tái)決策變量目標(biāo)函數(shù)約束條件（函數(shù)約束）線性規(guī)劃整數(shù)規(guī)劃共同點(diǎn)和區(qū)別？【結(jié)論1】類似于（4）稱為整數(shù)性約束！——仍屬于約束條件有無整數(shù)性約束，是線性規(guī)劃和整數(shù)規(guī)劃的唯一區(qū)別

！前面所建立的LP模型最后的最優(yōu)解有時(shí)候正好是整數(shù)解，剩下的小數(shù)解（或分?jǐn)?shù)解）在以前也能解釋通，因?yàn)槲覀兘⒌哪Ｐ投际沁B續(xù)型的。[例1]每千克蛋糕由0.26千克甲原料和0.74千克乙原料配制而成[例2]機(jī)械加工行業(yè)長期性生產(chǎn)的標(biāo)準(zhǔn)件A的日產(chǎn)量為108.3件，這就意味著有一件產(chǎn)品當(dāng)天只能完成30%的進(jìn)度，其余70%的加工任務(wù)在下一個(gè)工作日內(nèi)完成整數(shù)規(guī)劃整數(shù)規(guī)劃（IntegerProgramming，IP）是近40年來發(fā)展起來的規(guī)劃論的一個(gè)分支，它要求決策變量取整數(shù)值。整數(shù)規(guī)劃的分類——1）整數(shù)線性規(guī)劃（ILP）和整數(shù)非線性規(guī)劃（INLP）2）純整數(shù)規(guī)劃（PureIP）、全整數(shù)規(guī)劃（AllIP）、混合整數(shù)規(guī)劃（MixedIP）3）0-1規(guī)劃一般把去掉一個(gè)規(guī)劃問題中的若干約束而得到的另一個(gè)規(guī)劃問題稱為原規(guī)劃問題的松弛問題。IP問題的LP解【概念】IP問題的松弛問題的最優(yōu)解。原IP問題的最優(yōu)解？經(jīng)驗(yàn)嘗試四舍五入法！此時(shí)，x1=3,x2=3，不滿足函數(shù)約束（2），即通過四舍五入法得到的解為非可行解。取整法！此時(shí)，x1=3,x2=2，滿足所有函數(shù)約束，屬于可行解，對(duì)應(yīng)的目標(biāo)函數(shù)值為28，即安排生產(chǎn)甲設(shè)備3臺(tái)，乙設(shè)備2臺(tái)，可獲利潤28萬元。若令x1=4,x2=1呢？29萬元＞28萬元令x1=0，則x2=0,1,2,3,4,5maxz=25令x1=1，則x2=0,1,2,3,4maxz=26令x1=2，則x2=0,1,2,3maxz=27令x1=3，則x2=0,1,2maxz=28令x1=4，則x2=0,1maxz=29當(dāng)x1=4，x2=1時(shí)目標(biāo)函數(shù)取得最大值，即X*=(4,1)Tz*=29即在本計(jì)劃期內(nèi)安排生產(chǎn)甲設(shè)備4臺(tái)，乙設(shè)備1臺(tái)，可獲得最大利潤，且該利潤為29萬元?！窘Y(jié)論2】四舍五入也好，取整也罷，都不適用于IP問題最優(yōu)解的求解。有效途徑：1）枚舉法2）圖解法3）分支定界法4）割平面法整數(shù)線性規(guī)劃整數(shù)規(guī)劃與我們前面所講的線性規(guī)劃有哪些區(qū)別？整數(shù)規(guī)劃的分類？松弛問題、IP問題的LP解的概念。P1936-1（2）整數(shù)規(guī)劃的0-1規(guī)劃在生活中有哪些具體應(yīng)用？【ILP與一般LP比較具有下述特點(diǎn)】其可行域?yàn)檎麛?shù)點(diǎn)集。整數(shù)規(guī)劃問題的可行域僅是其松弛問題的可行域中的整數(shù)點(diǎn)集，相鄰整數(shù)點(diǎn)之間的區(qū)域不是可行域。目標(biāo)函數(shù)的優(yōu)劣。整數(shù)規(guī)劃的最優(yōu)值不優(yōu)于與之相對(duì)應(yīng)的線性規(guī)劃的最優(yōu)值。用枚舉法、舍入取整法求解一般不可行。6.1.2整數(shù)規(guī)劃的圖解法A適用條件只含有2個(gè)決策變量；可行的整數(shù)解個(gè)數(shù)相對(duì)較少；B解題步驟在對(duì)應(yīng)松弛問題的可行域內(nèi)標(biāo)出所有整數(shù)可行解對(duì)應(yīng)的點(diǎn)；畫出目標(biāo)函數(shù)等值線及其法線方向，按LP問題的圖解法求出松弛問題的最優(yōu)解；觀察，讓求出的最優(yōu)點(diǎn)朝域內(nèi)移動(dòng)，首次碰到的那個(gè)點(diǎn)就是IP問題的最優(yōu)整數(shù)解。5x1+7x2=352x1+x2=9?(3,3)??????????x1x21231253446.1.3整數(shù)規(guī)劃的幾個(gè)典型問題及其模型1、投資決策問題【例1】某產(chǎn)品擬訂在某省的東、南、西、北四個(gè)區(qū)建立銷售中心，總計(jì)有個(gè)點(diǎn)可以供選擇，考慮到各區(qū)居民消費(fèi)水平及居民的居住密集度，總部決定：1）在東區(qū)由A1、A2、A3三個(gè)點(diǎn)中至多選擇兩個(gè)；2）在南區(qū)由A4、A5兩個(gè)點(diǎn)中至少選擇一個(gè)；3）在西區(qū)由A6、A7兩個(gè)點(diǎn)中至少選擇一個(gè)；4）在北區(qū)由A8、A9、A10三個(gè)點(diǎn)中至少選擇兩個(gè)。各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)、各地實(shí)際情況的不同都是不一樣的，預(yù)測情況見下表所示(單位：萬元)。但投資總額不能超過720萬元，問怎么選擇銷售點(diǎn)，可使年利潤為最大?12345678910投資額10012015080709080140160180利潤36405022203025485861解：設(shè)0—1變量或這樣我們建立如下的數(shù)學(xué)模型：2、設(shè)備購置問題【例2】某廠擬用M元資金購買m種設(shè)備A1，A2，‥，Am，其中設(shè)備Ai單價(jià)為pi（i=1,2,‥,m）?，F(xiàn)有n個(gè)地點(diǎn)B1，B2，‥，Bn可裝備這些設(shè)備，其中Bj處最多可以裝置bj（j=1,2,‥,n）臺(tái)。預(yù)計(jì)將一臺(tái)設(shè)備Ai裝備于Bj處可以獲利cij元，則應(yīng)該如何購置這些設(shè)備，才能使總利潤為最大？解：設(shè)

yj——購買設(shè)備Ai的臺(tái)數(shù);xij——將設(shè)備Ai裝置于Bj處的臺(tái)數(shù);z——預(yù)計(jì)總利潤（元）.建立如下數(shù)學(xué)模型：3、工廠選址問題【例3】某一種商品有n個(gè)銷地，各銷地的需求量分別為bj噸/天?，F(xiàn)擬在m個(gè)地點(diǎn)中選址建廠來生產(chǎn)這種商品以滿足供應(yīng)，且規(guī)定一址最多只能建一個(gè)工廠。若選i址建廠，將來生產(chǎn)能力為ai噸/天，固定費(fèi)用為di元/天。已知i址至銷地j的運(yùn)價(jià)為cij元/噸。應(yīng)該如何選擇廠址和安排調(diào)運(yùn)，能使總的費(fèi)用最少？解：設(shè)

xij——從i址至銷地j的運(yùn)量（噸/天）

z——總費(fèi)用（元/天）

建立如下數(shù)學(xué)模型：4、指派問題（后面再詳細(xì)介紹）某單位需要完成若干項(xiàng)不同的任務(wù)，現(xiàn)有若干個(gè)對(duì)象能夠完成其中每項(xiàng)任務(wù)，但由于每個(gè)人特長與能力不同，每個(gè)人完成各項(xiàng)任務(wù)所費(fèi)時(shí)間(或效率)也不同。現(xiàn)假設(shè)必須每項(xiàng)任務(wù)只能交給一個(gè)對(duì)象去完成，怎樣把這些任務(wù)指派給個(gè)人，使得完成任務(wù)的總效率最高（或所需總時(shí)間最?。@類問題就是指派問題(或稱分配問題)。6.2整數(shù)規(guī)劃的一般解法整數(shù)規(guī)劃與線性規(guī)劃的顯著區(qū)別在于前者變量為整數(shù)型，后者變量為連續(xù)型。前面我們介紹的枚舉法對(duì)于可行域有界的IP問題還可以湊合，但是對(duì)于無界的IP問題，或者規(guī)模較大的IP問題，枚舉法實(shí)際上已經(jīng)不再生效。下面介紹整數(shù)規(guī)劃的兩種一般解法——分支定界法和割平面法。分支定界法BranchandBoundMethod基本思想：先求出IP問題的松弛問題的最優(yōu)解，若該解不滿足整數(shù)性約束，則以該解為出發(fā)點(diǎn)，將原問題分為兩個(gè)支問題，且每支增加一個(gè)新的約束，使得可行域縮??；然后再求支問題的最優(yōu)解，并對(duì)其再進(jìn)行分支，重復(fù)直至達(dá)到求的IP問題的最優(yōu)解。整數(shù)規(guī)劃的最優(yōu)值不優(yōu)于與之相對(duì)應(yīng)的線性規(guī)劃的最優(yōu)值。Z0：松弛問題的解；Zi：最好的整數(shù)解；Z*:最優(yōu)解；ZL：下界；ZU：上界。ZL=Zi≤Z*≤Z0=ZU。（最大化問題）ZL=Z0≤Z*≤Zi=ZU（最小化問題）【例4】用分支定界法求解下列IP問題。x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥4【練習(xí)】用分支定界法求解下列IP問題。6.4指派問題及其解法6.4.1標(biāo)準(zhǔn)指派問題及其數(shù)學(xué)模型指派問題（AssignmentProblem）某單位需要完成n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長與能力不同，每個(gè)人完成各項(xiàng)任務(wù)所費(fèi)時(shí)間(或效率)也不同。現(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總效率最高（或所需總時(shí)間最?。?，這類問題就是標(biāo)準(zhǔn)指派問題或分配問題?！纠?】有一份資料需要翻譯成英、日、俄三種文字，現(xiàn)有A、B、C三人，每人需完成其中的一種工作。因個(gè)人對(duì)不同文字的熟悉程度不一樣，所需要的工作時(shí)間也不同（見下表）。問：應(yīng)該指派哪一個(gè)人去完成哪一項(xiàng)工作才能使花費(fèi)的總的時(shí)間最短？譯英譯日譯俄A21513B10414C91416解：該例就是一個(gè)典型的指派問題。為解決這種問題，我們引入，且令記所需的總時(shí)間為z，稱上表所給的時(shí)間為價(jià)值系數(shù)表，由價(jià)值系數(shù)表中的數(shù)據(jù)構(gòu)成的矩陣稱為該例的效益矩陣。任何一個(gè)指派問題都有一個(gè)這樣的效益矩陣，其元素記為，表示第i個(gè)人完成第j項(xiàng)任務(wù)時(shí)的效益（如利潤、費(fèi)用、時(shí)間等）。由于每個(gè)人必須完成一項(xiàng)工作，且僅完成一項(xiàng)工作；而且每項(xiàng)工作必須由一個(gè)人完成，且僅只能由一個(gè)人完成，由此可以建立該問題的數(shù)學(xué)模型為：或者用下面的表達(dá)形式：該模型的可行解可以用一個(gè)矩陣表示，稱為解矩陣。例如它的一個(gè)可行解為上列矩陣，容易看出它是一個(gè)3階排列陣。標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型為：其中：約束條件1說明第j項(xiàng)任務(wù)只能由一個(gè)人去完成；約束條件2說明第i人只能完成一項(xiàng)任務(wù)。6.4.2指派問題的解法——匈牙利法指派問題是0-1規(guī)劃問題的特例。目前求解指派問題比較有效的算法是匈牙利數(shù)學(xué)家考尼格（Konig）提出的，因此得名為匈牙利法（TheHungarianMethodofAssignment）。[定理]系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。A匈牙利法的基本思想【基本思路】修改效益矩陣的行和列，使得在每一行和列中至少有一個(gè)為0的元素，直到在不同行、不同列中至少有一個(gè)0元素，從而得到與這些0元素相對(duì)應(yīng)的最優(yōu)分配方案。【理論依據(jù)】設(shè)一個(gè)指派問題的效益矩陣為（cij），若從其某行（或列）各元素中分別減去該行（或列）的最小元素，得到新的效益矩陣（bij），那么以（bij）為效益矩陣求得的最優(yōu)解和用原效益矩陣求得的最優(yōu)解相同。B匈牙利法基于的標(biāo)準(zhǔn)形式1）目標(biāo)要求為min；2）效益矩陣（cij）為n階方陣；3）效益矩陣中所有元素cij≥0，且為常數(shù)。

——以上被稱為指派模型的標(biāo)準(zhǔn)形C匈牙利法的計(jì)算步驟1）效益矩陣的初始變換——“0元”的獲得從效益矩陣的每行減去該行的最小元素從效益矩陣的每列減去該列的最小元素2）最優(yōu)性檢驗(yàn)是否存在n個(gè)位于不同行、不同列的0元？即：nb=n？滿足該條件的效益矩陣稱為最優(yōu)陣，否則稱為非最優(yōu)陣。3）非最優(yōu)陣的變化、調(diào)整【例6】有一份中文說明書需要翻譯成英、日、德、俄四種文字，現(xiàn)有A、B、C、D四人，他們將中文說明書翻譯成上述四中語言的說明書所需要的時(shí)間見下表。問：應(yīng)該指派哪一個(gè)人去完成哪一項(xiàng)工作才能使花費(fèi)的總時(shí)間最短？英語日語德語俄語A215134B1041415C9141613D7811947

2151341041415914161378119

013112601011057401422497min48

01311260101105740142

0042min

01370606905320100=（bij

）49

01370606905320100此時(shí)加圈0元素的個(gè)數(shù)，所以得到最優(yōu)解。50即：A翻譯成俄語，B翻譯成日語，C翻譯成英語，D翻譯成德語所需要的時(shí)間為：

00010100

10000010ABCDE甲127979乙89666丙71712149丁15146610戊410710952

127979896667171214915146610410710976764

5020223000010572980040636553

50202230000105729800406365541）對(duì)沒有圈0元素的行打√號(hào)；2）對(duì)所有已打√號(hào)行中所有含0元素的列打√號(hào)；3）再對(duì)已打√號(hào)的列中含加圈0素的行打√號(hào)；4）重復(fù)2）和3），直到再也不能找到可以打√號(hào)行、列為止；5）對(duì)沒有打√號(hào)的行畫一橫線，對(duì)打√號(hào)的列畫一豎線，這樣就得到了能覆蓋所有0元素的最少直線數(shù)。55

50202230000105729800406365√√√

這時(shí)候繼續(xù)變換效益矩陣，其方法是：一、沒有覆蓋的行給予行位勢為：最小值覆蓋的行給予行位勢為：0沒有覆蓋的列給予行列勢為：0覆蓋的列給予列位勢為：—（最小值）二、矩陣每個(gè)元素-（行位勢+列位勢）這樣得到新效益矩陣（其最優(yōu)解和原問題相同），能得到n個(gè)獨(dú)立的0元素，得到最優(yōu)解。

這時(shí)候繼續(xù)變換效益矩陣，其方法是：在所有未被直線覆蓋的元素中找出一個(gè)最小元素；然后在打√號(hào)行（未畫直線的行）各元素都減去這一最小元素；而在打√號(hào)列（畫直線的列）的各元素都加上這一最小元素；保證原來的各0元素不變。這樣得到新效益矩陣（其最優(yōu)解和原問題相同），若能得到n個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則重復(fù)上述步驟繼續(xù)變換效益矩陣。5850202230000105729800406365√√√最小元素=27020243000083501180040414359

7020243000083501180040414360

01000000100000100100

10000

最優(yōu)指派方案甲——B乙——D丙——E丁——C戊——A61本例還可以得到另外一個(gè)最優(yōu)的指派方案為：

01000001000000100010

10000最優(yōu)指派方案甲——B乙——