運籌學(xué)-課件ch3整數(shù)

整數(shù)規(guī)劃數(shù)學(xué)模型純整數(shù)規(guī)劃的求解0－1規(guī)劃的求解Mathematical

Model

ofIPSolving

Pure

Integer

ProgrammingSolving

Binary

Integer

ProgrammingChapter

3

整數(shù)規(guī)劃Integer

Programming運籌學(xué)Operations

Research3.1

整數(shù)規(guī)劃數(shù)學(xué)模型Mathematical

Model

of

IP一個規(guī)劃問題中要求部分或全部決策變量是整數(shù)，則這個規(guī)劃稱為整數(shù)規(guī)劃。當要求全部變量取整數(shù)值的，稱為純整數(shù)規(guī)劃；只要求一部分變量取整數(shù)值的，稱為混合整數(shù)規(guī)劃。如果模型是線性的，稱為整數(shù)線性規(guī)劃。本章只

整數(shù)線性規(guī)劃。很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題變量是人數(shù)、機器設(shè)備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù)對某一個項目要不要投資的決策問題，可選用一個邏輯變量x，當x=1表示投資，x=0表示不投資；的合理安排問題，當變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)值的一類變量。3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP星期二【例3-1

】備用來有一背包可以裝10公斤重、0.025m3的物品。他準、乙兩種物品，每件物品的重量、體積和價值如表3-1所示。問兩種物品各裝多少件，所裝物品的總價值最大？表3-1

1

2x

,x

0,且均取整數(shù)2x1

2.5x2

251.2x1

0.8x2

10【解】設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學(xué)模型為：max

Z

4x1

3x2(3-1)3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP物品重量（公斤/每件）體積（m3/每件）價值(元/每件)甲1.20.0024乙0.80.00253星期二如果不考慮x1、x2取整數(shù)的約束（稱為（3-1）的松弛問題），線性規(guī)劃的可行域如圖3-1中的陰影部分所示。3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP圖3-1星期二星期二3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型MathematicalModel

of

IP用圖解法求得點B為最優(yōu)解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必須取整數(shù)值，實際上整數(shù)規(guī)劃問題的可行解集只是圖中可行域內(nèi)的那些整數(shù)點。用湊整法來解時需要比較四種組合，但（4，7）、（4，8）（3，8）都不是可行解，（3，

7）雖屬可行解，但代入目標函數(shù)得Z=33,并非最優(yōu)。實際上

問題的最優(yōu)解是（5，5），Z=35。即兩種物品各裝5件，總價值35元。由圖3－1知，點（5，5）不是可行域的頂點，直接用圖解法或單純形法都無法求出整數(shù)規(guī)劃問題的最優(yōu)解，因此求解整數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。還有些問題用線性規(guī)劃數(shù)學(xué)模型無法描述，但可以通過設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學(xué)模型。3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP【例3-2

】在例3-1中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其立下列幾種情形的數(shù)學(xué)模型，使所裝物品價值最大。所裝物品不變；如果選擇旅行箱，則只能裝載丙和丁兩種物品，價值分別是4和3，載重量和體積的約束為1.8x1

0.6x2

121.5x1

2x2

20【解】此問題可以建立兩個整數(shù)規(guī)劃模型，但用一個模型描述更簡單。引入0－1變量（或稱邏輯變量）yi，令1,i

1,2yi

采用第i種方式裝載時0，

不采用第i種方式裝載時i=1,2分別是采用背包及旅行箱裝載。星期二（1）由于所裝物品不變，式(3-1)約束左邊不變，整數(shù)規(guī)劃數(shù)學(xué)模型為1

2y

y

1max

Z

4x1

3x2

1.2x1

0.8x2

10

y1＋12

y2

2x1

2.5x2

25

y1

20

y2xi

0,且取整數(shù),

yi

0或1

i

1,2（2）

由于不同載體所裝物品不一樣，數(shù)學(xué)模型為1

2

1(a)(b)(c)(d

)1.8x

0.6x

12

My2x1

