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

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

貨物每件體積/立方英尺每件重量/百千克每件利潤/百元甲19542乙273403托運(yùn)限制1365140甲種貨物至多托運(yùn)4件，問兩種貨物各托運(yùn)多少件，可使獲得利潤最大？解設(shè)x1、x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型5.1整數(shù)規(guī)劃實(shí)例例5.2某服務(wù)部門各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)如下表。按規(guī)定，服務(wù)員連續(xù)工作8個(gè)小時(shí)（4個(gè)時(shí)段），問如何安排服務(wù)員，使服務(wù)員總數(shù)最少。時(shí)段12345678服務(wù)員最少所需人數(shù)10891113853例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所示。問應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小？如果A2和A3兩地必須有且只有一個(gè)建廠，怎么辦？1、整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式整數(shù)規(guī)劃問題的松弛問題xj部分或全部取整數(shù)整數(shù)規(guī)劃的類型純整數(shù)規(guī)劃：變量全部是整數(shù)混合整數(shù)規(guī)劃：變量部分整數(shù)，部分非整數(shù)0-1型整數(shù)規(guī)劃：變量=0或110整數(shù)規(guī)劃對應(yīng)松弛問題最優(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

x2

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

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

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

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