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

1、整數(shù)規(guī)劃及其數(shù)學(xué)模型 分枝定界法 割平面法 0-1整數(shù)規(guī)劃 指派問(wèn)題 WinQSB軟件應(yīng)用,第五章 整數(shù)規(guī)劃 (Integer Programming),第一節(jié) 整數(shù)規(guī)劃及其數(shù)學(xué)模型,在很多實(shí)際問(wèn)題中，有些變量的取值必須是整數(shù) 在一個(gè)規(guī)劃問(wèn)題中，如果它的某些變量（或全部變量）要求取整數(shù)，這個(gè)規(guī)劃問(wèn)題就稱為整數(shù)規(guī)劃問(wèn)題，其中,如果所有變量都取整數(shù)，就稱為純整數(shù)規(guī)劃或全整數(shù)規(guī)劃 如果僅有一部分變量取整數(shù)，則稱為混合整數(shù)規(guī)劃 若變量值僅限于0或1，則稱為0-1規(guī)劃,一、問(wèn)題的提出,在整數(shù)規(guī)劃問(wèn)題中，不考慮整數(shù)要求，由其他 約束條件和目標(biāo)函數(shù)構(gòu)成的規(guī)劃問(wèn)題稱為該整 數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。 若松弛問(wèn)題是

2、一個(gè)線性規(guī)劃問(wèn)題，則其對(duì)應(yīng)的 整數(shù)規(guī)劃問(wèn)題稱為整數(shù)線性規(guī)劃（ILP）。 本章所討論的整數(shù)規(guī)劃都是指整數(shù)線性規(guī)劃。,（一）下料問(wèn)題,【例5-1】某工地需要長(zhǎng)度不同、直徑相同的成套鋼筋，每套鋼筋由兩根7米長(zhǎng)和七根2米長(zhǎng)的鋼筋組成?，F(xiàn)有15米的圓鋼毛坯150根，應(yīng)如何下料使廢料最少？,(二)工廠選址問(wèn)題,【例5-3】工廠A1和A2生產(chǎn)某種物資，由于該種物資供不應(yīng)求，故需要再建一家工廠，相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1、B2、B3、B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij（j=1,2,3,4）如下表所示,工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)

3、分別為1200萬(wàn)元或1500萬(wàn)元?，F(xiàn)要決定應(yīng)該建設(shè)A3還是A4，才能使今后每年的總費(fèi)用最少。,(三)投資問(wèn)題,【5-2】某投資公司可用于投資的資金是B，可供投資的項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別aj和cj。同時(shí)，由于種種原因，有三個(gè)附加條件： 第一，若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2，反之則不一定； 第二，項(xiàng)目3和項(xiàng)目4中至少選擇一個(gè)； 第三，項(xiàng)目5、項(xiàng)目6和項(xiàng)目7中恰好選擇兩個(gè)。應(yīng)當(dāng)怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大？,二、整數(shù)規(guī)劃模型的一般形式及解的特點(diǎn),求解整數(shù)規(guī)劃問(wèn)題,分析：考慮對(duì)應(yīng)的線性規(guī)劃問(wèn)題(LP),整數(shù)規(guī)劃解的性質(zhì),用單純形法解（如表所示），獲得最優(yōu)解,初始表,最

4、終表,可見(jiàn)，最優(yōu)解為x1=3.25 x2=2.5 z(0) =59/4=14.75,變量不為整數(shù)，顯然（LP）的最優(yōu)解不是（IP）的最優(yōu)解,怎么辦？,湊整：(4, 3), (4, 2), (3, 3), (3, 2) (4, 3), (4, 2), (3, 3)均不可行 (3, 2)對(duì)應(yīng)的目標(biāo)函數(shù)值 z=13 但(4, 1)對(duì)應(yīng)的目標(biāo)函數(shù)值 z=14 可見(jiàn)，直接湊整得到的解不見(jiàn)得是可行解；或者雖是可行解，但不一定是最優(yōu)解 故需要對(duì)整數(shù)規(guī)劃問(wèn)題發(fā)展新的解法 分枝定界法 割平面法 分配問(wèn)題的匈牙利法 0-1規(guī)劃的隱枚舉法,(a),(b),(5/3,5/2),第二節(jié) 整數(shù)規(guī)劃的解法 分枝定界法,【例

