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

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

例1.

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

個(gè)起作用設(shè)

m

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

M

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

若x1≤4，則x2≥1（第一組條件）；否則當(dāng)x1>4時(shí)，x2≤3（第二組條件）.

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

為任意大正數(shù)，則問題可表達(dá)為：需注意，當(dāng)約束為大于時(shí)，右端項(xiàng)中用減號(hào)。7ppt課件4.用以表示含固定費(fèi)用的函數(shù)

用xj

代表產(chǎn)品j

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

Kj

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

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

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

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

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

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

定理1

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

定理2

若矩陣A

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

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

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

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

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

m

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

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

m

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

m

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

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

；2.對(duì)矩陣中的每行，當(dāng)該行有直線覆蓋時(shí)，令

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

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

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

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

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

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

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

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

例1.

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

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

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

分為兩枝。

在L0

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

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

L0中分別增加約束條件：加上約束條件x2≤2，記為L(zhǎng)1；加上約束條件x2≥3，記為L(zhǎng)2。27ppt課件L1

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

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

兩個(gè)子問題。29ppt課件L11和L12

兩個(gè)子問題的可行域?yàn)椋篖11

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

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

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