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

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

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

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

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

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

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

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

8、PPRP*z*z*x 根據(jù)上述定理，可以給出分枝定界法的基本步驟(參見教材)。 實現(xiàn)上述步驟的程序框圖，如圖 3.3.1。 為了更好地說明用分枝定界法求整數(shù)規(guī)劃最優(yōu)解的過程，我們選擇只有兩個變量的引例3.2.1 進行求解。 例 3.3.1 用分枝定界法求解整數(shù)規(guī)劃問題 (P)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 解解：整數(shù)規(guī)劃問題 (P) 的可行域為： 1. 求解如下的松弛問題 (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。松弛問題的最優(yōu)解(2.5, 2.5) 由于原問題 (P) 目標函數(shù)的系數(shù)為整數(shù)，xi 0, 1, 2, ，故 z* 87，也就是說最優(yōu)值的上界 = 87。令最優(yōu)值的下界 z = 0，則有 z = 0 z* 87 = 。 我們將這些結(jié)果記錄在樹形圖中。 zz 2. 因為此時兩個變量都不是整數(shù)，我們從中選擇一個變量進行分枝。假定選擇 x1，在 (P0) 的約束之外，增加兩個互相排斥的約束條件：x1 2 與 x1 3，形成兩個子模型 (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) 的可行域被分成兩個相應(yīng)的子域 R1 和 R2。 顯然，被拋去的非陰影區(qū)域內(nèi)(2 x1 z = 75，所以，在 (P2) 的約束之外，增加兩個互相排斥的約束條件：x2 1 與 x2 2，形成兩個子模型 (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. 對子模型 (P5) 進行求解，得最優(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ōu)值不可能超過當前新的下界。 8. 對子模型 (P6) 進行求解，因為無可行解，故不再分枝。子模型 (P6)無可行解 至此，已將所有分枝的子模型求解完畢，當前新的下界值相應(yīng)的解，是現(xiàn)行最好的整數(shù)可行解，也就是原整數(shù)規(guī)劃問

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

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

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

15、固定變量組成的子模型的解使目標值最小。經(jīng)過幾次檢驗后，或者停止分枝，或者將另一個自由變量轉(zhuǎn)為固定變量，令其值為 0 或 1，繼續(xù)分枝。如此繼續(xù)進行，直至沒有自由變量或全部子模型停止分枝為止，就求出最優(yōu)解。 下面通過一個例子來說明“隱枚舉法”的解題步驟。 例 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 值，目標值 z0 = 0

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

17、1, 1, 0, 0)T最優(yōu)值為 z* = z6 = 6。 3.3.4 舍入誤差舍入誤差 對于整數(shù)規(guī)劃問題，可以先去掉整數(shù)限制來求解相應(yīng)的松弛問題，找出松弛問題的最優(yōu)解，然后將這個松弛問題的最優(yōu)解舍入成整數(shù)(與它相鄰的 2n 個整數(shù)點)，或者求最靠近它的那個可行整數(shù)解，對它們進行枚舉。但是，這些都不能保證得到整數(shù)規(guī)劃問題的最優(yōu)解，甚至不是可行解。 另外，用窮舉法對與它相鄰的 2n 個整數(shù)點進行考察，當 n 較大時也是不可行的。 例 3.3.3 求解整數(shù)規(guī)劃問題 (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ī)劃問題 (P) 去掉整數(shù)限制后得到如下的松弛問題 (P0)： (P0)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） 求解線性規(guī)劃問題 (P0)，得最優(yōu)解 x1 = 2.25，x2 = 3.75，最優(yōu)值 z = 41.25。(P0) 的可行域如圖 3.3.5 中陰影部分，最優(yōu)解在 P 點取到，圖中圓點為整數(shù)點，陰影中的圓點為 (P) 的可行解。 將 x1 = 2.25 和 x2 = 3.75 舍入成整數(shù)(與 P 相鄰的 2n = 4 個整數(shù)點)，或者找最靠近它的那個可行整數(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) 的那個可行整數(shù)解 (2, 3)，z = 34最靠近 (2.25, 3.75) 的整數(shù)解為 (2, 4)，但不可行(P) 的最優(yōu)解 (0, 5)，z = 40 提示提示：從理論上來講，舍入湊整法是不能用來求解整數(shù)規(guī)劃問題的，上述的例 3.3.3 也說明了這一點。 然而，在實踐中，不必把整數(shù)規(guī)劃與普通的線性規(guī)劃界限劃得太清。因為在許多實際問題中，模型的建立本身就包含了一些不確定因素，同

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

21、是應(yīng)用蒙特卡洛算法，在一定的計算量下，完全可以得出一個滿意解。 例 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 對該問題，目前尚無有效方法求出準確的最優(yōu)解。如果用窮舉法(完全搜索)試探，共需計算1005 = 1010 個點，計算量非常大。 然而概率理論能夠保證，應(yīng)用蒙特卡洛方法隨機計算106

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

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

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

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

26、年度付出的總報酬最少(即 4 個季度開始時保姆總數(shù)量之和最小)為目標，則問題的數(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ù)需求 各季度初的儲備量 雖然模型要求 x1, x2, x3, x4, S1, S2, S3, S4 為正整數(shù)，

27、但因為保姆數(shù)量較大，加之非整數(shù)因子 0.85 的影響，因此可以近似看作實數(shù)來處理。 其次，下一年各季度保姆服務(wù)的需求只是估計值，什么樣的數(shù)學(xué)解都無法作為實際問題的精確解。 因此，采用舍入湊整的方法來求解。 將上述整數(shù)規(guī)劃模型松弛成線性規(guī)劃模型，用 Matlab 求解得： 對上述結(jié)果取整，4 個季度開始時公司新招聘的保姆數(shù)量分別為 0, 15, 0, 59 人，每個季度開始時保姆總數(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ù)需求 再帶入各季度初儲備要求的約束條件 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雖不滿足儲備需求，但基本不影響制定招聘計劃。 于是，這個招聘問題的解為： 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 因此，公司可以擬定如下的招聘計劃： 第二季度開始時公司新招聘 15 人，第四季度開始時公司新招聘 59 人。 接下來討論哪些季度需求的增加不會影響招聘計劃。 由于春季開始時公司擁有 S1 = 120 名保姆，且春季開

30、始時公司招聘的保姆數(shù)量為 x1 = 0，因此，根據(jù)約束條件 65S1 6000 + 5x1 知，春季需求的增加不影響招聘計劃，且可以增加65S1 6000 = 1800(人日) 類似地，夏季和秋季需求的增加也不影響招聘計劃，且可以增加 30 和 935(人日)。 問題(2)的求解 設(shè) 4 個季度開始時公司新招聘的保姆數(shù)分別為 x1, x2, x3, x4 人，4 個季度結(jié)束時公司解雇的保姆數(shù)分別為 y1, y2, y3, y4 人，4 個季度開始時保姆總數(shù)量分別為 S1, S2, S3, S4 人。 以本年度付出的總報酬最少(即 4 個季度開始時保姆總數(shù)量之和最小)為目標，則問題的數(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 求解得： 對上述結(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ù)需求 再帶入各季度初儲備要求的約束條件 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雖不滿足儲備需求，但基本不影響制定招聘計劃。 于是，這個招聘問題的解為： 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 因此，公司可以擬定如下的招聘計劃： 第二季度開始時公司新招聘 15 人，第二季度結(jié)束時解雇 15 人；第四季度開始時公司新招聘 72 人。 此時，目標函數(shù)值為 466，比不允許解雇時的目標函數(shù)值(479)略有減少。 整數(shù)規(guī)劃補充范例整數(shù)規(guī)劃補充范例合理下料問題合理下料問題 鋼管零售商所進的原料鋼管長度都是 19m。銷售時零售商需要按照客戶的要求進行切割。 現(xiàn)有一客戶需要 50 根長 4m、20 根長 6m 和 15 根長 8m 的鋼管。應(yīng)如何下料最節(jié)??？

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

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

37、切割的原料鋼管的根數(shù)，若以切割后剩余的總余料量最小為目標，則按照表 1 最后一列可得 min Z1 = 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 若以切割原料鋼管的總根數(shù)最少為目標，則有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)當是非負整數(shù)(用 Z 表示整數(shù)集合，Z+ 表示非負整數(shù)集合)xiZ+, i =

38、1, 2, , 7 于是，問題(1)的數(shù)學(xué)模型為： 模型 1： 模型 2：7 , , 2 , 1 ,152203250234s.t. 3333min75365425432176543211ixxxxxxxxxxxxxxxxxxxxZiZ7 , , 2 , 1 ,152203250234s.t. min75365425432176543212ixxxxxxxxxxxxxxxxxxxxZiZ 這兩個模型均是整數(shù)規(guī)劃模型。首先將原問題松弛為線性規(guī)劃問題，求解后再取整。 應(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ī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ù)解帶入約束條件驗證，不滿足約束條件的要求： 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 的鋼管，它們的總長為 16m，故再增加一個模式 3(即2, 0, 1)給出的切割