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

矩陣表示：min

cxs.t Ax

=

bx≥

0矩陣

A:

m×n列向量

x:

n

×1b:

m

×1

且假定b

≥0行向量

c: 1×n（3.1.2）化為標(biāo)準(zhǔn)形式：變量沒有非負(fù)限制：如xj無非負(fù)限制時(shí)，可令xj

=xj

'－xj

",xj

'≥0,xj

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

'=xj

－l,則xj

'≥0如xj

≤u時(shí)，可令xj

'=u－xj,則xj

'≥0bi

≤

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

z'=-c

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

a12

x2

a1n

xn

b1引入松弛變量xn+1

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

b

a1n

xn

xn11引入松弛變量xn+2

≥0

，目標(biāo)函數(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目標(biāo)函數(shù)不變二、圖解法目標(biāo)函數(shù)等值線-x1

-3

x2

=α極小點(diǎn)目標(biāo)函數(shù)的負(fù)梯度x1x2α*§3.2

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

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

j

)j

1,

,k

j

k

l(

j

)jjk

j

1j1j

0j

0x

dj1

x

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

(cx(

j

)

)j1

(cd

(

j

)

)j1jkj

0j

0

j

1j1j

1,

,k

j

如某個(gè)cd(j)＜0,∵

μj可→1+,∞，,

∴l(xiāng)

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

，不存在有限最優(yōu)值如所有cd(j)≥0，為極小化目標(biāo)函數(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極點(diǎn)x(p)是最優(yōu)解j1λp=1，λj

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

B是m階可逆矩陣。

x＝[xB，xN]T未知量，它們?nèi)〔煌闹稻蜁?huì)得到方程組的不同的解特別地，令xN＝0，則得到解定義3.2.1稱為方程組Ax＝b的一個(gè)基本解。B稱為基矩陣，簡(jiǎn)稱為基。xB的各分量稱為基變量基變量的全體xB1，xB2，…,xBm稱為一組基xN的各分量稱為非基變量。又若B-1b≥0，則稱該解為約束條件Ax＝b，x≥0的基本可行解相應(yīng)地：

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

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

的

如果B-1b

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

的基本可行解例3.2.1

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

=(4,

2,

0,

0)T

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