運(yùn)籌學(xué)第05章整數(shù)規(guī)劃

1、第五章 整數(shù)規(guī)劃(Integer Programming)整數(shù)規(guī)劃的基本問(wèn)題及其數(shù)學(xué)模型割平面法分支定界法0-1整數(shù)規(guī)劃指派問(wèn)題WinQSB軟件應(yīng)用第一節(jié) 整數(shù)規(guī)劃的基本問(wèn)題及其數(shù)學(xué)模型一、問(wèn)題的提出 實(shí)際工作中的某些規(guī)劃問(wèn)題要求部分變量或全部變量取整數(shù)值，我們稱這樣的問(wèn)題為整數(shù)規(guī)劃問(wèn)題(Integer Programming，IP)。不考慮整數(shù)要求，由其他約束條件和目標(biāo)函數(shù)構(gòu)成的規(guī)劃問(wèn)題稱為該整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題(Slack Problem)。若松弛問(wèn)題是一個(gè)線性規(guī)劃問(wèn)題，我們稱該整數(shù)規(guī)劃問(wèn)題為整數(shù)線性規(guī)劃(Integer Linear ProgrammingILP)。 【例5-1】某工地

2、需要長(zhǎng)度不同、直徑相同的成套鋼筋，每套鋼筋由兩根7米長(zhǎng)和七根2米長(zhǎng)的鋼筋組成。現(xiàn)有長(zhǎng)15米的圓鋼毛坯150根，應(yīng)如何下料，使廢料最少？ 解：本題中沒(méi)有說(shuō)明15米長(zhǎng)的圓鋼毛坯有哪些下料方式，故需要首先找出下料方式。將15米長(zhǎng)的圓鋼毛坯切割為7米和2米兩種長(zhǎng)度的鋼筋有三種方式，如表5-1所示。 170304121021廢料(米)2米長(zhǎng)的鋼筋(根)7米長(zhǎng)的鋼筋(根)下料方式 設(shè) 分別表示采用第1、2、3種下料方式所切割的圓鋼毛坯數(shù)目。則廢料可表示為下列形式： 看約束條件。首先，工地需要的是成套鋼筋，故7米長(zhǎng)和2米長(zhǎng)的鋼筋數(shù)之比應(yīng)滿足2：7，用線性方程來(lái)表示，即： 整理得： 即： 綜合分析，問(wèn)題的數(shù)學(xué)

3、模型為： 【例5-2】現(xiàn)有資金總額為B，可供投資項(xiàng)目有 n 個(gè)，項(xiàng)目 j 所需投資額和預(yù)期收益分別為 aj 和 cj ( j1,2，n )。同時(shí)，由于種種原因，有三個(gè)附加條件：第一，若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2，反之則不一定；第二，項(xiàng)目3和項(xiàng)目4中至少選擇一個(gè)；第三，項(xiàng)目5、項(xiàng)目6和項(xiàng)目7中恰好選擇兩個(gè)。另外，圓鋼毛坯總數(shù)為150根，故 還應(yīng)滿足下面這個(gè)條件，即： 應(yīng)當(dāng)怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大？則問(wèn)題可表示為： 【例5-3】工廠 A1 和 A2 生產(chǎn)某種物資，由于該種物資供不應(yīng)求，故需要再建一家工廠，相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1、B2、B3、B4

4、四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij 見(jiàn)表5-2。 解：每一個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能，令： 表5-2150300400350需求量(千噸/年)2005254A42002167A36007538A24004392A1生產(chǎn)能力(千噸/年)B4B3B2B1 cij BjAi 工廠 A3 或 A4 開(kāi)工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬(wàn)元或1500萬(wàn)元?，F(xiàn)要決定應(yīng)該建設(shè)工廠 A3 還是 A4 ，才能使今后每年的總費(fèi)用(即全部物資運(yùn)費(fèi)和新工廠生產(chǎn)費(fèi)用之和)最少。 解：這是一個(gè)物資運(yùn)輸問(wèn)題，其特點(diǎn)是事先不能確定應(yīng)該建A3 和 A4 中的哪一個(gè)，因而不知

