算法編程-舊-06.線性0第章

第1章線性規(guī)劃在人們的生產(chǎn)實(shí)踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟(jì)效益的問題。此類問題構(gòu)成了運(yùn)籌學(xué)的一個重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(LinearProgramming

簡記LP)則是數(shù)學(xué)規(guī)劃的一個重要分支。自從

1947年G.B.Dantzig

提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實(shí)用

益廣泛與深入。特別是在計(jì)算機(jī)能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。1.1

線性規(guī)劃問題1.1.1

線性規(guī)劃的實(shí)例與定義例

1.1

某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺銷售后的利潤分別為4

千元與3

千元。生產(chǎn)甲機(jī)床需用A、B機(jī)器加工，加工時間分別為每臺2

小時和1

小時；生產(chǎn)乙機(jī)床需用

A、B、C

三種機(jī)器加工，加工時間為每臺各一小時。若每天可用于加工的機(jī)器時數(shù)分別為A機(jī)器10

小時、B機(jī)器8

小時和C

機(jī)器7

小時，問該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺，才能使總利潤最大？上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)x1臺甲機(jī)床和x2乙機(jī)床時總利潤z

最大，則x1

,x2應(yīng)滿足（1.1）s.t.1

2max

z

=

4x1

+

3x2

，ì?

2

x1

+

x2

?

10,?1

2x

+

x

?

8,??

x

,

x

3

0.?í?

x2

￡

7,??(1.2）變量x1

,x2稱之為決策變量，（1.1）式被稱為問題的目標(biāo)函數(shù)，（1.2）中的幾個不等式是問題的約束條件，記為

s.t.(即subjectto)。目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題。線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。在解決實(shí)際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步，往往也是很的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選適當(dāng)?shù)臎Q策變量，是建立有效模型的關(guān)鍵之一。1.1.2

線性規(guī)劃問題的解的概念為一般線性規(guī)劃問題的（數(shù)學(xué)）nmax

z

=

?

c

j

xj

，j=

1(1.3）s.t.j=

1i

=

1,

2,L

,

m,naij

xj

=

bijì??í??

????

x

?

0

j

1,

2,L

,

n.（1.4）其中bi

30，i

=1,2,L,m。T1

n可行解

滿足約束條件（1.4）的解x

=

[

x

,L

,

x ]稱為線性規(guī)劃問題的可行解，而使目標(biāo)函數(shù)（1.3）達(dá)到最大值的可行解叫最優(yōu)解?？尚杏?/p>

所有可行解構(gòu)成的集合稱為問題的可行域，記為R。1.1.3

線性規(guī)劃的

標(biāo)準(zhǔn)形式及

求解線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，性規(guī)劃的標(biāo)準(zhǔn)形式為min

f

T

x

，中規(guī)定線ì?

A祝x

b,??s.t.

?í

Aeq

?x

beq,ub.??

lb

＃x??中c,x,b,beq,lb,ub為列向量，c稱為價(jià)值向量，b稱為資源向量，A,Aeq為矩陣。中求解線性規(guī)劃 令為[x,fval]

=

linprog(f,A,b)[x,fval]

=

linprog(f,A,b,Aeq,beq)[x,fval]

=

linprog(f,A,b,Aeq,beq,lb,ub)其中x

返回的是決策向量的取值，fval

返回的是目標(biāo)函數(shù)的最優(yōu)值，f

為價(jià)值向量，A，b

對應(yīng)的是線性不等式約束，Aeq，beq對應(yīng)的是線性等式約束，lb和ub分別對應(yīng)的是決策向量的下界向量和上界向量。例1.2求解下列線性規(guī)劃問題max

z

=

2x1

+

3x2

-

5x3

，s.t.x1

+

x2

+

x3

=

7，2x1

-

5x2

+

x3

?

10，x1

+

3x2

+

x3

?

12，x1

,

x2

,

x3

3

0.解

（1）化成min

w

=

-

2x1

-

3x2

+

5x3

，輊xs.t.輊-

2

5

-

1

犏1

輊-

103

1犏x￡

犏犏2犏犏臌1犏x臌3，1

2

3[1,

1,

1]?[

x

,

x

,

x

]T犏臌127.（2）求解的 程序如下f=[-2;

-3;

5];a=[-2,5,-1;1,3,1];

b=[-10;12];aeq=[1,1,1];beq=7;[x,y]=linprog(f,a,b,aeq,beq,zeros(3,1));x,

y=-y（3）求解的Lingo程序如下model:sets:row/1..2/:b;col/1..3/:c,x;links(row,col):a;endsetsdata:c=23

-5;a=-2

5

-11

3

1;b=-10

12;enddatamax=@sum(col:c*x);@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));@sum(col:x)=7;end例1.2求解下列線性規(guī)劃問題max

z

=

2x1

+

3x2

-

5x3

，s.t.x1

+

x2

+

x3

=

7，2x1

-

5x2

+

x3

?

10，x1

+

3x2

+

x3

?

12，x1

,

x2

,

x3

3

