1、3.線性規(guī)劃的基本定理,1標準形式及圖解法 1.1標準形式,矩陣表示,3.線性規(guī)劃的基本性質(zhì),其中A是mn矩陣，c是n維行向量， b是m維列向量。,評注：為計算需要，一般假設b0.否則，可在方程兩端乘以(-1)即可化為非負。,3.線性規(guī)劃的基本性質(zhì),任意非標準形式均可劃為標準形式，如,引入松弛變量xn+1， xn+2 , xn+m.,則有,3.線性規(guī)劃的基本性質(zhì),若某變量xj無非負限制，則引入xj = xj - xj ， xj , xj 0 若有上下界限制，比如xj lj, 令xj = xj - lj, , 有 xj 0,3.線性規(guī)劃的基本性質(zhì),1.2. 圖解法 當自變量個數(shù)少于3時，我們可以

2、用較簡便的 方法求解。,3.線性規(guī)劃的基本性質(zhì),Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.,例如，考慮食譜問題,3.線性規(guī)劃的基本性質(zhì),可行區(qū)域的極點： (0, 25) (15, 2.5) 最優(yōu)解 (20, 0),2 基本性質(zhì) 2.1 線性規(guī)劃的可行域,3.線性規(guī)劃的基本性質(zhì),定理 3.1 線性規(guī)劃的可行域是凸集.,2.2 最優(yōu)極點,觀察上例，最優(yōu)解在極點(15,2.5)達到，我們 現(xiàn)在來證明這一事實:線性規(guī)劃若存在最優(yōu)解, 則最優(yōu)解一定可在某極點上達到.,考察線性規(guī)劃的標準形式(3. 2),3.線性規(guī)劃的基本性質(zhì),根據(jù)表示定理，任意可行點x

3、可表示為,把x的表達式代入(3. 2),得等價的線性規(guī)劃:,3.線性規(guī)劃的基本性質(zhì),于是,問題簡化成,3.線性規(guī)劃的基本性質(zhì),在(3.6)中令,3.線性規(guī)劃的基本性質(zhì),顯然,當,時目標函數(shù)取極小值.,3.線性規(guī)劃的基本性質(zhì),即(3.5)和(3.8)是(3.4)的最優(yōu)解,此時,2,若(3. 2)存在有限最優(yōu)解,則目標數(shù)的最優(yōu)值 可在某極點達到.,3.線性規(guī)劃的基本性質(zhì),定理3.2 設線性規(guī)劃(3.2)的可行域非空,則,3最優(yōu)基本可行解,3.線性規(guī)劃的基本性質(zhì),前面討論知道們最優(yōu)解可在極點達到，而極點 是一幾何概念，下面從代數(shù)的角度來考慮。,不失一般性,設rank(A)=m,A=B,N,B是m階可

4、逆的.,3.線性規(guī)劃的基本性質(zhì),于是,Ax=b可寫為,于是,稱為方程組Ax=b的一個基本解.,3.線性規(guī)劃的基本性質(zhì),定義3.1,為約束條件Ax=b,x0的一個基本可行解. B稱為 可行基矩陣,3.線性規(guī)劃的基本性質(zhì),稱為一組可行基.,且至少有一個分量為0,稱基本可行解是退化的.,3.線性規(guī)劃的基本性質(zhì),3.線性規(guī)劃的基本性質(zhì),3.線性規(guī)劃的基本性質(zhì),容易知道,基矩陣的個數(shù)是有限的,因此基本解從而基本可行解的個數(shù)也是有限的, 不超過,3.線性規(guī)劃的基本性質(zhì),定理3. 3 令K=x| Ax=b,x0,A是mn矩陣,r(A)=m 則K的極點集與Ax=b,x0的基本可行解集合等價.,3.線性規(guī)劃的基

5、本性質(zhì),證明: (提綱) 1)設x是K的極點,則x是Ax=b,x0的基本可行解. 2)設x是Ax=b,x0的基本可行解,則x是K的極點.,3.線性規(guī)劃的基本性質(zhì),1),先證極點x的正分量所對應的A的列線性無關.,3.線性規(guī)劃的基本性質(zhì),3.線性規(guī)劃的基本性質(zhì),3.線性規(guī)劃的基本性質(zhì),2)設x是Ax=b,x0的基本可行解,記,即,3.線性規(guī)劃的基本性質(zhì),總結(jié),線性規(guī)劃存在最優(yōu)解,目標函數(shù)的最優(yōu)值 一定能在某極點上達到.可行域K=x| Ax=b,x0的極點就是其基本可行解. 從而,求線性規(guī)劃的最優(yōu)解,只需要求出最優(yōu)基本 可行解即可.,3.線性規(guī)劃的基本性質(zhì),3. 4 基本可行解的存在問題,3.線性規(guī)劃的基本性質(zhì),定理3. 4 若Ax=b