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

1、第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃數(shù)學(xué)模型整數(shù)規(guī)劃數(shù)學(xué)模型純整數(shù)規(guī)劃的求解純整數(shù)規(guī)劃的求解01規(guī)劃的求解規(guī)劃的求解分支定界法分支定界法割平面法割平面法指派問(wèn)題指派問(wèn)題非標(biāo)準(zhǔn)形式的指派問(wèn)題非標(biāo)準(zhǔn)形式的指派問(wèn)題一、整數(shù)規(guī)劃的模型一、整數(shù)規(guī)劃的模型 很多實(shí)際規(guī)劃問(wèn)題都屬于整數(shù)規(guī)劃問(wèn)題很多實(shí)際規(guī)劃問(wèn)題都屬于整數(shù)規(guī)劃問(wèn)題 1. 變量是人數(shù)、機(jī)器設(shè)備臺(tái)數(shù)或產(chǎn)品件數(shù)等都要變量是人數(shù)、機(jī)器設(shè)備臺(tái)數(shù)或產(chǎn)品件數(shù)等都要求是求是； 2. 對(duì)某一個(gè)項(xiàng)目要不要投資的決策問(wèn)題，可選用對(duì)某一個(gè)項(xiàng)目要不要投資的決策問(wèn)題，可選用一個(gè)邏輯變量一個(gè)邏輯變量 x，當(dāng)，當(dāng)x=1表示投資，表示投資，x=0表示不投資；表示不投資； 3.

2、 人員的合理安排問(wèn)題，當(dāng)變量人員的合理安排問(wèn)題，當(dāng)變量xij=1表示安排第表示安排第i人去做人去做 j工作，工作，xij=0表示不安排第表示不安排第i人去做人去做 j工工 作。邏作。邏輯變量也是只允許取整數(shù)值的一類(lèi)變量。輯變量也是只允許取整數(shù)值的一類(lèi)變量。 例例 合理下料問(wèn)題合理下料問(wèn)題 設(shè)用某型號(hào)的圓鋼下零件設(shè)用某型號(hào)的圓鋼下零件A1, A2,Am 的毛坯。在的毛坯。在一根圓鋼上下料的方式有一根圓鋼上下料的方式有B1,B2, Bn 種，每種下料方種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問(wèn)怎樣安排下料方式，使得即滿

3、足需要，如表所示。問(wèn)怎樣安排下料方式，使得即滿足需要，所用的原材料又最少所用的原材料又最少？零件 方 個(gè)數(shù) 式零件零 件毛坯數(shù)nBB 1mAA 1mbb 1mnmnaaaa 1111 設(shè)：設(shè)：xj 表示用表示用Bj (j=1.2n) 種方式下料根數(shù)種方式下料根數(shù) 模型：模型：11min (1.2)0 (1.2)njjnijjijjZxa xbimxjn且為整數(shù)零件 方 個(gè)數(shù) 式零件零 件毛坯數(shù)nBB 1mAA 1mbb 1mnmnaaaa 1111單 銷(xiāo)地廠址 價(jià)生產(chǎn)能力建設(shè)費(fèi)用銷(xiāo)量nmmmnmmmnnbbbfacccAfacccAfacccABnBB 21212222221211112111

4、21 例例 某公司計(jì)劃在某公司計(jì)劃在m個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)有有A1,A2Am ，他們的生產(chǎn)能力分別是他們的生產(chǎn)能力分別是a1,a2,am（假設(shè)（假設(shè)生產(chǎn)同一產(chǎn)品）。第生產(chǎn)同一產(chǎn)品）。第i i個(gè)工廠的建設(shè)費(fèi)用為個(gè)工廠的建設(shè)費(fèi)用為fi (i=1.2m),又有又有n個(gè)地點(diǎn)個(gè)地點(diǎn)B1,B2, Bn 需要銷(xiāo)售這種產(chǎn)品，其銷(xiāo)量需要銷(xiāo)售這種產(chǎn)品，其銷(xiāo)量分別為分別為b1.b2bn 。從工廠運(yùn)往銷(xiāo)地的單位運(yùn)費(fèi)為。從工廠運(yùn)往銷(xiāo)地的單位運(yùn)費(fèi)為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最??？建設(shè)費(fèi)用和總運(yùn)輸費(fèi)

5、用最省？ 設(shè)：設(shè)： xij 表示從工廠運(yùn)往銷(xiāo)地的運(yùn)量表示從工廠運(yùn)往銷(xiāo)地的運(yùn)量( (i=1.2m、j=1.2n), 1 ), 1 在在Ai建廠建廠 又設(shè)又設(shè) Yi （i=1.2m） 0 0 不在不在Ai建廠建廠 模型：模型：111min (1.2) (1.2)0,0 1 (1.21.2)mijijiiinijiijmijjiijiZc xf yxa yimxbjnxyimjn或、 例例 機(jī)床分配問(wèn)題機(jī)床分配問(wèn)題 設(shè)有設(shè)有m臺(tái)同類(lèi)機(jī)床，要加工臺(tái)同類(lèi)機(jī)床，要加工n種零件。已知各種零件種零件。已知各種零件的加工時(shí)間分別為的加工時(shí)間分別為a1,a2,an ，問(wèn)如何分配，使各機(jī)床，問(wèn)如何分配，使各機(jī)床的總

