運籌學(xué)-整數(shù)規(guī)劃與分配問題PPT

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

例1.

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

個起作用設(shè)

m

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

M

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

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

定義邏輯變量：又設(shè)M

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

用xj

代表產(chǎn)品j

的生產(chǎn)數(shù)量，其生產(chǎn)費用函數(shù)表示為其中

Kj

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

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

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

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

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

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

定理1

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

定理2

若矩陣A

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

結(jié)合例2說明匈牙利法的計算步驟

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

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

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

m

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

xij=1就找到了最優(yōu)解。②打括號的零元素個數(shù)少于

m

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

m

，這時轉(zhuǎn)入第四步。

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

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

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

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

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

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

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

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

當人數(shù)多于工作任務(wù)數(shù)時，可以添加假想任務(wù)使得人數(shù)與工作任務(wù)數(shù)相同，因為工作任務(wù)是假想的，因此完成這些任務(wù)的時間是零。當任務(wù)數(shù)多于人數(shù)時，可添加假想的人。這樣的方法和運輸問題中處理的方法類似。2.當問題目標變?yōu)榍髽O大時可改寫為

此時效率矩陣中元素都變?yōu)榱素撝?，可利用定?，使效率矩陣中全部元素都變?yōu)榉秦摰?，就可以利用匈牙利法進行求解。23ppt課件§3分枝定界法分枝定界法(branchandboundmethod)是為了求解同整數(shù)規(guī)劃具有類似性質(zhì)的一大類問題而設(shè)計的一種較好的方法。結(jié)合例一來說明分枝定界法的思路和解題步驟：

例1.

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

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

將線性規(guī)劃問題L0

分為兩枝。

在L0

的最優(yōu)解中，任選一個非整數(shù)變量，如x2=2.5；因x2

的最優(yōu)整數(shù)解只可能是x2≤2或x2≥3，故在

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

的最優(yōu)解為：x1=3.5,x2=2,z=14.5L2

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

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

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

的最優(yōu)解為：x1=3,x2=2,z=13L12

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

例1.

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

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