第8章_整數(shù)規(guī)劃(帶答案)

1、12第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法 2 整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的計(jì)算機(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)注意：不是不是用四舍五入法用四舍五入法和和去尾法對(duì)線性規(guī)劃的非去尾法對(duì)線性規(guī)劃的非整數(shù)解加以處理就能解決的。整數(shù)解加以處理就能解決的。整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃一些基本算法的設(shè)計(jì)是一些基本算法的設(shè)計(jì)是以相應(yīng)以相應(yīng)

2、線性規(guī)劃的最優(yōu)解為出發(fā)點(diǎn)線性規(guī)劃的最優(yōu)解為出發(fā)點(diǎn)而發(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ī)劃中一個(gè)較弱的分支，目前整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃中一個(gè)較弱的分支，目前有成熟的方法解有成熟的方法解線性整數(shù)規(guī)劃問題線性整數(shù)規(guī)劃問題，而非線性，而非線性整數(shù)規(guī)劃問題，還沒有好的辦法。整數(shù)規(guī)劃問題，還

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

4、所受限制如表所示。甲種貨物至多托運(yùn)甲種貨物至多托運(yùn)4件件，問兩種貨物各托運(yùn)多，問兩種貨物各托運(yùn)多少件，可使獲得的利潤(rùn)最大。少件，可使獲得的利潤(rùn)最大。貨物貨物每件體積每件體積(立方米立方米)每件重量每件重量(百千克百千克)每件利潤(rùn)每件利潤(rùn)（百元）（百元）甲甲乙乙19527344023托運(yùn)限制托運(yùn)限制1365140 6貨物貨物每件體積每件體積(立方米立方米)每件重量每件重量(百千克百千克)每件利潤(rùn)每件利潤(rùn)（百元）（百元）甲甲乙乙19527344023托運(yùn)限制托運(yùn)限制1365140 解：設(shè)解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建分別為甲、乙兩種貨物托運(yùn)的件數(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ù)。如果去掉最后一個(gè)約束，就是一個(gè)線性規(guī)劃問題如果去掉最后一個(gè)約束，就是一個(gè)線性規(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)解（黃色叉號(hào)）為整數(shù)規(guī)劃的最優(yōu)解（黃色叉號(hào)）為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ī)劃的可行點(diǎn)數(shù)規(guī)劃的可行點(diǎn)，則對(duì)于整數(shù)規(guī)劃，易知，則對(duì)于整數(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ù)用管理運(yùn)籌學(xué)軟件用管理運(yùn)籌學(xué)軟件求解得：求解得：

8、x1 = 5 x2 = 2 x3 = 2 2 2 整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的計(jì)算機(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變量變量用用管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)軟件求軟件求解得解得: z = 16.25x1 = 4 x2 = 1.25 x3 = 1 123 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用應(yīng)用實(shí)例：應(yīng)用實(shí)例： 投資投資場(chǎng)所的選擇問題場(chǎng)所的選擇問題 背包問題背包問題

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

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

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 三個(gè)點(diǎn)三個(gè)點(diǎn)至多至多選擇選擇兩個(gè)兩個(gè)

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

13、如下表所示，請(qǐng)幫助該各區(qū)之間消防車行駛的時(shí)間如下表所示，請(qǐng)幫助該市制定一個(gè)最省的計(jì)劃。市制定一個(gè)最省的計(jì)劃。 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約束方程保證每個(gè)地區(qū)都有一個(gè)消防站在約束方程保證每個(gè)地區(qū)都有一個(gè)消防站在15分鐘行

14、程內(nèi)。分鐘行程內(nèi)。將將6個(gè)地區(qū)的條件分別列出：個(gè)地區(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個(gè)地區(qū)建一個(gè)（地區(qū)個(gè)地區(qū)建一個(gè)（地區(qū)1、2、6都解決了）都解決了）第第4個(gè)地區(qū)建一個(gè)（地區(qū)個(gè)地區(qū)建一個(gè)（地區(qū)3、4、5都解決了）都解決了）二、二、背包問題背包問題（補(bǔ)充）（補(bǔ)充）背包可裝入背包可裝入8單位重量，單位重量，10單位體積物品。若單位體積物品。若背包中背包中每件物品至多只能裝一個(gè)每件物品至多只能裝一個(gè)，怎樣才能使背包，怎樣才能使背包裝的物品價(jià)值最高。裝的物品價(jià)值最高。物品物品 名稱名稱 重量重量 體積體積 價(jià)值價(jià)值 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物品物品 名稱名稱 重量重量 體積體積 價(jià)值價(jià)值 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 物品重要性估價(jià)物品重要性估價(jià)223 3 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用三、固定成本問題三、固定成本問題 例例5高壓容器公司制造小、中、大三種尺寸的金屬高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的用，每種容器售出一只

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

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

20、：不投入固定費(fèi)用，是不定費(fèi)用，是不能投入生產(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為一個(gè)充分大的數(shù)

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

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

23、作時(shí)項(xiàng)工作時(shí))或或0(當(dāng)不指當(dāng)不指派第派第i人去完成第人去完成第j項(xiàng)工作時(shí)項(xiàng)工作時(shí))這可以表示為一個(gè)這可以表示為一個(gè)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 (甲只能干一項(xiàng)工作甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作乙只能干一項(xiàng)工作) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作丁只能干一項(xiàng)工作) 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)用每人只每人只能干一能干一項(xiàng)工作項(xiàng)工作一項(xiàng)工一項(xiàng)工作只能作只能由一個(gè)由一個(gè)人干人干 對(duì)于有對(duì)于有m個(gè)人完成個(gè)人完成n項(xiàng)任務(wù)的一般指派問題，項(xiàng)任務(wù)的一般指派問題，設(shè)：設(shè)：29變量為1-0,.,2, 1, 1,.,2, 1, 1min1111ijmiijnjijminjijijxnjxmixxCZm不一定等于不一定等于n，當(dāng)當(dāng)mn時(shí)，有的時(shí)，有的人沒有任務(wù)。人沒有任務(wù)。第第i個(gè)人完成的任務(wù)個(gè)人完成的任務(wù)且最多承擔(dān)一項(xiàng)

