《教案整數(shù)規(guī)劃課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《教案整數(shù)規(guī)劃課件.ppt（60頁珍藏版）》請在匯文網(wǎng)上搜索。

1、第一節(jié)第一節(jié) 問題的提出問題的提出 例子：某廠擬采用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如下表問兩種貨物托運多少箱，可使獲得利潤為最大？第五章 整數(shù)規(guī)劃（Integer Programming)分類：1.純整數(shù)線性規(guī)劃（Pure Integer Linear Programming）2.混合整數(shù)線性規(guī)劃（Mixed Integer Linear Programming）3.0-1型整數(shù)線性規(guī)劃（Zero-One Integer Linear Programming）解：設(shè)x1，x2分別表示兩種貨物托運的箱數(shù)，那么其線性規(guī)劃為可得最優(yōu)解為x*=（5/3，8/3)T。

2、如果選用“向上湊整”的方法可得到x(1)=(2,3)T,則此時已破壞了體積約束,超出可行域的范圍;如果“舍去小數(shù)”可得x(2)=(1,2)T,則此時雖是可行解,值為10，不是最優(yōu)解,因為當x*=(2,2)T是,其利潤為14.由于托運的箱數(shù)不能為分數(shù)，故上述規(guī)劃問題是整數(shù)規(guī)劃問題。若不考慮整數(shù)約束，其相應(yīng)的線性規(guī)劃問題為LP-1：第二節(jié)第二節(jié) 分枝定界法分枝定界法(Branch and Bound method)引言：窮舉法對小規(guī)模的問題可以。大規(guī)模問題則不行，如指派問題 n個人指派n件事，共有n！中指派方案。一、基本思想和算法依據(jù) 基本思想基本思想是：先求出相應(yīng)的線性規(guī)劃最優(yōu)解，若此解不符合整

3、數(shù)條件，那么其目標函數(shù)的值就是整數(shù)規(guī)劃問題最優(yōu)值的上界，而任意滿足整數(shù)條件的可行解的目標函數(shù)值將是其下界（定界），然后將相應(yīng)的線性規(guī)劃問題進行分枝，分別求解后續(xù)的分枝問題。如果后續(xù)分枝問題的最優(yōu)值小于上述下界,則剪掉此枝;如果后續(xù)某一分枝問題的最優(yōu)解滿足整數(shù)條件，且其最優(yōu)值大于上述下界，則用其取代上述下界，繼續(xù)考慮其它分枝，直到最終求得最優(yōu)的整數(shù)解。算法的依據(jù)算法的依據(jù)在于：“整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于相應(yīng)的線性規(guī)劃問題的最優(yōu)解”。具體說就是，對極大化問題，與整數(shù)規(guī)劃問題相應(yīng)的線性規(guī)劃問題的目標函數(shù)值，是該整數(shù)規(guī)劃問題目標函數(shù)的上界；任何滿足整數(shù)條件的可行解的目標函數(shù)值將是其下界。二、具體步驟（

4、以例子說明）解：第一步：先不考慮整數(shù)約束條件，求解相應(yīng)的線性規(guī)劃問題，得最優(yōu)解和最優(yōu)值如下x1=4.81,x2=1.82,Z=356 此解不滿足整數(shù)解條件。定出整數(shù)規(guī)劃問題目標函數(shù)的上下界。上界為 Z=356；用觀察法可知x1=0，x2=0是可行解，從而其整數(shù)規(guī)劃問題目標函數(shù)的下界應(yīng)為0，即0 Z*3569x1+7x2=567x1+20 x2=70Z=40 x1+90 x2LP-1LP-2第二步：分枝與定界過程。將其中一個非整數(shù)變量的解，比如x1,進行分枝，即x14.81=4,x14.81+1=5并分別加入LP問題的約束條件中,得兩個子LP規(guī)劃問題LP-1,LP-2,分別求解此兩個子線性規(guī)劃問

