第四章整數規劃與分配問題整數規劃的特點及作用分配問題與匈牙利法分枝定界法割平面法應用舉例1ppt課件1整數規劃的特點及應用在實際問題中，全部或部分變量取值必須是整數。比如人或機器是不可分割的，選擇地點可以設置邏輯變量等。在一個線性規劃問題中要求全部變量取整數值的，稱純整數線性規劃或簡稱純整數規劃；只要求一部分變量取整數值的，稱為混合整數規劃。2ppt課件對整數規劃問題求解，有人認為可以不考慮對變量的整數約束，作為一般線性規劃問題求解，當解為非整數時，用四舍五入或湊整方法尋找最優解。當變量取值較小時，得到的解可能與實際整數最優解差別很大。若問題中整數變量的數目很大，則湊整方法的組合數目很多。3ppt課件

例1.

求下述整數規劃問題的最優解解：如果不考慮整數約束（松弛問題）用圖解法得考慮到整數約束，用湊整法求解時，比較四個點(4,3),(4,2),(3,3),(3,2)，前三個都不是可行解，第四個雖然是可行解，但z=13不是最優。實際問題的最優解為（4,1）這時z*=14。最優解為(3.25,2.5)。4ppt課件邏輯（0-1）變量在建立數學模型中的作用1.m個約束條件中只有k

個起作用設

m

個約束條件可以表示為：定義邏輯變量又設

M

為任意大的正數，則約束條件可以改寫為：5ppt課件定義邏輯變量：此時約束條件可以改寫為：2.約束條件的右端項可能是r個值中的某一個即6ppt課件3.兩組條件滿足其中一組

若x1≤4，則x2≥1（第一組條件）；否則當x1>4時，x2≤3（第二組條件）.

定義邏輯變量：又設M

為任意大正數，則問題可表達為：需注意，當約束為大于時，右端項中用減號。7ppt課件4.用以表示含固定費用的函數

用xj

代表產品j

的生產數量，其生產費用函數表示為其中

Kj

是同產量無關的生產準備費用，問題的目標是使所有產品的總生產費用為最小，即8ppt課件定義邏輯變量（表示是否生產產品j）又設M

為任意大正數，為了表示上述定義，引入約束：顯然，當xj>0時，yj=1。9ppt課件將目標函數與約束條件合起來考慮有：由此看出，當

xj=0時，為使z極小化，應有yj=010ppt課件2分配問題與匈牙利法一、問題的提出與數學模型

分配問題也稱指派問題（assignmentproblem），是一種特殊的整數規劃問題。假定有m項任務分配給m個人去完成，并指定每人完成其中一項，每項只交給其中一個人去完成，應如何分配使總的效率為最高。如果完成任務的效率表現為資源消耗，考慮的是如何分配任務使得目標極小化；如果完成任務的效率表現為生產效率的高低，則考慮的是如何分配使得目標函數極大化。在分配問題中，利用不同資源完成不同計劃活動的效率常用表格形式表示為效率表，表格中數字組成效率矩陣。11ppt課件

例2.有一份說明書，要分別翻譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成。因各人專長不同，使這四個人分別完成四項任務總的時間為最小。效率表如下：效率矩陣用[aij]表示，為12ppt課件定義邏輯變量則分配問題的數學模型寫為：13ppt課件二、匈牙利法用表上作業法來求解分配問題時，單位運價表即效率表，產銷平衡表中產量和銷量都設為1即可。匈牙利數學家克尼格（

Konig）求解分配問題的計算方法被稱為匈牙利法，原理是如果效率矩陣所有元素aij>=0，而其中存在一組位于不同行不同列的零元素，則只要令對應于這些零元素位置的xij=1即為最優解。14ppt課件

定理1

如果從分配問題效率矩陣[aij]的每一行元素中分別減去（或加上）一個常數ui(被稱為該行的位勢)，從每一列分別減去（或加上）一個常數vj（被稱為該列的位勢），得到一個新的效率矩陣[bij]，若其中bij=aij-ui-vj，則[bij]的最優解等價于[aij]的最優解。

定理2

若矩陣A

的元素可分成“0”與非“0”兩部分，則覆蓋“0”元素的最少直線數等于位于不同行不同列的“0”元素的最大個數。AB甲35乙42AB甲02乙20AB甲03乙1015ppt課件

結合例2說明匈牙利法的計算步驟

第一步：找出效率矩陣每行的最小元素，并分別從每行中減去。

第二步：找出矩陣每列的最小元素，分別從各列中減去。16ppt課件

第三步：經過上述兩步變換后，矩陣的每行每列至少都有了一個零元素。下面確定能否找出

m

個位于不同行不同列的零元素的集合（該例中m=4），也就是看要覆蓋上面矩陣中的所有零元素，至少需要多少條直線。1.從第一行開始，若該行只有一個零元素，就對這個零元素打上（），對打括號的零元素所在的列畫一條線，若該行沒有零元素或者有兩個以上零元素（已劃去的不算在內），則轉下一行，依次進行到最后一行。17ppt課件2.從第一列開始，若該列只有一個零元素，就對這個零元素打上（）（同樣不考慮已劃去的零元素），再對打括號的零元素所在行畫一條直線。若該列沒有零元素或有兩個以上零元素，則轉下一列，依次進行到最后一列為止。18ppt課件3.重復上述步驟1、2，可能出現三種情況：①效率矩陣每行都有打括號的零元素，只要對應這些元素令

xij=1就找到了最優解。②打括號的零元素個數少于

m