2.5x2

25

My21.5x1

2x2

20

My1

y1

y2

1max

Z

4x1

3x21.2x1

0.8x2

10＋My2x1,x2

0,且均取整數(shù),y

0或13.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP星期二式中M為充分大的正數(shù)。從上式可知，當使用背包時(y1=1，y2=0)，式(b)和(d)是多余的；當使用旅行箱時(y1=0，y2=1)，式：(a)和(c)是多余的。上式也可以令y1

y,

y2

1

y同樣可以 對于有m個條件互相排斥、有m（≤m、≥m）個條件起作用的情形。3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP星期二3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP（1)右端常數(shù)是k個值中的一個時，類似式(3-2)的約束條件為

1k

kn

yii1

aij

x

jj

1

bi

yi

，i1（2)對于m組條件中有k（≤m）組起作用時，類似式(3-3)的約束條件寫成

1n

k

yii1

aij

x

jj

1

bi

Myi

，這里yi=1表示第i組約束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i個約束起作用。當約束條件是“≥”符號時右端常數(shù)項應(yīng)為bi

（3)對于m個條件中有k（≤m）個起作用時，約束條件寫成n

k

m

k

yii1

aij

x

jj

1

bi

Myi

，星期二3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP【例3-3】試引入0－1變量將下列各題分別表達為一般線性約束條件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，則x2≥0，否則x2≤8（3）x2取值0，1，3，5，7【解】

（1）3個約束只有1個起作用1

2

31

2

3x1

x2

6

y1M4x1

6x2

10

y2

M

y

y

y

2

yj

0或1，j

1,2,32x

4x

20

y

M

或2111y

yM)M24x1

6x2x

4xxx

y

j或，j

1,120,3星期二（3）右端常數(shù)是5個值中的1個3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP（2）兩組約束只有一組起作用星期二【例3-4】企業(yè)計劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工、外協(xié)加工任意一種形式生產(chǎn)．已知每種生產(chǎn)的固定費用、生產(chǎn)該產(chǎn)品的單件成本以及每種生產(chǎn)形式的最大加工數(shù)量（件）限制如表3－2所示，怎樣安排產(chǎn)品的加工使總成本最?。?－2【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)量，生產(chǎn)費用為0j

j

jj

jj(x

j

0)k

c

x

(x

0)C

(x

)

3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP固定成本（元）變動成本（元／件）最大加工數(shù)（件）本企業(yè)加工50081500外協(xié)加工Ⅰ80052000外協(xié)加工Ⅱ6007不限星期二式中kj是固定成本，cj是單位產(chǎn)品成本．設(shè)0－1變量yj，令j

1,

2,

3y

j

1

采用第j種加工方式，xj

0時0

不采用在第j種加工方式，xj＝0時min

Z

(500

y1

8x1

)

(800

y2

5x2

)

(600

y3

7x3

)數(shù)學(xué)模型為2121x

2000,1500xxxx

jx

j

My

j

j

1,02,3y

j

或，j

1,0213.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP（3-4）式（3-4）中是處理xj與yj一對變量之間邏輯關(guān)系的特殊約束，當xj>0時yj=1,當xj＝0時，為使Z最小化，有yj=0。例3-4是混合整數(shù)規(guī)劃問題．用WinQSB

求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=25400.x

j

Myj

0星期二作業(yè)：習(xí)題

3.1～3.61.線性整數(shù)規(guī)劃模型的特征2.

純（混合）整數(shù)規(guī)劃3.0－1規(guī)劃模型的應(yīng)用3.1

整數(shù)規(guī)劃的數(shù)學(xué)模型Mathematical

Model

of

IP下一節(jié)：純整數(shù)規(guī)劃的求解星期二3.2

純整數(shù)規(guī)劃的求解Solving

Pure

IntegerProgramming3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming求解純整數(shù)規(guī)劃的分枝定界法分枝定界法的步驟：求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界；檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算,若還存在非整數(shù)解并且目標值大于（max）整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。星期二【解】先求對應(yīng)的松弛問題（記為LP0）：1