6、加工任務(wù)相等，或者說(shuō)盡可能平衡。的總加工任務(wù)相等，或者說(shuō)盡可能平衡。設(shè)：設(shè)： 1 1 分配第分配第i臺(tái)機(jī)床加工第臺(tái)機(jī)床加工第j j種零件；種零件； xij （i=1.2m,=1.2m,j j=1.2n=1.2n） 0 0 相反。相反。于是，第于是，第i臺(tái)機(jī)床加工各種零件的總時(shí)間為：臺(tái)機(jī)床加工各種零件的總時(shí)間為：njijjmixa1)2 . 1( 又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有11 (1.2)mijixjn 因此，求因此，求xij ，使得，使得121111minmax(,)1 (1.2)0 1 (1.2,1.2)nnnjjjjjmjjjjmi

7、jiijZa xa xa xxjnxim jn或例例 投資項(xiàng)目選取問(wèn)題投資項(xiàng)目選取問(wèn)題某單位擬利用閑置資金某單位擬利用閑置資金15 萬(wàn)元進(jìn)行對(duì)外投資，現(xiàn)有萬(wàn)元進(jìn)行對(duì)外投資，現(xiàn)有 5個(gè)投個(gè)投資項(xiàng)目可供選擇，所需資金及投資回報(bào)收益期望值為資項(xiàng)目可供選擇，所需資金及投資回報(bào)收益期望值為項(xiàng)目項(xiàng)目所需資金（萬(wàn)元）所需資金（萬(wàn)元）收益期望值（萬(wàn)元）收益期望值（萬(wàn)元） A B C D E 6 4 2 4 5 10 8 7 6 9A，B，C，D，E 之間的關(guān)系是：之間的關(guān)系是： A、C、E 三項(xiàng)中需且只能選一項(xiàng)；三項(xiàng)中需且只能選一項(xiàng)； B、D 兩項(xiàng)中需且只能選一項(xiàng)；兩項(xiàng)中需且只能選一項(xiàng)； 選選 C 必須先選必

8、須先選 D 。問(wèn)題：如何選擇投資決策，使總投資期望值最大？問(wèn)題：如何選擇投資決策，使總投資期望值最大？ 解解用用 xj 分別表示分別表示 A ，B ，C ，D ，E 的被選情況，則的被選情況，則于是投資總收益期望值：于是投資總收益期望值：54321967810 xxxxxz約束條件：約束條件： 資金總額限制：資金總額限制：155424654321xxxxx1,0,1, 2,3, 4,5jjxjj項(xiàng)目 被選中項(xiàng)目 未被選中 A，C，E 選且只選一項(xiàng)：選且只選一項(xiàng)：1531xxx項(xiàng)目項(xiàng)目所需資所需資金（萬(wàn)元）金（萬(wàn)元）收益期收益期望值（萬(wàn)元）望值（萬(wàn)元） A B C D E 6 4 2 4 5 1

9、0 8 7 6 9 選選 C 必須先選必須先選 D ：于是數(shù)學(xué)模型為以下于是數(shù)學(xué)模型為以下 01 規(guī)劃：規(guī)劃：31x ,41x ,40 x30 x或34xx5 , 4 , 3 , 2 , 110111554246967810max43425315432154321jxxxxxxxxxxxxxxxxxxzj，或 B，D 選且只選一項(xiàng)：選且只選一項(xiàng)：142 xx 例例 某人有一某人有一可以裝可以裝10公斤重、公斤重、0.025m3的物品。他準(zhǔn)備的物品。他準(zhǔn)備用來(lái)裝甲、乙兩種物品，每件物品的重量、體積和價(jià)值如表所示。用來(lái)裝甲、乙兩種物品，每件物品的重量、體積和價(jià)值如表所示。問(wèn)兩種物品各裝多少件，所裝

10、物品的總價(jià)值最大？問(wèn)兩種物品各裝多少件，所裝物品的總價(jià)值最大？ 解解 設(shè)甲、乙兩種物品各裝設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學(xué)模型為：件，則數(shù)學(xué)模型為：且均取整數(shù), 0,255 . 22108 . 02 . 134max21212121xxxxxxxxZ物品物品重量重量(公斤公斤/每件每件)體積體積(m3/每件每件)價(jià)值價(jià)值(元元/每件每件)甲甲乙乙1.20.80.0020.002543 例例 在上例中，假設(shè)此人在上例中，假設(shè)此人，最大載重量為，最大載重量為12公斤，其體積是公斤，其體積是0.02m3。背包和旅行箱只能選擇其一背包和旅行箱只能選擇其一，建立，建立下列幾種情形的數(shù)學(xué)模型，使所

11、裝物品價(jià)值最大。下列幾種情形的數(shù)學(xué)模型，使所裝物品價(jià)值最大。(1) 所裝物品不變；所裝物品不變；(2) 如果選擇旅行箱，則如果選擇旅行箱，則，價(jià)值分別，價(jià)值分別是是4和和3，載重量和體積的約束為，載重量和體積的約束為2025 . 1126 . 08 . 12121xxxx 解解 此問(wèn)題可以建立兩個(gè)整數(shù)規(guī)劃模型，但用一個(gè)模型描此問(wèn)題可以建立兩個(gè)整數(shù)規(guī)劃模型，但用一個(gè)模型描述述 更簡(jiǎn)單。引入更簡(jiǎn)單。引入01變量變量 yi，令，令2 , 10, 1iiiyi種方式裝載時(shí)不采用第，種方式裝載時(shí)采用第i=1,2 分別是采用背包及旅行箱裝載。分別是采用背包及旅行箱裝載。由于由于,上例上例約束左約束左邊不變

12、邊不變, 整數(shù)規(guī)劃數(shù)學(xué)模型為整數(shù)規(guī)劃數(shù)學(xué)模型為121212121212max431.20.8101222.5252010,011,2iiZxxxxyyxxyyyyxyi且取整數(shù)或(2) 不同載體所裝物品不一樣，數(shù)學(xué)模型不同載體所裝物品不一樣，數(shù)學(xué)模型為為121221211221211212max431.20.810( )1.80.612( )22.525( )1.5220( )1,0,01(1,2)iZxxxxMyaxxMybxxMycxxMydyyx xyi且均取整數(shù)或1212121.20.81022.525,0,xxxxxx且 均 取 整 數(shù)2025 .1126 .08 .12121xxx

13、x M為充分大的正為充分大的正數(shù)?？芍?dāng)使用背數(shù)?？芍?，當(dāng)使用背包時(shí)包時(shí)(y1=1，y2=0)，式，式(b)和和(d)是多余的；當(dāng)是多余的；當(dāng)使用旅行箱時(shí)使用旅行箱時(shí)(y1=0，y2=1)，式，式(a)和和(c)是多是多余的。上式也可以令余的。上式也可以令yyyy1,21(1)右端常數(shù)是右端常數(shù)是k個(gè)值中的一個(gè)時(shí)，約束條件為個(gè)值中的一個(gè)時(shí)，約束條件為1111kiikiiinjjijyybxa，(2 2)對(duì)于對(duì)于m條件中有條件中有k（m）組起作用時(shí)，約束條件寫(xiě)成）組起作用時(shí)，約束條件寫(xiě)成11nmijjiiijia xbMyymk，這里這里yi=1表示第表示第i組約束不起作用，組約束不起作用，y

