物流運籌學課件4

1、郭淑紅郭淑紅guoshuhong_1307455345313074553453n例如，產品的件數(shù)、機器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分數(shù)或小數(shù)解顯然是不合理的。n全部決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃(All IP)n僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(Mixed IP)n要求決策變量只取0或1值，則稱0-1規(guī)劃(0-1 Programming) 整數(shù)線性規(guī)劃數(shù)學模型的一般形式：且部分或全部為整數(shù)或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZ人員安排規(guī)劃某服務部門各時段某服務部門各時段( (每每2 2小時為一時

2、段小時為一時段) )需要的服務人數(shù)如表：需要的服務人數(shù)如表：解：設第j 時段開始時上班的服務員人數(shù)為xj 第 j 時段來上班的服務員將在第j+3 時段結束時下班，故決策變量有x1,x2,x3,x4,x5 。 二、二、0-10-1規(guī)劃規(guī)劃)2 , 1(01iyi若不建工廠若建工廠 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxx

3、xxxxxxxxxxxxxxxxtsyyxcziijijijij混合整數(shù)規(guī)劃問題混合整數(shù)規(guī)劃問題且為整數(shù)0,13651914max21212121xxxxxxxxZ首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。0,13651914max21212121xxxxxxxxZx x1 1x x2 23 33 3(3/2,10/3)(3/2,10/3)5x1 +7 x2 =352x1 + x2 =9x1x2123125344)972,913(分支定界法分支定界法 LandDoig和和Dakin于于60年代提出年代提出一種隱枚舉法,用來解純整數(shù)規(guī)劃及混合整數(shù)規(guī)劃純整數(shù)規(guī)劃及混合整數(shù)規(guī)劃. 整

4、數(shù)規(guī)劃的可行域是相應的線性規(guī)劃松弛問題可行域的子集；因此，松弛問題最優(yōu)解是整數(shù)規(guī)劃最優(yōu)解的一個界 （對于max，為上界；對于min，為下界）。 分析整數(shù)規(guī)劃問題A對應的松弛問題B的最優(yōu)解（對于max）：說明：該方法可計算機求解；在部分可行解中求解，計算量小于枚舉法；對于大問題，計算量仍較大。例例取整數(shù)2121212121,0,35759256maxxxxxxxxxxxZ 第二步，定界過程。 這個解不滿足整數(shù)約束，因此不是原整數(shù)規(guī)劃的最優(yōu)解。 因為這個問題是求最大化問題，前面說過整數(shù)規(guī)劃是在線性規(guī)劃的基礎上增加了整數(shù)約束，現(xiàn)在不考慮整數(shù)約束求得這個解，其目標函值 Z是原整數(shù)規(guī)劃目標函數(shù)的上界，記

5、 。由于 必然滿足整數(shù)約束，其目標函數(shù)值為0，確定為現(xiàn)有下界，記 。 第三步，分枝過程，將不滿足整數(shù)約束的變量x1進行分枝，構造兩個新的約束條件：這樣就把相應的線性規(guī)劃的可行域分成兩個部分5 x2 1 2 5 3 4 x1 1 2 3 4 2x1 + x2 =9 5x1 +7x2 =35 17(3,2 )99121 623,2,3277L PxxZ：120 1753,2,3 2999L PxxZ：122 4,1,29LPxxZ：1233,2,2 8L PxxZ：124442,3 ,3 155L PxxZ：125462 ,3,2 977L PxxZ：6L P：無 可 行 解1272 ,3 ,2

6、7L PxxZ：128221,4 ,2 855L PxxZ：x13x1 4x22x2 3x12x1 3x23x2 409532下界：上界：297232下界：上界：295431下界：上界：297629下界：上界：2929下界：上界： 且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ 0,4 30 652 5min211212121xxxxxxxxxZLPLPIPIPx x1 1x x2 23 3(18/11,40/11)(18/11,40/11)2 21 11 12 23 3x x1 118/11, 18/11, x x2 2 =40/11 =40/11Z

7、=Z=218/11(218/11(19.8)19.8)即即Z Z 也是也是IPIP最小值的下限。最小值的下限。對于對于x x1 118/111.6418/111.64，取值取值x x1 1 1 1， x x1 1 2 2對于對于x x2 2 =40/11 3.64 =40/11 3.64，取，取值值x x2 2 3 3 ，x x2 2 4 4先將（先將（LPLP）劃分為（）劃分為（LP1LP1）和）和（LP2LP2）, ,取取x1 1, x1 2x1 1, x1 2且為整數(shù)0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且為整數(shù)0,2 4 30 652 )

