第五章整數(shù)規(guī)劃(第7講)

1、 第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃 Optimizing Methods第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1 整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法3 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃 在在 LP 問(wèn)題的討論中，有些最優(yōu)解是小數(shù)問(wèn)題的討論中，有些最優(yōu)解是小數(shù) . 但對(duì)但對(duì)于某些具體問(wèn)題常有要求最優(yōu)解是整數(shù)于某些具體問(wèn)題常有要求最優(yōu)解是整數(shù)( 即整數(shù)解即整數(shù)解) . 如決策變量為機(jī)器的臺(tái)數(shù)、人數(shù)、車(chē)輛數(shù)如決策變量為機(jī)器的臺(tái)數(shù)、人數(shù)、車(chē)輛數(shù) etc. 如果在問(wèn)題中所有決策變量有整數(shù)限制，稱為如果在問(wèn)題中所有決策變量有整數(shù)限制，稱

2、為 純純整數(shù)規(guī)劃整數(shù)規(guī)劃( Pure IP ) 或或 全整數(shù)規(guī)劃全整數(shù)規(guī)劃 ( All IP )； 如果在問(wèn)題中僅部分決策變量有整數(shù)限制，稱為如果在問(wèn)題中僅部分決策變量有整數(shù)限制，稱為 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃( Mixed IP ) ； 如果在問(wèn)題中決策變量?jī)H取如果在問(wèn)題中決策變量?jī)H取 0 、1，稱為，稱為 0-1 (整整數(shù)數(shù)) 規(guī)劃規(guī)劃 .Integer Programming1 整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型1 整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型 貨貨 物物每箱體積每箱體積（m3）每箱重量每箱重量（kg）每箱利潤(rùn)每箱利潤(rùn)（百元）（百元） 甲甲5220 乙乙

3、4510托運(yùn)限制托運(yùn)限制2413Example 1 （裝載問(wèn)題）（裝載問(wèn)題） 某廠擬用集裝箱托運(yùn)甲、乙某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)及托運(yùn)限制兩種貨物，每箱的體積、重量、可獲利潤(rùn)及托運(yùn)限制如表，問(wèn)兩種貨物各托如表，問(wèn)兩種貨物各托運(yùn)幾箱，可獲利潤(rùn)最大？運(yùn)幾箱，可獲利潤(rùn)最大？Solution: 設(shè)設(shè) x1、x2 分分別為甲、乙兩種貨物托別為甲、乙兩種貨物托運(yùn)箱數(shù)運(yùn)箱數(shù).則1212121212max2010. . 54242513,0,Zxxstxxxxx xx xI這是一個(gè)這是一個(gè) Pure IP 問(wèn)題問(wèn)題.第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1232yyy1231 3ii

4、iixxxaiExample 2 （工廠選址問(wèn)題）（工廠選址問(wèn)題）10iy 現(xiàn)準(zhǔn)備從現(xiàn)準(zhǔn)備從 A1、A2、A3 三個(gè)地點(diǎn)中選擇兩個(gè)開(kāi)設(shè)工廠，工廠建成后它每月的三個(gè)地點(diǎn)中選擇兩個(gè)開(kāi)設(shè)工廠，工廠建成后它每月的產(chǎn)量產(chǎn)量 ai (i =1,2,3)、三個(gè)客戶、三個(gè)客戶 B1、B2、B3 每月的需求量每月的需求量 bj (j =1,2,3) 及及 Ai 至客戶至客戶 Bj 的單位運(yùn)價(jià)的單位運(yùn)價(jià) cij 見(jiàn)表見(jiàn)表. BjAiB1B2B3aiA145370A223480A364590bj406045 已知三已知三工廠每月的經(jīng)營(yíng)費(fèi)用工廠每月的經(jīng)營(yíng)費(fèi)用 di (與與產(chǎn)量無(wú)關(guān)產(chǎn)量無(wú)關(guān))分別為分別為 100、90、

5、120 .問(wèn)如問(wèn)如何選址使每月經(jīng)營(yíng)和運(yùn)輸費(fèi)用最低何選址使每月經(jīng)營(yíng)和運(yùn)輸費(fèi)用最低 .Solution:因?yàn)橹挥腥齻€(gè)廠址選兩個(gè)，因?yàn)橹挥腥齻€(gè)廠址選兩個(gè)， ，所以簡(jiǎn)單的方法，所以簡(jiǎn)單的方法是任取兩個(gè)廠用運(yùn)輸問(wèn)題求解，再加上每月的經(jīng)營(yíng)是任取兩個(gè)廠用運(yùn)輸問(wèn)題求解，再加上每月的經(jīng)營(yíng)費(fèi)用比較即可費(fèi)用比較即可.233C 設(shè)設(shè)選地點(diǎn)選地點(diǎn) Ai 開(kāi)設(shè)工廠開(kāi)設(shè)工廠否則否則 i = 1,2,3 ； xij 為為Ai 開(kāi)設(shè)工廠時(shí)，從開(kāi)設(shè)工廠時(shí)，從 Ai 至至 Bj 的運(yùn)量的運(yùn)量ijijiiZc xd y1231 3jjjjxxxbj顯然顯然如果如果 Ai 處開(kāi)設(shè)工廠，處開(kāi)設(shè)工廠，則運(yùn)量滿足：則運(yùn)量滿足：不開(kāi)設(shè)呢？不開(kāi)