0.求得的最優(yōu)解為x1

=6.4286,x2

=0.5714，x3

=0，對應(yīng)的最優(yōu)值z

=14.5714。例1.3

求解線性規(guī)劃問題min

z

=

2x1

+

3x2

+

x3

，ì?

x1

+

4

x2

+

2

x3

?

8,s.t.3

x1

+

2

x2

?

6,1

2

3?

x

,

x

,

x

3

0.??í??解 編寫

程序如下c=[2;3;1];a=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))束，對應(yīng)的矩陣為空矩陣%這里沒有等式約求得的最優(yōu)解為x1

=0.8066,x2

=1.7900，x3

=0.0166對應(yīng)的最優(yōu)值z

=7.0000。1.1.4

可以轉(zhuǎn)化為線性規(guī)劃的問題例1.4

數(shù)學(xué)規(guī)劃問題min |

x1

|

+

|

x2

|

+

L

+

|

xn

|,s.

t.

Ax

￡

b.T1

n其中x

=

[

x

,L

,

x ]

，

A和b為相應(yīng)維數(shù)的矩陣和向量。對任意的xi

，存在ui

,

vi

3

0滿足xi

=

ui

-

vi

，|

xi

|=

ui

+

vi

，2i

ii事實(shí)上，只要取u

=2i

iix

+

|

x

| |x

|

-

x，v

=就可以滿足上面的條件。T1

n記u

=

[u

,L

,

u

]

，T1

nv

=[v

,L,v

]

，從而可以把上面的問題變成mini=1(ui

+

vi

)，n?ì?

A(u

-

v)

?

b,í??

u,

v

3

0.s.

t.min這里u

3

0表示向量u的每個分量大于等于

0。進(jìn)一步把模型改寫成n?i=

1(ui

+

vi

)，輊uì??

[

A,-

A]犏?

b,?í犏臌v????

u,

v

3

0.s.

t.例1.5（續(xù)例1.4類型的實(shí)例）

求解下列數(shù)學(xué)規(guī)劃問題s.t.1

2

3

41

2

3

4min

z

=

|

x1

|

+

2

|

x2

|

+

3

|

x3

|

+

4

|

x4

|，ì??

x

-

x

-

x

+

x

?

2,1,12.??í

x1

-

x2

+

x3

-

3

x4

???

x

-

x

-

2

x

+

3

x

???xi

+

|

xi

|i解 做

變量變換

u

=2

2i，

v

=

，i

=1,2,3,4

，并把新變量重新排序成一維向量1

4

1

4T=[u

,L,u

,v

,L,v

]

，則可把模型變換為線性規(guī)劃輊uy

=犏犏臌v模型min

cT

y

，輊uì??

[

A,-

A]犏?

b,犏臌v?í

???

y

3

0.s.

t.2其中c

=

[1,

2,

3,

4,1,

2,

3,

4]T

，b

=

[-

2,-

1,-

1]T

，輊1-

1-

11-

11--

1-

233

。犏A

=

犏1犏犏1臌計(jì)算的 程序如下clc,

clearc=1:4;

c=[c,c]';%構(gòu)造價(jià)值列向量

a=[1-1-1

1;

1-1

1-3;

1-1-23];a=[a,-a];%構(gòu)造變換后新的系數(shù)矩陣

b=[-2-1-1/2]';[y,z]=linprog(c,a,b,[],[],zeros(8,1))

%這里沒有等式約束，對應(yīng)的矩陣為空矩陣x=y(1:4)-y(5:end)

%變換到原問題的解，x=u-v求得最優(yōu)解x1

=

-

2，

x2

=

x3

=

x4

=

0，最優(yōu)值z

=

2。Lingo程序如下

model:sets:col/1..4/:c,x;row/1..3/:b;links(row,col):a;endsetsdata:c=12

34;b=-2-1

-0.5;a=1-1-1

1 1-1

1

-3 1

-1

-2

3;enddatamin=@sum(col:c*@abs(x));@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));@for(col:@free(x)); !x的分量可正可負(fù);endyi例

1.6

min{max

|

ei

|}，其中ei

=

xi

-

yi

。xi

yi取v

=

max

|

ei

|，這樣，上面的問題就變換成min

v

，s.t.1x

-

y1

?

v,L

,

xnyn

?

v,xn

?

v.ì?í??

y1

-

x1

?

v,L

,

yn1.2

投資的收益和風(fēng)險(xiǎn)1.2.1

問題提出市場上有n種資產(chǎn)si（i

=

1,

2,L

,

n）可以選擇，現(xiàn)用數(shù)為M

的相當(dāng)大的 作一個時期的投資。這n種資產(chǎn)在這一時期內(nèi) si

的平均收益率為ri

，風(fēng)險(xiǎn)損失率為qi

，投分散，總的風(fēng)險(xiǎn)越少，總體風(fēng)險(xiǎn)可用投資的si

中最大的一個風(fēng)險(xiǎn)來度量。si時要付交易費(fèi)，費(fèi)率為pi

，當(dāng)

額不超過給定值ui

