運(yùn)籌學(xué)基礎(chǔ)畢德春遼東學(xué)院信息技術(shù)學(xué)院運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第1頁第5章

整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃問題數(shù)學(xué)模型運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第2頁第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第3頁1整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第4頁例：某服務(wù)部門各時段（每2小時為一時段）需要服務(wù)員人數(shù)以下表，按要求，服務(wù)員連續(xù)工作8小時（即4個時段）為一班，現(xiàn)要求安排服務(wù)員工作時間，使服務(wù)部門服務(wù)員總數(shù)最小。時段12345678服務(wù)員最少數(shù)目108911138531.1.1引例第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第5頁解：設(shè)第j時段開始時上班服務(wù)員人數(shù)為xj，因為第j時段開始時上班服務(wù)員將在第(j+3)時段結(jié)束時下班，故決議變量只需考慮x1,x2,x3,x4,x5，此問題數(shù)學(xué)模型為：1.1.1引例第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第6頁這類問題數(shù)學(xué)模型普通形式為：求一組變量X1,X2,…,Xn，使1.1.1引例第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第7頁例：某單位有5個擬選擇投資項目，其所需投資額與期望收益以下表。因為各項目之間有一定聯(lián)絡(luò)，A、C、E之間必須選擇一項且僅需選擇一項；B和D之間需選擇也僅需選擇一項；又因為C和D兩項目親密相關(guān)，C實施必須以D實施為前提條件，該單位共籌集資金15萬元，問應(yīng)該選擇哪些項目投資，使期望收益最大？項目所需投資額（萬元）期望收益（萬元）A610B48C27D46E591.1.1引例第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第8頁解：決議變量：設(shè)目標(biāo)函數(shù)：期望收益最大約束條件：投資額限制條件6x1+4x2+2x3+4x4+5x515項目A、C、E之間必須且只需選擇一項：x1+x3+x5=1項目C實施要以項目D實施為前提條件：x3

x4項目B、D之間必須且只需選擇一項：x2+x4=1歸納起來，其數(shù)學(xué)模型為：1.1.1引例第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第9頁上例表明，利用0-1變量處理一類“可供選擇條件”問題非常簡明方便。下面再深入分別說明對0-1變量應(yīng)用。假定現(xiàn)有m種資源對可供選擇n個項目進(jìn)行投資數(shù)學(xué)模型為：求一組決議變量X1,X2,…,Xn，使1.1.1引例第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第10頁依據(jù)變量取整數(shù)情況，將整數(shù)規(guī)劃分為：（1）純整數(shù)規(guī)劃，全部變量都取整數(shù).（2）混合整數(shù)規(guī)劃，一部分變量取整數(shù),一部分變量取實數(shù)（3）0-1整數(shù)規(guī)劃,全部變量均取0或11.1.2整數(shù)規(guī)劃問題分類第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題提出運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第11頁2整數(shù)規(guī)劃問題求解思索

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第12頁考慮純整數(shù)問題：整數(shù)問題松弛問題：1.2.1整數(shù)規(guī)劃問題與其松弛問題第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題求解思索

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第13頁“舍入取整”法：即先不考慮整數(shù)性約束，而去求解其對應(yīng)LP問題（稱為松馳問題），然后將得到非整數(shù)最優(yōu)解用“舍入取整”方法。這么能否得到整數(shù)最優(yōu)解？1.2.2求解ILP問題方法思索第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題求解思索

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第14頁例

：設(shè)整數(shù)規(guī)劃問題以下