5、道新廠投產(chǎn)后的實(shí)際生產(chǎn)費(fèi)用。為此，引入0-1變量： 設(shè) xij 為由 Ai 運(yùn)往 Bj 物資數(shù)量(千噸)，(i,j1,2,3,4)。則問(wèn)題的數(shù)學(xué)模型為： 二、整數(shù)規(guī)劃模型的一般形式及解的特點(diǎn) 整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式為： 一般來(lái)說(shuō)，整數(shù)線性規(guī)劃可分為以下幾種類型： 1. 純整數(shù)線性規(guī)劃(Pure Integer Linear Programming)：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃，也稱為全整數(shù)規(guī)劃。 2. 混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming)：指決策變量中一部分必須取整數(shù)值，而另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。 3. 0-

6、1整數(shù)線性規(guī)劃(Zero-one Integer Linear Programming)：指決策變量只能取 0 或 1 兩個(gè)值的整數(shù)線性規(guī)劃。 第二節(jié) 割平面法 割平面法由高莫累(Gomory)于1958年提出。其基本思想是放寬變量的整數(shù)約束，首先求對(duì)應(yīng)的松弛問(wèn)題最優(yōu)解，當(dāng)某個(gè)變量xi不滿足整數(shù)約束時(shí)，尋找一個(gè)約束方程并添加到松弛問(wèn)題中，其作用是割掉非整數(shù)部分，縮小原松弛問(wèn)題的可行域，最后逼近整數(shù)問(wèn)題的最優(yōu)解。一、割平面法的基本思想 ILPLP是整數(shù)解？單純形法求解建立割平面方程，加入LP對(duì)偶單純形法求解計(jì)算結(jié)束是否 考慮松弛問(wèn)題為標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題的純整數(shù)規(guī)劃問(wèn)題(ILP)： 假設(shè)約束條件中

7、 aij(i1,2,m ；j1,2，,n)和 bi(i1,2,m)均為整數(shù)(若不為整數(shù)，可令等式兩邊同乘一個(gè)倍數(shù)化為整數(shù))。 下面先通過(guò)一個(gè)例子來(lái)說(shuō)明割平面法的基本思想。 【例5-5】 將該問(wèn)題圖示如下圖 ： 從圖(a)中可以看出，松弛問(wèn)題的最優(yōu)解為X*=(5/3，5/2)T，它不是一個(gè)整數(shù)解。因此我們?cè)O(shè)法給原線性規(guī)劃問(wèn)題增加一個(gè)約束條件，從而把包括X*在內(nèi)的一部分不含整數(shù)點(diǎn)的可行域從原可行域中分割出去。再求增加了這個(gè)約束條件后的新的線性規(guī)劃問(wèn)題的最優(yōu)解。 在上圖的基礎(chǔ)上，增加約束條件: 從圖5-1(b)中可以看出，當(dāng)我們?cè)黾恿思s束條件“后，得到新的最優(yōu)解X* = (2，2)T，它便是整數(shù)規(guī)劃

8、問(wèn)題最優(yōu)解。因此，割平面法的關(guān)鍵就在于如何尋找這類新的約束條件。 二、Gomory約束 假設(shè)用單純形法求得的線性規(guī)劃問(wèn)題最優(yōu)解不是整數(shù)解，其中必然有某個(gè)或某幾個(gè)基變量不為整數(shù)。記 B 為松弛問(wèn)題的最優(yōu)基，則問(wèn)題的基最優(yōu)解為： (2,2)不妨設(shè)第r 個(gè)分量 不為整數(shù)，根據(jù)最優(yōu)單純形表可得： (5.1)將 和 分成整數(shù)部分和非負(fù)真分?jǐn)?shù)之和，即：代入上式得：(5.2)(5.3)(5.4)移項(xiàng)，得：(5.5) 因?yàn)樽兞勘仨毴≌麛?shù)，即上式左邊必須是整數(shù)，從上式右邊看，因?yàn)?fr1，所以不能為正，即： 割平面方程(5.6)即: (5.7)三、割平面法的算法步驟 步驟1：將約束條件系數(shù)及右端項(xiàng)化為整數(shù)，用單

