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

1、5.1 整數(shù)規(guī)劃實(shí)例及一般模型整數(shù)規(guī)劃實(shí)例及一般模型5.2 分支定界法分支定界法5.3 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃5.4 指派問(wèn)題指派問(wèn)題例例5.1 某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如下物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如下表所示。表所示。 貨物每件體積/立方英尺每件重量/百千克每件利潤(rùn)/百元甲19542乙273403托運(yùn)限制1365140 甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大？l解解 設(shè)x1、x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型為整數(shù)2121121212

2、1,0,41404041365273195. .32maxxxxxxxxxxtsxxz例例5.2 某服務(wù)部門各時(shí)段（每某服務(wù)部門各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)如下表。按規(guī)定，服務(wù)員連續(xù)工作員人數(shù)如下表。按規(guī)定，服務(wù)員連續(xù)工作8個(gè)小時(shí)（個(gè)小時(shí)（4個(gè)個(gè)時(shí)段），問(wèn)如何安排服務(wù)員，使服務(wù)員總數(shù)最少。時(shí)段），問(wèn)如何安排服務(wù)員，使服務(wù)員總數(shù)最少。時(shí)段時(shí)段12345678服務(wù)員最少所需人數(shù)服務(wù)員最少所需人數(shù)10891113853且為整數(shù)0,35813119810min5215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxx

3、xxxzl例5.3 某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠，已知在A2地建廠的固定成本為175千元，在A3地建廠的固定成本為300千元，在A4地建廠的固定成本為375千元，在A5地建廠的固定成本為500千元，另外，在A1的產(chǎn)量，A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)（每千箱運(yùn)費(fèi)）如下表5-3所示。問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最?。咳绻鸄2和A3兩地必須有且只有一個(gè)建廠，怎么辦？1、整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式、整數(shù)規(guī)劃數(shù)學(xué)模型的

4、一般形式整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題 )n, 2 , 1j (0 x)m, 2 , 1i (b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整數(shù)部分或全部取整數(shù)l純整數(shù)規(guī)劃：變量純整數(shù)規(guī)劃：變量全部全部是整數(shù)是整數(shù)l混合整數(shù)規(guī)劃：變量部分整數(shù)，部分非整數(shù)混合整數(shù)規(guī)劃：變量部分整數(shù)，部分非整數(shù)l0-1型整數(shù)規(guī)劃：變量型整數(shù)規(guī)劃：變量= 0或或110 整數(shù)規(guī)劃對(duì)應(yīng)松弛問(wèn)題最優(yōu)解為：x1=2.44, x2=3.26,目標(biāo)函數(shù)值為14.66。 整數(shù)規(guī)劃的最優(yōu)解為：x1=4, x2=2,目標(biāo)函數(shù)值為14。12341232x1+3x2 =14.66x1 x

5、2 2x1+3x2 =142x1+3x2 =61、整數(shù)規(guī)劃的可行解集合是其松弛問(wèn)題可行解集合的子集 ；整數(shù)規(guī)劃最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于松弛問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值。2、整數(shù)規(guī)劃的最優(yōu)解不一定是對(duì)松弛問(wèn)題最優(yōu)解變量的簡(jiǎn)單取整。l分支：若松弛問(wèn)題最優(yōu)解中存在變量xi=bi不滿足整數(shù)約束，記bi為不超過(guò)bi的最大整數(shù)，則構(gòu)造兩個(gè)新 的約束xi bi ，和xi bi+1。將它們分別并入到原松弛問(wèn)題中，形成原松弛問(wèn)題的兩個(gè)分支（后繼問(wèn)題）。當(dāng)分支的最優(yōu)解也不滿足整數(shù)約束時(shí)，可以繼續(xù)構(gòu)造它們的分支。l定界：在分支的過(guò)程中，若某個(gè)后繼問(wèn)題恰好獲得了整數(shù)規(guī)劃的一個(gè)可行解，則這一可行解的目標(biāo)函數(shù)值可看成一個(gè)“界

6、限”，作為處理其他分支的依據(jù)。l例5.4 求解如下整數(shù)規(guī)劃：首先求解其松弛規(guī)劃：0,18241432. .23max21212121xxxxxxtsxxz最優(yōu)解為X=(3.25,2.5)，z=14.75因?yàn)閤1=3.25，所以將其分為x1=4兩個(gè)分支31x41x因?yàn)閤2=8/3，所以將其分為x2=3兩個(gè)分支32x22x所以X*=(4,1)，Z*=14l例5.5 廣州某食品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，目前有10個(gè)位置可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集程度，規(guī)定：l在東區(qū)由三個(gè)點(diǎn)中最多選擇兩個(gè)；l在西區(qū)由兩個(gè)點(diǎn)中至少選擇一個(gè)；l在南區(qū)由兩個(gè)點(diǎn)中至少選擇一個(gè)；l