14、i=0表示第表示第i個(gè)約束起作用。個(gè)約束起作用。當(dāng)約束條件是當(dāng)約束條件是“”符號(hào)時(shí)右端常數(shù)項(xiàng)應(yīng)為符號(hào)時(shí)右端常數(shù)項(xiàng)應(yīng)為iibMy(3) 對(duì)于對(duì)于m條件中有條件中有k(m)個(gè)起作用時(shí)，約束條件寫(xiě)成個(gè)起作用時(shí)，約束條件寫(xiě)成11nmijjiiijia xbMyymk，一般地一般地: 同樣可以討論對(duì)于有同樣可以討論對(duì)于有m個(gè)條件個(gè)條件、有、有m(m、m)個(gè)條個(gè)條件起作用的情形。件起作用的情形。例例 試引入試引入01變量將下列各題分別表達(dá)為一般線性約束條件變量將下列各題分別表達(dá)為一般線性約束條件:(1) x1+x26或或4x1+6x210或或2x1+4x220 ;(2) 若若x15，則，則x20，否則，否

15、則x28;(3) x1取值取值0，1，3，5，7。 解解 (1) 3個(gè)約束只有個(gè)約束只有1個(gè)起作用個(gè)起作用1211221231236461024202011,2,3jxxy Mxxy Mxxy Myyyyj或 ，3 , 2 , 1101)1 (2042)1 (1064)1 (6321321221121jyyyyMyxxMyxxMyxxj，或或或(3) 右端常數(shù)是右端常數(shù)是5個(gè)值中的個(gè)值中的1個(gè)個(gè)4 , 3 , 2 , 1101753432143211jyyyyyyyyyxj，或10)1 (8)1 (552211或yMyxyMxMyxyMx(2) 兩組約束只有一組起作用兩組約束只有一組起作用(2

16、) 若若x15，則，則x20，否則，否則x28; (3) x1取值取值0，1，3，5，7。整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)規(guī)劃的數(shù)學(xué)模型一般形式一般形式11max(min) (1.2)0 (1.2) njjjnijjijjZZc xa xbimxjn或且部分或全部為整數(shù) 依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0 01 1整數(shù)規(guī)劃。整數(shù)規(guī)劃。 純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)數(shù)（這時(shí)）。）。 全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)全整數(shù)規(guī)

17、劃：除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)整數(shù)外，系數(shù)aij和常數(shù)和常數(shù)bi也要求取整數(shù)（這時(shí)也要求取整數(shù)（這時(shí)）。）。 混合整數(shù)規(guī)劃：只有一部分的決策變量要混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。 01整數(shù)規(guī)劃：所有決策變量只能取整數(shù)規(guī)劃：所有決策變量只能取 0 或或 1 兩個(gè)整數(shù)兩個(gè)整數(shù)。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系 從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過(guò)舍入取整，尋求性規(guī)劃的基礎(chǔ)上，通過(guò)舍

18、入取整，尋求滿足整數(shù)要求的解即可。滿足整數(shù)要求的解即可。 但實(shí)際上兩者卻有很大的不同，通但實(shí)際上兩者卻有很大的不同，通過(guò)舍入得到的解（整數(shù)）也不一定就是過(guò)舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。是整數(shù)可行解。例：設(shè)整數(shù)規(guī)劃問(wèn)題如下例：設(shè)整數(shù)規(guī)劃問(wèn)題如下 且為整數(shù)0,13651914max21212121xxxxxxxxZ 首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱為松弛問(wèn)題）。為松弛問(wèn)題）。0,13651914max21212121xxxxxxxxZ用圖解法求出最優(yōu)解用圖解法

19、求出最優(yōu)解x13/2, x2 = 10/3且有且有Z = 29/6x1x233(3/2,10/3) 現(xiàn)求整數(shù)解（最優(yōu)解）：現(xiàn)求整數(shù)解（最優(yōu)解）：如用如用“舍入取整法舍入取整法”可可得到得到4個(gè)點(diǎn)即個(gè)點(diǎn)即(1，3) (2，3)(1，4)(2，4)。顯然，。顯然，它們都不可能是整數(shù)規(guī)它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。劃的最優(yōu)解。 按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集，如圖所示。是一個(gè)有限集，如圖所示。 因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最因