6、設(shè)呢？1231 3iiiiixxxa yi客戶端需求滿足：客戶端需求滿足：目標(biāo)（每月的費(fèi)用）：目標(biāo)（每月的費(fèi)用）：111213212223313233123111213121222323132333112131122232132333123min4532344510090120. .70809040604520,01,1,2,3ijiZxxxxxxxxxyyystxxxyxxxyxxxyxxxxxxxxxyyyxyori j這是一個(gè)這是一個(gè) Mixed IP 問(wèn)題問(wèn)題.可用于設(shè)計(jì)分配系統(tǒng)、新生活小區(qū)的設(shè)置可用于設(shè)計(jì)分配系統(tǒng)、新生活小區(qū)的設(shè)置 etc.1 整數(shù)規(guī)劃問(wèn)整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型題及其

7、數(shù)學(xué)模型1niiyj123123256180 ,437240 xxxxxx 在在 Ex.2 中，引進(jìn)中，引進(jìn) 01 變量給出了在變量給出了在 n 件任務(wù)中件任務(wù)中,選擇選擇 j 項(xiàng)的約束項(xiàng)的約束1mijiijxa y又用又用 來(lái)刻畫(huà)不設(shè)來(lái)刻畫(huà)不設(shè)第第 i 項(xiàng)任務(wù)，則項(xiàng)任務(wù)，則 xij j = 1n 都不起作用，為零都不起作用，為零.可應(yīng)用于選擇性可應(yīng)用于選擇性約束條件中約束條件中 某工廠生產(chǎn)第某工廠生產(chǎn)第 j 種產(chǎn)品的數(shù)量為種產(chǎn)品的數(shù)量為 xj ( j =1,2,3) 其使其使用的材料在甲、乙中選擇一種，其消耗約束分別為：用的材料在甲、乙中選擇一種，其消耗約束分別為：其他資源約束條其他資源約束

8、條件未列出件未列出引進(jìn)引進(jìn) 01 變量變量 y 11nijjija xbip01y選擇材料甲選擇材料甲選擇材料乙選擇材料乙123123256180,437240(1)xxxMyxxxMyM 為充分大的為充分大的正數(shù)正數(shù)一般地，假定要在一般地，假定要在 p個(gè)約束條件個(gè)約束條件 中中至少要選擇至少要選擇 q 個(gè)約束條件得到滿足，可引進(jìn)個(gè)約束條件得到滿足，可引進(jìn)0-1變量變量 y11101.nijjiijpiiia xbMyipypqyor第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃71maxjjjZc x71. .3501,1 7jjjjsta xxorjExample 3 （背包問(wèn)題）（背包問(wèn)題） 假設(shè)有人要

9、出發(fā)旅行，考慮帶七假設(shè)有人要出發(fā)旅行，考慮帶七種物品，每件物品的重量與價(jià)值如表種物品，每件物品的重量與價(jià)值如表. 現(xiàn)在假設(shè)他最多帶現(xiàn)在假設(shè)他最多帶 35kg 物品，問(wèn)該帶物品，問(wèn)該帶哪幾件物品使總價(jià)值最大？哪幾件物品使總價(jià)值最大？ 物品物品重量重量 aj價(jià)值價(jià)值 cj 1 3 12 2 4 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112Solution:10jx如果帶第如果帶第 j 件物品件物品否則否則 j = 17這是一個(gè)這是一個(gè) 0-1 規(guī)劃問(wèn)題規(guī)劃問(wèn)題. 一般整數(shù)規(guī)劃中的變量一般整數(shù)規(guī)劃中的變量 x , 也可用也可用 0-1 變量替代，如變量替代，如0

10、x15 ，x=x020+x121+x222+x323 其中其中 x0,x1,x2,x3 為為0-1 變量變量 .1 整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型整數(shù)規(guī)劃問(wèn)題及其數(shù)學(xué)模型125424xx12121212max2010. . 54242513,0,Zxxstxxxxx x 參見(jiàn)參見(jiàn) Ex.1, 去掉整數(shù)約束，得去掉整數(shù)約束，得舍入化整舍入化整o 1 2 3 4 5 x14321x2122513xx由圖解法得最優(yōu)由圖解法得最優(yōu)解為：解為：x1= 4.8, x2= 0 Zmax = 96顯然，顯然，x1 不是整數(shù)不是整數(shù). 是否可以根據(jù)化整的原問(wèn)題的解？是否可以根據(jù)化整的原問(wèn)題的解？x1=5、x2=0 不

