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

3.線性規(guī)劃的基本定理1標(biāo)準(zhǔn)形式及圖解法1.1標(biāo)準(zhǔn)形式1可編輯課件PPT矩陣表示3.線性規(guī)劃的基本性質(zhì)其中A是m

n矩陣，c是n維行向量，b是m維列向量。評注：為計算需要，一般假設(shè)b

0.否則，可在方程兩端乘以(-1)即可化為非負(fù)。2可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)任意非標(biāo)準(zhǔn)形式均可劃為標(biāo)準(zhǔn)形式，如引入松弛變量xn+1，xn+2,…xn+m.3可編輯課件PPT則有3.線性規(guī)劃的基本性質(zhì)4可編輯課件PPT若某變量xj無非負(fù)限制，則引入xj=

xj'

-

xj''，xj',

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

lj,令xj'=xj-lj,,

有xj'

03.線性規(guī)劃的基本性質(zhì)5可編輯課件PPT1.2.圖解法當(dāng)自變量個數(shù)少于3時，我們可以用較簡便的方法求解。3.線性規(guī)劃的基本性質(zhì)Min3x+2.5ys.t.2x+4y

403x+2y

50

x,y

0.例如，考慮食譜問題6可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)30104020501020304050yx03x+2.5y2x+4y

403x+2y

50(15,2.5)可行區(qū)域的極點：(0,25)(15,2.5)最優(yōu)解(20,0)7可編輯課件PPT2基本性質(zhì)2.1線性規(guī)劃的可行域3.線性規(guī)劃的基本性質(zhì)定理

3.1

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

2.2最優(yōu)極點觀察上例，最優(yōu)解在極點(15,2.5)達(dá)到，我們現(xiàn)在來證明這一事實:線性規(guī)劃若存在最優(yōu)解,則最優(yōu)解一定可在某極點上達(dá)到.8可編輯課件PPT考察線性規(guī)劃的標(biāo)準(zhǔn)形式(3.2)3.線性規(guī)劃的基本性質(zhì)根據(jù)表示定理，任意可行點x可表示為9可編輯課件PPT把x的表達(dá)式代入(3.2),得等價的線性規(guī)劃:3.線性規(guī)劃的基本性質(zhì)10可編輯課件PPT于是,問題簡化成3.線性規(guī)劃的基本性質(zhì)11可編輯課件PPT在(3.6)中令3.線性規(guī)劃的基本性質(zhì)顯然,當(dāng)時目標(biāo)函數(shù)取極小值.12可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)(p)x因此極點是問題(3.2)的最優(yōu)解.即(3.5)和(3.8)是(3.4)的最優(yōu)解,此時13可編輯課件PPT2,若(3.2)存在有限最優(yōu)解,則目標(biāo)數(shù)的最優(yōu)值可在某極點達(dá)到.3.線性規(guī)劃的基本性質(zhì)定理3.2設(shè)線性規(guī)劃(3.2)的可行域非空,則1,(3.2)存在最優(yōu)解的充要條件是所有(j)cd非負(fù),其中是可行域的極方向d(j)14可編輯課件PPT3最優(yōu)基本可行解3.線性規(guī)劃的基本性質(zhì)前面討論知道們最優(yōu)解可在極點達(dá)到，而極點是一幾何概念，下面從代數(shù)的角度來考慮。不失一般性,設(shè)rank(A)=m,A=[B,N],B是m階可逆的.15可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)于是,Ax=b可寫為于是特別的令Nx=0,則16可編輯課件PPT稱為方程組Ax=b的一個基本解.3.線性規(guī)劃的基本性質(zhì)定義3.1B稱為基矩陣,的各分量稱為基變量.xB基變量的全體稱為一組基.的各分量稱為基變量.xN為約束條件Ax=b,x0的一個基本可行解.B稱為可行基矩陣17可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)稱為一組可行基.Bb>0,稱基本可行解是非退化的,若-1若Bb

0,-1且至少有一個分量為0,稱基本可行解是退化的.18可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)19可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)20可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)21可編輯課件PPT容易知道,基矩陣的個數(shù)是有限的,因此基本解從而基本可行解的個數(shù)也是有限的,不超過3.線性規(guī)劃的基本性質(zhì)22可編輯課件PPT定理3.3令K={x|Ax=b,x

0},A是m×n矩陣,r(A)=m則K的極點集與Ax=b,x

0的基本可行解集合等價.3.線性規(guī)劃的基本性質(zhì)證明:(提綱)1)設(shè)x是K的極點,則x是Ax=b,x

0的基本可行解.2)設(shè)x是Ax=b,x

0的基本可行解,則x是K的極點.23可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)1),先證極點x的正分量所對應(yīng)的A的列線性無關(guān).24可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)25可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)26可編輯課件PPT3.線性規(guī)劃的基本性質(zhì)2)設(shè)x是Ax=b,x

0的基本可行解,記27可編輯課件PPT即3.線性規(guī)劃的基本性質(zhì)28可編輯課件PPT總結(jié),線性規(guī)劃存在最優(yōu)解,目標(biāo)函數(shù)的最優(yōu)值一定能在某極點上達(dá)到.可行域K={x|Ax=b,x

0}的極點就是其基本可行解.從而,求線性規(guī)劃的最優(yōu)解,只需要求出最優(yōu)基本可行解即可.3.線性規(guī)劃的基本性質(zhì)29可編輯課件PPT3.4基本可行解的存在問題3.線性規(guī)劃的基本性質(zhì)定理3.4若Ax=b,x

0有可行解,則一定存在基本可行解,其中A是秩為m的m

n矩陣.30可編輯課