5、題,其最優(yōu)解分別是LP-1:x1=4,x2=2.1,Z1=349 LP-2:x1=5,x2=1.57,Z2=341沒有得到全部決策變量均是整數(shù)的解。再次定出上下界0 Z*349 繼續(xù)對問題LP-1，LP-2進行分枝。先對目標函數(shù)值大的進行分枝，即分別將 x22.1=2,x22.1+1=3加入到約束條件中去,得子問題LP-3,LP-4,分別求解得問題LP-3的所有解均是整數(shù)解,而問題LP-4還有非整數(shù)解,但由于 Z3Z4,對LP-4分枝已沒有必要，剪掉。LP-3:x1=4,x2=2,Z3=340（是整數(shù)解，定下界）LP-4:x1=1.42,x2=3,Z4=327（剪掉）上下界為 340 Z*34

6、9 在對問題LP-2進行分枝,x2 1.57=1，x21.57+1=2,得子問題LP-5,LP-6,求解得LP-5:x1=5.44,x2=1,Z5=308(下界340,剪掉)LP-6:無可行解（剪掉）于是得到原整數(shù)規(guī)劃問題的最優(yōu)解為LP:x1=4,x2=2,Z3=340 x1=4.81LP:x2=1.82 Z=356LP-1:x1=4x1 4 x2=2.1 Z=349LP-2:x1=5x15 x2=1.57 Z=341LP-3:x1=4x1 4 x2=2x2 2 Z=340LP-6 x15 無可行解 剪掉 x22LP-4:x1=1.42x1 4 x2=3 剪掉x2 3 Z=327LP-5:x1

7、=5.44x15 x2=1 剪掉x2 1 Z=308整個過程如下:步驟:1 求解相應(yīng)的線性規(guī)劃問題的最優(yōu)解和最優(yōu)值,如果a)沒有可行解,停止;b)若有滿足整數(shù)條件的最優(yōu)解,則已得到整數(shù)規(guī)劃問題的最優(yōu)解,停止;c)若有最優(yōu)解,但不滿足整數(shù)條件,記此最優(yōu)值為原整數(shù)規(guī)劃問題Z*的上界,然后,用觀察法求出下界.2 分枝、定界，直到得到最優(yōu)解為止。a）在以后的各枝中，若某一子規(guī)劃問題的最優(yōu)解滿足整數(shù)條件，則用其最優(yōu)值置換Z*的下界。b）若某一分枝的最優(yōu)值小于Z*的下界，則剪掉此枝，即以后不在考慮此枝三、算法需要注意的幾點（以極大化問題為例）1 在計算過程中，若以得到一個整數(shù)可行解x(0)，其相應(yīng)的目標函

8、數(shù)值為Z0，那么在計算其它分枝過程中，如果解某一線性規(guī)劃所得的目標函數(shù)值ZZ0，即可停止計算。因為進一步的分枝結(jié)果的最優(yōu)值只能比Z更差。2 若有若干個待求解的分枝，先選那一個待求解的分枝呢？選取目標函數(shù)值最大的那一枝。例 求下列整數(shù)規(guī)劃問題的解不考慮整數(shù)約束X1=5/2X2=2Z=23x1 2x1 3LP1LP2Z=21Z=22不考慮整數(shù)約束X1=5/2X2=2Z=23第1個子問題X1=2X2=9/4Z=21第2個子問題X1=3X2=1Z=22x1 2x1 3練習：用分支定界法求解下述整數(shù)規(guī)劃問題 x1=5/3LP:x2=8/3 Z=44/3LP-1:x1=1x1 1 x2=16/5 剪掉 Z

9、=68/5LP-2:x1=2x12 x2=2 Z=14第三節(jié)第三節(jié) 割平面解法割平面解法(Cutting Plane Approach)割平面法是1958年美國學者R.E.Gomory提出的?；舅枷胧牵合炔豢紤]變量的取整數(shù)約束，求解相應(yīng)的線性規(guī)劃，然后不斷增加線性約束條件（即割平面），將原可行域割掉不含整數(shù)可行解的一部分，最終得到一個具有整數(shù)坐標頂點的可行域，而該頂點恰好是原整數(shù)規(guī)劃問題的最優(yōu)解。例：求解加松弛變量x3、x4，使其變成標準形（如有非整數(shù)的系數(shù)，則將其所在的方程乘以某一常數(shù)，變成具有整數(shù)系數(shù)的約束方程），用單純形法求解得最優(yōu)解x1=3/4，x2=7/4，x3=x4=0，最優(yōu)值為

