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

第四章 整數(shù)規(guī)劃與分配問題,數(shù)學模型 割平面法 分枝定界法 0-1整數(shù)規(guī)劃 分配問題,整數(shù)規(guī)劃,Integer Linear Programming,簡述,LP雖然用途廣泛，但經(jīng)常地，客觀上要求 L.P.最優(yōu)解中不能含有非整數(shù)值（如股票的購買之解答），整數(shù)規(guī)劃就是專門用來求解這類問題的有效工具 重點掌握：0-1 規(guī)劃靈活應用、分枝定界法。,提出問題,某廠生產(chǎn)A1，A2兩種品牌電視，用B1，B2兩種原料，具體數(shù)據(jù)如下，求如何安排生產(chǎn)使利潤最大,整數(shù)規(guī)劃,數(shù)學模型,若所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃pure integer linear programming 若部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃mixed integer linear programming 若xj 只取0或1，成為0-1整數(shù)規(guī)劃zero-one integer linear programming,松弛問題,整數(shù)規(guī)劃,整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解,注 釋,最優(yōu)解不一定在頂點上達到 最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)解 整數(shù)可行解遠多于頂點，枚舉法不可取,整數(shù)規(guī)劃問題的求解方法,分枝定界法branch and bound method 分枝定界法是一種隱枚舉方法（implicit enumeration）或部分枚舉方法，是枚舉方法基礎上的改進，幾乎所有的計算機計算都用此算法。其關鍵是分支和定界。 例,Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0 X1 ， X2 取整數(shù),s.t.,6,分支定界法,思路與解題步驟 只解松弛問題 1、在全部可行域上解松弛問題 若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解 2、分枝過程 若松弛問題最優(yōu)解中某個 xk=bk 不是整數(shù)，令 bk 為 bk 的整數(shù)部分 構造兩個新的約束條件 xk bk 和 xk bk +1，分別加于原松弛問題，形成兩個新的整數(shù)規(guī)劃 3、求解分枝的松弛問題 定界過程 設兩個分枝的松弛問題分別為問題 1 和問題 2 ，它們的最優(yōu)解有如下情況,整數(shù)規(guī)劃,分支問題解可能出現(xiàn)的情況,情況 2, 4, 5 找到最優(yōu)解 情況 3 在縮減的域上繼續(xù)分枝定界法 情況 6 問題 1 的整數(shù)解作為界被保留，用于以后與問題 2 的后續(xù)分枝所得到的解進行比較，結論如情況 4或5,整數(shù)規(guī)劃,分支定界法圖解整數(shù)規(guī)劃,松弛問題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,該整數(shù)規(guī)劃松弛問題的解為： （X1 ，X2 ）=（3/2 ,10/3） Z1 = 29/6,14X1 + 9X2 51,- 6X1 + 3X2 1,51/14,1/3,9,整數(shù)規(guī)劃 Integer Programming（IP）,分支定界法圖解整數(shù)規(guī)劃,松弛問題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,（3/2 ，10/3） Z1 = 29/6,B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,B2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0,B2：解 （1,7/3 ） Z21 = 17/3,B1：解 （2,23/9 ） Z11 = 41/9,1,2,10,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問題的求解方法 分支定界法圖解整數(shù)規(guī)劃,（3/2 ,10/3） Z1 = 29/6,B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,B2：解 （1,7/3 ） Z21 = 17/3,B1：解 （2,23/9 ） Z11 = 41/9,B11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0,B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B12：解 （33/14,2 ） Z12 = 61/14,1 2,X=2,X=3,11,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問題的求解方法 分支定界法圖解整數(shù)規(guī)劃,（3/2 ，10/3） Z1 = 29/6,B2：解 （1,7/3 ） Z21 = 17/3,B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B12：解 （33/14,2 ） Z12 = 61/14,B121 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0,B122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B121：解 （3，1 ） Z121 = 4,B122：解 （2，2 ） Z122 = 4,B1：解 （2，23/9 ） Z11 = 41/9,1 2 3,12,割平面法cutting plane approach,割平面法求解整數(shù)規(guī)劃問題時，若其松馳問題的最優(yōu)解 X* 不滿足整數(shù)要求時，則從 X* 的非整分量中選取一個，用以構造一個線性約束條件（Gomory 割平面），將其加入原松馳問題中，形成一個新的線性規(guī)劃，然后求解之。其關鍵在于新增加的這個線性約束條件將切割掉部分非整數(shù)解，至少將當前松馳問題的非整數(shù)最優(yōu)解切割掉了，而不會切割掉問題的任何整數(shù)解。,13,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問題的求解方法 割平面法cutting plane approach 構造切割方程的步驟： 1、令 xi 是相應松馳問題的最優(yōu)解中為非整數(shù)值的一個基變量，由單純形表最終表得： xi + aik xk = bi （1 式） 其中 i Q （Q 指基變量下標集） k K （K 指非基變量下標集）,14,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問題的求解方法 割平面法cutting plane approach 構造切割方程的步驟： 2、將 bi 和 aik 都分解成整數(shù)部分 N （不超過 b 的最大整數(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,15,整數(shù)規(guī)劃 Integer Programming（IP）,割平面法cutting plane approach 構造切割方程的步驟： 2、將（2 式）代入（1 式）得： xi + Nik xk - Ni = fi - fik xk （3 式） 3、提出變量為整（當然含非負）的條件： 由于（3 式）中等式左邊需整，而 0 fi 1 ，故有 fi - fik xk 0 （4 式） 此即為所需切割方程。,16,整數(shù)規(guī)劃 Integer Programming（IP）,割平面法cutting plane approach 構造切割方程的步驟： （1）切割方程 fi - fik xk 0 真正進行了切割，至少把非整數(shù)最優(yōu)解這一點切割掉了。 證明：（反證法）假設松馳問題的最優(yōu)解 X* 未被切割掉，則由 fi - fik x*k 0， 又因為 x*k = 0，（因 x*k 為非基變量） 有 fi 0 ，這與 fi 0 矛盾。 （2）不會切割掉任何整數(shù)解，因為切割方程是由變量為整的條件提出的。,17,整數(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ù),LP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0,18,1、求解 LP 得到非整數(shù)最優(yōu)解： X =（3/4，7/4，0，0），Max Z = 5/2,求解步驟：,19,整數(shù)規(guī)劃 Integer Programming（IP）,求解步驟： 2、構造切割方程： 由 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,20,整數(shù)規(guī)劃 Integer Programming（IP）,求解步驟： 3、求解新的松弛問題,21,0-1整數(shù)規(guī)劃問題,0-1 變量及其應用 0-1變量作為邏輯變量（Logical variable），常常被引用來表示系統(tǒng)是否處于某個特定的狀態(tài)，或者決策變量是否取某個特定的方案。,xj =,1 當決策取方案 P j 時 0 當決策不取方案 Pj 時,22,0-1整數(shù)規(guī)劃,一、項目選定(選址）問題,整數(shù)規(guī)劃,在經(jīng)濟全球化的時代，許多公司為在全球范圍內最優(yōu)地配置資源（如獲取廉價勞動力或原料等），要在不同地方建廠或倉庫及其他服務設施，這些都要進行項目或地址的選擇。在選址之前，許多侯選地點要進行分析和比較，而每個決策都涉及到一個選還是不選的問題。,案例一,某銷售公司打算通過在武漢或長春設立分公司（也許兩個城市都設）增加市場份額，管理層同時也計劃在新設分公司的城市最多建一個配送中心，當然也可以不建配送中心。經(jīng)過計算，每種選擇對公司收益的凈現(xiàn)值、所需費用列在下表中，總預算投資費用不得超過20萬。如何決策使總凈現(xiàn)值最大,設 xj=,10,- 決策j問題的答案是“是” - 決策j問題的答案是“否”,max z = 18x1 + 10x2 + 12x3+8x4,最優(yōu)解 x1 =1，x2=1,案例練習,例1：某油田在10個有油氣構造處要選擇若干個鉆探采油，設第j個構造開采時需投資aj元，投產(chǎn)后預計年收凈益為cj元，若該油田投資的總限額為b元，問：應選擇哪幾個構造開采最為有利？,設 xj=,10,- 選擇開采第j個構造 -不選擇開采第j個構造,max z=cjxj,j=1,10,ajxj b,xj0或1 (j=1,2,-,10),j=1,10,-年總收益,-投資額限制,1、表示選擇性決策,若在開采時還需滿足下述條件： （a）若開采8號，則必須同時開采6號； （b）若開采5號，則不許開采3號； （c） 2 號和4號至少開采一個； （d） 8 號與7號必須同時開采； （e）1號、4號、6號、9號開采時不能超過兩個，試表示上述約束條件。,設 xj=,10,- 選擇開采第j個構造 -不選擇開采第j個構造,max z=cjxj,j=1,10,ajxj b,xj0或1 (j=1,2,-,10),j=1,10,-年總收益,-投資額限制,（a）當x8=1,x6=1，x60,當x8=0,x6=1，x6=0, x8 x6,（b）當x5 =1,x3=0， x3 1,當x5 =0,x3=0， x3 =1, x5 + x3 1,（c） x2 + x4 1,（d） x8 = x7,（e） x1 + x4 + x6 + x9 2,在生產(chǎn)或經(jīng)營過程中，某一個業(yè)務活動開展通常伴隨著固定成本的發(fā)生，比如添置或起用設備，新采購材料時產(chǎn)生的差旅費，對工人必要培訓的費用等，這些構成產(chǎn)品的固定成本。這時，業(yè)務活動的總成本就包括與活動數(shù)量大小相關的變動成本和起動活動的固定成本。,二 固定費用（成本）問題,案例,某工廠近期接到一批訂單，要安排生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，每件產(chǎn)品分別需要原料A、B、C中的一種或幾種中的若干單位，合同規(guī)定要在15天內完成，但數(shù)量不限。由于四種產(chǎn)品都在同一種設備上生產(chǎn)，且一臺設備同一時間只能加工一件產(chǎn)品。目前，工廠只有一臺正使用中的這種設備（設備1），合同期內可擠出3天來生產(chǎn)訂單，但會產(chǎn)生150元的機會成本損失；還有一臺長期未用的設備（設備2）可以啟用，啟用時要做必要的檢查和修理，費用1000元；公司還考慮向鄰廠租用2臺（設備3，4），由于對方也在統(tǒng)籌使用，租期分別只能7和12天，租金分別2000和3100，工廠可以決定租一臺或兩臺，也可以一臺不租。另外，每種產(chǎn)品如果生產(chǎn)會有固定成本和變動成本，具體如下表，假設每天工作8小時，工廠最多使用3臺設備，問：工廠如何生產(chǎn)和利用設備，利潤最大,24 120 56 96 150 1000 2000 3100,例 應用 0-1 變量解決含互斥約束條件問題 設：工序 B 有兩種方式完成 方式（1 ）的工時約束為 0.3X1 + 0.5X2 150 方式（2 ）的工時約束為 0.2X1 + 0.4X2 120 問題是完成工序 B 只能從兩種方式中任選一種，如何將這兩個互斥的約束條件統(tǒng)一在一個線性規(guī)劃模型中呢？,三 互相排斥問題,32,例 7 應用 0-1 變量解決含互斥約束條件問題 引入 0-1 變量,y1 =,0 若工序 B 采用方式（1 ）完成 1 若工序 B 不采用方式（1 ）完成,y2 =,0 若工序 B 采用方式（2 ）完成 1 若工序 B 不采用方式（2 ）完成,三 互相排斥問題,33,例 7 應用 0-1 變量解決含互斥約束條件問題 于是前面兩個互斥的約束條件可以統(tǒng)一為如下三個約束條件： 0.3X1 + 0.5X2 150 + M1y1 0.2X1 + 0.4X2 120 + M2y2 y1 + y2 = 1 其中 M1 ，M2 都是足夠大的正數(shù)。,三 互相排斥問題,34,案例,因為資金和管理水平的限制，某公司想以相同的價格和不同的租期（工時）租賃另一公司甲、乙、丙、丁四個車間中的兩個，來生產(chǎn)五種新開發(fā)的產(chǎn)品（A、B、C、D、E）中的最多三種。由于車間的機床和工人的經(jīng)驗不同，生產(chǎn)不同產(chǎn)品的效率也不同，導致不同產(chǎn)品（任一階段）在不同的車間生產(chǎn)所用的工時數(shù)不同（根據(jù)生產(chǎn)部的初步實驗和經(jīng)驗判斷估計出的數(shù)據(jù)見下表）另外，根據(jù)公司市場部的預測，每種產(chǎn)品的單位利潤和在租期內最大的銷售量以及各車間在租期內的總工時數(shù)等也見表）,取M=1000，得X1=20，X3=23，X4=2，Z=434,0-1整數(shù)規(guī)劃的解法,枚舉法 隱枚舉法,整數(shù)規(guī)劃,指派(分配）問題,例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最少（每人只譯一種）,整數(shù)規(guī)劃,指派問題的標準形式及其數(shù)學模型 指派問題的標準形式（以人和事為例）是： 有 n 個人和 n 件事，已知第 i 人做第 j 事的費用為 Cij（i，j = 1，2，n），要求確定人和事之間的一一對應的指派方案，使完成這件事的總費用最少。如,指派問題（assignment problem）,例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最少（每人只譯一種）,39,建立模型：,設 xij=,1,0,譯英文：,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,?。?x14+ x24 + x34 + x44 =1,xij =0或1 (i=1,2,3,4; j=1,2,3,4),Min z= aijxij (aij-效率),i=1j=1,4 4,若第i項工作交與第j個人完成,若第i項工作不交與第j個人完成,一般模型,指派問題的標準形式，令,1 當指派第 i 人完成第 j 項任務 0 當不指派第 i 人完成第 j 項任務,xij =,min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij = 1 或 0,41,匈牙利解法,標準的指派問題是一類特殊的 0-1 整數(shù)規(guī)劃問題，可以用多種相應的解法來求解。但是，這些方法都沒有充分利用指派問題的特殊性質來有效減少計算量。1955年，庫恩（W.W.Kuhn）利用匈牙利數(shù)學家康尼格（D.Knig）的關于矩陣中獨立零元素的定理，提出了指派問題的一種解法，由此，習慣上稱之為匈牙利解法。,42,匈牙利解法的關鍵是利用了指派問題最優(yōu)解的如下性質： 若從指派問題的系數(shù)矩陣 C = （ cij ）nn 的某行（或某列）各元素分別減去一個常數(shù) k ，得到一個新的系數(shù)矩陣C = （ cij ）則以 C 和 C 為系數(shù)矩陣的兩個指派問題有相同的最優(yōu)解。,匈牙利解法,43,步驟一： 變換系數(shù)矩陣。使其每行及每列至少有一個零元素，同時不出現(xiàn)負元素。 步驟二： 進行試指派，即確定獨立零元素。 步驟三： 繼續(xù)變換系數(shù)矩陣，然后返回步驟二。,匈牙利解法的一般步驟,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 2,2 4 9 7,min,（ cij ）=,匈牙利解法的一般步驟,45,指派問題（assignment problem） 匈牙利解法的一般步驟 以上例說明步驟,0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2,0 0 4 2,min,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,= （ cij ）,指派問題（assignment problem）,46,以上例說明步驟,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,此時加圈 0 元素的個數(shù) m = n = 4，所以得到最優(yōu)解,指派問題（assignment problem）,47,匈牙利解法的一般步驟 以上例說明步驟,0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0,（ xij ）=,指派問題（assignment problem）,48,匈牙利解法的一般步驟 例,指派問題（assignment problem）,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 9,7 6 7 6 4,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）,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 元素的個數(shù) m = 4， 而n = 5，所以解題沒有完成。獨立零元素（加圈零元素）少于 n 個，表示還不能確定最優(yōu)指派方案。此時需確定能覆蓋所有零元素的最少直線數(shù)目的直線集合。方法如下：,指派問題（assignment problem）,51,匈牙利解法的一般步驟,對沒有加圈零元素的行打號； 對所有打號行的所有含零元素的列打號； 再對已打號的列中含零元素的行打號； 重復2）和3），直到再也不能找到可以打號行或列為止； 對沒有打號的行畫一橫線，對打號的列畫一豎線，這樣就得到能覆蓋所有零元素的最少直線數(shù)目的直線集合。,指派問題（assignment problem）,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 problem）,53,匈牙利解法的一般步驟 繼續(xù)變換系數(shù)矩陣。其方法是在未被直線覆蓋的元素中找出一個最小元素。然后在打號行各元素都減去這一最小元素，而在打號列的各元素都加上這一最小元素，以保證原來的 0 元素不變。這樣得到新系數(shù)矩陣（其最優(yōu)解和原問題相同）。若得到 n 個獨立的 0 元素，則已得最優(yōu)解，否則重復該步驟繼續(xù)變換系數(shù)矩陣。,指派問題（assignment problem）,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）,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,此時加圈 0 元素的個數(shù) m = 5， 而n = 5，獨立零元素（加圈零元素）等于 n 個，此時已得到最優(yōu)解，其解矩陣為,指派問題（assignment problem）,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)指派： 甲 B 乙 C 丙 E 丁 D 戊 A,指派問題（assignment problem）,57,在實際應用中，常會遇到各種非標準形式的制派問題。一般的處理方法是先將其轉化為標準形式，然后再用匈牙利法求解。 最大化指派問題設最大化指派問題系數(shù)矩陣