11、是可行解，不是可行解， x1=4、x2=0 Z=80 . 但是但是 x1=4、x2=1 也可行也可行 且且 Z=90 .所以，所以，“舍入化整舍入化整”的結(jié)果：的結(jié)果： 1、化整后未必可行；、化整后未必可行；2、即使是可行解，也未必是最優(yōu)解；、即使是可行解，也未必是最優(yōu)解；3、用這個(gè)方法即使能得到最優(yōu)解，但如果有、用這個(gè)方法即使能得到最優(yōu)解，但如果有n 個(gè)變個(gè)變 量，則取舍方案有量，則取舍方案有 2n 種，計(jì)算量也是很大的種，計(jì)算量也是很大的.Go back第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃125424xxo 1 2 3 4 5 x14321x2122513xx 有人在研究在建立模型中，什么條件下

12、有人在研究在建立模型中，什么條件下 LP 問(wèn)題的問(wèn)題的解一定是整數(shù)解？解一定是整數(shù)解？ 如：如： 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題從從 Ex.1 的討論，可得到一些啟迪的討論，可得到一些啟迪1、是否能在是否能在 LP 的約束區(qū)域中的約束區(qū)域中, 切切去去 n 塊不含整數(shù)解的可行域使整數(shù)塊不含整數(shù)解的可行域使整數(shù)解作為頂點(diǎn)，則解作為頂點(diǎn)，則 LP 的最優(yōu)解即為的最優(yōu)解即為整數(shù)解整數(shù)解 ；如增加約束如增加約束 x14, 則則 LP 問(wèn)題的解即為整數(shù)解問(wèn)題的解即為整數(shù)解;2、在在 LP 的可行域中，整數(shù)點(diǎn)不多，的可行域中，整數(shù)點(diǎn)不多，（12個(gè)）個(gè)）是否可以用窮舉法是否可以用窮舉法.2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法一

13、、割平面法一、割平面法 1959年由年由 R.E.Gomory 首先提出，從此使首先提出，從此使 IP 逐漸逐漸形成為一個(gè)獨(dú)立的運(yùn)籌學(xué)分支形成為一個(gè)獨(dú)立的運(yùn)籌學(xué)分支. 割平面法的實(shí)質(zhì)割平面法的實(shí)質(zhì)是用解是用解 LP 問(wèn)題的方法求解問(wèn)題的方法求解 IP 問(wèn)題；問(wèn)題；割平面法的割平面法的基本思想基本思想是通過(guò)對(duì)是通過(guò)對(duì) LP 問(wèn)題的求解，如果最問(wèn)題的求解，如果最優(yōu)解是整數(shù)解，則就是優(yōu)解是整數(shù)解，則就是 IP 的解；否則設(shè)法對(duì)的解；否則設(shè)法對(duì) LP 問(wèn)題問(wèn)題增加約束增加約束(割平面割平面)，把，把 LP 問(wèn)題的可行域中去掉一部分問(wèn)題的可行域中去掉一部分不含整數(shù)解的，再求不含整數(shù)解的，再求 LP 問(wèn)題

14、，反復(fù)進(jìn)行問(wèn)題，反復(fù)進(jìn)行 .割平面法的割平面法的關(guān)鍵關(guān)鍵在于如何尋找適當(dāng)?shù)那懈罴s束條件在于如何尋找適當(dāng)?shù)那懈罴s束條件. 用割平面法求解用割平面法求解 IP 問(wèn)題常常會(huì)計(jì)算量大、收斂速度問(wèn)題常常會(huì)計(jì)算量大、收斂速度慢的情況，但在理論上是重要的，被認(rèn)為是慢的情況，但在理論上是重要的，被認(rèn)為是 IP 的核心的核心.第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃二、分支定界法二、分支定界法分支與定界分支與定界法的基本思想是對(duì)有約束條件的最優(yōu)化問(wèn)法的基本思想是對(duì)有約束條件的最優(yōu)化問(wèn)題的所有可行解（其數(shù)目為有限集）空間適當(dāng)?shù)剡M(jìn)行題的所有可行解（其數(shù)目為有限集）空間適當(dāng)?shù)剡M(jìn)行搜索搜索 . 具體執(zhí)行時(shí)，把可行解空間不斷分割為

15、越來(lái)越小具體執(zhí)行時(shí)，把可行解空間不斷分割為越來(lái)越小的子集（稱為分支），并確定每個(gè)分支內(nèi)的解值的下的子集（稱為分支），并確定每個(gè)分支內(nèi)的解值的下界或上界（稱為定界）界或上界（稱為定界）. . 在每次分支后，對(duì)凡是界超在每次分支后，對(duì)凡是界超出已知可行解值的子集被剪去，從而不斷縮小搜索范出已知可行解值的子集被剪去，從而不斷縮小搜索范圍圍. . 這個(gè)過(guò)程一直進(jìn)行到找出最優(yōu)解為止，該可行解這個(gè)過(guò)程一直進(jìn)行到找出最優(yōu)解為止，該可行解的值不大于或不小于任何子集的界的值不大于或不小于任何子集的界 .優(yōu)點(diǎn)：優(yōu)點(diǎn)：1、適用面廣、適用面廣 2、可檢查較少的解（運(yùn)、可檢查較少的解（運(yùn)氣好）氣好）3、可獲得最優(yōu)解、可

