運(yùn)籌學(xué)精品課件之整數(shù)規(guī)劃

運(yùn)籌學(xué)

Operations

ResearchChapter4整數(shù)規(guī)劃IntegerProgramming1.整數(shù)規(guī)劃的數(shù)學(xué)建模2.整數(shù)規(guī)劃的求解算法

3.案例分析29一月2023第四章整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)第二節(jié)解純整數(shù)規(guī)劃的割平面法第三節(jié)分枝定界法第四節(jié)0-1型整數(shù)規(guī)劃第五節(jié)指派問題29一月2023

在求解線性規(guī)劃問題時(shí)，得到的最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但許多實(shí)際問題要求得到的解為整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問題，稱為整數(shù)線性規(guī)劃(IntegerlinearProgramming)。第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)29一月2023

例1

某服務(wù)部門各時(shí)段（每2h為一時(shí)段）需要的服務(wù)員人數(shù)見下表。按規(guī)定服務(wù)員連續(xù)工作8小時(shí)為一班。現(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門服務(wù)員總數(shù)最少。時(shí)段12345678服務(wù)員最少數(shù)目10891113853

設(shè)xi表示第i時(shí)段開始上班的人數(shù)29一月2023例2現(xiàn)有資金總額為B，可供選擇的投資項(xiàng)目n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj，此外，由于種種原因，有三個(gè)附加條件：（1）若選擇1，則必須選擇2，反之則不一定；（2）項(xiàng)目3和4至少選擇一個(gè)；（3）項(xiàng)目5、6、7中恰好選擇2個(gè)。應(yīng)該如何選擇項(xiàng)目，才能使總預(yù)期收益最大？設(shè)第i個(gè)項(xiàng)目為xi，則其有兩種狀態(tài)，選擇投資（記為1）和不選擇投資（記為0）。29一月2023例3工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需再建一家工廠，相應(yīng)的方案有A3和A4兩個(gè)。這種物資的需求地有B1~B4四個(gè)。各工廠的生產(chǎn)能力、各地年需求量、各廠至各需求地的單位運(yùn)費(fèi)cij見下表。工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬元或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)A3還是A4，才能使每年的總費(fèi)用（即全部物資運(yùn)費(fèi)和新工廠生產(chǎn)費(fèi)用之和）最少。B1B2B3B4生產(chǎn)能力A12934400A28357600A37612200A44525200需求量35040030015029一月2023設(shè)xij表示第i個(gè)工廠供應(yīng)給第j個(gè)需求的地的產(chǎn)量，y表示是否建設(shè)A3工廠（取1表示建設(shè)A3工廠，取0表示不建設(shè)A3工廠）29一月2023【例4】指派問題或分配問題。人事部門欲安排四人到四個(gè)不同崗位工作，每個(gè)崗位一個(gè)人。經(jīng)考核四人在不同崗位的成績（百分制）如表5－3所示，如何安排他們的工作使總成績最好。表5－3工作人員ABCD甲85927390乙95877895丙82837990丁8690808829一月2023

【解】此工作分配問題可以采用枚舉法求解，即將所有分配方案求出，總分最大的方案就是最優(yōu)解。本例的方案有4?。?×3×2×1＝24種，當(dāng)人數(shù)和工作數(shù)較多時(shí)，方案數(shù)是人數(shù)的階乘，計(jì)算量非常大。用0－1規(guī)劃模型求解此類分配問題顯得非常簡單。設(shè)數(shù)學(xué)模型如下：目標(biāo)函數(shù)為29一月2023每項(xiàng)工作只能安排一人，約束條件為變量約束：要求每人做一項(xiàng)工作，約束條件為29一月2023引例

某廠擬用火車裝運(yùn)甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤以及裝運(yùn)所受限制如下：貨物集裝箱體積(米3)重量(百斤)利潤(百元) 甲5220乙4510托運(yùn)限制2413問兩種貨物各裝運(yùn)多少箱，可使獲得利潤最大？29一月2023

是不是可通過把不考慮整數(shù)要求求得的最優(yōu)解經(jīng)過“化整”得到滿足整數(shù)要求的最優(yōu)解呢？設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為x1和x2。顯然，x1、x2都要求為整數(shù),于是可建立整數(shù)規(guī)劃模型：

Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)

x1,x2≥0(4)

x1,x2為整數(shù)(5)29一月2023

