線性規(guī)劃的圖解法與單純形解法-文庫(kù)吧資料
2024-08-14 17:27本頁(yè)面
【正文】 1nxn = b1 a21 x1+ a22 x2+ …+ a2nxn = b2 … … am1 x1+ am2 x2+ …+ amnxn = bm x1, x2,…, xn ≥ 0 44 線性規(guī)劃求解的人工變量法 分別對(duì)每個(gè)約束方程中加入一個(gè)人工變量 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ù)值不受影響，我們賦予人工變量一個(gè)很大的負(fù)價(jià)值系數(shù) M (M為任意大的正數(shù) )。然后，再通過基變換，使得基變量中不含非零的人工變量。 ? 人工變量法的基本思路是： 若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量，則在每個(gè)約束方程中加入一個(gè)人工變量便可在系數(shù)矩陣中形成一個(gè)單位向量。 （ 5 ） 計(jì)算新的基矩陣的逆矩陣11?B ，求出bB 11? ，重復(fù)（ 2 ）至（ 5 ）。 （ 3 ） 根據(jù)? ? kjjj??? ?? 0|m ax ，所對(duì)應(yīng)的非基變量kX 為換入變量，計(jì)算kPB1? ，若01 ?? kPB 那問題無解，停止計(jì)算，否則進(jìn)行下一步。 41 單純形法計(jì)算的矩陣描述 基于矩陣描述單純形法求解線性規(guī)劃問題的一般計(jì)算步驟為： （ 1 ） 根據(jù)給出的線性規(guī)劃問題，在加入松馳變量或人工變量后，得到初始基變量，求初始基矩陣 B 的逆陣 1?B 。 j，迭代后為P j ，則有P jBP 39。 39 單純形法計(jì)算的矩陣描述 非基變量 基變量 BX NX SX X S0 B N I b zc jj ? C B C N 0 當(dāng)?shù)舾刹胶螅兞繛閄 B 時(shí)，該步的單純形中由X B 系數(shù)組成的矩陣為 I ，這時(shí)對(duì)應(yīng)X S 的系數(shù)矩陣在新表中應(yīng)為B 1? 。 多重最優(yōu)解的判斷 :最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 ,則線則性規(guī)劃具有多重最優(yōu)解。 33 最優(yōu)解的判別定理 ? 定理 3 有無界解的判別定理 若? ? T( 0 ) 12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) ? m + k 0, 并且對(duì)應(yīng)的變量系數(shù),i m ka ??≤ 0 ， i = 1,2, , … , m , 則該線性規(guī)劃問題有無界解（或無有界最優(yōu)解）。 32 最優(yōu)解的判別定理 ? 定理 1 最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對(duì)應(yīng)于基 B 的一個(gè)基可行解，對(duì)于一切 j = m +1 , … , n , 有檢驗(yàn)數(shù) ? j≤ 0, 則 X ( 0 ) 為最優(yōu)解。 29 【 例 】 求解線性規(guī)劃 21 42m a x xxZ ?????????????????0,21024221212121xxxxxxxx【 解 】 :化為標(biāo)準(zhǔn)型后用單純形法計(jì)算如下表所示 30 XB x1 x2 x3 x4 x5 b θ (1) x3 x4 x5 － 1 1 1 [2] 2 － 1 1 0 0 0 1 0 0 0 1 4→ 10 2 2 5 — λj 2 4↑ 0 0 0 (2) x2 x4 x5 － 1/2 [2] 1/2 1 0 0 1/2 － 1 1/2 0 1 0 0 0 1 2 6→ 4 — 3 8 λj 4↑ 0 － 2 0 0 (3) x2 x1 x5 0 1 0 1 0 0 1/4 － 1/2 [3/4] 1/4 1/2 － 1/4 0 0 1 7/2 3 5/2→ 14 — 10/3 λj 0 0 0↑ － 2 0 (4) x2 x1 x3 0 1 0 1 0 0 0 0 1 1/3 1/3 － 1/3 － 1/3 2/3 4/3 8/3 14/3 10/3 λj 0 0 0 － 2 0 31 表 (3)中 λj全部非正 ,則最優(yōu)解為 : 20,)25,0,0,27,3()1( ?? ZX T 表 (3)表明 ,非基變量 x3的檢驗(yàn)數(shù) λ3=0, x3若增加 ,目標(biāo)函數(shù)值不變 , 即當(dāng) x3進(jìn)基時(shí) Z仍 等于 20。 表 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)解無界 。 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3階單位矩陣 ,x x x5為基變量。 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可作為初始基變量，單純法計(jì)算結(jié)果如表 。 ③計(jì)算各非基變量 xj的檢驗(yàn)數(shù) ?j，若所有 ?j≤0，則問題已得到最優(yōu)解， ④在大于 0的檢驗(yàn)數(shù)中，若某個(gè) ?k所對(duì)應(yīng)的系數(shù)列向量 Pk≤0，則此問 ⑤根據(jù) max{?j｜ ?j＞ 0}=?k原則，確定 xk為換入變量 (進(jìn)基變量 )，再按 ?規(guī)則計(jì)算： ?=min{bi/aik| aik＞ 0}=bl/ aik 確定 xl為換出變量。 19 單純形算法的計(jì)算步驟 ① 將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 當(dāng)目標(biāo)函數(shù)中有基變量 xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi消去即可求出檢驗(yàn)數(shù)。 本例中 σ 1=3, σ 2=4, σ 3=0, σ 4=0。 13 【 例 】 用單純形法求下列線性規(guī)劃的最優(yōu)解 ????????????0,30340243max21212121xxxxxxxxZ14 【 解 】 化為標(biāo)準(zhǔn)型 ， 加入松馳變量 x x4則標(biāo)準(zhǔn)型為 系數(shù)矩陣 A及可行基 B1 r(B1)=2， B1是一個(gè)初始基 ,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)解，可以從目標(biāo)函數(shù)中的系
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1