22x

x

0,22.5x

25LP0:

x4x1

3x2x1

10.2x.82

101max

Z用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.7,如下圖所示。

1

2x

,x

0,且均取整數(shù)2x1

2.5x2

251.2x1

0.8x2

103.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming【例3-5

】用分枝定界法求解例5.1max

Z

4x1

3x2星期二1.2x1

0.8x2

102x1

2.5x2

25松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2o10

ABC8.33103.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming星期二ABC1

2x1,

x2

0

x1

3

2x

2.5x

251.2x1

0.8x2

10LP1:

max

Z

4x1

3x2LP1o10x134LP2LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.51x1,

x2

0

x

41.2x1

0.8x2

10

2x

2.5x

25LP2

:

1

2max

Z

4x1

3x2增加約束x1

3及x1

4得到兩個線性規(guī)劃x2①②10BCLP1LP3LP3:X=(4.33,6),Z3=35.331

2x1,

x2

0

2x1

2.5x2

25max

Z

4x1

3x21.2x1

0.8x2

10LP3

:

x

4，x

6及2選擇目標值最大的分枝LP2進行分枝，增加約束6x2①②A10x2

7不可行LP1:X=(3,7.6),Z1=34.8o10x13410x1oACLP134，,4可行域是一條線段21121即x1

xx21

0,5.x2x22258.x0x2.110LP

:434xx2m1Zaxx1

4及x1

5，到線性規(guī)劃LP4及LP5：由于Z3

Z1，選擇LP3進行分枝，增加約束6x2①②101

2x1,

x2

0

2x

2.5x

25LP5

:

max

Z

4x1

3x21.2x1

0.8x2

10

x1

5，x2

6LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP5LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5盡管LP1的解中x1不為整數(shù)，但Z5>Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7x1≤3

x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5無可行解x2≥73.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming3.2.2求解IP的割平面法設(shè)純整數(shù)規(guī)劃nijnjj

1,n,j

j

1max

j

1xbji

xa0x且cZ為整數(shù)，松弛問題nnaij

x

jj

1max

Z

cj

x

jj

1bi

xj

0，j

1,,

n的最優(yōu)解Tm,0(T)12

B1Xbb(B,,,b)bbb1＝設(shè)xi不為整數(shù)，kxk為非基變量xi

bi

aik

xk星期二將分離成一個整數(shù)與一個非負真分數(shù)之和：bi

及aikaik

aik

fik

,0

fi

1,0

fik

1bi

[bi

]

fi

,則有kk

fik

xkxi

[bi

]

fi

[aij

]xkkk

fik

xkxi

[bi

]

[aij

]xk

fi等式兩邊都為整數(shù)并且有kfi

fik

xk

fi

13.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming星期二ksi

fi

fik

xk此式稱為以xi行為源行（來源行）的割平面，或分數(shù)切割式，或R.E.Gomory(

)約束方程。將Gomory約束加入到松弛問題的最優(yōu)表中，用對偶單純形法計算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(shù)解。

0k加入松弛變量si得

fik

xkfi則3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming星期二例如，561x1行：移項：令45632

53

6

x

x

0加入松弛變量s1得

2

34563561s

x

x

同理，對于x2行有：

2

34133132s

x

x

3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming星期二

1

21

2x

,x

0且為整數(shù)x

2x

103.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming【例3-6】用割平面法求解下列IP問題max

Z

4x1

3x26x1

4x2

30

1

21

2x

,

x

0x

2x

10【解】放寬變量約束，對應(yīng)的松弛問題是max

Z

4x1

3x26x1

4x2

30星期二3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。表3-3最優(yōu)解X(0)＝(5/2，15/4),不是IP的最優(yōu)解。選擇表3-3的第一行(也可以選第二行)為源行4

24

52Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4星期二3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming分離系數(shù)后改寫成1214

210加入松弛變量x5得到

