數(shù)模往屆2013整數(shù)

2.

整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃建?！麛?shù)線性規(guī)劃模型整數(shù)線性規(guī)劃的解法特殊形式的整數(shù)規(guī)劃問題整數(shù)線性規(guī)劃建模示例引例1

資源分配問題：某個中型的百貨商場要求售貨人員每周工作5天，連續(xù)休息

2天，工資200元/周，已知對售貨人員的需求經(jīng)過統(tǒng)計(jì)分析如下表，如何安排可使配備銷售人員的總費(fèi)用最少?星期—二三四五六日所需售貨員人數(shù)18151216191412開始休息的人數(shù)x1x2x3x4x5x6x7設(shè)決策變量如上,

建立規(guī)劃模型如下：min

z

=

200(

x1

+

x2

+

x3

+

x4

+

x5

+

x6

+

x7

)x2

+

x3

+

x4

+

x5

+

x6

?

18

x6

+

x7

+

x1

+

x2

+

x3

?

193

4

5

6

7x

+

x

+

x

+

x

+

x

?

15x4

+

x5

+

x6

+

x7

+

x1

?

127

1

2

3

4x

+

x

+

x

+

x

+

x

?

14x1

+

x2

+

x3

+

x4

+

x5

?

12x5

+

x6

+

x7

+

x1+x2

?

16

x1

,

x2

,

x3

,

x4

,

x5

,

x6

,

x7

?

0x1

,x2

,x3

,x4

,x5

,x6

,x7為整數(shù)0.605.663.641.621.626.672.63要求變量取為整數(shù)的線性規(guī)劃問題，稱為整數(shù)線性規(guī)劃問題。如果所有的變量都要求為整數(shù)，稱之為純整數(shù)規(guī)劃或全整數(shù)規(guī)劃；如果僅有一部分變量要求為整數(shù)，則稱為混合整數(shù)規(guī)劃。整數(shù)線性規(guī)劃的一般形式(極小化)是：整數(shù)線性規(guī)劃的模型jx

為整數(shù),j=1,2,,nn

ai

,

j

x

j

￡

(=)bj

,

i

=

1,2,,

mj

=1nmin

z

=

c

j

x

jj

=1AX

￡

(=)bX為整數(shù)(或部分分量為整數(shù))min

z

=

CT

X不考慮整數(shù)約束，可得x1=4.8, x2=0,目標(biāo)值96;但由顯然可得最優(yōu)整數(shù)解為x1＝4, x2＝1，目標(biāo)值90；舉例——圖解max

z

=

40x1

+

90x29

x1

+

7

x2

￡

567

x1

+

20

x2

￡

70s.t.2x1

?

0,

x

?

0x1,x2為整數(shù).上界U＝356，(4.81,1.52)下界L＝0，(0,0)將原問題分成2個子問題：原規(guī)劃加上x1≤4；原規(guī)劃加上x1≥5；

s.t.

Ax

=

b

x

?

0

min

cT

xx

?

Z

niix

?

x

+

10

x

?

Zx

￡

xi0i基本求解方法1)——分支限界算法基本思路：先去掉整數(shù)約束求解相應(yīng)的線性規(guī)劃，若解x0為整數(shù)則結(jié)束，否則該線性規(guī)劃的最優(yōu)值cTx0是IP問題的上界U，而IP的任一可行解對應(yīng)一個下界L；進(jìn)一步將可行域分枝，逐步減少上界和增大下界，二者相等時終止算法。

mincT

xs.t.

Ax

=

b

x

?

0s.t.

Ax

=

bx

?

0x

?

Z

nmin

cT

x深度優(yōu)先寬度優(yōu)先max

z=

5x1

+

8x2s.t.

x1

+

x2

￡

61

2x1

?

0,

x2

?

05

x

+

9x

￡

45x1,x2為整數(shù).LP0x=(2.25,

3.75)Z*=41.25LP1x=(3,

3)Z*=39x2

￡

3

x2

?

4LP2x=(1.8,

4)Z*=41LP3x=(1,4.44)Z*=40.561

1x

￡

1

x

?

2LP4無可行解LP5x=(1,

4)Z*=37x2

