物流運籌學(xué) 課件 第5章 整數(shù)規(guī)劃

Chapter5整數(shù)規(guī)劃

(IntegerProgramming)整數(shù)規(guī)劃的特點及應(yīng)用分支定界法分支定界法枚舉法分配問題與匈牙利法本章主要內(nèi)容：引例例5.1某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如下表所示。貨物每件體積/立方英尺每件重量/百千克每件利潤/百元甲19542乙273403托運限制1365140甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大？解設(shè)x1、x2分別為甲、乙兩種貨物托運的件數(shù)，建立模型例5.2某企業(yè)在A1地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個地方建廠，已知在A2地建廠的固定成本為175千元，在A3地建廠的固定成本為300千元，在A4地建廠的固定成本為375千元，在A5地建廠的固定成本為500千元，另外，在A1的產(chǎn)量，A2，A3，A4，A5建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運價（每千箱運費）如下表所示。問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最??？B1B2B3產(chǎn)量A184330A252310A343420A497530A5104240銷量302020解:(1)設(shè)xij為從Ai運往Bj的運輸量(單位:千箱)1,當(dāng)廠址Ai被選中時

0,當(dāng)廠址Ai沒有被選中時yi=此外還必須滿足非負約束及yi=0,1(i=2,…,5)整數(shù)規(guī)劃的特點及應(yīng)用例5.3指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。

工作人員ABCD甲85927390乙95877895丙82837990丁86908088整數(shù)規(guī)劃的特點及應(yīng)用設(shè)數(shù)學(xué)模型如下：要求每人做一項工作，約束條件為：整數(shù)規(guī)劃的特點及應(yīng)用每項工作只能安排一人，約束條件為：變量約束：整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃（簡稱：IP） 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：整數(shù)規(guī)劃問題的松弛問題xj部分或全部取整數(shù)整數(shù)規(guī)劃（簡稱：IP） 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)線性規(guī)劃問題的種類：

純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。

0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃問題解的特征：

整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集。整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標函數(shù)值不會優(yōu)于后者最優(yōu)解的目標函數(shù)值。整數(shù)規(guī)劃的特點及應(yīng)用例5.3設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。整數(shù)規(guī)劃的特點及應(yīng)用用圖解法求出最優(yōu)解為：x1＝3/2,x2=10/3，且有Z=29/6

現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個點即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點的目標函數(shù)值最大，即為Z=4。整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃問題的求解方法：

分支定界法和割平面法枚舉法匈牙利法（指派問題）分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界： 任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時，目標值是分枝問題的上界；當(dāng)原問題是求最小值時，目標值是分枝問題的下界。 檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標值大于(max)整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：分支定界法例

用分枝定界法求解解:先求對應(yīng)的松弛問題（記為LP0）用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。分支定界法1010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212分支定界法上述分枝過程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP21:X=(4.33,6)Z21=35.33x2≤6LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x1≤4x1≥5LP22無可行解x2≥7分支定界法例

用分枝定界法求解整數(shù)規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題)LPIP分支定界法用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x2⑴⑵3(18/11,40/11)⑶21123x1＝18/11,x2=40/11Z=－218/11≈(－19.8)即Z也是IP最小值的下限。對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2分支定界法分支：分別求出（LP1）和（LP2）的最優(yōu)解。分支定界法先求LP1,如圖所示。此時在B點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計算。x1x2⑴⑵33(18/11,40/11)⑶11BAC同理求LP2,如圖所示。在C

點取得最優(yōu)解。即:x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)<Z(1)＝－16∴原問題有比－16更小的最優(yōu)解，但x2不是整數(shù)，故繼續(xù)分支。分支定界法在IP2中分別再加入條件：x2≤3,x2≥4得下式兩支：分別求出LP21和LP22的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求LP21,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(21)＝-87/5≈-17.4<Z(1)=-16但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。求LP22，如圖所示。無可行解，故不再分枝。分支定界法

在（LP21）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：分別求出（LP211）和（LP212）的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACDEF先求（LP211）,如圖所示。此時在E點取得最優(yōu)解。即x1＝2,x2=3,Z(211)＝－17找到整數(shù)解，問題已探明，此枝停止計算。求（LP212），如圖所示。此時F在點取得最優(yōu)解。即x1＝3,x2=2.5,Z(212)＝－31/2≈－15.5>Z(211)

如對LP212繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。分支定界法原整數(shù)規(guī)劃問題的最優(yōu)解為:x1=2,x2=3,Z*=－17以上的求解過程可以用一個樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP21x1=12/5,x2=3Z(21)

＝－17.4LP22無可行解LP211x1=2,x2=3Z(211)

＝－17LP212x1=3,x2=5/2Z(212)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃例求解如下整數(shù)規(guī)劃：首先求解其松弛規(guī)劃：最優(yōu)解為X=(3.25,2.5)’，z=14.75因為x1=3.25，所以將其分為x1<=3和x1>=4兩個分支因為x2=8/3，所以將其分為x2<=2和x2>=3兩個分支因為ZD<ZC,所以不再分支因為ZE<ZC,所以ZC是最優(yōu)解所以X*=(4,1)，Z*=14解純整數(shù)規(guī)劃的割平面法注意：對于任一有理數(shù)

，將其分為兩部分，可表示為：式中：

為不超過

的最大整數(shù)，

是一非負真分數(shù)。例如：

由于在切割方程中

前面為負號，而

常常為正，故在把它加入松弛問題的最終單純形表進行求解時，大多采用對偶單純形法。

需要指出的是，由于條件（5-2e）僅是得出整數(shù)解的必要條件，不能保證一次切割即可達到整數(shù)解，往往需要多次迭代。此外，若松弛問題的某一最優(yōu)解有多個分數(shù)分量，則對每一分數(shù)分量均可導(dǎo)出一切割方程。

