線性規(guī)劃的基本定理_第1頁
線性規(guī)劃的基本定理_第2頁
線性規(guī)劃的基本定理_第3頁
線性規(guī)劃的基本定理_第4頁
線性規(guī)劃的基本定理_第5頁
已閱讀5頁,還剩27頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

3.線性規(guī)劃的基本定理1標準形式及圖解法1.1標準形式矩陣表示3.線性規(guī)劃的基本性質(zhì)其中A是mn矩陣,c是n維行向量,b是m維列向量。評注:為計算需要,一般假設(shè)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

'

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

50

x,y

0.例如,考慮食譜問題3.線性規(guī)劃的基本性質(zhì)30104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行區(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可表示為把x的表達式代入(3.2),得等價的線性規(guī)劃:3.線性規(guī)劃的基本性質(zhì)于是,問題簡化成3.線性規(guī)劃的基本性質(zhì)在(3.6)中令3.線性規(guī)劃的基本性質(zhì)顯然,當時目標函數(shù)取極小值.3.線性規(guī)劃的基本性質(zhì)(p)x因此極點是問題(3.2)的最優(yōu)解.即(3.5)和(3.8)是(3.4)的最優(yōu)解,此時2,若(3.2)存在有限最優(yōu)解,則目標數(shù)的最優(yōu)值可在某極點達到.3.線性規(guī)劃的基本性質(zhì)定理3.2設(shè)線性規(guī)劃(3.2)的可行域非空,則1,(3.2)存在最優(yōu)解的充要條件是所有(j)cd非負,其中是可行域的極方向d(j)3最優(yōu)基本可行解3.線性規(guī)劃的基本性質(zhì)前面討論知道們最優(yōu)解可在極點達到,而極點是一幾何概念,下面從代數(shù)的角度來考慮。不失一般性,設(shè)rank(A)=m,A=[B,N],B是m階可逆的.3.線性規(guī)劃的基本性質(zhì)于是,Ax=b可寫為于是特別的令Nx=0,則稱為方程組Ax=b的一個基本解.3.線性規(guī)劃的基本性質(zhì)定義3.1B稱為基矩陣,的各分量稱為基變量.xB基變量的全體稱為一組基.的各分量稱為基變量.xN為約束條件Ax=b,x0的一個基本可行解.B稱為可行基矩陣3.線性規(guī)劃的基本性質(zhì)稱為一組可行基.Bb>0,稱基本可行解是非退化的,若-1若Bb0,-1且至少有一個分量為0,稱基本可行解是退化的.3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)容易知道,基矩陣的個數(shù)是有限的,因此基本解從而基本可行解的個數(shù)也是有限的,不超過3.線性規(guī)劃的基本性質(zhì)定理3.3令K={x|Ax=b,x0},A是m×n矩陣,r(A)=m則K的極點集與Ax=b,x0的基本可行解集合等價.3.線性規(guī)劃的基本性質(zhì)證明:(提綱)1)設(shè)x是K的極點,則x是Ax=b,x0的基本可行解.2)設(shè)x是Ax=b,x0的基本可行解,則x是K的極點.3.線性規(guī)劃的基本性質(zhì)1),先證極點x的正分量所對應(yīng)的A的列線性無關(guān).3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)3.線性規(guī)劃的基本性質(zhì)2)設(shè)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ì)定

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論