首先不考慮整數(shù)約束，得到線性規(guī)劃問題（松弛問題）。1.2.2求解ILP問題方法思索第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題求解思索

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第15頁用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6。現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解必定在線性規(guī)劃問題可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題可行解集是一個有限集，如圖所表示。x1x2⑴⑵33(3/2,10/3)1.2.2求解ILP問題方法思索第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題求解思索

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第16頁所以，可將集合內(nèi)整數(shù)點一一找出，其最大目標(biāo)函數(shù)值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。慣用求解整數(shù)規(guī)劃方法有：割平面法和分支定界法，對于0－1規(guī)劃問題采取隱枚舉法和匈牙利法。1.2.2求解ILP問題方法思索第1節(jié)整數(shù)規(guī)劃問題數(shù)學(xué)模型│整數(shù)規(guī)劃問題求解思索

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第17頁第2節(jié)分配問題與匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第18頁1分配問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第19頁在實際中經(jīng)常會碰到這么問題，有n項不一樣任務(wù)，需要n個人分別完成其中一項，但因為任務(wù)性質(zhì)和各人專長不一樣，所以各人去完成不一樣任務(wù)效率（或花費(fèi)時間或費(fèi)用）也就不一樣。于是產(chǎn)生了一個問題，應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)總效率最高（或所需時間最少），這類問題稱為指派問題或分配問題。2.1.1分配問題含義第2節(jié)分配問題與匈牙利法│分配問題

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第20頁分配第i個人去完成第j項任務(wù)不分配第i個人去完成第j項任務(wù)例：有一份說明書，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成。因各人專長不一樣，他們完成翻譯不一樣文字所需時間（h）以下表，應(yīng)怎樣分配，使這四個人分別完成這四項任務(wù)總時間為最??？2.1.2分配問題實例第2節(jié)分配問題與匈牙利法│分配問題

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第21頁2.1.2分配問題實例第2節(jié)分配問題與匈牙利法│分配問題

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第22頁設(shè)n個人被分配去做n件工作，要求每個人只做一件工作，每件工作只有一個人去做。已知第I個人去做第j件工作效率（時間或費(fèi)用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)怎樣分配才能使總效率（時間或費(fèi)用）最高？設(shè)決議變量

1分配第i個人去做第j件工作

xij=0相反(I,j=1.2.…n)其數(shù)學(xué)模型為：2.1.3分配問題數(shù)學(xué)模型第2節(jié)分配問題與匈牙利法│分配問題

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第23頁2匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第24頁

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119例：用匈牙利法求解以下指派問題，已知效率矩陣分別以下：2.2.1匈牙利法例一第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第25頁24972.2.1匈牙利法例一第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第26頁422.2.1匈牙利法例一第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第27頁◎?◎??◎◎2.2.1匈牙利法例一第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第28頁例：

有一份漢字說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將漢字說明書譯成不一樣語種說明書所需時間以下表所表示，問怎樣分配任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁59822.2.2匈牙利法例二第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第29頁第一步，變換系數(shù)矩陣：－52.2.2匈牙利法例二第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第30頁第二步，試指派：◎◎◎??

只找到3個獨(dú)立零元素2.2.2匈牙利法例二第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第31頁第三步，作最少直線覆蓋全部0元素：◎◎◎??√√√獨(dú)立零元素個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋全部元素中最小元素為1，然后打√各行都減去1；打√各列都加上1，得以下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：2.2.2匈牙利法例二第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第32頁000000得到4個獨(dú)立零元素，所以最優(yōu)解矩陣為：◎◎◎??√√√◎◎◎??最優(yōu)值:15=2+4=1+8◎◎◎??◎2.2.2匈牙利法例二第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第33頁115764戊69637丁86458丙9117129乙118957甲EDCBA費(fèi)工作用人員例：用匈牙利法求解以下指派問題，已知效率矩陣分別以下：2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第34頁-1-22.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第35頁◎?◎◎◎??2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第36頁◎?◎◎◎??√√√2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第37頁◎?◎◎◎??2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第38頁◎?◎?◎?◎?√√√√√√√2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第39頁◎?◎?◎?◎?√√√√√√√2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第40頁◎?◎?◎?◎?√√√√√√√2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第41頁◎??◎??◎?◎?◎此問題有最優(yōu)解是唯一嗎？最優(yōu)值：28=5+7+6+6+42.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第42頁◎??◎??◎?◎?◎2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第43頁◎??◎??◎?◎?◎2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第44頁例：用匈牙利法求解以下指派問題，已知效率矩陣分別以下：2.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第45頁48212.2.3匈牙利法例三第2節(jié)分配問題與匈牙利法│匈牙利法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第46頁3非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第47頁設(shè)m為最大化指派問題系數(shù)矩陣C中最大元素。令矩陣B＝（m-cij）nn則以B為系數(shù)矩陣最小化指派問題和原問題有相同最優(yōu)解。例：