10、Z=5/2，是非整數(shù)解。尋求割平面：由最終表得x1-1/4x3+1/4x4=3/4x2+3/4x3+1/4x4=7/4任選一取分數(shù)值的基變量，比如x1，將該式中所有變量的系數(shù)、右端常數(shù)項均改寫成整數(shù)與非負真分數(shù)之和的形式，并移項得x1-x3=3/4 -（3/4x3+1/4x4）（注注：所有的x均是整數(shù)。x3、x4可通過在原約束條件中乘以某一常數(shù)變成整數(shù)。）則整數(shù)約束條件可由下式替代 3/4 -（3/4x3+1/4x4）0 即得割平面方程-3x3-x4-3引入松弛變量x5，將其加入到原規(guī)劃的約束條件中，利用上述最終表得左邊項必是整數(shù)；0(3/4x3+1/4x4)3/4內(nèi)不包含任何整數(shù)-1+3/4

11、用對偶單純形算法進行計算。x5作換出變量，x3換入變量，迭代得已得到整數(shù)解，最優(yōu)解為x1=1，x2=1，最優(yōu)值為2。注：新約束-3x3-x4-3的幾何意義。用x1，x2表示上述約束，得 x2 1，其圖形見下圖。3x1+x2=4-x1+x2=1x2 1求切平面的基本步驟：1 令xi是相應(yīng)線性規(guī)劃問題最優(yōu)解中為分數(shù)解的一個基變量，由單純形最終表得到 xi+aikxk=bi，其中i為基變量的標號；k為非基變量的標號。2 將bi和aik都分解成整數(shù)部分N與非負分數(shù)部分f之和，即 bi=Ni+fi，其中0fi1 aik=Nik+fik,其中0fik00 xj=0Min Z=(K1y1+c1x1)+（K2

12、y2+c2x2）+（K3y3+c2x2）xj yjM 若有n個決策變量,則可以產(chǎn)生2n個可能變量的組合,故完全枚舉是不可能的.求解0-1整數(shù)規(guī)劃問題的解法均是部分枚舉法或稱為隱枚舉法(Implicit enumeration)基本思想基本思想是:在2n個可能的變量組合中,往往只有一部分是可行解.只要發(fā)現(xiàn)某個變量組合不滿足其中的某一約束條件時,就不必要檢驗其它的約束條件是否可行。若發(fā)現(xiàn)一個可行解,則根據(jù)它的目標函數(shù)值可以產(chǎn)生一個過濾條件(Filtering constraint),對于目標函數(shù)值比它差的的變量組合就不必再去檢驗它的可行性（類似分支定界法中的定界。實際上，隱枚舉法是一種特殊的分支定

13、界法）。在以后求解過程中,每當發(fā)現(xiàn)比原來更好的可行解,則依次替代原來的過濾條件(可減少運算次數(shù),較快地發(fā)現(xiàn)最優(yōu)解)。0-1整數(shù)規(guī)劃問題的解法整數(shù)規(guī)劃問題的解法以例子說明上述求解方法例1:求解下述0-1整數(shù)規(guī)劃問題解：求解過程見下表所以，最優(yōu)解為（x1，x2，x3)T=(1,0,1)T,最優(yōu)值為8.注：當決策變量(x1,x2,x3)按(0,0,0),(0,0,1),(0,1,0),(0,1,1),.方式取值時,為了減少計算次數(shù),通常將目標函數(shù)中的決策變量的順序按其系數(shù)的大小重新排序,以使最優(yōu)解能較早出現(xiàn)。對最大化問題,按從小到大的順序排列；對極小化問題,則相反。例2：求解下述0-1整數(shù)規(guī)劃問題解

14、：重新排序為練習：求解下述整數(shù)規(guī)劃問題=0+2-2-+-4+-+=5,2,1103-2253.31075min54321432154321Ljorxxx6xxx5xxxxtsxxxxxZj1-+25432xxx-x第五節(jié)第五節(jié) 指派問題（指派問題（Assignment Problem）1.標準指派問題的提法及模型 指派問題的標準形式是：有n個人和n件事，已知第i個人做第j件事的費用為cij（i，j=1，2，n），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事的總費用最小。數(shù)學模型為:若指派第i個人做第j件事若不指派第i個人做第j件事(i,j=1,2,n)設(shè)n2個0-1變量其中矩陣C稱為

