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

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

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

1947年G.B.Dantzig

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

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

線性規(guī)劃問(wèn)題1.1.1

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

1.1

某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺(tái)銷(xiāo)售后的利潤(rùn)分別為4

千元與3

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

小時(shí)和1

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

A、B、C

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

小時(shí)、B機(jī)器8

小時(shí)和C

機(jī)器7

小時(shí)，問(wèn)該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺(tái)，才能使總利潤(rùn)最大？上述問(wèn)題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)x1臺(tái)甲機(jī)床和x2乙機(jī)床時(shí)總利潤(rùn)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稱(chēng)之為決策變量，（1.1）式被稱(chēng)為問(wèn)題的目標(biāo)函數(shù)，（1.2）中的幾個(gè)不等式是問(wèn)題的約束條件，記為

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

線性規(guī)劃問(wèn)題的解的概念為一般線性規(guī)劃問(wèn)題的（數(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 ]稱(chēng)為線性規(guī)劃問(wèn)題的可行解，而使目標(biāo)函數(shù)（1.3）達(dá)到最大值的可行解叫最優(yōu)解?？尚杏?/p>

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

線性規(guī)劃的

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

求解線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號(hào)可以是小于號(hào)也可以是大于號(hào)。為了避免這種形式多樣性帶來(lái)的不便，性規(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稱(chēng)為價(jià)值向量，b稱(chēng)為資源向量，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

對(duì)應(yīng)的是線性不等式約束，Aeq，beq對(duì)應(yīng)的是線性等式約束，lb和ub分別對(duì)應(yīng)的是決策向量的下界向量和上界向量。例1.2求解下列線性規(guī)劃問(wèn)題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ī)劃問(wèn)題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，對(duì)應(yīng)的最優(yōu)值z(mì)

=14.5714。例1.3

求解線性規(guī)劃問(wèn)題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.??í??解 編寫(xiě)

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

=0.8066,x2

=1.7900，x3

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

=7.0000。1.1.4

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

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

x1

|

+

|

x2

|

+

L

+

|

xn

|,s.

t.

Ax

￡

b.T1

n其中x

=

[

x

,L

,

x ]

，

A和b為相應(yīng)維數(shù)的矩陣和向量。對(duì)任意的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

]

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

+

vi

)，n?ì?

A(u

-

v)

?

b,í??

u,

v

3

0.s.

t.min這里u

3

0表示向量u的每個(gè)分量大于等于

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

1(ui

+

vi

)，輊uì??

[

A,-

A]犏?

b,?í犏臌v????

u,

v

3

0.s.

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

求解下列數(shù)學(xué)規(guī)劃問(wèn)題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))

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

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

=

-

2，

x2

=

x3

=

x4

=

0，最優(yōu)值z(mì)

=

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

|，這樣，上面的問(wèn)題就變換成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

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

=

1,

2,L

,

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

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

的平均收益率為ri

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

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

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

，當(dāng)

額不超過(guò)給定值ui

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

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

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

=5%）。已知n

=4時(shí)相關(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

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

=0,1,L,n符號(hào)規(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

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

+1種資產(chǎn)si

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

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

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

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

xi

|

i

=

1,

2,L

,

n}.si

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

iì?íp

x

,

xi

>

ui

,xi

￡

ui

.???

piui

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

很少，pi

ui更小，這樣

si

的凈收益可以簡(jiǎn)化為(ri

-

pi

)xi

。3．要使凈收益盡可能大，總體風(fēng)險(xiǎn)盡可能小，這是一個(gè)多目標(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.

模型簡(jiǎn)化ⅰ)

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

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

xi

￡

a

，可找到相M應(yīng)的投資方案。這樣把多目標(biāo)規(guī)劃變成一個(gè)目標(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ù)期收益兩方面時(shí)，希望選擇一個(gè)令自己滿意的投資組合。因此對(duì)風(fēng)險(xiǎn)、收益分別賦予權(quán)重s（0

<s

?1）和(1-s)，s

稱(chēng)為投資偏好系數(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.