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

第八章

整數(shù)規(guī)劃1整數(shù)規(guī)劃問題線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問題中，只有當(dāng)決策變量的取值為整數(shù)時(shí)才有意義。例如，產(chǎn)品的件數(shù)、機(jī)器的臺(tái)數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱為整數(shù)線性規(guī)劃，簡稱整數(shù)規(guī)劃(IntegerProgramming)。全部決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃(AllIP)；僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(MixedIP)；要求決策變量只能取0或1值，則稱為0-1規(guī)劃(0-1rogramming)。

2整數(shù)規(guī)劃問題為了滿足整數(shù)要求，似乎可以把線性規(guī)劃的小數(shù)最優(yōu)解進(jìn)行“舍入化整”以得到與最優(yōu)解相近的整數(shù)解?！吧崛牖币话闶遣豢尚械模夯蟮慕庥锌赡艹蔀榉强尚薪?；雖是可行解，卻不是最優(yōu)解。例如一、問題的提出

產(chǎn)品資源甲乙現(xiàn)有量A219B5735單臺(tái)利潤63

問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。3整數(shù)規(guī)劃問題解：設(shè)x1為甲產(chǎn)品的臺(tái)數(shù)，x2為乙產(chǎn)品的臺(tái)數(shù)。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)不考慮整數(shù)約束則是一個(gè)LP問題,稱為原整數(shù)規(guī)劃的松弛問題。不考慮整數(shù)約束的最優(yōu)解：x1

*=28/9=3.111，

x2

*

=25/9=2.778，Z

*

=293/9=32.556舍入化整x1=3，x2=3，Z=33，不滿足約束條件5x1+7x2≤35，非可行解；x1=3，x2=2，Z=28，滿足約束條件，是可行解，但不是最優(yōu)解；x1=4，x2=1，Z=29，滿足約束條件，才是最優(yōu)解。45x1+7x2=352x1+x2=9?(3,3)??????????第一節(jié)、整數(shù)規(guī)劃的圖解法

x1x21231253445步驟：在線性規(guī)劃的可行域內(nèi)列出所有決策變量可能取的整數(shù)值，求出這些變量所有可行的整數(shù)解，比較它們相應(yīng)的目標(biāo)函數(shù)值，最優(yōu)的目標(biāo)函數(shù)值所對(duì)應(yīng)的解就是整數(shù)規(guī)劃的最優(yōu)解。實(shí)用性：只有兩個(gè)決策變量，可行的整數(shù)解較少。

第一節(jié)、整數(shù)規(guī)劃的圖解法

二、整數(shù)規(guī)劃的圖解法

6例1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運(yùn)所受限制如表所示。貨物每件體積（立方英尺）每件重量（百千克）每件利潤（百元）甲乙19527344023托運(yùn)限制1365140

第一節(jié)、整數(shù)規(guī)劃的圖解法甲種貨物至多托運(yùn)4件，問兩種貨物各托運(yùn)多少件，可使獲得利潤最大。解：設(shè)x1、

x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：Maxz=2x1+3x2

約束條件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0為整數(shù)。如果去掉最后一個(gè)約束，就是一個(gè)線性規(guī)劃問題。利用圖解法，7得到線性規(guī)劃的最優(yōu)解為x1=2.44,x2=3.26,目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4,x2=2,目標(biāo)函數(shù)值為14。性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=6第一節(jié)、整數(shù)規(guī)劃的圖解法??????????8例2：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0為整數(shù)例3：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3

為整數(shù)

x3

為0-1變量用《管理運(yùn)籌學(xué)》軟件求解得：

x1=5x2=2x3=2用《管理運(yùn)籌學(xué)》軟件求解得：

x1=4x2=1.25x3=1z=16.25第二節(jié)、整數(shù)規(guī)劃的計(jì)算機(jī)求解9第三節(jié)、整數(shù)規(guī)劃的應(yīng)用

例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj

(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：

在東區(qū)由A1

，A2

，A3三個(gè)點(diǎn)至多選擇兩個(gè)；在西區(qū)由A4

，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)由A6