此例可解得x1=4.8,x2=0，湊整為x1=5,x2=0，這就破壞了條件(2)，因而不是可行解；如截?cái)嘈?shù)變?yōu)閤1=4,x2=0，這當(dāng)然滿足所有約束條件，但不是最優(yōu)解，因?yàn)閷1=4,x2=0有z＝80，而對x1=4,x2=1（也是可行解）有z＝90。29一月2023整數(shù)規(guī)劃的數(shù)學(xué)模型若要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃若要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解29一月2023第二節(jié)割平面法29一月2023考慮純整數(shù)規(guī)劃問題：設(shè)其中aij和bi皆為整數(shù)（若不為整數(shù)時(shí)，可乘上一個(gè)倍數(shù)化為整數(shù)）。29一月2023割平面法是R.E.Gomory于1958年提出的一種方法，它主要用于求解純整數(shù)規(guī)劃。割平面法是用增加新的約束來切割可行域，增加的新約束稱為割平面方程或切割方程。其基本思路為：

若其松弛問題的最優(yōu)解X*不滿足整數(shù)約束，則從X*的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件，將其加入原松弛問題中，形成一個(gè)新的線性規(guī)劃，然后求解之。若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。29一月2023為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應(yīng)當(dāng)滿足兩個(gè)基本性質(zhì)：（1）已獲得的不符合整數(shù)要求的LP最優(yōu)解不滿足該線性約束條件，從而不可能在以后的解中出現(xiàn)；（2）凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)解始終被保留在每次剩余的線性規(guī)劃可行域中。

29一月2023例1用割平面法求解整數(shù)規(guī)劃問題步驟1：標(biāo)準(zhǔn)化其松弛問題B029一月2023Cj1100CBXBbx1x2x3x411x2x17/43/401103/4-1/41/41/4cj-zj00-1/2-1/2引進(jìn)一個(gè)割平面來縮小可行域，割平面要切去松弛問題的非整數(shù)最優(yōu)解而又不要切去問題的的任一個(gè)整數(shù)可行解。用單純形法求解：29一月2023步驟2：求一個(gè)割平面方程

1）在最終表上任選一個(gè)含有不滿足整數(shù)條件基變量的約束方程。如選x1，則含x1的約束方程為

2）將所選擇的約束方程中非基變量的系數(shù)及常數(shù)項(xiàng)進(jìn)行拆分處理。具體規(guī)則是：將上述系數(shù)和常數(shù)項(xiàng)均拆分成一個(gè)整數(shù)加上一個(gè)非負(fù)真分?jǐn)?shù)（純小數(shù)）之和。則（3）式變?yōu)椋?9一月2023

3）將上述約束方程（4）重新組合。組合的原則是：將非負(fù)基變量系數(shù)及常數(shù)項(xiàng)中的非負(fù)真分?jǐn)?shù)移到等號右端，將其他部分移到等號左端，即得：

等式左端實(shí)際上由三部分組成，常數(shù)項(xiàng)的整數(shù)部分，基變量及非基變量（含松弛變量或剩余變量），前兩部分都是整數(shù)或應(yīng)取整數(shù)，而松弛變量x3、x4由松弛問題標(biāo)準(zhǔn)型知，也應(yīng)取非負(fù)整數(shù)（對于這一點(diǎn)，當(dāng)原問題的約束方程組中的系數(shù)或常數(shù)項(xiàng)中有非整數(shù)時(shí)，要求將約束方程先化為成整數(shù)系數(shù)及整數(shù)常數(shù)項(xiàng)，然后再標(biāo)準(zhǔn)化，就可滿足）。29一月2023很明顯，（5）左端為整數(shù)，右端<3/4，則有其右端0，即4）將割平面方程加到松弛問題的約束方程中，構(gòu)成新的松弛問題并求解（對偶單純形法）。

29一月2023割平面方程

Cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/4001cj-zj00-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3cj-zj000-1/3-2/329一月20231、本題注只用一次割平面就求得了最優(yōu)解，但大多數(shù)問題中不是只用一、二次割平面就能求得整數(shù)最優(yōu)解。若一次割平面不能求得整數(shù)最優(yōu)解，則按步驟2中的4個(gè)步驟，在松弛問題的最終單純形表中找出第二個(gè)割平面方程，將此割平面方程加到伴隨規(guī)劃中，過程伴隨規(guī)劃，再用對偶單純形法(單純形法)求解。若求得了整數(shù)最優(yōu)解，則停止計(jì)算，否則繼續(xù)再作割平面，縮小可行域，直到求得整數(shù)最優(yōu)解為止。注意：29一月20232、實(shí)際解題時(shí)，經(jīng)驗(yàn)表明若從最終單純形表中選擇具有最大分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約束，往往可以提高“切割”效果，減少“切割”次數(shù)。3、在用割平面法解整數(shù)規(guī)劃時(shí)，常會遇到收斂很慢的情形，因此實(shí)際中通常不單獨(dú)使用。29一月2023第三節(jié)分枝定界法29一月2023

