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

1、整數(shù)規(guī)劃及其數(shù)學(xué)模型整數(shù)規(guī)劃及其數(shù)學(xué)模型分枝定界法分枝定界法割平面法割平面法0-1整數(shù)規(guī)劃整數(shù)規(guī)劃指派問題指派問題WinQSB軟件應(yīng)用軟件應(yīng)用第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃 (Integer Programming) 第一節(jié)第一節(jié) 整數(shù)規(guī)劃及其數(shù)學(xué)模型整數(shù)規(guī)劃及其數(shù)學(xué)模型在很多實(shí)際問題中，有些變量的取值必須是整數(shù)在很多實(shí)際問題中，有些變量的取值必須是整數(shù)在一個(gè)規(guī)劃問題中，如果它的在一個(gè)規(guī)劃問題中，如果它的某些變量（或全部某些變量（或全部變量）要求取整數(shù)變量）要求取整數(shù)，這個(gè)規(guī)劃問題就稱為，這個(gè)規(guī)劃問題就稱為整數(shù)規(guī)整數(shù)規(guī)劃問題劃問題，其中，其中v如果所有變量都取整數(shù)，就稱為如果所有變量都取整數(shù)，

2、就稱為純整數(shù)規(guī)劃或全整純整數(shù)規(guī)劃或全整數(shù)規(guī)劃數(shù)規(guī)劃v如果僅有一部分變量取整數(shù)，則稱為如果僅有一部分變量取整數(shù)，則稱為混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃v 若變量值僅限于若變量值僅限于0 0或或1 1，則稱為，則稱為0-10-1規(guī)劃規(guī)劃一、問題的提出一、問題的提出在整數(shù)規(guī)劃問題中，不考慮整數(shù)要求，由其他在整數(shù)規(guī)劃問題中，不考慮整數(shù)要求，由其他約束條件和目標(biāo)函數(shù)構(gòu)成的規(guī)劃問題稱為該整約束條件和目標(biāo)函數(shù)構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的數(shù)規(guī)劃問題的松弛問題松弛問題。若松弛問題是一個(gè)線性規(guī)劃問題，則其對(duì)應(yīng)的若松弛問題是一個(gè)線性規(guī)劃問題，則其對(duì)應(yīng)的整數(shù)規(guī)劃問題稱為整數(shù)規(guī)劃問題稱為整數(shù)線性規(guī)劃（整數(shù)線性規(guī)劃（ILP

3、）。本章所討論的整數(shù)規(guī)劃都是指整數(shù)線性規(guī)劃。本章所討論的整數(shù)規(guī)劃都是指整數(shù)線性規(guī)劃。 （一）下料問題（一）下料問題【例【例5-1】某工地需要長度不同、直徑相同的成套】某工地需要長度不同、直徑相同的成套鋼筋，每套鋼筋由兩根鋼筋，每套鋼筋由兩根7米長和七根米長和七根2米長的鋼筋米長的鋼筋組成?，F(xiàn)有組成?，F(xiàn)有15米的圓鋼毛坯米的圓鋼毛坯150根，應(yīng)如何下料根，應(yīng)如何下料使廢料最少？使廢料最少？ 下料方式下料方式7 7米長的鋼筋（根）米長的鋼筋（根）2 2米長的鋼筋（根）米長的鋼筋（根）廢料廢料1 12 20 01 12 21 14 40 03 30 07 71 1 (二二)工廠選址問題工廠選址問題【

4、例【例5-35-3】工廠】工廠A1和和A2生產(chǎn)某種物資，由于該種物資供不應(yīng)求，生產(chǎn)某種物資，由于該種物資供不應(yīng)求，故需要再建一家工廠，相應(yīng)的建廠方案有故需要再建一家工廠，相應(yīng)的建廠方案有A3和和A4兩個(gè)。這種物兩個(gè)。這種物資的需求地有資的需求地有B1、B2、B3、B4四個(gè)。各工廠年生產(chǎn)能力、各地四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij（j=1,2,3,4）如如下表所示下表所示B1B2B3B4生產(chǎn)能力生產(chǎn)能力（千噸（千噸/年）年）A12934400A28357600A37612200A44525200需求量需求量（千噸（千噸/

5、年）年）350400300150工廠工廠A3或或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為12001200萬元或萬元或15001500萬元。現(xiàn)要決定應(yīng)該建設(shè)萬元。現(xiàn)要決定應(yīng)該建設(shè)A3還是還是A4，才能使今后每年的總，才能使今后每年的總費(fèi)用最少。費(fèi)用最少。( (三三) )投資問題投資問題【5-2】某投資公司可用于投資的資金是】某投資公司可用于投資的資金是B，可供，可供投資的項(xiàng)目有投資的項(xiàng)目有n個(gè)，項(xiàng)目個(gè)，項(xiàng)目j所需投資額和預(yù)期收益所需投資額和預(yù)期收益分別分別aj和和cj。同時(shí)，由于種種原因，有三個(gè)附加。同時(shí)，由于種種原因，有三個(gè)附加條件：條件：第一，若選擇項(xiàng)目第一，若選