，但未被劃去的零元素之間存在閉回路，這時順著閉回路的走向，對每個間隔的零元素打一個括號，然后對所有打括號的零元素所在行（或列）畫一條直線，同樣得到最優解。19ppt課件③矩陣中所有零元素或被劃去，或打上括號，但打括號的零元素少于

m

，這時轉入第四步。

第四步：按定理1進行如下變換1.從矩陣未被直線覆蓋的數字中找出一個最小的k

；2.對矩陣中的每行，當該行有直線覆蓋時，令

ui=0，無直線覆蓋的，令ui=k

；3.對矩陣中有直線覆蓋的列，令vj=-k，對無直線覆蓋的列，令vj=0；4.從原矩陣的每個元素aij中分別減去ui和vj。20ppt課件

第五步：回到第三步，反復進行，直到矩陣的每一行都有一個打括號的零元素為止，即找到最優分配方案。

由于調整后的矩陣中新出現了一個零，因此對打括號的元素重新進行調整，得到如下矩陣，這時只要把打括號元素所對應的決策變量取值為1，就得到最優解。

該問題中，最優值為：4+4+9+11=28h21ppt課件求下面所示效率矩陣的指派問題的最小解ABCDE甲127979乙89666丙71712149丁15146610戊4107109課堂練習22ppt課件

三、兩點說明1.分配問題中人數和工作任務不相等時

當人數多于工作任務數時，可以添加假想任務使得人數與工作任務數相同，因為工作任務是假想的，因此完成這些任務的時間是零。當任務數多于人數時，可添加假想的人。這樣的方法和運輸問題中處理的方法類似。2.當問題目標變為求極大時可改寫為

此時效率矩陣中元素都變為了負值，可利用定理1，使效率矩陣中全部元素都變為非負的，就可以利用匈牙利法進行求解。23ppt課件§3分枝定界法分枝定界法(branchandboundmethod)是為了求解同整數規劃具有類似性質的一大類問題而設計的一種較好的方法。結合例一來說明分枝定界法的思路和解題步驟：

例1.

求下述整數規劃問題的最優解24ppt課件第一步：尋找替代問題并求解。放寬或取消原問題的某些約束，找出一個替代問題。若替代問題的最優解是原問題的可行解，這個解就是原問題的最優解，否則是源問題最優解的上界(求極大值)或下界(求極小值)。

例1對應的松弛問題L0其最優解為：最優值為：25ppt課件第二步：分枝與定界。將替代問題分成若干子問題，對子問題也要容易求解，且各子問題的解的集合要包含原問題的解集。然后對每個子問題求最優解，若滿足原問題的約束，則找到原問題的可行解，否則該解為所屬分枝的邊界值；如果所有子問題的最優解均非原問題可行解，則選取邊界值最大(求極大值)或最小(求極小值)的子問題再進一步細分子問題求解。分枝過程一直進行下去，直到找到一個原問題的可行解為止。如果計算中同時出現兩個以上可行解，則選取其中最大(求極大值)或最小(求極小值)的一個保留。26ppt課件

將線性規劃問題L0

分為兩枝。

在L0

的最優解中，任選一個非整數變量，如x2=2.5；因x2

的最優整數解只可能是x2≤2或x2≥3，故在

L0中分別增加約束條件：加上約束條件x2≤2，記為L1；加上約束條件x2≥3，記為L2。27ppt課件L1

的最優解為：x1=3.5,x2=2,z=14.5L2

的最優解為：x1=2.5,x2=3,z=13.528ppt課件由于兩個子問題的最優解仍非原問題的可行解，故選取最優值較大的子問題L1進行分枝，將分解為L11和L12

兩個子問題。29ppt課件L11和L12

兩個子問題的可行域為：L11

的最優解為：x1=3,x2=2,z=13L12

的最優解為：x1=4,x2=1,z=14這時兩個問題獲得的均為可行解，保留可行解中較大的一個30ppt課件第三步：剪枝，將各子問題邊界值與保留的可行解的值進行比較，把邊界值劣于可行解的分枝剪去，如果除保留下來的可行解外，其余分枝均被剪去，則該可行解就是原問題的最優解，否則回到第二步，選取邊界值最優的一個繼續分枝。如果計算又出現新的可行解，則與原可行解比較，保留最優的，并重復上述步驟。31ppt課件32ppt課件通過剪枝，求解得最優解為（4,1），最優解為14。用分枝定界法可求解純整數規劃問題和混合整數規劃問題，比窮舉法優越，但若變量數目很大，其計算量也相當客觀。33ppt課件§4割平面法割平面法是求解整數規劃問題最早提出的一種方法，1958年由Gomory提出，其基本思想是在整數規劃問題的松弛問題中依次引進線性約束條件，稱為(Gomory約束)，使問題的可行域逐步縮小，但每次切割只割去問題的部分非整數解，直到使問題的最優目標函數點成為縮小后可行域的一個頂點。34ppt課件

例1.

求下述整數規劃問題的最優解第一步：把約束條件的系數化成整數，不考慮變量的整數約束35ppt課件加松弛變量，用單純形法求解得最終單純形表：x1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj-zj00-1/4-5/436ppt課件第二步：找出非整數解變量中分數部分最大的一個基變量，并寫下該行約束：將常數寫成整數與一個正的分數值的和；將整數項移到等式左端：37ppt課件38ppt課件39ppt課件

新約束條件只割去可行域部分非整數解，原有的整數解全部保留40ppt課件將Gomory約束加到G0得到新的線性規劃問題G1，如下：41ppt課件第四步：重復第一至第三步一直到找出問題的整數最優解為止42ppt課件由于得到的解仍為非整數解，重復第二步43ppt課件44ppt課件45ppt課件