《管理運籌學》03-整數(shù)規(guī)劃

第3章,IntegerProgramming,IP,整數(shù)規(guī)劃,3.1整數(shù)規(guī)劃問題及其建模3.2分支定界法3.3割平面法3.40-1型整數(shù)線性規(guī)劃的解法3.5指派問題3.6整數(shù)規(guī)劃應(yīng)用,第3章整數(shù)規(guī)劃,第3章整數(shù)規(guī)劃,2,基本概念,整數(shù)規(guī)劃：變量取整數(shù)的線性規(guī)劃；純整數(shù)規(guī)劃：所有變量都取整數(shù)的線性規(guī)劃；混合整數(shù)規(guī)劃：部分變量取整數(shù)的線性規(guī)劃；0-1規(guī)劃：所有變量都取0、1兩個值的規(guī)劃；0-1混合規(guī)劃：部分變量取0、1兩個值的規(guī)劃。,例3-1背包問題,3.1整數(shù)規(guī)劃問題及其建模,4,線性規(guī)劃最優(yōu)解為:x1=0，x2=0，x3=2.5而整數(shù)規(guī)劃的最優(yōu)解是x1=1，x2=0，x3=2,例3-2廠址選擇問題在N個地點中選r個（Nr）建廠，在第i個地點建廠（i=1，2，N）所需投資為Ii萬元，占地Li畝，建成以后的生產(chǎn)能力為Pi萬噸?，F(xiàn)在有總投資I萬元，土地L畝，應(yīng)如何選擇廠址，使建成后總生產(chǎn)能力最大。設(shè),3.1整數(shù)規(guī)劃問題及其建模,5,整數(shù)規(guī)劃模型為:,0-1規(guī)劃,例3-3考慮固定成本的最小生產(chǎn)費用問題在最小成本問題中，設(shè)第j種設(shè)備的固定成本為，運行的變動成本為，則生產(chǎn)成本與設(shè)備運行時間的關(guān)系為：,6,混合0-1規(guī)劃,設(shè)第j種設(shè)備運行每小時可以生產(chǎn)第i種產(chǎn)品件，而第i種產(chǎn)品定貨為件。要滿足定貨同時使設(shè)備運行的總成本最小的問題為：,3.1整數(shù)規(guī)劃問題及其建模,線性規(guī)劃與整數(shù)規(guī)劃的關(guān)系,7,線性規(guī)劃,整數(shù)規(guī)劃,X*=（13/5，19/5）Z*=89/5=17.8,X*=（5，3）Z*=17,基本思想分支（Branch）定界（Bound）,3.2分支定界法（B&B）,第3章整數(shù)規(guī)劃,8,分支（Branch）這兩個子問題的可行域都是原線性規(guī)劃問題可行域的子集，這兩個子問題的最優(yōu)解的目標函數(shù)值都不會比原線性規(guī)劃問題的最優(yōu)解的目標函數(shù)值更小。如果這兩個問題的最優(yōu)解仍不是整數(shù)解，則繼續(xù)選擇一個非整數(shù)的變量，繼續(xù)將這個子問題分解為兩個更下一級的子問題。這個過程稱為“分枝（Branch）”。定界（Bound）如果某一個子問題的最優(yōu)解是整數(shù)解，則它的目標函數(shù)值可作為整數(shù)規(guī)劃最優(yōu)目標函數(shù)值的上界。如果某一個子問題的解還不是整數(shù)解，但這個非整數(shù)解的目標函數(shù)值已經(jīng)超過這個上界，那么這個子問題不必再進行分枝。如果在分枝過程中得到新的整數(shù)解且該整數(shù)解的目標函數(shù)值小于已記錄的上界，則用較小的整數(shù)解的目標函數(shù)值代替原來的上界。上界的值越小，就可以避免更多不必要的分枝。確定整數(shù)解目標函數(shù)值上界并不斷更新上界，并且不斷“剪除”目標函數(shù)值超過上界的分枝的過程，稱為定界（Bound）。,第3章整數(shù)規(guī)劃,9,例3-4用分枝定界法求解以下整數(shù)規(guī)劃先求得相應(yīng)的線性規(guī)劃的最優(yōu)解，為,3.2分支定界法（B&B）,第3章整數(shù)規(guī)劃,10,11,Sub-6無可行解,原問題,Sub-2,Sub-1,Sub-3,Sub-4,Sub-5,Sub-7,Sub-9,Sub-8,Sub-10無可行解,x22,x23,x15,x15,x21,x22,x14,x16,x20,x21,圖3-3.探索過程示意圖,1,3.3.1割平面法基本思想,3.3割平面法,第3章整數(shù)規(guī)劃,12,首先放棄變量的整數(shù)要求，求得線性規(guī)劃的最優(yōu)解。如果最優(yōu)解恰是一個整數(shù)解，則線性規(guī)劃的最優(yōu)解就是相應(yīng)的整數(shù)規(guī)劃的最優(yōu)解。如果線性規(guī)劃的最優(yōu)解不是整數(shù)解，則要構(gòu)造一個新的約束，對線性規(guī)劃問題的可行域進行切割，切除已經(jīng)得到的線性規(guī)劃的最優(yōu)解，但保留原可行域中所有的整數(shù)解，求解新的線性規(guī)劃問題如果最優(yōu)解仍不是整數(shù)解，再增加附加的約束將其切除，但仍保持最初可行域中所有的整數(shù)解，如此一直進行，直至得到一個整數(shù)的最優(yōu)解為止。,3.3.1割平面法基本思想,第3章整數(shù)規(guī)劃,13,設(shè)放棄變量整數(shù)要求得到的線性規(guī)劃的最優(yōu)單純形表如下：,設(shè)其中基變量Xr的值br不是整數(shù)，以I表示整數(shù)，以F表示正的真分數(shù)，令,yrj=Irj+Frj(0Frj1),br=Ir+Fr(0Fi1),將上面兩式代入約束r中，得,第6章整數(shù)規(guī)劃,14,改寫成,因此對于整數(shù)可行解，約束（3-2）可以寫成更嚴格的不等式,這就是源于第r行的割平面。線性規(guī)劃的任何整數(shù)可行解都滿足這個約束；未切割掉任何一個整數(shù)解。線性規(guī)劃的非整數(shù)最優(yōu)解不滿足這個約束。切割掉了非整的LP解X；,第3章整數(shù)規(guī)劃,15,2若Xk的分量全為整數(shù)，則Xk即為原問題的最優(yōu)解，停止計算；否則根據(jù)Xk的一個非整分量所在單純形表的那一行，譬如第r行，構(gòu)造源于第i行的割平面，給它引入一個弛變量xn+k+1，得,3把這個新約束添到最優(yōu)單純形表中，并增加一列(即xn+k+1列)，用對偶單純形法繼續(xù)迭代，求得一個新解Xk+1，令k:=k+1，返2。,3.3.2割平面法基本步驟1用單純形法求解IP的伴隨LP問題，得到其解X0，令k=0；,n,第6章整數(shù)規(guī)劃,16,例3-5試用割平面法求解以下整數(shù)規(guī)劃：,解求解線性規(guī)劃得最優(yōu)單純形表,選擇一個非整數(shù)的基變量，例如x2=8/5，構(gòu)造約束條件(3-4）b2=8/5=1+3/5，I2=1，F(xiàn)2=3/5y23=1/5=0+1/5，I23=0，F(xiàn)23=1/5y24=-3/5=-1+2/5，I24=-1，F(xiàn)24=2/5附加的約束條件為3/5-（1/5x3+2/5x4）0即1/5x3+2/5x43/5將這個約束加到線性規(guī)劃的最優(yōu)單純形表中，并增加一個松弛變量x5,得下表,第3章整數(shù)規(guī)劃,17,第3章整數(shù)規(guī)劃,18,用對偶單純形法，x5離基，x3進基,已獲得整數(shù)的最優(yōu)解：X*=（2，1）Z*=10,為了得到切割約束1/5x3+2/5x43/5在（x1,x2）平面中的表達式，將其中的松弛變量x3，x4用x1，x2表示x3=3x1+x2-4，x4=x1+2x2-4代入切割約束，得到x1+x23這個切割過程的圖解如下圖,第3章整數(shù)規(guī)劃,19,隱枚舉法（ImplicitEumeration）例3-6用隱枚舉法求解下列問題可行解：X=(1，0，0)，Z=3增加過濾條件（filteringconstraint）,3.40-1型整數(shù)規(guī)劃的解法,第3章整數(shù)規(guī)劃,20,3.40-1型整數(shù)規(guī)劃的解法,第3章整數(shù)規(guī)劃,21,按價值系數(shù)從小到大排列maxz=-2x2+3x1+5x3-2x2+3x1+5x332x2+x1-x324x2+x1+x34x2+x134x1+x36,改進算法（更早發(fā)現(xiàn)最優(yōu)解）,第3章整數(shù)規(guī)劃,22,-2x2+3x1+5x35,第3章整數(shù)規(guī)劃,23,-2x2+3x1+5x38,指派問題或分派問題（assignmentproblem）：需完成n項任務(wù)，恰好有n個人可承擔這些任務(wù)。各人完成任務(wù)的效率(或所費時間)不同。應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高(或所需總時間最小)。例3-5甲、乙、丙、丁四人配送A,B,C,D四種貨物,所需時間如下表所示。若一種貨物只交一人送貨，則應(yīng)指派何人配送何種貨物,能使總的時間最少？,3.5指派問題,第3章整數(shù)規(guī)劃,24,效率矩陣,設(shè)xij=1表示第i人送j貨，否則xij=0上述問題的模型為：,第3章整數(shù)規(guī)劃,25,一般指派問題的模型,指派問題的求解方法匈牙利法性質(zhì)3-1.若從系數(shù)矩陣(cij)的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣(bij)，那么以(bij)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。性質(zhì)3-2.若一個方陣的一部分元素為0，另一部分元素不為0，則覆蓋方陣內(nèi)所有0元素的最少直線數(shù)恰好等于獨立0元素（位于不同行，不同列的0元素）的最多個數(shù)。,第3章整數(shù)規(guī)劃,26,例3-7：匈牙利法的步驟一、系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。二、尋找獨立0元素最優(yōu)值為：Z*=11+9+4+5=29,第3章整數(shù)規(guī)劃,27,甲C，乙A，丙D，丁B,例3-5：先減列元素獨立0元素的個數(shù)為3，小于矩陣的階數(shù)。,3.5指派問題,第3章整數(shù)規(guī)劃,28,三、找出能覆蓋非最優(yōu)陣中所有0元的最少直線集合,第6章整數(shù)規(guī)劃,29,(4)重復(fù)(2)、(3)步驟，直到找不出新的打號的行、列為止；(5)對沒有打號的行畫橫線，對所有打號的列畫豎線，這就是能覆蓋所有0元的最少直線的集合。,三、用最少的直線數(shù)覆蓋矩陣中的所有0元素,第3章整數(shù)規(guī)劃,30,四、增加矩陣中的0元素在沒有被直線覆蓋的部分中找出最小元素。然后在打行各元素中都減去這最小元素，而在打列的各元素都加上這最小元素。若得到n個獨立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進行。,第3章整數(shù)規(guī)劃,31,最優(yōu)解,可令bij=M-cij。其中M是足夠大的常數(shù)(如選（cij）中最大元素為M即可)，這時系數(shù)矩陣可變換為B=(bij),極大化的指派問題,第3章整數(shù)規(guī)劃,32,目標函數(shù)經(jīng)變換后，即解,所得(bij)最小解即為原問題(cij)的最大解。,例3-8某航空公司是一家經(jīng)營小型飛機、短途航線的運輸企業(yè)。管理層準備拓展經(jīng)營領(lǐng)域，面臨的問題是：是采購更多的小型飛機來開辟一些新的短途航，還是開始通過為一些跨地區(qū)航線購買大型飛機來進軍全國市場，或者兩種方法同時進行，已知采購成本、年利潤、最多購買的數(shù)量限制如下表。并且可用資金為1億元，如何進行決策，能使年利潤達到最大？,3.6整數(shù)規(guī)劃的應(yīng)用,第3章整數(shù)規(guī)劃,33,x1,x2,3.6整數(shù)規(guī)劃的應(yīng)用,第3章整數(shù)規(guī)劃,34,整數(shù)規(guī)劃模型為：,例3-9某速遞公司的線路選擇問題。公司提供快遞服務(wù)，所有快件兩天內(nèi)都能送到?？旒谕砩系竭_各收集中心，并于第二天早上裝上送往該區(qū)域地區(qū)的幾輛汽車。因為快遞行業(yè)競爭激烈，為了減少平均送