6、擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目，就必須同時(shí)選擇項(xiàng)目2，反，反之則不一定；之則不一定；第二，項(xiàng)目第二，項(xiàng)目3和項(xiàng)目和項(xiàng)目4中至少選擇一個(gè)；中至少選擇一個(gè)；第三，項(xiàng)目第三，項(xiàng)目5、項(xiàng)目、項(xiàng)目6和項(xiàng)目和項(xiàng)目7中恰好選擇兩個(gè)。中恰好選擇兩個(gè)。應(yīng)當(dāng)怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大？應(yīng)當(dāng)怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大？整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式且部分或全部為整數(shù)，或 n)21(j 0)21( )min(max11jnjijijnjjjxmibxaxcZZ 依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃整數(shù)規(guī)劃/ /全整

7、數(shù)規(guī)劃、混合整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0 01 1整數(shù)規(guī)劃整數(shù)規(guī)劃二、整數(shù)規(guī)劃模型的一般形式及解的特點(diǎn)二、整數(shù)規(guī)劃模型的一般形式及解的特點(diǎn)且且為為整整數(shù)數(shù)0,143292)(23max21212121xxxxxxIPxxZ求解整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題分析：考慮對(duì)應(yīng)的線性規(guī)劃問題分析：考慮對(duì)應(yīng)的線性規(guī)劃問題(LP)0,143292)(23max21212121xxxxxxLPxxZ整數(shù)規(guī)劃解的性質(zhì)整數(shù)規(guī)劃解的性質(zhì)3200CB XB b x1x2x3x40 x3921109/20 x414230114/2j32003200CB XB b x1x2x3x43x113/4103/4-1/

8、42x25/201-1/21/2j00-5/4-1/4用單純形法解（用單純形法解（如表所示如表所示），獲得最優(yōu)解），獲得最優(yōu)解初始表初始表最終表最終表可見，最優(yōu)解為可見，最優(yōu)解為x1=3.25 x2=2.5 z(0) =59/4=14.75變量不為整數(shù)，顯然（變量不為整數(shù)，顯然（LP）的最優(yōu)解不是（）的最優(yōu)解不是（IP）的最優(yōu)解）的最優(yōu)解 湊整湊整：(4, 3), (4, 2), (3, 3), (3, 2) (4, 3), (4, 2), (3, 3)均不可行均不可行 (3, 2)對(duì)應(yīng)的目標(biāo)函數(shù)值對(duì)應(yīng)的目標(biāo)函數(shù)值 z=13 但但(4, 1)對(duì)應(yīng)的目標(biāo)函數(shù)值對(duì)應(yīng)的目標(biāo)函數(shù)值 z=14可見，直接

9、湊整得到的解不見得是可行解；或者雖是可行可見，直接湊整得到的解不見得是可行解；或者雖是可行解，但不一定是最優(yōu)解解，但不一定是最優(yōu)解故需要對(duì)整數(shù)規(guī)劃問題發(fā)展新的解法故需要對(duì)整數(shù)規(guī)劃問題發(fā)展新的解法 分枝定界法分枝定界法 割平面法割平面法 分配問題的匈牙利法分配問題的匈牙利法 0-1規(guī)劃的隱枚舉法規(guī)劃的隱枚舉法0 x2 x1(a)(b)(5/3,5/2)第二節(jié)第二節(jié) 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法 分枝定界法分枝定界法且均為整數(shù)0,521023max2122121xxxxxxxz【例【例5-75-7】求解整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題【思考【思考】（IPIP）的最優(yōu)解是否會(huì)優(yōu)于（）的最優(yōu)解是否會(huì)優(yōu)于（

10、LPLP）的最優(yōu)解？）的最優(yōu)解？（IPIP）的可行域與（）的可行域與（LPLP）可行域的關(guān)系如何？）可行域的關(guān)系如何？若（若（LPLP）有最優(yōu)解，且其最優(yōu)解為整數(shù)，則它是否也）有最優(yōu)解，且其最優(yōu)解為整數(shù)，則它是否也是（是（IPIP）的最優(yōu)解？）的最優(yōu)解？若（若（LPLP）有最優(yōu)解，但其最優(yōu)解不是整數(shù)，怎么辦？）有最優(yōu)解，但其最優(yōu)解不是整數(shù)，怎么辦？假設(shè)已知（假設(shè)已知（IPIP）的一個(gè)整數(shù)可行解，則（）的一個(gè)整數(shù)可行解，則（IPIP）的最優(yōu)）的最優(yōu)解與該解有怎樣的關(guān)系？解與該解有怎樣的關(guān)系？v 適用范圍適用范圍 全整數(shù)規(guī)劃問題或混合整數(shù)規(guī)劃問題全整數(shù)規(guī)劃問題或混合整數(shù)規(guī)劃問題v 本世紀(jì)本世紀(jì)60

11、60年代初由年代初由Land DoigLand Doig和和DakinDakin等人提出等人提出v 基本思路基本思路 設(shè)有最大化的整數(shù)規(guī)劃問題設(shè)有最大化的整數(shù)規(guī)劃問題(IP)，與它相應(yīng)的線性規(guī)，與它相應(yīng)的線性規(guī)劃問題為劃問題為(LP)松弛問題。從解松弛問題。從解(LP)開始，若其開始，若其最優(yōu)解不符合整數(shù)條件，那么最優(yōu)解不符合整數(shù)條件，那么(LP)的最優(yōu)目標(biāo)函數(shù)的最優(yōu)目標(biāo)函數(shù)必是必是(IP)最優(yōu)解最優(yōu)解z*的一個(gè)上界，記作的一個(gè)上界，記作z ;而而(IP)的任意的任意可行解的目標(biāo)函數(shù)值將是可行解的目標(biāo)函數(shù)值將是z*的一個(gè)下界的一個(gè)下界z 。分枝定界。分枝定界法就是將法就是將(LP)的可行域分成

12、子區(qū)域（分枝），逐步的可行域分成子區(qū)域（分枝），逐步減小減小z 和增大和增大z ，最終求得，最終求得z*的方法。的方法。【例【例5-75-7】且為整數(shù)且為整數(shù))2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考慮全整數(shù)規(guī)劃問題：考慮全整數(shù)規(guī)劃問題：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整數(shù)規(guī)劃的松弛問題：整數(shù)規(guī)劃的松弛問題：步驟：步驟： 1、先不考慮整數(shù)約束，解、先不考慮整數(shù)約束，解( IP )的松弛問題的松弛問題( LP )，可能，可能得到以下情況之一：得到以下情況之一： ( LP

13、 )沒有最優(yōu)解，則沒有最優(yōu)解，則( IP )也沒有最優(yōu)解，停止計(jì)算；也沒有最優(yōu)解，停止計(jì)算； 若若( LP )有最優(yōu)解，并符合有最優(yōu)解，并符合( IP )的整數(shù)條件，則的整數(shù)條件，則( LP )的的最優(yōu)解即為最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算；的最優(yōu)解，停止計(jì)算； 若若( LP )有最優(yōu)解，但不符合有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)一步。為討論方便，設(shè)( LP )的最優(yōu)解為：的最優(yōu)解為： 不不全全為為整整數(shù)數(shù)其其中中目目標(biāo)標(biāo)函函數(shù)數(shù)最最優(yōu)優(yōu)值值為為), 2 , 1(.Z)0 , 0 ,( (0)21)0(mibbbbbXiTmr 2、定

14、界：、定界： 記記( IP )的目標(biāo)函數(shù)最優(yōu)值為的目標(biāo)函數(shù)最優(yōu)值為Z* ,以以Z(0) 作為作為Z* 的上界，的上界，記為記為 Z(0) 。再用觀察法找到一個(gè)整數(shù)可行解。再用觀察法找到一個(gè)整數(shù)可行解 X，并，并以其相應(yīng)的目標(biāo)函數(shù)值以其相應(yīng)的目標(biāo)函數(shù)值 Z作為作為Z* 的下界，記為的下界，記為Z Z（?。ㄈj = 0），則有：），則有： Z Z* 。ZZ將這兩個(gè)約束條件分別加入問題將這兩個(gè)約束條件分別加入問題(IP) ，形成兩個(gè)子問題，形成兩個(gè)子問題(IP1)和和(IP2) ，再解這兩個(gè)問題的松弛問題，再解這兩個(gè)問題的松弛問題(LP1)和和(LP2) 。 3、分枝：分枝： 在在( LP )的最

15、優(yōu)解的最優(yōu)解X(0)中，任選一個(gè)不符合整數(shù)條件的中，任選一個(gè)不符合整數(shù)條件的變量，例如變量，例如xr= （不為整數(shù)），以（不為整數(shù)），以 表示不超過表示不超過 的的最大整數(shù)。構(gòu)造兩個(gè)約束條件最大整數(shù)。構(gòu)造兩個(gè)約束條件 xr 和和xr 1 1rbrbrbrbrb 4、修改上、下界：修改上、下界：( (按照以下兩點(diǎn)規(guī)則進(jìn)行按照以下兩點(diǎn)規(guī)則進(jìn)行) ) 在各分枝問題中，找出目標(biāo)函數(shù)值最大者作為新在各分枝問題中，找出目標(biāo)函數(shù)值最大者作為新的上界；的上界； 從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。大者作為新的下界。 5、比較與剪枝比較與剪枝 ：

16、 各分枝的目標(biāo)函數(shù)值中，若有小于各分枝的目標(biāo)函數(shù)值中，若有小于Z 者，則剪掉此枝，者，則剪掉此枝，表明此子問題已經(jīng)探清，不必再分枝了表明此子問題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝否則繼續(xù)分枝 。 如此反復(fù)進(jìn)行，直到得到如此反復(fù)進(jìn)行，直到得到ZZ* 為止，即得最優(yōu)解為止，即得最優(yōu)解 X* Z3200CB XB b x1x2x3x40 x3921109/20 x414230114/232003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/200-5/4-1/4解解:用單純形法解對(duì)應(yīng)的用單純形法解對(duì)應(yīng)的(LP)問題問題,如表所示如表所示,獲得最優(yōu)

17、解獲得最優(yōu)解初始表初始表最終表最終表可見，最優(yōu)解為可見，最優(yōu)解為x1=3.25 x2=2.5 z(0) =59/4=14.75且且為為整整數(shù)數(shù)0,143292)(23max21212121xxxxxxIPxxZ例例1、用分枝定界法求解整數(shù)規(guī)劃問題、用分枝定界法求解整數(shù)規(guī)劃問題選選 x2 進(jìn)行分枝，即增加兩個(gè)約束進(jìn)行分枝，即增加兩個(gè)約束x22 和和x2 3 ，則，則且且為為整整數(shù)數(shù)0,2 14329 2) 1(23max212212121xxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,3 14329 2)2(23max212212121xxxxxxxIPxxZ 分別在分別在(LP1)和和(LP2)中

18、引入松弛變量中引入松弛變量x5和和x6 ，將新加，將新加約束條件加入上表計(jì)算，即約束條件加入上表計(jì)算，即 x2+ x5= 2 , x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x520100100-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/2100-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5繼續(xù)分枝

19、，繼續(xù)分枝，加入約束加入約束 x1 3, x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) z(3),故故x1=4, x2=1為最優(yōu)解為最優(yōu)