，A7兩個(gè)點(diǎn)中至少選一個(gè)；在北區(qū)由A8

，A9

，A10

三個(gè)點(diǎn)中至少選兩個(gè)。一、投資場(chǎng)所的選擇Aj

各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)不同都是不一樣的，預(yù)測(cè)情況見下表所示(單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤為最大?10解：設(shè)：0--1變量xi=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒被選用）。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xj≥0

xj

為0--1變量，i=1,2,3,……,10第三節(jié)、整數(shù)規(guī)劃的應(yīng)用11Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xj≥0

xj

為0--1變量，i=1,2,3,……,10最優(yōu)解：x1=1,x2=1,x3=0,

x4=0,x5=1,

x6=1,

x7=0,x8=0,x9=1,

x10=1最大利潤245萬元。即在A1,A2,A5,A6,A9,A10

等6個(gè)地點(diǎn)建立銷售門市部。實(shí)際投資額為100+120+70+90+160+180=720第三節(jié)、整數(shù)規(guī)劃的應(yīng)用12例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動(dòng)力有300人月，機(jī)器有100臺(tái)月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬元，中號(hào)為150萬元，大號(hào)為200萬元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤為最大。二、固定成本問題第三節(jié)、整數(shù)規(guī)劃的應(yīng)用13解：這是一個(gè)整數(shù)規(guī)劃的問題。設(shè)x1，x2，x3分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說明固定費(fèi)用的這種性質(zhì)，設(shè)yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時(shí))或0（當(dāng)不生產(chǎn)第i種容器即xi=0時(shí)）引入約束xi≤Myi

，i=1，2，3，M充分大，以保證當(dāng)yi

=0時(shí)，xi=0。這樣我們可建立如下的數(shù)學(xué)模型：

Maxz=4x1+5x2+6x3-100y1-150y2-200y3

s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi

，i=1，2，3，M充分大

xj≥0xj∈N

yj

為0--1變量，i=1,2,3第三節(jié)、整數(shù)規(guī)劃的應(yīng)用14例6．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如表所示，問應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。三、指派問題:有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總的效率最高，這就是指派問題。第三節(jié)、整數(shù)規(guī)劃的應(yīng)用15解：引入0—1變量xij，并令xij

=1(當(dāng)指派第i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第i人去完成第j項(xiàng)工作時(shí))．這可以表示為一個(gè)0--1整數(shù)規(guī)劃問題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一項(xiàng)工作)

x21+x22+x23+x24=1(乙只能干一項(xiàng)工作)

x31+x32+x33+x34=1(丙只能干一項(xiàng)工作)

x41+x42+x43+x44=1(丁只能干一項(xiàng)工作)

x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij

∈N為0--1變量，i,j

=1,2,3,4

***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用16

對(duì)于有m

個(gè)人，n項(xiàng)任務(wù)的一般指派問題，設(shè)：第三節(jié)、整數(shù)規(guī)劃的應(yīng)用并設(shè)：cij

為第i人去完成第n項(xiàng)任務(wù)的成本（如時(shí)間、費(fèi)用等）則一般指派問題的模型可以寫為：約束條件：xij為0-1變量，對(duì)所有的i和j.17因?yàn)閙不一定等于n，當(dāng)m>n，即人數(shù)多于任務(wù)數(shù)時(shí)，就有人沒有任務(wù)，所以前面?zhèn)€約束條件都是“小于等于1”，這是說每個(gè)人至多承擔(dān)一項(xiàng)任務(wù)，而后面n個(gè)約束條件說明每項(xiàng)工作正好有一人承擔(dān)，所以都是“等于1”.當(dāng)n>m時(shí)，需要設(shè)假想的n-m個(gè)人便獲得可行解.第三節(jié)、整數(shù)規(guī)劃的應(yīng)用18第三節(jié)、整數(shù)規(guī)劃的應(yīng)用還有一種指派問題叫做多重指派問題，它于一般的指派問題的區(qū)別在于：一般的指派問題中每個(gè)人至多承擔(dān)一項(xiàng)任務(wù)，而多重指派問題中一個(gè)人可以根據(jù)自己能力的大小承擔(dān)一項(xiàng)、兩項(xiàng)或更多項(xiàng)的任務(wù).這時(shí)約束條件中的前個(gè)條件不是而是改為其中ai是第i個(gè)人至多承擔(dān)的任務(wù)的數(shù)，對(duì)于不同的i