20、此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。 如上例：其中如上例：其中（2，2）（）（3，1）點(diǎn)為最點(diǎn)為最大值，大值，Z=4。 目前，常用的求解整數(shù)規(guī)劃的方法有：目前，常用的求解整數(shù)規(guī)劃的方法有： 分支定界法和割平面法；分支定界法和割平面法； 對(duì)于特別的對(duì)于特別的0 01 1規(guī)劃問(wèn)題采用隱枚舉法和匈規(guī)劃問(wèn)題采用隱枚舉法和匈牙利法。牙利法。 分支定界法是一種隱枚舉法或部分枚舉法，是枚舉分支定界法是一種隱枚舉法或部分枚舉法，是枚舉法基礎(chǔ)上的改進(jìn)。分支定界法的關(guān)鍵是分支和定界。法基礎(chǔ)上的改進(jìn)。分支定界法的關(guān)鍵是分支和定界。

21、“ “分支分支”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，而而“定界定界”則可以提高搜索的效率則可以提高搜索的效率。 所謂所謂“”，是在分支過(guò)程中，若某個(gè)后繼問(wèn)，是在分支過(guò)程中，若某個(gè)后繼問(wèn)題恰巧獲得整數(shù)規(guī)劃問(wèn)題的一個(gè)可行解，那么，它的題恰巧獲得整數(shù)規(guī)劃問(wèn)題的一個(gè)可行解，那么，它的目標(biāo)函數(shù)值就是一個(gè)目標(biāo)函數(shù)值就是一個(gè)“界限界限”，可作為衡量處理其它，可作為衡量處理其它分支的一個(gè)依據(jù)。分支的一個(gè)依據(jù)。 若整數(shù)規(guī)劃的松馳問(wèn)題的最優(yōu)解不符合整數(shù)要求，若整數(shù)規(guī)劃的松馳問(wèn)題的最優(yōu)解不符合整數(shù)要求，不妨假設(shè)不妨假設(shè) 不符合整數(shù)要求不符合整數(shù)要求, ,則可構(gòu)造兩個(gè)則可構(gòu)造兩個(gè)約束條

22、件約束條件 和和 如此不斷繼續(xù)，如此不斷繼續(xù)，直到獲得整數(shù)規(guī)劃的最優(yōu)解。這就是所謂的直到獲得整數(shù)規(guī)劃的最優(yōu)解。這就是所謂的“”iibx iibx 1iibx分支定界法分支定界法 基本思想：基本思想： 切割可行域，去掉非整數(shù)點(diǎn)。一次分枝變成兩切割可行域，去掉非整數(shù)點(diǎn)。一次分枝變成兩個(gè)可行域，分別求最優(yōu)解個(gè)可行域，分別求最優(yōu)解. 通過(guò)對(duì)松弛問(wèn)題的分枝，通過(guò)對(duì)松弛問(wèn)題的分枝，不斷降低（不斷降低（IP）最優(yōu)值的上界，提高下界，當(dāng)上界等）最優(yōu)值的上界，提高下界，當(dāng)上界等于下界時(shí)，得到最優(yōu)解。于下界時(shí)，得到最優(yōu)解。1 求解純整數(shù)規(guī)劃的分支定界法求解純整數(shù)規(guī)劃的分支定界法11max,1,2,0,1,2, ,

