【正文】 松馳變量，),( 21TxxxX mnnnS ???? ? ， I 為 nm ? 單位矩陣。 ? 定理 2 有無窮多最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對應(yīng)于基 B 的一個(gè)基可行解，對于一切 j = m +1, … , n , 有檢驗(yàn)數(shù) ? j ≤ 0, 且存在某個(gè)非基變量對應(yīng)的檢驗(yàn)數(shù) ? m + k =0, 則該線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無界解 。 23 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 24 【 例 】 用單純形法求解 421 22m i n xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj25 【 解 】 這是一個(gè)極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解 。 ②找出或構(gòu)造一個(gè) m階單位矩陣作為初始可行基，建立初始單純形表。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) σ j≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。令非基變量取值為零，便得到一基可行解。 ? 線性規(guī)劃問題求解時(shí)可能出現(xiàn)四種結(jié)局： 唯一最優(yōu)解 、無窮多個(gè)最優(yōu)解 、 有無界解 、 無解或無可行解 。 ? 簡單、直觀的圖解法一般只適用于具有 兩個(gè)決策變量 的線性規(guī)劃問題。 ? 用圖解法求解實(shí)際線性規(guī)劃問題，一般按照如下基本步驟： Step1 畫直坐標(biāo)系； Step2 根據(jù)約束條件畫出可行域； Step3 畫過坐標(biāo)原點(diǎn)的目標(biāo)函數(shù)線； Step4 確定目標(biāo)函數(shù)值的增大方向 (目標(biāo)函數(shù)線法線方向 ) Step5 目標(biāo)函數(shù)線沿著增大方向平行移動(dòng)，與可行域相交且有最大目標(biāo)函數(shù)值的頂點(diǎn)，即為線性規(guī)劃問題的最優(yōu)解 。 ? 如果某一線性規(guī)劃問題有最優(yōu)解，我們可以按照這樣的思路來求解：先找可行域中的一個(gè)頂點(diǎn)，計(jì)算頂點(diǎn)處的目標(biāo)函數(shù)值，然后判別是否有其它頂點(diǎn)處的目標(biāo)函數(shù)值比這個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值更大，如有，轉(zhuǎn)到新的頂點(diǎn)，重復(fù)上述過程，直到找不到使目標(biāo)函數(shù)值更大的新頂點(diǎn)為止。 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ù)中的系數(shù)看出。 當(dāng)目標(biāo)函數(shù)中有基變量 xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi消去即可求出檢驗(yàn)數(shù)。 ③計(jì)算各非基變量 xj的檢驗(yàn)數(shù) ?j，若所有 ?j≤0，則問題已得到最優(yōu)解， ④在大于 0的檢驗(yàn)數(shù)中，若某個(gè) ?k所對應(yīng)的系數(shù)列向量 Pk≤0，則此問 ⑤根據(jù) max{?j｜ ?j＞ 0}=?k原則，確定 xk為換入變量 (進(jìn)基變量 )，再按 ?規(guī)則計(jì)算： ?=min{bi/aik| aik＞ 0}=bl/ aik 確定 xl為換出變量。 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3階單位矩陣 ,x x x5為基變量。 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。 33 最優(yōu)解的判別定理 ? 定理 3 有無界解的判別定理 若? ? T( 0 ) 12 , , , , 0 , , 0mX b b b? ? ??為對應(yīng)于基 B 的一個(gè)基可行解，存在某個(gè)非基變量對應(yīng)的檢驗(yàn)數(shù) ? m + k 0, 并且對應(yīng)的變量系數(shù),i m ka ??≤ 0 ， i = 1,2, , … , m , 則該線性規(guī)劃問題有無界解（或無有界最優(yōu)解）。 39 單純形法計(jì)算的矩陣描述 非基變量 基變量 BX NX SX X S0 B N I b zc jj ? C B C N 0 當(dāng)?shù)舾刹胶?，基變量為X B 時(shí)，該步的單純形中由X B 系數(shù)組成的矩陣為 I ，這時(shí)對應(yīng)X S 的系數(shù)矩陣在新表中應(yīng)為B 1? 。 41 單純形法計(jì)算的矩陣描述 基于矩陣描述單純形法求解線性規(guī)劃問題的一般計(jì)算步驟為： （ 1 ） 根據(jù)給出的線性規(guī)劃問題，在加入松馳變量或人工變量后，得到初始基變量，求初始基矩陣 B 的逆陣 1?B 。 （ 5 ） 計(jì)算新的基矩陣的逆矩陣11?B ，求出bB 11? ，重復(fù)（ 2 ）至（ 5 ）。然后，再通過基變換，使得基變量中不含非零的人工變量。 ?這種方法我們通常稱其為大 M法。 但最優(yōu)解中含有人工變量 x5≠0說明這個(gè)解是偽最優(yōu)解 ， 是不可行的 ， 因此原問題無可行解 。 第二階段 ，單純形法求解原問題 第一階段計(jì)算得到的最終單純形表中除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換成原問題的目標(biāo)函數(shù)后，作為第二階段計(jì)算的初始表，繼續(xù)求解。 ????????????