運籌與優(yōu)化-第3章線性性質

矩陣表示：min

cxs.t Ax

=

bx≥

0矩陣

A:

m×n列向量

x:

n

×1b:

m

×1

且假定b

≥0行向量

c: 1×n（3.1.2）化為標準形式：變量沒有非負限制：如xj無非負限制時，可令xj

=xj

'－xj

",xj

'≥0,xj

"≥0變量有上下界：如xj≥l時，可令xj

'=xj

－l,則xj

'≥0如xj

≤u時，可令xj

'=u－xj,則xj

'≥0bi

≤

0：maxz：令z'=-z,則min

z'=-c

x引入松弛變量將不等式化為等式：如a11x1

a12

x2

a1n

xn

b1引入松弛變量xn+1

≥0，目標函數(shù)不變a11x1

b

a1n

xn

xn11引入松弛變量xn+2

≥0

，目標函數(shù)不變

a2n

xna21

x1

b2

xn

2如a

x

21

1

a22

x2

a2n

xn

b2min

c1x1

c2

x2

cnxn

s.t.a11x1

a12

x2

a1n

xn1xnam1x1

am

2

x2

b1

amn,

n

x

j

0,

j

1,2x,n

xnm

bm松弛變量min

c1x1

c2

x2

cn

a1n

xn

b1xn

s.t.a11x1

a12

x2am1x1

am

2

x2x1,

x2

,

,

xn

0

amn

xn

bm目標函數(shù)不變二、圖解法目標函數(shù)等值線-x1

-3

x2

=α極小點目標函數(shù)的負梯度x1x2α*§3.2

基本性質一、線性規(guī)劃的可行域定理3.2.1

線性規(guī)劃的可行域是凸集約束條件均為線性等式及不等式二、最優(yōu)極點設可行域的極點為x(1)，x(2),…x(k)，極方向為d(1),d(2),…d(l)。根據定理2.1.1，任何可行點x可以表示為(

j

)j

1,

,k

j

k

l(

j

)jjk

j

1j1j

0j

0x

dj1

x

j1得到以λj，μj為變量的等價的線性規(guī)劃s.t.kljmin

(cx(

j

)

)j1

(cd

(

j

)

)j1jkj

0j

0

j

1j1j

1,

,k

j

如某個cd(j)＜0,∵

μj可→1+,∞，,

∴l(xiāng)

目標函數(shù)→-∞問題

，不存在有限最優(yōu)值如所有cd(j)≥0，為極小化目標函數(shù)，令μj=0。k令cx(

p

)

mkin

cx(

j

)1

jkj

0j

1,

,jmin

(cx(

j

)

)j1ks.t.

j

1j1j1klcx

(cx(

j

)

)

j

(cd

(

j

)

)

jj1

j1k

(cx(

j

)

)

jk(

p

)(

p

)j(cx

)

cx極點x(p)是最優(yōu)解j1λp=1，λj

=0，j≠p定理3.2.2設線性規(guī)劃(3.1.2)的可行域非空，則有下列結論：1。(3.1.2)存在有限最優(yōu)解的充要條件是所有的cd(j)為非負數(shù)。其中d(j)是可行域的極方向。2。若(3.1.2)存在有限最優(yōu)解，則目標函數(shù)的最優(yōu)值可在某個極點上達到。而把問題歸入不存在最優(yōu)解的情形三、最優(yōu)基本可行解基本可行解--極點的代數(shù)含意假設A＝[B，N]，設矩陣A的秩為m,

B是m階可逆矩陣。

x＝[xB，xN]T未知量，它們取不同的值就會得到方程組的不同的解特別地，令xN＝0，則得到解定義3.2.1稱為方程組Ax＝b的一個基本解。B稱為基矩陣，簡稱為基。xB的各分量稱為基變量基變量的全體xB1，xB2，…,xBm稱為一組基xN的各分量稱為非基變量。又若B-1b≥0，則稱該解為約束條件Ax＝b，x≥0的基本可行解相應地：

稱B為可行基矩陣xB1，xB2，…,xBm為一組可行基

若B-1b＞0，即基變量的取值均為正數(shù)，則稱基本可行解是非

的

如果B-1b

≥0且至少有一個分量是零，則稱基本可行解是

的基本可行解例3.2.1

考慮下列不等式定義的多面集：引進松弛變量x3，x4令解得基本解：x(1)

=(4,

2,

0,

0)T

→基本可行解→基本解當A是m×n矩陣，且秩為m時，基本可行解的個數(shù)不