20、解 LP4樹形圖如下：樹形圖如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14例例2、用分枝定界法求解整數(shù)規(guī)劃問題、用分枝定界法求解整數(shù)規(guī)劃問題（圖解法計(jì)算）（圖解法計(jì)算）且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題0

21、,4 30 652 5min211212121xxxxxxxxxZ記為（記為（LP）用圖解法求用圖解法求（LP）的最優(yōu)的最優(yōu)解，如圖所示解，如圖所示x1x233(18/11,40/11)對(duì)于對(duì)于x118/111.64， 取值取值x1 1， x1 2對(duì)于對(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）最小值的下限最小值的下限有下式：有下式：且且為為整整數(shù)數(shù)0,1 4 30 652 )1(5min

22、2111212121xxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 現(xiàn)在只要求出（現(xiàn)在只要求出（LP1）和（）和（LP2）的最優(yōu)解即可）的最優(yōu)解即可同理求同理求（LP2） ,如圖所示如圖所示在在C 點(diǎn)取得最優(yōu)解點(diǎn)取得最優(yōu)解即即x12, x2 =10/3, Z(2) 56/318.7 Z(2) Z(0) 原問題目標(biāo)函數(shù)值的下界為原問題目標(biāo)函數(shù)值的下界為-18.7-18.7x2 不是整數(shù)，故利用不是整數(shù)，故利用3 10/34 加入條件加入條件x1x233(18/11,40/11) 先求先求（LP1）, ,如圖所示。此

23、如圖所示。此時(shí)，在時(shí)，在B 點(diǎn)取得最優(yōu)解點(diǎn)取得最優(yōu)解x11, x2 =3, Z(1)16找到整數(shù)解，問題已探明，找到整數(shù)解，問題已探明，此枝停止計(jì)算。且由此可知此枝停止計(jì)算。且由此可知目標(biāo)函數(shù)最優(yōu)值的上界為目標(biāo)函數(shù)最優(yōu)值的上界為-1611BAC加入條件：加入條件： x23, x24 有下式：有下式：且且為為整整數(shù)數(shù)0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最優(yōu)解即可）的最優(yōu)解即可x1x2

24、33(18/11,40/11)11BAC先求先求（LP3）, ,如圖所示。此時(shí)如圖所示。此時(shí)D 在點(diǎn)取得最優(yōu)解在點(diǎn)取得最優(yōu)解即即 x112/5=2.4, x2 =3, Z(3)-87/5=-17.4-18.7但但x112/5不是整數(shù)，可繼續(xù)不是整數(shù)，可繼續(xù)分枝。即分枝。即 3x12D求求（LP4），），如圖所示如圖所示無可行解，不再分枝無可行解，不再分枝 在在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件）的基礎(chǔ)上繼續(xù)分枝。加入條件3x12有下式：有下式：且且為為整整數(shù)數(shù)0,2 3 2 4 30 652 )5(5min211211212121xxxxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,3 3 2

25、4 30 652 )6(5min211211212121xxxxxxxxxxIPxxZ只要求出（只要求出（LP5）和（）和（LP6）的最優(yōu)解即可）的最優(yōu)解即可x1x233(18/11,40/11)11BACD先求先求（LP5）, ,如圖所示。此時(shí)如圖所示。此時(shí)E 在點(diǎn)取得最優(yōu)解在點(diǎn)取得最優(yōu)解即即 x12, x2 =3, Z(5)17找到整數(shù)解，問題已探明，此找到整數(shù)解，問題已探明，此枝停止計(jì)算。枝停止計(jì)算。E求求（LP6），），如圖所示。此時(shí)如圖所示。此時(shí) F在點(diǎn)取得最優(yōu)解在點(diǎn)取得最優(yōu)解x13, x2 =2.5, Z(6)31/2=15.5 Z(5) F 如對(duì)如對(duì)Z(6) 繼續(xù)分解，其最小值也

26、不會(huì)低于繼續(xù)分解，其最小值也不會(huì)低于15.5，問題探明，問題探明, ,剪枝剪枝至此，原問題至此，原問題( (IP) )的最優(yōu)解為：的最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) 17以上的求解過程可以上的求解過程可以用一個(gè)樹形圖表以用一個(gè)樹形圖表示如右：示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4無可無可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23

