數(shù)學(xué)建模_整數(shù)規(guī)劃

1、第三講第三講整數(shù)規(guī)劃整數(shù)規(guī)劃3.1 引言引言 在工程設(shè)計(jì)和企業(yè)管理中，常會(huì)遇到要求決策變量取離散非負(fù)整數(shù)值的線性規(guī)劃問(wèn)題。 例如，最優(yōu)調(diào)度的車輛數(shù)，設(shè)置的銷售網(wǎng)點(diǎn)數(shù)，指派工作的人數(shù)等。 這類問(wèn)題在形式上與線性規(guī)劃類似，只是比線性規(guī)劃增加了某些約束條件，來(lái)限制全部或部分決策變量必須取離散的非負(fù)整數(shù)值。我們稱之為整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問(wèn)題，也經(jīng)常簡(jiǎn)稱為整數(shù)規(guī)劃整數(shù)規(guī)劃問(wèn)題。 整數(shù)規(guī)劃是近四十年來(lái)發(fā)展起來(lái)的、規(guī)劃論的一個(gè)重要的理論分支。根據(jù)對(duì)決策變量的要求不同，分為四種類型： 純整數(shù)規(guī)劃純整數(shù)規(guī)劃：所有決策變量均要求為離散的非負(fù) 整數(shù)。 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃：部分決策變量要求為離散的非負(fù) 整數(shù)

2、。 純純 0 1 整數(shù)規(guī)劃整數(shù)規(guī)劃：所有決策變量均要求為 0 或 1。 混合混合 0 1 整數(shù)規(guī)劃整數(shù)規(guī)劃：部分決策變量要求為 0 或 1。 3.2 引例：生產(chǎn)組織計(jì)劃問(wèn)題與選址問(wèn)題引例：生產(chǎn)組織計(jì)劃問(wèn)題與選址問(wèn)題 引例 3.2.1(生產(chǎn)組織計(jì)劃問(wèn)題生產(chǎn)組織計(jì)劃問(wèn)題)某工廠在一個(gè)計(jì)劃期內(nèi)擬生產(chǎn)甲、乙兩種大型設(shè)備。除了 A、B 兩種部件需要外部供應(yīng)且供應(yīng)受到嚴(yán)格限制之外，該廠有充分的能力來(lái)加工制造這兩種設(shè)備所需的其余零件，并且所需原材料和能源也可滿足供應(yīng)。每種設(shè)備所用部件數(shù)量和部件的供應(yīng)限額以及設(shè)備的利潤(rùn)由表 3.2.1 給出。問(wèn)該廠在本計(jì)劃期內(nèi)如何安排甲、乙設(shè)備的生產(chǎn)數(shù)量，才能獲取最大利潤(rùn)？

3、部件設(shè)備AB利潤(rùn)(百萬(wàn))甲6115乙4320部件的最大供應(yīng)量2510表 3.2.1 設(shè) x1, x2 分別為該計(jì)劃期內(nèi)甲、乙設(shè)備的生產(chǎn)數(shù)量，Z 為生產(chǎn)這兩種設(shè)備可獲得的總利潤(rùn)。依題意，給出問(wèn)題的數(shù)學(xué)模型為： max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 這是一個(gè)純整數(shù)規(guī)劃問(wèn)題。 引例 3.2.2 (選址問(wèn)題選址問(wèn)題)某商業(yè)連鎖集團(tuán)擬在 n 個(gè)連鎖店所在城市中建立 m 個(gè)配貨中心，每個(gè)城市最多建立一個(gè)配貨中心。若在第 i 個(gè)城市建立配貨中心，其配貨能力為 Di，單位時(shí)間的固定成本為 ai，i = 1, , n，第 j 個(gè)連鎖店的

4、需求量為 bj，j = 1, , n。從第 i 個(gè)配貨中心到第 j 個(gè)連鎖店的單位運(yùn)輸成本為 cij。應(yīng)如何選擇配貨中心位置和安排運(yùn)輸計(jì)劃，才能得到經(jīng)濟(jì)上花費(fèi)最少的方案。 問(wèn)題可分為兩部分： 選擇哪些城市作為配貨中心 如何安排運(yùn)輸計(jì)劃 首先考慮后一個(gè)問(wèn)題：已經(jīng)選定了 m 個(gè)配貨中心，如何安排運(yùn)輸計(jì)劃。 假設(shè)從配貨中心 i 運(yùn)往連鎖店 j 的物資數(shù)量為 xij，Z 為單位時(shí)間內(nèi)的總費(fèi)用。則上述問(wèn)題可歸結(jié)為如下的數(shù)學(xué)模型： njmixnjbxmiDxxcZijjmiijinjijminjijij, 1 , 1 , 0, 1 , 1 ,s.t.min1111 這是一個(gè)線性規(guī)劃問(wèn)題(廣義的運(yùn)輸問(wèn)題)。

