運(yùn)籌學(xué)第五章整數(shù)規(guī)劃.ppt

第五章 整數(shù)規(guī)劃,5.1 整數(shù)規(guī)劃問(wèn)題的提出,例5-1 某廠擬用集裝箱托運(yùn)甲、乙兩種貨物。每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如下表所示：,問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得的利潤(rùn)最大？,解：,設(shè)x1 , x2 分別為甲、乙兩種貨物的托運(yùn)箱數(shù)，則模型為：,Max z = 20x1 +10x2,St. 5x1 +4x2 24,2x1 +5 x2 13,x1 ，x2 0,x1 ，x2 整數(shù),暫不考慮整數(shù)約束，求得最優(yōu)解為,x1 = 4.8 ，x2 = 0， Max z = 96,（1）若,x1 = 4.8 ，x2 = 0,x1 = 5 ，x2 = 0,不是可行解；,（2）若,x1 = 4.8 ，x2 = 0,x1 = 4，x2 = 0,是可行解，但不是最優(yōu)解,因?yàn)?x1 = 4，x2 = 0時(shí)，z = 80,而可行解,x1 = 4，x2 = 1時(shí)，z = 90,5.2 整數(shù)規(guī)劃的類型,整數(shù)規(guī)劃按變量取值的不同，可以分為以下幾類：,1. 純整數(shù)規(guī)劃：所有的變量都取整數(shù)值；,2. 混合整數(shù)規(guī)劃：部分變量取整數(shù)值；,3. 01規(guī)劃：所有變量只取0，1兩個(gè)值；,4. 01混合規(guī)劃：部分變量只取0，1兩個(gè)值。,整數(shù)規(guī)劃（Integer Programming）問(wèn)題的一般形式,整數(shù)規(guī)劃與其松弛問(wèn)題,當(dāng)放棄整數(shù)約束時(shí)得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問(wèn)題。,整數(shù)規(guī)劃的可行域是松弛問(wèn)題的可行域，反之不成立。,5.3.1 混合整數(shù)規(guī)劃的求解-分枝定界方法,分枝：當(dāng) 不符合整數(shù)要求時(shí)，構(gòu)造兩個(gè)約束條件：,加入松弛問(wèn)題分別形成兩個(gè)子問(wèn)題（分枝）,定界：當(dāng)子問(wèn)題獲得整數(shù)規(guī)劃的一個(gè)可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個(gè)界限,5.3 整數(shù)規(guī)劃的解法,分枝定界法基本思想：,首先不考慮變量的整數(shù)約束，求解相應(yīng)的線性規(guī)劃問(wèn)題：,O,A,C,D,xr,Ir,Ir+1,.,.,.,.,分枝,每一次分枝得到的子問(wèn)題的最優(yōu)目標(biāo)函數(shù)值都要比上一層問(wèn)題的最優(yōu)目標(biāo)函數(shù)值小，或者相等。,z0,z11,z12,z21,z22,z23,z24,整數(shù)解,下界,若z21 z11，z22 z11，則無(wú)須繼續(xù)分枝,定界,利用定界，可以終止許多不必要的分枝過(guò)程。,如果在分枝過(guò)程中得到新的整數(shù)解且該整數(shù)解的目標(biāo)函數(shù)值大于已記錄的下界，則應(yīng)將較大的整數(shù)解的目標(biāo)函數(shù)值代替原來(lái)的下界。,當(dāng)所有最低一層子問(wèn)題出現(xiàn)以下三種情況時(shí)，分枝定界法終止：,1. 子問(wèn)題無(wú)可行解；,2. 子問(wèn)題已獲得整數(shù)解；,3. 子問(wèn)題的目標(biāo)函數(shù)值未達(dá)到下界。,例,S,解S得：,S2,對(duì)S分枝：,構(gòu)造約束：,和,形成分枝問(wèn)題S1和S2，得解B和C,S1,1,3,2,X,2,5,4,S2,對(duì)S1分枝：,構(gòu)造約束：,和,形成分枝問(wèn)題S11和S12，得解D,S12,S11無(wú)可行解,1,3,2,X,2,5,4,S2,對(duì)S12分枝：,構(gòu)造約束：,和,形成分枝問(wèn)題S121和S122，得解E和F,S121,S122,首先求解整數(shù)規(guī)劃（IP）對(duì)應(yīng)的松弛問(wèn)題（LP），如果（LP）的最優(yōu)解不是整數(shù)解，則逐次增加一個(gè)新約束（即割平面），它能割去松弛問(wèn)題可行域中不含整數(shù)解的區(qū)域.逐次切割，直到得到一個(gè)整數(shù)最優(yōu)極點(diǎn)（即整數(shù)解）為止。,5.3.2 純整數(shù)規(guī)劃的求解-Gomory割平面方法,基本思想：,（1）首先放棄變量的整數(shù)要求，求得線性規(guī)劃的最優(yōu)解；,（2）如果最優(yōu)解是一個(gè)非整數(shù)解，則構(gòu)造一個(gè)新的約束，對(duì)線性規(guī)劃問(wèn)題的可行域進(jìn)行切割，切除已得到的最優(yōu)解，但保留原可行域中所有的整數(shù)解，求解新的線性規(guī)劃問(wèn)題；,（3）如果最優(yōu)解仍不是整數(shù)解，再以增加附加約束的方法將其切除，但仍保持最初可行域中所有的整數(shù)解，直至求得一個(gè)整數(shù)最優(yōu)解為止。,整數(shù)規(guī)劃的求解-Gomory割平面方法,松弛問(wèn)題的最優(yōu)解,Gomory定理,在松弛問(wèn)題的最優(yōu)單純形表中，假如有一常數(shù)項(xiàng) 不是整數(shù)，且對(duì)應(yīng)的方程為：,分解 和 成最大整數(shù)與正分?jǐn)?shù)之和：,則,包含了整數(shù)規(guī)劃的所有整數(shù)可行解，但不包括松弛問(wèn)題的最優(yōu)解。,例題求解,選擇第一個(gè)方程：,分解為：,在原松弛問(wèn)題中加入約束：,即,形成松弛問(wèn)題2,整數(shù)點(diǎn),松弛問(wèn)題2的最優(yōu)解,割平面,選擇第四個(gè)方程（具有最大分?jǐn)?shù)部分）：,分解為：,在松弛問(wèn)題2中加入約束：,即,形成松弛問(wèn)題3,得到最優(yōu)解,割平面：,如果選擇第二個(gè)方程：,分解為：,在松弛問(wèn)題2中加入約束：,即,形成松弛問(wèn)題3,沒(méi)有找到整數(shù)解，繼續(xù)做下去,5.3.3 整數(shù)規(guī)劃的圖解法,x1,x2,6,4.8,2.6,6.5,*,*,*,*,*,*,*,5.3.4 整數(shù)規(guī)劃的計(jì)算機(jī)求解,LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 90.00001 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 90.00000 VARIABLE VALUE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0,Max 20x1 +10x2 st 5x1 +4x2 24 2x1 +5x2 13 end gin x1 x2 (或gin 2),5.4 整數(shù)規(guī)劃的應(yīng)用,例5-2 投資場(chǎng)所的選擇,某公司擬在城市的東、南、西、北四區(qū)建立門市部，擬議中有10個(gè)位置Ai （i = 1,2, , 10）可供選擇，并規(guī)定： 在東區(qū)，由A1 、A2 、A3 三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)，由A4 、A5 兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)，由A6 、A7 兩個(gè)點(diǎn)中至少選一個(gè)； 在北區(qū)，由A8 、A9 、A10 三個(gè)點(diǎn)中至少選兩個(gè)。 Ai 各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)如下表所示：,但投資總額不能超過(guò)720萬(wàn)元。問(wèn)應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？,解：,設(shè),(i = 1,2, , 10),Z = 36 x1,+ 40 x2,+ 50 x3,Max,100x1,+ 120x2,+ 150x3,720,x4 + x5 1,x1 + x2 + x3 2,x6 + x7 1,xi = 0或1,+ 22 x4,+ 20 x5,+ 30 x6,+ 25 x7,+ 48 x8,+ 58 x9,+ 61 x10,+ 80x4,+ 70x5,+ 90x6,+ 80x7,+ 140x8,+ 160x9,+ 180x10,x8 + x9 + x10 2,在東區(qū)，由A1 、A2 、A3 三個(gè)點(diǎn)中至多選兩個(gè),在西區(qū)，由A4 、A5 兩個(gè)點(diǎn)中至少選一個(gè),在南區(qū)，由A6 、A7 兩個(gè)點(diǎn)中至少選一個(gè),在北區(qū)，由A8 、A9 、A10 三個(gè)點(diǎn)中至少選兩個(gè),例5-3 資金分配問(wèn)題,某集團(tuán)公司計(jì)劃新建五個(gè)工廠A1 、A2 、A3 、A4 、A5 ，所需投資分別為100、150、125、200、250萬(wàn)元?，F(xiàn)僅有資金總額750萬(wàn)元，又據(jù)估計(jì)，工廠建成后每年可獲利潤(rùn)分別為20、25、20、40、45萬(wàn)元。試決定應(yīng)建哪些工廠，使投資總額不超過(guò)現(xiàn)有資金總額，并使工廠建成后每年獲得的總利潤(rùn)最大？,解：,對(duì)于工廠Ai （i = 1,2, , 5）來(lái)說(shuō)，只有建或不建兩種情況，因此，可設(shè),xi =,1 當(dāng)建工廠Ai 時(shí)，（i = 1,2, , 5）,0 相反,則模型為,Max z = 20x1 + 25x2 + 20x3 +40 x4 +45 x5,st. 100x1 + 150x2 + 125x3 +200 x4 +250 x5 750,xi = 0或1 （i = 1,2, , 5）,例5-4 固定成本問(wèn)題,高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如下表所示：,資源,金屬板（噸）,勞動(dòng)力（人月）,機(jī)器設(shè)備（臺(tái)月）,小號(hào)容器,中號(hào)容器,大號(hào)容器,2 4 8,2 3 4,1 2 3,不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板有500噸，勞動(dòng)力有300人月，機(jī)器有100臺(tái)月。此外，不管每種容器制造的數(shù)量是多少，都要支付一筆固定費(fèi)用：小號(hào)是100萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。,解：分析問(wèn)題,設(shè)x1 、x2 、x3 分別為小號(hào)容器、中號(hào)容器、大號(hào)容器的生產(chǎn)數(shù)量；,各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，故設(shè)：,yi =,1 當(dāng)生產(chǎn)第 i 種容器，即 xi 0,0 當(dāng)不生產(chǎn)第 i 種容器，即 xi =0,目標(biāo)函數(shù)：為扣除了固定費(fèi)用后的利潤(rùn),約束條件：金屬板、勞動(dòng)力、機(jī)器設(shè)備的限制,為避免出現(xiàn)某種容器不投入固定費(fèi)用就生產(chǎn)這樣一種不合理情況，必須加上如下約束：,x1 y1 M,x2 y2 M,x3 y3 M,M是充分大的數(shù)，例如，此問(wèn)題中，M可取200,x1 200y1,x2 200y2,x3 200y3,線性規(guī)劃模型為：,目標(biāo)函數(shù),Max z = 4x1 + 5x2 + 6x3 100y1 150y2 200y3,金屬板限制,2x1 + 4x2 + 8x3 500,勞動(dòng)力限制,2x1 + 3x2 + 4x3 300,機(jī)器設(shè)備限制,x1 + 2x2 + 3x3 100,x1 y1 M,x2 y2 M,x3 y3 M,x1 ，x2 ，x3 0,y1 ，y2 ，y3 為01變量,求解得：,x1 =100，x2 =0，x3 =0,y1 =1，y2 =0，y3 =0,例5-5 分布系統(tǒng)設(shè)計(jì),某企業(yè)在A1 地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱。為了擴(kuò)大生產(chǎn)，打算在A2 、 A3 、 A4 、 A5 地中再選擇幾個(gè)地方建廠。已知在A2 、 A3 、 A4 、 A5 地建廠的固定成本分別為175、300、375、500千元，各產(chǎn)地的產(chǎn)量及各銷地的銷量及從產(chǎn)地到銷地的單位運(yùn)價(jià)如下表所示。,（1）問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得總固定成本和總運(yùn)輸費(fèi)用之和最?。唬?）如果由于政策要求必須在A2 、 A3 建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠？,解：,設(shè) xij 為從Ai 到Bj 的運(yùn)輸量；,yi =,1 當(dāng)Ai 廠址被選中；,0 當(dāng)Ai 廠址沒(méi)被選中,Min z = 175y2 +300y3 +375y4 + 500y5 + 8x11 + 4x12 + 3x13 + 5x21 + 2x22 + 3x23 + 4x31 + 3x32 + 4x33 + 9x41 + 7x42 + 5x43 + 10x51 + 4x52 + 2x53,A1 廠的產(chǎn)量限制,x11 + x12 + x13 30,對(duì)于A2 、 A3 、 A4 、 A5 ，只有廠址被選中，才會(huì)有生產(chǎn)量,x21 + x22 + x23 10 y2,x31 + x32 + x33 20 y3,x41 + x42 + x43 30 y4,x51 + x52 + x53 40 y5,各銷地的銷量限制,x11 + x21 + x31 +x41 + x51 = 30,x12 + x22 + x32 +x42 + x52 = 20,x13 + x23 + x33 +x43 + x53 = 20,xij 0，為整數(shù)， yi 為01變量,（1）,求解得：,y5 =1， x52 = 20， x53 = 20， x11 = 30，其余為0，最優(yōu)目標(biāo)函數(shù)值=860,（2）,在上述模型上加上約束條件：,y2 + y3 =1,求解得：,y2 =1， y4 =1， x22 = 10， x41 = 30， x12 = 10， x13 = 20，其余為0，最優(yōu)目標(biāo)函數(shù)值=940,0-1規(guī)劃的求解隱枚舉方法,最優(yōu)解（x1,x2,x3)=(1,0,1); z=8,隱枚舉方法求解過(guò)程,n個(gè)員工分配做n項(xiàng)工作，已知第i個(gè)員工做第j項(xiàng)工作的成本為cij，i=1,n; j=1,n。求最佳分配方案。,4.5 指派問(wèn)題與匈亞利法,指派問(wèn)題的數(shù)學(xué)模型,s.t.,指派問(wèn)題的解應(yīng)對(duì)應(yīng)于成本矩陣的不同行與不同列，且總成本最小,對(duì)于每個(gè)指派問(wèn)題，需要有效率矩陣（cij ）,（cij ）=,c11 c12 c1n,c21 c22 c2n,cn1 cn2 cnn,引入變量,xij =,1 當(dāng)指派第i 個(gè)人完成第j項(xiàng)任務(wù),0 當(dāng)不指派第i 個(gè)人完成第j項(xiàng)任務(wù),則每人的效率及目標(biāo)為,c11 x11,+c12 x12,+.,+c1n x1n,c21 x21,+c22 x22,+.,+c2n x2n,.,cn1 xn1,+cn2 xn2,+.,+cnn xnn,.,Z=,Min,n項(xiàng)任務(wù)，恰好有n個(gè)人承擔(dān)去完成。由于每人的專長(zhǎng)不同，各人完成不同的任務(wù)效率也不同。于是就產(chǎn)生了應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高。,第1項(xiàng)任務(wù)只能由1人完成,x11 + x21 + . xn1 = 1,第2項(xiàng)任務(wù)只能由1人完成,x12 + x22 + . xn2 = 1,.,第j項(xiàng)任務(wù)只能由1人完成,x1j + x2j + . xnj = 1,.,第n項(xiàng)任務(wù)只能由1人完成,x1n + x2n + . xnn = 1,.,.,.,.,(j =1, 2, , n),第1個(gè)人只能完成1項(xiàng)任務(wù),x11 + x12 + . x1n = 1,第2個(gè)人只能完成1項(xiàng)任務(wù),x21 + x22 + . x2n = 1,.,.,第i個(gè)人只能完成1項(xiàng)任務(wù),xi1 + xi2 + . xin = 1,.,.,第n個(gè)人只能完成1項(xiàng)任務(wù),xn1 + xn2 + . xnn = 1,.,.,(i =1, 2, , n),故模型為,(j =1, 2, , n),第j項(xiàng)任務(wù)只能由1人完成,(i =1, 2, , n),第i個(gè)人只能完成1項(xiàng)任務(wù),xij = 0或1,滿足上述約束條件的可行解xij 可寫(xiě)成矩陣形式，稱為解矩陣,（xij ）=,0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1,指派問(wèn)題的求解方法,（1）計(jì)算機(jī)求解,（2）匈牙利法,（3）隱枚舉法,指派問(wèn)題的性質(zhì),定理：對(duì)于指派問(wèn)題，成本矩陣的任一行(或列)減去(或加上)一個(gè)相同的數(shù)得到的新指派問(wèn)題與原問(wèn)題同解。,定理：,系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。,匈牙利法的計(jì)算步驟為：,第一步：使系數(shù)矩陣出現(xiàn)0元素。,第二步：進(jìn)行試指派，以尋求最優(yōu)解。,第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最 多的獨(dú)立元素?cái)?shù)。,第四步：變換矩陣增加0元素，再返回第二步。,第四步說(shuō)明：調(diào)整效益矩陣，使之增加一些零元素： (1) 在沒(méi)有被直線覆蓋的元素中，找出最小元素； (2) 在沒(méi)有被直線覆蓋的元素中，減去最小元素； (3) 在直線交叉處的元素中，加上最小元素； (4) 被一條直線覆蓋的元素不變.,例4-6 有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作E、J、G、R。現(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種的說(shuō)明書(shū)所需的時(shí)間如下表所示：,問(wèn)應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？,解：用匈牙利法。,第一步：使系數(shù)矩陣出現(xiàn)0元素。,（cij ）=,2 15 13 4,10 4 14 15,9 14 16 13,7 8 11 9,2,4,9,7,0 13 11 2,6 0 10 11,0 5 7 4,0 1 4 2,4,2,0 13 7 0,6 0 6 9,0 5 3 2,0 1 0 0,=（bij ）,第二步：進(jìn)行試指派。,可見(jiàn)，m = n = 4，所以得最優(yōu)解為,（xij ）=,0 0 0 1,0 1 0 0,1 0 0 0,0 0 1 0,即指定甲譯俄文，乙譯日文，丙譯英文，丁譯德文，所需總時(shí)間最少。,所需時(shí)間為,例4-7 求下表所示效率矩陣的指派問(wèn)題的最優(yōu)解。,解：第一輪,第一步：使系數(shù)矩陣出現(xiàn)0元素。,12 7 9 7 9,8 9 6 6 6,7 17 12 14 9,15 14 6 6 10,4 10 7 10 9,7,6,7,6,4,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,第二步：進(jìn)行試指派。,由于m = 4，n = 5，解題沒(méi)有完成。,第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素（不同行不同列的零元素）數(shù)。,由于 l = 4 n = 5，轉(zhuǎn)第四