9、純形法求解整數(shù)規(guī)劃問(wèn)題(ILP)的松弛問(wèn)題(LP)。設(shè)得到最優(yōu)基B，相應(yīng)的基最優(yōu)解為X*。 步驟2：判別X*的所有分量是否全為整數(shù)？如是，則X*即為(ILP)的最優(yōu)解，算法終止；若否，則取X*中分?jǐn)?shù)最大的分量 ，引入割平面(5.7)。 步驟3：將式(5.7)引入松弛變量后加入原最終單純形表，用對(duì)偶單純形法繼續(xù)求解。轉(zhuǎn)步驟2。 【例】用割平面法求解數(shù)規(guī)劃問(wèn)題不考慮整數(shù)要求，化為標(biāo)準(zhǔn)型：標(biāo)準(zhǔn)型的技術(shù)系數(shù)矩陣為：Cj1100CBXBbx1x2x3x40 x3621100 x420450111001 x15/3105/6-1/61x28/301-2/31/300-1/6-1/61 x1311/21/2

10、00 x4803-2101/2-1/20在松弛問(wèn)題最優(yōu)解中，x1, x2 均為非整數(shù)解，由上表有：將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和: CBXBbx1x2x3x41 x15/3105/6-1/61x28/301-2/31/300-1/6-1/6 以上式子只須考慮一個(gè)即可，解題經(jīng)驗(yàn)表明，考慮式子右端最大真分?jǐn)?shù)的式子，往往會(huì)較快地找到所需割平面約束條件。以上兩個(gè)式子右端真分?jǐn)?shù)相等，可任選一個(gè)考慮。 引入松弛變量 x5 后得到下式，將此約束條件加到上表中，繼續(xù)求解。 現(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右邊得： 移項(xiàng)的割平面方程為： 等式右邊滿足： 0 x5-2/300-1/3-1/31Cj1100

11、0CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/30j00-1/6-1/601x10100-15/21x240101-20 x320011-3j0000-1/21 x121010-1/21x2201-1010 x420011-3j0000-1/2【例5-6】用割平面法求解例5-5。 首先，將整數(shù)約束去掉，將松弛問(wèn)題化為標(biāo)準(zhǔn)形: 約束條件的系數(shù)為: 因基變量x15/3，x25/2，均為非整數(shù)，故該最優(yōu)解不是整數(shù)規(guī)劃的可行解。若以變量 x1 所在的行為源行，得到相應(yīng)的割平面為： 001110205x40012310 x30 x4x3x2x1bXBCB00

12、1101/32/3110/3x10-1/31/30j10205x401-1/31/3015/3x1-1/6-1/300j1/20105/2x211(5.8)左端加入松弛變量，得到： (5.9)將式(5.9)加入上表中，用對(duì)偶單純形法繼續(xù)求解如下表： 0-1/6-1/300j1-2/3-1/300-2/3x5001/20105/2x210-1/31/3015/3x11x5x4x3x2x1bxBcB000112x1-1/40-1/400j-3/211/2001x403/40-1/4102x21-1/201/2011因此，原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為X*=(2，2)T，其最優(yōu)值z(mì)*=4。 將上式代入割平

13、面方程：整理后得到： 根據(jù)原整數(shù)規(guī)劃問(wèn)題的約束條件可以得到：得到： 圖解法中割平面方程 如何得到？原整數(shù)規(guī)劃問(wèn)題標(biāo)準(zhǔn)化后其形式為： 第三節(jié) 分支定界法 分枝定界法是在20世紀(jì)60年代初由Land Doing和Dakin等人提出的適合于解純整數(shù)或混合正數(shù)規(guī)劃問(wèn)題。 分支定界法實(shí)際是一種隱枚舉法或部分枚舉法，它是在枚舉法基礎(chǔ)上的改進(jìn)，在枚舉過(guò)程中逐批把一部分可行解排斥在考察范圍之外，從而大大減少了計(jì)算量。分支定界法的關(guān)鍵是分支和定界。 若松弛問(wèn)題的最優(yōu)解不符合整數(shù)要求，假設(shè)變量不符合整數(shù)要求， 為不超過(guò) 的最大整數(shù)，則在松弛問(wèn)題中分別加入兩個(gè)約束條件： 和 ，以形成兩個(gè)子問(wèn)題。 一、分支定界法的基

14、本思想 兩個(gè)子問(wèn)題的可行域的并集包含了原問(wèn)題(ILP)的全部可行解，而包括原最優(yōu)解在內(nèi)的松弛問(wèn)題的部分非整數(shù)解被剔除了。然后分別求解兩個(gè)子問(wèn)題，根據(jù)需要，各子問(wèn)題可以再產(chǎn)生自己的子問(wèn)題。這個(gè)過(guò)程就是分支。 在分支過(guò)程中，若某個(gè)子問(wèn)題的最優(yōu)解為整數(shù)解，其目標(biāo)函數(shù)值就是整數(shù)規(guī)劃問(wèn)題的一個(gè)“界限”，可以此作為判斷其他分支優(yōu)劣的一個(gè)依據(jù)。二、分支定界法的一般步驟 【例5-7】用分支定界法求解例5-5。 解：根據(jù)前面的求解知道，(LP)的最優(yōu)解為 x15/3，x25/2，z25/6。 若某一子問(wèn)題最優(yōu)解(無(wú)論是否為整數(shù)解)的目標(biāo)函數(shù)值小于或等于該界限，則可以將該子問(wèn)題剔除而不予考慮了。若有其他子問(wèn)題的最

15、優(yōu)解為整數(shù)解，則將其目標(biāo)函數(shù)值與原來(lái)的界限相比較，取更優(yōu)的一個(gè)作為新的界限。這個(gè)過(guò)程就是定界。 由于(LP)的最優(yōu)解不是整數(shù)解，可任選一個(gè)變量進(jìn)行分支。若選 x15/3進(jìn)行分支，則分支出的約束條件為： (5.10)和 (5.10) 分別將上述兩個(gè)約束條件加入(LP)中，因此原問(wèn)題的松弛問(wèn)題(LP)被劃分為兩個(gè)子問(wèn)題： 0,21xx 再求解(LP2)：最優(yōu)解為 x11，x25/2，最優(yōu)值 z7/2最優(yōu)解為 x12，x22，最優(yōu)值 z4故取 z4 作為(ILP)最優(yōu)值的一個(gè)下界。 先求解(LP1)： 由于(LP1)的最優(yōu)值為7/24，故其子問(wèn)題的目標(biāo)函數(shù)值不會(huì)超過(guò)7/2，也不會(huì)超過(guò)4。因此(LP1

16、)是一個(gè)失去希望的問(wèn)題，不必再對(duì)它進(jìn)行分支。若(LP1)的最優(yōu)值大于4，需要對(duì)它進(jìn)一步分支。 上述求解過(guò)程可用圖5-4來(lái)說(shuō)明： 分支定界法解整數(shù)規(guī)劃的一般步驟可歸結(jié)如下： 步驟1：取(ILP)的目標(biāo)函數(shù)值的初始下界 。用單純形法求解整數(shù)規(guī)劃問(wèn)題(ILP)的松弛問(wèn)題(LP)。 步驟2：若問(wèn)題(LP)不可行，則(ILP)也不可行，算法終止；若問(wèn)題(LP)的最優(yōu)解X*為(ILP)的可行解，則它就是(ILP)的最優(yōu)解，算法終止。若問(wèn)題(LP)的最優(yōu)解存在，但不滿足(ILP)的整數(shù)要求，轉(zhuǎn)步驟3。 步驟3：任選X*中不滿足整數(shù)要求的一個(gè)變量 進(jìn)行分支，即對(duì)問(wèn)題(LP)分別增加約束條件 和 ，形成兩個(gè)子問(wèn)

17、題，并求解。轉(zhuǎn)步驟4。 步驟4：考察所有子問(wèn)題，有以下四種情況： a.若某個(gè)子問(wèn)題的最優(yōu)解也是問(wèn)題(ILP)的可行解，則將它的目標(biāo)函數(shù)值與 作比較，并取較優(yōu)的一個(gè)作為新的界限 。如所有子問(wèn)題都已考察完畢，則保留下來(lái)的 及其對(duì)應(yīng)的解即為問(wèn)題(ILP)的最優(yōu)解。 b. 若某個(gè)子問(wèn)題的最優(yōu)解不是(ILP)的可行解，且其最優(yōu)值不如 ，則將這一分支刪掉。 c. 若某個(gè)子問(wèn)題不可行，則將這一分支刪掉。 d. 若某個(gè)子問(wèn)題的最優(yōu)解不是(ILP)的可行解，且其最優(yōu)值優(yōu)于 ，則該問(wèn)題為待考察的問(wèn)題。如有多個(gè)問(wèn)題待考察，優(yōu)先對(duì)其中最優(yōu)值最大的一個(gè)子問(wèn)題進(jìn)行考察，轉(zhuǎn)步驟3。 解：用圖解法解對(duì)應(yīng)的(LP)問(wèn)題，如表所

18、示，獲得最優(yōu)解?！纠坑梅种Фń绶ㄇ蠼庹麛?shù)規(guī)劃問(wèn)題(3.25,2.5)x1x2 選 x2 進(jìn)行分支，即增加兩個(gè)約束，x2 2和 x23，分支出以下兩個(gè)問(wèn)題：x1x2x1x2(3.5,2)用圖解法求解 LP1 問(wèn)題：用圖解法求解 LP2 問(wèn)題：x1x2(2.5,3) 對(duì)(LP1)繼續(xù)分支，加入約束 x13和 x14，分支出以下兩個(gè)問(wèn)題：x1x2(3,2)用圖解法求解 LP3 問(wèn)題：x1x2(4,1)用圖解法求解 LP4 問(wèn)題：用圖解法求得 LP2 問(wèn)題的目標(biāo)函數(shù)值為：所以 LP2 問(wèn)題不需要進(jìn)行繼續(xù)分支。樹(shù)形圖如下：x22x23x13LPLP1LP2LP3LP4x1=13/4, x2=5/2Z(

19、0) 59/4=14.75x1=7/2, x2=2Z(1) 29/2=14.5x1=5/2, x2=3Z(4) 27/2=13.5x1=3, x2=2Z(2) 13x1=4, x2=1Z(3) 14x14第四節(jié) 01整數(shù)規(guī)劃一、0-1變量的應(yīng)用 第一節(jié)中我們討論過(guò)0-1變量，即只能取0或1的變量，它是邏輯變量，通常用來(lái)表示在是與否之間二選一的問(wèn)題，如某個(gè)方案A是否被選中，可用下面的0-1變量來(lái)表示： 當(dāng)采取方案A時(shí) 當(dāng)不采取方案A 時(shí)【例5-8】含有相互排斥的約束條件的問(wèn)題。 設(shè)某廠生產(chǎn)第j 種產(chǎn)品的數(shù)量為 xj (j=1，2，3)，其材料可在甲或乙中選擇一種，當(dāng)選擇甲或乙時(shí)，相應(yīng)的材料消耗的