，ai可以是不一樣的.19四、分布系統(tǒng)設(shè)計(jì)

例7．某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)(每千箱運(yùn)費(fèi))如下表所示。（1）

問應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小?

（2）

如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠?第三節(jié)、整數(shù)規(guī)劃的應(yīng)用20解：

a)

設(shè)xij為從Ai運(yùn)往Bj

的運(yùn)輸量(單位千箱)，yi

=1(當(dāng)Ai被選中時(shí))或0（當(dāng)Ai沒被選中時(shí))．這可以表示為一個(gè)整數(shù)規(guī)劃問題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。

s.t.x11+x12+x13≤30(A1

廠的產(chǎn)量限制)

x21+x22+x23≤10y2(A2

廠的產(chǎn)量限制)

x31+x32+x33≤20y3(A3

廠的產(chǎn)量限制)

x41+x42+x43≤30y4(A4

廠的產(chǎn)量限制)

x51+x52+x53≤40y5(A5

廠的產(chǎn)量限制)

x11+x21+x31+x41+x51=30(B1

銷地的限制)

x12+x22+x32+x42+x52=20(B2

銷地的限制)

x13+x23+x33+x43+x53=20(B3

銷地的限制)

xij≥0xj∈N

，yi為0--1變量，i=1,2,3,4,5；j=1,2,3

***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用21b)

如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠?

解：

設(shè)xij為從Ai運(yùn)往Bj

的運(yùn)輸量(單位千箱)，yi=1(當(dāng)Ai

被選中時(shí))或0（當(dāng)Ai

沒被選中時(shí))．這可以表示為一個(gè)整數(shù)規(guī)劃問題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。

s.t.x11+x12+x13≤30(A1

廠的產(chǎn)量限制)

x21+x22+x23≤10y2(A2

廠的產(chǎn)量限制)

x31+x32+x33≤20y3(A3

廠的產(chǎn)量限制)

x41+x42+x43≤30y4(A4

廠的產(chǎn)量限制)

x51+x52+x53≤40y5(A5

廠的產(chǎn)量限制)

x11+x21+x31+x41+x51=30(B1

銷地的限制)

x12+x22+x32+x42+x52=20(B2

銷地的限制)

x13+x23+x33+x43+x53=20(B3

銷地的限制)

y2+y3=1(必須在A2，A3地建一個(gè)廠)

xij≥0yi為0--1變量，i=1,2,3,4,5；j=1,2,322五、投資問題例8．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：

項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬元，第二、三、四年不限；

項(xiàng)目B：第三年初需要投資，到第五年未能回收本利128％，但規(guī)定最低投資金額為3萬元，最高金額為5萬元；

項(xiàng)目C：第二年初需要投資，到第五年未能回收本利140%，但規(guī)定其投資額或?yàn)?萬元或?yàn)?萬元或?yàn)?萬元或?yàn)?萬元。

項(xiàng)目D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大?第三節(jié)、整數(shù)規(guī)劃的應(yīng)用23解：1)設(shè)xiA、xiB、xiC、xiD(i

＝1，2，3，4，5)分別表示第

i

年年初給項(xiàng)目A，B，C，D的投資額；設(shè)y1A，y3B，是0—1變量，并規(guī)定:

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用設(shè)y2C

是非負(fù)整數(shù)變量，并規(guī)定：第2年投資C項(xiàng)目8萬元時(shí)，取值為4；第2年投資C項(xiàng)目6萬元時(shí)，取值為3；第2年投資C項(xiàng)目4萬元時(shí)，取值為2；第2年投資C項(xiàng)目2萬元時(shí)，取值為1；第2年不投資C項(xiàng)目時(shí)，取值為0；

24這樣我們建立如下的決策變量：

第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C(=20000y2C)

D

x1D

x2D

x3D

x4D

