運籌(第四章整數(shù)規(guī)劃)

1、2022-6-291運籌學(xué)運籌學(xué)OPERATIONS RESEARCH2022-6-292第四章第四章 整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃與分配問題n整數(shù)規(guī)劃的有關(guān)概念及特點整數(shù)規(guī)劃的有關(guān)概念及特點 n整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用n指派問題及匈牙利解法指派問題及匈牙利解法 n整數(shù)規(guī)劃的求解方法：分枝定界法、割平面法整數(shù)規(guī)劃的求解方法：分枝定界法、割平面法 2022-6-293純整數(shù)規(guī)劃：純整數(shù)規(guī)劃：在整數(shù)規(guī)劃中，如果所有的變量都為在整數(shù)規(guī)劃中，如果所有的變量都為非負整數(shù)，則稱為純整數(shù)規(guī)劃問題；非負整數(shù)，則稱為純整數(shù)規(guī)劃問題；混合整數(shù)規(guī)劃：混合整數(shù)規(guī)劃：如果有一部分變量為非負整數(shù)，則如果有一部分變量為非

2、負整數(shù)，則稱之為混合整數(shù)規(guī)劃問題。稱之為混合整數(shù)規(guī)劃問題。0-10-1變量：變量：在整數(shù)規(guī)劃中，如果變量的取值只限于在整數(shù)規(guī)劃中，如果變量的取值只限于0 0和和1 1，這樣的變量我們稱之為，這樣的變量我們稱之為0-10-1變量。變量。0-10-1規(guī)劃：規(guī)劃：在整數(shù)規(guī)劃問題中，如果所有的變量都在整數(shù)規(guī)劃問題中，如果所有的變量都為為0-10-1變量，則稱之為變量，則稱之為0-10-1規(guī)劃。規(guī)劃。1 1 整數(shù)規(guī)劃的有關(guān)概念及特點整數(shù)規(guī)劃的有關(guān)概念及特點1 1.1 .1 概念概念整數(shù)規(guī)劃：整數(shù)規(guī)劃： 要求決策變量取整數(shù)值的規(guī)劃問題。要求決策變量取整數(shù)值的規(guī)劃問題。 （線性整數(shù)規(guī)劃、非線性整數(shù)規(guī)劃等）（

3、線性整數(shù)規(guī)劃、非線性整數(shù)規(guī)劃等）2022-6-294求整數(shù)解的線性規(guī)劃問題，不是用求整數(shù)解的線性規(guī)劃問題，不是用四舍五入四舍五入法或法或去尾法去尾法對性規(guī)劃的非整數(shù)解加以處理就能解決的，對性規(guī)劃的非整數(shù)解加以處理就能解決的，用用枚舉法枚舉法又往往會計算量太大，所以要用整數(shù)規(guī)又往往會計算量太大，所以要用整數(shù)規(guī)劃的特定方法加以解決。劃的特定方法加以解決。例：例： 求解下列整數(shù)規(guī)劃：求解下列整數(shù)規(guī)劃：1 1.2 .2 整數(shù)規(guī)劃的求解特點整數(shù)規(guī)劃的求解特點并取整數(shù)并取整數(shù), 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz2022-6-2951x2x143221 xx