20、約束條件分別為： 和(5.12 a)(5.12 a)試問(wèn)這類相互排斥的約束條件如何體現(xiàn)在模型中？ 解：引入0-1變量： 和 因而，兩個(gè)相互排斥的約束條件可用下列線性約束條件統(tǒng)一起來(lái)： 其中M是一個(gè)充分大的數(shù)。 若y1=1，而y2=0，即選用材料乙，由(5.12d) 式得：式(5.12c)自然成立； 若y1=0，而y2=1，即選用材料甲，由(5.12c) 式得：式(5.12d)自然成立. 【例5-9】固定費(fèi)用問(wèn)題。有一種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單位消耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見(jiàn)表5-5。要求制訂一個(gè)生產(chǎn)計(jì)劃，使總收益最大。 12108單位售價(jià)2001

21、50100固定費(fèi)用654 單位可變費(fèi)用100321C300432B500842A資源量IIIIII 單耗量資源產(chǎn)品解：設(shè) xj 表示三種產(chǎn)品的產(chǎn)量(j=1，2，3)。 引入0-1變量： 則問(wèn)題的數(shù)學(xué)模型可歸結(jié)如下： 如果生產(chǎn)第 j 種產(chǎn)品，則其產(chǎn)量xj0，由xjMjyj 知，yj1。相應(yīng)的固定費(fèi)用將被考慮，Mj 為 xj 的某個(gè)上界。 二、0-1型整數(shù)規(guī)劃的解法 0-1型規(guī)劃是一類特殊的整數(shù)規(guī)劃，因?yàn)樽兞恐挥?或1兩個(gè)可能的取值，故最多有 2n 個(gè)可行解，理論上可以用枚舉法進(jìn)行求解。但當(dāng) n 較大時(shí)，采用完全枚舉法求解幾乎是不可能的。 隱枚舉法是求解0-1整數(shù)規(guī)劃問(wèn)題的一種比較簡(jiǎn)便的方法。其實(shí)