15、是效率矩陣或系數(shù)矩陣。其解的形式可用0-1矩陣的形式來描述，即(xij)nn。標準的指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題和特殊的運輸問題。1955年W.W.Kuhn利用匈牙利數(shù)學家D.Konig關(guān)于矩陣中獨立零元素的定理,提出了解指派問題的一種算法,習慣上稱之為匈牙利解法。2.匈牙利解法 匈牙利解法的關(guān)鍵是指派問題最優(yōu)解的以下性質(zhì)：若從指派若從指派問題的系數(shù)矩陣問題的系數(shù)矩陣C=（cij）的某行（或某列）各元素分別減去一個的某行（或某列）各元素分別減去一個常數(shù)常數(shù)k，得到一個新的矩陣得到一個新的矩陣C=（cij)，則以則以C和和C為系數(shù)矩陣的兩為系數(shù)矩陣的兩個指派問題有相

16、同的最優(yōu)解。個指派問題有相同的最優(yōu)解。（這種變化不影響約束方程組，而只是使目標函數(shù)值減少了常數(shù)k，所以，最優(yōu)解并不改變。）作變換，其不變性是最優(yōu)解對于指派問題，由于系數(shù)矩陣均非負，故若能在在系數(shù)矩陣中找到n個位于不同行和不同列的零元素（獨立的0元素），則對應(yīng)的指派方案總費用為零，從而一定是最優(yōu)的。匈牙利法匈牙利法的步驟如下：步1：變換系數(shù)矩陣。對系數(shù)矩陣中的每行元素分別減去該行的最小元素；再對系數(shù)矩陣中的每列元素分別減去該列中的最小元素。若某行或某列已有0元素，就不必要在減了（不能出現(xiàn)負元素）。步2：在變換后的系數(shù)矩陣中確定獨立0元素（試指派）。若獨立0元素已有n個，則已得出最優(yōu)解；若獨立0元

17、素的個數(shù)少于n個，轉(zhuǎn)步3。確定獨立0元素的方法：當n較小時，可用觀察法、或試探法；當n較大時，可按下列順序進行 從只有一個0元素的行（列）開始，給這個0元素加圈，記作，然后劃去所在的列（行）的其它0元素，記作。給只有一個0元素的列（行）的0加圈，記作，然后劃去所在行的0元素，記作。反復進行，直到系數(shù)矩陣中的所有0元素都被圈去或劃去為止。如遇到行或列中0元素都不只一個（存在0元素的閉回路），可任選其中一個0元素加圈，同時劃去同行和同列中的其它0元素。被劃圈的0元素即是獨立的0元素。步3：作最少數(shù)目的直線，覆蓋所有0元素（目的是確定系數(shù)矩陣的下一個變換），可按下述方法進行1）對沒有的行打“”號；2

18、）在已打“”號的行中，對 所在列打“”3）在已打“”號的列中，對所在的行打“”號；4）重復2）3），直到再也找不到可以打“”號的行或列為止；5）對沒有打“”的行劃一橫線，對打“”的列劃一縱線，這樣就得到覆蓋所有0元素的最少直線數(shù)。步4：繼續(xù)變換系數(shù)矩陣，目的是增加獨立0元素的個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（為了消除負元素）。得到新的系數(shù)矩陣，返回步2。以例說明匈牙利法的應(yīng)用。例1：求解效率矩陣為如下的指派問題的最優(yōu)指派方案。解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0

19、元素）第二步：確定獨立0元素元素的個數(shù)m=4，而n=5，進行第三步。第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個變換。第四步：對上述矩陣進行變換，目的是增加獨立0元素的個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？）由解矩陣可得指派方案和最優(yōu)值為32。例2 某大型工程有五個工程項目，決定向社會公開招標，有五家建筑能力相當?shù)慕ㄖ痉謩e獲得中標承建。已知建筑公司Ai（I=1，2，3，4，5）的報價cij（百

