數(shù)學(xué)建模第五章整數(shù)規(guī)劃

1、 第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃 運(yùn)運(yùn) 籌籌 學(xué)學(xué) operations research 第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃 在在 lp 問題的討論中，有些最優(yōu)解是小數(shù)問題的討論中，有些最優(yōu)解是小數(shù) . 但對(duì)但對(duì)于某些具體問題常有要求最優(yōu)解是整數(shù)于某些具體問題常有要求最優(yōu)解是整數(shù)( 即整數(shù)解即整數(shù)解) . 如決策變量為機(jī)器的臺(tái)數(shù)、人數(shù)、車輛數(shù)如決策變量為機(jī)器的臺(tái)數(shù)、人數(shù)、車輛數(shù) etc. 如果在問題中所有決策變量有整數(shù)限制，稱為如果在問題中所有決策變量有整數(shù)限制，稱為 純純整數(shù)規(guī)劃整數(shù)規(guī)劃( pure ip ) 或或 全整數(shù)規(guī)劃全整數(shù)規(guī)劃 ( all ip )； 如果在問題中僅部分決策變量有整數(shù)

2、限制，稱為如果在問題中僅部分決策變量有整數(shù)限制，稱為 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃( mixed ip ) ； 如果在問題中決策變量?jī)H取如果在問題中決策變量?jī)H取 0 、1，稱為，稱為 0-1 (整整數(shù)數(shù)) 規(guī)劃規(guī)劃 .integer programming第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃問題及其數(shù)學(xué)模型2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法3 整數(shù)規(guī)劃的應(yīng)用舉例整數(shù)規(guī)劃的應(yīng)用舉例1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃問題及其數(shù)學(xué)模型1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃問題及其數(shù)學(xué)模型 貨貨 物物每箱體積每箱體積（m3）每箱重量每箱重量（kg）每箱利潤(rùn)每箱利潤(rùn)（百元）（百元