22、質(zhì)也是一種分支定界法。 隱枚舉法是是在 2n 個(gè)可能的變量組合中，只有一部分是可行解。只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件，就不必再檢驗(yàn)是否滿足其它約束。 如所有約束條件都滿足，就是0-1規(guī)劃的一個(gè)可行解，可根據(jù)相應(yīng)的目標(biāo)函數(shù)值產(chǎn)生一個(gè)過(guò)濾條件，對(duì)于目標(biāo)函數(shù)值劣于該可行解的變量組合不必再去檢驗(yàn)其可行性。在以后的求解過(guò)程中，如發(fā)現(xiàn)某個(gè)可行解比原來(lái)保留的可行解更優(yōu)，則用它替換原來(lái)的過(guò)濾條件。 確定初始解滿足約束？產(chǎn)生界限是停止檢查約束否分支，計(jì)算目標(biāo)值目標(biāo)值優(yōu)？剪支否是【例5-11】求解0-1整數(shù)規(guī)劃 (5.13a)(5.13b)(5.13c)(5.13d)(1，1，1)(1，1，0)(1，

23、0，1)(1，0，0)(0，1，1)(0，1，0)(0，0，1)(0，0，0)dcba過(guò)濾條件約束條件z 值(x1，x2，x3)0z 05z 5-2338z 816【例5-12】求解0-1整數(shù)規(guī)劃 步驟1：將問(wèn)題轉(zhuǎn)化為如下標(biāo)準(zhǔn)形式： 如目標(biāo)函數(shù)為max z，令 ，可化為 。如某個(gè)變量 的系數(shù)為負(fù)，令 ，使系數(shù)變正。 其中cj0，且c1c2cn。 如約束條件為，兩邊同乘(-1)；如約束條件為等式，可令變量 ，代入目標(biāo)函數(shù)和其它約束條件中，將 xn 消掉。 按目標(biāo)函數(shù)中系數(shù)由小到大的順序重新排列變量，并將約束條件中的排列順序做相應(yīng)改變。 目標(biāo)函數(shù)進(jìn)行調(diào)整： (5.14a)(5.14b)數(shù)學(xué)模型調(diào)整