5、 其次，同時(shí)考慮選擇配貨中心和安排運(yùn)輸計(jì)劃。 假設(shè)在單位時(shí)間內(nèi)，從配貨中心 i 運(yùn)往連鎖店 j 的物資數(shù)量為 xij，Z 為單位時(shí)間內(nèi)的總費(fèi)用。 引入布爾變量 則上述問(wèn)題可歸結(jié)為如下的數(shù)學(xué)模型： 個(gè)城市建立配貨中心不在第個(gè)城市建立配貨中心在第 , 0 , 1iiyinjiyxnjbxniyDxmyyaxcZiijjniijiinjijniiniiininjijij, 1 , ,1 , 0 , 0, 1 , 1 ,s.t.min111111 這是一個(gè)混合 01 規(guī)劃問(wèn)題。3.3 整數(shù)規(guī)劃算法整數(shù)規(guī)劃算法 3.3.1 分枝定界法分枝定界法 分枝定界法是求解整數(shù)規(guī)劃問(wèn)題的一種有效算法，在二十世紀(jì)六十

6、年代初由 Land 和Doig 提出并經(jīng) Dakin 修正而完善。它不僅適用于求解純整數(shù)規(guī)劃問(wèn)題，同時(shí)也適用于求解混合整數(shù)規(guī)劃問(wèn)題。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。 分枝定界法對(duì)可行域恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索，基本上是一種“分而治之”的策略。 通常，它把可行域反復(fù)地劃分為越來(lái)越小的一系列子域，稱之為分枝；子域的一個(gè)邊界為整數(shù)，在子域上解線性規(guī)劃，對(duì)于最大值問(wèn)題，線性規(guī)劃解的目標(biāo)函數(shù)值是整數(shù)規(guī)劃的上界，整數(shù)規(guī)劃任意可行點(diǎn)的目標(biāo)函數(shù)值是其下界，這稱為定界。在子域分解的過(guò)程中，上界非增，下界非減，經(jīng)有限多次分解即可得到整數(shù)規(guī)劃的最優(yōu)解。 整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型的一般形

7、式一般形式為： , 1 , 0 , 0 ),(s.t. (min) max )P(TixXborAXXCZ 定義定義 凡是放棄問(wèn)題 (P) 中的某些約束條件后得到的問(wèn)題 ( )，稱為 (P) 的松弛問(wèn)題。 P 定理定理 若用 R 表示問(wèn)題 (P) 的可行域，用 x* 和 z* 表示問(wèn)題 (P) 的最優(yōu)解與最優(yōu)值；用 表示問(wèn)題 ( ) 的可行域，用 和 表示問(wèn)題 ( ) 的最優(yōu)解與最優(yōu)值。則對(duì)于任何松弛問(wèn)題 ( )，有： (1) R ； (2) ( ) 無(wú)可行解 (P) 無(wú)可行解； (3) z* (對(duì)于求最小值的問(wèn)題 (P)， 則有 z* )； (4) R 也是 (P) 的最優(yōu)解。 RP*x*z

8、PPRP*z*z*x 根據(jù)上述定理，可以給出分枝定界法的基本步驟(參見教材)。 實(shí)現(xiàn)上述步驟的程序框圖，如圖 3.3.1。 為了更好地說(shuō)明用分枝定界法求整數(shù)規(guī)劃最優(yōu)解的過(guò)程，我們選擇只有兩個(gè)變量的引例3.2.1 進(jìn)行求解。 例 3.3.1 用分枝定界法求解整數(shù)規(guī)劃問(wèn)題 (P)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 解解：整數(shù)規(guī)劃問(wèn)題 (P) 的可行域?yàn)椋?1. 求解如下的松弛問(wèn)題 (P0)： (P0)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0，i = 1, 2得

9、最優(yōu)解 x1 = 2.5，x2 = 2.5，最優(yōu)值 z = 87.5。松弛問(wèn)題的最優(yōu)解(2.5, 2.5) 由于原問(wèn)題 (P) 目標(biāo)函數(shù)的系數(shù)為整數(shù)，xi 0, 1, 2, ，故 z* 87，也就是說(shuō)最優(yōu)值的上界 = 87。令最優(yōu)值的下界 z = 0，則有 z = 0 z* 87 = 。 我們將這些結(jié)果記錄在樹形圖中。 zz 2. 因?yàn)榇藭r(shí)兩個(gè)變量都不是整數(shù)，我們從中選擇一個(gè)變量進(jìn)行分枝。假定選擇 x1，在 (P0) 的約束之外，增加兩個(gè)互相排斥的約束條件：x1 2 與 x1 3，形成兩個(gè)子模型 (P1) 和 (P2)： (P1)：max Z = 15x1 20 x2 (P2)：max Z =