約束方程2將式(3-8)作為約束條件添加到表3－3中，用對偶單純形法計算，如表3－4所示星期二Cj43000bCBXBx1x2x3x4x54x1101/4－1/205/23x201－1/83/4015/40x500－1[－2]1－2→λj00－5/8－1/4↑04x1101/20－1/433x201－1/203/830x4001/21－1/21λj00－1/20－1/8最優(yōu)解X(1)＝(3，3)，最優(yōu)值Z＝21。所有變量為整數(shù)，X(1)就是IP的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，重復(fù)上述計算過程。3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming表3－4如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割。作業(yè)：習(xí)題

3.7，3.8理解分枝與定界的含義選擇合適的“

枝”生“

枝”掌握何時停止生“

枝”割平面法的基本原理分離源行，求出Gomory約束在最優(yōu)表中增加Gomory約束，用對偶單純形法迭代3.2

純整數(shù)規(guī)劃的求解Solving

Pure

Integer

Programming下一節(jié)：0－1規(guī)劃的求解星期二3.3

0－1規(guī)劃的求解Solving

BIP3.3.1

求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：找出任意一可行解，目標函數(shù)值為Z0原問題求最大值時，則增加一個約束c1

x1

c2

x2

cn

xn

Z0

(*)當求最小值時，上式改為小于等于約束列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢驗其它約束，若不滿足式（*），則認為不可行，若所有約束都滿足，則認為此解是可行解，求出目標值目標函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解3.3

0－1規(guī)劃的求解

Solving

BIP星期二【例3-7】用隱枚舉法求解下列BIP問題2

312

31x3x14x16x1

2x2

3x3

52x

2

x3

3

105x2

x3

6

42x

x

x

32x

4x

5

10max

Zx

j

或，j

1,120,3,4【解】（1）不難看出，當所有變量等于0或1的任意組合時，第一個約束滿足，說明第一個約束沒有約束力，是多余的，從約束條件中去掉。還能通過觀察得到X0＝(1，0，0，1)是一個可行解，目標值Z0

＝

11

是BIP問題的下界，構(gòu)造一個約：束

，原BIP問題變?yōu)?

3

5x4

113.3

0－1規(guī)劃的求解

Solving

BIP星期二星期二max

Z

x1

2x2

3x3

5x46

2x

2

3x3

5x4

113 5x2

x3

6x4

42x2

x3

x4

3(3

9a)(3

9b)(3

9c)(3

9d

)2x2

4x3

5x4

10x

j

0或1，j

1,2,3,4(2)

列出變量取值0和1的組合，共24＝16個，分別代入約束條件

判斷是否可行。首先判斷式（3-9a）是否滿足，如果滿足，接

下來判斷其它約束，否則認為不可行，計算過程見表3－7所示。3.3

0－1規(guī)劃的求解

Solving

BIPjXj3-9a3-9b3-9c3-9dZjjXj3-9a3-9b3-9c3-9dZj1(0,0,0,0)×9(1,0,0,0)×2(0,0,0,1)×10(1,0,0,1)√√√√113(0,0,1,0)×11(1,0,1,0)×4(0,0,1,1)×12(1,0,1,1)√√√√145(0,1,0,0)×13(1,1,0,0)×6(0,1,0,1)×14(1,1,0,1)√√√√137(0,1,1,0)×15(1,1,1,0)√×8(0,1,1,1)×16(1,1,1,1)√√√×表3－5(3)由表3-5知，BIP問題的最優(yōu)解：X＝（1，0，1，1），最優(yōu)值Z＝143.3

0－1規(guī)劃的求解

Solving

BIP星期二選擇不同的初始可行解，計算量會不一樣。一般地，當目標函數(shù)求最大值時，首先考慮目標函數(shù)系數(shù)最大的變量等于1，如例3-8。當目標函數(shù)求最小值時，先考慮目標函數(shù)系數(shù)最大

的變量等于0。在表3－7的計算過程中，當目標值等于14時，將其下界11改為14，可以減少計算量。3.3.2

