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

xn+2,…xn+m.則有3.線性規劃的基本性質若某變量xj無非負限制，則引入xj

=

xj

'

-

xj

''，

xj

',

xj

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

lj,令xj

'=xj

-lj,,

有xj

'

03.線性規劃的基本性質1.2.圖解法當自變量個數少于3時，我們可以用較簡便的方法求解。3.線性規劃的基本性質Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.例如，考慮食譜問題3.線性規劃的基本性質30104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行區域的極點：(0,25)(15,2.5)最優解(20,0)2基本性質2.1線性規劃的可行域3.線性規劃的基本性質定理

3.1

線性規劃的可行域是凸集.

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

從而,求線性規劃的最優解,只需要求出最優基本可行解即可.3.線性規劃的基本性質3.4基本可行解的存在問題3.線性規劃的基本性質定