5、5-7】求解整數(shù)規(guī)劃問(wèn)題,【思考】 （IP）的可行域與（LP）可行域的關(guān)系如何？ （IP）的最優(yōu)解是否會(huì)優(yōu)于（LP）的最優(yōu)解？ 若（LP）有最優(yōu)解，且其最優(yōu)解為整數(shù)，則它是否也是（IP）的最優(yōu)解？ 若（LP）有最優(yōu)解，但其最優(yōu)解不是整數(shù)，怎么辦？ 假設(shè)已知（IP）的一個(gè)整數(shù)可行解，則（IP）的最優(yōu)解與該解有怎樣的關(guān)系？,適用范圍 全整數(shù)規(guī)劃問(wèn)題或混合整數(shù)規(guī)劃問(wèn)題 本世紀(jì)60年代初由Land Doig和Dakin等人提出 基本思路 設(shè)有最大化的整數(shù)規(guī)劃問(wèn)題(IP)，與它相應(yīng)的線性規(guī)劃問(wèn)題為(LP)松弛問(wèn)題。從解(LP)開始，若其最優(yōu)解不符合整數(shù)條件，那么(LP)的最優(yōu)目標(biāo)函數(shù)必是(IP)最優(yōu)解z

6、*的一個(gè)上界，記作z ;而(IP)的任意可行解的目標(biāo)函數(shù)值將是z*的一個(gè)下界z 。分枝定界法就是將(LP)的可行域分成子區(qū)域（分枝），逐步減小z 和增大z ，最終求得z*的方法。,【例5-7】,考慮全整數(shù)規(guī)劃問(wèn)題：,整數(shù)規(guī)劃的松弛問(wèn)題：,步驟：,1、先不考慮整數(shù)約束，解( IP )的松弛問(wèn)題( LP )，可能得到以下情況之一： ( LP )沒(méi)有最優(yōu)解，則( IP )也沒(méi)有最優(yōu)解，停止計(jì)算； 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算； 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)( LP

7、)的最優(yōu)解為：,2、定界： 記( IP )的目標(biāo)函數(shù)最優(yōu)值為Z* ,以Z(0) 作為Z* 的上界，記為 Z(0) 。再用觀察法找到一個(gè)整數(shù)可行解 X，并以其相應(yīng)的目標(biāo)函數(shù)值 Z作為Z* 的下界，記為Z Z（取xj = 0），則有： Z Z* 。,4、修改上、下界：(按照以下兩點(diǎn)規(guī)則進(jìn)行) 在各分枝問(wèn)題中，找出目標(biāo)函數(shù)值最大者作為新 的上界； 從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最 大者作為新的下界。,5、比較與剪枝 ： 各分枝的目標(biāo)函數(shù)值中，若有小于Z 者，則剪掉此枝， 表明此子問(wèn)題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝 。,如此反復(fù)進(jìn)行，直到得到ZZ* 為止，即得最優(yōu)解 X*,解:用單純形

8、法解對(duì)應(yīng)的(LP)問(wèn)題,如表所示,獲得最優(yōu)解,初始表,最終表,可見(jiàn)，最優(yōu)解為x1=3.25 x2=2.5 z(0) =59/4=14.75,例1、用分枝定界法求解整數(shù)規(guī)劃問(wèn)題,選 x2 進(jìn)行分枝，即增加兩個(gè)約束x22 和x2 3 ，則,分別在(LP1)和(LP2)中引入松弛變量x5和x6 ，將新加約束條件加入上表計(jì)算，即 x2+ x5= 2 , x2+x6=3 得下表:,x1=7/2, x2=2 Z(1) =29/2=14.5 繼續(xù)分枝， 加入約束 x1 3, x1 4,LP1,LP2,x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考慮分枝,接(LP1)繼續(xù)

9、分枝，加入約束 x1 3和x1 4 ，則,分別引入松弛變量x7 和 x8 ，然后進(jìn)行計(jì)算,x1=3, x2=2 Z(3) =13 找到整數(shù)解，問(wèn)題已探明，停止計(jì)算,LP3,x1=4, x2=1 Z(4) =14 找到整數(shù)解，問(wèn)題已探明，停止計(jì)算 因?yàn)閦(4)z(3), 故x1=4, x2=1 為最優(yōu)解,LP4,樹形圖如下：,LP1 x1=7/2, x2=2 Z(1)29/2=14.5,LP x1=13/4, x2=5/2 Z(0) 59/4=14.75,LP2 x1=5/2, x2=3 Z(2)27/2=13.5,LP3 x1=3, x2=2 Z(3) 13,LP4 x1=4, x2=1 Z(

10、4) 14,x22,x23,x13,x14,例2、用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（圖解法計(jì)算）,記為（IP）,解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題,記為（LP）,用圖解法求（LP）的最優(yōu)解，如圖所示,x1,x2,3,3,(18/11,40/11),對(duì)于x118/111.64， 取值x1 1， x1 2 對(duì)于x2 =40/11 3.64，取值x2 3 ，x2 4 先將（LP）劃分為（LP1）和（LP2）,取x1 1, x1 2,x118/11, x2 =40/11 Z(0) =218/11(19.8) 即Z 也是（IP）最小值的下限,有下式：,現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可,