時，交易費(fèi)按ui

計(jì)算。另外，假定同期銀行存款利率是r0

，既無交易費(fèi)又無風(fēng)險(xiǎn)（r0

=5%）。已知n

=4時相關(guān)數(shù)據(jù)如表1.1。表1.1投資的相關(guān)數(shù)據(jù)siri

(%)qi

(%)pi

(%)ui

(元)ui282.51103s2211.52198s3235.54.552s4252.66.540試給該公司設(shè)計(jì)一種投資組合方案，即用給定M

，有選擇地 若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，使總體風(fēng)險(xiǎn)盡可能小。1.2.2

符號規(guī)定和基本假設(shè)，債券等，i

=0,1,L,n符號規(guī)定si

表示第i

種投資項(xiàng)目，如中s0

指存入銀行；ri

,pi,qi

分別表示si的平均收益率，交易費(fèi)率，風(fēng)險(xiǎn)損率，其中p0

=0，q0

=0；，i

=

0,1,L

,

n；ui

表示si

的交易

；xi

表示投資項(xiàng)目si

的a

表示投資風(fēng)險(xiǎn)度；Q

表示總體收益；基本假設(shè)（1）投資數(shù)額M

相當(dāng)大，為了便于計(jì)算，假設(shè)M

=1投 分散，總的風(fēng)險(xiǎn)越??；總體風(fēng)險(xiǎn)用投資項(xiàng)目si

中最大的一個風(fēng)險(xiǎn)來度量；（4）n

+1種資產(chǎn)si

之間是相互獨(dú)立的；在投資的這一時期內(nèi)，ri,pi,qi為定值，不受意外因素影響；凈收益和總體風(fēng)險(xiǎn)只受ri

,pi,qi影響，不受其它因素干擾。1.2.3

模型的分析與建立總體風(fēng)險(xiǎn)用所投資的si

中最大的一個風(fēng)險(xiǎn)來衡量，即max{qi

xi

|

i

=

1,

2,L

,

n}.si

所付交易費(fèi)是一個分段函數(shù)，即交易費(fèi)=i

iì?íp

x

,

xi

>

ui

,xi

￡

ui

.???

piui

,而題目所給的定值ui（單位：元）相對總投資M

很少，pi

ui更小，這樣

si

的凈收益可以簡化為(ri

-

pi

)xi

。3．要使凈收益盡可能大，總體風(fēng)險(xiǎn)盡可能小，這是一個多目標(biāo)規(guī)劃模型。目標(biāo)函數(shù)為i=

0ni

i?

minmax{q

x

}.ì??í?

max

?

(ri

-

pi

)

xi

,??約束條件為(1

+

pi

)xi

=

M

,0,1,L

,

n.ni=

0i??

x

?

0,

iì??í?

???4.

模型簡化ⅰ)

在實(shí)際投資中，投資者承受風(fēng)險(xiǎn)的程度不一樣，若給定風(fēng)險(xiǎn)一個界限a

，使最大的一個風(fēng)險(xiǎn)qi

xi

￡

a

，可找到相M應(yīng)的投資方案。這樣把多目標(biāo)規(guī)劃變成一個目標(biāo)的線性規(guī)劃模型一 固定風(fēng)險(xiǎn)水平，優(yōu)化收益nmax

?

(ri

-

pi

)

xi

，i=

0i=

0(1

+

pi

)

xi

=

M

,i

0,1,L

,

n.ì?

qi

xi?

M

￡

a,ns.t.

?ix

?

0,í????

?ⅱ)

若投資者希望總

至少達(dá)到水平k

以上，在風(fēng)險(xiǎn)最小的情況下尋求相應(yīng)的投資組合。模型二 固定 水平，極小化風(fēng)險(xiǎn)(1

+

pi

)

xi

=

M

,i

0,1,L

,

n.nni=

0i=

0ix

?

0,ì?min{max{qi

xi

}}，(ri

-

pi

)

xi

?

k,??s.t.í????

??

?ⅲ)投資者在權(quán)衡資產(chǎn)風(fēng)險(xiǎn)和預(yù)期收益兩方面時，希望選擇一個令自己滿意的投資組合。因此對風(fēng)險(xiǎn)、收益分別賦予權(quán)重s（0

<s

?1）和(1-s)，s

稱為投資偏好系數(shù)。模型三i=

0(ri

-

pi

)

xi

，nmin

s{max{qi

xi

}}-

(1-

s)?ns.t.

?

(1

+

pi

)

xi

=

M

,

xi

?

0,i=

0i

0,1,

2,L

,

n.1.2.4

模型一的求解模型一為min

f

=

[-

0.05,-

0.27,-

0.19,-

0.185,-

0.185]?[

x

,

x

,

x

,

x

,

x

]Ts.t.24?

0.015

x

￡

a,i?

0.026

x

￡

a,?0

1

2

3

4ì?

x0

+

1.01x1

+

1.02

x2

+

1.045

x3

+

1.065

x4

=

1,?

0.025

x1

￡

a,?í??

0.