16、獲得最優(yōu)解缺點(diǎn)：本質(zhì)是窮缺點(diǎn)：本質(zhì)是窮舉，復(fù)雜性大于窮舉法舉，復(fù)雜性大于窮舉法2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法設(shè)設(shè)min( )(1)x Af xmin( )(2)x Bf xAB如果如果 則稱問(wèn)題（則稱問(wèn)題（2）是問(wèn)題（）是問(wèn)題（1）的松弛問(wèn)題）的松弛問(wèn)題. .Note : 1、松弛問(wèn)題未必比原問(wèn)題難解；、松弛問(wèn)題未必比原問(wèn)題難解；如：如：整數(shù)規(guī)劃與線性規(guī)劃；整數(shù)規(guī)劃與線性規(guī)劃；TSP 與指派問(wèn)題與指派問(wèn)題 etc. 如：如： A：尋找全國(guó)：尋找全國(guó)18 歲百米最快的運(yùn)動(dòng)員歲百米最快的運(yùn)動(dòng)員.B：尋找：尋找全國(guó)所有百米最快的運(yùn)動(dòng)員全國(guó)所有百米最快的運(yùn)動(dòng)員. .顯然，顯然，B 問(wèn)題是問(wèn)題是 A

17、問(wèn)題的松弛問(wèn)題，且問(wèn)題的松弛問(wèn)題，且B 問(wèn)題更易解問(wèn)題更易解 .2、如果松弛問(wèn)題易解，則先解松弛問(wèn)題是有益的如果松弛問(wèn)題易解，則先解松弛問(wèn)題是有益的 .1）設(shè)設(shè) x0 是松弛問(wèn)題的最優(yōu)解，且是松弛問(wèn)題的最優(yōu)解，且 則原問(wèn)題已解則原問(wèn)題已解0 xA0 xA2）即使即使 給出了原問(wèn)題最優(yōu)值的界給出了原問(wèn)題最優(yōu)值的界 f(x0) .x0BABAx0第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃分枝與定界法為什么能少檢查一些解？分枝與定界法為什么能少檢查一些解？B10sB1B210.2s*10sB3B410.3s*幾點(diǎn)注意：幾點(diǎn)注意：確定問(wèn)題（子問(wèn)題）的最優(yōu)值的確定問(wèn)題（子問(wèn)題）的最優(yōu)值的界界 通常是通過(guò)求解松弛問(wèn)題

18、，通常是通過(guò)求解松弛問(wèn)題，用松弛問(wèn)題的解作為界，也可用松弛問(wèn)題的解作為界，也可以用啟發(fā)式算法得到以用啟發(fā)式算法得到 .Note 松弛問(wèn)題選擇的松弛問(wèn)題選擇的原則原則、松弛問(wèn)題要與原問(wèn)題的、松弛問(wèn)題要與原問(wèn)題的 最優(yōu)值盡量接近；最優(yōu)值盡量接近；松弛問(wèn)題要盡量容易解松弛問(wèn)題要盡量容易解 . .這兩個(gè)原則不易統(tǒng)一，所以可選擇不同的松弛問(wèn)題這兩個(gè)原則不易統(tǒng)一，所以可選擇不同的松弛問(wèn)題2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法劃分方法的選擇劃分方法的選擇原則是希望分出來(lái)的子問(wèn)題容易被查清，可加快計(jì)算原則是希望分出來(lái)的子問(wèn)題容易被查清，可加快計(jì)算.選哪個(gè)活問(wèn)題先檢查選哪個(gè)活問(wèn)題先檢查先檢查最大上界（極大化問(wèn)題）的活

19、問(wèn)題先檢查最大上界（極大化問(wèn)題）的活問(wèn)題優(yōu)點(diǎn)：優(yōu)點(diǎn)：檢查子問(wèn)題較其他規(guī)則為少；檢查子問(wèn)題較其他規(guī)則為少；缺點(diǎn)：缺點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較大計(jì)算機(jī)儲(chǔ)存量較大先檢查最新產(chǎn)生的最大上界的活問(wèn)題先檢查最新產(chǎn)生的最大上界的活問(wèn)題優(yōu)點(diǎn)：優(yōu)點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較少計(jì)算機(jī)儲(chǔ)存量較少 ；缺點(diǎn)：缺點(diǎn)：需要更多的分支運(yùn)算需要更多的分支運(yùn)算選擇的不同，提供了發(fā)揮的余地選擇的不同，提供了發(fā)揮的余地 分枝與定界法的重要在于它提出了一類(lèi)新的思分枝與定界法的重要在于它提出了一類(lèi)新的思路（隱枚舉法），使得許多原來(lái)不好解決的問(wèn)題有路（隱枚舉法），使得許多原來(lái)不好解決的問(wèn)題有了解決的可能性了解決的可能性. （具有普適性）（具有普適性）第五章

