1、12第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法 2 整數(shù)規(guī)劃的計算機(jī)求解整數(shù)規(guī)劃的計算機(jī)求解 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用 4 整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法3整數(shù)規(guī)劃整數(shù)規(guī)劃是一類要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃，是一類要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃，可分成可分成線性線性和和非線性非線性兩類。兩類。求整數(shù)解的線性規(guī)劃問題，求整數(shù)解的線性規(guī)劃問題，應(yīng)注意：應(yīng)注意：不是不是用四舍五入法用四舍五入法和和去尾法對線性規(guī)劃的非去尾法對線性規(guī)劃的非整數(shù)解加以處理就能解決的。整數(shù)解加以處理就能解決的。整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃一些基本算法的設(shè)計是一些基本算法的設(shè)計是以相應(yīng)以相應(yīng)

2、線性規(guī)劃的最優(yōu)解為出發(fā)點線性規(guī)劃的最優(yōu)解為出發(fā)點而發(fā)展出來的。而發(fā)展出來的。根據(jù)變量的取值情況，整數(shù)線性規(guī)劃又可以分根據(jù)變量的取值情況，整數(shù)線性規(guī)劃又可以分為為純整數(shù)規(guī)劃純整數(shù)規(guī)劃（所有變量?。ㄋ凶兞咳》秦?fù)非負(fù)整數(shù)），整數(shù)），混合混合整數(shù)規(guī)劃整數(shù)規(guī)劃（部分變量?。ú糠肿兞咳》秦?fù)非負(fù)整數(shù)），整數(shù)），0-1整數(shù)規(guī)整數(shù)規(guī)劃劃（變量只?。ㄗ兞恐蝗?或或1）等。）等。第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃4整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃中一個較弱的分支，目前整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃中一個較弱的分支，目前有成熟的方法解有成熟的方法解線性整數(shù)規(guī)劃問題線性整數(shù)規(guī)劃問題，而非線性，而非線性整數(shù)規(guī)劃問題，還沒有好的辦法。整數(shù)規(guī)劃問題，還

3、沒有好的辦法。整整數(shù)線性規(guī)劃數(shù)線性規(guī)劃(Integer Linear Programming，簡記為簡記為ILP)問題研究的是要求變量取整數(shù)值時，問題研究的是要求變量取整數(shù)值時，在一組線性約束條件下一個線性函數(shù)最優(yōu)問題，在一組線性約束條件下一個線性函數(shù)最優(yōu)問題，是應(yīng)用非常廣泛的運籌學(xué)的一個重要分支。是應(yīng)用非常廣泛的運籌學(xué)的一個重要分支。 第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃51 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法例例1. 某公司擬用集裝箱托運甲、乙兩種貨物，某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。托運

4、所受限制如表所示。甲種貨物至多托運甲種貨物至多托運4件件，問兩種貨物各托運多，問兩種貨物各托運多少件，可使獲得的利潤最大。少件，可使獲得的利潤最大。貨物貨物每件體積每件體積(立方米立方米)每件重量每件重量(百千克百千克)每件利潤每件利潤（百元）（百元）甲甲乙乙19527344023托運限制托運限制1365140 6貨物貨物每件體積每件體積(立方米立方米)每件重量每件重量(百千克百千克)每件利潤每件利潤（百元）（百元）甲甲乙乙19527344023托運限制托運限制1365140 解：設(shè)解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運的件數(shù)，建分別為甲、乙兩種貨物托運的件數(shù)，建立模型。立模型。 目標(biāo)函

5、數(shù)：目標(biāo)函數(shù)： Max z = 2x1 +3x2 約束條件：約束條件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0, 為整數(shù)為整數(shù)。如果去掉最后一個約束，就是一個線性規(guī)劃問題如果去掉最后一個約束，就是一個線性規(guī)劃問題.1 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法7利用圖解法，得到線性規(guī)劃的最優(yōu)解為利用圖解法，得到線性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為14.66。由圖表可看出由圖表可看出, 整數(shù)規(guī)劃的最優(yōu)解（黃色叉號）為整數(shù)規(guī)劃的最優(yōu)解（黃色叉號）為x1=4, x2=2,目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為1

6、4。Max z = 2x1 +3x2195x1+273x2=13654 x1+40 x2 =1404231123x2x11 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法Max z = 2x1 +3x2 約束條件：約束條件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 48由于相應(yīng)的由于相應(yīng)的線性規(guī)劃的可行域包含線性規(guī)劃的可行域包含了其了其整整數(shù)規(guī)劃的可行點數(shù)規(guī)劃的可行點，則對于整數(shù)規(guī)劃，易知，則對于整數(shù)規(guī)劃，易知有以下性質(zhì)：有以下性質(zhì)：性質(zhì)性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值劃或混合整數(shù)規(guī)劃