10、 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1 4x2 25 x1 3x2 10 x1 3x2 10 x1 2 x1 3 xi 0，i = 1, 2 xi 0，i = 1, 2 相應(yīng)地，模型 (P0) 的可行域被分成兩個(gè)相應(yīng)的子域 R1 和 R2。 顯然，被拋去的非陰影區(qū)域內(nèi)(2 x1 z = 75，所以，在 (P2) 的約束之外，增加兩個(gè)互相排斥的約束條件：x2 1 與 x2 2，形成兩個(gè)子模型 (P5) 和 (P6)： (P5)：max Z = 15x1 20 x2 (P6)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1

11、4x2 25 x1 3x2 10 x1 3x2 10 x1 3 x1 3 x2 1 x2 2 xi 0，i = 1, 2 xi 0，i = 1, 2 7. 對(duì)子模型 (P5) 進(jìn)行求解，得最優(yōu)解為 x1 = 3.5，x2 = 1，最優(yōu)值 z = 72.5。子模型 (P5) 的最優(yōu)解 (3.5, 1) 由于最優(yōu)值 z = 72.5 75 = z，故不再分枝。因?yàn)榉种?，新模型的最?yōu)值不可能超過(guò)當(dāng)前新的下界。 8. 對(duì)子模型 (P6) 進(jìn)行求解，因?yàn)闊o(wú)可行解，故不再分枝。子模型 (P6)無(wú)可行解 至此，已將所有分枝的子模型求解完畢，當(dāng)前新的下界值相應(yīng)的解，是現(xiàn)行最好的整數(shù)可行解，也就是原整數(shù)規(guī)劃問(wèn)

12、題的最優(yōu)解為：x1* = 1，x2* = 3。最優(yōu)目標(biāo)函數(shù)值為 z = 75。 z zz z整數(shù)解 (1, 3)最優(yōu)值為 75整數(shù)解 (2, 2)最優(yōu)值為 70 注：圖 3.3.3 中的子模型 (P3)、(P4)、(P5) 不再分枝，并不是說(shuō)它們分枝后不可以找到新的整數(shù)可行解，而是表明：即使找出新的整數(shù)可行解也不會(huì)優(yōu)于目前最好的整數(shù)可行解，其目標(biāo)函數(shù)值不會(huì)大于目前的下界值，這些可行解已被全部隱含枚舉了。實(shí)質(zhì)上實(shí)質(zhì)上，分枝定界法是一種隱枚舉法分枝定界法是一種隱枚舉法(Implicit Enumeration)。 提示提示：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題，其計(jì)算量一般比較大，所以此法只能求解規(guī)模不太

13、大的整數(shù)規(guī)劃問(wèn)題。對(duì)于規(guī)模較大的整數(shù)規(guī)劃問(wèn)題，可以采取啟發(fā)式算法，例如遺傳算法來(lái)求解。 3.3.2 求解求解 0 1 規(guī)劃模型的隱枚舉法規(guī)劃模型的隱枚舉法 01 規(guī)劃是整數(shù)規(guī)劃的特殊情況，可用前面介紹的方法求解。但由其變量取值的特性，它另有一種特殊的分枝定界法隱枚舉法，該方法也是通過(guò)求解線性松弛模型來(lái)獲得原整數(shù)規(guī)劃模型的最優(yōu)解：不過(guò)這里恰好與一般分枝定界法相反，是由放棄所有線性約束，只保留變量 01 約束而得到的。 隱枚舉法要求 01 規(guī)劃為下述標(biāo)準(zhǔn)形式其中 cj 0，約束條件必須為“”。 njxmibxaxcZjinjjijnjjj, 1 ,1 , 0, 1 ,s.t.min11 當(dāng)某一 c