20、第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1212121212max58. .65945,0,Zxxstxxxxx xx xI125945xxExample 4 用分支定界法求解如右用分支定界法求解如右 IP 問(wèn)題問(wèn)題12121212max58. .65945,0,Zxxstxxxxx x126xxSolution:解松弛問(wèn)題解松弛問(wèn)題 P0得：得：x1=2.25、x2=3.75 Zmax=41.25去掉整數(shù)約束為去掉整數(shù)約束為原原問(wèn)題的松弛問(wèn)題問(wèn)題的松弛問(wèn)題41.25是原問(wèn)題最優(yōu)值的上界是原問(wèn)題最優(yōu)值的上界進(jìn)行分支，任選一個(gè)不是整數(shù)的變量進(jìn)行分支，任選一個(gè)不是整數(shù)的變量,如取如取 x2 則可認(rèn)為則可認(rèn)為最優(yōu)解

21、最優(yōu)解 x24 或或 x23 . 原問(wèn)題分為兩個(gè)子問(wèn)題原問(wèn)題分為兩個(gè)子問(wèn)題 . 3x24 之間無(wú)整數(shù)解之間無(wú)整數(shù)解0 1 2 3 4 5 6 7 8 9 x1x254321P1P2再分別求解兩個(gè)松弛問(wèn)題再分別求解兩個(gè)松弛問(wèn)題 P1、P2P0 x1=2.25x2=3.75Z0=41.25P1(x23)P2（x24）x1=3、x2=3Z1=39*x1=1.8、x2=4Z2=41P3（x12）P4 (x11)不可行不可行*x1=1、x2=40/9Z4=365/9P5（x24）P6 (x25)x1=1、x2=4 Z5=37*x1=0、x2=5 Z6=40* 此時(shí)已沒(méi)有活問(wèn)題，所以最此時(shí)已沒(méi)有活問(wèn)題，所

22、以最優(yōu)解為優(yōu)解為 x1=0、x2=5 Zmax=40 .2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法1232312313123max20816. .42552743753601,1 3jZxxxstxxxxxxxxxxxorjExample 5 （投資方案的最優(yōu)選擇）（投資方案的最優(yōu)選擇） 背包問(wèn)題可以看成為一個(gè)一次性的投資問(wèn)題，簡(jiǎn)背包問(wèn)題可以看成為一個(gè)一次性的投資問(wèn)題，簡(jiǎn)單的擴(kuò)展：?jiǎn)蔚臄U(kuò)展：1、分幾次投資；、分幾次投資；2、雖然一次性投資，但、雖然一次性投資，但不同的項(xiàng)目有一些政策上的限制不同的項(xiàng)目有一些政策上的限制 etc. 某公司欲對(duì)三個(gè)項(xiàng)目進(jìn)行投資，某公司欲對(duì)三個(gè)項(xiàng)目進(jìn)行投資，根據(jù)預(yù)算四年內(nèi)的投資

23、額、三個(gè)項(xiàng)目根據(jù)預(yù)算四年內(nèi)的投資額、三個(gè)項(xiàng)目每年所需投資額以及所創(chuàng)利潤(rùn)如表每年所需投資額以及所創(chuàng)利潤(rùn)如表. 問(wèn)應(yīng)對(duì)哪幾個(gè)項(xiàng)目進(jìn)行投資，可獲利最大？問(wèn)應(yīng)對(duì)哪幾個(gè)項(xiàng)目進(jìn)行投資，可獲利最大？投資投資年度年度項(xiàng)目項(xiàng)目投資投資額度額度A1A2A310425251273403745136回報(bào)回報(bào)利潤(rùn)利潤(rùn)20816Solution:10jx如果對(duì)項(xiàng)目如果對(duì)項(xiàng)目Aj 投資投資否則否則 j = 13設(shè)設(shè) 對(duì)于對(duì)于0-1 規(guī)劃的求解，首先會(huì)規(guī)劃的求解，首先會(huì)想到枚舉法，但變量取想到枚舉法，但變量取0、1的所的所有組合有有組合有 2n . 是否能設(shè)計(jì)一些方是否能設(shè)計(jì)一些方法，只檢查所有組合的一部分就法，只檢查所有組

24、合的一部分就求得最優(yōu)解，即隱枚舉法求得最優(yōu)解，即隱枚舉法.分支定界法是分支定界法是一種隱枚舉一種隱枚舉.給出一個(gè)重要思想給出一個(gè)重要思想:設(shè)門(mén)檻設(shè)門(mén)檻 (1、可行性、可行性2、目標(biāo)函數(shù)值、目標(biāo)函數(shù)值)第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1232312313123max20816. .42552743753601,1 3jZxxxstxxxxxxxxxxxorj(x1 x2 x3)約束條件約束條件Z值值(0 0 0)(0 0 1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1)01682028(x1 x2 x3)約約 束束 條條 件件Z值值(0 0 0) (0 0

25、1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1) 增加一個(gè)判別增加一個(gè)判別 A , 目標(biāo)函目標(biāo)函 數(shù)值小于已知可行解的值，數(shù)值小于已知可行解的值， 則不必繼續(xù)計(jì)算則不必繼續(xù)計(jì)算 .A 0162028可以改進(jìn)嗎？可以改進(jìn)嗎？(x2 x3 x1)約約 束束 條條 件件Z值值(0 0 0)(0 0 1)(0 1 0)(0 1 1)(1 0 0)(1 0 1)(1 1 0)(1 1 1)A 02028還有想法嗎？還有想法嗎？Go back第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃Example 6 （人員時(shí)間安排問(wèn)題）（人員時(shí)間安排問(wèn)題） 為了盡可能有效地利用勞動(dòng)力，有必要