7、的最大目標(biāo)函數(shù)值小于小于或等于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。1 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法9例例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1, x2, x3 0 , 均為整數(shù)均為整數(shù)用管理運籌學(xué)軟件用管理運籌學(xué)軟件求解得：求解得：

8、x1 = 5 x2 = 2 x3 = 2 2 2 整數(shù)規(guī)劃的計算機(jī)求解整數(shù)規(guī)劃的計算機(jī)求解純整數(shù)規(guī)劃問題純整數(shù)規(guī)劃問題1011例例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 - 3x2 + 2x3 3 x3 1 x1, x2, x3 0 x1，x3 為整數(shù)，為整數(shù)，x3 為為0-1變量變量用用管理運籌學(xué)管理運籌學(xué)軟件求軟件求解得解得: z = 16.25x1 = 4 x2 = 1.25 x3 = 1 123 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用應(yīng)用實例：應(yīng)用實例： 投資投資場所的選擇問題場所的選擇問題 背包問題背包問題

9、 固定成本固定成本問題問題 指派指派問題問題 分布系統(tǒng)設(shè)計分布系統(tǒng)設(shè)計 投資投資問題問題13143 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用 一、投資場所的選擇一、投資場所的選擇 例例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有建立銷售門市部，擬議中有10個位置個位置 Aj (j=1,2,3,10)可供選可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定: 在東區(qū)由在東區(qū)由A1 ， A2 ，A3 三個點三個點至多至多選擇選擇兩個兩個； 在西區(qū)由在西區(qū)由A4 ， A5 兩

10、個點中兩個點中至少至少選選一個一個； 在南區(qū)由在南區(qū)由A6 ， A7 兩個點中兩個點中至少至少選選一個一個； 在北區(qū)由在北區(qū)由A8 ， A9 ， A10 三個點中三個點中至少至少選選兩個兩個。 Aj 各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測情況見表所示預(yù)測情況見表所示 (單位：萬元單位：萬元)。但投資總額。但投資總額不能超過不能超過720萬萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大?解：設(shè)：解：設(shè)：0-1變量變量 xi = 1 (Ai 點被點被選用選用)或或 0 (Ai 點點沒被

11、選用沒被選用)。 這樣我們可建立如下的數(shù)學(xué)模型：這樣我們可建立如下的數(shù)學(xué)模型：Max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0 且且xi 為為0-1變量變量，i = 1, 2, 3, ,10在東區(qū)由在東區(qū)由A1 ， A2 ，A3 三個點三個點至多至多選擇選擇兩個兩個

12、；在西區(qū)由在西區(qū)由A4 ， A5 兩個點中兩個點中至少至少選選一個一個；在南區(qū)由在南區(qū)由A6 ， A7 兩個點中兩個點中至少至少選選一個一個；在北區(qū)由在北區(qū)由A8 ， A9 ， A10 三個點中三個點中至少至少選選兩個兩個補充例、解決某市消防站的布點問題，該城市有補充例、解決某市消防站的布點問題，該城市有6個個區(qū)，每個區(qū)都可以建消防站。市政府希望設(shè)置的消區(qū)，每個區(qū)都可以建消防站。市政府希望設(shè)置的消防站最少，但必須滿足在城市的任何地區(qū)發(fā)生火警防站最少，但必須滿足在城市的任何地區(qū)發(fā)生火警時，消防車時，消防車要在要在15分鐘內(nèi)分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間

13、如下表所示，請幫助該各區(qū)之間消防車行駛的時間如下表所示，請幫助該市制定一個最省的計劃。市制定一個最省的計劃。 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0 設(shè)設(shè) xi =1,0; 1i 區(qū)建消防站，區(qū)建消防站，0i 區(qū)不建消區(qū)不建消防站，防站，i=1,6min z = x1 + x2 + x3 + x4 + x5 + x6約束方程保證每個地區(qū)都有一個消防站在約束方程保證每個地區(qū)都有一個消防站在15分鐘行

14、程內(nèi)。分鐘行程內(nèi)。將將6個地區(qū)的條件分別列出：個地區(qū)的條件分別列出：s.t. x1 + x2 1, x1 + x2 + x6 1 x3 + x4 1, x3 + x4 + x5 1 x4 + x5 + x6 1, x2 + x5 + x6 1 xi = 0, 1; i=1,6 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 018 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24