26、且最多承擔(dān)一項(xiàng)第第j項(xiàng)工作正好有一項(xiàng)工作正好有一人承擔(dān)人承擔(dān)注意：當(dāng)注意：當(dāng)m0 yi=0時(shí)，當(dāng)不利用第時(shí)，當(dāng)不利用第i種設(shè)備生產(chǎn)時(shí)，此時(shí)相應(yīng)種設(shè)備生產(chǎn)時(shí)，此時(shí)相應(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時(shí)，時(shí)，Xi=0.(沒有準(zhǔn)備費(fèi)就不啟沒有準(zhǔn)備費(fèi)就不啟用該設(shè)備用該設(shè)備)，引入一個(gè)很大的，引入一個(gè)很大的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個(gè)庫房個(gè)庫房武漢和廣州不能同時(shí)建武漢和廣州不能同時(shí)建i=1,2,3,4北京北京上海上海廣州廣州武漢武漢華北華北華中華中華南華南2第第6

28、題：指派問題題：指派問題（1）引入引入01變量變量 xij，并令并令 xij =1(當(dāng)指派第當(dāng)指派第i人去完成第人去完成第j項(xiàng)工作時(shí)項(xiàng)工作時(shí)) 0(當(dāng)不指派第當(dāng)不指派第i人去完成第人去完成第j項(xiàng)工作時(shí)項(xiàng)工作時(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+ 19x4465 x11+ x12+ x13+ x14= 1 (甲只能干一項(xiàng)工作甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24= 1 (乙只能

29、干一項(xiàng)工作乙只能干一項(xiàng)工作) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作丁只能干一項(xiàng)工作) 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）增加了一項(xiàng)工作增加了一項(xiàng)工作E，問應(yīng)指派，問應(yīng)指派四個(gè)人干四個(gè)人干哪四項(xiàng)工作哪四項(xiàng)工作，共有五項(xiàng)工作，則結(jié)果中肯定，共有五項(xiàng)工作，則結(jié)果中肯定有一項(xiàng)工作無人做。有一項(xiàng)工作無人做。 mn，人數(shù)少于任務(wù)數(shù)。此時(shí)，添加虛擬，人數(shù)少于任務(wù)數(shù)。此時(shí)，添加虛擬人數(shù)人數(shù)n-m=1個(gè)，該人是虛擬的，因此完成各個(gè)，該人是虛擬的，因此完成各項(xiàng)工

31、作所需的時(shí)間都設(shè)為項(xiàng)工作所需的時(shí)間都設(shè)為0.此時(shí)變?yōu)榇藭r(shí)變?yōu)?個(gè)人個(gè)人完成完成5項(xiàng)工作的問題了。項(xiàng)工作的問題了。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甲乙丙甲乙丙丁每個(gè)丁每個(gè)人做第人做第5項(xiàng)工作項(xiàng)工作的時(shí)間的時(shí)間 約束條件 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個(gè)虛擬人去個(gè)虛擬人去做哪項(xiàng)工作，做哪項(xiàng)工作

33、，表明實(shí)際中該表明實(shí)際中該項(xiàng)工作無人做項(xiàng)工作無人做70方法二：方法二：x11+ x12+ x13+ x14 + x15 = 1 (甲只能干一項(xiàng)工作甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24 + x25 = 1 (乙只能干一項(xiàng)工作乙只能干一項(xiàng)工作)x31+ x32+ x33+ x34 + x35 = 1 (丙只能干一項(xiàng)工作丙只能干一項(xiàng)工作)x41+ x42+ x43+ x44 + x45 = 1 (丁只能干一項(xiàng)工作丁只能干一項(xiàng)工作)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）增加了一個(gè)人，問應(yīng)指派哪四個(gè)人去）增加了一個(gè)人，問應(yīng)指派哪四個(gè)人去干這四項(xiàng)工作，肯定有一個(gè)人沒有工作做。干這四項(xiàng)工作

35、，肯定有一個(gè)人沒有工作做。目標(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è)一個(gè)工作，每個(gè)人完成此項(xiàng)工方法一：虛設(shè)一個(gè)工作，每個(gè)人完成此項(xiàng)工作的時(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