14、j0 0時(shí)，令 = 1 xj0，則再令 = cj0，原目標(biāo)函數(shù)變?yōu)閺亩鼓繕?biāo)函數(shù)中各變量的系數(shù)變?yōu)榉秦?fù)數(shù)。 0jx)1 (0000001jjjjjjjjjjjjnjjjxcxcxcxcxcZ0jc0000jjjjjjjxccxc 隱枚舉法的解法思路與分枝定界法有相似之處，即利用變量只能取 0 或 1 進(jìn)行分枝。首先令全部變量取 0 值(當(dāng)求最大值時(shí)，令全部變量取 1 值)，檢驗(yàn)解是否滿足約束條件。若均滿足，已得最優(yōu)解；若不全滿足。則令一個(gè)變量取值為 0 或 1(此變量稱為固定變量固定變量)，將模型分成兩個(gè)子棋型，其余未被指定取值的變量稱為自由變量自由變量。由于 cj 0，因此自由變量為 0 與

15、固定變量組成的子模型的解使目標(biāo)值最小。經(jīng)過(guò)幾次檢驗(yàn)后，或者停止分枝，或者將另一個(gè)自由變量轉(zhuǎn)為固定變量，令其值為 0 或 1，繼續(xù)分枝。如此繼續(xù)進(jìn)行，直至沒有自由變量或全部子模型停止分枝為止，就求出最優(yōu)解。 下面通過(guò)一個(gè)例子來(lái)說(shuō)明“隱枚舉法”的解題步驟。 例 3.3.2 求解下列 01 規(guī)劃的最優(yōu)解 min Z = 8x1 2x2 + 4x3 + 7x4 + 5x5 s.t. 3x1 3x2 + x3 + 2x4 + 3x5 2 5x1 3x2 2x3 x4 + x5 4 xi0, 1，i = 1, 2, 3, 4, 5 解解：將原模型記為 P0，所有自由變量全部取 0 值，目標(biāo)值 z0 = 0

16、，顯然不是可行解。 不妨取 x1 作為固定變量，在 P0 中增加約束 x1 = 0 記為 P1，增加約束 x1 = 1 記為 P2。 模型 P2 中 x1 = 1，其他為自由變量，均取 0 值，此時(shí)X = (1, 0, 0, 0, 0)T為可行解，停止分枝。目標(biāo)值 z2 = 8，因此，原模型的最優(yōu)值的上界為 8。 模型 P1 不滿足算法中停止的條件，需繼續(xù)分枝。將 x2 變?yōu)楣潭ㄗ兞?，于是模?P1 分為兩個(gè)分枝 P3 和 P4，繼續(xù)考慮 P3 和 P4。 為了清晰地表達(dá)求解過(guò)程，類似于分枝定界法，我們作出樹形圖(圖 3.3.4)，圖中黑體數(shù)字表示該變量為固定變量。 最優(yōu)解為X* = (0,

17、1, 1, 0, 0)T最優(yōu)值為 z* = z6 = 6。 3.3.4 舍入誤差舍入誤差 對(duì)于整數(shù)規(guī)劃問(wèn)題，可以先去掉整數(shù)限制來(lái)求解相應(yīng)的松弛問(wèn)題，找出松弛問(wèn)題的最優(yōu)解，然后將這個(gè)松弛問(wèn)題的最優(yōu)解舍入成整數(shù)(與它相鄰的 2n 個(gè)整數(shù)點(diǎn))，或者求最靠近它的那個(gè)可行整數(shù)解，對(duì)它們進(jìn)行枚舉。但是，這些都不能保證得到整數(shù)規(guī)劃問(wèn)題的最優(yōu)解，甚至不是可行解。 另外，用窮舉法對(duì)與它相鄰的 2n 個(gè)整數(shù)點(diǎn)進(jìn)行考察，當(dāng) n 較大時(shí)也是不可行的。 例 3.3.3 求解整數(shù)規(guī)劃問(wèn)題 (P) (P)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） xi 0,

18、 1, 2, 解解：將整數(shù)規(guī)劃問(wèn)題 (P) 去掉整數(shù)限制后得到如下的松弛問(wèn)題 (P0)： (P0)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） 求解線性規(guī)劃問(wèn)題 (P0)，得最優(yōu)解 x1 = 2.25，x2 = 3.75，最優(yōu)值 z = 41.25。(P0) 的可行域如圖 3.3.5 中陰影部分，最優(yōu)解在 P 點(diǎn)取到，圖中圓點(diǎn)為整數(shù)點(diǎn)，陰影中的圓點(diǎn)為 (P) 的可行解。 將 x1 = 2.25 和 x2 = 3.75 舍入成整數(shù)(與 P 相鄰的 2n = 4 個(gè)整數(shù)點(diǎn))，或者找最靠近它的那個(gè)可行整數(shù)解，有 (P0) 的最優(yōu)解 (2

19、.25, 3.75)，z = 41.25(P0) 的舍入解(2, 3)z = 34(可行解)(3, 3)z = 39(可行解)(2, 4)z = 42(不可行解)(3, 4)z = 47(不可行解)最靠近 (P0) 的那個(gè)可行整數(shù)解 (2, 3)，z = 34最靠近 (2.25, 3.75) 的整數(shù)解為 (2, 4)，但不可行(P) 的最優(yōu)解 (0, 5)，z = 40 提示提示：從理論上來(lái)講，舍入湊整法是不能用來(lái)求解整數(shù)規(guī)劃問(wèn)題的，上述的例 3.3.3 也說(shuō)明了這一點(diǎn)。 然而，在實(shí)踐中，不必把整數(shù)規(guī)劃與普通的線性規(guī)劃界限劃得太清。因?yàn)樵谠S多實(shí)際問(wèn)題中，模型的建立本身就包含了一些不確定因素，同

