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

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

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

4、一般形式整數(shù)規(guī)劃問題的松弛問題整數(shù)規(guī)劃問題的松弛問題 )n, 2 , 1j (0 x)m, 2 , 1i (b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整數(shù)部分或全部取整數(shù)整數(shù)規(guī)劃的類型整數(shù)規(guī)劃的類型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ī)劃對應松弛問題最優(yōu)解為：x1=2.44, x2=3.26,目標函數(shù)值為14.66。 整數(shù)規(guī)劃的最優(yōu)解為：x1=4, x2=2,目標函數(shù)值為14。12341232x1+

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

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

7、在西區(qū)由兩個點中至少選擇一個；l在南區(qū)由兩個點中至少選擇一個；l在北區(qū)由三個點中至少選擇兩個。投資總額不能超過720萬元，問應該選擇哪幾個銷售點，可使年利潤為最大？ 109876 5432161584825302022504036maxxxxxxxxxxxz.10,.,3 , 2 , 110021127201801501201001098765432110321ixxxxxxxxxxxxxxxxii變量，為且s.t.在東區(qū)由三個點中最多選擇兩個在西區(qū)由兩個點中至少選擇一個在南區(qū)由兩個點中至少選擇一個在北區(qū)由三個點中至少選擇兩個l例例5.6 有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用

8、及售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見下表。要求制定一個生產(chǎn)計劃，使總收益最大。解解 為提高搜索效率，減少運算量，先按照目標函數(shù)中各變量系數(shù)的大小順序重新排列各變量。 對于求極大值問題，按照從小到大對于求極大值問題，按照從小到大排為x3,x2,x1。（注意：對于求極小值問題，應從大到小排序求極小值問題，應從大到小排序）(x3,x2,x1)z值約束條件過濾條件abcd0，0，00，0，10，1，00，1，11，0，01，0，11，1，01，1，100z22z1不檢驗3不檢驗-1不檢驗1不檢驗0不檢驗2不檢驗l例例5.9 有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗

9、的時間(我們稱之為消耗系數(shù))如表5-6所示，問應如何分配任務，才能使總的消耗時間最少？l步驟1：首先讓每一行、每一列減去該行（列）的最小數(shù)，保證每一行、每一列都有零。l步驟2：試指派。l將只有一個0元素的行（列）的0最先畫圈，變?yōu)?（稱為獨立零元素獨立零元素）。然后將其所在列（行）其它的0劃掉。然后繼續(xù)尋找，直到?jīng)]有0可劃為止。l步驟3：如果獨立零元素的個數(shù)等于n計算停止，按照獨立零元素對應的位置進行指派即可。否則進入下一步進行調整。l步驟4：調整：l任意選擇一個沒有獨立零元素的行，將該行所有元素減去該行除外的最小數(shù)(m)；l然后該行的將會變?yōu)椋瑸榱藢⒇摂?shù)刪除，我們將該行所有元素加上m；l則原

10、來的所在的列中的0會被變?yōu)檎龜?shù)。為了使0所在行能夠找到新的0，須讓該行所有元素再減去除0外的最小數(shù)。如果此時沒有出現(xiàn)負數(shù)，調整結束；否則繼續(xù)使負數(shù)所在列加上一個常數(shù)，繼續(xù)循環(huán)。l直到系數(shù)矩陣中沒有負數(shù)，而且整個消耗系數(shù)矩陣的所有元素總和已經(jīng)變?。淮藭r調整結束，重新回到step2。15172124192322182617161919212317C每行減該行最小數(shù)每行減該行最小數(shù)02691540101032460每列減該列最小數(shù)每列減該列最小數(shù)0169144010003236001691440100032360此時獨立零元素有3個，第四行沒有，故轉入步驟4。01691440100032360l第四

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

12、以讓第一行再減1 -2+2 -1016110332100050140105100110120052140105100110120052140此時找到了4個獨立零元素，所以最優(yōu)方案為：01001000*00100001X6917161917*z 65325746798596811練習題：練習題： 1723211919161726182223192421181519*Z 70*Z 非標準形式指派問題的處理非標準形式指派問題的處理1、最大化指派問題：目標函數(shù)求、最大化指派問題：目標函數(shù)求max nn2n1nn22221n11211cccccccccC nn2n1nn22221n11211cmcmcm

13、cmcmcmcmcmcmB最大元素：最大元素：m將原系數(shù)矩陣將原系數(shù)矩陣C轉換為轉換為B有5個工人，要指派去做5項工作，每人做各項工作的能力見下表。應如何指派，才能使總的得分最大？ J1J2J3J4J5S1S2S3S4S51551712511012931313080853912106812工人工作12989128130127651301108131151203515C15151515151515151515151515151515151515151515151515C1298912813012765130110813115120351536763721538910215145724103151

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