8、2(5min2111212121xxxxxxxxIPxxZx1x233(18/11,40/11)11BAC同理求同理求LP2,LP2,如圖所示。在如圖所示。在C C 點點取得最優(yōu)解。即取得最優(yōu)解。即: :x x1 12, 2, x x2 2 =10/3, =10/3, Z Z(2)(2)56/356/318.7 18.7 ZZ(2)(2) Z Z(1)(1)16 16 原問題有比原問題有比1616更小的最優(yōu)更小的最優(yōu)解，但解，但 x2 x2 不是整數(shù)，故繼續(xù)不是整數(shù)，故繼續(xù)分支。分支。且為整數(shù)0,3 2 4 30 652 )21(5min21211212121xxxxxxxxxIPxxZ且為整

9、數(shù)0,4 2 4 30 652 )22(5min21211212121xxxxxxxxxIPxxZ分別求出分別求出LP21LP21和和LP22LP22的最優(yōu)解的最優(yōu)解x1x233(18/11,40/11)11BACD先求先求LP21,LP21,如圖所示。此時如圖所示。此時D D 在在點取得最優(yōu)解。點取得最優(yōu)解。即即 x x1 112/52.4, x12/52.4, x2 2 =3, =3, Z Z(21)(21)-87/5-17.4 Z-87/5-17.4 Z(211) 如對如對LP212繼續(xù)分解，其最小繼續(xù)分解，其最小值也不會低于值也不會低于15.5 ，問題探，問題探明明,剪枝。剪枝。LP1

10、x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22無可無可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13 且且均均取取整整數(shù)數(shù),0,255.22108.02.134max21212121xxxxxxxxZ)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 1010108 . 02 . 121

11、 xx255 . 2221 xx松弛問題松弛問題LPLP0 0的最優(yōu)解的最優(yōu)解X X=(3.57,7.14),Z=(3.57,7.14),Z0 0=35.7=35.7x1x2oABC得到兩個線性規(guī)劃及增加約束4311xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.510 x1x2oABCLP1LP2134LP21:X=

12、(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max2121212121xxxxxxxxLPxxZ，不可行，得到線性規(guī)劃，顯然及進行分枝，增加約束選擇目標值最大的分枝7762222xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，10 x1x2oACLP134可可行行域域是是一一條條線線段段即即，, 40,464255 . 22108 . 02 . 1:21134max121121212121 xxxxxxxxxxLPxxZ：及，得線性規(guī)劃及進行分枝，增加約

13、束，選擇由于212211542111121LPLPxxLPZZ6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22無可行解無可行解x

14、27課后練習：課后練習：12121212 max 85 1.56. .2 6,0,zxxxxstxxx x且為整數(shù)12341231241234 m ax 8500 2 3 12. 2 6, , ,0zxxxxxxxstxxxx x x x 計算步驟舉例求解整數(shù)規(guī)劃模型：化標準型：）分析：分析：第一步第一步，如果原問題的系數(shù)有小數(shù)，將其化為整數(shù)。如第一個約束化為122312xx。(15/4, 3/2)X 37.5z松弛問題的最優(yōu)解，非整數(shù)規(guī)劃的可行解。1x1341333884xxx134133(0)(0)(3)884xxx1343133488xxx 343130488xx在最終單純形表中選擇分數(shù)

15、部分最大的基變量列出該行約束：將所有系數(shù)分成整數(shù)與一個正的分數(shù)之和：將分數(shù)部分移至右端：分析右邊的分數(shù)項，其取值小于1，即得到了Gomory約束：引入0-1變量的實際問題0-1型整數(shù)規(guī)劃的解法 如果線性規(guī)劃中的所有決策變量的取如果線性規(guī)劃中的所有決策變量的取值只能取值只能取0 0、1 1，則這類線性規(guī)劃問題是，則這類線性規(guī)劃問題是一種特殊的整數(shù)規(guī)劃問題稱之為一種特殊的整數(shù)規(guī)劃問題稱之為0-10-1規(guī)劃規(guī)劃，把只能取，把只能取0 0或或1 1值的變量稱為值的變量稱為0-10-1變量。變量。0-10-1變量是一種邏輯變量。變量是一種邏輯變量。 n, 2 , 1j ,A0A1xm, 2 , 1i,b

16、),(xa. t . sxc)x( fmax(min)jn1jijijn1jjj不不成成立立時時當當條條件件成成立立時時當當條條件件其其數(shù)學模型數(shù)學模型如下：如下：本節(jié)先介紹引入本節(jié)先介紹引入0-1變量的變量的實際問題實際問題： 投資場所（項目）的選定投資場所（項目）的選定相互排斥的約束條件相互排斥的約束條件關于固定費用的問題關于固定費用的問題 然后，再研究然后，再研究0-1規(guī)劃問題的一般解法規(guī)劃問題的一般解法-隱枚舉法隱枚舉法。7 , 2 , 1iA, 0A, 1xiii 點點沒沒有有被被選選用用當當點點被被選選用用當當令令 10 x1xx1xx)85(2xxxBxbxczmaxi76543

17、2171iii71iii約約束束條條件件目目標標函函數(shù)數(shù)：（1 1）兩個約束條件中只有一個起作用）兩個約束條件中只有一個起作用 當采用車運方式當采用車運方式當采用船運方式當采用船運方式, 0, 1y例：例：利用利用0 0 1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件x x 1 1+x +x 2 2 2 2 或或 2 2x x 1 1+3x +3x 2 2 5 ; 5 ; 為為非非常常大大的的正正數(shù)數(shù)）（或或MyyyyMyxxMyxxa10,1)1(532)1(2)(2121221121解：解： 為為非非常常大大的的正正數(shù)數(shù)）（或或MyyyyMyxxMyxxa10,1)

