第八章整數(shù)規(guī)劃§1整數(shù)規(guī)劃的圖解法§2整數(shù)規(guī)劃的計(jì)算機(jī)求解§3整數(shù)規(guī)劃的應(yīng)用§4整數(shù)規(guī)劃的分枝定界法§1整數(shù)規(guī)劃的圖解法例1.某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種儀器設(shè)備的生產(chǎn)，已知生產(chǎn)儀器設(shè)備需要A、B兩種材料的消耗以及資源的限制，如右表。問題：工廠應(yīng)分別生產(chǎn)多少件甲、乙種儀器設(shè)備才能使工廠獲利最多？解、目標(biāo)函數(shù)：Maxz=x1+x2約束條件：s.t.3x1+2x2≤102x2≤5x1，x2≥0為整數(shù)不考慮整數(shù)約束得到最優(yōu)解：

x1=1.667，x2=2.5；z=4.167考慮整數(shù)約束得到最優(yōu)解：

x1=2，x2=2；

z=4整數(shù)規(guī)劃的最優(yōu)目標(biāo)值小于相應(yīng)線性規(guī)劃的最優(yōu)目標(biāo)值(相當(dāng)于附加一個(gè)約束)§2整數(shù)規(guī)劃的計(jì)算機(jī)求解例2：

Maxz=15x1+10x2+7x3

s.t.5x1-10x2+7x3≤86x1+4x2+8x3≤12-3x1+2x2+2x3≤10x1,x2,x3≥0為整數(shù)例2：

Maxz=15x1+10x2+7x3

s.t.5x1-10x2+7x3≤86x1+4x2+8x3≤12-3x1+2x2+2x3≤10x1,x2,x3≥0

x3為整數(shù)

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

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

x1=1x2=1.5x3=0z=30二、固定成本問題例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如右表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動(dòng)力有300人月，機(jī)器有100臺(tái)月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬元，中號(hào)為150萬元，大號(hào)為200萬元。現(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。

解：這是一個(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-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj

為0--1變量，i=1,2,3§3整數(shù)規(guī)劃的應(yīng)用(2)例6．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如右表所示，問應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。

解：引入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

為0--1變量，i,j=1,2,3,4***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

§3整數(shù)規(guī)劃的應(yīng)用(3)三、指派問題

有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同。現(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總的效率最高，這就是指派問題。

四、分布系統(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))如右表所示。

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

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

解：

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)量限制)b）增加約束：y2+y3=1

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≥0yi為0--1變量，i=1,2,3,4,5；j=1,2,3***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

§3整數(shù)規(guī)劃的應(yīng)用(4)§3整數(shù)規(guī)劃的應(yīng)用(6)2）約束條件：第一年：年初有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；關(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。3）目標(biāo)函數(shù)及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.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，yiA，yiB=0或1，i=1,2,3,4,5y2C=0，1，2，3，4xiA，xiB，xiC，xiD≥0(i=1、2、3、4、5）§4整數(shù)規(guī)劃的分枝定界法(1)問題（A）Minz=c1x1+c2x2+…+cnxn記問題（B）為去掉整數(shù)約束的問題（A）

s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0為整數(shù)在分枝定界法過程中求解問題(B)，應(yīng)有以下情況之一：①(B)無可行解，則(A)亦無可行解，停止對(duì)此問題的計(jì)算；②(B)有最優(yōu)解，并滿足整數(shù)約束，即同時(shí)為(A)的最優(yōu)解，那么z*同時(shí)是當(dāng)前問題(A)最優(yōu)目標(biāo)值的上界和下界。停止對(duì)這個(gè)問題的計(jì)算；③(B)有最優(yōu)解x及最優(yōu)值z(mì)但不符合整數(shù)條件。這時(shí)得到當(dāng)前問題(A)最優(yōu)目標(biāo)值的一個(gè)下界z＝z,于是通過以下判斷可對(duì)此問題進(jìn)一步計(jì)算。分枝定界法的計(jì)算過程：1、對(duì)原問題(A)，求解松弛問題(B)。根據(jù)上面分析，若出現(xiàn)情況①，②則停機(jī)。若情況③發(fā)生，得到(A)問題最優(yōu)值的一個(gè)下界。我們?nèi)握?A)問題的一個(gè)可行解，那么對(duì)應(yīng)的目標(biāo)函數(shù)值是(A)最優(yōu)值的一個(gè)上界zˉ。即得到z＜z*