24、為： 步驟2：令所有變量取0，求出目標(biāo)函數(shù)值，代入約束條件檢查是否可行，如果可行即為問(wèn)題的最優(yōu)解；否則轉(zhuǎn)下一步。 令 ， 得-10，代入兩個(gè)約束條件： 各約束條件均不滿足。 步驟3：分支和定界。 依次令各變量分別取0或1，將問(wèn)題劃分為兩個(gè)子問(wèn)題，分別檢查是否可行，如不可行繼續(xù)對(duì)邊界值較小的子問(wèn)題分支，直到找出一個(gè)可行解為止，這時(shí)得到 值的一個(gè)上界。步驟4：考察所有子問(wèn)題，有以下四種情況： 若某個(gè)子問(wèn)題的邊界值對(duì)應(yīng)原問(wèn)題的可行解，則將它的邊界值與保留的 值作比較，并取較優(yōu)的一個(gè)作為新的 值。如所有子問(wèn)題都已考察完畢，則保留下來(lái)的 值及其對(duì)應(yīng)的解即為0-1整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。 若某個(gè)子問(wèn)題的邊界

25、值大于保留下來(lái)的 值，不管其是否可行，則將這一分支剪掉。 若某個(gè)子問(wèn)題不可行，則將這一分支剪掉。 若某個(gè)子問(wèn)題可行且邊界值優(yōu)于 值，但該邊界值對(duì)應(yīng)的解不是可行解，則該問(wèn)題待考察。如有多個(gè)問(wèn)題待考察，優(yōu)先對(duì)其中最優(yōu)值最大的一個(gè)子問(wèn)題進(jìn)行考察，轉(zhuǎn)步驟3。(0，0，1，0，1)(0，0，1，1，0)(0，0，0，1，0)(0，1，0，1，0)(0，1，1，0，0)(0，0，1，0，0)(1，0，1，0，0)(1，1，0，0，0)(0，1，0，0，0)(1，0，0，0，0)(0，0，0，0，0)(x2，x3，x5，x4，x1)ba備注約束條件z 值序號(hào)上述求解過(guò)程也可用表格表示： 21-3-1-5-3