￡

4x1

?

5LP6x=(0,

5)Z*=40Z

=

41.25Z

=

0Z

=

41Z

=

39Z

=

40.56Z

=

39Z

=

40Z

=

40終止分支準(zhǔn)則：得整數(shù)解無可行解最優(yōu)值小于下界max

z=

5x1

+

8x2s.t.

x1

+

x2

￡

6x1

?

0,

x2

?

05

x1

+

9x2

￡

45x1,x2為整數(shù).LP0x=(2.25,

3.75)Z*=41.25LP1x=(3,

3)Z*=39x2

￡

3

x2

?

4LP2x=(1.8,

4)Z*=41LP3x=(1,4.44)Z*=40.561

1x

￡

1

x

?

2LP4無可行解x=(1,

4)Z*=37x2

￡

4x=(0,

5)Z*=40Z

=

41.25Z

=

0Z

=

41.25Z

=

39Z

=

41Z

=

39Z

=

40.56

LP5Z

=

39終止分支準(zhǔn)則：得整數(shù)解無可行解3)最優(yōu)值小于下界Z

=

41Z

=

39Z

=

40.56x1

?

5

Z

=

39LP6

Z

=

40Z

=

40寬度優(yōu)先max

z=

5x1

+

8x2s.t.

x1

+

x2

￡

6x1

?

0,

x2

?

05

x1

+

9x2

￡

45x1,x2為整數(shù).LP0x=(2.25,

3.75)Z*=41.25LP1x=(3,

3)Z*=39x2

￡

3

x2

?

4LP2x=(1.8,

4)Z*=41LP3x=(1,4.44)Z*=40.561

1x

￡

1

x

?

2LP4無可行解LP5x=(1,

4)Z*=37x2

￡

4x=(0,

5)Z*=40Z

=

41.25Z

=

0Z

=

41.25Z

=

39Z

=

41Z

=

39Z

=

41Z

=

39終止分支準(zhǔn)則：得整數(shù)解無可行解最優(yōu)值小于下界Z

=

41Z

=

39Z

=

40x1

?

5

Z

=

40LP6

Z

=

41Z

=

40深度優(yōu)先求解方法2——割平面算法基本思路：先利用線性規(guī)劃單純形算法得到的相應(yīng)線性規(guī)劃的最優(yōu)頂點(diǎn)，割去最優(yōu)頂點(diǎn)所在的一點(diǎn)區(qū)域，但不丟掉可行整數(shù)解，最終使得對應(yīng)的最優(yōu)頂點(diǎn)為整數(shù)頂點(diǎn)?；拘再|(zhì)：割平面法割去了整數(shù)規(guī)劃問題相應(yīng)的線性規(guī)劃問題的非整數(shù)最優(yōu)解所在的部分區(qū)域；割平面未割去原整數(shù)規(guī)劃問題的任一可行解，即未割去其相應(yīng)的線性規(guī)劃問題的任一可行整數(shù)解。整數(shù)最優(yōu)解特殊形式的整數(shù)規(guī)劃問題背包問題(KnapsackProblem)模型:假設(shè)n種不同的科學(xué)設(shè)備要求裝入“神X”飛船中,對于i=1,2……n,設(shè)ci>0是每個i類型設(shè)備的單位科學(xué)價(jià)值以及ai>0是單位重量(或體積),若整個重量(或體積)的限度是b,那么最大化裝載的整個設(shè)備價(jià)值的模型如下:ixi是裝載第i種設(shè)備的數(shù)量.x

?

Z

+

,

i

=

1,2,,

nc

xi

ia

x

￡

bi

imax

z

=s.t.ni

=1ni

=1注記:二維或多維背包問題:

同時考慮體積和重量等其它約束限制時;求解方法－－動態(tài)規(guī)劃方法(以后討論,LINDO軟件有現(xiàn)成程序)；更常見的是設(shè)備已經(jīng)打包,只有帶或不帶之說,這樣xi僅取0或1,即為0-1背包問題；計(jì)算價(jià)值/體積比求解方法0-1背包問題求解示例max

z

=

2

x1

+

9

x2

+

3

x3

+

8

x4

+