26、對(duì)一天各為了盡可能有效地利用勞動(dòng)力，有必要對(duì)一天各個(gè)不同時(shí)刻需要人員的情況作一分析，特別是在一些個(gè)不同時(shí)刻需要人員的情況作一分析，特別是在一些大型服務(wù)性機(jī)構(gòu)中，顧客的需要是重復(fù)性的，但不同大型服務(wù)性機(jī)構(gòu)中，顧客的需要是重復(fù)性的，但不同時(shí)刻之間需要的服務(wù)量是有顯著差別的時(shí)刻之間需要的服務(wù)量是有顯著差別的. 如：電話接如：電話接線員、公交乘務(wù)員、護(hù)士等較長(zhǎng)時(shí)間的服務(wù)機(jī)構(gòu)，因線員、公交乘務(wù)員、護(hù)士等較長(zhǎng)時(shí)間的服務(wù)機(jī)構(gòu)，因而合理安排可提高效率，減少雇員而合理安排可提高效率，減少雇員. 如下是某航空公如下是某航空公司的售票員人數(shù)問(wèn)題，假設(shè)每日工作司的售票員人數(shù)問(wèn)題，假設(shè)每日工作 8 小時(shí)且連續(xù)工小時(shí)且連

27、續(xù)工作，由統(tǒng)計(jì)資料得各時(shí)段需要的最少人數(shù)作，由統(tǒng)計(jì)資料得各時(shí)段需要的最少人數(shù) . 問(wèn)該公司問(wèn)該公司最少需雇傭多少售票員？最少需雇傭多少售票員？12345123451234512345. .10138895113013,1 5jstxxxxxxxxxxxxxxxxxxxxxj51minjjZx時(shí)段時(shí)段始末時(shí)間始末時(shí)間至少需要至少需要的售票員數(shù)的售票員數(shù)108：0010：0010210：0012：008312：0014：009414：0016：0011516：0018：0013618：0020：008720：0022：005822：0024：0033 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例Solut

28、ion: 由表中情況可知，只由表中情況可知，只需考慮時(shí)段需考慮時(shí)段15的上班人數(shù)即可的上班人數(shù)即可.因?yàn)橐驗(yàn)?、9點(diǎn)、點(diǎn)、11點(diǎn)等上班人數(shù)不點(diǎn)等上班人數(shù)不影響需要人數(shù)；影響需要人數(shù)；2、時(shí)段時(shí)段 5 以后以后上班的人員工作時(shí)間不到上班的人員工作時(shí)間不到8小時(shí)小時(shí). 設(shè)設(shè) xj 表示第表示第 j 個(gè)時(shí)段開(kāi)始工作的人數(shù)，個(gè)時(shí)段開(kāi)始工作的人數(shù)，j =15 .可用可用0-1規(guī)劃表示規(guī)劃表示 進(jìn)一步討論進(jìn)一步討論, 售售票員的吃飯時(shí)間、票員的吃飯時(shí)間、工資等工資等.第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃各班工作時(shí)間及工資：各班工作時(shí)間及工資：班次班次上班時(shí)間上班時(shí)間休息時(shí)間休息時(shí)間月工資月工資108：0017：

29、0011：3012：30800208：0017：0012：0013：00800308：0017：0012：3013：30800412：0021：0015：3016：30850512：0021：0016：0017：00850612：0021：0016：3017：30850715：0024：0018：3019：30900815：0024：0019：0020：00900915：0024：0019：3020：30900時(shí)段時(shí)段所需所需售票售票員數(shù)員數(shù)班班 次次12345678901（08：0011：30）1011100000002（11：3012：00）601100000003（12：0012：30）

30、900111100004（12：3013：00）910011100005（13：0013：30）911011100006（13：3015：00）1111111100007（15：0015：30）1111111111108（15：3016：00）1111101111109（16：0016：30）1211100111110（16：3017：00）1311110011111（17：0017：30）1400011011112（17：3018：30）1500011111113（18：3019：00）800011101114（19：0019：30）800011100115（19：3020：00）80001

31、1110016（20：0020：30）500011111017（20：3021：00）500011111118（21：0024：00）3000000111設(shè)設(shè) xj (j=19)為第為第 j 班次的上班人數(shù)班次的上班人數(shù).min Z = 800(x1+x2+x3)+850(x4+x5 +x6)+900(x7+x8+x9)s.t.x1+x2+x310 x2+x36共共18個(gè)約束條件個(gè)約束條件 .3 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例Example 7 （裝配線平衡問(wèn)題）（裝配線平衡問(wèn)題） 若某工廠的產(chǎn)品裝配若某工廠的產(chǎn)品裝配線由線由 6 道工序組成，各工序的加工時(shí)間及緊前工序見(jiàn)表道工序組成，各

