[ppt模板]線性規(guī)劃(編輯修改稿)
2025-02-15 09:52 本頁面
【文章內(nèi)容簡介】 x1+x2+x3 ? x3 ? +x4 =7 x1x2+ x3 ? x3 ? x5=2 3x1+x2+2x3 ? 2x3 ? =5 x1, x2 , x3 ?， x3 ?, x4， x5 ? 0 對于標(biāo)準(zhǔn)型 LP問題 max )121( ?? XCzT ???????)141(0)131(..XbAXts 設(shè) A 是 nm ? 階矩陣 , nm ? , 且 A 的秩為 m 。 可行解： 滿足約束條件（ 113）和（ 114）的解稱為可行解。 基： A中任何一組 m個(gè)線性無關(guān)的列向量構(gòu)成的子矩陣 ,稱為該問題的一個(gè)基（ basis） ,與中的這些列向量對應(yīng)的變量稱為基變量（ basic variable） 13 線性規(guī)劃問題解的概念 最優(yōu)解 ： 若基本可行解又是最優(yōu)解（也稱基本最優(yōu)解），這個(gè)基就稱為最優(yōu)基（ optimal basis）。 基本解： 對于基 ,令非基變量為零 ,求得滿足（ 113）的解，稱為基對應(yīng)的基本解 （ basic solution）。 基本可行解： 滿足（ 114）的基本解稱為基本可行解（ basic feasible solution）；基本可行解所對應(yīng)的基稱為可行基 （ feasible basis）。 14 線性規(guī)劃問題的圖解法： 當(dāng)決策變量個(gè)數(shù) n=2時(shí)， LP問題可以通過在平面上作圖的方法求解，稱為圖解法。 圖解法求解的目的： 。 ，把問題的最優(yōu)解找出來。 圖解法的步驟： 。 分別求出滿足每個(gè)約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為 可行域 ； 。 先過原點(diǎn)作一條矢量指向點(diǎn)（ c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形； 。 依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對應(yīng)的坐標(biāo)就是 最優(yōu)解。 一般地，將目標(biāo)函數(shù)直線放在可行域中 求最大值時(shí)直線沿著矢量方向移動(dòng) 求最小值時(shí)沿著矢量的反方向移動(dòng) x1 x2 O 10 20 30 40 10 20 30 40 (3,4) (15,10) 最優(yōu)解 X=(15,10) 最優(yōu)值 Z=85 402 21 ?? xx 21 ?? xx0,0402212121??????xxxxxx例 21 43m a x xxZ ??2 4 6 x1 x2 2 4 6 最優(yōu)解 X=(3,1) 最優(yōu)值 Z=5 (3,1) ???????????????006346321212121xxxxxxxx、min Z=x1+2x2 例 (1,2) 2 4 6 x1 x2 2 4 6 X（ 2） ＝（ 3,1） X（ 1） ＝（ 1,3） (5,5) ???????????????006346321212121xxxxxxxx、min Z=5x1+5x2 例 有無窮多個(gè)最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 當(dāng) α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 2 4 6 x1 x2 2 4 6 (1,2) ???????????????006346321212121xxxxxxxx、無界解 (無最優(yōu)解 ) max Z=x1+2x2 例 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無可行解 即無最優(yōu)解 max Z=10x1+4x2 例 由以上例題可知，線性規(guī)劃的解有 4種形式 ： (例 ) (例 ) (例 ):產(chǎn)生原因：是由于在建立實(shí)際問題的數(shù)學(xué)模型中遺漏了某些必要的資源約束條件。 (例 ):原因是模型本身錯(cuò)誤，約束條件之間互相矛盾，應(yīng)檢查修正。 2情形為有最優(yōu)解 4情形為無最優(yōu)解 圖解法得到的啟示 ，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解。 ，則可行域是一凸集。 ，則最優(yōu)解一定在某個(gè)頂點(diǎn)可達(dá)到。 ：先找出凸集的任一頂點(diǎn)，計(jì)算 Z值，比較相鄰頂點(diǎn) Z值，如大，轉(zhuǎn)到相鄰頂點(diǎn)，一直到找出使 Z值最大的頂點(diǎn)為止。 (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯(cuò) (3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng) 線性規(guī)劃問題解的概念 線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式： Max S = CX （ 19） . AX=b （ 110） X ? 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1