20、時(shí)常常也允許近似的或粗略的結(jié)果。因此，舍入湊整法在實(shí)踐中經(jīng)常是有用的。 但要注意，需要大致驗(yàn)證是否可行解。3.4 求解整數(shù)規(guī)劃的蒙特卡洛方法求解整數(shù)規(guī)劃的蒙特卡洛方法 在3.4 中介紹的分枝定界方法，算法的每一個(gè)計(jì)算步驟都是固定的，而且可以保證求得最優(yōu)解。 但是，當(dāng)整數(shù)線性規(guī)劃的決策變量數(shù)目很大時(shí)，分枝定界法的代價(jià)可能是巨大的；特別是當(dāng)整數(shù)規(guī)劃本身是非線性的時(shí)候，尚未有一種成熟而有效的求解方法，因?yàn)榉蔷€性規(guī)劃本身的通用有效解法尚未找到。 然而，由于整數(shù)規(guī)劃解的數(shù)目是有限的，于是為枚舉法提供了方便。當(dāng)然，當(dāng)決策變量數(shù)目很大、取值范圍很寬情況下，企圖用完全搜索(即窮舉法)計(jì)算出最優(yōu)值是不現(xiàn)實(shí)的，但

21、是應(yīng)用蒙特卡洛算法，在一定的計(jì)算量下，完全可以得出一個(gè)滿意解。 例 3.4.1 已知非線性整數(shù)規(guī)劃為：max s.t.Z = x12 x22 3x32 4x42 2x52 8x1 2x2 3x3 x4 2x5x1 x2 x3 x4 x5 400 x1 2x2 2x3 x4 6x5 800 2x1 x2 6x3 200 x3 x4 5x5 2005x1 9x2 45 0 xi 99，i = 1, 2, 3, 4, 5 對(duì)該問(wèn)題，目前尚無(wú)有效方法求出準(zhǔn)確的最優(yōu)解。如果用窮舉法(完全搜索)試探，共需計(jì)算1005 = 1010 個(gè)點(diǎn)，計(jì)算量非常大。 然而概率理論能夠保證，應(yīng)用蒙特卡洛方法隨機(jī)計(jì)算106

22、個(gè)點(diǎn)，便可找到問(wèn)題的滿意解，而且時(shí)間代價(jià)非常小(運(yùn)行 Matlab 程序不到 30 秒)。 解解：用蒙特卡洛方法求解這個(gè)問(wèn)題必須借助計(jì)算機(jī)來(lái)實(shí)現(xiàn)。 首先編寫 M 文件 mente.m 定義目標(biāo)函數(shù) f 和約束向量函數(shù) g，程序如下： 其次，編寫主程序求問(wèn)題的解。 由于是隨機(jī)搜索，故運(yùn)行程序 10 次，可得如下表所示的結(jié)果：106運(yùn)行程序最優(yōu)解最優(yōu)值時(shí)間第一次運(yùn)行 x = (1, 3, 30, 97, 10)T 4032526.5s第二次運(yùn)行 x = (1, 2, 23, 99, 6)T4067626.3s第三次運(yùn)行 x = (7, 0, 21, 98, 9)T3971526.6s第四次運(yùn)行 x

23、 = (6, 1, 24, 99, 3)T4076026.5s第五次運(yùn)行 x = (1, 4, 23, 97, 4)T3908226.6s第六次運(yùn)行 x = (2, 2, 18, 99, 4)T4003526.6s第七次運(yùn)行 x = (3, 3, 27, 99, 12)T4146326.4s第八次運(yùn)行 x = (2, 0, 4, 98, 19)T3902626.3s第九次運(yùn)行 x = (5, 1, 30, 99, 3)T4171126.5s第十次運(yùn)行 x = (4, 2, 27, 99, 9)T4133926.7s 注注：蒙特卡洛(Monte Carlo)算法是一種隨機(jī)搜索算法，它允許算法在執(zhí)