分枝定界法(branchandboundmethod)是20世紀(jì)60年代由Land-Doig和Dakin等人提出的。這種方法既可用于純整數(shù)規(guī)劃問題，也可用于混合整數(shù)規(guī)劃問題，而且便于用計(jì)算機(jī)求解，所以很快成為解整數(shù)規(guī)劃的最主要的方法。分枝定界法的主要思路是：首先求解整數(shù)規(guī)劃的松弛問題，如果求得的最優(yōu)解不符合整數(shù)條件，則增加新約束——縮小可行域；將原整數(shù)規(guī)劃問題分枝——分為兩個(gè)子規(guī)劃，再解子規(guī)劃的松弛規(guī)劃┅通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷地定界，最后得到原整數(shù)規(guī)劃問題的整數(shù)最優(yōu)解。29一月2023分枝定界法的思路：

1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；

2.若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；

3.任意選一個(gè)非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個(gè)新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分枝問題的下界；29一月2023分枝定界法的思路：

4.

檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計(jì)算，若還存在非整數(shù)解并且目標(biāo)值大于（max）整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。29一月2023

步驟1：用單純形法求解松弛問題，得到最優(yōu)解及最優(yōu)值。

步驟2：分枝。例2解整數(shù)規(guī)劃問題41/9>10/3,優(yōu)先選擇B1分枝。29一月2023無可行解61/14(B12)>10/3(B2),優(yōu)先選擇B12分枝。29一月20234>10/3，所以B2無需分枝。29一月2023【例3】用分枝定界法求解【解】先求對應(yīng)的松弛問題（記為LP0）：用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.7,如下圖所示。29一月20231010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC29一月20231010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②29一月20231010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②29一月20231010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP329一月2023盡管LP1的解中x1不為整數(shù)，但Z5>Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。分枝過程如圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5無可行解x2≥729一月2023

(1)用觀察法求整數(shù)規(guī)劃原問題R的一個(gè)可行解，其目標(biāo)值便是R的最優(yōu)目標(biāo)值z*的一個(gè)下界z。

(2)求解松弛問題R0，若R0無可行解，則R也無可行解，結(jié)束；若得到R0的最優(yōu)解x(0)和最優(yōu)值z0。若x(0)符合R的整數(shù)條件，則顯然x(0)也是R的最優(yōu)解，結(jié)束；否則，以R0作為一個(gè)分枝標(biāo)明求解的結(jié)果，z0是問題R的最優(yōu)目標(biāo)值z*的一個(gè)上界z。

分支定界法的步驟29一月2023

(3)分枝。取目標(biāo)函數(shù)值最大的一個(gè)枝Rs，在Rs的解中任選一不符合整數(shù)條件的變量xj，其值為bj，構(gòu)造兩個(gè)約束條件xj≤[bj]和xj≥[bj]+1。將兩個(gè)約束條件分別加入問題Rs，得兩個(gè)后繼規(guī)劃問題Rs1和Rs2。不考慮整數(shù)條件求解這兩個(gè)后繼問題，以每個(gè)后繼問題為一分枝標(biāo)明求解的結(jié)果。分支定界法的步驟29一月2023

(4)定界。在各分枝中找出目標(biāo)函數(shù)值最大者作為新的上界z；從已符合整數(shù)要求的各分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界z。

(5)比較與剪枝。各分枝的最優(yōu)目標(biāo)函數(shù)值中如果有小于z者，則剪掉這一枝（用打×表示），即以后不再考慮了。若已沒有大于z的分枝，則已得到R的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)(3)。29一月2023第四節(jié)0-1整數(shù)規(guī)劃29一月2023

0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量xj僅取值0或1。這種只能取0或1的變量稱為0-1變量或二進(jìn)制變量。29一月2023例1(含有互斥約束條件的問題)：設(shè)工序B的每周時(shí)約束條件為：0.3x1+0.5x2150，現(xiàn)還有一種新的加工方式,對應(yīng)約束為：0.2x1+0.4x2120，兩種加工方式只能選一種?；コ?9一月2023如果有m個(gè)互相排斥的約束條件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m

為保證這m個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量yi(i=1,2,…，m)和一個(gè)充分大的常數(shù)M，將約束條件改為如下形式：

αi1x１+αi2x2+…+αinxn≤bi+yiM

i=1,2,…，m(5-13)

y1+y2+…+ym=m?

1(5-14)顯然，在m個(gè)yi中只有一個(gè)能取0值，設(shè)yi*=0，就只有i=i*這個(gè)約束條件起作用，而別的式子都是多余的。29一月2023例2(固定費(fèi)用問題)：三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、單件可變費(fèi)用、售價(jià)、資源單耗量以及固定成本見右表，制定一個(gè)生產(chǎn)計(jì)劃使總收益最大。產(chǎn)品1產(chǎn)品2產(chǎn)品3資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)8101229一月2023