分枝－隱枚舉法求解BIP問題將分枝定界法與隱枚舉法結(jié)合起來用，得到分枝－隱枚舉法。計算步驟如下：（1）將BIP問題的目標函數(shù)的系數(shù)化為非負，如max

Z

22

1

x2

,

max

Z

2x1

3x2

33.3

0－1規(guī)劃的求解

Solving

BIP星期二求主枝：目標函數(shù)是max形式時令所有變量等于1，得到目標值的上界；目標函數(shù)是min形式時令所有變量等于0，得到目標值的下界；如果主枝的解滿足所有約束條件則得到最優(yōu)解，否則轉(zhuǎn)下一步；分枝與定界：從第一個變量開始依次取“1”或“0”，求極大值時其后面的變量等于“1”，求極小值時其后面的變量等于“0”，用分枝定界法搜索可行解和最優(yōu)解。分枝－隱枚舉法是從非可行解中進行分枝搜索可行解，第（1）步到第（3）步用了隱枚舉法的思路，第（4）步用了分枝定界法的思路。2020年11月10日星期二當變量作了代換后，約束條件中的變量也相應(yīng)作代換。max

Z

2x1

3x2

x3

4x4令x2

1

x2

,max

Z

x3

2x1

3x2

4x4

33.3

0－1規(guī)劃的求解

Solving

BIP(2)變量重新排序：變量依據(jù)目標函數(shù)系數(shù)值按升排序；停止分枝和需要繼續(xù)分枝的原則：當某一子問題是可行解時則停止分枝并保留；不是可行解但目標值劣于現(xiàn)有保留分枝的目標值時停止分枝并剪枝；后續(xù)分枝變量無論取“1”或“0”都不能得到可行解時停止分枝并剪枝；當某一子問題不可行但目標值優(yōu)于現(xiàn)有保留分枝的所有目標值，則要繼續(xù)分枝。【例3-8】用分枝－隱枚舉法求解下列BIP問題343

43

5x43

6x4

4max

Z

63

x

3

5x

10(3

10a)(3

10b)(3

10c)x

j

0或1，j

1,2,3,43.3

0－1規(guī)劃的求解

Solving

BIP星期二解（1）目標函數(shù)系數(shù)全部非負，直接對變量重新排序max

Z x2

3x3

5x4

6x15

x3

6x4

3x1

4x3

x4

2x1

324x3

5x4

x1

10(3

10a)(3

10b)(3

10c)x

j

0或1，j

1,2,3,4（2）求主枝：令X＝(1，1，1，1)得到主枝1，檢查約束條件知(3-10c)不滿足，則進行分枝。（3）令x2=0同時令x3=0及x3=1得到分枝2和分枝3，X2和X3是可行解，分枝停止并保留，如表3-8及圖

示。3.3

0－1規(guī)劃的求解

Solving

BIP星期二星期二表3-8令x2=1同時令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1時只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝過程結(jié)束。整個計算過程可用圖3－2和表3-8表示。分枝(x2,

x3,

x4,

x1)3-10a3-10b3-10cZj可行性1(1,1,1,1)√√×16不可行2(0,0,1,1)√√√11可行3(0,1,1,1)√√√14可行4(1,0,1,1)√√√13可行5(1,1,0,1)×11不可行6(1,1,1,0)×10不可行3.3

0－1規(guī)劃的求解

Solving

BIP搜索到3個可行解，3個目標值中Z3最大，因此X3是最優(yōu)解，轉(zhuǎn)換到原問題的最優(yōu)解為X＝（1，0，1，1），最優(yōu)值Z＝14，計算結(jié)束。圖3－23.3

0－1規(guī)劃的求解

Solving

BIP星期二【例3-9】用分枝－隱枚舉法求解下列BIP問題jmin

Z

1

3x2

6x3

2x4

4x56 2x2

x3

7x4

x5

124x2

5x3

x4

3x5

10(3

11a)(3

11b)x

0或1，j

1,2,3,4解（1）令x2=1－x'及x

=1－x'，代入模型后整理得2

5

53jmin

Z

63