24、行的過(guò)程中隨機(jī)選擇下一個(gè)計(jì)算步驟。許多情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇省時(shí)，因此蒙特卡洛算法可在很大程度上降低算法的復(fù)雜度。但另一方面，同一實(shí)例用蒙特卡洛算法求解兩次可能得到完全不同的結(jié)果，也就是說(shuō)，用蒙特卡洛算法能夠求得問(wèn)題的一個(gè)解，但無(wú)法判斷這個(gè)解是否正確，求得正確解的概率依賴于算法所用的時(shí)間，算法所用的時(shí)間越多，得到正確解的概率就越高。 3.5 范例范例招聘計(jì)劃招聘計(jì)劃 招聘計(jì)劃招聘計(jì)劃：一家保姆服務(wù)公司專門向顧主提供保姆服務(wù)。根據(jù)估計(jì)，下一年的需求是：春季 6000 人日，夏季 7500 人日，秋季 5500 人日，冬季 9000 人日。公司新招聘的保姆

25、必須經(jīng)過(guò) 5 天的培訓(xùn)才能上崗，每個(gè)保姆每季度工作(新保姆包括培訓(xùn))65 天。保姆從該公司而不是從顧主那里得到報(bào)酬，每人每月工資 3000 元。春季開始時(shí)公司擁有 120 名保姆，在每個(gè)季度結(jié)束后，將有 15% 的保姆自動(dòng)離職。 (1) 如果公司不允許解雇保姆，請(qǐng)你為公司制定下一年的招聘計(jì)劃；哪些季度需求的增加不影響招聘計(jì)劃？可以增加多少？ (2) 如果公司在每個(gè)季度結(jié)束后允許解雇保姆，請(qǐng)為公司制定下一年的招聘計(jì)劃。 解解：?jiǎn)栴}(1)的求解 設(shè) 4 個(gè)季度開始時(shí)公司新招聘的保姆數(shù)分別為 x1, x2, x3, x4 人，4 個(gè)季度開始時(shí)保姆總數(shù)量分別為 S1, S2, S3, S4 人。 以本

26、年度付出的總報(bào)酬最少(即 4 個(gè)季度開始時(shí)保姆總數(shù)量之和最小)為目標(biāo)，則問(wèn)題的數(shù)學(xué)模型為 min Z = S1 + S2 + S3 + S4 s.t. 65S1 6000 + 5x1 65S2 7500 + 5x2 65S3 5500 + 5x3 65S4 9000 + 5x4 S1 = 120 + x1 S2 = 0.85S1 + x2 S3 = 0.85S2 + x3 S4 = 0.85S3 + x4 x1, x2, x3, x4, S1, S2, S3, S4Z + 各季度的服務(wù)需求 各季度初的儲(chǔ)備量 雖然模型要求 x1, x2, x3, x4, S1, S2, S3, S4 為正整數(shù)，

27、但因?yàn)楸Ｄ窋?shù)量較大，加之非整數(shù)因子 0.85 的影響，因此可以近似看作實(shí)數(shù)來(lái)處理。 其次，下一年各季度保姆服務(wù)的需求只是估計(jì)值，什么樣的數(shù)學(xué)解都無(wú)法作為實(shí)際問(wèn)題的精確解。 因此，采用舍入湊整的方法來(lái)求解。 將上述整數(shù)規(guī)劃模型松弛成線性規(guī)劃模型，用 Matlab 求解得： 對(duì)上述結(jié)果取整，4 個(gè)季度開始時(shí)公司新招聘的保姆數(shù)量分別為 0, 15, 0, 59 人，每個(gè)季度開始時(shí)保姆總數(shù)量分別為 120, 117, 99, 143 人。 x1 = 0.0000S1 = 120.0000 x2 = 14.5000S2 = 116.5000 x3 = 0.0000S3 = 99.0250 x4 = 58

28、.8145S4 = 142.9857 將上述取整得到的整數(shù)解帶入各季度服務(wù)需求的約束條件65S1 6000 + 5x1, 65S2 7500 + 5x265S3 5500 + 5x3, 65S4 9000 + 5x4有65S1 5x1 = 7800 600065S2 5x2 = 7530 750065S3 5x3 = 6435 550065S4 5x4 = 9000 9000滿足服務(wù)需求 再帶入各季度初儲(chǔ)備要求的約束條件 S1 = 120 + x1, S2 = 0.85S1 + x2 S3 = 0.85S2 + x3, S4 = 0.85S3 + x4有 S1 x1 = 120 S2 0.85

29、S1 x2 = 0 S3 0.85S2 x3 = 0.45 S4 0.85S3 x4 = 0.15雖不滿足儲(chǔ)備需求，但基本不影響制定招聘計(jì)劃。 于是，這個(gè)招聘問(wèn)題的解為： x1 = 0, x2 = 15, x3 = 0, x4 = 59 S1 = 120, S2 = 117, S3 = 99, S4 = 143相應(yīng)的最優(yōu)值為：Z = S1 + S2 + S3 + S4 = 479 因此，公司可以擬定如下的招聘計(jì)劃： 第二季度開始時(shí)公司新招聘 15 人，第四季度開始時(shí)公司新招聘 59 人。 接下來(lái)討論哪些季度需求的增加不會(huì)影響招聘計(jì)劃。 由于春季開始時(shí)公司擁有 S1 = 120 名保姆，且春季開

30、始時(shí)公司招聘的保姆數(shù)量為 x1 = 0，因此，根據(jù)約束條件 65S1 6000 + 5x1 知，春季需求的增加不影響招聘計(jì)劃，且可以增加65S1 6000 = 1800(人日) 類似地，夏季和秋季需求的增加也不影響招聘計(jì)劃，且可以增加 30 和 935(人日)。 問(wèn)題(2)的求解 設(shè) 4 個(gè)季度開始時(shí)公司新招聘的保姆數(shù)分別為 x1, x2, x3, x4 人，4 個(gè)季度結(jié)束時(shí)公司解雇的保姆數(shù)分別為 y1, y2, y3, y4 人，4 個(gè)季度開始時(shí)保姆總數(shù)量分別為 S1, S2, S3, S4 人。 以本年度付出的總報(bào)酬最少(即 4 個(gè)季度開始時(shí)保姆總數(shù)量之和最小)為目標(biāo)，則問(wèn)題的數(shù)學(xué)模型為

31、min Z = S1 + S2 + S3 + S4 s.t. 65S1 6000 + 5x1 65S2 7500 + 5x2 65S3 5500 + 5x3 65S4 9000 + 5x4 S1 = 120 + x1 S2 = 0.85S1 + x2 y1 S3 = 0.85S2 + x3 y2 S4 = 0.85S3 + x4 y3 xi, yi, SiZ +, i = 1, 2, 3, 4 將上述整數(shù)規(guī)劃模型松弛成線性規(guī)劃模型，用 Matlab 求解得： 對(duì)上述結(jié)果取整有：x1 = 0.0000S1 = 120.0000y1 = 0.0000 x2 = 14.5000S2 = 116.50

32、00y2 = 14.4096x3 = 0.0000S3 = 84.6154y3 = 0.0000 x4 = 72.0833S4 = 144.0064x1 = 0 x2 = 15x3 = 0 x4 = 72S1 = 120S2 = 117S3 = 85S4 = 144y1 = 0y2 = 15y3 = 0 將上述取整得到的整數(shù)解帶入服務(wù)需求的約束條件65S1 6000 + 5x1, 65S2 7500 + 5x265S3 5500 + 5x3, 65S4 9000 + 5x4有65S1 5x1 = 7800 600065S2 5x2 = 7530 750065S3 5x3 = 5525 5500

33、65S4 5x4 = 9000 9000滿足服務(wù)需求 再帶入各季度初儲(chǔ)備要求的約束條件 S1 = 120 + x1, S2 = 0.85S1 + x2 y1 S3 = 0.85S2 + x3 y2, S4 = 0.85S3 + x4 y3有 S1 x1 = 120 S2 0.85S1 x2 + y1 = 0 S3 0.85S2 x3 + y2 = 0.45 S4 0.85S3 x4 + y3 = 0.25雖不滿足儲(chǔ)備需求，但基本不影響制定招聘計(jì)劃。 于是，這個(gè)招聘問(wèn)題的解為： x1 = 0, x2 = 15, x3 = 0, x4 = 72 S1 = 120, S2 = 117, S3 = 8

34、5, S4 = 144 y1 = 0, y2 = 15, y3 = 0相應(yīng)的最優(yōu)值為：Z = S1 + S2 + S3 + S4 = 466 因此，公司可以擬定如下的招聘計(jì)劃： 第二季度開始時(shí)公司新招聘 15 人，第二季度結(jié)束時(shí)解雇 15 人；第四季度開始時(shí)公司新招聘 72 人。 此時(shí)，目標(biāo)函數(shù)值為 466，比不允許解雇時(shí)的目標(biāo)函數(shù)值(479)略有減少。 整數(shù)規(guī)劃補(bǔ)充范例整數(shù)規(guī)劃補(bǔ)充范例合理下料問(wèn)題合理下料問(wèn)題 鋼管零售商所進(jìn)的原料鋼管長(zhǎng)度都是 19m。銷售時(shí)零售商需要按照客戶的要求進(jìn)行切割。 現(xiàn)有一客戶需要 50 根長(zhǎng) 4m、20 根長(zhǎng) 6m 和 15 根長(zhǎng) 8m 的鋼管。應(yīng)如何下料最節(jié)?。?/p>