某人事部門擬招聘4人任職4項工作，對他們綜合考評得分以下表（滿分100分），怎樣安排工作使總分最多。2.3.1最大化指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第48頁解:選矩陣中最大元素95，減去其它元素。用匈牙利法求解C’，最優(yōu)解為：即甲安排做第二項工作、乙做第三項、丙做第四項、丁做第三項,最高總分Z＝92＋95＋90＋80＝3572.3.1最大化指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第49頁當(dāng)人數(shù)m大于工作數(shù)n時，加上m－n項虛擬工作，比如：當(dāng)人數(shù)m小于工作數(shù)n時，加上n－m個人，比如2.3.2不平衡指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第50頁若某人可做幾件事，則將該人化作相同幾個“人”來接收指派，且費(fèi)用系數(shù)取值相同。例：丙能夠同時任職A和C工作，求最優(yōu)指派方案。2.3.3一個人可做幾件事指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第51頁將該人做此事效率系數(shù)取做足夠大數(shù)，可用M表示。例：分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)。每個人完成各項任務(wù)時間如表所表示。因為任務(wù)數(shù)多于人數(shù)，考慮任務(wù)E必須完成，其它4項中可任選3項完成。試確定最優(yōu)分配方案，使完成任務(wù)總時間最少。

任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁24423623452.3.4某事一定不能由某人做指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第52頁解:這是不平衡指派問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。因為任務(wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因為工作E必須完成，故設(shè)戊完成E時間為M（M為非常大數(shù)），其余效率系數(shù)為0，則標(biāo)準(zhǔn)型效率矩陣表示為：

任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M2.3.4某事一定不能由某人做指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第53頁用匈牙利法求出最優(yōu)指派方案為：即甲－B，乙－D，丙－E，?。瑼,任務(wù)C放棄。最少時間為105。2.3.4某事一定不能由某人做指派問題第2節(jié)分配問題與匈牙利法│非標(biāo)準(zhǔn)型指派問題運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第54頁第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第55頁1普通性求解方法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第56頁例：求解以下0－1規(guī)劃問題3.1.1普通性求解方法示例第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│普通性求解方法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第57頁解：對于0－1規(guī)劃問題，因為每個變量只取0，1兩個值，普通會用窮舉法來解，即將全部0，1組合找出，使目標(biāo)函數(shù)到達(dá)極值要求就可求得最優(yōu)解。x1.x2.x3約束條件滿足條件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)

－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15 ×(1.0.1)0211∨8(1.1.0)3×(1.1.1)26×3.1.1普通性求解方法示例第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│普通性求解方法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第58頁由上表可知，問題最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一個可行解，為盡快找到最優(yōu)解，可將3x1－2x2＋5x3≥5作為一個約束，凡是目標(biāo)函數(shù)值小于5組合無須討論，以下表。x1.x2.x3約束條件滿足條件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(0.0.1)5－1101∨5(0.1.0)-2×(0.1.1)3×(1.0.0)3×(1.0.1)80211∨8(1.1.0)1×(1.1.1)4×3.1.1普通性求解方法示例第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│普通性求解方法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第59頁例：求解以下0－1規(guī)劃問題解：因為目標(biāo)函數(shù)中變量x1,x2,x4系數(shù)均為負(fù)數(shù)，可作以下變換：令x1＝1－x1′,x2=1-x2′,x3=x3′,x4=1-x4′帶入原題中，但需重新調(diào)整變量編號。令x3′=x1′,x4′=x2′得到下式。3.1.2隱枚舉法示例一第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│普通性求解方法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第60頁2隱枚舉法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第61頁能夠從(1.1.1.1)開始試算，x′(3)＝(1.1.0.1)最優(yōu)解。x(3)＝(1.0.1.0)是原問題最優(yōu)解，Z*=－23.2.1隱枚舉法示例一第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│隱枚舉法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第62頁例：求解以下0－1規(guī)劃問題令y1=x5,y2=x4,y3=x2,y4=x3,y5=x1