27、x24x12x13 且全為整數(shù)且全為整數(shù)0,13651914max21212121xxxxxxxxZ練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題 LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP3x1=33/14, x2=2Z(3) 61/14LP4無可無可行解行解x22x23LP5x1=2, x2=2Z(7) 4LP6x1=3, x2=1Z(8) 4x12x13一、計(jì)算步驟一、計(jì)算步驟 1、用單純形法求解、用單純形法求解( IP )對(duì)應(yīng)的松弛問題對(duì)應(yīng)的

28、松弛問題( LP ) 若若( LP )沒有最優(yōu)解，則沒有最優(yōu)解，則( IP )也沒有最優(yōu)解，也沒有最優(yōu)解，停止計(jì)算；停止計(jì)算； 若若( LP )有最優(yōu)解，并符合有最優(yōu)解，并符合( IP )的整數(shù)條件，的整數(shù)條件，則則( LP )的最優(yōu)解即為的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算；的最優(yōu)解，停止計(jì)算； 若若( LP )有最優(yōu)解，但不符合有最優(yōu)解，但不符合( IP )的整數(shù)條件，的整數(shù)條件，轉(zhuǎn)入下一步。轉(zhuǎn)入下一步。第三節(jié)第三節(jié) 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法 割平面法割平面法 2 2、從、從( (LP) )的最優(yōu)解中，任選不為整數(shù)的分量的最優(yōu)解中，任選不為整數(shù)的分量xi ,將最將最優(yōu)單純形表中該

