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

第八章

整數(shù)規(guī)劃1整數(shù)規(guī)劃問題線性規(guī)劃的決策變量取值可以是任意非負實數(shù)，但許多實際問題中，只有當決策變量的取值為整數(shù)時才有意義。例如，產(chǎn)品的件數(shù)、機器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分數(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)解進行“舍入化整”以得到與最優(yōu)解相近的整數(shù)解。“舍入化整”一般是不可行的：化整后的解有可能成為非可行解；雖是可行解，卻不是最優(yōu)解。例如一、問題的提出

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

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

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)不考慮整數(shù)約束則是一個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ù)解，比較它們相應的目標函數(shù)值，最優(yōu)的目標函數(shù)值所對應的解就是整數(shù)規(guī)劃的最優(yōu)解。實用性：只有兩個決策變量，可行的整數(shù)解較少。

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

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

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

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

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

約束條件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0為整數(shù)。如果去掉最后一個約束，就是一個線性規(guī)劃問題。利用圖解法，7得到線性規(guī)劃的最優(yōu)解為x1=2.44,x2=3.26,目標函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4,x2=2,目標函數(shù)值為14。性質(zhì)1：任何求最大目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值；任何求最小目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(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變量用《管理運籌學》軟件求解得：

x1=5x2=2x3=2用《管理運籌學》軟件求解得：

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

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

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

在東區(qū)由A1

，A2

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

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

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

，A9

，A10

三個點中至少選兩個。一、投資場所的選擇Aj

各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測情況見下表所示(單位：萬元)。但投資總額不能超過720萬元，問應選擇哪幾個銷售點，可使年利潤為最大?10解：設：0--1變量xi=1(Ai點被選用）或0(Ai點沒被選用）。這樣我們可建立如下的數(shù)學模型：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ī)劃的應用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個地點建立銷售門市部。實際投資額為100+120+70+90+160+180=720第三節(jié)、整數(shù)規(guī)劃的應用12例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人月，機器有100臺月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為150萬元，大號為200萬元。現(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。二、固定成本問題第三節(jié)、整數(shù)規(guī)劃的應用13解：這是一個整數(shù)規(guī)劃的問題。設x1，x2，x3分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設yi=1(當生產(chǎn)第i種容器,即xi＞0時)或0（當不生產(chǎn)第i種容器即xi=0時）引入約束xi≤Myi

，i=1，2，3，M充分大，以保證當yi

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

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

=1(當指派第i人去完成第j項工作時)或0（當不指派第i人去完成第j項工作時)．這可以表示為一個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(甲只能干一項工作)

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

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

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

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

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

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

對于有m

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

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

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

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

問應該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運輸費用之和最小?

（2）

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

a)

設xij為從Ai運往Bj

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

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

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

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

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

如果由于政策要求必須在A2，A3地建一個廠，應在哪幾個地方建廠?

解：

設xij為從Ai運往Bj

的運輸量(單位千箱)，yi=1(當Ai

被選中時)或0（當Ai

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

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地建一個廠)

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

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

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

項目C：第二年初需要投資，到第五年未能回收本利140%，但規(guī)定其投資額或為2萬元或為4萬元或為6萬元或為8萬元。

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

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

i

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

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

是非負整數(shù)變量，并規(guī)定：第2年投資C項目8萬元時，取值為4；第2年投資C項目6萬元時，取值為3；第2年投資C項目4萬元時，取值為2；第2年投資C項目2萬元時，取值為1；第2年不投資C項目時，取值為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ī)劃的應用252）約束條件：第一年：年初有100000元，D項目在年末可收回投資，故第一年年初應把全部資金投出去，于是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ī)劃的應用26關于項目A的投資額規(guī)定:x1A≥40000y1A

，x1A≤200000y1A

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

y1A=0時，x1A=0；當y1A=1時，x1A≥40000。關于項目B的投資額規(guī)定:x3B≥30000y3B

，x3B≤50000y3B

；保證當

y3B=0時，x3B=0；當y3B=1時，50000≥

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

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

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

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

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

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

31第四節(jié)分枝定界法這樣就把相應的線性規(guī)劃的可行域分成兩個部分，如圖所示。??????????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é)分枝定界法求解相應的線性規(guī)劃的最優(yōu)解問題2相應的線性規(guī)劃的最優(yōu)解：x1=3，x2=20/7，Z2=226/7問題3相應的線性規(guī)劃的最優(yōu)解：x1=4，x2=1，Z3=29第四步，定界過程LP3的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是29，大于原有下界0，則新的下界為29；現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為226/7。LP2的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值226/7大于現(xiàn)有下界，則應繼續(xù)分枝。第五步，分枝過程將不滿足整數(shù)約束的變量x2進行分枝，構(gòu)造兩個新的約束條件：

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é)分枝定界法求解相應的線性規(guī)劃的最優(yōu)解問題4相應的線性規(guī)劃的最優(yōu)解：

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

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é)分枝定界法求解相應的線性規(guī)劃的最優(yōu)解：問題6相應的線性規(guī)劃的最優(yōu)解：

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

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é)分枝定界法求解相應的線性規(guī)劃的最優(yōu)解問題8相應的線性規(guī)劃的最優(yōu)解：

x1=2，x2=3，Z8=27問題9相應的線性規(guī)劃的最優(yōu)解：x1=7/5，x2=4，Z9=142/5第十步，定界過程LP8的最優(yōu)解，滿足整數(shù)約束，不必再分枝，下界仍為29；現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為29。雖然LP9的解仍不滿足整數(shù)約束的要求，它的目標函數(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ī)劃的分枝定界法步驟

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

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

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

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

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

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

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

第三步：判斷

是否等于z

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

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

第五步：求解B1和B2

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

和z。

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

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

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