得到下式3.2.2隱枚舉法示例二第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│隱枚舉法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第63頁y1.y2.y3.y4.y5約束條件滿足條件Z值(1)(2)是∨否×(0，0，0，0，0)00×(1，0，0，0，0)1-1×(0，1，0，0，0)-11×(0，0，1，0，0)-21×(0，0，0，1，0)4-4∨8(0，0，0，0，1)3-2×所以，

Y*=（0.0.0.1.0），原問題最優(yōu)解為：X*

＝（0.0.1.0.0），Z*=83.2.2隱枚舉法示例二第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│隱枚舉法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第64頁（0，1，1，0，0）用隱枚舉法求解0—1規(guī)劃問題3.2.3隱枚舉法示例三第3節(jié)0-1整數(shù)規(guī)劃與隱枚舉法│隱枚舉法

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第65頁第4節(jié)割平面法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第66頁1割平面法基本思想

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第67頁若分量不全是整數(shù)，則對增加一個割平面條件，將可行區(qū)域割掉一塊，恰好在被割掉區(qū)域內(nèi)，而原ILP問題任何一個可行解（格點）都沒有被割去.4.1.1割平面法基本思想第4節(jié)割平面法│割平面法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第68頁把增添了割平面條件問題記為，用對偶單純形法求解LP問題.若最優(yōu)解是整數(shù)向量，則是原ILP問題最優(yōu)解，計算結(jié)束；不然對問題在增加一個割平面條件，形成問題，…，如此繼續(xù)下去，經(jīng)過求解不停改進(jìn)松弛LP問題，知道得到最優(yōu)整數(shù)解為止。4.1.1割平面法基本思想第4節(jié)割平面法│割平面法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第69頁4.1.1割平面法基本思想第4節(jié)割平面法│割平面法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第70頁2割平面法求解過程

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第71頁例

：用割平面法求解整數(shù)規(guī)劃問題解：增加松弛變量x3和x4

，得到(LP)初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/44.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第72頁此題最優(yōu)解為：X＊

(1,3/2)Z=3/2但不是整數(shù)最優(yōu)解，引入割平面。以x2為源行生成割平面，因為1/4=0+1/4,3/2=1+1/2,我們已將所需要數(shù)分解為整數(shù)和分?jǐn)?shù)，所以，生成割平面條件為:4.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第73頁將x3=6-3x1-2x2,x4=3x1-2x2,帶入中，得到等價割平面條件：x2≤1如圖。x1x2⑴⑵33第一個割平面4.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第74頁Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40現(xiàn)將生成割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-14.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第75頁

此時，X1

