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

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

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

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

4、5 . 45 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若當(dāng)作一般線(xiàn)性規(guī)劃求若當(dāng)作一般線(xiàn)性規(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ū)域交叉點(diǎn)，可比較這域交叉點(diǎn)，可比較這些點(diǎn)對(duì)應(yīng)的函數(shù)值，些點(diǎn)對(duì)應(yīng)的函數(shù)值，找出最優(yōu)。找出最優(yōu)。) 1, 4(2022-3-1762 2 應(yīng)用舉例應(yīng)用舉例2 2.1.1 邏輯變量在數(shù)學(xué)模型中

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

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

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

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

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

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

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

12、456容積（容積（m3）0.080.100.120.150.200.25需求量（個(gè)）需求量（個(gè)）500550700900450400可變費(fèi)用（元可變費(fèi)用（元/個(gè)）個(gè)）5.08.010.012.116.318.2由于生產(chǎn)不同容積包裝箱時(shí)需進(jìn)行專(zhuān)門(mén)的準(zhǔn)備、下由于生產(chǎn)不同容積包裝箱時(shí)需進(jìn)行專(zhuān)門(mén)的準(zhǔn)備、下料等，生產(chǎn)每一種包裝箱的固定費(fèi)用都是料等，生產(chǎn)每一種包裝箱的固定費(fèi)用都是12001200元。元。又若某容積的包裝箱數(shù)量不夠時(shí)，可用比它大的代又若某容積的包裝箱數(shù)量不夠時(shí)，可用比它大的代替。試問(wèn)該廠(chǎng)應(yīng)訂做哪幾種代號(hào)的包裝箱各多少個(gè)，替。試問(wèn)該廠(chǎng)應(yīng)訂做哪幾種代號(hào)的包裝箱各多少個(gè)，可使得費(fèi)用最?。靠墒沟觅M(fèi)用

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

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

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

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

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

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

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

20、22-3-1725匈牙利解法匈牙利解法步驟：步驟：1 1、在效率矩陣每行減去該行最小元素；、在效率矩陣每行減去該行最小元素；2 2、在效率矩陣每列減去該列最小元素；、在效率矩陣每列減去該列最小元素；411429131541116141381441579102591100532410011578005005411000324501152802022-3-17263 3、尋找獨(dú)立、尋找獨(dú)立“0”0”元素元素( (不同行不同列）不同行不同列）（1 1）從第一行開(kāi)始，若該行只有一個(gè)）從第一行開(kāi)始，若該行只有一個(gè)“0”0”元素，元素，則對(duì)該則對(duì)該“0”0”元素打括號(hào)（元素打括號(hào)（ ）（表示這一行的人只（

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

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

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

24、線(xiàn)覆蓋的列，令線(xiàn)覆蓋的列，令 。其余為。其余為0 0。）對(duì)矩陣的每個(gè)元素計(jì)算對(duì)矩陣的每個(gè)元素計(jì)算 ，得到，得到一個(gè)新矩陣，轉(zhuǎn)第三步重復(fù)進(jìn)行，直至每一行都有一個(gè)新矩陣，轉(zhuǎn)第三步重復(fù)進(jìn)行，直至每一行都有一打括號(hào)的一打括號(hào)的0 0元素。元素。kuikvjjiijvua2022-3-1730（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-3-

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

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

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

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

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

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

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

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

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

34、性規(guī)劃的方法求得整一個(gè)頂點(diǎn)，這樣就可以用線(xiàn)性規(guī)劃的方法求得整數(shù)最優(yōu)解。數(shù)最優(yōu)解。2022-3-1742例例 求解下列整數(shù)規(guī)劃：求解下列整數(shù)規(guī)劃：并取整數(shù)并取整數(shù), 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz0,921432.23max21212121xxxxxxtsxxz解：解：1 1、解對(duì)應(yīng)的線(xiàn)性規(guī)劃（松弛問(wèn)題），并將、解對(duì)應(yīng)的線(xiàn)性規(guī)劃（松弛問(wèn)題），并將約束條件的系數(shù)均化為整數(shù)：約束條件的系數(shù)均化為整數(shù)：2022-3-1743加入松弛變量后求解，得最終單純形表：加入松弛變量后求解，得最終單純形表：25/2011/2-1/2313/410-1/43/40

35、0-1/4-5/41x4x3x1x2x2xj如果上述求解結(jié)果是整數(shù)解，則結(jié)束；否則轉(zhuǎn)下如果上述求解結(jié)果是整數(shù)解，則結(jié)束；否則轉(zhuǎn)下一步；一步；2 2、找出非整數(shù)解中分?jǐn)?shù)部分最大的一個(gè)基變量，、找出非整數(shù)解中分?jǐn)?shù)部分最大的一個(gè)基變量，并將該行對(duì)應(yīng)的約束方程所有常數(shù)（系數(shù)及常數(shù)項(xiàng)）并將該行對(duì)應(yīng)的約束方程所有常數(shù)（系數(shù)及常數(shù)項(xiàng)）分解成一個(gè)整數(shù)與一個(gè)正分?jǐn)?shù)之和；將所有分式項(xiàng)分解成一個(gè)整數(shù)與一個(gè)正分?jǐn)?shù)之和；將所有分式項(xiàng)移到等式右端。移到等式右端。例如上例，取第一行約束例如上例，取第一行約束. . 2022-3-174443424324322121212212)211(21252121xxxxxxxxxx易知，左端為整數(shù)，要是等式成立，右端也必為整易知，左端為整數(shù)，要是等式成立，右端也必為整數(shù)，且數(shù)，且02121211212121214343xxxx將將 代入上式，得代入上式，得214213293214xxxxxx112221 xx2022-3-17451x2x143221 xx