15、32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第第2個地區(qū)建一個（地區(qū)個地區(qū)建一個（地區(qū)1、2、6都解決了）都解決了）第第4個地區(qū)建一個（地區(qū)個地區(qū)建一個（地區(qū)3、4、5都解決了）都解決了）二、二、背包問題背包問題（補充）（補充）背包可裝入背包可裝入8單位重量，單位重量，10單位體積物品。若單位體積物品。若背包中背包中每件物品至多只能裝一個每件物品至多只能裝一個，怎樣才能使背包，怎樣才能使背包裝的物品價值最高。裝的物品價值最高。物品物品 名稱名稱 重量重量 體積體積 價值價值 1

16、書書 5 2 20 2 攝像機(jī)攝像機(jī) 3 1 30 3 枕頭枕頭 1 4 10 4 休閑食品休閑食品 2 3 18 5 衣服衣服 4 5 15 解：解：xi為是否帶第為是否帶第 i 種物品種物品Max Z=20 x1 + 30 x2 +10 x3+18x4 +15x55x1+3x2 +x3 +2x4 +4x5 82x1+x2 +4x3 +3x4 +5x5 10 xi為為0, 1物品物品 名稱名稱 重量重量 體積體積 價值價值 1 書書 5 2 20 2 攝像機(jī)攝像機(jī) 3 1 30 3 枕頭枕頭 1 4 10 4 休閑食品休閑食品 2 3 18 5 衣服衣服 4 5 15 一般形式：一般形式：0

17、max11iniiiniiixbxaxCZ, 整數(shù)整數(shù) xi為是否攜帶第為是否攜帶第i 種物品種物品ai為為i 物品單位重量，物品單位重量，b為最大負(fù)重為最大負(fù)重ci為為i 物品重要性估價物品重要性估價223 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用三、固定成本問題三、固定成本問題 例例5高壓容器公司制造小、中、大三種尺寸的金屬高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī)器設(shè)備，制造一容器，所用資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的用，每種容器售出一只