7、在北區(qū)由三個(gè)點(diǎn)中至少選擇兩個(gè)。投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)該選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大？ 109876 5432161584825302022504036maxxxxxxxxxxxz.10,.,3 , 2 , 110021127201801501201001098765432110321ixxxxxxxxxxxxxxxxii變量，為且s.t.在東區(qū)由三個(gè)點(diǎn)中最多選擇兩個(gè)在西區(qū)由兩個(gè)點(diǎn)中至少選擇一個(gè)在南區(qū)由兩個(gè)點(diǎn)中至少選擇一個(gè)在北區(qū)由三個(gè)點(diǎn)中至少選擇兩個(gè)l例例5.6 有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見下表。要求制定一

8、個(gè)生產(chǎn)計(jì)劃，使總收益最大。解解 為提高搜索效率，減少運(yùn)算量，先按照目標(biāo)函數(shù)中各變量系數(shù)的大小順序重新排列各變量。 對(duì)于求極大值問(wèn)題，按照從小到大對(duì)于求極大值問(wèn)題，按照從小到大排為x3,x2,x1。（注意：對(duì)于求極小值問(wèn)題，應(yīng)從大到小排序求極小值問(wèn)題，應(yīng)從大到小排序）(x3,x2,x1)z值約束條件過(guò)濾條件abcd0，0，00，0，10，1，00，1，11，0，01，0，11，1，01，1，100z22z1不檢驗(yàn)3不檢驗(yàn)-1不檢驗(yàn)1不檢驗(yàn)0不檢驗(yàn)2不檢驗(yàn)l例例5.9 有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間(我們稱之為消耗系數(shù))如表5-6所示，問(wèn)應(yīng)如何分配任務(wù)，才

9、能使總的消耗時(shí)間最少？l步驟1：首先讓每一行、每一列減去該行（列）的最小數(shù)，保證每一行、每一列都有零。l步驟2：試指派。l將只有一個(gè)0元素的行（列）的0最先畫圈，變?yōu)?（稱為獨(dú)立零元素獨(dú)立零元素）。然后將其所在列（行）其它的0劃掉。然后繼續(xù)尋找，直到?jīng)]有0可劃為止。l步驟3：如果獨(dú)立零元素的個(gè)數(shù)等于n計(jì)算停止，按照獨(dú)立零元素對(duì)應(yīng)的位置進(jìn)行指派即可。否則進(jìn)入下一步進(jìn)行調(diào)整。l步驟4：調(diào)整：l任意選擇一個(gè)沒有獨(dú)立零元素的行，將該行所有元素減去該行除外的最小數(shù)(m)；l然后該行的將會(huì)變?yōu)?，為了將?fù)數(shù)刪除，我們將該行所有元素加上m；l則原來(lái)的所在的列中的0會(huì)被變?yōu)檎龜?shù)。為了使0所在行能夠找到新的0，須