4、5 . 45 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若當(dāng)作一般線性規(guī)劃求若當(dāng)作一般線性規(guī)劃求解，圖解法的結(jié)果如下。解，圖解法的結(jié)果如下。1、非整數(shù)規(guī)劃、非整數(shù)規(guī)劃最優(yōu)解最優(yōu)解 顯然不是整數(shù)規(guī)劃的可行解。顯然不是整數(shù)規(guī)劃的可行解。2、四舍五入后的結(jié)果四舍五入后的結(jié)果 也不是整數(shù)規(guī)劃的可行解。也不是整數(shù)規(guī)劃的可行解。)5 . 2,25. 3()3, 3(3、可行解是陰影區(qū)可行解是陰影區(qū)域交叉點，可比較這域交叉點，可比較這些點對應(yīng)的函數(shù)值，些點對應(yīng)的函數(shù)值，找出最優(yōu)。找出最優(yōu)。) 1, 4(2022-6-2962 2 應(yīng)用舉例應(yīng)用舉例2 2.1.1 邏輯變量在數(shù)學(xué)模型中

5、的應(yīng)用邏輯變量在數(shù)學(xué)模型中的應(yīng)用1 1、m m個約束條件中只有個約束條件中只有k k個起作用個起作用設(shè)有設(shè)有m m個約束條件個約束條件mibxanjiijij,.,2 , 1,1定義定義0-10-1整型變量：整型變量：，10iy第第i i個約束起作用個約束起作用第第i i個約束不起作用個約束不起作用2022-6-297設(shè)設(shè)M M是任意大正數(shù)，則原約束中只有是任意大正數(shù)，則原約束中只有k k個真正個真正起作用的情況可表示為：起作用的情況可表示為：kmyyymiMybxamnjiiijij.,.,2 , 1,2112022-6-2982 2、約束條件右端項是、約束條件右端項是r r個可能值中的一個

6、個可能值中的一個rnjijijbbbxa或或或或,.,211則通過定義則通過定義，10iy約束條件右端項不是約束條件右端項不是b bi i約束條件右端項是約束條件右端項是b bi i可將上述條件表示為可將上述條件表示為 1.,2111rnjriiiijijyyyybxa2022-6-2993 3、兩組條件中滿足其中一組、兩組條件中滿足其中一組例如表示條件：若例如表示條件：若 ，則，則 ； 否則否則 時時則通過定義則通過定義10iy第第i i組條件起作用，組條件起作用，i=1i=1，2 2第第i i組條件不起作用組條件不起作用可將上述條件表示為可將上述條件表示為 41x, 32x, 41x, 1

7、2x其中：其中：M M是任意大正數(shù)是任意大正數(shù)134142122211211yyMyxMyxMyxMyx2022-6-2910定義定義4 4、表示含有固定費用的函數(shù)、表示含有固定費用的函數(shù)例如：例如： 表示產(chǎn)品表示產(chǎn)品 的生產(chǎn)數(shù)量，其生產(chǎn)費用函數(shù)的生產(chǎn)數(shù)量，其生產(chǎn)費用函數(shù)為：為： jx目標(biāo)函數(shù)：目標(biāo)函數(shù)：00, 0,)(jjjjjjjxxxcKxC其中其中 是與產(chǎn)量無關(guān)是與產(chǎn)量無關(guān)的生產(chǎn)準(zhǔn)備費用的生產(chǎn)準(zhǔn)備費用 jKnjjjxCz1)(min10jy0jx0jx則原問題可表示為則原問題可表示為)(min1njjjjjyKxcz100.或jjjyMyxtsj2022-6-29112 2.2.2 應(yīng)

8、用舉例應(yīng)用舉例例例1 1 東方大學(xué)計算機實驗室聘用東方大學(xué)計算機實驗室聘用4 4名大學(xué)生（代號名大學(xué)生（代號1,2,3,41,2,3,4）和）和2 2名研究生（代號名研究生（代號5,65,6）值班。已知各學(xué)生從）值班。已知各學(xué)生從周一至周五每天可安排的值班時間及每人每小時報酬見下周一至周五每天可安排的值班時間及每人每小時報酬見下表所示。表所示。學(xué)生學(xué)生代號代號酬金酬金(元元/h)每天可安排的值班時間每天可安排的值班時間(h)周一周一周二周二周三周三周四周四周五周五110.060607210.00606339.94830549.855640510.830460611.3062442022-6-2

9、912實驗室每天開放時間為實驗室每天開放時間為8:00AM10:00PM,8:00AM10:00PM,共共1414小時。開放小時。開放時間內(nèi)需要有一名學(xué)生值班。規(guī)定大學(xué)生每周值班時間是時間內(nèi)需要有一名學(xué)生值班。規(guī)定大學(xué)生每周值班時間是815815小時，研究生是小時，研究生是712712小時，每次值班不小于小時，每次值班不小于2 2小時。小時。又每名學(xué)生每周值班次數(shù)不得多于三次，每天值班人員中又每名學(xué)生每周值班次數(shù)不得多于三次，每天值班人員中至少有一名研究生，每天值班人數(shù)不超過至少有一名研究生，每天值班人數(shù)不超過3 3人。試為該實人。試為該實驗室安排一張人員值班表，使得總酬金支出為最少。驗室安排

10、一張人員值班表，使得總酬金支出為最少。解：解：設(shè)設(shè) 表示學(xué)生表示學(xué)生i i在周在周j j的值班時間。的值班時間。ijx, 1, 0ijy學(xué)生學(xué)生i i在周在周j j不值班不值班學(xué)生學(xué)生i i在周在周j j值班值班 表示學(xué)生表示學(xué)生i i在周在周j j的最多可值班時間。的最多可值班時間。則則目標(biāo)函數(shù)目標(biāo)函數(shù)：ija61i51jijixczmin2022-6-29136 , 5,127)3(51ixjij研究生值班研究生值班7-127-12小時小時6,.,1, 3)4(51iyjij每周不超過每周不超過3 3次次5,.,1, 3)5(61jyiij每天不超過每天不超過3 3人人5,.,11)6(6

11、5jyyjj每天有一研究生每天有一研究生5,.,1, 6,.12)7(jiyaxyijijijij值班不超過每人可安排的時間值班不超過每人可安排的時間5,.1,14) 1 (61jxiij每天開放每天開放1414小時小時4,.1,158)2(51ixjij大學(xué)生值班大學(xué)生值班8-158-15小時小時約約束束條條件件2022-6-2914例例2 2 紅星日用化工廠為發(fā)運產(chǎn)品，下一年度需要紅星日用化工廠為發(fā)運產(chǎn)品，下一年度需要6 6種不同容積的包裝箱，每種包裝箱的需求量及生產(chǎn)種不同容積的包裝箱，每種包裝箱的需求量及生產(chǎn)一個的可變費用如下表所示。一個的可變費用如下表所示。包裝箱代號包裝箱代號1234

12、56容積（容積（m3）0.080.100.120.150.200.25需求量（個）需求量（個）500550700900450400可變費用（元可變費用（元/個）個）5.08.010.012.116.318.2由于生產(chǎn)不同容積包裝箱時需進行專門的準(zhǔn)備、下由于生產(chǎn)不同容積包裝箱時需進行專門的準(zhǔn)備、下料等，生產(chǎn)每一種包裝箱的固定費用都是料等，生產(chǎn)每一種包裝箱的固定費用都是12001200元。元。又若某容積的包裝箱數(shù)量不夠時，可用比它大的代又若某容積的包裝箱數(shù)量不夠時，可用比它大的代替。試問該廠應(yīng)訂做哪幾種代號的包裝箱各多少個，替。試問該廠應(yīng)訂做哪幾種代號的包裝箱各多少個，可使得費用最??？可使得費用最

13、省？2022-6-2915解：解：設(shè)設(shè) 表示代號為表示代號為j j的包裝箱的訂做數(shù)量的包裝箱的訂做數(shù)量。jx，10jy不訂不訂j j包裝箱包裝箱訂訂j j包裝箱包裝箱目標(biāo)函數(shù)目標(biāo)函數(shù)654326112 .183 .161 .1210851200minxxxxxxyzjj約束條件約束條件6,.1,jMyxjj2022-6-291685065 xx1750654xxx24506543xxxx300065432xxxxx3500654321xxxxxx4006x6,.1, 0jxj2022-6-2917例例3 3（固定成本問題）（固定成本問題）高壓容器公司制造小、中、大三種尺寸的金屬容器，高壓容器公

14、司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。每種容器售容器所需的各種資源的數(shù)量如表所示。每種容器售出一只所得的利潤分別為出一只所得的利潤分別為 4 4萬元、萬元、5 5萬元、萬元、6 6萬元，萬元，可使用的金屬板有可使用的金屬板有500500噸，勞動力有噸，勞動力有300300人人/ /月，機月，機器有器有100100臺臺/ /月，此外不管每種容器制造的數(shù)量是多月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是少，都要支付一筆固定的費用：小號是l00l00萬元，萬

15、元，中號為中號為 150 150 萬元，大號為萬元，大號為200200萬元?，F(xiàn)在要制定一萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。個生產(chǎn)計劃，使獲得的利潤為最大。 2022-6-2918解解：設(shè)設(shè) 分別為小號容器、中號容器和大號容分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。器的生產(chǎn)數(shù)量。 建立如下的數(shù)學(xué)模型：建立如下的數(shù)學(xué)模型：資源資源小號容器小號容器中號容器中號容器大號容器大號容器金屬板（噸）金屬板（噸）248勞動力（人月）勞動力（人月）234機器設(shè)備（臺月）機器設(shè)備（臺月）123321,xxx，10jy不生產(chǎn)不生產(chǎn)j j型號容器型號容器生產(chǎn)生產(chǎn)j j型號容器型號容器2022-6-

16、2919321321200150100654maxyyyxxxZ3 , 2 , 11-0, 010032300432500842321321321jyxMyxxxxxxxxxxjjjj變量，變量，是是2022-6-29203 3 指派問題及匈牙利解法指派問題及匈牙利解法 3 3.1 .1 指派問題與模型指派問題與模型 m m項任務(wù)分配給項任務(wù)分配給m m個人去完成，每人只能完成其中個人去完成，每人只能完成其中一項，每項任務(wù)只能分給一人完成，應(yīng)如何分配一項，每項任務(wù)只能分給一人完成，應(yīng)如何分配使得效率最高？使得效率最高？ a aijij是第是第j j個人完成第個人完成第i i項任務(wù)的效率項任務(wù)的

17、效率( (如如 時間）。時間）。 人人任務(wù)任務(wù)12 m1a11a12a1m2a21a22a2mmam1am2amm2022-6-2921設(shè)設(shè)于是建立模型如下：于是建立模型如下： 否則項任務(wù)個人完成第第01ijxijmimjijijxaz11min1,.mji,1,01,.mj, 11,.mi, 111或ijmiijmjijxxx2022-6-29223 3.1 .1 指派問題的匈牙利解法指派問題的匈牙利解法該指派問題可當(dāng)作運輸問題解決，但匈牙利解法更該指派問題可當(dāng)作運輸問題解決，但匈牙利解法更有效。有效。解法思想：解法思想：效率矩陣的元素效率矩陣的元素 ，若有一組位于，若有一組位于不同行不同列

18、的零元素，則令這些位置的決策變量不同行不同列的零元素，則令這些位置的決策變量取值為取值為1 1，其余均為，其余均為0 0，這顯然就是最優(yōu)解。，這顯然就是最優(yōu)解。0ija2022-6-2923定理定理2 2：若矩陣若矩陣A A的元素可分為的元素可分為“0”0”元和元和“非非0”0”元，元，則覆蓋則覆蓋“0”0”元的最少直線數(shù)等于位于不同行、不元的最少直線數(shù)等于位于不同行、不同列的同列的“0”0”元的最大個數(shù)。元的最大個數(shù)。定理定理1 1：效率矩陣效率矩陣 的每一行元素分別減去（加的每一行元素分別減去（加上）一個常數(shù)上）一個常數(shù) ，每一列元素分別減去（加上），每一列元素分別減去（加上）一個元素一個

19、元素 ，得新效率矩陣，得新效率矩陣 ， ，則則 的最優(yōu)解等價于的最優(yōu)解等價于 的最優(yōu)解。的最優(yōu)解。ijaiujvjiijijvuabijbijaijb2022-6-2924例：例：有一份說明書，要分別譯成英、日、德、俄四種語言，有一份說明書，要分別譯成英、日、德、俄四種語言，交給甲、乙、丙、丁四人去完成，各人的效率不同，如何交給甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任務(wù)，可使總效率最高。分配任務(wù)，可使總效率最高。表中數(shù)據(jù)為完成任務(wù)所需時間（單位：小時）。表中數(shù)據(jù)為完成任務(wù)所需時間（單位：小時）。 人任務(wù)甲乙丙丁英文21097日文154148德文13141611俄文415139202

20、2-6-2925匈牙利解法匈牙利解法步驟：步驟：1 1、在效率矩陣每行減去該行最小元素；、在效率矩陣每行減去該行最小元素；2 2、在效率矩陣每列減去該列最小元素；、在效率矩陣每列減去該列最小元素；411429131541116141381441579102591100532410011578005005411000324501152802022-6-29263 3、尋找獨立、尋找獨立“0”0”元素元素( (不同行不同列）不同行不同列）（1 1）從第一行開始，若該行只有一個）從第一行開始，若該行只有一個“0”0”元素，元素，則對該則對該“0”0”元素打括號（元素打括號（ ）（表示這一行的人只（表

21、示這一行的人只有這一個任務(wù)可指派），有這一個任務(wù)可指派），并劃去該并劃去該“0”0”元素所在元素所在的列的列（表示該項任務(wù)不能再指派給別人）（表示該項任務(wù)不能再指派給別人） ；若該；若該行無行無“0”0”元素或有兩個以上的元素或有兩個以上的“0”0”元素（不含劃元素（不含劃去的去的0 0），則轉(zhuǎn)下一行；），則轉(zhuǎn)下一行；（2 2）從第一列開始，若該列只有一個）從第一列開始，若該列只有一個“0”0”元素，元素，則對該則對該“0”0”元素打括號（元素打括號（ ），并劃去該），并劃去該“0”0”元元素所在的行；若該列無素所在的行；若該列無“0”0”元素或有兩個以上的元素或有兩個以上的“0”0”元素（不

22、含劃去的元素（不含劃去的0 0），則轉(zhuǎn)下一列；），則轉(zhuǎn)下一列；2022-6-2927（0）82511（0）5423（0）001145完成上述步驟后可能出現(xiàn)下列情況：完成上述步驟后可能出現(xiàn)下列情況：）效率矩陣的每一行都有一個打括號的效率矩陣的每一行都有一個打括號的0 0元素，元素，則按照打括號的則按照打括號的0 0元素位置指派任務(wù)，即是最優(yōu)解；元素位置指派任務(wù)，即是最優(yōu)解；2022-6-2928）打括號的打括號的0 0元素個數(shù)小于元素個數(shù)小于m m，但未被劃去的，但未被劃去的0 0元元素之間存在閉回路，則沿此閉回路，每隔一個素之間存在閉回路，則沿此閉回路，每隔一個0 0元元打一括號，然后對打括號

23、的打一括號，然后對打括號的0 0元素所在行或所在列元素所在行或所在列畫直線；畫直線；）矩陣中所有矩陣中所有0 0元素或被打括號，或被劃去，但打元素或被打括號，或被劃去，但打括號的括號的0 0元素個數(shù)元素個數(shù) ，則進入下一步；，則進入下一步；m0000000)0()0(00)0(2022-6-2929（3 3）設(shè)法使每一行都有一個打括號的）設(shè)法使每一行都有一個打括號的“0”0”元素。元素。按按定理定理1 1繼續(xù)對矩陣進行變換：繼續(xù)對矩陣進行變換：）從矩陣未被直線覆蓋的元素中找出最小者從矩陣未被直線覆蓋的元素中找出最小者k k，）對矩陣中無直線覆蓋的行，令對矩陣中無直線覆蓋的行，令 ，有直，有直線

24、覆蓋的列，令線覆蓋的列，令 。其余為。其余為0 0。）對矩陣的每個元素計算對矩陣的每個元素計算 ，得到，得到一個新矩陣，轉(zhuǎn)第三步重復(fù)進行，直至每一行都有一個新矩陣，轉(zhuǎn)第三步重復(fù)進行，直至每一行都有一打括號的一打括號的0 0元素。元素。kuikvjjiijvua2022-6-2930（0）82511（0）5423（0）001145根據(jù)上圖，根據(jù)上圖，k=2k=2，002254110003245011528020223211000542301130803211)0()0(05423)0(113)0(80最優(yōu)解：最優(yōu)解：2811944, 1, 1, 1, 134132241zxxxx2022-6-2

25、931兩點說明：兩點說明：1 1、任務(wù)數(shù)、任務(wù)數(shù) 人數(shù)人數(shù) 時如何處理時如何處理增加虛擬的人或虛擬的任務(wù)增加虛擬的人或虛擬的任務(wù) 2 2、指派問題中目標(biāo)函數(shù)變?yōu)?、指派問題中目標(biāo)函數(shù)變?yōu)镸AXMAX時如何處理時如何處理 。每行每列找最大者，用此最大元素減去相應(yīng)各行各每行每列找最大者，用此最大元素減去相應(yīng)各行各列的元素，得到同解矩陣。列的元素，得到同解矩陣。2022-6-29324 4 分枝定界法分枝定界法 分枝定界法分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問題，又能解決方法，它既能解決純整數(shù)規(guī)劃的問題，又能解決混合整數(shù)規(guī)劃的問題?；旌?/p>

26、整數(shù)規(guī)劃的問題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法編制而成的。界法編制而成的。下面舉例來說明分枝定界法的思想和步驟。下面舉例來說明分枝定界法的思想和步驟。2022-6-29331 1、求解整數(shù)規(guī)劃相應(yīng)的一般線性規(guī)劃問題（即先、求解整數(shù)規(guī)劃相應(yīng)的一般線性規(guī)劃問題（即先去掉整數(shù)約束）。去掉整數(shù)約束）。易知：整數(shù)規(guī)劃的可行域（?。┌诰€性規(guī)劃的易知：整數(shù)規(guī)劃的可行域（小）包含于線性規(guī)劃的可行域可行域 ( (大）。大）。 若線性規(guī)劃的最優(yōu)解恰是整數(shù)解，則其就是整若線性規(guī)劃的最優(yōu)解恰是整數(shù)解，則其就是整數(shù)規(guī)劃的最優(yōu)解。否則該最優(yōu)解，是整數(shù)規(guī)劃最優(yōu)數(shù)

27、規(guī)劃的最優(yōu)解。否則該最優(yōu)解，是整數(shù)規(guī)劃最優(yōu)解的上界或下界。解的上界或下界。例例 求解下列整數(shù)規(guī)劃：求解下列整數(shù)規(guī)劃：并取整數(shù)并取整數(shù), 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz2022-6-29340,5 . 45 . 01432.23max21212121xxxxxxtsxxz解：解：1 1、解對應(yīng)的線性規(guī)劃：、解對應(yīng)的線性規(guī)劃：其最優(yōu)解為其最優(yōu)解為 ，顯然不是整數(shù)規(guī)劃的可行解。顯然不是整數(shù)規(guī)劃的可行解。L0：75.140z)5 . 2,25. 3(2022-6-2935性質(zhì)性質(zhì) 求求MAXMAX的問題的問題：整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值整數(shù)規(guī)劃的最優(yōu)目

28、標(biāo)函數(shù)值小小于或等于于或等于相應(yīng)的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值；相應(yīng)的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值； 求求MINMIN的問題：整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值的問題：整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值大大于或等于于或等于相應(yīng)的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值。相應(yīng)的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值。2 2、分枝與定界：、分枝與定界： 將對應(yīng)的線性規(guī)劃問題分解成幾個子問題，每將對應(yīng)的線性規(guī)劃問題分解成幾個子問題，每個子問題就是一分枝，而所有子問題的解集之和個子問題就是一分枝，而所有子問題的解集之和要包含原整數(shù)規(guī)劃的解集。要包含原整數(shù)規(guī)劃的解集。2022-6-2936求解每一分枝子問題：求解每一分枝子問題： 若其最優(yōu)解滿足整數(shù)約束，則它就

29、是原問題的若其最優(yōu)解滿足整數(shù)約束，則它就是原問題的一個可行解（不一定是最優(yōu)）；否則，就是該枝的一個可行解（不一定是最優(yōu)）；否則，就是該枝的上界或下界。上界或下界。 若所有分支的最優(yōu)解都不滿足整數(shù)條件（即不若所有分支的最優(yōu)解都不滿足整數(shù)條件（即不是原問題的可行解），則選取一個邊界值最優(yōu)的分是原問題的可行解），則選取一個邊界值最優(yōu)的分支繼續(xù)分解，直至找到一個原問題的可行解。支繼續(xù)分解，直至找到一個原問題的可行解。 若在同一級分枝中同時出現(xiàn)兩個以上的原問題若在同一級分枝中同時出現(xiàn)兩個以上的原問題可行解，則保留目標(biāo)值最優(yōu)的一個，其余不再考慮。可行解，則保留目標(biāo)值最優(yōu)的一個，其余不再考慮。從各分枝中找原

30、問題可行解的目的是為下一步的比從各分枝中找原問題可行解的目的是為下一步的比較與剪枝。較與剪枝。2022-6-2937將上述線性規(guī)劃問題分為兩枝，并求解。將上述線性規(guī)劃問題分為兩枝，并求解。5 .14, 2, 5 . 3121zxx解得解得5 .13, 3, 5 . 2221zxx解得解得L1：L2：0,25 . 45 . 01432.23max212212121xxxxxxxtsxxz0,35 . 45 . 01432.23max212212121xxxxxxxtsxxz顯然兩個分枝均非整數(shù)可行解，選邊界值較大的顯然兩個分枝均非整數(shù)可行解，選邊界值較大的L L1 1繼續(xù)分枝。繼續(xù)分枝。 202

31、2-6-2938將將L1L1分為兩枝，并求解。分為兩枝，并求解。13, 2, 3121zxx解得解得14, 1, 4221zxx解得解得L11：L12：0,325 . 45 . 01432.23max2112212121xxxxxxxxtsxxz兩個分枝均是整數(shù)可行解，保留目標(biāo)值較大的兩個分枝均是整數(shù)可行解，保留目標(biāo)值較大的L L1212。 0,425 . 45 . 01432.23max2112212121xxxxxxxxtsxxz2022-6-29393 3、比較與剪枝比較與剪枝 將各子問題的邊界值與保留下的整數(shù)可行解對將各子問題的邊界值與保留下的整數(shù)可行解對應(yīng)的目標(biāo)值比較，將邊界值劣于可

32、行行解的分支減應(yīng)的目標(biāo)值比較，將邊界值劣于可行行解的分支減剪去。剪去。 若比較剪枝后，只剩下所保留的整數(shù)可行解，則若比較剪枝后，只剩下所保留的整數(shù)可行解，則該解就是原整數(shù)規(guī)劃的最優(yōu)解；否則選取邊界值最該解就是原整數(shù)規(guī)劃的最優(yōu)解；否則選取邊界值最大的一個分枝繼續(xù)分解，在其后的過程中出現(xiàn)新的大的一個分枝繼續(xù)分解，在其后的過程中出現(xiàn)新的整數(shù)可行解時，則與原可行解比較，保留較優(yōu)的一整數(shù)可行解時，則與原可行解比較，保留較優(yōu)的一個，重復(fù)第三步。個，重復(fù)第三步。2022-6-2940L0：X22X23X13X14用圖表示上例的求解過程與求解結(jié)果用圖表示上例的求解過程與求解結(jié)果75.14, 5 . 2,25.

33、 3121zxx5 .14, 2, 5 . 3121zxx5 .13, 3, 5 . 2221zxx13, 2, 3121zxx14, 1, 4221zxx2022-6-29415 5 割平面法割平面法 5 5.1.1 基本思想基本思想 在整數(shù)規(guī)劃的松弛問題中，依次引進新的約束條在整數(shù)規(guī)劃的松弛問題中，依次引進新的約束條件（割平面），使問題的可行域逐步減小，但每件（割平面），使問題的可行域逐步減小，但每次割去的只是部分非整數(shù)解，直到使問題的目標(biāo)次割去的只是部分非整數(shù)解，直到使問題的目標(biāo)函數(shù)值達到最優(yōu)的整數(shù)點成為縮小后的可行域的函數(shù)值達到最優(yōu)的整數(shù)點成為縮小后的可行域的一個頂點，這樣就可以用線性

34、規(guī)劃的方法求得整一個頂點，這樣就可以用線性規(guī)劃的方法求得整數(shù)最優(yōu)解。數(shù)最優(yōu)解。2022-6-2942例例 求解下列整數(shù)規(guī)劃：求解下列整數(shù)規(guī)劃：并取整數(shù)并取整數(shù), 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz0,921432.23max21212121xxxxxxtsxxz解：解：1 1、解對應(yīng)的線性規(guī)劃（松弛問題），并將、解對應(yīng)的線性規(guī)劃（松弛問題），并將約束條件的系數(shù)均化為整數(shù)：約束條件的系數(shù)均化為整數(shù)：2022-6-2943加入松弛變量后求解，得最終單純形表：加入松弛變量后求解，得最終單純形表：25/2011/2-1/2313/410-1/43/400-1/4-5/41x4x3x1x2x2xj如果上述求解結(jié)果是整數(shù)解，則結(jié)束；否則轉(zhuǎn)下如果上述求解結(jié)果是整數(shù)解，則結(jié)束；否則轉(zhuǎn)下一步；一步；2 2、找出非整數(shù)解中分?jǐn)?shù)部分最大的一個基變量，、找出非整數(shù)解中分?jǐn)?shù)部分最大的一個基變量，并將該行對應(yīng)的約束方程所有常數(shù)（系數(shù)及常數(shù)項）并將該行對