29、行的系數(shù)優(yōu)單純形表中該行的系數(shù) 和和 分解為整數(shù)部分和小分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，作割平面方程數(shù)部分之和，并以該行為源行，作割平面方程ikaib由最終單純形表可以得到：由最終單純形表可以得到： ikikibxaxikaib將將 和和分成整數(shù)部分和非負(fù)真分?jǐn)?shù)之和，即分成整數(shù)部分和非負(fù)真分?jǐn)?shù)之和，即iiifNb10iiifbN的整數(shù)部分，為ikikikfNa10ikikikfaN的整數(shù)部分，為代入上式得：代入上式得：kkikkiikikixffNxNx 因變量為整數(shù)，即上式左邊必須是整數(shù)，由右邊看，因?yàn)橐蜃兞繛檎麛?shù)，即上式左邊必須是整數(shù)，由右邊看，因?yàn)?0fi 11，所以不能為

30、正，即，所以不能為正，即 0kkikixff割平面方程割平面方程 3 3、將由割平面方程得到的約束條件作為一個(gè)新、將由割平面方程得到的約束條件作為一個(gè)新的約束條件置于最優(yōu)單純形表中，用對(duì)偶單純形法的約束條件置于最優(yōu)單純形表中，用對(duì)偶單純形法求出新的最優(yōu)解，返回求出新的最優(yōu)解，返回1 1。例例1 、用割平面法求解整數(shù)規(guī)劃問題、用割平面法求解整數(shù)規(guī)劃問題且為整數(shù), 0,14329223max21212121xxxxxxxxZ2123maxxxz0,1432924321421321xxxxxxxxxx 解：增加松弛變量解：增加松弛變量x3和和x4 ，得到，得到(LP)的初始單純形表的初始單純形表和最

31、優(yōu)單純形表和最優(yōu)單純形表：Cj3200CBXBbx1x2x3x40 x31423100 x492101Z00100Cj3200CBXBbx1x2x3x42x25/2011/2-1/23x113/410-1/41/4Z-3/200-1/4-5/4 此題的最優(yōu)解為：此題的最優(yōu)解為：X =(13/4 ,5/2) 。但不是整數(shù)最優(yōu)解，但不是整數(shù)最優(yōu)解，引入割平面?？梢允褂玫母钇矫娴臈l件有引入割平面。可以使用的割平面的條件有: 252121432xxx4134141431xxx41414343xx21212143xx252121432xxx21221214432xxxx43422121212xxxx41