11、同理求（LP2） ,如圖所示 在C 點(diǎn)取得最優(yōu)解 即x12, x2 =10/3, Z(2) 56/318.7 Z(2) Z(0) 原問(wèn)題目標(biāo)函數(shù)值的下界為-18.7 x2 不是整數(shù)，故利用3 10/34 加入條件,x1,x2,3,3,(18/11,40/11),先求（LP1）,如圖所示。此時(shí)，在B 點(diǎn)取得最優(yōu)解 x11, x2 =3, Z(1)16 找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。且由此可知目標(biāo)函數(shù)最優(yōu)值的上界為-16,1,1,B,A,C,加入條件： x23, x24 有下式：,只要求出（LP3）和（LP4）的最優(yōu)解即可,x1,x2,3,3,(18/11,40/11),1,1,B,A,C

12、,先求（LP3）,如圖所示。此時(shí)D 在點(diǎn)取得最優(yōu)解 即 x112/5=2.4, x2 =3, Z(3)-87/5=-17.4-18.7 但x112/5不是整數(shù)，可繼續(xù)分枝。即 3x12,D,求（LP4），如圖所示 無(wú)可行解，不再分枝,在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3x12有下式：,只要求出（LP5）和（LP6）的最優(yōu)解即可,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求（LP5）,如圖所示。此時(shí)E 在點(diǎn)取得最優(yōu)解 即 x12, x2 =3, Z(5)17 找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。,E,求（LP6），如圖所示。此時(shí) F在點(diǎn)取得最優(yōu)解 x13,

13、x2 =2.5, Z(6)31/2=15.5 Z(5),F,如對(duì)Z(6) 繼續(xù)分解，其最小值也不會(huì)低于15.5，問(wèn)題探明,剪枝,至此，原問(wèn)題(IP)的最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) 17 以上的求解過(guò)程可以用一個(gè)樹形圖表示如右：,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP3 x1=12/5, x2=3 Z(3) 17.4,LP4 無(wú)可 行解,LP5 x1=2, x2=3 Z(5) 17,LP6 x1=3, x2=5/2 Z(6) 15.5,x

14、11,x12,x23,x24,x12,x13,練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題,x11,x12,x22,x23,x12,x13,一、計(jì)算步驟 1、用單純形法求解( IP )對(duì)應(yīng)的松弛問(wèn)題( LP ) 若( LP )沒(méi)有最優(yōu)解，則( IP )也沒(méi)有最優(yōu)解，停止計(jì)算； 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算； 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。,第三節(jié) 整數(shù)規(guī)劃的解法 割平面法,2、從(LP)的最優(yōu)解中，任選不為整數(shù)的分量xi ,將最優(yōu)單純形表中該行的系數(shù) 和 分解為整數(shù)部分和小數(shù)部分之和，

15、并以該行為源行，作割平面方程,割平面方程,3、將由割平面方程得到的約束條件作為一個(gè)新的約束條件置于最優(yōu)單純形表中，用對(duì)偶單純形法求出新的最優(yōu)解，返回1。,例1 、用割平面法求解整數(shù)規(guī)劃問(wèn)題,解：增加松弛變量x3和x4 ，得到(LP)的初始單純形表和最優(yōu)單純形表：,此題的最優(yōu)解為：X =(13/4 ,5/2) 。但不是整數(shù)最優(yōu)解，引入割平面。可以使用的割平面的條件有:,為加快割平面的速度，一般選擇較大的 fi 作為割平面方程進(jìn)行計(jì)算,現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中,割平面方程為:,【例5-7】求解整數(shù)規(guī)劃問(wèn)題,【練習(xí)】求解整數(shù)規(guī)劃問(wèn)題,01整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的

16、決策變量xi 只取兩個(gè)值0或1，一般的解法為隱枚舉法,【例5-11】求解下列01規(guī)劃問(wèn)題,第四節(jié) 0-1整數(shù)規(guī)劃,由上表可知，問(wèn)題的最優(yōu)解為 X*=( x1=1， x2=0， x3=1 ),解：對(duì)于01規(guī)劃問(wèn)題，由于每個(gè)變量只取0、1兩個(gè)值，一般會(huì)用窮舉法來(lái)求解，即將所有的0、1組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。,由上表可知： x1 =0，x2=0，x3=1是一個(gè)可行解，為盡快找到最優(yōu)解，可將3x12x25x35作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5的組合不必討論，如下表。,問(wèn)題的最優(yōu)解為 X*=( x1 =1，x2=0，x3=1 ),隱枚舉法,如果重新排列變量的順序可使問(wèn)題更快地求