32、工序的加工時(shí)間及緊前工序見(jiàn)表:工序工序加工時(shí)間加工時(shí)間(分分)緊前工序緊前工序1325322461，3582634 若這條裝配線設(shè)若干個(gè)工作站，若這條裝配線設(shè)若干個(gè)工作站，被裝配的產(chǎn)品在這些編了號(hào)的工作站被裝配的產(chǎn)品在這些編了號(hào)的工作站上流水移動(dòng)時(shí)，每個(gè)工作站都要完成上流水移動(dòng)時(shí)，每個(gè)工作站都要完成一道或幾道工序，假設(shè)每個(gè)工作站加一道或幾道工序，假設(shè)每個(gè)工作站加工被裝配的產(chǎn)品時(shí)至多耗時(shí)工被裝配的產(chǎn)品時(shí)至多耗時(shí) 10分鐘分鐘 .問(wèn)最少應(yīng)設(shè)幾個(gè)工作站，每個(gè)工作站完成哪些工序問(wèn)最少應(yīng)設(shè)幾個(gè)工作站，每個(gè)工作站完成哪些工序?流水節(jié)拍流水節(jié)拍Solution: 顯然，需要的工作站不會(huì)多于顯然，需要的工作站

33、不會(huì)多于 4 個(gè)個(gè).設(shè)設(shè)10jw在裝配線上有工作站在裝配線上有工作站 j否則否則 j = 1410ijx工序工序i 在工作站在工作站 j上進(jìn)行上進(jìn)行否則否則 i = 16; j = 14第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃目標(biāo)：目標(biāo)： min Z = w1 + w2 + w3 + w4對(duì)工序?qū)ば?i , 它應(yīng)恰在某一工作站上它應(yīng)恰在某一工作站上完成，即完成，即 xi1 + xi2 + xi3 + xi4 = 1 i = 16 對(duì)工作站對(duì)工作站 j ，如果設(shè)立則在該工作站上完成的各道工，如果設(shè)立則在該工作站上完成的各道工序所需的時(shí)間總和不超過(guò)序所需的時(shí)間總和不超過(guò) 10 分鐘，即分鐘，即3x1j +

34、 5x2j + 2x3j + 6x4j + 8x5j + 3x6j 10 j = 143x1j + 5x2j + 2x3j + 6x4j + 8x5j + 3x6j 10wj如果不設(shè)立，則不能將任何工序分配給該工作站，即如果不設(shè)立，則不能將任何工序分配給該工作站，即 wj = 0 則則 xij = 0 i = 16 所以，上式改為所以，上式改為3 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例工序工序加工時(shí)間加工時(shí)間(分分)緊前工序緊前工序1325322461，3582634 對(duì)于緊前約束，如工序?qū)τ诰o前約束，如工序 2 必須在必須在工序工序 3 之前完成，如果工序之前完成，如果工序 3 在最后在最后一

35、個(gè)工作站一個(gè)工作站 4 上完成，顯然，工序上完成，顯然，工序 2 必在它之前完成必在它之前完成 . 如果工序如果工序 3 在工作站在工作站 3 上完成上完成 (x33 = 1)，則工序，則工序 2 必須在工作站必須在工作站 1、2、3 上完成，即上完成，即x21 + x22 + x23 x33類(lèi)似類(lèi)似 x21 + x22 x32 ，x21 x31其他其他x11 + x12 + x13 x43 ，x11 + x12 x42 ，x11 x41x31 + x32 + x33 x43 ，x31 + x32 x42 ，x31 x41 以上是以上是 6 道工序、道工序、4個(gè)工作站、個(gè)工作站、5個(gè)工序順序約

36、束的裝配線個(gè)工序順序約束的裝配線平衡問(wèn)題，共有平衡問(wèn)題，共有28個(gè)變量、個(gè)變量、29個(gè)約束條件個(gè)約束條件 .Zmin = 3x11=x21=x31=x42=x62=x53=1其余為其余為 0 緊前約束也可以用一個(gè)不等式描述：緊前約束也可以用一個(gè)不等式描述： x31 + 2x32 + 3x33 + 4x34 x21 + 2x22 + 3x23 + 4x24第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃Example 8 （排序問(wèn)題）（排序問(wèn)題）工藝路線工藝路線j # 機(jī)床加工時(shí)間（小時(shí)）機(jī)床加工時(shí)間（小時(shí)）123i #產(chǎn)產(chǎn)品品1 8 1 22 5 9 63 0 2 10 0 用編號(hào)為用編號(hào)為 1#、2#、3#、