32、34141431xxx41341434331xxxx43314143413xxxx 為加快割平面的速度，一般選擇較大的為加快割平面的速度，一般選擇較大的 fi 作為割平面作為割平面方程進(jìn)行計(jì)算方程進(jìn)行計(jì)算現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中212121543xxx21212143xx21212143xxCj32000CBXBbx1x2x3x4x52x25/2011/2-1/203x113/410-1/43/400 x5-1/200-1/2-1/2100-1/4-5/402x22010-113x17/21001-1/20 x310011-2

33、000-1-1/221215x割平面方程為割平面方程為: :Cj320000CBXBbx1x2x3x4x5x62x22010-1103x17/21001-1/200 x310011-200 x6-1/20000-1/21000-1-1/202x21010-1023x1410010-10 x3300110-40 x5100001-2000-10-1且均為整數(shù)0,521023max2122121xxxxxxxz【例【例5-75-7】求解整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題且為整數(shù)0,205462max21212121xxxxxxxxz【練習(xí)【練習(xí)】求解整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題 01整數(shù)規(guī)劃是一種特殊形

34、式的整數(shù)規(guī)劃，整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量這時(shí)的決策變量xi 只取兩個(gè)值只取兩個(gè)值0或或1，一般的解法為，一般的解法為隱枚舉法隱枚舉法【例【例5-11】求解下列】求解下列01規(guī)劃問題規(guī)劃問題 10,(4) 64 (3) 3 (2) 44(1) 22523max3213221321321321或或xxxxxxxxxxxxxxxxZ第四節(jié)第四節(jié) 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃x1 , x2 , x3約束條件約束條件滿足條件滿足條件Z 值值 (1) (2) (3) (4)是是 否否( 0, 0, 0 ) 0 0 0 00( 0, 0, 1 ) 1 1 0 15( 0, 1, 0 ) 2

35、4 1 42( 1, 0, 0 ) 1 1 1 03( 0, 1, 1 ) 1 5( 1, 0, 1 ) 0 2 1 18( 1, 1, 0 ) 3( 1, 1, 1 ) 2 6由上表可知，問題的最優(yōu)解為由上表可知，問題的最優(yōu)解為 X*=( x1=1， x2=0， x3=1 )解：對(duì)于解：對(duì)于01規(guī)劃問題，由于每個(gè)變量只取規(guī)劃問題，由于每個(gè)變量只取0、1兩個(gè)值，一兩個(gè)值，一般會(huì)用窮舉法來求解，即將所有的般會(huì)用窮舉法來求解，即將所有的0、1組合找出，使目標(biāo)函組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。數(shù)達(dá)到極值要求就可求得最優(yōu)解。 由上表可知：由上表可知： x1 =0，x2=0，x3=1是一

36、個(gè)可行解，為盡快找是一個(gè)可行解，為盡快找到最優(yōu)解，可將到最優(yōu)解，可將3x12x25x35作為一個(gè)約束，凡是目標(biāo)函作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于數(shù)值小于5的組合不必討論，如下表。的組合不必討論，如下表。x1 , x2 , x3約束條件約束條件滿足條件滿足條件Z 值值(0) (1) (2) (3) (4)是是 否否( 0, 0, 0 ) 0 0 0 0 00( 0, 0, 1 ) 5 1 1 0 15( 0, 1, 0 )-2( 0, 1, 1 ) 3( 1, 0, 0 ) 3( 1, 0, 1 ) 8 0 2 1 18( 1, 1, 0 ) 1( 1, 1, 1 ) 4問題的最優(yōu)解為問題的最優(yōu)

