線性規(guī)劃的基本定理

3.線性規(guī)劃的基本定理1標(biāo)準(zhǔn)形式及圖解法1.1標(biāo)準(zhǔn)形式矩陣表示3.線性規(guī)劃的基本性質(zhì)其中A是mn矩陣，c是n維行向量，b是m維列向量。評(píng)注：為計(jì)算需要，一般假設(shè)b0.否則，可在方程兩端乘以(-1)即可化為非負(fù)。3.線性規(guī)劃的基本性質(zhì)任意非標(biāo)準(zhǔn)形式均可劃為標(biāo)準(zhǔn)形式，如引入松弛變量xn+1，

xn+2,…xn+m.則有3.線性規(guī)劃的基本性質(zhì)若某變量xj無(wú)非負(fù)限制，則引入xj

=

xj

'

-

xj

''，

xj

',

xj

''0若有上下界限制，比如xj

lj,令xj

'=xj

-lj,,

有xj

'

03.線性規(guī)劃的基本性質(zhì)1.2.圖解法當(dāng)自變量個(gè)數(shù)少于3時(shí)，我們可以用較簡(jiǎn)便的方法求解。3.線性規(guī)劃的基本性質(zhì)Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.例如，考慮食譜問(wèn)題3.線性規(guī)劃的基本性質(zhì)30104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行區(qū)域的極點(diǎn)：(0,25)(15,2.5)最優(yōu)解(20,0)2基本性質(zhì)2.1線性規(guī)劃的可行域3.線性規(guī)劃的基本性質(zhì)定理

3.1

線性規(guī)劃的可行域是凸集.

2.2最優(yōu)極點(diǎn)觀察上例，最優(yōu)解在極點(diǎn)(15,2.5)達(dá)到，我們現(xiàn)在來(lái)證明這一事實(shí):線性規(guī)劃若存在最優(yōu)解,則最優(yōu)解一定可在某極點(diǎn)上達(dá)到.考察線性規(guī)劃的標(biāo)準(zhǔn)形式(3.2)3.線性規(guī)劃的基本性質(zhì)根據(jù)表示定理，任意可行點(diǎn)x可表示為把x的表達(dá)式代入(3.2),得等價(jià)的線性規(guī)劃:3.線性規(guī)劃的基本性質(zhì)于是,問(wèn)題簡(jiǎn)化成3.線性規(guī)劃的基本性質(zhì)在(3.6)中令3.線性規(guī)劃的基本性質(zhì)顯然,當(dāng)時(shí)目標(biāo)函數(shù)取極小值.3.線性規(guī)劃的基本性質(zhì)(p)x因此極點(diǎn)是問(wèn)題(3.2)的最優(yōu)解.即(3.5)和(3.8)是(3.4)的最優(yōu)解,此時(shí)2,若(3.2)存在有限最優(yōu)解,則目標(biāo)數(shù)的最優(yōu)值可在某極點(diǎn)達(dá)到.3.線性規(guī)劃的基本性質(zhì)定理3.2設(shè)線性規(guī)劃(3.2)的可行域非空,則1,(3.2)存在最優(yōu)解的充要條件是所有(j)cd非負(fù),其中是可行域的極方向d(j)3最優(yōu)基本可行解3.線性規(guī)劃的基本性質(zhì)前面討論知道們最優(yōu)解可在極點(diǎn)達(dá)到，而極點(diǎn)是一幾何概念，下面從代數(shù)的角度來(lái)考慮。不失一般性,設(shè)rank(A)=m,A=[B,N],B是m階可逆的.3.線性規(guī)劃的基本性質(zhì)于是,Ax=b可寫為于是特別的令Nx=0,則稱為方程組Ax=b的一個(gè)基本解.3.線性規(guī)劃的基本性質(zhì)定義3.1B稱為基矩陣,的各分量稱為基變量.xB基變量的全體稱為一組基.的各分量稱為基變量.xN為約束條件Ax=b,x0的一個(gè)基本可行解.B稱為可行基矩陣3.線性規(guī)劃的基本性質(zhì)稱為一組可行基.Bb>0,稱基本可行解是非退化的,若-1若Bb0,-1且至少有一個(gè)分量為0,稱基本可行解是退化的.3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)容易知道,基矩陣的個(gè)數(shù)是有限的,因此基本解從而基本可行解的個(gè)數(shù)也是有限的,不超過(guò)3.線性規(guī)劃的基本性質(zhì)定理3.3令K={x|Ax=b,x0},A是m×n矩陣,r(A)=m則K的極點(diǎn)集與Ax=b,x0的基本可行解集合等價(jià).3.線性規(guī)劃的基本性質(zhì)證明:(提綱)1)設(shè)x是K的極點(diǎn),則x是Ax=b,x0的基本可行解.2)設(shè)x是Ax=b,x0的基本可行解,則x是K的極點(diǎn).3.線性規(guī)劃的基本性質(zhì)1),先證極點(diǎn)x的正分量所對(duì)應(yīng)的A的列線性無(wú)關(guān).3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)2)設(shè)x是Ax=b,x0的基本可行解,記即3.線性規(guī)劃的基本性質(zhì)總結(jié),線性規(guī)劃存在最優(yōu)解,目標(biāo)函數(shù)的最優(yōu)值一定能在某極點(diǎn)上達(dá)到.可行域K={x|Ax=b,x0}的極點(diǎn)就是其基本可行解.

從而,求線性規(guī)劃的最優(yōu)解,只需要求出最優(yōu)基本可行解即可.3.線性規(guī)劃的基本性質(zhì)3.4基本可行解的存在問(wèn)題3.線性規(guī)劃的基本性質(zhì)定