x5D

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用252）約束條件：第一年：年初有100000元，D項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x1A+x1D=100000；第二年：A次年末才可收回投資,故第二年年初的資金為1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的資金為1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的資金為1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的資金為1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D；第三節(jié)、整數(shù)規(guī)劃的應(yīng)用26關(guān)于項(xiàng)目A的投資額規(guī)定:x1A≥40000y1A

，x1A≤200000y1A

，200000是足夠大的數(shù)；保證當(dāng)

y1A=0時(shí)，x1A=0；當(dāng)y1A=1時(shí)，x1A≥40000。關(guān)于項(xiàng)目B的投資額規(guī)定:x3B≥30000y3B

，x3B≤50000y3B

；保證當(dāng)

y3B=0時(shí)，x3B=0；當(dāng)y3B=1時(shí)，50000≥

x3B≥30000。關(guān)于項(xiàng)目C的投資額規(guī)定:x2C=20000y2C

，y2C=0，1，2，3，4。第三節(jié)、整數(shù)規(guī)劃的應(yīng)用273）目標(biāo)函數(shù)及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5D

s.t.x1A+x1D=100000；

x2A+x2C+x2D=1.06x1D；

x3A+x3B+x3D=1.15x1A+1.06x2D；

x4A+x4D=1.15x2A+1.06x3D；

x5D=1.15x3A+1.06x4D；

x1A≥40000y1A

，

x1A≤200000y1A

，

x3B≥30000y3B

，

x3B≤50000y3B

；

x2C=20000y2C

，

y1A，y3B=0或1，y2C=0，1，2，3，4xiA

，xiB

，xiC

，xiD≥0(i=1、2、3、4、5）第三節(jié)、整數(shù)規(guī)劃的應(yīng)用28第四節(jié)分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整數(shù)規(guī)劃相應(yīng)的LP(即不考慮整數(shù)限制)的最優(yōu)解，若求得的最優(yōu)解符合整數(shù)要求，則是原IP的最優(yōu)解；若不滿足整數(shù)條件，則任選一個(gè)不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)規(guī)劃的最優(yōu)解。

29第四節(jié)分枝定界法定界的含義：整數(shù)規(guī)劃是在相應(yīng)的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的約束條件，整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于相應(yīng)線性規(guī)劃的最優(yōu)解。對(duì)極大化問題來說，相應(yīng)線性規(guī)劃的目標(biāo)函數(shù)最優(yōu)值是原整數(shù)規(guī)劃函數(shù)值的上界；對(duì)極小化問題來說，相應(yīng)線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值是原整數(shù)規(guī)劃目標(biāo)函數(shù)值的下界。30第四節(jié)分枝定界法例maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)第一步,不考慮變量的整數(shù)約束,求相應(yīng)LP(問題1)的最優(yōu)解：

x1=28/9，x2=25/9，Z1=293/9第二步,定界過程這個(gè)解不滿足整數(shù)約束，這時(shí)目標(biāo)函值Z1是整數(shù)規(guī)劃的目標(biāo)上界；因?yàn)閤1=x2=0是整數(shù)規(guī)劃問題的可行解，所以下界為0。第三步,分枝過程將不滿足整數(shù)約束的變量x1進(jìn)行分枝，x1稱為分枝變量，構(gòu)造兩個(gè)新的約束條件：

x1≤[28/9]=3，x1≥[28/9]+1=4

31第四節(jié)分枝定界法這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個(gè)部分，如圖所示。??????????5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4問題2：maxZ=

6x1+5x2問題3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)32第四節(jié)分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題2相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2=20/7，Z2=226/7問題3相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=4，x2=1，Z3=29第四步，定界過程LP3的解滿足整數(shù)約束，不必再分枝，它的目標(biāo)函數(shù)值是29，大于原有下界0，則新的下界為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為226/7。LP2的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值226/7大于現(xiàn)有下界，則應(yīng)繼續(xù)分枝。第五步，分枝過程將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x2≤[20/7]=2，x2≥[20/7]+1=3

33??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3第四節(jié)分枝定界法問題4：maxZ=

6x1+5x2問題5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=2