26、-4-6-8-10 -4，剪枝 -4，剪枝 可行 -4，剪枝3 -4，剪枝 -4，剪枝 -4，剪枝所以，最優(yōu)解： 即原問(wèn)題的最優(yōu)解為： 第五節(jié) 指派問(wèn)題一、指派問(wèn)題的數(shù)學(xué)模型 指派問(wèn)題又稱分配問(wèn)題，是指將 m 項(xiàng)工作分配 n 個(gè)工人去完成(通常mn)，應(yīng)如何分工使總工時(shí)或總費(fèi)用最少的一類問(wèn)題。 現(xiàn)有 n 項(xiàng)工作分配 n 個(gè)工人去完成，已知工人 j 完成工作i需要花費(fèi)時(shí)間 cij 。要求每項(xiàng)工作只能由一個(gè)工人去完成，每個(gè)工人只能完成一項(xiàng)工作。應(yīng)如何分工，使總工時(shí)最少？ 在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n 項(xiàng)不同的任務(wù)，需要n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完

27、成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。 這類問(wèn)題一般有兩個(gè)要求：一是每項(xiàng)工作只能由一個(gè)工人去完成；二是每個(gè)工人只能完成一項(xiàng)工作。這類問(wèn)題的標(biāo)準(zhǔn)提法如下： AnA2A1BnB2B1工作工人設(shè)： 則該問(wèn)題的數(shù)學(xué)模型可寫(xiě)為： 【例5-13】某工廠要生產(chǎn)四種產(chǎn)品，該工廠有四個(gè)車(chē)間都可以生產(chǎn)這四種產(chǎn)品。但由于設(shè)備情況與技術(shù)情況不同，所以生產(chǎn)成本不同，其單位產(chǎn)品的生產(chǎn)成本如下表所示： 問(wèn)應(yīng)當(dāng)怎樣分配這四種產(chǎn)品到各車(chē)間，才能使總的生產(chǎn)成本最小？試建立該問(wèn)題的數(shù)學(xué)模型。

28、 6443車(chē)間46233車(chē)間35415車(chē)間210454車(chē)間1產(chǎn)品4產(chǎn)品3產(chǎn)品2產(chǎn)品1 產(chǎn)品車(chē)間解：這是一個(gè)標(biāo)準(zhǔn)形式的指派問(wèn)題。引入0-1變量： 這個(gè)問(wèn)題的約束條件如下：(1)每個(gè)車(chē)間只能生產(chǎn)一種產(chǎn)品，即：簡(jiǎn)寫(xiě)為： （i =1,2,3,4） 則問(wèn)題的數(shù)學(xué)模型可歸結(jié)為： (2)一種產(chǎn)品只能由一個(gè)車(chē)間生產(chǎn)，即： 簡(jiǎn)寫(xiě)為：（j =1,2,3,4） (3)變量工 xij 必須等于0或1，即 xij =0或1。 二、匈牙利算法 分配問(wèn)題是 0-1 規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。 庫(kù)恩(W.W.Kuhn)于