3、） 甲甲5220 乙乙4510托運(yùn)限制托運(yùn)限制2413example 1 （裝載問題）（裝載問題） 某廠擬用集裝箱托運(yùn)甲、乙某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)及托運(yùn)限制兩種貨物，每箱的體積、重量、可獲利潤(rùn)及托運(yù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 問題問題.第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1232

4、yyy1231 3iiiixxxaiexample 2 （工廠選址問題）（工廠選址問題）10iy 現(xiàn)準(zhǔn)備從現(xiàn)準(zhǔn)備從 a1、a2、a3 三個(gè)地點(diǎn)中選擇兩個(gè)開設(shè)工廠，工廠建成后它每月的三個(gè)地點(diǎn)中選擇兩個(gè)開設(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 見表見表. bjaib1b2b3aia145370a223480a364590bj406045 已知三已知三工廠每月的經(jīng)營(yíng)費(fèi)用工廠每月的經(jīng)營(yíng)費(fèi)用 di (與與產(chǎn)量無關(guān)產(chǎn)量無關(guān))分別為

5、分別為 100、90、120 .問如問如何選址使每月經(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)輸問題求解，再加上每月的經(jīng)營(yíng)是任取兩個(gè)廠用運(yùn)輸問題求解，再加上每月的經(jīng)營(yíng)費(fèi)用比較即可費(fèi)用比較即可.233c 設(shè)設(shè)選地點(diǎn)選地點(diǎn) ai 開設(shè)工廠開設(shè)工廠否則否則 i = 1,2,3 ； xij 為為ai 開設(shè)工廠時(shí)，從開設(shè)工廠時(shí)，從 ai 至至 bj 的運(yùn)量的運(yùn)量ijijiizc xd y1231 3jjjjxxxbj顯然顯然如果如果 ai 處開設(shè)工廠，處開設(shè)工廠，則運(yùn)量滿足：則運(yùn)

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

7、問題及其數(shù)學(xué)模型題及其數(shù)學(xué)模型1niiyj123123256180 ,437240 xxxxxx 在在 ex.2 中，引進(jìn)中，引進(jìn) 01 變量給出了在變量給出了在 n 件任務(wù)中件任務(wù)中,選擇選擇 j 項(xiàng)的約束項(xiàng)的約束1mijiijxa y又用又用 來刻畫不設(shè)來刻畫不設(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 （背包問題）（

9、背包問題） 假設(shè)有人要出發(fā)旅行，考慮帶七假設(shè)有人要出發(fā)旅行，考慮帶七種物品，每件物品的重量與價(jià)值如表種物品，每件物品的重量與價(jià)值如表. 現(xiàn)在假設(shè)他最多帶現(xiàn)在假設(shè)他最多帶 35kg 物品，問該帶物品，問該帶哪幾件物品使總價(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ī)劃問題規(guī)劃問題. 一般整數(shù)規(guī)劃中的變量一般整數(shù)規(guī)劃中的變量 x , 也可用也可用 0-1 變量替

10、代，如變量替代，如0 x15 ，x=x020+x121+x222+x323 其中其中 x0,x1,x2,x3 為為0-1 變量變量 .1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃問題及其數(shù)學(xué)模型125424xx12121212max2010. . 54242513,0,zxxstxxxxx x 參見參見 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ù)化整的原問題的解？是否可以根據(jù)化整的原問題的解？

11、x1=5、x2=0 不是可行解，不是可行解， 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 問題的問題的解一定是整數(shù)解？解一定是整數(shù)解？ 如：如： 運(yùn)輸問題運(yù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 問題的解即為整數(shù)解問題的解即為整數(shù)解;2、在在 lp 的可行域中，整數(shù)點(diǎn)不多，的可行域中，整數(shù)點(diǎn)不多，（12個(gè)）個(gè)）是否可以用窮舉法是否可以用窮舉法.2 整數(shù)規(guī)劃

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

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

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

16、）3、可獲得最優(yōu)解、可獲得最優(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如果如果 則稱問題（則稱問題（2）是問題（）是問題（1）的松弛問題）的松弛問題. .note : 1、松弛問題未必比原問題難解；、松弛問題未必比原問題難解；如：如：整數(shù)規(guī)劃與線性規(guī)劃；整數(shù)規(guī)劃與線性規(guī)劃；tsp 與指派問題與指派問題 etc. 如：如： a：尋找全國(guó)：尋找全國(guó)18 歲百米最快的運(yùn)動(dòng)員歲百米最快的運(yùn)動(dòng)員.b：尋找：尋找全國(guó)所有百米最快的運(yùn)動(dòng)員全國(guó)所有百米最快的運(yùn)動(dòng)員. .顯然，顯然，

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

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

19、上界（極大化問題）的活問題先檢查最大上界（極大化問題）的活問題優(yōu)點(diǎn)：優(yōu)點(diǎn)：檢查子問題較其他規(guī)則為少；檢查子問題較其他規(guī)則為少；缺點(diǎn)：缺點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較大計(jì)算機(jī)儲(chǔ)存量較大先檢查最新產(chǎn)生的最大上界的活問題先檢查最新產(chǎ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ā)揮的余地 分枝與定界法的重要在于它提出了一類新的思分枝與定界法的重要在于它提出了一類新的思路（隱枚舉法），使得許多原來不好解決的問題有路（隱枚舉法），使得許多原來不好解決的問題有了解決的可能性了解決的可能性. （具有普適性

20、）（具有普適性）第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃1212121212max58. .65945,0,zxxstxxxxx xx xi125945xxexample 4 用分支定界法求解如右用分支定界法求解如右 ip 問題問題12121212max58. .65945,0,zxxstxxxxx x126xxsolution:解松弛問題解松弛問題 p0得：得：x1=2.25、x2=3.75 zmax=41.25去掉整數(shù)約束為去掉整數(shù)約束為原原問題的松弛問題問題的松弛問題41.25是原問題最優(yōu)值的上界是原問題最優(yōu)值的上界進(jìn)行分支，任選一個(gè)不是整數(shù)的變量進(jìn)行分支，任選一個(gè)不是整數(shù)的變量,如取如取 x2

21、則可認(rèn)為則可認(rèn)為最優(yōu)解最優(yōu)解 x24 或或 x23 . 原問題分為兩個(gè)子問題原問題分為兩個(gè)子問題 . 3x24 之間無整數(shù)解之間無整數(shù)解0 1 2 3 4 5 6 7 8 9 x1x254321p1p2再分別求解兩個(gè)松弛問題再分別求解兩個(gè)松弛問題 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í)已沒有活問題，所以

22、最此時(shí)已沒有活問題，所以最優(yōu)解為優(yōu)解為 x1=0、x2=5 zmax=40 .2 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法1232312313123max20816. .42552743753601,1 3jzxxxstxxxxxxxxxxxorjexample 5 （投資方案的最優(yōu)選擇）（投資方案的最優(yōu)選擇） 背包問題可以看成為一個(gè)一次性的投資問題，簡(jiǎn)背包問題可以看成為一個(gè)一次性的投資問題，簡(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)行投資

23、，根據(jù)預(yù)算四年內(nèi)的投資額、三個(gè)項(xiàng)目根據(jù)預(yù)算四年內(nèi)的投資額、三個(gè)項(xiàng)目每年所需投資額以及所創(chuàng)利潤(rùn)如表每年所需投資額以及所創(chuàng)利潤(rùn)如表. 問應(yīng)對(duì)哪幾個(gè)項(xiàng)目進(jì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è)門檻設(shè)門檻 (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

25、 0 0) (0 0 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í)間安排問題）（人員時(shí)間安排問題） 為了盡可能有

26、效地利用勞動(dòng)力，有必要對(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ù)問題，假設(shè)每日工作司的售票員人數(shù)問題，假設(shè)每日工作 8

27、 小時(shí)且連續(xù)工小時(shí)且連續(xù)工作，由統(tǒng)計(jì)資料得各時(shí)段需要的最少人數(shù)作，由統(tǒng)計(jì)資料得各時(shí)段需要的最少人數(shù) . 問該公司問該公司最少需雇傭多少售票員？最少需雇傭多少售票員？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ī)

28、劃的應(yīng)用舉例solution: 由表中情況可知，只由表中情況可知，只需考慮時(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í)段開始工作的人數(shù)，個(gè)時(shí)段開始工作的人數(shù)，j =15 .可用可用0-1規(guī)劃表示規(guī)劃表示 進(jìn)一步討論進(jìn)一步討論, 售售票員的吃飯時(shí)間、票員的吃飯時(shí)間、工資等工資等.第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃各班工作時(shí)間及工資：各班工作時(shí)間及工資：班次班次上班時(shí)間上班時(shí)間休息時(shí)間休息時(shí)間月工資月

29、工資108：0017：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（

30、12：0012：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：30

31、20：00）800011110016（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 （裝配線平衡問題）（裝配線平衡問題） 若某工廠的產(chǎn)品裝配若某工廠的產(chǎn)品裝配線由線由 6 道工序組成，各工序的加工時(shí)間及緊前

32、工序見表道工序組成，各工序的加工時(shí)間及緊前工序見表:工序工序加工時(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分鐘分鐘 .問最少應(yīng)設(shè)幾個(gè)工作站，每個(gè)工作站完成哪些工序問最少應(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í)間總和不超過序所需的時(shí)間總和不超過 10 分鐘，

34、即分鐘，即3x1j + 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 之前完成，如果工序之前完成，如果工

35、序 3 在最后在最后一個(gè)工作站一個(gè)工作站 4 上完成，顯然，工序上完成，顯然，工序 2 必在它之前完成必在它之前完成 . 如果工序如果工序 3 在工作站在工作站 3 上完成上完成 (x33 = 1)，則工序，則工序 2 必須在工作站必須在工作站 1、2、3 上完成，即上完成，即x21 + x22 + x23 x33類似類似 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è)

36、工作站、5個(gè)工序順序約束的裝配線個(gè)工序順序約束的裝配線平衡問題，共有平衡問題，共有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 （排序問題）（排序問題）工藝路線工藝路線j # 機(jī)床加工時(shí)間（小時(shí)）機(jī)床加工時(shí)間（小時(shí)）1234i #產(chǎn)產(chǎn)品品1 8 1 22 5 9 63 0 2 10 0 用編號(hào)為用編

37、號(hào)為 1#、2#、3#、4# 的的4種機(jī)床生產(chǎn)種機(jī)床生產(chǎn)3種產(chǎn)品種產(chǎn)品 1#、2#、3#，產(chǎn)品的工藝路線及，產(chǎn)品的工藝路線及工序加工時(shí)間見表工序加工時(shí)間見表. 一臺(tái)機(jī)床一次只能加工一個(gè)產(chǎn)品一臺(tái)機(jī)床一次只能加工一個(gè)產(chǎn)品, 現(xiàn)要求現(xiàn)要求 2# 產(chǎn)品從開始加工到完成經(jīng)歷時(shí)間不超過產(chǎn)品從開始加工到完成經(jīng)歷時(shí)間不超過 29 小小時(shí)時(shí). 問如何確定各產(chǎn)品在機(jī)床上的加工順序，使在最短問如何確定各產(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 # 上開始加工時(shí)間上開始加工時(shí)間.第一組約束為每一產(chǎn)品應(yīng)按工藝路線進(jìn)行：第

38、一組約束為每一產(chǎn)品應(yīng)按工藝路線進(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)

39、引進(jìn) 0-1 變量變量 y1 , 上述選擇性約束條件為：上述選擇性約束條件為：類似類似 y2, y3, y4 為為 0-1 變量，對(duì)機(jī)床變量，對(duì)機(jī)床 2#、3#、4# 有有工藝路線工藝路線j # 機(jī)床加工時(shí)間（小時(shí)）機(jī)床加工時(shí)間（小時(shí)）1234i #產(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)品

40、從產(chǎn)品從 1# 機(jī)床開始加工機(jī)床開始加工到到 4# 機(jī)床加工完成其經(jīng)歷時(shí)間機(jī)床加工完成其經(jīng)歷時(shí)間要求為：要求為：工藝路線工藝路線j # 機(jī)床加工時(shí)間（小時(shí)）機(jī)床加工時(shí)間（小時(shí)）1234i #產(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)分段線性問題利潤(rùn)分段線性問題)工時(shí)定額工時(shí)定額(小時(shí)小時(shí)/件件)產(chǎn)品產(chǎn)品總有總有效效工時(shí)工時(shí)甲甲乙乙車間車間金工金工43480裝配裝配25500售價(jià)售價(jià)(元元/件件)300520 某廠生產(chǎn)甲、乙兩種產(chǎn)品，需經(jīng)某廠生產(chǎn)甲、乙兩種產(chǎn)品，需經(jīng)過金工和裝配兩個(gè)車間加工，相關(guān)數(shù)據(jù)如表所示：過金工和

41、裝配兩個(gè)車間加工，相關(guān)數(shù)據(jù)如表所示： 產(chǎn)品乙無論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總產(chǎn)品乙無論生產(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 件開始，每件成本為件開始，每件成本為 195 元元.2、產(chǎn)品甲的產(chǎn)量不超過、產(chǎn)品甲的產(chǎn)量不超過 40 件時(shí)，每件成本件時(shí)，每件成本 200 元，但元，但 超過超過 40 件，則甲的全部產(chǎn)品每件成本都為