【正文】 1 線性規(guī)劃的圖解法與單純形解法 ? 線性規(guī)劃問題的圖解法 ? 線性規(guī)劃單純形解法的原理 ? 線性規(guī)劃單純形解法的計算步驟 ? 單純形法計算的矩陣描述 ? 線性規(guī)劃單純形求解的大 M法 ? 線性規(guī)劃單純形求解的兩階段法 ? 線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象 2 線性規(guī)劃問題的圖解法 ? 圖解法，就是用作圖的方法求解線性規(guī)劃問題。 ? 簡單、直觀的圖解法一般只適用于具有 兩個決策變量 的線性規(guī)劃問題。 ? 用圖解法求解實際線性規(guī)劃問題，一般按照如下基本步驟： Step1 畫直坐標系； Step2 根據(jù)約束條件畫出可行域； Step3 畫過坐標原點的目標函數(shù)線； Step4 確定目標函數(shù)值的增大方向 (目標函數(shù)線法線方向 ) Step5 目標函數(shù)線沿著增大方向平行移動，與可行域相交且有最大目標函數(shù)值的頂點，即為線性規(guī)劃問題的最優(yōu)解 。 3 x1 x2 O 10 20 30 40 10 20 30 40 (15,10) 最優(yōu)解 X=(15,10) 最優(yōu)值 Z=85 402 21 ?? xx 21 ?? xx0,0402212121??????xxxxxx例 21 43m a x xxZ ??4 2 4 6 x1 x2 2 4 6 最優(yōu)解 X=(3,1) 最優(yōu)值 Z=5 (3,1) ???????????????006346321212121xxxxxxxx、min Z=x1+2x2 例 5 2 4 6 x1 x2 2 4 6 X（ 2） ＝（ 3,1） X（ 1） ＝（ 1,3） ???????????????006346321212121xxxxxxxx、min Z=5x1+5x2 例 有無窮多個最優(yōu)解 即具有多重解 ,通解為 0≤α≤1 當 α= Ｘ =(x1,x2)=(1,3)+(3,1)=(2,2) 6 2 4 6 x1 x2 2 4 6 ???????????????006346321212121xxxxxxxx、無界解 (無最優(yōu)解 ) max Z=x1+2x2 例 7 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無可行解 即無最優(yōu)解 max Z=10x1+4x2 例 8 由以上例題可知，線性規(guī)劃的解有 4種形式： (例 ) (例 ) (例 ) (例 ) 2情形為有最優(yōu)解 4情形為無最優(yōu)解 9 由圖解法得到的啟示 ? 線性規(guī)劃問題求解的基本依據(jù)是：線性規(guī)劃問題的最優(yōu)解總可在可行域的頂點中尋找。尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個頂點處的目標函數(shù)值。 ? 線性規(guī)劃問題求解時可能出現(xiàn)四種結(jié)局： 唯一最優(yōu)解 、無窮多個最優(yōu)解 、 有無界解 、 無解或無可行解 。 ? 如果某一線性規(guī)劃問題有最優(yōu)解，我們可以按照這樣的思路來求解：先找可行域中的一個頂點，計算頂點處的目標函數(shù)值，然后判別是否有其它頂點處的目標函數(shù)值比這個頂點處的目標函數(shù)值更大，如有，轉(zhuǎn)到新的頂點，重復(fù)上述過程，直到找不到使目標函數(shù)值更大的新頂點為止。 10 (1)可行解區(qū)域要畫正確 (2)目標函數(shù)增加的方向不能畫錯 (3)目標函數(shù)的直線怎樣平行移動 11 線性規(guī)劃單純形解法的原理 ? 單純形方法的基本思想 從可行域中的一個基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如不是，尋找下一個基可行解，并且同時努力使目標函數(shù)得到改進，如此迭代下去，直到找到最優(yōu)解或判定問題無解為止。 ? 單純形算法必須解決三個方面的問題： 1. 如何確定初始的基可行解？ 2. 如何進行解的最優(yōu)性判別？ 3. 如何尋找改進的基可行解？ 12 確定初始的基可行解 ? 標準型的線性規(guī)劃問題 ??????????0m a x1XbxPCXznjjj???????????????100000100001),( 21????? mPPP系數(shù)矩陣中存在一個單位陣 以單位陣為一初始可行基。令非基變量取值為零，便得到一基可行解。 13 【 例 】 用單純形法求下列線性規(guī)劃的最優(yōu)解 ????????????0,30340243max21212121xxxxxxxxZ14 【 解 】 化為標準型 ， 加入松馳變量 x x4則標準型為 系數(shù)矩陣 A及可行基 B1 r(B1)=2， B1是一個初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T ??????????????0,30340243m a x432142132121xxxxxxxxxxxxZ???????10310112A???????10011B15 以上得到的一組基可行解是不是最優(yōu)解，可以從目標函數(shù)中的系數(shù)看出。目標函數(shù) Z=3x1+4x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標函數(shù)中非基變量的系數(shù)大于零，那么目標函數(shù)就沒有達到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作 σ j , j=1,2…, n。 本例中 σ 1=3, σ 2=4, σ 3=0, σ 4=0。 最優(yōu)解判斷標準 當所有檢驗數(shù) σ j≤0（ j=1， … ， n）時，基本可行解為最優(yōu)解。 當目標函數(shù)中有基變量 xi時，利用約束條件將目標函數(shù)中的 xi消去即可求出檢驗數(shù)。 檢驗數(shù) 目標函數(shù)用非基變量表達時的變量系數(shù) 16 進基列 出基行 bi /ai2， ai20 θi 表 14 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 σ j 3 4 0 0 (2) x3 x2 σ j (3) x1 x2 σ j 基變量 1 10 0 0 1/3 0 1/3 10 5/3 1 1/3 40 5/3 0 4/3 30 1 0 3/5 1/5 18 0 1 1/5 2/5 4 0 0 1 1 將 3化為 1 乘以1/3后得到 30 18 17 最優(yōu)解 X=(18， 4， 0， 0)T，最優(yōu)值 Z=70 O 20 30 10 40 (3,4) X(3)=(18,4) 最優(yōu)解 X=(18,4) 最優(yōu)值 Z=70 402 21 ?? xx 21 ?? xx??????????????0,30340243m a x432142132121xxxxxxxxxxxxZX(1)=(0,0) 20 10 x2 x1 30 0,0402212121??????xxxxxxX(2)=(0,10) 18 單純形表 c j c 1 c 2 … c m c m +1 … c m + k … c n c B X B x 1 x 2 … x m x m +1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ?