最新整數(shù)規(guī)劃問題

1、整數(shù)規(guī)劃問題第四章第四章 整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃與分配問題數(shù)學(xué)模型割平面法分枝定界法0-1整數(shù)規(guī)劃分配問題整數(shù)規(guī)劃整數(shù)規(guī)劃Integer Linear ProgrammingInteger Linear Programming整數(shù)規(guī)劃問題簡述簡述LP雖然用途廣泛，但經(jīng)常地，客觀上要求 L.P.最優(yōu)解中不能含有非整數(shù)值（如股票的購買之解答），整數(shù)規(guī)劃就是專門用來求解這類問題的有效工具重點掌握重點掌握：0-1 規(guī)劃靈活應(yīng)用、分枝定界法。整數(shù)規(guī)劃問題提出問題提出問題 某廠生產(chǎn)A1，A2兩種品牌電視，用B1，B2兩種原料，具體數(shù)據(jù)如下，求如何安排生產(chǎn)使利潤最大整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題數(shù)學(xué)模型數(shù)

2、學(xué)模型njxxmibxatsxczjjnjijijnjjj, 2 , 10, 2 , 1,),(. .max(min)11部分或全部為整數(shù)若所有若所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃的解為整數(shù)，稱為純整數(shù)規(guī)劃pure integer linear programming若部分若部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃的解為整數(shù)，稱為混合整數(shù)規(guī)劃mixed integer linear programming若若xj 只取只取0或或1，成為，成為0-1整數(shù)規(guī)劃整數(shù)規(guī)劃zero-one integer linear programming松弛問題松弛問題整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其

3、松弛問題的最優(yōu)解整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解整數(shù)規(guī)劃問題注 釋 最優(yōu)解不一定在頂點上達到最優(yōu)解不一定在頂點上達到 最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)解數(shù)解 整數(shù)可行解遠多于頂點，枚舉法不可取整數(shù)可行解遠多于頂點，枚舉法不可取整數(shù)規(guī)劃問題6整數(shù)規(guī)劃問題的求解方法整數(shù)規(guī)劃問題的求解方法分枝定界法分枝定界法branch and bound method 分枝定界法是一種隱枚舉方法（分枝定界法是一種隱枚舉方法（implicit enumeration）或部分或部分枚舉方法，是枚舉方法基礎(chǔ)上的改進，幾乎所有的計算機計算都用枚舉方法，是枚舉方法基礎(chǔ)上的

4、改進，幾乎所有的計算機計算都用此算法。其關(guān)鍵是分支和定界。此算法。其關(guān)鍵是分支和定界。例例 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0 X1 ， X2 取整數(shù)取整數(shù)s.t.整數(shù)規(guī)劃問題分支定界法分支定界法思路與解題步驟思路與解題步驟 只解松弛問題只解松弛問題1、在全部可行域上解松弛問題、在全部可行域上解松弛問題 若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解優(yōu)解2、分枝過程、分枝過程 若松弛問題最優(yōu)解中某個若松弛問題最優(yōu)解中某個 xk=bk 不是整數(shù)，令不是整數(shù)，令 bk 為為 b

5、k 的整數(shù)部分的整數(shù)部分 構(gòu)造兩個新的約束條件構(gòu)造兩個新的約束條件 xk bk 和和 xk bk +1，分別分別加于原松弛問題，形成兩個新的整數(shù)規(guī)劃加于原松弛問題，形成兩個新的整數(shù)規(guī)劃3、求解分枝的松弛問題、求解分枝的松弛問題 定界過程定界過程 設(shè)兩個分枝的松弛問題分別為問題設(shè)兩個分枝的松弛問題分別為問題 1 和問題和問題 2 ，它們，它們的最優(yōu)解有如下情況的最優(yōu)解有如下情況 整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題分支問題解可能出現(xiàn)的情況分支問題解可能出現(xiàn)的情況情況情況 2, 4, 5 找到最優(yōu)解找到最優(yōu)解情況情況 3 在縮減的域上繼續(xù)分枝定界法在縮減的域上繼續(xù)分枝定界法情況情況 6 問題問題 1 的整

6、數(shù)解作為的整數(shù)解作為界界被保留，用于以后與問題被保留，用于以后與問題 2 的后續(xù)分枝所得到的解進行比較，結(jié)論如情況的后續(xù)分枝所得到的解進行比較，結(jié)論如情況 4或或5整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題9分支定界法圖解整數(shù)規(guī)劃分支定界法圖解整數(shù)規(guī)劃 松弛問題松弛問題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0該整數(shù)規(guī)劃松弛問題的解為：該整數(shù)規(guī)劃松弛問題的解為：（X1 ，X2 ）=（3/2 ,10/3）Z1 = 29/614X1 + 9X2 51- 6X1 + 3X2 151/141/3整數(shù)規(guī)劃問題10整數(shù)規(guī)劃 Integer Program

7、ming（IP）分支定界法圖解整數(shù)規(guī)劃分支定界法圖解整數(shù)規(guī)劃松弛問題松弛問題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0（3/2 ，10/3）Z1 = 29/6B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0B2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0B2：解解（1,7/3 ）Z21 = 17/3B1：解解（2,23/9 ）Z11 = 41/912B1B2整數(shù)規(guī)劃問題11整數(shù)規(guī)劃

8、Integer Programming（IP）整數(shù)規(guī)劃問題的求解方法整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃分支定界法圖解整數(shù)規(guī)劃（3/2 ,10/3）Z1 = 29/6B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0B2：解解（1,7/3 ）Z21 = 17/3B1：解解（2,23/9 ）Z11 = 41/9B11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X

9、1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B12：解解（33/14,2 ）Z12 = 61/141 2X=2X=3整數(shù)規(guī)劃問題12整數(shù)規(guī)劃 Integer Programming（IP）整數(shù)規(guī)劃問題的求解方法整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃分支定界法圖解整數(shù)規(guī)劃（3/2 ，10/3）Z1 = 29/6B2：解解（1,7/3 ）Z21 = 17/3B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B12：解解（33/14,2 ）Z12 = 61/14B121 Max Z = X1 +

10、X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0B122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B121：解解（3，1 ）Z121 = 4B122：解解（2，2 ）Z122 = 4B1：解解（2，23/9 ）Z11 = 41/9 1 2 3整數(shù)規(guī)劃問題13割平面法割平面法cutting plane approach割平面法求解整數(shù)規(guī)劃問題時，若其松馳問題的最優(yōu)解割平面法求解整數(shù)規(guī)劃問題時，若其松馳問題的最優(yōu)解 X* 不滿足不滿足整數(shù)要求時，則從整數(shù)要求時，

11、則從 X* 的非整分量中選取一個，用以構(gòu)造一個線性的非整分量中選取一個，用以構(gòu)造一個線性約束條件（約束條件（Gomory 割平面），將其加入原松馳問題中，形成一個割平面），將其加入原松馳問題中，形成一個新的線性規(guī)劃，然后求解之。其關(guān)鍵在于新增加的這個線性約束條新的線性規(guī)劃，然后求解之。其關(guān)鍵在于新增加的這個線性約束條件將切割掉部分非整數(shù)解，至少將當前松馳問題的非整數(shù)最優(yōu)解切件將切割掉部分非整數(shù)解，至少將當前松馳問題的非整數(shù)最優(yōu)解切割掉了，而割掉了，而不會切割掉問題的任何整數(shù)解不會切割掉問題的任何整數(shù)解。整數(shù)規(guī)劃問題14整數(shù)規(guī)劃 Integer Programming（IP）整數(shù)規(guī)劃問題的求解方

12、法整數(shù)規(guī)劃問題的求解方法割平面法割平面法cutting plane approach 構(gòu)造切割方程的步驟：構(gòu)造切割方程的步驟：1、令、令 xi 是相應(yīng)松馳問題的最優(yōu)解中為非整數(shù)值的一個基變量，由是相應(yīng)松馳問題的最優(yōu)解中為非整數(shù)值的一個基變量，由單純形表最終表得：單純形表最終表得： xi + aik xk = bi （1 式）式）其中其中 i Q （Q 指基變量下標集）指基變量下標集） k K （K 指非基變量下標集）指非基變量下標集）整數(shù)規(guī)劃問題15整數(shù)規(guī)劃 Integer Programming（IP）整數(shù)規(guī)劃問題的求解方法整數(shù)規(guī)劃問題的求解方法割平面法割平面法cutting plane a

13、pproach 構(gòu)造切割方程的步驟：構(gòu)造切割方程的步驟：2、將、將 bi 和和 aik 都分解成整數(shù)部分都分解成整數(shù)部分 N （不超過不超過 b 的最大整數(shù)）與非的最大整數(shù)）與非負真分數(shù)部分負真分數(shù)部分 f 之和，即：之和，即： bi = Ni + fi ， 其中其中 0 fi 1 （2 式）式） aik = Nik + fik ，其中其中 0 fik 1例如：若例如：若 b = 2.35 ，則則 N = 2 ，f = 0.35； 若若 b = -1.45 ，則則 N = -2 ，f = 0.55整數(shù)規(guī)劃問題16整數(shù)規(guī)劃 Integer Programming（IP）割平面法割平面法cutti

14、ng plane approach 構(gòu)造切割方程的步驟：構(gòu)造切割方程的步驟：2、將（、將（2 式）代入（式）代入（1 式）得：式）得： xi + Nik xk - Ni = fi - fik xk （3 式）式）3、提出變量為整（當然含非負）的條件：、提出變量為整（當然含非負）的條件：由于（由于（3 式）中等式左邊需整，而式）中等式左邊需整，而 0 fi 1 ，故有故有 fi - fik xk 0 （4 式）式）此即為所需切割方程。此即為所需切割方程。整數(shù)規(guī)劃問題17整數(shù)規(guī)劃 Integer Programming（IP）割平面法割平面法cutting plane approach 構(gòu)造切割方

15、程的步驟：構(gòu)造切割方程的步驟：（1）切割方程）切割方程 fi - fik xk 0 真正進行了切割，至少把非整數(shù)最優(yōu)真正進行了切割，至少把非整數(shù)最優(yōu)解這一點切割掉了。解這一點切割掉了。證明：（反證法）假設(shè)松馳問題的最優(yōu)解證明：（反證法）假設(shè)松馳問題的最優(yōu)解 X* 未被切割掉，則由未被切割掉，則由 fi - fik x*k 0， 又因為又因為 x*k = 0，（，（因因 x*k 為非基變量）為非基變量） 有有 fi 0 ，這與這與 fi 0 矛盾。矛盾。（2）不會切割掉任何整數(shù)解，因為切割方程是由變量為整的條件）不會切割掉任何整數(shù)解，因為切割方程是由變量為整的條件提出的。提出的。整數(shù)規(guī)劃問題18

16、整數(shù)規(guī)劃 Integer Programming（IP）割平面法割平面法cutting plane approach例例求解求解IP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0 X1 ，X2 整數(shù)整數(shù)LP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0整數(shù)規(guī)劃問題191、求解、求解 LP 得到非整數(shù)最優(yōu)解：得到非整數(shù)最優(yōu)解： X =（3/4，7/4，0，0），），Max Z = 5/2求解步驟：求解步驟：整數(shù)規(guī)劃問題20整數(shù)規(guī)劃 Integer Programming（IP）求解步驟求解步驟：2

17、、構(gòu)造切割方程：、構(gòu)造切割方程： 由由 B 表表中的第中的第 2 個方程個方程 X2 + 3/4 X3 + 1/4 X4 = 7/4 有有 b2 = 7/4 = 1 + 3/4 a23 = 3/4 = 0 + 3/4 ， a24 = 1/4 = 0 + 1/4 因此，切割方程為因此，切割方程為 3/4 3/4 X3 1/4 X4 0 增加松弛變量增加松弛變量 X5 ，并將如下方程的約束條件添加到并將如下方程的約束條件添加到 B 表中。表中。 - 3 X3 - 1 X4 + X5 = - 3 X5 0整數(shù)規(guī)劃問題21整數(shù)規(guī)劃 Integer Programming（IP）求解步驟：求解步驟：3、

18、求解新的松弛問題、求解新的松弛問題 整數(shù)規(guī)劃問題220-1整數(shù)規(guī)劃問題整數(shù)規(guī)劃問題0-1 變量及其應(yīng)用變量及其應(yīng)用 0-1變量作為邏輯變量（變量作為邏輯變量（Logical variable），），常常被引用來表示常常被引用來表示系統(tǒng)是否處于某個特定的狀態(tài)，或者決策變量是否取某個特定的方系統(tǒng)是否處于某個特定的狀態(tài)，或者決策變量是否取某個特定的方案。案。xj = 1 當決策取方案當決策取方案 P j 時時0 當決策不取方案當決策不取方案 Pj 時時整數(shù)規(guī)劃問題0-1整數(shù)規(guī)劃整數(shù)規(guī)劃一、項目選定一、項目選定(選址）問題選址）問題整數(shù)規(guī)劃整數(shù)規(guī)劃 在在經(jīng)濟全球化經(jīng)濟全球化的時代，許多公司為在全球的時

19、代，許多公司為在全球范圍內(nèi)范圍內(nèi)最優(yōu)地配置資源最優(yōu)地配置資源（如獲取廉價勞動（如獲取廉價勞動力或原料等），要在不同地方建廠或倉庫力或原料等），要在不同地方建廠或倉庫及其他服務(wù)設(shè)施，這些都要進行項目或地及其他服務(wù)設(shè)施，這些都要進行項目或地址的選擇。在選址之前，許多侯選地點要址的選擇。在選址之前，許多侯選地點要進行分析和比較，而每個決策都涉及到一進行分析和比較，而每個決策都涉及到一個個選選還是還是不選不選的問題。的問題。整數(shù)規(guī)劃問題案例一案例一 某銷售公司打算通過在武漢或長春設(shè)立分公司（也許兩個城某銷售公司打算通過在武漢或長春設(shè)立分公司（也許兩個城市都設(shè)）增加市場份額，管理層同時也計劃在新設(shè)分公司

20、的市都設(shè)）增加市場份額，管理層同時也計劃在新設(shè)分公司的城市最多建一個配送中心，當然也可以不建配送中心。經(jīng)過城市最多建一個配送中心，當然也可以不建配送中心。經(jīng)過計算，每種選擇對公司收益的凈現(xiàn)值、所需費用列在下表中，計算，每種選擇對公司收益的凈現(xiàn)值、所需費用列在下表中，總預(yù)算投資費用不得超過總預(yù)算投資費用不得超過20萬。如何決策使總凈現(xiàn)值最大萬。如何決策使總凈現(xiàn)值最大整數(shù)規(guī)劃問題設(shè) xj=10- 決策j問題的答案是“是” - 決策j問題的答案是“否” max z = 18x1 + 10 x2 + 12x3+8x4 12x1 +6 x2 +10 x3+ 4x4 20 x3+ x4 1 （建建1個配送

21、中心）個配送中心） x3 x1 x4 x2 xj = 0或或1(j=1,2,3,4)最優(yōu)解最優(yōu)解 x1 =1，x2=1整數(shù)規(guī)劃問題案例練習(xí)案例練習(xí) 例1：某油田在10個有油氣構(gòu)造處要選擇若干個鉆探采油，設(shè)第j個構(gòu)造開采時需投資aj元，投產(chǎn)后預(yù)計年收凈益為cj元，若該油田投資的總限額為b元，問：應(yīng)選擇哪幾個構(gòu)造開采最為有利？設(shè) xj=10- 選擇開采第j個構(gòu)造 -不選擇開采第j個構(gòu)造max z=cjxjj=110ajxj bxj0或1 (j=1,2,-,10)j=110-年總收益-投資額限制1、表示選擇性決策若在開采時還需滿足下述條件： （a）若開采8號，則必須同時開采6號； （b）若開采5號，

22、則不許開采3號； （c） 2 號和4號至少開采一個； （d） 8 號與7號必須同時開采； （e）1號、4號、6號、9號開采時不能超過兩個，試表示上述約束條件。整數(shù)規(guī)劃問題設(shè) xj=10- 選擇開采第j個構(gòu)造 -不選擇開采第j個構(gòu)造max z=cjxjj=110ajxj bxj0或1 (j=1,2,-,10)j=110-年總收益-投資額限制整數(shù)規(guī)劃問題（a）當當x8=1x6=1，x60當當x8=0 x6=1，x6=0 x8 x6（b）當當x5 =1x3=0， x3 1當當x5 =0 x3=0， x3 =1 x5 + x3 1（c） x2 + x4 1（d） x8 = x7（e） x1 + x4

23、+ x6 + x9 2整數(shù)規(guī)劃問題 在生產(chǎn)或經(jīng)營過程中，某一個業(yè)務(wù)活動在生產(chǎn)或經(jīng)營過程中，某一個業(yè)務(wù)活動開展通常伴隨著固定成本的發(fā)生，比如開展通常伴隨著固定成本的發(fā)生，比如添置或起用設(shè)備，新采購材料時產(chǎn)生的添置或起用設(shè)備，新采購材料時產(chǎn)生的差旅費，對工人必要培訓(xùn)的費用等，這差旅費，對工人必要培訓(xùn)的費用等，這些構(gòu)成產(chǎn)品的固定成本。這時，業(yè)務(wù)活些構(gòu)成產(chǎn)品的固定成本。這時，業(yè)務(wù)活動的總成本就包括與活動數(shù)量大小相關(guān)動的總成本就包括與活動數(shù)量大小相關(guān)的的變動成本變動成本和起動活動的和起動活動的固定成本固定成本。二二 固定費用（成本）問題固定費用（成本）問題整數(shù)規(guī)劃問題案例案例某工廠近期接到一批訂單，要安

24、排生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，每件產(chǎn)品分別需要原料某工廠近期接到一批訂單，要安排生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，每件產(chǎn)品分別需要原料A、B、C中的一種或幾種中的若干單位，合同規(guī)定要在中的一種或幾種中的若干單位，合同規(guī)定要在15天內(nèi)完成，但數(shù)量不限。由于四種產(chǎn)品都在同天內(nèi)完成，但數(shù)量不限。由于四種產(chǎn)品都在同一種設(shè)備上生產(chǎn)，且一臺設(shè)備同一時間只能加工一件產(chǎn)品。目前，工廠只有一臺正使用中的這種一種設(shè)備上生產(chǎn)，且一臺設(shè)備同一時間只能加工一件產(chǎn)品。目前，工廠只有一臺正使用中的這種設(shè)備（設(shè)備設(shè)備（設(shè)備1），合同期內(nèi)可擠出），合同期內(nèi)可擠出3天來生產(chǎn)訂單，但會產(chǎn)生天來生產(chǎn)訂單，但會產(chǎn)生150元的機會成本損失；還

25、有一臺長元的機會成本損失；還有一臺長期未用的設(shè)備（設(shè)備期未用的設(shè)備（設(shè)備2）可以啟用，啟用時要做必要的檢查和修理，費用）可以啟用，啟用時要做必要的檢查和修理，費用1000元；公司還考慮向元；公司還考慮向鄰廠租用鄰廠租用2臺（設(shè)備臺（設(shè)備3，4），由于對方也在統(tǒng)籌使用，租期分別只能），由于對方也在統(tǒng)籌使用，租期分別只能7和和12天，租金分別天，租金分別2000和和3100，工廠可以決定租一臺或兩臺，也可以一臺不租。另外，每種產(chǎn)品如果生產(chǎn)會有固定成本和，工廠可以決定租一臺或兩臺，也可以一臺不租。另外，每種產(chǎn)品如果生產(chǎn)會有固定成本和變動成本，具體如下表，假設(shè)每天工作變動成本，具體如下表，假設(shè)每天工作

26、8小時，工廠最多使用小時，工廠最多使用3臺設(shè)備，問：工廠如何生產(chǎn)和利用臺設(shè)備，問：工廠如何生產(chǎn)和利用設(shè)備，利潤最大設(shè)備，利潤最大 241205696 150100020003100整數(shù)規(guī)劃問題31例例 應(yīng)用應(yīng)用 0-1 變量解決含互斥約束條件問題變量解決含互斥約束條件問題設(shè)：工序設(shè)：工序 B 有兩種方式完成有兩種方式完成 方式（方式（1 ）的工時約束為）的工時約束為 0.3X1 + 0.5X2 150 方式（方式（2 ）的工時約束為）的工時約束為 0.2X1 + 0.4X2 120 問題是完成工序問題是完成工序 B 只能從兩種方式中任選一種，如何將這兩個只能從兩種方式中任選一種，如何將這兩個互

27、斥的約束條件統(tǒng)一在一個線性規(guī)劃模型中呢？互斥的約束條件統(tǒng)一在一個線性規(guī)劃模型中呢？三三 互相排斥問題互相排斥問題整數(shù)規(guī)劃問題32例例 7 應(yīng)用應(yīng)用 0-1 變量解決含互斥約束條件問題變量解決含互斥約束條件問題引入引入 0-1 變量變量y1 =0 若工序若工序 B 采用方式（采用方式（1 ）完成）完成1 若工序若工序 B 不采用方式（不采用方式（1 ）完成）完成y2 =0 若工序若工序 B 采用方式（采用方式（2 ）完成）完成1 若工序若工序 B 不采用方式（不采用方式（2 ）完成）完成三三 互相排斥問題互相排斥問題整數(shù)規(guī)劃問題33例例 7 應(yīng)用應(yīng)用 0-1 變量解決含互斥約束條件問題變量解決含

28、互斥約束條件問題于是前面兩個互斥的約束條件可以統(tǒng)一為如下三個約束于是前面兩個互斥的約束條件可以統(tǒng)一為如下三個約束條件：條件： 0.3X1 + 0.5X2 150 + M1y1 0.2X1 + 0.4X2 120 + M2y2 y1 + y2 = 1 其中其中 M1 ，M2 都是足夠大的正數(shù)。都是足夠大的正數(shù)。三三 互相排斥問題互相排斥問題整數(shù)規(guī)劃問題案例案例因為資金和管理水平的限制，某公司想以相同的價格和不同的租期（工時）租因為資金和管理水平的限制，某公司想以相同的價格和不同的租期（工時）租賃另一公司甲、乙、丙、丁四個車間中的賃另一公司甲、乙、丙、丁四個車間中的兩個兩個，來生產(chǎn)五種新開發(fā)的產(chǎn)品

29、（，來生產(chǎn)五種新開發(fā)的產(chǎn)品（A、B、C、D、E）中的最多中的最多三種三種。由于車間的機床和工人的經(jīng)驗不同，生產(chǎn)不同。由于車間的機床和工人的經(jīng)驗不同，生產(chǎn)不同產(chǎn)品的效率也不同，導(dǎo)致不同產(chǎn)品（任一階段）在不同的車間生產(chǎn)所用的工時產(chǎn)品的效率也不同，導(dǎo)致不同產(chǎn)品（任一階段）在不同的車間生產(chǎn)所用的工時數(shù)不同（根據(jù)生產(chǎn)部的初步實驗和經(jīng)驗判斷估計出的數(shù)據(jù)見下表）另外，根據(jù)數(shù)不同（根據(jù)生產(chǎn)部的初步實驗和經(jīng)驗判斷估計出的數(shù)據(jù)見下表）另外，根據(jù)公司市場部的預(yù)測，每種產(chǎn)品的單位利潤和在租期內(nèi)最大的銷售量以及各車間公司市場部的預(yù)測，每種產(chǎn)品的單位利潤和在租期內(nèi)最大的銷售量以及各車間在租期內(nèi)的總工時數(shù)等也見表）在租期內(nèi)

30、的總工時數(shù)等也見表）整數(shù)規(guī)劃問題取取M=1000，得得X1=20，X3=23，X4=2，Z=434:1,1,1,2,3,4;1,2,3,4,500max11 114 28 315 49 5)23)jxizjzxxxxxij12生產(chǎn)j第產(chǎn)品的數(shù)量（件）j=1,2,3,4,5租i車間實際生產(chǎn)j產(chǎn)品y，否則，否則5x1+8x2+4x3+9x4+7x5180+M(1-y7x1+11x2+3x3+10 x4+7x50+M(1-y4x1+9x2+3x3+8x4+6x5170+M(1)12342121 1225 2323 3415 4518 512345300101jyyyyxzxzxzxzxzzzzzzx

31、z34ij-y3x1+7x2+5x3+9x4+5x5165+M(1-y且取整，y或 ；或整數(shù)規(guī)劃問題0-1整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法 枚舉法 隱枚舉法整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題指派指派(分配）問題分配）問題例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最少（每人只譯一種）整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題38指派問題的標準形式及其數(shù)學(xué)模型指派問題的標準形式及其數(shù)學(xué)模型指派問題的標準形式（以人和事為例）是：指派問題的標準形式（以人和事為例）是： 有有 n 個人和個人和 n 件事，已知第件事，已知第

32、 i 人做第人做第 j 事的費用為事的費用為 Cij（i，j = 1，2，n），），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這件要求確定人和事之間的一一對應(yīng)的指派方案，使完成這件事的總費用最少。如事的總費用最少。如指派問題（指派問題（assignment problem）例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最少（每人只譯一種）少（

33、每人只譯一種）整數(shù)規(guī)劃問題建立模型：建立模型：設(shè) xij=10譯英文：x11+ x12 + x13 + x14 =1譯日文：x21+ x22 + x23 + x24 =1譯德文：x31+ x32 + x33 + x34 =1譯俄文：x41+ x42 + x43 + x44 =1甲：x11+ x21 + x31 + x41 =1乙：x12+ x22 + x32 + x42 =1丙：x13+ x23 + x33 + x43 =1?。簒14+ x24 + x34 + x44 =1xij =0或1 (i=1,2,3,4; j=1,2,3,4)Min z= aijxij(aij-效率)i=1j=14 4

34、若第i項工作交與第j個人完成若第i項工作不交與第j個人完成整數(shù)規(guī)劃問題40一般模型一般模型指派問題的標準形式，令指派問題的標準形式，令 1 當指派第當指派第 i 人完成第人完成第 j 項任務(wù)項任務(wù) 0 當不指派第當不指派第 i 人完成第人完成第 j 項任務(wù)項任務(wù)xij =min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij = 1 或或 0整數(shù)規(guī)劃問題41匈牙利解法匈牙利解法 標準的指派問題是一類特殊的標準的指派問題是一類特殊的 0-1 整數(shù)規(guī)劃問題，整數(shù)規(guī)劃問題，可以用多種相應(yīng)的解法來求解。但是，這些方法都沒可以用多種相應(yīng)的解法來求

35、解。但是，這些方法都沒有充分利用指派問題的特殊性質(zhì)來有效減少計算量。有充分利用指派問題的特殊性質(zhì)來有效減少計算量。1955年，庫恩（年，庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼利用匈牙利數(shù)學(xué)家康尼格（格（D.Knig）的關(guān)于矩陣中獨立零元素的定理，提的關(guān)于矩陣中獨立零元素的定理，提出了指派問題的一種解法，由此，習(xí)慣上稱之為匈牙出了指派問題的一種解法，由此，習(xí)慣上稱之為匈牙利解法。利解法。整數(shù)規(guī)劃問題42 匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如下下性質(zhì)：性質(zhì)： 若從指派問題的系數(shù)矩陣若從指派問題的系數(shù)矩陣 C = （ cij ）nn 的某的某行（

36、或某列）各元素分別行（或某列）各元素分別減去一個常數(shù)減去一個常數(shù) k ，得到一個得到一個新的系數(shù)矩陣新的系數(shù)矩陣C = （ cij ）則以則以 C 和和 C 為系數(shù)矩陣為系數(shù)矩陣的兩個指派問題有的兩個指派問題有相同的最優(yōu)解相同的最優(yōu)解。匈牙利解法匈牙利解法整數(shù)規(guī)劃問題43步驟一：步驟一： 變換系數(shù)矩陣。使其每行及每列至少變換系數(shù)矩陣。使其每行及每列至少有一個零元素，同時不出現(xiàn)負元素。有一個零元素，同時不出現(xiàn)負元素。步驟二：步驟二： 進行試指派，即確定獨立零元素。進行試指派，即確定獨立零元素。步驟三：步驟三： 繼續(xù)變換系數(shù)矩陣，然后返回步驟二。繼續(xù)變換系數(shù)矩陣，然后返回步驟二。匈牙利解法的一般步

37、驟匈牙利解法的一般步驟整數(shù)規(guī)劃問題44以上例說明步驟以上例說明步驟 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 22497min（ cij ）=匈牙利解法的一般步驟匈牙利解法的一般步驟整數(shù)規(guī)劃問題45指派問題（指派問題（assignment problem）匈牙利解法的一般步驟匈牙利解法的一般步驟以上例說明步驟以上例說明步驟 0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2 0 0 4 2min 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0= （

38、cij ）指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題46以上例說明步驟以上例說明步驟 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此時加圈此時加圈 0 元素的個數(shù)元素的個數(shù) m = n = 4，所以得到最優(yōu)解所以得到最優(yōu)解指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題47匈牙利解法的一般步驟匈牙利解法的一般步驟以上例說明步驟以上例說明步驟 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（ xij ）=指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題48匈牙利解法的一般步驟匈牙利解法的一

39、般步驟例例指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題49匈牙利解法的一般步驟匈牙利解法的一般步驟 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題50匈牙利解法的一般步驟匈牙利解法的一般步驟 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 此時加圈此時加圈 0 元素的

40、個數(shù)元素的個數(shù) m = 4， 而而n = 5，所以解題沒所以解題沒有完成。獨立零元素（加圈零有完成。獨立零元素（加圈零元素）少于元素）少于 n 個，表示還不能個，表示還不能確定最優(yōu)確定最優(yōu)指派方案。此時需確定指派方案。此時需確定能覆蓋所有能覆蓋所有零元素的最少直線數(shù)零元素的最少直線數(shù)目的直線集合。方法如下：目的直線集合。方法如下：指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題51匈牙利解法的一般步驟匈牙利解法的一般步驟對沒有加圈零元素的行打?qū)]有加圈零元素的行打號；號；對所有打?qū)λ写蛱栃械乃泻阍氐牧写蛱栃械乃泻阍氐牧写蛱?；號；再對已打再對已打號的列中含零?/p>

41、素的行打號的列中含零元素的行打號；號；重復(fù)重復(fù)2）和）和3），直到再也不能找到可以打），直到再也不能找到可以打號行號行或列為止；或列為止；對沒有打?qū)]有打號的行畫一橫線，對打號的行畫一橫線，對打號的列畫一豎號的列畫一豎線，這樣就得到線，這樣就得到能覆蓋所有能覆蓋所有零元素的最少直線數(shù)零元素的最少直線數(shù)目的直線集合。目的直線集合。指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題52匈牙利解法的一般步驟匈牙利解法的一般步驟 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5指派問題（指派問題（assignment proble

42、m）整數(shù)規(guī)劃問題53匈牙利解法的一般步驟匈牙利解法的一般步驟 繼續(xù)變換系數(shù)矩陣。其方法是在未被直線覆蓋的繼續(xù)變換系數(shù)矩陣。其方法是在未被直線覆蓋的元素中找出一個最小元素。然后在打元素中找出一個最小元素。然后在打號號行行各元素都各元素都減減去這一最小元素，而在打去這一最小元素，而在打號號列列的各元素都的各元素都加加上這上這一最小元素，以保證原來的一最小元素，以保證原來的 0 元素不變。這樣得到新元素不變。這樣得到新系數(shù)矩陣（其最優(yōu)解和原問題相同）。若得到系數(shù)矩陣（其最優(yōu)解和原問題相同）。若得到 n 個獨個獨立的立的 0 元素，則已得最優(yōu)解，否則重復(fù)該步驟繼續(xù)變元素，則已得最優(yōu)解，否則重復(fù)該步驟繼

43、續(xù)變換系數(shù)矩陣。換系數(shù)矩陣。指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題54匈牙利解法的一般步驟匈牙利解法的一般步驟 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素最小元素= 2 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題55匈牙利解法的一般步驟匈牙利解法的一般步驟 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3 此時加圈此時加

44、圈 0 元素的個數(shù)元素的個數(shù) m = 5， 而而n = 5，獨立零元素獨立零元素（加圈零元素）等于（加圈零元素）等于 n 個，個，此此時已得到最優(yōu)解，其解矩陣為時已得到最優(yōu)解，其解矩陣為指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題56匈牙利解法的一般步驟匈牙利解法的一般步驟（ xij ）= 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 最優(yōu)指派：最優(yōu)指派：甲甲 B乙乙 C丙丙 E丁丁 D戊戊 A指派問題（指派問題（assignment problem）整數(shù)規(guī)劃問題57 在實際應(yīng)用中，常會遇到各種非標準形式的制派問題

45、。一般的在實際應(yīng)用中，常會遇到各種非標準形式的制派問題。一般的處理方法是先將其轉(zhuǎn)化為標準形式，然后再用匈牙利法求解。處理方法是先將其轉(zhuǎn)化為標準形式，然后再用匈牙利法求解。n最大化指派問題最大化指派問題設(shè)最大化指派問題系數(shù)矩陣設(shè)最大化指派問題系數(shù)矩陣 C = （ cij ） ，其中最大元素為其中最大元素為 m 。令矩陣令矩陣 B = （ bij ）= （ m - cij ），），則以則以 B 為系數(shù)矩陣的最小化指派問題和以為系數(shù)矩陣的最小化指派問題和以 C 為系數(shù)矩陣的最大化指為系數(shù)矩陣的最大化指派問題有相同最優(yōu)解。派問題有相同最優(yōu)解。1.人數(shù)和事數(shù)不等的指派問題人數(shù)和事數(shù)不等的指派問題若若人少事多人少事多，則添加一些虛擬，則添加一些虛擬的的“人人”，其費用系數(shù)取，其費用系數(shù)取 0 ，若，若人多事少人多事少，則添加一些虛擬的，則添加一些虛擬的“事事”，其費用系數(shù)取，其費用