18、所得的利潤分別為利潤分別為 4萬元、萬元、5萬元、萬元、6萬元萬元，可使用的金屬板有，可使用的金屬板有500噸，勞動力有噸，勞動力有300人人/月，機(jī)月，機(jī)器有器有100臺臺/月，此外不管每種容器制造的數(shù)量是多少，都月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆要支付一筆固定的費用：小號是固定的費用：小號是l00萬元，中號為萬元，中號為 150 萬萬元，大號為元，大號為200萬元。萬元。現(xiàn)在要制定一個生產(chǎn)計劃，使獲得現(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。的利潤為最大。23解：這是一個整數(shù)規(guī)劃的問題。解：這是一個整數(shù)規(guī)劃的問題。 設(shè)設(shè)x1，x2， x3 分別為小號容器、中號容器和大分別

19、為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在各種容器的固定費用只有在生產(chǎn)該種容器時才投入，若不生產(chǎn)則沒有這部分生產(chǎn)該種容器時才投入，若不生產(chǎn)則沒有這部分費用，費用，為了說明固定費用的這種性質(zhì)，為了說明固定費用的這種性質(zhì)，設(shè)設(shè) yi = 1(當(dāng)當(dāng)生產(chǎn)第生產(chǎn)第 i種容器種容器, 即即 xi 0 時時) 或或0（當(dāng)不生產(chǎn)第（當(dāng)不生產(chǎn)第 i種種容器即容器即 xi = 0 時）。時）。 引入約束引入約束 xi M yi ，i =1，2，3，M充分大，充分大，以保證當(dāng)以保證當(dāng) yi = 0 時，時，xi = 0 。 3 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用即：不投入固即

20、：不投入固定費用，是不定費用，是不能投入生產(chǎn)的能投入生產(chǎn)的24這樣我們可建立如下的數(shù)學(xué)模型：這樣我們可建立如下的數(shù)學(xué)模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 yj 為為0-1變量變量，i = 1,2,33 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用沒有固定投入，就不生產(chǎn)沒有固定投入，就不生產(chǎn).yi =0，則，則xi=0. xi是數(shù)量，是數(shù)量，M為一個充分大的數(shù)

21、。為一個充分大的數(shù)。一個容器至少需要一個容器至少需要2個勞動個勞動力，共有力，共有300個勞動力，因個勞動力，因此容器數(shù)量不會超過此容器數(shù)量不會超過150.因因此當(dāng)此當(dāng)yi =1時，時，M可取可取150投入固定費用，投入固定費用，生產(chǎn)小號容器生產(chǎn)小號容器y1y2y325三、指派問題三、指派問題 有有 n n 項不同的任務(wù)，恰好項不同的任務(wù)，恰好 n n 個人可分個人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派須指派每個人去完成一項任務(wù)每個人去完成一項任務(wù)，怎樣把，怎樣把 n n

22、 項任務(wù)指派給項任務(wù)指派給n n個人，使得完成個人，使得完成 n n 項任務(wù)的項任務(wù)的總的效率最高總的效率最高，這就是，這就是指派問題。指派問題。 3 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用26例例6 6有四個工人，要分別指派他們完成四項有四個工人，要分別指派他們完成四項不同的工作，不同的工作，每人做各項工作所消耗的時間每人做各項工作所消耗的時間如下表所示如下表所示，問應(yīng)如何指派工作，才能使，問應(yīng)如何指派工作，才能使總總的消耗時間為最少的消耗時間為最少。3 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用27解：引入解：引入01變量變量 xij，并令并令 xij =1(當(dāng)指派第當(dāng)指派第 i人去完成第人去完成第j項工

23、作時項工作時)或或0(當(dāng)不指當(dāng)不指派第派第i人去完成第人去完成第j項工作時項工作時)這可以表示為一個這可以表示為一個0-1整數(shù)規(guī)劃問題：整數(shù)規(guī)劃問題：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x443 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用28整數(shù)規(guī)劃模型為：整數(shù)規(guī)劃模型為：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21

24、x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作

25、只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 為為0-1變量變量，i,j = 1,2,3,43 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用每人只每人只能干一能干一項工作項工作一項工一項工作只能作只能由一個由一個人干人干 對于有對于有m個人完成個人完成n項任務(wù)的一般指派問題，項任務(wù)的一般指派問題，設(shè)：設(shè)：29變量為1-0,.,2, 1, 1,.,2, 1, 1min1111ijmiijnjijminjijijxnjxmixxCZm不一定等于不一定等于n，當(dāng)當(dāng)mn時，有的時，有的人沒有任務(wù)。人沒有任務(wù)。第第i個人完成的任務(wù)個人完成的任務(wù)且最多承擔(dān)一項

26、且最多承擔(dān)一項第第j項工作正好有一項工作正好有一人承擔(dān)人承擔(dān)注意：當(dāng)注意：當(dāng)m0 yi=0時，當(dāng)不利用第時，當(dāng)不利用第i種設(shè)備生產(chǎn)時，此時相應(yīng)種設(shè)備生產(chǎn)時，此時相應(yīng)的的Xi=0 目標(biāo)函數(shù)為：目標(biāo)函數(shù)為： Min Z=7x1+2x2+5x3+100y1+300y2+200y358 (1) 約束條件約束條件 X1 800，X2 1200，X3 1400， X1+X2+X3=2000(改大于等于結(jié)果相同改大于等于結(jié)果相同) 0.5X1+1.8X2+1.0X3 2000 還得保證還得保證Yi=0時，時，Xi=0.(沒有準(zhǔn)備費就不啟沒有準(zhǔn)備費就不啟用該設(shè)備用該設(shè)備)，引入一個很大的，引入一個很大的M X

27、i M Yi（i=1,2,3） Xi 0,（i=1,2,3） Yi（i=1,2,3）是）是0-1變量變量59 （2）約束條件改為 0.5X1+1.8X2+1.0X3 250060 （3）約束條件改為 0.5X1+1.8X2+1.0X3 280061 （4）去掉電量的約束條件62第第5題題635：二二50080070064yi是是0-1變量，變量， yi=0，相當(dāng)于該，相當(dāng)于該庫房不存在庫房不存在需求量需求量上海上海y2，武漢，武漢y40,10,01,1最多最多2個庫房個庫房武漢和廣州不能同時建武漢和廣州不能同時建i=1,2,3,4北京北京上海上海廣州廣州武漢武漢華北華北華中華中華南華南2第第6

28、題：指派問題題：指派問題（1）引入引入01變量變量 xij，并令并令 xij =1(當(dāng)指派第當(dāng)指派第i人去完成第人去完成第j項工作時項工作時) 0(當(dāng)不指派第當(dāng)不指派第i人去完成第人去完成第j項工作時項工作時)目標(biāo)函數(shù) Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x4465 x11+ x12+ x13+ x14= 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能

29、干一項工作乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干)66 （2）把目標(biāo)函數(shù)改為求最大值即可，即：）把目標(biāo)函數(shù)改為求最大值即可，即：M