10、讓該行所有元素再減去除0外的最小數(shù)。如果此時(shí)沒有出現(xiàn)負(fù)數(shù)，調(diào)整結(jié)束；否則繼續(xù)使負(fù)數(shù)所在列加上一個(gè)常數(shù)，繼續(xù)循環(huán)。l直到系數(shù)矩陣中沒有負(fù)數(shù)，而且整個(gè)消耗系數(shù)矩陣的所有元素總和已經(jīng)變小；此時(shí)調(diào)整結(jié)束，重新回到step2。15172124192322182617161919212317C每行減該行最小數(shù)每行減該行最小數(shù)02691540101032460每列減該列最小數(shù)每列減該列最小數(shù)0169144010003236001691440100032360此時(shí)獨(dú)立零元素有3個(gè)，第四行沒有，故轉(zhuǎn)入步驟4。01691440100032360l第四行沒有獨(dú)立零元素，所第四行沒有獨(dú)立零元素，所以讓該行減以讓該行減

11、2l第四行第四列的第四行第四列的0變?yōu)樽優(yōu)?2，所以讓第四列再加所以讓第四列再加2l第四列的獨(dú)立零元素被破壞，第四列的獨(dú)立零元素被破壞，所以讓第二行再減所以讓第二行再減1 -2+2 -1016110332100050140016110332100050140此時(shí)獨(dú)立零元素還是只有3個(gè)，第二行沒有，故轉(zhuǎn)入步驟4。l第二行沒有獨(dú)立零元素，所第二行沒有獨(dú)立零元素，所以讓該行減以讓該行減2l第二行第一列的第二行第一列的0變?yōu)樽優(yōu)?2，所以讓第一列再加所以讓第一列再加2l第一列的獨(dú)立零元素被破壞，第一列的獨(dú)立零元素被破壞，所以讓第一行再減所以讓第一行再減1 -2+2 -10161103321000501

12、40105100110120052140105100110120052140此時(shí)找到了4個(gè)獨(dú)立零元素，所以最優(yōu)方案為：01001000*00100001X6917161917*z 65325746798596811練習(xí)題：練習(xí)題： 1723211919161726182223192421181519*Z 70*Z 非標(biāo)準(zhǔn)形式指派問(wèn)題的處理非標(biāo)準(zhǔn)形式指派問(wèn)題的處理1、最大化指派問(wèn)題：目標(biāo)函數(shù)求、最大化指派問(wèn)題：目標(biāo)函數(shù)求max nn2n1nn22221n11211cccccccccC nn2n1nn22221n11211cmcmcmcmcmcmcmcmcmB最大元素：最大元素：m將原系數(shù)矩陣將原

13、系數(shù)矩陣C轉(zhuǎn)換為轉(zhuǎn)換為B有5個(gè)工人，要指派去做5項(xiàng)工作，每人做各項(xiàng)工作的能力見下表。應(yīng)如何指派，才能使總的得分最大？ J1J2J3J4J5S1S2S3S4S51551712511012931313080853912106812工人工作12989128130127651301108131151203515C15151515151515151515151515151515151515151515151515C129891281301276513011081311512035153676372153891021514572410315121000343050131678013123502831512

14、100034205013067801212350183151290-3 +3-10041080162975011123200831212801000001000001000001000001*X64*z2、人數(shù)、人數(shù)事數(shù)事數(shù)人數(shù)人數(shù)事數(shù)：添加虛擬事數(shù)：添加虛擬“事事”， c = 03、一個(gè)人可以做幾件事、一個(gè)人可以做幾件事將一人化為相同的多個(gè)人來(lái)接受指派，這多個(gè)將一人化為相同的多個(gè)人來(lái)接受指派，這多個(gè)人做同一件事的費(fèi)用相同人做同一件事的費(fèi)用相同4、某事不能由某人來(lái)做、某事不能由某人來(lái)做將相應(yīng)的費(fèi)用系數(shù)取無(wú)窮大將相應(yīng)的費(fèi)用系數(shù)取無(wú)窮大Ml例5.12 某大型工程共由5個(gè)項(xiàng)目A、B、C、D、E組成，現(xiàn)有三個(gè)公司甲、乙、丙分別來(lái)投標(biāo)，各自給出的報(bào)價(jià)如下表所示。這里甲乙丙三家公司實(shí)力均比較雄厚，可以同時(shí)進(jìn)行兩個(gè)項(xiàng)目的施工，請(qǐng)給出最優(yōu)施工分配方案。ABCDE甲151791218乙1418101