23、njjjnijjijjzc xa xbjmxjn且全為整數(shù)IPIP的松馳問(wèn)題：的松馳問(wèn)題：11max,1,2,0,1,2, ,njjjnijjijjzc xa xbimxjnLP,*:LPxzIPz設(shè)的最優(yōu)解為最優(yōu)值為 則 的最優(yōu)值滿足*zzz.zIP其中為在任何一個(gè)可行解處的目標(biāo)值 檢驗(yàn)與分支：檢驗(yàn)與分支：,*.xIPxIPzz如果 滿足的整數(shù)要求 則 為的最優(yōu)解：否則,rx考慮一個(gè)不滿足整數(shù)要求的將約束 1rrrrxxxx和)(的最大整數(shù)不超過(guò)形成兩個(gè)子問(wèn)題分別加入aaLP,;LPIP如果無(wú)最優(yōu)解 則無(wú)最優(yōu)解 求解求解LP LP : :1LP1maxnjjjzc x11,2,nijjija

24、 xbimrrxx njxj, 2 , 1, 02LP1maxnjjjzc x11,2,nijjija xbim1rrxxnjxj, 2 , 1, 0 求解求解LP1, LP2 ：設(shè)其解及最優(yōu)值分別為設(shè)其解及最優(yōu)值分別為.)(,(),(,(222111xzzxxzzx*,1zzz故對(duì)故對(duì)LP1剪支剪支.的最優(yōu)值均滿足：的最優(yōu)值均滿足：(i)如如則則LP1及由及由LP1分支的所有子問(wèn)題分支的所有子問(wèn)題,1zz 剪支及上下界改進(jìn)分析剪支及上下界改進(jìn)分析1()LP以為例,其他分支類(lèi)似(ii)如如:1zz滿足滿足IP的要求時(shí)，則的要求時(shí)，則1x當(dāng)當(dāng)1x是是IP的可行解，故的可行解，故改進(jìn)下界改進(jìn)下界*

25、,1zz ,:1zz 同理，此時(shí)同理，此時(shí)LP1剪支剪支.*x注意到注意到IP的最優(yōu)解的最優(yōu)解必是必是LP1或或LP2的可行解的可行解, 于是于是),(*)(*11xzzxzz或或).(*)(*22xzzxzz,max*21zzz 改進(jìn)上界：改進(jìn)上界：,max:21zzz 對(duì)對(duì)21,xx中中. .zz直至產(chǎn)生或全分支被剪支例例 用分支定界法求解下列整數(shù)規(guī)劃模型：用分支定界法求解下列整數(shù)規(guī)劃模型：解解 先求對(duì)應(yīng)的松弛問(wèn)題先求對(duì)應(yīng)的松弛問(wèn)題(記為記為L(zhǎng)P0)： 0,255 . 22108 . 02 . 1:034max21212121xxxxxxLPxxZ用圖解法得到最優(yōu)解用圖解法得到最優(yōu)解X（3

26、.57,7.14）,Z0=35.7,如下圖所示如下圖所示:且均取整數(shù),0,255.22108.02.134max21212121xxxxxxxxZ8.3310108 . 02 . 121xx255 . 2221xx松弛問(wèn)題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC10*035.7Z1010 x1x2oABC0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6), Z1=34.8LP2:X=(4,6.5),Z2=35.50,4255 . 22108 . 02 . 1:234ma

27、x211212121xxxxxxxLPxxZ得到兩個(gè)線性規(guī)劃及增加約束4311xx*035.5Z1010 x1x2oABCLP1LP334LP3:X=(4.33, 6), Z3=35.330,64255 . 22108 . 02 . 1:334max2121212121xxxxxxxxLPxxZ，2222677LPxxx選擇目標(biāo)值最大的分枝進(jìn)行分支，增加約束及，顯然不可行，得到線性規(guī)劃6不可行72xLP1:X=(3, 7.6), Z1=34.8*035.33Z1010 x1x2oACLP134可行域是一條線段即，, 40,464255 . 22108 . 02 . 1:434max121121

28、212121xxxxxxxxxxLPxxZ：及，到線性規(guī)劃及進(jìn)行分枝，增加約束，選擇由于545431113LPLPxxLPZZ60,65255 . 22108 . 02 . 1:534max2121212121xxxxxxxxLPxxZ，LP4:X=(4,6), Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6), Z1=34.8LP3LP5*3435.33Z*3535.33Z 盡管盡管LP1的解中的解中x1不為整數(shù)，但不為整數(shù)，但Z5Z1因此因此LP5的最優(yōu)解的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過(guò)程可用下圖表示上述分枝過(guò)程可用下圖表示LP0:

29、X=(3.57, 7.14), Z0=35.7LP1: X=(3, 7.6) Z1=34.8LP2: X=(4, 6.5) Z2=35.5x13x14LP3: X=(4.33, 6) Z3=35.33x26LP4: X=(4, 6) Z4=34LP5: X=(5, 5) Z5=35x14x15無(wú)可行解無(wú)可行解x27 例例 用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)

30、題0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（LP）用圖解法求用圖解法求（LP）的最的最優(yōu)解，如圖所示。優(yōu)解，如圖所示。x1x233(18/11,40/11)對(duì)于對(duì)于x118/111.64， 取值取值x1 1， x1 2對(duì)于對(duì)于x2 =40/11 3.64，取值取值x2 3 ，x2 4先將先將（LP）劃分為（）劃分為（LP1）和（）和（LP2）, ,取取x1 1, x1 2 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最小值的下最小值的下限。限。有下式：有下式：且且為為整整數(shù)數(shù)0,1 4 30 652 )

