運(yùn)籌學(xué)整數(shù)規(guī)劃1ppt課件

.,Chapter4整數(shù)規(guī)劃(IntegerProgramming),整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用分支定界法分配問題與匈牙利法,本章主要內(nèi)容：,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃（簡稱：IP）要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。,整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：,.,整數(shù)規(guī)劃的特點(diǎn)及應(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ī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃的典型例子,例4.1工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個。這種物資的需求地有B1,B2,B3,B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij，見下表：,工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用最少。,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,解：這是一個物資運(yùn)輸問題，特點(diǎn)是事先不能確定應(yīng)該建A3還是A4中哪一個，因而不知道新廠投產(chǎn)后的實(shí)際生產(chǎn)物資。為此，引入0-1變量：,再設(shè)xij為由Ai運(yùn)往Bj的物資數(shù)量，單位為千噸；z表示總費(fèi)用，單位萬元。則該規(guī)劃問題的數(shù)學(xué)模型可以表示為：,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,混合整數(shù)規(guī)劃問題,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,例4.2現(xiàn)有資金總額為B?？晒┻x擇的投資項(xiàng)目有n個，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj（j1,2,.,n），此外由于種種原因，有三個附加條件：若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2。反之不一定項(xiàng)目3和4中至少選擇一個；項(xiàng)目5,6,7中恰好選擇2個。應(yīng)該怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大。,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,解：對每個投資項(xiàng)目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個項(xiàng)目的決策選擇，記為：,投資問題可以表示為：,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,例4.3指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,設(shè),數(shù)學(xué)模型如下：,要求每人做一項(xiàng)工作，約束條件為：,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,每項(xiàng)工作只能安排一人，約束條件為：,變量約束：,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃問題解的特征：,整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集。整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標(biāo)函數(shù)值不會優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,例4.3設(shè)整數(shù)規(guī)劃問題如下,首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,用圖解法求出最優(yōu)解為：x13/2,x2=10/3，且有Z=29/6,現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個點(diǎn)即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。,x1,x2,3,3,(3/2,10/3),按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點(diǎn)的目標(biāo)函數(shù)值最大，即為Z=4。,.,整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用,整數(shù)規(guī)劃問題的求解方法：,分支定界法和割平面法匈牙利法（指派問題）,.,分支定界法,1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界：任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：xixi和xixi+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分枝問題的下界。檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計(jì)算，若還存在非整數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。,分支定界法的解題步驟：,.,分支定界法,例4.4用分枝定界法求解整數(shù)規(guī)劃問題,解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題),LP,IP,.,分支定界法,用圖解法求松弛問題的最優(yōu)解，如圖所示。,x1,x2,3,(18/11,40/11),2,1,1,2,3,x118/11,x2=40/11Z=218/11(19.8)即Z也是IP最小值的下限。,對于x118/111.64，取值x11，x12對于x2=40/113.64，取值x23，x24先將（LP）劃分為（LP1）和（LP2）,取x11,x12,.,分支定界法,分支：,分別求出（LP1）和（LP2）的最優(yōu)解。,.,分支定界法,先求LP1,如圖所示。此時(shí)在B點(diǎn)取得最優(yōu)解。x11,x2=3,Z(1)16找到整數(shù)解，問題已探明，此枝停止計(jì)算。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,同理求LP2,如圖所示。在C點(diǎn)取得最優(yōu)解。即:x12,x2=10/3,Z(2)56/318.7Z(2)Z(1)16原問題有比16更小的最優(yōu)解，但x2不是整數(shù)，故繼續(xù)分支。,.,分支定界法,在IP2中分別再加入條件：x23,x24得下式兩支：,分別求出LP21和LP22的最優(yōu)解,.,分支定界法,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求LP21,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x112/52.4,x2=3,Z(21)-87/5-17.4Z(211)如對LP212繼續(xù)分解，其最小值也不會低于15.5，問題探明,剪枝。,.,分支定界法,原整數(shù)規(guī)劃問題的最優(yōu)解為:x1=2,x2=3,Z*=17以上的求解過程可以用一個樹形圖表示如右：,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=12/5,x2=3Z(21)17.4,LP22無可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3,x2=5/2Z(212)15.5,x11,x12,x23,x24,x12,x13,.,分支定界法,例4.5用分枝定界法求解,解:先求對應(yīng)的松弛問題（記為LP0）,用圖解法得到最優(yōu)解X(3.57,7.14),Z0=35.7,如下圖所示。,.,分支定界法,10,10,松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,.,分支定界法,10,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,.,分支定界法,10,x1,x2,o,A,B,C,LP1,LP21,3,4,LP21:X=(4.33,6),Z21=35.33,6,.,分支定界法,10,x1,x2,o,A,C,LP1,3,4,6,LP211:X=(4,6),Z211=34,LP212:X=(5,5),Z212=35,5,LP212,.,分支定界法,上述分枝過程可用下圖表示：,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6)Z1=34.8,LP2:X=(4,6.5)Z2=35.5,x13,x14,LP21:X=(4.33,6)Z21=35.33,x26,LP211:X=(4,6)Z211=34,LP212:X=(5,5)Z212=35,x14,x15,LP22無可行解,x27,.,小結(jié),學(xué)習(xí)要點(diǎn)：掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu)掌握分支定界法原理能夠用分支定界法求解一般整數(shù)規(guī)劃問題,課后練習(xí)：,.,分配問題與匈牙利法,指派問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式：,設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的效率（時(shí)間或費(fèi)用）為Cij(i=1.2n;j=1.2n)并假設(shè)Cij0。問應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？,設(shè)決策變量,.,分配問題與匈牙利法,指派問題的數(shù)學(xué)模型為：,.,分配問題與匈牙利法,克尼格定理:如果從分配問題效率矩陣aij的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣bij，則以bij為效率矩陣的分配問題與以aij為效率矩陣的分配問題具有相同的最優(yōu)解。,.,分配問題與匈牙利法,指派問題的求解步驟：,1)變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即從(cij)的每行元素都減去該行的最小元素；再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。,2)進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個獨(dú)立0元素，就以這n個獨(dú)立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。,.,分配問題與匈牙利法,找獨(dú)立0元素，常用的步驟為：,從只有一個0元素的行開始，給該行中的0元素加圈，記作。然后劃去所在列的其它0元素，記作；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進(jìn)行到最后一行。從只有一個0元素的列開始（畫的不計(jì)在內(nèi)），給該列中的0元素加圈，記作；然后劃去所在行的0元素，記作，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進(jìn)行到最后一列。若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。,.,分配問題與匈牙利法,若元素的數(shù)目m等于矩陣的階數(shù)n（即：mn），那么這指派問題的最優(yōu)解已得到。若mn,則轉(zhuǎn)入下一步。,3)用最少的直線通過所有0元素。其方法：,對沒有的行打“”；對已打“”的行中所有含元素的列打“”；再對打有“”的列中含元素的行打“”；重復(fù)、直到得不出新的打號的行、列為止；對沒有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。,注：l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若lmn，表示還不能確定最優(yōu)指派方案，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨(dú)立的0元素，為此轉(zhuǎn)第4步。,.,分配問題與匈牙利法,4)變換矩陣(bij)以增加0元素在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點(diǎn)處的元素加上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。,.,分配問題與匈牙利法,例4.6有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？,.,分配問題與匈牙利法,解：1）變換系數(shù)矩陣，增加0元素。,5,2）試指派（找獨(dú)立0元素）,找到3個獨(dú)立零元素但m=3n=4,.,分配問題與匈牙利法,3）作最少的直線覆蓋所有0元素,獨(dú)立零元素的個數(shù)m等于最少直線數(shù)l，即lm=3n=4；,4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個最小元素；直線交點(diǎn)處的元素加上這個最小值。得到新的矩陣，重復(fù)2）步進(jìn)行試指派,.,分配問題與匈牙利法,試指派,得到4個獨(dú)立零元素，所以最優(yōu)解矩陣為：,即完成4個任務(wù)的總時(shí)間最少為：241+8=15,.,分配問題與匈牙利法,例4.7已知四人分別完成四項(xiàng)工作所需時(shí)間如下表，求最優(yōu)分配方案。,.,分配問題與匈牙利法,解：1）變換系數(shù)矩陣，增加0元素。,2）試指派（找獨(dú)立0元素）,獨(dú)立0元素的個數(shù)為4,指派問題的最優(yōu)指派方案即為甲負(fù)責(zé)D工作，乙負(fù)責(zé)B工作，丙負(fù)責(zé)A工作，丁負(fù)責(zé)C工作。這樣安排能使總的工作時(shí)間最少，為4491128。,.,分配問題與匈牙利法,例4.8已知五人分別完成五項(xiàng)工作耗費(fèi)如下表，求最優(yōu)分配方案。,.,分配問題與匈牙利法,-1,-2,解：1）變換系數(shù)矩陣，增加0元素。,.,分配問題與匈牙利法,2）試指派（找獨(dú)立0元素）,獨(dú)立0元素的個數(shù)l45，故畫直線調(diào)整矩陣。,.,分配問題與匈牙利法,選擇直線外的最小元素為1；直線外元素減1，直線交點(diǎn)元素加1，其他保持不變。,.,分配問題與匈牙利法,l=m=4n=5,選擇直線外最小元素為1，直線外元素減1，直線交點(diǎn)元素加1，其他保持不變，得到新的系數(shù)矩陣。,.,分配問題與匈牙利法,總費(fèi)用為=5+7+6+6+4=28,注：此問題有多個最優(yōu)解,.,分配問題與匈牙利法,總費(fèi)用為=7+9+4+3+5=28,.,分配問題與匈牙利法,總費(fèi)用為=8+9+4+3+4=28,.,分配問題與匈牙利法,課堂練習(xí)：用匈牙利法求解下列指派問題。,練習(xí)1：,練習(xí)2：,.,分配問題與匈牙利法,48,21,答案：,.,分配問題與匈牙利法,非標(biāo)準(zhǔn)型的指派問題：,匈牙利法的條件是：模型求最小值、效率cij0。當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時(shí)，處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解。,.,分配問題與匈牙利法,1.最大化指派問題,處理方法：設(shè)m為最大化指派問題系數(shù)矩陣C中最大元素。令矩陣B（m-cij）nn則以B為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解。,例4.9某人事部門擬招聘