對于0-1型整數(shù)規(guī)劃，一般采用隱枚舉法，而不必采用完全枚舉法。包括:

(1)只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。

(2)若已發(fā)現(xiàn)一個(gè)可行解，則可根據(jù)它的目標(biāo)函數(shù)值產(chǎn)生一個(gè)過濾條件，對于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性；在以后的求解中每當(dāng)發(fā)現(xiàn)更好的可行解就替換原來的過濾條件。0-1型整數(shù)規(guī)劃的解法29一月2023例3求解0－1整數(shù)規(guī)劃(x1，x2，x3)z值約束條件（1）

（3）

（4）

（5）過渡條件（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）05-233816√√√√√√√√√√√√z0z5z8若將目標(biāo)函數(shù)系數(shù)按小到大排列：maxz=-2x2+3x1+5x3，計(jì)算量大減。29一月2023第五節(jié)指派問題29一月2023指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型匈牙利解法求解指派問題一般的指派問題29一月2023有n項(xiàng)任務(wù)，恰好n個(gè)人承擔(dān)，第i人完成第j項(xiàng)任務(wù)的花費(fèi)(時(shí)間或費(fèi)用等)為cij，要求確定人和事之間的一一對應(yīng)的指派方案，使總花費(fèi)最省？一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的系數(shù)矩陣如下：Cij的含義可以不同，如費(fèi)用、成本、時(shí)間等。29一月2023為建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入n×n個(gè)0-1變量：指派問題的數(shù)學(xué)模型可寫成如下形式：1若派第i人做第j事0若不派第i人做第j事（ij=1，2,…，n）第j項(xiàng)工作由一個(gè)人做第i人做一項(xiàng)工作29一月2023指派問題的每個(gè)可行解，可用矩陣表示如下：矩陣X中，每行各元素中只有1個(gè)元素為1，其余各元素等0；每列各元素中也只有1個(gè)元素為1，其余各元素等0。指派問題有n！個(gè)可行解。29一月2023例4有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需時(shí)間如下表。問應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？29一月2023指派問題的數(shù)學(xué)模型如下：29一月2023已知條件可用系數(shù)矩陣（效率矩陣）表示為：其可行解也可用每行僅有一個(gè)1，每列也僅有一個(gè)1的矩陣表示，如：29一月2023二、匈牙利法解題步驟

1955年，庫恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，稱為匈牙利解法。

標(biāo)準(zhǔn)指派問題是一種特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題和特殊的運(yùn)輸問題。29一月2023

匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如下性質(zhì)：若從指派問題的系數(shù)矩陣C的某行（或某列）各元素分別減去一個(gè)常數(shù)k，得到一個(gè)新的矩陣C’，則以C’和C為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。（系數(shù)矩陣的變化并不影響數(shù)學(xué)模型的約束方程組，而只是目標(biāo)函數(shù)值減少了常數(shù)k，所以最優(yōu)解不變）二、匈牙利法解題步驟29一月2023-2-4-9-7

若某行(列)已有0元素，那就不必再減了。例1的計(jì)算為：1.使系數(shù)矩陣各行、各列出現(xiàn)零元素作法：系數(shù)矩陣各行元素減去所在行的最小元素，再從所得矩陣的各列減去所在列最小元素。(因一行中xij

取值一個(gè)1，其余為0，cij

同時(shí)減去一常數(shù)不影響xij取值)。匈牙利法解題步驟如下：29一月2023-4-2這就保證每行每列至少有一個(gè)0元素，同時(shí)不出現(xiàn)負(fù)元素。29一月2023

2.試求最優(yōu)解作法：由獨(dú)立0元素的行（列）開始，獨(dú)立0元素處右上角畫“*”標(biāo)記，在有“*”

的行列中劃去其它0元素；再在剩余的0元素中重復(fù)此做法，直至不能標(biāo)記

“*”為止。29一月2023（1）當(dāng)遇到在所有的行和列中，0元素都不止一個(gè)時(shí)（存在0元素的閉回路），可任選其中一個(gè)0元素加圈，同時(shí)劃去同行和同列中其他0元素。（2）如能找出n個(gè)位于不同行不同列的零元素，令對應(yīng)的xij=1，其余xij=0，得最優(yōu)解，結(jié)束；否則，看下面的例題轉(zhuǎn)第3步。29一月2023例5求表中所示效率矩陣的指派問題的最小解。

任務(wù)人ABCDE甲127979乙89666丙71712149丁