18、1(532)1(2)(2121221121 10,1753)(321321321或或yyyyyyyyyxb變量變量 x x 只能取值只能取值0 0、3 3、5 5 或或 7 7 中的一個中的一個 ; ; 10,17530321, 032103210或或或或yyyyyyyyyyyyx例：例：利用利用0 0 1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件 10,1753)(321321321或或yyyyyyyyyxb50(1)( )00 1()xyMxMycxyM 或或非非常常大大的的正正變量變量x x 或等于或等于 0 0，或，或 50 ;50 ;例：例：利用利用0 0

19、1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件50(1)( )00 1()xyMxMycxyM 或或非非常常大大的的正正1121122212122 (1)1 (1)2 (1)( )4 (1)1,01xyMxyMxyMdxyMyyMy y （ 非非常常大大的的正正）或或若若 x x1 1 2 2，則，則 x x2 2 1 1，否則，否則x x2 2 4 ; 4 ;例：例：利用利用0 0 1 1變量將下題表示成一般線性約束條件變量將下題表示成一般線性約束條件1121122212122 (1)1 (1)2 (1)( )4 (1)1,01xyMxyMxyMdxyMyyMy y

20、（ 非非常常大大的的正正）或或 非非常常大大的的正正數(shù)數(shù)）（或或MyyyyyyyyMyxxMyxMyxMyxxe10,2)1 (6)1 (2)1 (2)1 (5)(432143214433321121以下四個約束條件中至少滿足兩個以下四個約束條件中至少滿足兩個x x1 1+x+x2 2 5 5， x x1 1 2 2， x x3 3 2 2， x x3 3+x+x4 4 6 6 非非常常大大的的正正數(shù)數(shù)）（或或MyyyyyyyyMyxxMyxMyxMyxxe10,2)1 (6)1 (2)1 (2)1 (5)(432143214433321121例：例：利用利用0 0 1 1變量將下題表示成一般

21、線性約束條件變量將下題表示成一般線性約束條件項目投資選擇項目投資選擇有有600萬元投資萬元投資5個項目，收益如表，求利潤最大的方案？個項目，收益如表，求利潤最大的方案？ 互斥約束問題互斥約束問題 例如關于煤資源的限制，其約束條件為： 企業(yè)也可以考慮采用天然氣進行加熱處理： 這兩個條件是互相排斥的。引入01變量y，令 互斥問題可由下述的條件來代替，其中M是充分大的數(shù)。 租賃生產問題),.,2 , 1(01njjjxj不投資對項目投資對項目投資問題可以表示為：投資問題可以表示為： ）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj, 2 , 1j1021.max765431211隱枚

22、舉法的步驟：隱枚舉法的步驟： 1.找出任意一可行解，目標函數(shù)值為找出任意一可行解，目標函數(shù)值為Z0 2. 原問題求最大值時，則增加一個約束原問題求最大值時，則增加一個約束1 1220(*)nnc xc xc xZ當求最小值時，上式改為小于等于約束當求最小值時，上式改為小于等于約束 3. 列出所有可能解，對每個可能解先檢驗式（列出所有可能解，對每個可能解先檢驗式（*），若滿足再），若滿足再檢驗其它約束，若不滿足式（檢驗其它約束，若不滿足式（*），則認為不可行，若所有約束），則認為不可行，若所有約束都滿足，則認為此解是可行解，求出目標值都滿足，則認為此解是可行解，求出目標值 4. 目標函數(shù)值最大（

23、最?。┑慕饩褪亲顑?yōu)解目標函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解 【例例】用隱枚舉法求解下面問題用隱枚舉法求解下面問題 4 , 3 , 2 , 11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或【解解】（1）不難看出，當所有變量等于）不難看出，當所有變量等于0或或1的任意組合時，的任意組合時，第一個約束滿足，說明第一個約束沒有約束力，是多余的，第一個約束滿足，說明第一個約束沒有約束力，是多余的，從約束條件中去掉。還能通過觀察得到從約束條件中去掉。還能通過觀察得到X0(1，0，0，1)是一是一個可行解，目標值個