17、得最優(yōu)解，如：,問(wèn)題的最優(yōu)解為 X*=( x1=1，x2=0，x3=1 ),【例】求解下列01規(guī)劃問(wèn)題,解：令 x11x1, x2=1- x2, x4=1- x4，則目標(biāo)函數(shù)變?yōu)?此時(shí)，x*=(1, 0, 1, 0)，z*=-2,練習(xí)：求解下列01規(guī)劃問(wèn)題,所以， 原問(wèn)題的最優(yōu)解為： X*(0, 0, 1, 0, 0)，Z*=8,第五節(jié) 指派問(wèn)題,在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n 項(xiàng)不同的任務(wù)，需要n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，指派哪個(gè)人去完成哪項(xiàng)任務(wù)，可使完成 n 項(xiàng)任務(wù)的總效

18、率最高（或所需時(shí)間最少）？這類問(wèn)題稱為指派問(wèn)題或分配問(wèn)題。,每一項(xiàng)工作只能分配給一個(gè)人； 每一個(gè)人只能并且必須接受一項(xiàng)工作,一、指派問(wèn)題的一般提法,【5-13】某工廠要生產(chǎn)四種產(chǎn)品，該工廠有四個(gè)車間都可以生產(chǎn)這四種產(chǎn)品。但由于設(shè)備情況與技術(shù)情況不同，所以生產(chǎn)成本不同，其單位產(chǎn)品的生產(chǎn)成本如表所示。問(wèn)應(yīng)當(dāng)如何分配這四種產(chǎn)品到各車間，才能使總的生產(chǎn)成本最??？試建立該問(wèn)題的數(shù)學(xué)模型。,解 引入0-1變量xij (i, j1,2,3,4,5)，令：,這個(gè)問(wèn)題的約束條件如下：,(1)一個(gè)車間只生產(chǎn)一種產(chǎn)品，即,(2)一種產(chǎn)品只由一個(gè)車間生產(chǎn)，即,(3)變量工xij 必須等于0或1，即xij =0或1。,

19、目標(biāo)函數(shù)為：Min,其數(shù)學(xué)模型為：,設(shè)n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作,每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j件工作的的效率（ 時(shí)間或費(fèi)用）為cij (i =1, 2, , n; j =1, 2, , n)并假設(shè)cij 0。問(wèn)應(yīng)如何分配才能使總效率（ 時(shí)間或費(fèi)用）最高？,效率矩陣（成本矩陣）:(cij )nn,二、匈牙利法,分配問(wèn)題是0-1規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，但這些方法卻沒(méi)有充分利用指派問(wèn)題的特點(diǎn)。,庫(kù)恩(W.W.Kuhn)于1955年提出了指派問(wèn)題的解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩

20、陣中獨(dú)立零元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有零元素的最小直線數(shù)，習(xí)慣上稱之為匈牙利解法。,分配問(wèn)題最優(yōu)解的以下性質(zhì)：若從系數(shù)矩陣(cij )的某行(或某列)各元素分別減去該行（列）的最小元素，得到新矩陣(cij),那么以(cij)為系數(shù)矩陣求得的最優(yōu)解和利用原系數(shù)矩陣求得的最優(yōu)解相同。,證明,設(shè)成本矩陣第一行各元素均減去同一個(gè)數(shù)k，得到的新矩陣記為(cij ),第一步：變換成本矩陣，使每行每列中至少出現(xiàn)一個(gè)0元素 (1) 令(cij) nn的每行元素都減去該行的最小元素； (2) 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。,匈牙利法的步驟（以例5-13為例）,第二

21、步：試求最優(yōu)解 在新矩陣中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為： (1) 從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加，記作 。然后劃去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了； (2) 給只有一個(gè)0元素的列(行)中的0元素加，記作 ；然后劃去 所在行的0元素，記作 ； (3) 反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止；,0,0,0,0,(4) 若仍有沒(méi)有劃的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有

22、0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加(表示選擇性多的要“禮讓”選擇性少的)，然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止； (5) 若 元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已得到;若m n, 則轉(zhuǎn)入下一步。,0,例、有一份中文說(shuō)明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書譯成不同語(yǔ)種的說(shuō)明書所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？,求解過(guò)程如下： 第一步，變換系數(shù)矩陣：,5,第二步，試指派：,找到 3 個(gè)獨(dú)立零元素 但 m = 3 n = 4,第三步：作最少的直線覆蓋所有0元素 (1)