31、1(5min2111212121xxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 現(xiàn)在只要求出（現(xiàn)在只要求出（LP1）和（）和（LP2）的最優(yōu)解即可。）的最優(yōu)解即可。x1x233(18/11,40/11) 先求先求（LP1）, ,如圖所示。如圖所示。此時(shí)此時(shí)B 在點(diǎn)取得最優(yōu)解。在點(diǎn)取得最優(yōu)解。x11, x2 =3, Z(1)16找到整數(shù)解，問(wèn)題已探找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。明，此枝停止計(jì)算。11同理求同理求（LP2） ,如圖所示。如圖所示。在在C 點(diǎn)取得最優(yōu)解。點(diǎn)取得最優(yōu)解。即即x12, x2 =10/

32、3, Z(2) 56/318.7 Z2 Z116 原問(wèn)題有比原問(wèn)題有比（16）更小的最優(yōu)解，但）更小的最優(yōu)解，但 x2 不是整數(shù)，故利用不是整數(shù)，故利用BAC加入條件：加入條件： x23, x24 有下式：有下式：且且為為整整數(shù)數(shù)0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最優(yōu)解即可。）的最優(yōu)解即可。x1x233(18/11,40/11)11BAC先求先求（LP3）, ,如圖所示。如圖所示

33、。此時(shí)此時(shí)D 在點(diǎn)取得最優(yōu)解。在點(diǎn)取得最優(yōu)解。即即 x112/52.4, x2 =3, Z(3)-87/5-17.4 Z(5) F 如對(duì)如對(duì) Z(6) 繼續(xù)分解，其最小值也不會(huì)低于繼續(xù)分解，其最小值也不會(huì)低于15.5 ，問(wèn)題探明問(wèn)題探明, ,剪枝。剪枝。 至此，原問(wèn)至此，原問(wèn)題（題（IP）的最優(yōu)）的最優(yōu)解為：解為： x1=2， x2 =3, Z* = Z(5) 17以上的求解過(guò)程以上的求解過(guò)程可以用一個(gè)樹(shù)形可以用一個(gè)樹(shù)形圖表示如右：圖表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP

34、3x1=12/5, x2=3Z(3) 17.4LP4無(wú)可無(wú)可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13 且全為整數(shù)且全為整數(shù)0,13651914max21212121xxxxxxxxZ用分枝定界法求解整數(shù)規(guī)劃問(wèn)題用分枝定界法求解整數(shù)規(guī)劃問(wèn)題 LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP5x1=1, x2=2Z(5) 3LP6無(wú)可無(wú)可行解行解x22x23LP3x1=33/14, x2=2

35、Z(3) 61/14LP4無(wú)可無(wú)可行解行解x22x23LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x12x13LP1x1=1, x2=7/3Z(1) 10/3LPx1=2/3, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9LP3x1=33/14, x2=2Z(3) 61/14LP4無(wú)可無(wú)可行解行解LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x11x12x22x23x12x13且且為為整整數(shù)數(shù)0,143292)(23max21212121xxxxxxIPxxZ3200CB XB b x1x2x3

36、x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解解:用單純形法解對(duì)應(yīng)的用單純形法解對(duì)應(yīng)的(LP)問(wèn)題問(wèn)題,如表所示如表所示,獲得最優(yōu)解。獲得最優(yōu)解。初始表初始表最終表最終表例例 用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法）用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法） x1=13/4 x2=5/2 Z(0) =59/414.75 選選 x2 進(jìn)行分枝，即增加兩個(gè)約束，進(jìn)行分枝，即增加兩個(gè)約束，2 x2 3 有下式：有下式：121212212max

37、322 92314(1) 2,0ZxxxxxxLPxx x且為整數(shù)121212212max322 92314(2) 3,0ZxxxxxxLPxx x且為整數(shù) 分別在分別在(LP1)和和(LP2)中引入松弛變量中引入松弛變量x5和和x6 ，將新加，將新加約束條件加入上表計(jì)算。即約束條件加入上表計(jì)算。即 x2+ x5= 2 , x2+x6=3 得得下表下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-

38、1/2001/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5繼續(xù)分枝，加繼續(xù)分枝，加入約束入約束 3 x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403

39、x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考慮分枝先不考慮分枝接接(LP1)繼續(xù)分枝，加入約束繼續(xù)分枝，加入約束 4 x1 3，有下式：有下式：且且為為整整數(shù)數(shù)0,3 2 14329 2)3(23max2112212121xxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,4 2 14329 2)4(23max2112212121xxxxxxxxIPxxZ分別引入松弛變量分別引入松弛變量x7 和和 x8 ，然后進(jìn)行計(jì)算。，然后進(jìn)行計(jì)算。CB XB

40、b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整數(shù)解，找到整數(shù)解，問(wèn)題已探明，問(wèn)題已探明，停止計(jì)算。停止計(jì)算。LP3CB XB b x1x2x3x4x5x83x

41、17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1 x1=4, x2=1 Z(4) =14找到整數(shù)解，找到整數(shù)解，問(wèn)題已探明，問(wèn)題已探明，停止計(jì)算。停止計(jì)算。LP4樹(shù)形圖如下：樹(shù)形圖如下：LP1x1=7/2, x2=2Z(1)29/2

42、=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14 且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題 （單純形法）（單純形法）cj-1-5000cBxBbx1x2x3x4x50 x32-111000 x4 30560100 x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-

43、5x240/11011/11 5/110-1x1 18/11101/11-6/1100 x526/1100-1/116/111-Z218/11006/1119/110LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4無(wú)可無(wú)可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13 先不考慮整數(shù)約束，按一般線性先不考慮整數(shù)約束，按一般線性規(guī)劃問(wèn)題求其最優(yōu)解，線性規(guī)劃問(wèn)題

44、規(guī)劃問(wèn)題求其最優(yōu)解，線性規(guī)劃問(wèn)題的最優(yōu)基本可行解是解集的一個(gè)極點(diǎn)的最優(yōu)基本可行解是解集的一個(gè)極點(diǎn)，這個(gè)極點(diǎn)的的坐標(biāo)未必都是整數(shù)，這個(gè)極點(diǎn)的的坐標(biāo)未必都是整數(shù)，若不是整數(shù)解，可增加一條約束，相若不是整數(shù)解，可增加一條約束，相當(dāng)于增加一個(gè)平面將這個(gè)極點(diǎn)割掉，當(dāng)于增加一個(gè)平面將這個(gè)極點(diǎn)割掉，稱這種方法為割平面法。稱這種方法為割平面法。割平面法的基本思想割平面法的基本思想例例 求解整數(shù)線性規(guī)劃問(wèn)題求解整數(shù)線性規(guī)劃問(wèn)題 C B sO A x1 x2整數(shù), 0,104114. .max212121xxxxtsxxs解解 引入松馳變量將其化為標(biāo)準(zhǔn)形式引入松馳變量將其化為標(biāo)準(zhǔn)形式，利用單純，利用單純形法求其最

45、優(yōu)解。形法求其最優(yōu)解。最優(yōu)單純形表如下最優(yōu)單純形表如下4 , 3 , 2 , 1, 0104114. .max423121ixxxxxt sxxsi整數(shù) 從最優(yōu)單純形表中看出約束條件變成從最優(yōu)單純形表中看出約束條件變成 5 . 225. 075. 225. 04231xxxx 變形得變形得423125. 05 . 0225. 075. 02xxxx上式分別記為上式分別記為,1I2I 423125. 05 . 025. 075. 0 xIxI 都應(yīng)小于等于都應(yīng)小于等于0的整數(shù)。引進(jìn)多余變量的整數(shù)。引進(jìn)多余變量 21,II65,xx5 . 025. 075. 025. 06453xxxx4 , 3

46、 , 2 , 1, 0104114. .max423121ixxxxxt sxxsi整數(shù)jcjxBxBcib1x2x3x4x1x2xj 1 1 0 0 111 0 0.25 0 0 1 0 0.252.752.5 0 0 -0.25 -0.25 用對(duì)偶用對(duì)偶單純形單純形法求解法求解jcjxBxBcib1x2x3x4x5x6x1x2x5x6xj 1 1 0 0 0 0 11001 0 0.25 0 0 00 1 0 0.25 0 00 0 -0.25 0 1 00 0 0 -0.25 0 12.752.5-0.75-0.5 0 0 -0.25 -0.25 0 0 取取i=3為主元行為主元行,k=

47、3為主元列為主元列,進(jìn)行換基迭代。再取進(jìn)行換基迭代。再取i=4為主為主元行，元行，k=4為主元列，進(jìn)行換基迭代得表。為主元列，進(jìn)行換基迭代得表。5 . 025. 075. 025. 06453xxxx jcBcBxjxib1x2x3x4x5x6x1x2x5x6xj 1 1 0 0 0 0 11001 0 0 0 1 00 1 0 0 0 10 0 1 0 -4 00 0 0 1 0 -42232 0 0 0 0 -1 -1 最優(yōu)基本可行解為：最優(yōu)基本可行解為： 0, 2, 3, 2, 24321其余為xxxx設(shè)純整數(shù)規(guī)劃設(shè)純整數(shù)規(guī)劃njxbxaxcZjinjjijnjjj, 10max11且為

48、整數(shù)， 松弛問(wèn)題松弛問(wèn)題njxbxaxcZjinjjijnjjj, 10max11，的最優(yōu)解的最優(yōu)解TmTbbbbBbbBX),() 0 ,(21112 求解求解IP的割平面法的割平面法jcnmmcccc11BcBXbmcc 1mxx 11 mbbnmmxxxx 11im 11,11,11001mnm mmnaaaa 0 0jjiijcc aj單純形法最終表單純形法最終表設(shè)設(shè)xi不為整數(shù)，不為整數(shù)，,iikkiiiikkkkkxa xbxba xx即為非基變量將將 分離成一個(gè)分離成一個(gè)與一個(gè)與一個(gè)之和：之和：ikiab及 ,01,01iiiikikikiikbbfaafff則有則有kkikkk

49、ijiiixfxafbx iiijkiikkkkxba xff x上式兩邊都為上式兩邊都為并且有并且有1ikkikifxff加入松弛變量加入松弛變量si得得iikkiksf xf 此式稱為以此式稱為以xi行為源行行為源行(來(lái)源行來(lái)源行)的的，或，或，或，或R.E.Gomory。 將將Gomory約束方程加入到松弛問(wèn)題的最優(yōu)表中，約束方程加入到松弛問(wèn)題的最優(yōu)表中，用對(duì)偶單純形法計(jì)算，若最優(yōu)解中還有非整數(shù)解，用對(duì)偶單純形法計(jì)算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(shù)解。再繼續(xù)切割，直到全部為整數(shù)解。0iikkkff x則則324313322354613651xxxxxx例如，例如，32

50、46536511)1(xxxx1行：行：移項(xiàng)：移項(xiàng)：46536532411xxxx令令046536532xx加入松弛變量加入松弛變量s1得得324653651xxs同理，對(duì)于同理，對(duì)于x2行有：行有：324313312xxs 例例 用割平面法求解下列用割平面法求解下列IP問(wèn)題問(wèn)題且為整數(shù)0,102304634max21212121xxxxxxxxZ解解 放寬變量約束，對(duì)應(yīng)的松弛問(wèn)題是放寬變量約束，對(duì)應(yīng)的松弛問(wèn)題是 0,102304634max21212121xxxxxxxxZ加入松弛變量加入松弛變量x3及及x4后，用單純形法求解，得到最優(yōu)表后，用單純形法求解，得到最優(yōu)表 最優(yōu)解最優(yōu)解X(0)(

51、5/2，15/4),不是不是IP的最優(yōu)解。選擇的最優(yōu)解。選擇表的第一行表的第一行(也可以選第二行也可以選第二行)為源行為源行252141431xxxCj4300bCBXBx1x2x3x443x1x210011/41/81/23/45/215/4j005/81/4分離系數(shù)后改寫(xiě)成分離系數(shù)后改寫(xiě)成212)211(41431xxx021412124341xxxx加入松弛變量加入松弛變量x5得到高莫雷約束方程得到高莫雷約束方程34522xxx 將上式作為約束條件添加到上表中，用對(duì)偶單將上式作為約束條件添加到上表中，用對(duì)偶單純形法計(jì)算，如表所示純形法計(jì)算，如表所示: Cj43000bCBXBx1x2x3

52、x4x5430 x1x2x51000101/41/811/23/42 0015/215/42j005/81/40430 x1x2x41000101/21/21/2001 1/43/81/2331j001/201/8最優(yōu)解最優(yōu)解X(1)(3，3)，最優(yōu)值，最優(yōu)值Z21。所有變量為整數(shù)，。所有變量為整數(shù)，X(1)就是就是IP的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，重復(fù)上述計(jì)算過(guò)程。重復(fù)上述計(jì)算過(guò)程。 1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbbBcB11xnx2x1mxmx0111mabBcB1

53、01m00110nna11mmamna1bmbrx011rmarnarbrs000011rmarna1 rb1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs000011rmrmaarnrnaa1 rrbbbBcB101xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs00001rmfrnf1rfbBcB100rf正則解正則解 1 求解求解01整數(shù)規(guī)劃的隱枚舉法（整數(shù)規(guī)劃的隱枚舉法（適合于變量個(gè)適合于變量個(gè) 數(shù)較少數(shù)較少的的0-1規(guī)劃）規(guī)劃）隱枚舉法的步驟：隱枚舉法的步驟： 1

54、.找出任意一可行解，目標(biāo)函數(shù)值為找出任意一可行解，目標(biāo)函數(shù)值為Z0 ； 2. 原問(wèn)題原問(wèn)題，則增加一個(gè)約束，則增加一個(gè)約束1 1220(*)nnc xc xc xZ當(dāng)當(dāng)，上式改為，上式改為約束；約束； 3. 列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式(*)，若，若滿足再檢驗(yàn)其它約束，若不滿足式滿足再檢驗(yàn)其它約束，若不滿足式(*)，則認(rèn)為不可行，則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值值 ； 4. 目標(biāo)函數(shù)值最大目標(biāo)函數(shù)值最大(最小最小)的解就是最優(yōu)解。的解就是最優(yōu)解。 例例 用隱枚舉法求解下列用隱

55、枚舉法求解下列BIP問(wèn)題問(wèn)題4 , 3 , 2 , 11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或1153264321xxxx 解解 (1) 不難看出，當(dāng)所有變量不難看出，當(dāng)所有變量等于等于0或或1的任意組合時(shí)，第一個(gè)的任意組合時(shí)，第一個(gè)約束滿足，說(shuō)明第一個(gè)約束沒(méi)有約束滿足，說(shuō)明第一個(gè)約束沒(méi)有約束力，是多余的，從約束條件約束力，是多余的，從約束條件中去掉。中去掉。 還能通過(guò)觀察得到還能通過(guò)觀察得到X0(1，0，0，1)是一個(gè)可行解，目標(biāo)是一個(gè)可行解，目標(biāo)值值Z011是是BIP問(wèn)題的下界，構(gòu)問(wèn)題的下

56、界，構(gòu)造一個(gè)約束：造一個(gè)約束：原原BIP問(wèn)題變?yōu)閱?wèn)題變?yōu)?2341234123412341234max6235623511( )3564( )23 ( )( )24510011,2,3,4jZxxxxxxxxaxxxxbxxxxcdxxxxxj或 ，(2) 列出變量取值列出變量取值0和和1的組合，共的組合，共2416個(gè)，分個(gè)，分別代入約束條件判斷是否可行。別代入約束條件判斷是否可行。 首先判斷式首先判斷式(a)是否滿足，如果滿足，接下來(lái)是否滿足，如果滿足，接下來(lái)判斷其它約束，否則認(rèn)為不可行，計(jì)算過(guò)程見(jiàn)判斷其它約束，否則認(rèn)為不可行，計(jì)算過(guò)程見(jiàn)下表所示。下表所示。 3. 列出所有可能解，對(duì)每個(gè)可能

