《管理運(yùn)籌學(xué)》演示(整數(shù)規(guī)劃)

《管理運(yùn)籌學(xué)》演示1999年12月1宅)sylpy@263.net2021/6/271目錄線性規(guī)劃圖解法單純形表結(jié)構(gòu)線性規(guī)劃單純形法(1)最小元素法伏格爾法閉回路法位勢(shì)法閉回路調(diào)整法目標(biāo)規(guī)劃圖解法(1)目標(biāo)規(guī)劃圖解法(2)整數(shù)規(guī)劃(分枝定界法)和和線性規(guī)劃單純形法(2)圖解法與單純形法的聯(lián)系指派問(wèn)題(匈牙利法)(1)使用計(jì)算機(jī)軟件包求解指派問(wèn)題(匈牙利法)(2)0-1規(guī)劃(隱枚舉法)整數(shù)規(guī)劃(割平面法)典型應(yīng)用案例線性規(guī)劃單純形法(3)目標(biāo)規(guī)劃單純形法線性規(guī)劃求解幾種結(jié)果幾種常用規(guī)劃數(shù)學(xué)軟件比較動(dòng)態(tài)規(guī)劃(1)動(dòng)態(tài)規(guī)劃(2)最小樹(shù)問(wèn)題(破圈法/避圈法)最短路問(wèn)題(迪克斯拉法)(1)最大流問(wèn)題(福克遜法)最小費(fèi)用最大流問(wèn)題(2)對(duì)偶單純形法改進(jìn)單純形法動(dòng)態(tài)規(guī)劃(逆推法)(順推法)(3)2021/6/272對(duì)于整數(shù)規(guī)劃問(wèn)題,先不考慮整數(shù)約束,求相應(yīng)的線性規(guī)劃問(wèn)題的最優(yōu)解,如果最優(yōu)解是一個(gè)非整數(shù)最優(yōu)解,構(gòu)造約束條件,縮小線性規(guī)劃問(wèn)題的可行域,丟棄不含整數(shù)解的區(qū)域，然后在縮小后的子可行域中繼續(xù)求解,直止求出相應(yīng)的線性規(guī)劃的最優(yōu)解為整數(shù)解。分枝：如果求出的最優(yōu)解是一個(gè)非整數(shù)解，則以這個(gè)解任一分量相鄰的兩個(gè)整數(shù)點(diǎn)為邊緣將線性規(guī)劃的可行域分成兩個(gè)子區(qū)域，每個(gè)子區(qū)域就是一個(gè)分枝（或子問(wèn)題）；定界：在分枝過(guò)程中，通過(guò)分枝找到更好的最優(yōu)值和整數(shù)解不斷地修改上下界，和減小上下界之間的范圍，當(dāng)上下界相同時(shí)，即得到整數(shù)最優(yōu)解。分枝定界法的基本思想:2021/6/273.定界。設(shè)整數(shù)規(guī)劃的目標(biāo)最優(yōu)值為z*，則，其中，和為整數(shù)規(guī)劃目標(biāo)值的上、下界；.分枝。在非整數(shù)最優(yōu)解中，任選一個(gè)不符合整數(shù)條件的變量，構(gòu)造兩個(gè)約束條件：

.修改上下界。方法如下：在各分枝中，找出目標(biāo)值最大者作為新的上界；從已符合整數(shù)條件的分枝中，找出目標(biāo)值最大者作為新的下界。.比較和剪枝。比較各個(gè)分枝的目標(biāo)值，如果有小于者，則剪掉這個(gè)分枝；否則，繼續(xù)分枝。反復(fù)進(jìn)行，當(dāng)，得到整數(shù)最優(yōu)解。例1：用分枝定界法求整數(shù)規(guī)劃分枝定界法的求解步驟:.先不考慮整數(shù)約束條件，求解相應(yīng)的線性規(guī)劃，有以下幾種情況：如果線性規(guī)劃沒(méi)有可行解，則整數(shù)規(guī)劃也沒(méi)有可行解，停止計(jì)算；如果線性規(guī)劃有最優(yōu)解，且為整數(shù)最優(yōu)解，則這個(gè)解為整數(shù)規(guī)劃的整數(shù)最優(yōu)解；如果線性規(guī)劃有最優(yōu)解，但為非整數(shù)最優(yōu)解，則轉(zhuǎn)入下一步；2021/6/2749x1+7x2=56BC0x1x2125346789125346787x1+20x2=70整數(shù)規(guī)劃(分枝定界法)(例1)Bz=40x1+90x2x1=4.81x2=1.82z=356B0

Z*

3562021/6/2759x1+7x2=56x1=4x1=5BC0x1x2125346789125346787x1+20x2=70B1B2x1=4.81x2=1.82z=356BB2x1=4.00x2=2.10z=349x1=5.00x2=1.57z=341B1整數(shù)規(guī)劃(分枝定界法)(例2)0

Z*

3560

Z*

3560

Z*

349z=40x1+90x22021/6/2769x1+7x2=56x2=3x1=4x1=5BC0x1x2125346789125346787x1+20x2=70B3B4x2=1x2=2x2=2B2B5B4B3x1=4.00x2=2.00z=340x1=1.42x2=3.00z=327x1=4.81x2=1.82z=356BB2x1=4.00x2=2.10z=349x1=5.00x2=1.57z=341B1B5x1=5.44x2=1.00z=308無(wú)可行解B6整數(shù)最優(yōu)解:x1=4.0,x2=2.0整數(shù)規(guī)劃(分枝定界法)(例1)0