＝(2/3,1),Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成割平面，其條件為：用上表約束解出x4和s1，將它們帶入上式得到等價割平面條件：x1≥x2，見圖：x1x2⑴⑵33第一個割平面第二個割平面4.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第76頁將生成割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/24.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第77頁CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10至此得到最優(yōu)表，其最優(yōu)解為X＊=(1,1),Z=1,這也是原問題最優(yōu)解。4.2.1割平面法求解過程示例一第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第78頁例：用割平面法求解數(shù)規(guī)劃問題4.2.2割平面法求解過程示例二第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第79頁Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6初始表最優(yōu)表4.2.2割平面法求解過程示例二第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第80頁將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和4.2.2割平面法求解過程示例二第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第81頁以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端最大真分?jǐn)?shù)式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分?jǐn)?shù)相等，可任選一個考慮?，F(xiàn)選第二個式子，并將真分?jǐn)?shù)移到右邊得：引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。4.2.2割平面法求解過程示例二第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第82頁Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/604.2.2割平面法求解過程示例二第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第83頁Cj11000CBXBbx1x2x3x4s11x10100－101x240101－20x320011－3－Z－40000－1/2此整數(shù)規(guī)劃有兩個最優(yōu)解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。4.2.2割平面法求解過程示例二第4節(jié)割平面法│割平面法求解過程運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第84頁第5節(jié)分枝定界法運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第85頁1分枝定界法基本思想

運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第86頁例：用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計算）記為（IP）解：首先去掉整數(shù)約束，變成普通線性規(guī)劃問題記為（LP）5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第87頁用圖解法求（LP）最優(yōu)解，如圖所表示。x1＝18/11,x2=40/11,Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值下限。對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2x1x2⑴⑵33(18/11,40/11)⑶5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第88頁

現(xiàn)在只要求出（LP1）和（LP2）最優(yōu)解即可。5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第89頁x1x2⑴⑵33(18/11,40/11)⑶先求（LP1）,如圖所表示。此時B在點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停頓計算。同理求（LP2）,如圖所表示。在C點取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7

∵Z2<Z1＝－16∴原問題有比（－16）更小最優(yōu)解，但x2不是整數(shù)，故利用3≥10/3≥4加入條件。11BAC5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第90頁加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）最優(yōu)解即可。5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第91頁x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所表示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。求（LP4），如圖所表示。無可行解，不再分枝。D5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第92頁在（LP3）基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）最優(yōu)解即可。5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第93頁x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所表示。此時E在點取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問題探明，此枝停頓計算。求（LP6），如圖所表示。此時F在點取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

如對Z(6)

繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。EF5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第94頁至此，原問題（IP）最優(yōu)解為：x1=2，x2

=3,Z*=Z(5)

＝－17以上求解過程能夠用一個樹形圖表示如右：LP1x1=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無可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃5.1.1分枝定界法基本思想第5節(jié)分枝定界法│分枝定界法基本思想運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第95頁2分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第96頁例：用分枝定界法求解整數(shù)規(guī)劃問題（圖解法）5.2.1分枝定界法示例一第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第97頁LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)

＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃5.2.1分枝定界法示例一第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第98頁LP1x1=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無可行解LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃5.2.2分枝定界法示例二第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第99頁例：用分枝定界法求解整數(shù)規(guī)劃問題（單純形法）5.2.3分枝定界法示例三第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第100頁3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對應(yīng)(LP)問題,如表所表示,取得最優(yōu)解。初始表最終表5.2.3分枝定界法示例三第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第101頁x1=13/4x2=5/2Z(0)=59/4≈14.75.選x2進(jìn)行分枝，即增加兩個約束，2≥x2≥3有下式：分別在(LP1)和(LP2)中引入松弛變量x5、x6

，將新約束條件加入上表計算。即x2+x5=2,－x2+x6=－3如表:5.2.3分枝定界法示例三第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第102頁32000CB

XB

bx1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2，

x2=2，Z(1)=29/2=14.5繼續(xù)分枝，加入約束3≥x1≥4LP15.2.3分枝定界法示例三第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第103頁32000CB

XB

bx1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3，Z(2)=27/2=13.5∵Z(2)<Z(1)

∴先不考慮分枝5.2.3分枝定界法示例三第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第104頁接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進(jìn)行計算。5.2.3分枝定界法示例三第5節(jié)分枝定界法│分枝定界法示例運(yùn)籌學(xué)整數(shù)規(guī)劃與分配問題版第105頁CB

XB

bx1x2x3x4x5x73x17/2101/20-1/202x22010010