30、ax Z= 20 x11+ 19x12+ 20 x13+ 28x14+18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x44約束條件不變約束條件不變67 （3）增加了一項工作增加了一項工作E，問應(yīng)指派，問應(yīng)指派四個人干四個人干哪四項工作哪四項工作，共有五項工作，則結(jié)果中肯定，共有五項工作，則結(jié)果中肯定有一項工作無人做。有一項工作無人做。 mn，人數(shù)少于任務(wù)數(shù)。此時，添加虛擬，人數(shù)少于任務(wù)數(shù)。此時，添加虛擬人數(shù)人數(shù)n-m=1個，該人是虛擬的，因此完成各個，該人是虛擬的，因此完成各項工

31、作所需的時間都設(shè)為項工作所需的時間都設(shè)為0.此時變?yōu)榇藭r變?yōu)?個人個人完成完成5項工作的問題了。項工作的問題了。Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20 x24+ 20 x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20 x42+ 24x43+ 19x44 +16x45 + 0 x51+ 0 x52+ 0 x53+ 0 x54 +0 x5568甲乙丙甲乙丙丁每個丁每個人做第人做第5項工作項工作的時間的時間 約束條件 x11+ x12+ x13+ x14 + x1

32、5 = 1 x21+ x22+ x23+ x24 + x25 = 1 x31+ x32+ x33+ x34 + x35 = 1 x41+ x42+ x43+ x44 + x45 = 1 x51+ x52+ x53+ x54 + x55 = 1 x11+ x21+ x31+ x41 + x51 =1 x12+ x22+ x32+ x42 + x52 =1 x13+ x23+ x33+ x43 + x53 = 1 x14+ x24+ x34+ x44 + x54 = 1 x15+ x25+ x35+ x45 + x55 = 169結(jié)果中安排第結(jié)果中安排第5個虛擬人去個虛擬人去做哪項工作，做哪項工作

33、，表明實際中該表明實際中該項工作無人做項工作無人做70方法二：方法二：x11+ x12+ x13+ x14 + x15 = 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24 + x25 = 1 (乙只能干一項工作乙只能干一項工作)x31+ x32+ x33+ x34 + x35 = 1 (丙只能干一項工作丙只能干一項工作)x41+ x42+ x43+ x44 + x45 = 1 (丁只能干一項工作丁只能干一項工作)x11+ x21+ x31+ x41 1 ( A工作工作)x12+ x22+ x32+ x42 1 ( B工作工作)x13+ x23+ x33+ x43

34、 1 ( C工作工作)x14+ x24+ x34+ x44 1 ( D工作工作)x15+ x25+ x35+ x45 1 ( E工作工作)Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20 x24+ 20 x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20 x42+ 24x43+ 19x44 +16x45 用用普通線性規(guī)普通線性規(guī)劃模塊劃模塊求解求解 （4）增加了一個人，問應(yīng)指派哪四個人去）增加了一個人，問應(yīng)指派哪四個人去干這四項工作，肯定有一個人沒有工作做。干這四項工作

35、，肯定有一個人沒有工作做。目標(biāo)函數(shù)目標(biāo)函數(shù) Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x44 + 16x51+ 17x52+ 20 x53+ 21x5471 方法一：虛設(shè)一個工作，每個人完成此項工方法一：虛設(shè)一個工作，每個人完成此項工作的時間設(shè)為作的時間設(shè)為0.72x11+ x12+ x13+ x14 + x15 = 1 x21+ x22+ x23+ x24 + x25 = 1x31+ x32+ x33

36、+ x34 + x35 = 1x41+ x42+ x43+ x44 + x45 = 1x51+ x52+ x53+ x54 + x55 = 1x11+ x21+ x31+ x41 + x51 =1x12+ x22+ x32+ x42 + x52 =1x13+ x23+ x33+ x43 + x53 = 1x14+ x24+ x34+ x44 + x54 = 1x15+ x25+ x35+ x45 + x55 = 1Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+0 x15 + 18x21+24x22+27x23+ 20 x24+ 0 x25+ 26x31+16x32+15x33+ 18x34+ 0 x35+ 17x41+ 20 x42+ 24x43+ 19x44 +0 x45 + 16x51+ 17x52+20 x53+ 21x54 +0 x5