x2=334第四節(jié)分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題4相應(yīng)的線性規(guī)劃的最優(yōu)解：

x1=3，x2=2，Z4=28問題5相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=14/5，x2=3，Z5=159/5第六步，定界過程LP4的解滿足整數(shù)約束，不必再分枝，它的目標(biāo)函數(shù)值是28，小于原有下界29，則下界仍為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為159/5。LP5的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值159/5大于現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。第七步，分枝過程將不滿足整數(shù)約束的變量x1進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x1≤[14/5]=2，x1≥[14/5]+1=3

35第四節(jié)分枝定界法問題6：maxZ=

6x1+5x2問題7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=2

x2=3??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=236第四節(jié)分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解：問題6相應(yīng)的線性規(guī)劃的最優(yōu)解：

x1=2，x2=25/7，Z6=209/7問題7相應(yīng)的線性規(guī)劃的最優(yōu)解：無最優(yōu)解第八步，定界過程LP7的無最優(yōu)解，不必再分枝，下界仍為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為209/7。LP6的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值209/7大于現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。第九步，分枝過程將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x2≤3，x2≥4

37第四節(jié)分枝定界法問題8：maxZ=

6x1+5x2問題9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=438第四節(jié)分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題8相應(yīng)的線性規(guī)劃的最優(yōu)解：

x1=2，x2=3，Z8=27問題9相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=7/5，x2=4，Z9=142/5第十步，定界過程LP8的最優(yōu)解，滿足整數(shù)約束，不必再分枝，下界仍為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為29。雖然LP9的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值142/5小于現(xiàn)有下界29，則不再繼續(xù)分枝。上界=下界，得整數(shù)規(guī)劃問題的最優(yōu)解：x1=4，x2=1，Z=2939分枝定界過程x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥4第四節(jié)分枝定界法40

整數(shù)規(guī)劃的分枝定界法步驟

從以上解題過程可得用分枝定界法求解目標(biāo)函數(shù)值最大的整數(shù)規(guī)劃的步驟，我們將求解的整數(shù)規(guī)劃問題稱為A，將與其相對(duì)應(yīng)的線性規(guī)劃問題稱為B：

第一步：求解問題B，可得以下情況之一：

1.B沒有可行解，則A也沒有可行解，求解過程停止。

2.B有最優(yōu)解，且符合問題A的整數(shù)條件，則B的最優(yōu)解即為A的最優(yōu)解，求解過程停止。

3.B有最優(yōu)解，但不符合A的整數(shù)條件，記其目標(biāo)函數(shù)值為z1。

第二步：確定A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界，其上界即為

=z1,再用觀察法找到A的一個(gè)整數(shù)可行解，求其目標(biāo)函數(shù)值作為z*的下界，記為z。

第三步：判斷

是否等于z

。若相等，則整數(shù)規(guī)劃最優(yōu)解即為其目標(biāo)函數(shù)值等于z的A的那個(gè)整數(shù)可行解；否則進(jìn)行第四步。41整數(shù)規(guī)劃的分枝定界法步驟

第四步：在B的最優(yōu)解中選一個(gè)最遠(yuǎn)離整數(shù)要求的變量，不妨設(shè)此變量為xj=bj，以[bj]表示小于bj的最大整數(shù)，構(gòu)造以下兩個(gè)約束條件，并加入問題B，得到B的兩個(gè)分枝B1和B2。xj≤[bj]和xj≥[bj]+1

第五步：求解B1和B2

。修改A問題的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上下界，

和z。

第六步：比較和剪枝。各分枝的最優(yōu)目標(biāo)函數(shù)值中若有小于z者，則剪掉這枝（用打Х表示），即以后不再考慮了。若大于z

，則不符合整數(shù)條件，則重復(fù)第三步至第六步，直至

，求出最優(yōu)解為止。對(duì)于求目標(biāo)函數(shù)值最小的整數(shù)規(guī)劃的求解步驟與上述步驟基本相似。42§4整數(shù)規(guī)劃的分枝定界法例9用分枝定界法求解整數(shù)規(guī)劃Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0且x1,x2為整