57、解先檢驗(yàn)式列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式(*)，若，若滿足再檢驗(yàn)其它約束，若不滿足式滿足再檢驗(yàn)其它約束，若不滿足式(*)，則認(rèn)為不可行，則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值值 ；jXjabcdZjjXjabcdZj1(0,0,0,0)9(1,0,0,0)2(0,0,0,1)10 (1,0,0,1)113(0,0,1,0)11(1,0,1,0)4(0,0,1,1)12 (1,0,1,1)145(0,1,0,0)13 (1,1,0,0)6(0,1,0,1)14 (1,1,0,1)137(0,1,1,0)15 (1,1,1

58、,0)8(0,1,1,1)16 (1,1,1,1) (3) 由上表知，由上表知，BIP問(wèn)題的最優(yōu)解：?jiǎn)栴}的最優(yōu)解：X(1，0，1，1)，最優(yōu)值，最優(yōu)值Z14。 注：注： (1) 選擇不同的初始可行解，計(jì)算量會(huì)不選擇不同的初始可行解，計(jì)算量會(huì)不一樣。一樣。 一般地，當(dāng)目標(biāo)函數(shù)求最大值時(shí)，首先考慮目一般地，當(dāng)目標(biāo)函數(shù)求最大值時(shí)，首先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于標(biāo)函數(shù)系數(shù)最大的變量等于1。 當(dāng)目標(biāo)函數(shù)求最小值時(shí)，先考慮目標(biāo)函數(shù)系數(shù)當(dāng)目標(biāo)函數(shù)求最小值時(shí)，先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于最大的變量等于0；(2) 在上表的計(jì)算過(guò)程中，當(dāng)目標(biāo)值等于在上表的計(jì)算過(guò)程中，當(dāng)目標(biāo)值等于14時(shí)，將時(shí)，將其下界其下

59、界11改為改為14，可以減少計(jì)算量。，可以減少計(jì)算量。 在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n 項(xiàng)不同的任項(xiàng)不同的任務(wù)，需要?jiǎng)?wù)，需要n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專(zhuān)長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率和各人的專(zhuān)長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。 于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這

60、類(lèi)問(wèn)題稱為類(lèi)問(wèn)題稱為。 指派問(wèn)題是指派問(wèn)題是0-1 規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。 利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是，即，即。指派問(wèn)題指派問(wèn)題 例例 人事部門(mén)欲安排四人到四個(gè)不同的崗位工作，每個(gè)崗位人事部門(mén)欲安排四人到四個(gè)不同的崗位工作，每個(gè)崗位一個(gè)人經(jīng)考核四人在不同崗位的成績(jī)（百分制）如表所示，如一個(gè)人經(jīng)考核四人在不同