37、4# 的的4種機(jī)床生產(chǎn)種機(jī)床生產(chǎn)3種產(chǎn)品種產(chǎn)品 1#、2#、3#，產(chǎn)品的工藝路線及，產(chǎn)品的工藝路線及工序加工時(shí)間見(jiàn)表工序加工時(shí)間見(jiàn)表. 一臺(tái)機(jī)床一次只能加工一個(gè)產(chǎn)品一臺(tái)機(jī)床一次只能加工一個(gè)產(chǎn)品, 現(xiàn)要求現(xiàn)要求 2# 產(chǎn)品從開(kāi)始加工到完成經(jīng)歷時(shí)間不超過(guò)產(chǎn)品從開(kāi)始加工到完成經(jīng)歷時(shí)間不超過(guò) 29 小小時(shí)時(shí). 問(wèn)如何確定各產(chǎn)品在機(jī)床上的加工順序，使在最短問(wèn)如何確定各產(chǎn)品在機(jī)床上的加工順序，使在最短時(shí)間時(shí)間內(nèi)制成全部產(chǎn)品內(nèi)制成全部產(chǎn)品.Solution:設(shè)設(shè) xij 為為 i # 產(chǎn)品在機(jī)床產(chǎn)品在機(jī)床 j # 上開(kāi)始加工時(shí)間上開(kāi)始加工時(shí)間.第一組約束為每一產(chǎn)品應(yīng)按工藝路線進(jìn)行：第一組約束為每一產(chǎn)品應(yīng)按工

38、藝路線進(jìn)行：#11131314#212222243233 1 : 8 12 : 5 9 3 :2xxxxxxxxxx 3 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例2111 5xx 1121121111 8 5(1 )xxMyxxMy2232232222133333313314244241449 2(1 )1 10(1 )2 6(1 )xxMyxxMyxxMyxxMyxxMyxxMy 第二組約束為一族選擇性第二組約束為一族選擇性的約束條件，以保證每一機(jī)床的約束條件，以保證每一機(jī)床同一時(shí)間只能加工一個(gè)產(chǎn)品：同一時(shí)間只能加工一個(gè)產(chǎn)品： 如對(duì)如對(duì) 1#有有：1121 8xx或或引進(jìn)引進(jìn) 0-1 變量變量

39、y1 , 上述選擇性約束條件為：上述選擇性約束條件為：類(lèi)似類(lèi)似 y2, y3, y4 為為 0-1 變量，對(duì)機(jī)床變量，對(duì)機(jī)床 2#、3#、4# 有有工藝路線工藝路線j # 機(jī)床加工時(shí)間（小時(shí)）機(jī)床加工時(shí)間（小時(shí)）123i #產(chǎn)產(chǎn)品品1 8 1 22 5 9 63 0 2 10 0M 為充分為充分大的正數(shù)大的正數(shù)第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃max142433max 2,6,10Cxxx142433 2, 6, 10CxCxCxminZC2421 621 xx 三個(gè)產(chǎn)品都完工的時(shí)間為：三個(gè)產(chǎn)品都完工的時(shí)間為：將它化為線性約束將它化為線性約束目標(biāo)函數(shù)為目標(biāo)函數(shù)為 2#產(chǎn)品從產(chǎn)品從 1# 機(jī)床開(kāi)始加

40、工機(jī)床開(kāi)始加工到到 4# 機(jī)床加工完成其經(jīng)歷時(shí)間機(jī)床加工完成其經(jīng)歷時(shí)間要求為：要求為：工藝路線工藝路線j # 機(jī)床加工時(shí)間（小時(shí)）機(jī)床加工時(shí)間（小時(shí)）123i #產(chǎn)產(chǎn)品品1 8 1 22 5 9 63 0 2 10 03 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例Example 9 (利潤(rùn)分段線性問(wèn)題利潤(rùn)分段線性問(wèn)題)工時(shí)定額工時(shí)定額(小時(shí)小時(shí)/件件)產(chǎn)品產(chǎn)品總有總有效效工時(shí)工時(shí)甲甲乙乙車(chē)間車(chē)間金工金工43480裝配裝配25500售價(jià)售價(jià)(元元/件件)300520 某廠生產(chǎn)甲、乙兩種產(chǎn)品，需經(jīng)某廠生產(chǎn)甲、乙兩種產(chǎn)品，需經(jīng)過(guò)金工和裝配兩個(gè)車(chē)間加工，相關(guān)數(shù)據(jù)如表所示：過(guò)金工和裝配兩個(gè)車(chē)間加工，相關(guān)數(shù)據(jù)如

41、表所示： 產(chǎn)品乙無(wú)論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總產(chǎn)品乙無(wú)論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總為為 400元，試根據(jù)產(chǎn)品甲生產(chǎn)成本的下列兩種情況分別元，試根據(jù)產(chǎn)品甲生產(chǎn)成本的下列兩種情況分別建立數(shù)學(xué)模型求利潤(rùn)最大建立數(shù)學(xué)模型求利潤(rùn)最大 .1、產(chǎn)品甲的生產(chǎn)成本分段線性：第、產(chǎn)品甲的生產(chǎn)成本分段線性：第 1 30 件，每件件，每件 成本為成本為 200 元；第元；第 31 70 件，每件成本為件，每件成本為 190 元元; 從第從第 71 件開(kāi)始，每件成本為件開(kāi)始，每件成本為 195 元元.2、產(chǎn)品甲的產(chǎn)量不超過(guò)、產(chǎn)品甲的產(chǎn)量不超過(guò) 40 件時(shí)，每件成本件時(shí)，每件成本 200 元，但元，但 超過(guò)超過(guò) 40 件，則甲的全部產(chǎn)品每件成本都為件