Z*

3560

Z*

3560

Z*

3490

Z*

349Z下界=Z*=Z上界z=40x1+90x22021/6/277對(duì)于整數(shù)規(guī)劃問(wèn)題,首先不考慮整數(shù)約束,求解相應(yīng)的線性規(guī)劃問(wèn)題的解,如果最優(yōu)解是一個(gè)非整數(shù)解,就增加一個(gè)約束條件,縮小線性規(guī)劃問(wèn)題的可行域,繼續(xù)求解,直到求出相應(yīng)的線性規(guī)劃問(wèn)題的最優(yōu)解為整數(shù)解。割平面法的基本思想:例：求解下列整數(shù)規(guī)劃：整數(shù)整數(shù)最優(yōu)解:2021/6/278例3：用割平面法求解整數(shù)規(guī)劃整數(shù)11001400-111031011100解：先不考慮整數(shù)約束，求相應(yīng)的線性規(guī)劃的最優(yōu)解，用單純形法求解，標(biāo)準(zhǔn)型和初始單純形表如下：2021/6/27911003/47/41110-1/41/4013/41/400-1/2-1/2-5/2經(jīng)過(guò)若干步迭代后，得到如下最優(yōu)表及最優(yōu)解：最優(yōu)解：x1=3/4,x2=7/4,x3=x4=0,max

z

=5/2,顯然不符合整數(shù)條件。構(gòu)造切割方程：首先，從最優(yōu)表中任意選一非整數(shù)分量，寫(xiě)出其相應(yīng)的約束條件，如：再將上式中的系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和，并移項(xiàng)(整數(shù)移到左邊，分?jǐn)?shù)移到右邊)，如：2021/6/2710從約束條件可以看出，由于x1和x2為非負(fù)整數(shù),所以x3和x4也必然為非負(fù)整數(shù)，這樣，在上式括號(hào)內(nèi)的數(shù)值則為正數(shù)，而且等式右邊必定是負(fù)數(shù)，即有，化簡(jiǎn)后，即得到一切割方程：再將其作為新的約束條件，加到最優(yōu)表中(添加松弛變量x5

)；1100000-1/2-1/2-5/203/47/4-311010-1/41/4013/41/400-3-1001顯然，需要按照對(duì)偶單純形法繼續(xù)迭代，x5為換出變量，x3為換入變量，迭代結(jié)果如下：2021/6/271111000000-1/3-2-1/61111101001/30100001-11/120-1/3111整數(shù)最優(yōu)解：x1=1,x2=1,x3=1,x4=x5=0,max

z

=22021/6/2712例：用隱枚舉法求0－1規(guī)劃解：先找出一個(gè)可行解，顯然，滿足約束條件，是一個(gè)可行解，目標(biāo)值z(mì)為3。由于目標(biāo)函數(shù)是求最大化，所以，增加一個(gè)過(guò)濾條件為：計(jì)算過(guò)程可列表進(jìn)行，為減少計(jì)算工作量，在表中可將目標(biāo)函數(shù)中的系數(shù)按遞增順序排列，并結(jié)合新的目標(biāo)值改進(jìn)過(guò)濾條件。2021/6/2713(0)(1)(2)(3)(4)05-1101

滿足條件是,否約束條件

××計(jì)算過(guò)程如下表:(1)(2)(3)(4)約束條件滿足條件是,否×

3×80211

改進(jìn)過(guò)濾條件,用代替2021/6/2714(1)(2)(3)(4)-2×63×1×約束條件滿足條件是,否×

×再改進(jìn)過(guò)濾條件,用代替最優(yōu)解:最優(yōu)值:2021/6/2715例1.設(shè)有四項(xiàng)工作A、B、C、D，需分配甲、乙、丙、丁四個(gè)人去完成，每個(gè)人只能完成一件工作，每件工作只能由一個(gè)人去完成，這四個(gè)人完成各項(xiàng)工作所需的費(fèi)用如下表所示，問(wèn)如何分配工作才能使總費(fèi)用最?。咳斯ぷ鰽BCD甲乙丙丁4679610835711884962021/6/271600最優(yōu)解:60302016232024指派問(wèn)題(匈牙利法)(例1)修改指派矩陣:試求最優(yōu)解:00000004002021/6/2717修改指派矩陣方法:從每一行元素中減去該行的最小元素；再?gòu)乃镁仃嚨母髁性刂袦p去該列的最小元素。試求最優(yōu)解方法：從第一行開(kāi)始，給只有一個(gè)0元素的行的0元素加圈，記為◎，表示代表這一行的人承擔(dān)了某一項(xiàng)任務(wù)；然后劃去0元素所在列的其它0元素，并記為

，表示這一列所代表的任務(wù)已有人承擔(dān)了，不需要其他人再來(lái)承擔(dān)。給只有一個(gè)0元素的列的0元素加圈，記為◎，然后劃去0元素所在行的其它0元素，并記為

；反復(fù)進(jìn)行，直到所有的0元素加圈和劃去為止。2021/6/2718例2:求下列表所示效率矩陣的指派問(wèn)題的最優(yōu)解:任務(wù)人員甲乙丙丁戊1287154ABCDE791714109612677614610969109指派問(wèn)題(匈牙利法)(例2)2021/6/2719

-2