29、1955年提出了指派問(wèn)題的解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有零元素的最小直線數(shù)，習(xí)慣上稱之為匈牙利解法。 分配問(wèn)題最優(yōu)解的以下性質(zhì)：若從系數(shù)矩陣(cij)的某行(或某列)各元素分別減去該行（列）的最小元素，得到新矩陣(cij),那么以(cij)為系數(shù)矩陣求得的最優(yōu)解和利用原系數(shù)矩陣求得的最優(yōu)解相同。 匈牙利算法的一般步驟可以表述如下： 步驟1：變換系數(shù)矩陣。 先把系數(shù)矩陣各行分別減去本行的最小元素，再把各列分別減去本列的最小元素，使系數(shù)矩陣中各行各列都至少有一個(gè)零元素，且不出現(xiàn)負(fù)數(shù)。轉(zhuǎn)步驟2。 在新矩陣中

30、找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為： 從只有一個(gè)0元素的行開(kāi)始，給這個(gè)0元素加。然后劃去所在列的其它0元素，記作 ；這表示這列所代表的任務(wù)已指派完。 給只有一個(gè)0元素的列中的0元素加 ；然后劃去所在行的0元素，記作 。 反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。 步驟2：確定獨(dú)立零元素。 若仍有沒(méi)有劃的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開(kāi)始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加。 若

31、某行(某列)只有一個(gè)零元素，將該零元素加一個(gè)三角符號(hào)()，同時(shí)將該零元素所在列(行)的其它零元素劃去。如此反復(fù)進(jìn)行，直到系數(shù)矩陣中所有零元素都被標(biāo)注或被劃去。 【例5-14】已知指派問(wèn)題的系數(shù)矩陣為： 解：首先，將各行分別減去本行的最小元素，然后對(duì)各列也如此，即：4123其次，確立獨(dú)立零元素。 因獨(dú)立零元素有4個(gè)，故得到最優(yōu)解： 若元素的數(shù)目m 等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。 若獨(dú)立零元素有 n 個(gè)，則令獨(dú)立零元素位置對(duì)應(yīng)的變量取1，其它變量取0，這樣得到的矩陣X即為最優(yōu)分配方案。若獨(dú)立零元素不足 n 個(gè)，轉(zhuǎn)步驟3。 步驟3：做能覆蓋所有零元素的最少

32、直線組合。 最優(yōu)解表明：車(chē)間1生產(chǎn)產(chǎn)品1，車(chē)間2生產(chǎn)產(chǎn)品2，車(chē)間3生產(chǎn)產(chǎn)品3，車(chē)間4生產(chǎn)產(chǎn)品4，得到最優(yōu)值為: 對(duì)沒(méi)有標(biāo)的行打“”； 對(duì)打“”行中被劃掉的零元素所在列打“”； 對(duì)打“”列中標(biāo)的零元素所在行打“”； 重復(fù)和，直到再也不能找到可打“”行或列為止。 對(duì)未打“”的行畫(huà)一直線，對(duì)打“”的列畫(huà)一直線，這樣就得到覆蓋所有零元素的最少直線組合。轉(zhuǎn)步驟4。 步驟4：繼續(xù)變換系數(shù)矩陣。 【例5-15】已知指派問(wèn)題的系數(shù)矩陣如下：用匈牙利算法求解。 取未被直線覆蓋的元素中的最小值，令打“”行中各元素減去該最小值，同時(shí)令打“”列中各元素加上該最小值以消除負(fù)數(shù)。轉(zhuǎn)步驟2。 解：首先，變換成本矩陣。 其次

33、，確立獨(dú)立零元素。 因獨(dú)立零元素只有3個(gè)，故不能得到最優(yōu)分配方案。需要繼續(xù)進(jìn)行下面的步驟。 第三步，做能覆蓋所有零元素的最少直線組合。 第四步，變換矩陣。在新的系數(shù)矩陣中確定獨(dú)立零元素。 未被直線覆蓋的元素中的最小值為2，將第一、四行各元素減2，再將第一列各元素加2，得到： 由于獨(dú)立零元素有4個(gè)，因此得到最優(yōu)分配方案： 最優(yōu)值: 【例】有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如下表所示：求解過(guò)程如下：52895丁41013丙8954乙21176甲DCBA任務(wù)人員第一步，變換系數(shù)矩陣：?jiǎn)柸绾畏峙扇蝿?wù)，可使總時(shí)間最少？ 找到 3 個(gè)獨(dú)立零元素，但 m