【正文】 n ≥ 0 44 線性規(guī)劃求解的人工變量法 分別對每個約束方程中加入一個人工變量 x n + 1 … , x n + m 得到 m a x z = c 1 x 1 + c 2 x 2 + … + c n x n a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 45 ?為了使加入人工變量后線性規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值不受影響，我們賦予人工變量一個很大的負(fù)價值系數(shù) M (M為任意大的正數(shù) )。 ? 人工變量法的基本思路是： 若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量，則在每個約束方程中加入一個人工變量便可在系數(shù)矩陣中形成一個單位向量。 （ 3 ） 根據(jù)? ? kjjj??? ?? 0|m ax ，所對應(yīng)的非基變量kX 為換入變量，計算kPB1? ，若01 ?? kPB 那問題無解，停止計算，否則進(jìn)行下一步。 j，迭代后為P j ，則有P jBP 39。 多重最優(yōu)解的判斷 :最優(yōu)表中存在非基變量的檢驗數(shù)為零 ,則線則性規(guī)劃具有多重最優(yōu)解。 32 最優(yōu)解的判別定理 ? 定理 1 最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對應(yīng)于基 B 的一個基可行解，對于一切 j = m +1 , … , n , 有檢驗數(shù) ? j≤ 0, 則 X ( 0 ) 為最優(yōu)解。 表 27 21m a x xxZ ???????????????0,42123212121xxxxxx【 例 】 求解線性規(guī)劃 【 解 】 化為標(biāo)準(zhǔn)型 21m a x xxZ ????????????????4,1,042123421321?jxxxxxxxj28 初始單純形表為 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 ?j － 1 1 0 0 λ2=10, x2進(jìn)基 ， 而 a120， a220， 沒有比值 ， 從而線性規(guī)劃的最優(yōu)解無界 。 20 【 例 】 利用單純形列表算法求解例 ????????????0,30340243max21212121xxxxxxxxZ21 【 例 】 用單純形法求解 ????????????02053115232321321321xxxxxxxxx、321 2m ax xxxZ ???22 321 2m a x xxxZ ???【 解 】 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： ?????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計算結(jié)果如表 。 19 單純形算法的計算步驟 ① 將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 本例中 σ 1=3, σ 2=4, σ 3=0, σ 4=0。 ? 單純形算法必須解決三個方面的問題： 1. 如何確定初始的基可行解？ 2. 如何進(jìn)行解的最優(yōu)性判別？ 3. 如何尋找改進(jìn)的基可行解？ 12 確定初始的基可行解 ? 標(biāo)準(zhǔn)型的線性規(guī)劃問題 ??????????0m a x1XbxPCXznjjj???????????????100000100001),( 21????? mPPP系數(shù)矩陣中存在一個單位陣 以單位陣為一初始可行基。尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個頂點處的目標(biāo)函數(shù)值。1 線性規(guī)劃的圖解法與單純形解法 ? 線性規(guī)劃問題的圖解法 ? 線性規(guī)劃單純形解法的原理 ? 線性規(guī)劃單純形解法的計算步驟 ? 單純形法計算的矩陣描述 ? 線性規(guī)劃單純形求解的大 M法 ? 線性規(guī)劃單純形求解的兩階段法 ? 線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象 2 線性規(guī)劃問題的圖解法 ? 圖解法，就是用作圖的方法求解線性規(guī)劃問題。 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 當(dāng) α= Ｘ =(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)解總可在可行域的頂點中尋找。 10 (1)可行解區(qū)域要畫正確 (2)目標(biāo)函數(shù)增加的方向不能畫錯 (3)目標(biāo)函數(shù)的直線怎樣平行移動 11 線性規(guī)劃單純形解法的原理 ? 單純形方法的基本思想 從可行域中的一個基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如不是，尋找下一個基可行解，并且同時努力使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問題無解為止。目標(biāo)函數(shù) Z=3x1+4x2中 x1的系數(shù)大于零，如果 x1為一正數(shù)，則 Z的值就會增大，同樣若 x2不為零為一正數(shù)，也能使 Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作 σ j , j=1,2…, n。 檢驗數(shù) 目標(biāo)函數(shù)用非基變量表達(dá)時的變量系數(shù) 16 進(jìn)基列 出基行 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