＜zˉ。(注：找(A)問題的可行解往往需要較大的計(jì)算量，這時(shí)可簡(jiǎn)單記zˉ＝+，而先不必費(fèi)很大力量去求較好的上界。從以下分析可以看到，找到一個(gè)好的最優(yōu)目標(biāo)值上界，將對(duì)算法的快速求得目標(biāo)非常有效。)，轉(zhuǎn)2，進(jìn)行以下一般步的迭代；

§4整數(shù)規(guī)劃的分枝定界法(2)2、對(duì)當(dāng)前問題進(jìn)行分枝和定界：分技：無妨設(shè)當(dāng)前問題為(A)，其松弛問題(B)的最優(yōu)解不符合整數(shù)約束，任取非整數(shù)的分量xr

。構(gòu)造兩個(gè)附加約束：xr≤[xr]

和xr≥[xr]+1，對(duì)(A)分別加入這兩個(gè)約束，可得到兩個(gè)子問題(A1)和(A2)，顯然這兩個(gè)子問題的可行解集的并是(A)的可行解集；定界：根據(jù)前面分析，對(duì)每個(gè)當(dāng)前問題(A)可以通過求解松弛問題(B)，以及找(A)的可行解得到當(dāng)前問題的上、下界zˉ和z

。

對(duì)一般迭代步，設(shè)根據(jù)分枝定界方法得到了原問題(A)的一個(gè)同層子問題(AI)，i＝1，2，...，n之和的分解。這里的同層子問題是指每個(gè)子問題(AI)都是(A)經(jīng)過相同分枝次數(shù)得到的。3、比較與剪枝：

對(duì)當(dāng)前子問題進(jìn)行考察，若不需再進(jìn)行計(jì)算，則稱之為剪枝。一般遇到下列情況就需剪枝：①(B)無可行解；②(B)的最優(yōu)解符合整數(shù)約束；③(B)的最優(yōu)值z(mì)≥zˉ。通過比較，若子問題不剪枝則返回2。

分枝定界法當(dāng)所有子問題都剪枝了，即沒有需要處理的子問題時(shí)，達(dá)到當(dāng)前上界zˉ的可行解即原問題的最優(yōu)解，算法結(jié)束。§4整數(shù)規(guī)劃的分枝定界法(4)

隱枚舉法是求解0—1規(guī)劃最常用的方法之一對(duì)于n個(gè)決策變量的完全0—1規(guī)劃，其可行點(diǎn)最多有2n

個(gè)，當(dāng)n較大時(shí)其計(jì)算量大得驚人。隱枚舉法的基本思想是根據(jù)0—1規(guī)劃的特點(diǎn)，進(jìn)行分技逐步求解。1、用于隱枚舉法的0—1規(guī)劃標(biāo)準(zhǔn)形式：為了計(jì)算的方便，需要把一般的0—1規(guī)劃問題等價(jià)地化成下列標(biāo)準(zhǔn)形式

Minf=c1x1+c2x2+…+cnxncj≥0j=1,2,…,n

s.t.ai1x1+ai2x2+…+ainxn≤bii=1,2,…,mx1，x2，…，xn=0或1下面說明一個(gè)完全的0—1規(guī)劃問題可以化為等價(jià)的標(biāo)準(zhǔn)形式：(1)若目標(biāo)函數(shù)求最大：Maxz，可令f=-z，變?yōu)榍笞钚inf；(2)若目標(biāo)函數(shù)的系數(shù)有負(fù)值時(shí)，如cj＜0。那么，可以令相應(yīng)的yj=1-xj；(3)當(dāng)某個(gè)約束不等式是“≥”時(shí)，只需兩端同乘以-1，即變?yōu)椤啊堋保?4)當(dāng)某個(gè)約束是等式約束時(shí)，可得到兩個(gè)方向相反的不等式?！?整數(shù)規(guī)劃的分枝定界法(5)隱枚舉法的基本過程：1、將0—1規(guī)劃問題化為標(biāo)準(zhǔn)形式，設(shè)其最優(yōu)解為x*，最優(yōu)目標(biāo)值為f*。顯然x=0時(shí)，目標(biāo)值f＝0是不考慮線性不等式約束的最小解，于是f*≥0。若x=0是可行解，那末f＝0是該問題的最優(yōu)解，結(jié)束計(jì)算。否則，置所有分量為自由變量。轉(zhuǎn)2；2、任選一自由變量xk，令xk為固定變量，分別固定為xk=0與xk＝1，令所有自由變量取零值，則得到兩個(gè)分枝。對(duì)每個(gè)分枝的試探解進(jìn)行檢驗(yàn)（把自由變量逐次定為固定變量的順序可以是任意的，在不進(jìn)行先驗(yàn)考察時(shí)，常按指標(biāo)變量從小到大的順序進(jìn)行