35、 問(wèn)題分析問(wèn)題分析 對(duì)于下料問(wèn)題，首先要確定采用哪些可行的切割模式。所謂切割模式切割模式，是指按照顧客要求的長(zhǎng)度在原料鋼管上安排切割的一種組合。 例如，我們可以將 19m 的鋼管切割成 3 根長(zhǎng)4m 的鋼管，余料為 7m；或者可以將長(zhǎng) 19m 的鋼管切割成長(zhǎng) 4m、6m 和 8m 的鋼管各 1 根，余料為 1m； 顯然，可行的切割模式是很多的。 其次，應(yīng)當(dāng)明確哪些切割模式是合理的。合理的切割模式應(yīng)該要求余料小于客戶需要鋼管的最小尺寸 4m。 例如，可以將長(zhǎng) 19m 的鋼管切割成 3 根 4m 的鋼管是可行的，但余料為 7m，可進(jìn)一步將 7m 的余料切割成 4m 鋼管(余料為 3m)，或者將 7

36、m 的余料切割成 6m 鋼管(余料為 1m) 經(jīng)過(guò)簡(jiǎn)單的計(jì)算可知，問(wèn)題(1)的合理切割模式一共有 7 種，如表 1 所示： 表 1 問(wèn)題(1)的合理切割模式模式4m 鋼管根數(shù)6m 鋼管根數(shù)8m 鋼管根數(shù)余料/m14003231013201341203511116030170023 于是問(wèn)題轉(zhuǎn)化為在滿足客戶需要的條件下，按照哪幾種合理的模式，每種模式切割多少根原料鋼管最為節(jié)省。 而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。 下面將對(duì)這兩個(gè)目標(biāo)分別討論。 建立模型及求解建立模型及求解 用 xi 表示按照表 1 第 i 種模式(i = 1, 2, , 7)

37、切割的原料鋼管的根數(shù)，若以切割后剩余的總余料量最小為目標(biāo)，則按照表 1 最后一列可得 min Z1 = 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 若以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有min Z2 = x1 + x2 + x3 + x4 + x5 + x6 + x7 約束條件為客戶的需求，按照表 1 應(yīng)有 4x1 + 3x2 + 2x3 + x4 + x5 50 x2 + 2x4 + x5 + 3x6 20 x3 + x5 + 2x7 15 最后，切割的原料鋼管的根數(shù) xi 顯然應(yīng)當(dāng)是非負(fù)整數(shù)(用 Z 表示整數(shù)集合，Z+ 表示非負(fù)整數(shù)集合)xiZ+, i =

38、1, 2, , 7 于是，問(wèn)題(1)的數(shù)學(xué)模型為： 模型 1： 模型 2：7 , , 2 , 1 ,152203250234s.t. 3333min75365425432176543211ixxxxxxxxxxxxxxxxxxxxZiZ7 , , 2 , 1 ,152203250234s.t. min75365425432176543212ixxxxxxxxxxxxxxxxxxxxZiZ 這兩個(gè)模型均是整數(shù)規(guī)劃模型。首先將原問(wèn)題松弛為線性規(guī)劃問(wèn)題，求解后再取整。 應(yīng)用 Matlab 求解模型 1，得最優(yōu)整數(shù)解為： x1 = 0, x2 = 12, x3 = 0, x4 = 0 x5 = 15,

39、 x6 = 0, x7 = 0最優(yōu)值為：Z = 27。 將上述整數(shù)解帶入約束條件驗(yàn)證，滿足約束條件的要求。 應(yīng)用 Matlab 求解模型 2，得最優(yōu)整數(shù)解為： x1 = 2, x2 = 9, x3 = 1, x4 = 0 x5 = 11, x6 = 0, x7 = 1得最優(yōu)值為：Z = 24。 將上述整數(shù)解帶入約束條件驗(yàn)證，不滿足約束條件的要求： 4x1 + 3x2 + 2x3 + x4 + x5 = 48 50 x2 + 2x4 + x5 + 3x6 = 20 20 x3 + x5 + 2x7 = 14 15需要調(diào)整需要調(diào)整 由于缺少 2 根 4m 和 1 根 8m 的鋼管，它們的總長(zhǎng)為 16m，故再增加一個(gè)模式 3(即2, 0, 1)給出的切割