這時，我們往往優(yōu)先使用其中較“強”的一個，以切去可行域較大的部分。

為簡單起見，?？芍苯舆x用具有較大分數(shù)部分的變量所對應(yīng)的切割方程為割平面。

例廣州某食品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，目前有10個位置可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集程度，規(guī)定：在東區(qū)由三個點中最多選擇兩個；在西區(qū)由兩個點中至少選擇一個；在南區(qū)由兩個點中至少選擇一個；在北區(qū)由三個點中至少選擇兩個。投資總額不能超過720萬元，問應(yīng)該選擇哪幾個銷售點，可使年利潤為最大？

s.t.在東區(qū)由三個點中最多選擇兩個在西區(qū)由兩個點中至少選擇一個在南區(qū)由兩個點中至少選擇一個在北區(qū)由三個點中至少選擇兩個例有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用及售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見下表。要求制定一個生產(chǎn)計劃，使總收益最大。0-1型整數(shù)規(guī)劃問題的解法枚舉法：列出變量取值為0或1的可能的組合（若有n個變量則有2n個組合），再逐一驗證它們是否滿足約束條件，然后對滿足約束條件的可行解計算目標函數(shù)值，其中目標函數(shù)值最優(yōu)的就是最優(yōu)解方法的改進：通過設(shè)置過濾條件有效地減少驗證組合為可行解的次數(shù)。(x1,x2,x3)zABCD過濾條件(0,0,0)(0,0,1)05YYYYYYYY(0,1,0)-2YYYY(0,1,1)3YNYY(1,0,0)3YYYY(1,0,1)8YYYY(1,1,0)1YNYY(1,1,1)6YNYYz≥0z≥5z≥8(x1,x2,x3)zABCD過濾條件(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)05-233816YYYYYYYYYYYYz≥0z≥5z≥8分配問題與匈牙利法指派問題的數(shù)學(xué)模型的標準形式：

設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（時間或費用）最高？設(shè)決策變量分配問題與匈牙利法指派問題的數(shù)學(xué)模型為：分配問題與匈牙利法克尼格定理

:

如果從分配問題效率矩陣[aij]的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣[bij]，則以[bij]為效率矩陣的分配問題與以[aij]為效率矩陣的分配問題具有相同的最優(yōu)解。分配問題與匈牙利法指派問題的求解步驟：1)變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即從(cij)的每行元素都減去該行的最小元素；再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2)進行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。分配問題與匈牙利法找獨立0元素，常用的步驟為：

從只有一個0元素的行開始，給該行中的0元素加圈，記作◎。然后劃去◎所在列的其它0元素，記作?

；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行。從只有一個0元素的列開始（畫?的不計在內(nèi)），給該列中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?

，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進行，直到所有0元素都已圈出和劃掉為止。分配問題與匈牙利法

若◎元素的數(shù)目m等于矩陣的階數(shù)n（即：m＝n），那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。3)用最少的直線通過所有0元素。其方法：

對沒有◎的行打“√”；對已打“√”的行中所有含?元素的列打“√”；再對打有“√”的列中含◎元素的行打“√”；重復(fù)①、②直到得不出新的打√號的行、列為止；對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。注：l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若l＝m<n，表示還不能確定最優(yōu)指派方案，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉(zhuǎn)第4步。分配問題與匈牙利法4)變換矩陣(bij)以增加0元素 在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。分配問題與匈牙利法例5.6有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。－52）試指派（找獨立0元素）◎◎◎??

找到3個獨立零元素但m=3<n=4分配問題與匈牙利法3）作最少的直線覆蓋所有0元素

◎◎◎??√√√獨立零元素的個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。得到新的矩陣，重復(fù)2）步進行試指派分配問題與匈牙利法000000試指派◎◎◎??◎得到4個獨立零元素，所以最優(yōu)解矩陣為：即完成4個任務(wù)的總時間最少為：2＋4＋1+8=15分配問題與匈牙利法例5.7已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。

任務(wù)人員ABCDE甲759811乙9127119丙85468丁73696戊467511分配問題與匈牙利法-1-2解：1）變換系數(shù)矩陣，增加0元素。分配問題與匈牙利法◎?◎◎◎??2）試指派（找獨立0元素）獨立0元素的個數(shù)l＝4<5，故畫直線調(diào)整矩陣。分配問題與匈牙利法◎?◎◎◎??√√√選擇直線外的最小元素為1；直線外元素減1，直線交點元素加1，其他保持不變。分配問題與匈牙利法◎?◎?◎?◎?√√√√√√√l=m=4<n=5選擇直線外最小元素為1，直線外元素減1，直線交點元素加1，其他保持不變，得到新的系數(shù)矩陣。分配問題與匈牙利法◎??◎??◎?◎?◎總費用為=5+7+6+6+4=28注：此問題有多個最優(yōu)解分配問題與匈牙利法◎??◎??◎?◎?◎總費用為=7+9+4+3+5=28分配問題與匈牙利法◎??◎??◎?◎?◎總費用為=8+9+4+3+4=28分配問題與匈牙利法課堂練習(xí)：用匈牙利法求解下列指派問題。練習(xí)1：練習(xí)2：分配問題與匈牙利法4821答案：分配問題與匈牙利法非標準型的指派問題：匈牙利法的條件是：模型求最小值、效率cij≥0。當(dāng)遇到各種非標準形式的指派問題時，處理方法是先將其轉(zhuǎn)化為標準形式，然后用匈牙利法來求解。分配問題與匈牙利法1.最大化指派問題處理方法：設(shè)m為最大化指派問題系數(shù)矩陣C中最大元素。令矩陣B＝（m-c