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

第五章整數(shù)規(guī)劃5.1整數(shù)規(guī)劃實例及一般模型5.2分支定界法5.30-1整數(shù)規(guī)劃5.4指派問題5.1整數(shù)規(guī)劃實例例5.1某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如下表所示。

貨物每件體積/立方英尺每件重量/百千克每件利潤/百元甲19542乙273403托運限制1365140甲種貨物至多托運4件，問兩種貨物各托運多少件，可使獲得利潤最大？解設x1、x2分別為甲、乙兩種貨物托運的件數(shù)，建立模型5.1整數(shù)規(guī)劃實例例5.2某服務部門各時段（每2小時為一時段）需要的服務員人數(shù)如下表。按規(guī)定，服務員連續(xù)工作8個小時（4個時段），問如何安排服務員，使服務員總數(shù)最少。時段12345678服務員最少所需人數(shù)10891113853例5.3某企業(yè)在A1地已有一個工廠，其產品的生產能力為30千箱，為了擴大生產，打算在A2，A3，A4，A5地中再選擇幾個地方建廠，已知在A2地建廠的固定成本為175千元，在A3地建廠的固定成本為300千元，在A4地建廠的固定成本為375千元，在A5地建廠的固定成本為500千元，另外，在A1的產量，A2，A3，A4，A5建成廠的產量，那時銷地的銷量以及產地到銷地的單位運價（每千箱運費）如下表5-3所示。問應該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最??？如果A2和A3兩地必須有且只有一個建廠，怎么辦？1、整數(shù)規(guī)劃數(shù)學模型的一般形式整數(shù)規(guī)劃問題的松弛問題xj部分或全部取整數(shù)整數(shù)規(guī)劃的類型純整數(shù)規(guī)劃：變量全部是整數(shù)混合整數(shù)規(guī)劃：變量部分整數(shù)，部分非整數(shù)0-1型整數(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+3x2=14.66x1

x2

2x1+3x2=142x1+3x2=6整數(shù)規(guī)劃解的特點（與松弛問題的關系）1、整數(shù)規(guī)劃的可行解集合是其松弛問題可行解集合的子集；整數(shù)規(guī)劃最優(yōu)解的目標函數(shù)值不會優(yōu)于松弛問題最優(yōu)解的目標函數(shù)值。2、整數(shù)規(guī)劃的最優(yōu)解不一定是對松弛問題最優(yōu)解變量的簡單取整。5.2分支定界法分支：若松弛問題最優(yōu)解中存在變量xi=bi′不滿足整數(shù)約束，記[bi′]為不超過bi′的最大整數(shù)，則構造兩個新的約束xi≤[bi′]，和xi≥[bi′]+1。將它們分別并入到原松弛問題中，形成原松弛問題的兩個分支（后繼問題）。當分支的最優(yōu)解也不滿足整數(shù)約束時，可以繼續(xù)構造它們的分支。定界：在分支的過程中，若某個后繼問題恰好獲得了整數(shù)規(guī)劃的一個可行解，則這一可行解的目標函數(shù)值可看成一個“界限”，作為處理其他分支的依據。例5.4求解如下整數(shù)規(guī)劃：首先求解其松弛規(guī)劃：最優(yōu)解為X=(3.25,2.5)’，z=14.75因為x1=3.25，所以將其分為x1<=3和x1>=4兩個分支因為x2=8/3，所以將其分為x2<=2和x2>=3兩個分支所以X*=(4,1)，Z*=145.30-1ILP例5.5

廣州某食品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，目前有10個位置可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集程度，規(guī)定：在東區(qū)由三個點中最多選擇兩個；在西區(qū)由兩個點中至少選擇一個；在南區(qū)由兩個點中至少選擇一個；在北區(qū)由三個點中至少選擇兩個。投資總額不能超過720萬元，問應該選擇哪幾個銷售點，可使年利潤為最大？

s.t.在東區(qū)由三個點中最多選擇兩個在西區(qū)由兩個點中至少選擇一個在南區(qū)由兩個點中至少選擇一個在北區(qū)由三個點中至少選擇兩個例5.6有三種資源被用于生產三種產品，資源量、產品單件可變費用及售價、資源單耗量及組織三種產品生產的固定費用見下表。要求制定一個生產計劃，使總收益最大。5.3.20-1ILP的隱枚舉法解為提高搜索效率，減少運算量，先按照目標函數(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，1021不檢驗3不檢驗-1不檢驗1不檢驗0不檢驗2不檢驗5.4指派問題例5.9有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間(我們稱之為消耗系數(shù))如表5-6所示，問應如何分配任務，才能使總的消耗時間最少？5.4.2指派問題的匈牙利算法步驟1：首先讓每一行、每一列減去該行（列）的最小數(shù)，保證每一行、每一列都有零。步驟2：試指派。將只有一個0元素的行（列）的0最先畫圈，變?yōu)?（稱為獨立零元素）。然后將其所在列（行）其它的0劃掉。然后繼續(xù)尋找，直到沒有0可劃為止。步驟3：如果獨立零元素的個數(shù)等于n計算停止，按照獨立零元素對應的位置進行指派即可。否則進入下一步進行調整。步驟4：調整：任意選擇一個沒有獨立零元素的行，將該行所有元素減去該行除外的最小數(shù)(m)；然后該行的將會變?yōu)?，為了將負?shù)刪除，我們將該行所有元素加上m；則原來的所在的列中的0會被變?yōu)檎龜?shù)。為了使0所在行能夠找到新的0，須讓該行所有元素再減去除0外的最小數(shù)。如果此時沒有出現(xiàn)負數(shù)，調整結束；否則繼續(xù)使負數(shù)所在列加上一個常數(shù)，繼續(xù)循環(huán)。直到系數(shù)矩陣中沒有負數(shù)，而且整個消耗系數(shù)矩陣的所有元素總和已經變小；此時調整結束，重新回到step2。每行減該行最小數(shù)每列減該列最小數(shù)步驟1：行減、列減步驟2：試指派(某行某列只有一個0，優(yōu)先選中)此時獨立零元素有3個，第四行沒有，故轉入步驟4。步驟4：調整第四行沒有獨立零元素，所以讓該行減2第四行第四列的0變?yōu)?2，所以讓第四列再加2第四列的獨立零元素被破壞，所以讓第二行再減1√-2√+2√-1步驟2再次試指派此時獨立零元素還是只有3個，第二行沒有，故轉入步驟4。步驟4：調整第二行沒有獨立零元素，所以讓該行減2第二行第一列的0變?yōu)?2，所以讓第一列再加2第一列的獨立零元素被破壞，所以讓第一行再減1√-2√+2√-1步驟2再次試指派此時找到了4個獨立零元素，所以最優(yōu)方案為：練習題：非標準形式指派問題的處理1、最大化指派問題：目標函數(shù)求max最大元素：m將原系數(shù)矩陣C轉換為B最大化指派問題例題有5個工人，要指派去做5項工作，每人做各項工作的能力見下表。應如何指派，才能使總的得分最大？

J1J2J3J4J5S1S2S3S4S51551712511012931313080853912106812工人工作√-3√+3√-12、人數(shù)≠事數(shù)人數(shù)<事數(shù)：添加虛擬“人”，c=0人數(shù)>事數(shù)：添加虛擬“事”，c=03、一個人可以做幾件事將一人化為相同的多個人來接受指派，這多個人做同一件事的費用相同4、某事不能由某人來做將相應的費用系數(shù)取無窮大M一個人做多件事例5.