37、解為 X*=( x1 =1，x2=0，x3=1 )隱枚舉法如果重新排列變量的順序可使問題更快地求得最優(yōu)解，如：如果重新排列變量的順序可使問題更快地求得最優(yōu)解，如：令令x2=1-x2(0 x21)，將目標(biāo)函數(shù)中變量前的系數(shù)均化為正數(shù)，將目標(biāo)函數(shù)中變量前的系數(shù)均化為正數(shù)，則目標(biāo)函數(shù)變?yōu)閯t目標(biāo)函數(shù)變?yōu)?2355)1(23213321xxxxxxzmax尋找最優(yōu)目標(biāo)函數(shù)值尋找最優(yōu)目標(biāo)函數(shù)值x1 ， x2， x3約束條件約束條件滿足條件滿足條件Z 值值(0) (1) (2) (3) (4)是是 否否( 1, 1, 1 ) 8 0 0 0 08問題的最優(yōu)解為問題的最優(yōu)解為 X*=( x1=1，x2=0，x

38、3=1 ) 【例】求解下列【例】求解下列01規(guī)劃問題規(guī)劃問題4 , 3 , 2 , 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解：令解：令 x11x1, x2=1- x2, x4=1- x4，則目標(biāo)函數(shù)變，則目標(biāo)函數(shù)變?yōu)闉?173)1 ()1 (7)1 ( 3max43214321xxxxxxxxZ此時(shí)，此時(shí)，x*=(1, 0, 1, 0)，z*=-2練習(xí)：求解下列練習(xí)：求解下列01規(guī)劃問題規(guī)劃問題)5 , 4 , 3 , 2 , 1( 1054 24423 248510min543215432154321jxxxxxx

39、xxxxxxxxxxZj或所以，所以， 原問題的最優(yōu)解為：原問題的最優(yōu)解為： X*(0, 0, 1, 0, 0)，Z*=8第五節(jié)第五節(jié) 指派問題指派問題 在實(shí)際中經(jīng)常會(huì)遇到這樣的問題，有在實(shí)際中經(jīng)常會(huì)遇到這樣的問題，有n 項(xiàng)不同的任項(xiàng)不同的任務(wù)，務(wù)，需要需要n 個(gè)人分別完成其中的一項(xiàng)個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問題，指派哪個(gè)人去完成哪項(xiàng)任務(wù)，可使完成了一個(gè)問題，指派哪個(gè)人去完成哪項(xiàng)任務(wù)

40、，可使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少）？這類問項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少）？這類問題稱為題稱為指派問題指派問題或或分配問題分配問題。 每一項(xiàng)工作只能分配給一個(gè)人；每一項(xiàng)工作只能分配給一個(gè)人； 每一個(gè)人只能并且必須接受一項(xiàng)工作每一個(gè)人只能并且必須接受一項(xiàng)工作 一、指派問題的一般提法一、指派問題的一般提法【5-135-13】某工廠要生產(chǎn)四種產(chǎn)品，該工廠有四個(gè)車間都可以生】某工廠要生產(chǎn)四種產(chǎn)品，該工廠有四個(gè)車間都可以生產(chǎn)這四種產(chǎn)品。但由于設(shè)備情況與技術(shù)情況不同，所以生產(chǎn)成產(chǎn)這四種產(chǎn)品。但由于設(shè)備情況與技術(shù)情況不同，所以生產(chǎn)成本不同，其單位產(chǎn)品的生產(chǎn)成本如表所示。問應(yīng)當(dāng)如何分配這

41、本不同，其單位產(chǎn)品的生產(chǎn)成本如表所示。問應(yīng)當(dāng)如何分配這四種產(chǎn)品到各車間，才能使總的生產(chǎn)成本最??？試建立該問題四種產(chǎn)品到各車間，才能使總的生產(chǎn)成本最??？試建立該問題的數(shù)學(xué)模型。的數(shù)學(xué)模型。 產(chǎn)品產(chǎn)品車間車間1234145410251453332643446解解 引入引入0-10-1變量變量xij ( (i, j1,2,3,4,5)1,2,3,4,5)，令：令： 時(shí)生產(chǎn)產(chǎn)品，當(dāng)不指派車間時(shí)生產(chǎn)產(chǎn)品，當(dāng)指派車間jijixij01這個(gè)問題的約束條件如下：這個(gè)問題的約束條件如下：(1)(1)一個(gè)車間只生產(chǎn)一種產(chǎn)品，即一個(gè)車間只生產(chǎn)一種產(chǎn)品，即1111444342413433323124232221141

42、31211xxxxxxxxxxxxxxxx141jijx簡寫為：簡寫為： （i=1,2,3,4） (2)(2)一種產(chǎn)品只由一個(gè)車間生產(chǎn)，即一種產(chǎn)品只由一個(gè)車間生產(chǎn)，即 111144342414433323134232221241312111xxxxxxxxxxxxxxxx簡寫為：簡寫為：141iijx（ j =1,2,3,4） (3)(3)變量工變量工xij 必須等于必須等于0 0或或1 1，即，即xij =0=0或或1 1。 目標(biāo)函數(shù)為：目標(biāo)函數(shù)為：Min 443412116454xxxxz設(shè)決策變量設(shè)決策變量 1 分配第分配第i 個(gè)人去做第個(gè)人去做第j 件工作件工作 xij = 0 相反相

43、反 ( i , j =1.2. n )其數(shù)學(xué)模型為： 設(shè)設(shè)n個(gè)人被分配去做個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作件工作，規(guī)定每個(gè)人只做一件工作,每每件工作只有一個(gè)人去做。已知第件工作只有一個(gè)人去做。已知第i個(gè)人去做第個(gè)人去做第j件工作的的效件工作的的效率（率（ 時(shí)間或費(fèi)用）為時(shí)間或費(fèi)用）為cij (i =1, 2, , n; j =1, 2, , n)并假設(shè)并假設(shè)cij 0。問應(yīng)如何分配才能使總效率（。問應(yīng)如何分配才能使總效率（ 時(shí)間或費(fèi)用）最高？時(shí)間或費(fèi)用）最高？ninjijijxcz11min), 2 , 1,( 10), 2 , 1( 1), 2 , 1( 111njixnjxn

44、ixijniijnjij或效率矩陣（成本矩陣）效率矩陣（成本矩陣）:(:(cij ) )nn 二、匈牙利法二、匈牙利法 分配問題是分配問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，但這些方法卻規(guī)劃或運(yùn)輸問題的解法去求解，但這些方法卻沒有充分利用指派問題的特點(diǎn)。沒有充分利用指派問題的特點(diǎn)。 庫恩庫恩( (W.W.Kuhn) )于于19551955年提出了指派問題的解法，他引用了年提出了指派問題的解法，他引用了匈牙利數(shù)學(xué)家康尼格匈牙利數(shù)學(xué)家康尼格( (D.Konig) )的關(guān)于矩陣中獨(dú)立零元素的定理

45、：的關(guān)于矩陣中獨(dú)立零元素的定理：系數(shù)矩陣中獨(dú)立系數(shù)矩陣中獨(dú)立0 0元素的最多個(gè)數(shù)等于能覆蓋所有零元元素的最多個(gè)數(shù)等于能覆蓋所有零元素的最小直線數(shù)，習(xí)慣上稱之為匈牙利解法。素的最小直線數(shù)，習(xí)慣上稱之為匈牙利解法。 分配問題最優(yōu)解的以下性質(zhì)：分配問題最優(yōu)解的以下性質(zhì)：若從系數(shù)矩陣若從系數(shù)矩陣(cij )的某行的某行( (或某列或某列) )各元素分別減去該行（列）的最小元素，得各元素分別減去該行（列）的最小元素，得到新矩陣到新矩陣(cij),那么以那么以(cij)為系數(shù)矩陣求得的最優(yōu)解和為系數(shù)矩陣求得的最優(yōu)解和利用原系數(shù)矩陣求得的最優(yōu)解相同。利用原系數(shù)矩陣求得的最優(yōu)解相同。 證明證明), 2 , 1