24、可行解，目標值Z0=11是該問題的下界是該問題的下界,增加下面約束增加下面約束1153264321xxxx)9 . 3()9 . 3()9 . 3()9 . 3(4 , 3 , 2 , 110105423246531153265326max43214321432143214321dcbajxxxxxxxxxxxxxxxxxxxxxZj，或(2) 列出變量取值列出變量取值0和和1的組合，共的組合，共2416個，分別代入約束條件個，分別代入約束條件判斷是否可行。首先判斷式（判斷是否可行。首先判斷式（3.9a）是否滿足，如果滿足，接下）是否滿足，如果滿足，接下來判斷其它約束，否則認為不可行。來判斷其

25、它約束，否則認為不可行。 (3) 由表知，由表知，該該問題的最優(yōu)解：問題的最優(yōu)解：X（1，0，1，1），最優(yōu)值），最優(yōu)值Z14 選擇不同的初始可行解，計算量會不一樣。一般地，選擇不同的初始可行解，計算量會不一樣。一般地，當目標函數(shù)求最大值時，首先考慮目標函數(shù)系數(shù)最大當目標函數(shù)求最大值時，首先考慮目標函數(shù)系數(shù)最大的變量等于的變量等于1。當目標函數(shù)求最小值時，先考慮目標。當目標函數(shù)求最小值時，先考慮目標函數(shù)系數(shù)最大的變量等于函數(shù)系數(shù)最大的變量等于0。 解：(1)觀察一個可行解x1 = 1 x2 = x3 = 0 此時，z = 3 (2) (2)增加一個過濾條件增加一個過濾條件 3x3x1 1-2x

26、-2x2 2+5x+5x3 33 3 * * 最優(yōu)解：最優(yōu)解：x x1 1* * = 1 x = 1 x2 2* * = 0 x = 0 x3 3* * = 1 = 1 此時，此時，z z* * = 8 = 8例： 用窮舉法解0-1整數(shù)規(guī)劃1 , 0,322228232243max32132132321321321xxxxxxxxxxxxxxxxxS321xxx最優(yōu)解為最優(yōu)值為S=3., 0, 0, 1321xxx解：對于這個問題，很容易建立一個數(shù)學模型的，解：對于這個問題，很容易建立一個數(shù)學模型的， 引入引入0-1變量變量 ， 當當 =1時，表示分配第時，表示分配第i個人完成第個人完成第j項

27、任務項任務 當當 =0時，表示不分配第時，表示不分配第i個人完成第個人完成第j項任務項任務 一項任務只由一個人完成，有如下約束一項任務只由一個人完成，有如下約束 一人只能完成一項任務，有如下約束一人只能完成一項任務，有如下約束 設設 工作人做不分配第工作人做分配第jijixij01數(shù)學模型如下：數(shù)學模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ要求每人做一項工作，約束條件為：要求每人做一項工作，約束條件為： 1111444342413433323124232221

28、14131211xxxxxxxxxxxxxxxx 111144342414433323134232221241312111xxxxxxxxxxxxxxxx：4 ,3,2, 110 jixij、，或或指派問題的數(shù)學模型:nBBB21nAAA21nnnnnnccccccccc212222111211要求每個工人有一項工作,每項工作只有一個工人來作.如何安排使總的效益最好., 2 , 1, .0,1njijixjixijij項工作個人不去做第表示第項工作個人去做第表示分配第設10., 2 , 11., 2 , 11min1111或ijniijnjijninjijijxnjxnixxcS二、指派問題的

29、解法匈牙利法匈牙利法(1955年W.W.Kuhn求解分配問題,使用了匈牙利數(shù)學家Kuhn的兩個定理,故稱匈牙利解法. .)()(,配問題的最優(yōu)解相同配問題的最優(yōu)解與原分目標函數(shù)系數(shù)矩陣的分為則以矩陣的最小元素后得到的新列該行各元素分別減去列中某一行是在系數(shù)矩陣是分配問題目標函數(shù)的設BAbBaAnnijnnij 若方陣中的一部分元素為零,一部分非零,則覆蓋方陣內所有零元素的最小直線數(shù),等于方陣內位于不同行不同列的零元素的最多個數(shù)。根據(jù)定理1,2設計出分配問題的一般解法:第一步:將效率矩陣A的每一行各減去該行的最小元素,再從新矩陣中的各列減去該列的最小元素,得矩陣B;第二步:從有零元素最少的行(列

30、)開始,圈出零元素后劃去同行(列)的其他零元素.若被圈出的零元素恰好布滿B的不同行不同列,則將這些零元素改為1,其余元素改為0,得最優(yōu)分配矩陣.否則轉第三步;分配問題的一般解法詳解: 對沒有被圈出零的打”; 對有的行上所有有零元素的列打; 再對打的列上有被圈出零的行打;第三步:根據(jù)定理2作出覆蓋零元素的最小直線集: 重復 ,直到得不出新打的行,列為止; 對沒有打的行畫橫虛線;對所有打的列畫縱虛線,這就是覆蓋所有零元素的最小直線集,轉第四步;第四步:在沒有被覆蓋的元素中找出最小元素,對沒有畫直線的行上各元素都減去這個最小元素;對畫有直線的列上各元素都加上這個最小元素,這樣得到的矩陣如果不同行不同

31、列上都有被圈出的零,則可將其換為1,其余元素換為0,最優(yōu)分配方案求出,否則轉第三步.例： 某配送中心有 四項配送任務,分配給 四輛汽車 去完成,每輛汽車完成各項配送任務的時間如下表,問如何分配任務使總的用時最少.4321,AAAA4321,BBBB4321AAAA4321BBBB解:取出效率矩陣進行運算.9118713161491514410413152A794224在B中找出位于不同行,不同列的四個零元素,作法如下:24104750111006211130B00102350960607130 先從零元素最少的行(列)開始,選取一個零元素將其圈起來,同時將零元素所在行,列的其余零元素劃去; 如

32、果恰有四個被圈起來的零元素,處于不同行不同列,則將這些零改為1,其余元素改為0,得到最優(yōu)分配方案.00102350960607130B00000100000100101000B最優(yōu)分配方案是: .,34132241ABABABAB最優(yōu)值(即總用時)是minS=4+4+9+11=28.9118713161491514410413152A注意:對于 來說不是最優(yōu)方案,但對整體來說達到最優(yōu),這就是運籌學思想.4B例：工廠有 五個獨立車間,該廠計劃生產五種產品 ,由于產品性質和各車間設備不同,每個車間生產各種產品消耗的資金(萬元)不同,如下表.問如何安排生產任務,使總的耗資最少.54321,AAAAA

33、54321,BBBBB54321AAAAA54321BBBBB解:610710410661415121412177666989797124676726360400895751000003220205263604008957510000032202052636040089575100000322020500414040081135380000342020722 , 6 , 3 , 6 , 5 , 7 , 5 ,10min),(),(),(),(),(5534134221BABABABABA).(3266767min萬元S4347511576469637964589117129118957 713

34、2036304520142405263402-1 -2 5032015304310140305242402 50320153043101403052424022 2）試指派（找獨立）試指派（找獨立0 0元素）元素） 獨立獨立0 0元素的個數(shù)元素的個數(shù)l l4545，故畫直線調整矩陣。，故畫直線調整矩陣。 5032015304310140305242402選擇直線外的最小元素選擇直線外的最小元素為為1；直線外元素減；直線外元素減1，直線交點元素加直線交點元素加1，其，其他保持不變。他保持不變。 5033004203310240306231301l =m=4 n=5選擇直線外最小元素為選擇直線外最小元素為1，直線外元素減直線外元素減1，直線交點，直線交點元素加元素加1，其他保持不變，其他保持不變，得到新的系數(shù)矩陣。得到新的系數(shù)矩陣。 6044003202300230206130300總費用為總費用為=5+7+6+6+4=28=5+7+6+6+4=28注：此問題有多個最優(yōu)解注：此問題有多個最優(yōu)解 6044003202300230206130300總費用為總費用為=7+9+4+3+5=28=7+9+4+3+5=28 6044003202300230206130300總費用為總費用為=8+9+4+3+4=28=8