10

x5

+

6

x6

+

4

x7

+

10

x8s.t.

x1

+

3

x2

+

4

x3

+

3

x4

+

3

x5

+

x6

+

5

x7

+

10

x8

￡

15xi

?

{0,1},

i

=

1,2,,82

,

9

,

3

,

8

,

10

,

6

,

4

,

10,

15,111

3

4

3

3

1

5

102

3,

3

, 2

2

,

3

6,

41

1

14

81

111

14 4

<45<

104

3

31

10

5最優(yōu)解？

(1,

1,

1,

1,

1,

1,

0,

0)特殊形式的整數(shù)規(guī)劃問題旅行售貨員問題TSP(Traveling

Salesperson

Problem)

:

假設(shè)有一個旅行售貨員從某個城市出發(fā)，通過若干城市各一次且僅一次，最后回到原出發(fā)城市，問如何選擇行走路線，能使行程最短？設(shè)有n個不同城市以i=1,2,…,n表示,

設(shè)dij表示城市i到城市j的距離，則該問題建模如下:xij是標(biāo)識是否選擇從走城市i到城市j的路線.s.t.TSPmin

z

=nnxij

?

{0,1},

i,

j

=

1,2,,

nn

ni

dij

xij=1

j

=1j

?ij

=1

xij

=

1,

i

=

1,2,,

ni

?

ji

=1

xij

=

1,

j

=

1,2,,

ns.t.d

xmin

z

=ijijx

?

1,

j

=

1,2,,

nij

ijnj

=1

x

?

1,

i

=

1,2,,

ni

?

jni

=1i

?

jxij

?

{0,1},

i,

j

=

1,2,,

n推銷員問題ni

=1nj

=1fi最少一次v2v1v311202vv13v1120TSP問題最優(yōu)示意圖推銷員問題最優(yōu)示意圖2輛鐵路平板車的裝貨問題：要把7種規(guī)格的包裝箱C1～C7裝到2輛鐵路平板車上去,包裝箱的寬和高都是相同的,

但厚度(t:cm)及重量(w:kg)是不同的.下表給出了包裝箱C1～C7

的厚度、重量及數(shù)量:箱名數(shù)量C1C2C3C4C5C6C7t(cm)48.752.061.372.048.752.064.0w(kg)200030001000500400020001000數(shù)目8796648建模示例:鐵路平板車的裝貨問題——美國數(shù)模競賽1988(B)每輛平板車有10.2m長的地方可以用來裝箱(像面包片那樣)，載重為40t。由于當(dāng)?shù)刎涍\(yùn)的限制，對于C5、C6、C7三類包裝箱的總數(shù)有特定的約束,他們所占有的空間(厚度)不得超過302.7cm。試建立數(shù)學(xué)模型將這些包裝箱裝到平板車上去，并使浪費(fèi)的空間最小.分析:包裝箱共總89t，總厚27.5m，都超過了所能裝載的限量：2×40＝80t和2×10.2＝20.4m。于是需選擇裝載標(biāo)準(zhǔn)——浪費(fèi)最小且滿足要求或滿足限量且裝載量最大.特殊約束:數(shù)量約束假設(shè):

xij——在第i輛平板車裝包裝箱Cj的個數(shù)+xij

?

Z11

21x

+

x

￡

8x12

+

x22

￡

713

23x

+

x

￡

9x14

+

x24

￡

6x15

+

x25

￡

6x16

+

x26

￡

4x17

+

x27

￡

82x11

+

3x12

+

x13

+

0.5x14

+

4x15

+

2x16

+

x17

￡

4025

26

27+

0.487

x

+

0.52

x

+

0.64

x

￡

10.2重量約

2x21

+

3x22

+

x23

+

0.5x24

+

4x25

+

2x26

+

x27

￡

40束厚

0.487

x11

+

0.52

x12

+

0.613

x13

+

0.72

x14度

+

0.487

x15

+

0.52

x16

+

0.64

x17

￡

10.2約

0.487

x21

+

0.52

x22

+

0.613

x23

+

0.72

x24束0.487

x15

+

0.52

x16

+

0.64

x17

￡

3.0270.487

x25

+