46、;, 3 , 2();, 2 , 1(11njniccnjkccijijjj設(shè)成本矩陣第一行各元素均減去同一個(gè)數(shù)設(shè)成本矩陣第一行各元素均減去同一個(gè)數(shù)k，得到的新矩，得到的新矩陣記為陣記為( (cij ) )kzkxcxcxkxcxcxkcxczninjijijninjijijnjjnjjjninjijijnjjjninjijij1121111112111111)( 第一步：變換成本矩陣，使每行每列中至少出現(xiàn)一第一步：變換成本矩陣，使每行每列中至少出現(xiàn)一個(gè)個(gè)0元素元素 (1) 令令(cij) nn的每行元素都減去該行的最小元素；的每行元素都減去該行的最小元素； (2) 再從所得新系數(shù)矩陣的每列元

47、素中減去該列的再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。最小元素。644362335415104543110401143046010321401101011130430103匈牙利法的步驟（以（以 例例5-135-13為例）為例） 第二步：試求最優(yōu)解第二步：試求最優(yōu)解 在新矩陣中找盡可能多的獨(dú)立在新矩陣中找盡可能多的獨(dú)立0元素，若能找出元素，若能找出n個(gè)個(gè)獨(dú)立獨(dú)立0元素，就以這元素，就以這n個(gè)獨(dú)立個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣元素對(duì)應(yīng)解矩陣(xij)中的元中的元素為素為1，其余為，其余為0，這就得到最優(yōu)解。找獨(dú)立，這就得到最優(yōu)解。找獨(dú)立0元素，常元素，常用的步驟為：用的步驟為： (1) 從只有

48、一個(gè)從只有一個(gè)0元素的行元素的行(列列)開始，給這個(gè)開始，給這個(gè)0元素加元素加，記作，記作 。然后劃去。然后劃去 所在列所在列(行行)的其它的其它0元素，記作元素，記作 ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了； (2) 給只有一個(gè)給只有一個(gè)0元素的列元素的列(行行)中的中的0元素加元素加，記，記作作 ；然后劃去；然后劃去 所在行的所在行的0元素，記作元素，記作 ； (3) 反復(fù)進(jìn)行反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的兩步，直到盡可能多的0元素都元素都被圈出和劃掉為止；被圈出和劃掉為止；00000001101011130430101000010000100001 (4) (4) 若仍有沒有劃若仍有沒有劃的的0 0元素，且同行元素，且同行( (列列) )的的0 0元素元素至少有兩個(gè)，則從剩有至少有兩個(gè)，則從剩有0 0元素最少的行元素最少的行( (列列) )開始，比較開始，比較這行各這行各0 0元素所在列中元素所在列中0 0元素的數(shù)目，選擇元素的數(shù)目，選擇0 0元素少的那元素少的那列的這個(gè)列的這個(gè)0 0元素加元素加( (表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇選擇性少的性少的) )，然后劃掉同行同列的其它，然后劃掉同