20、萬元）見表，問該部門應(yīng)該怎樣分配建造任務(wù)，才能使總的建造費用最小？解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素）第二步：確定獨立0元素,即加圈元素的個數(shù)m=4，而n=5，進行第三步。第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個變換。第四步：對上述矩陣進行變換，目的是增加獨立0元素個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？因為僅在目標函數(shù)系數(shù)中進行操作）此矩陣中已有5個獨立的0元素，故可得指

21、派問題的最優(yōu)指派方案為：也就是說，最優(yōu)指派方案為：讓A1承建B3，A2承建B2，A3承建B1，A4承建B4，A5承建B5。這樣安排建造費用為最小，即7+9+6+6+6=34（百萬元）3.一般的指派問題 在實際應(yīng)用中，常會遇到各種非標準形式的指派問題。通常的處理方法是先將它們轉(zhuǎn)化為標準形式，然后用匈牙利解法求解。最大化指派問題 設(shè)最大化指派問題系數(shù)矩陣C中最大元素為m。令矩陣B=(bij)=(m-cij),則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。人數(shù)和事數(shù)不等的指派問題 若人少事多，則添上一些虛擬的“人”。這些虛擬的人作各事的費用系數(shù)可取0，理解為這些費

22、用實際上不會發(fā)生。若人多事少，則添上一些虛擬的“事”。這些虛擬的事被各人做的費用系數(shù)同樣也取0。一個人可做幾件事的指派問題 若某個人可做幾件事，則可將該人看做相同的幾個人來接受指派。這幾個人作同一件事的費用系數(shù)當然都一樣。某事一定不能由某人作的指派問題 若某事一定不能由某個人做，則可將相應(yīng)的費用系數(shù)取做足夠大的數(shù)M。例3：對于例2的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，而讓技術(shù)力量較強的建設(shè)公司A1，A2，A3參加招標承建，根據(jù)實際情況，可允許每家建設(shè)公司承建一項或二項工程。求使總費用最少的指派方案。上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛

23、擬的事B6，使之成為標準指派問題的系數(shù)矩陣：解：由于每家建筑公司最多可以承建兩項，因此可把每家建筑公司看成兩家建筑公司，其系數(shù)矩陣為然后，用匈牙利解法求解。可得費用最省為4+7+9+8+7=35（百萬元）練習：某最大化指派問題的效率矩陣如下，求最優(yōu)方案隱枚舉法目標函數(shù)：最小約束條件：約束方程的右端值：不限目標函數(shù)系數(shù)：非負固定變量自由變量算法的步驟1.令全部變量Xj都是自由變量且取0值，檢驗解是否可行；若可行，已經(jīng)得到最優(yōu)解；如不可行，轉(zhuǎn)入2。2.將某一變量轉(zhuǎn)為固定變量，令其取值為1或0，使問題分成兩個子域。令一個子域中的自由變量都取0值，加上固定變量取值，組成此子域的解。3.計算此解的目標函

24、數(shù)值，與已求出的可行解的最小目標函數(shù)比較。如果前者大，則不必檢驗其是否可行而停止分支，若子域都檢驗過，轉(zhuǎn)第7步，否則轉(zhuǎn)第6步。如前者小，轉(zhuǎn)第4步。4.檢驗解是否可行，如可行，得到一個可行解，計算目標函數(shù)值Z，并停止分支，若子域都檢驗過，轉(zhuǎn)第7步，否則，轉(zhuǎn)第6步。如不可行，進行第5步。5.將固定變量的值代入第一個不等式約束方程，并令等式左端的自由變量當系數(shù)為負時取值為1，系數(shù)為正時取值為0，這就是左端能取的最小值。若此最小值大于右端值，則稱此子域為不可行子域，若所有子域都檢驗過，轉(zhuǎn)第7步，否則轉(zhuǎn)第6步；若此最小值小于右端值，則依次檢驗下一個不等式約束方程，直至所有的不等式約束方程都通過，若子域都檢驗過，轉(zhuǎn)第7步，否則，轉(zhuǎn)第6步。6.定出尚未檢驗過的另一個字域的解，進行第3至5步，若所有子域都停止計算，目標函數(shù)值最小的可行解就是最優(yōu)解；否則，轉(zhuǎn)第7步7.檢查有無自由變量。若有，轉(zhuǎn)第2步；若沒有，計算停止。目標函數(shù)值最小的可行解就是最優(yōu)解。