【文章內(nèi)容簡(jiǎn)介】 是： mmXCkii????1? ?另外，若可行域?yàn)闊o(wú)界，則可能無(wú)最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。根據(jù)以上討論，可以得到以下結(jié)論： 線(xiàn)性規(guī)劃問(wèn)題的所有可行解構(gòu)成的集合是凸集 ， 也可能為無(wú)界域 ， 它們有有限個(gè)頂點(diǎn) ， 線(xiàn)性規(guī)劃問(wèn)題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)； 若線(xiàn)性規(guī)劃問(wèn)題有最優(yōu)解 ， 必在某頂點(diǎn)上得到 。 雖然頂點(diǎn)數(shù)目是有限的 (它不大于個(gè) )， 若采用 “ 枚舉法 ”找所有基可行解 ， 然后一一比較 ， 最終可能找到最優(yōu)解 。 但當(dāng) n,m的數(shù)較大時(shí) ， 這種辦法是行不通的 ，所以要繼續(xù)討論 ， 如何有效地找到最優(yōu)解 ， 有多種方法 ， 這里僅介紹 單純形法 。 第 2節(jié) 結(jié)束 （ 第三版） 《 運(yùn)籌學(xué) 》 教材編寫(xiě)組 編 清華大學(xué)出版社 運(yùn)籌學(xué) 第 1章 線(xiàn)性規(guī)劃與單純形法 第 3節(jié) 單純形法 錢(qián)頌迪 制作 第 1章 線(xiàn)性規(guī)劃與單純形法 第 3節(jié) 單純形法 舉例 初始基可行解的確定 最優(yōu)性檢驗(yàn)與解的判斷 基變換 迭代（旋轉(zhuǎn)運(yùn)算） 單純形法求解線(xiàn)性規(guī)劃的思路： ? 一般線(xiàn)性規(guī)劃問(wèn)題具有線(xiàn)性方程組的變量數(shù)大于方程個(gè)數(shù) ， 這時(shí)有不定的解 。但可以從線(xiàn)性方程組中找出一個(gè)個(gè)的單純形 ， 每一個(gè)單純形可以求得一組解 ，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小 ， 決定下一步選擇的單純形 。 這就是迭代 ， 直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止 。 這樣問(wèn)題就得到了最優(yōu)解 ，先舉一例來(lái)說(shuō)明 。 注： ? 單純形是指 0維中的點(diǎn) ， 一維中的線(xiàn)段 ， 二維中的三角形 ， 三維中的四面體 ， n維空間中的有 n+1個(gè)頂點(diǎn)的多面體 。 例如在三維空間中的四面體 ， 其頂點(diǎn)分別為 (0， 0， 0)， (1， 0， 0)，(0， 1， 0)， (0， 0， 1)。 具有單位截距的單純形的方程是 ∑ xi≤ 1， 并且 xi≥ 0， i=1,2,…,m。 舉例 例 6 試以例 1來(lái)討論如何用單純形法求解。例 1的標(biāo)準(zhǔn)型為： )111(00032m a x 54321 ?????? xxxxxz5,2,10124)121(164825241321????????????jxxxxxxxxj 約束方程 (112)式的系數(shù)矩陣 ? ? 從 (112)式中可以看到 x3,x4,x5的系數(shù)列向量 ? ?????????????100010040004121, 54321 PPPPPA?????????????????????????????????100,010,001543 PPP P3 ,P4,P5是線(xiàn)性獨(dú)立的，這些向量構(gòu)成一個(gè)基 對(duì)應(yīng)于 B的變量 x3,x4,x5為 基變量 . ? ?????????????100010001, 543 PPPB124)121(164825241321????????xxxxxxx)131(412416282514213?????????????xxxxxxx從 (112)式中可以得到（ 113） 將 (113)式代入目標(biāo)函數(shù) (111) ? 得到 ? 當(dāng)令非基變量 x1=x2=0， 便得到 z=0。 這時(shí)得到一個(gè)基可行解 X(0) ? X(0)=(0,0,8,16,12)T ? 這個(gè)基可行解表示：工廠(chǎng)沒(méi)有安排生產(chǎn)產(chǎn)品 Ⅰ 、Ⅱ ；資源都沒(méi)有被利用，所以工廠(chǎng)的利潤(rùn)指標(biāo)z=0。 )111(00032m a x 54321 ?????? xxxxxz)141(320 21 ???? xxz從分析目標(biāo)函數(shù)的表達(dá)式 (114)可以看到 ? 非基變量 x1,x2(即沒(méi)有安排生產(chǎn)產(chǎn)品 Ⅰ ，Ⅱ )的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品 Ⅰ 或 Ⅱ ，就可以使工廠(chǎng)的利潤(rùn)指標(biāo)增加。所以只要在目標(biāo)函數(shù) (114)的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，就需要將非基變量與基變量進(jìn)行對(duì)換。 如何確定換入，換出變量 ? 一般選擇正系數(shù)最大的那個(gè)非基變量 x2為換入變量 ， 將它換入到基變量中去 ，同時(shí)還要確定基變量中有一個(gè)要換出來(lái)成為非基變量 ， 可按以下方法來(lái)確定換出變量 。 ? 現(xiàn)分析 (113)式 ， 當(dāng)將 x2定為換入變量后 ， 必須從 x3,x4,x5中確定一個(gè)換出變量 ，并保證其余的都是非負(fù) ， 即 x3,x4,x5≥ 0。 當(dāng) x1=0,由 (113)式得到 )151(041201602825423??????????????xxxxx)131(412416282514213?????????????xxxxxxxx2取何值時(shí)，才能滿(mǎn)足非負(fù)要求 ? 從 (115)式中可以看出 ， 只有選擇 ? x2=min(8/2,,12/4)=3時(shí) ， ? 才能使 (115)式成立 。 ? 因當(dāng) x2=3時(shí) ， 基變量 x5=0， 這就決定用 x2去替換 x5。 ? 以上數(shù)學(xué)描述說(shuō)明了每生產(chǎn)一件產(chǎn)品 Ⅱ ，需要用掉各種資源數(shù)為 (2， 0， 4)。 由這些資源中的薄弱環(huán)節(jié) ， 就確定了產(chǎn)品 Ⅱ的產(chǎn)量 。 ? 這里就是由原材料 B的數(shù)量確定了產(chǎn)品 Ⅱ的產(chǎn)量 x2=12/4=3件 。 為了求得以 x3,x4,x2為基變量的一個(gè)基可行解和進(jìn)一步分析問(wèn)題，需將 (113)中 x2的位置與 x5的位置對(duì)換。得到 )131(412416282514213?????????????xxxxxxx? ?? ?? ?)161(312424161825214123???????????????xxxxxxx用高斯消去法 ? 將 (116)式中 x2的系數(shù)列向量變換為單位列向量 。其運(yùn)算步驟是： ? ③ ′ =③ /4；① ′ =① 2③ ′ 。② ′ =② , ? 并將結(jié)果仍按原順序排列有 ： ? ?? ?? ?? ?17134132416121239。5239。1439。513?????????????????xxxxxxx再將 (117)式代入目標(biāo)函數(shù) (111)式得到 ? ? ?181432951???? xxz 令非基變量 x 1 =x 5 =0 ，得到 z=9 ，并得到另一個(gè)基可行解 X(1) X(1)=(0,3,2,16,0)T ? 從目標(biāo)函數(shù)的表達(dá)式 (118)中可以看到 ， 非基變量 x1的系數(shù)是正的 ， 說(shuō)明目標(biāo)函數(shù)值還可以增大 ， X(1)還 不是最優(yōu)解 。 ? 于是再用上述方法 ， 確定換入 、 換出變量 ， 繼續(xù)迭代 ， 再得到另一個(gè)基可行解 X(2) ? X(2)=(2,3,0,8,0)T ? 再經(jīng)過(guò)一次迭代 ， 再得到一個(gè)基可行解 X(3) ? X(3)=(4,2,0,0,4)T ? 而這時(shí)得到目標(biāo)函數(shù)的表達(dá)式是： ? z= (119) ? 再檢查 (119)式，可見(jiàn)到所有非基變量 x3,x4的系數(shù)都是負(fù)數(shù)。這說(shuō)明若要用剩余資源 x3,x4，就必須支付附加費(fèi)用。 ? 所以當(dāng) x3=x4=0時(shí)，即不再利用這些資源時(shí)，目標(biāo)函數(shù)達(dá)到最大值。所以 X(3)是最優(yōu)解。即當(dāng)產(chǎn)品 Ⅰ 生產(chǎn) 4件，產(chǎn)品 Ⅱ 生產(chǎn) 2件，工廠(chǎng)才能得到最大利潤(rùn)。 通過(guò)上例，可以了解利用單純形法求解線(xiàn)性規(guī)劃問(wèn)題的思路?，F(xiàn)將每步迭代得到的結(jié)果與圖解法做一對(duì)比，其幾何意義就很清楚了。 ? 原例 1的線(xiàn)性規(guī)劃問(wèn)題是二維的 ， ? 即兩個(gè)變量 x1,x2；當(dāng)加入松弛變量 x3,x4,x5后 ， ? 變換為高維的 。 ? 這時(shí)可以想象 ， 滿(mǎn)足所有約束條件的可行域是高維空間的凸多面體 (凸集 )。 這凸多面體上的頂點(diǎn)，就是基可行解。 初始基可行解 X(0)=(0,0,8,16,12)T 就相當(dāng)于圖 12中的原點(diǎn) (0， 0)， X(1)=(0,3,2,16,0)T 相當(dāng)于 圖 12中 的 Q4點(diǎn) (0， 3)； ? X(2)=(2， 3， 0， 8， 0)T相當(dāng)于 ? 圖 12中的 Q3點(diǎn) (2， 3)， ? 最優(yōu)解 X(3)=(4， 2， 0， 0， 4)T ? 相當(dāng)于圖 12中的 Q2點(diǎn) (4， 2)。 ? 從初始基可行解 X(0)開(kāi)始迭代 ， 依次得到 X(1)， X(2)，X(3)。 這相當(dāng)于圖 12中的目標(biāo)函數(shù)平移時(shí) ， ? 從 0點(diǎn)開(kāi)始 ， 首先碰到 Q4， 然后碰到 Q3， 最后達(dá)到 Q2。下面討論一般線(xiàn)性規(guī)劃問(wèn)題的求解 。 一般線(xiàn)性規(guī)劃問(wèn)題的求解 初始基可行解的確定 ? 為了確定初始基可行解 ， 要首先找出初始可行基 ， 其方法如下 。 ? (1)直接觀(guān)察 ? (2)加松弛變量 ? (3)加非負(fù)的人工變量 (1)直接觀(guān)察 ? ?? ?njxbxPxczjnjjjnijjj,2,10211201m a x1???????????若線(xiàn)性規(guī)劃問(wèn)題 從 Pj(j=1,2,…,n)中一般能直接觀(guān)察到存在一個(gè)初始可行基 ? ?????????????????111, 21????? mPPPB(2)加松弛變量 ? 對(duì)所有約束條件是 “ ≤ ” 形式的不等式 ，可以利用化為標(biāo)準(zhǔn)型的方法 ， 在每個(gè)約束條件的左端加上一個(gè)松弛變量 。 ? 經(jīng) 過(guò) 整 理 ， 重 新 對(duì) xj 及aij(i=1,2,…,m。j=1,2,…,n)進(jìn)行編號(hào) ，則可得下列方程組 x1,x2,…,xm 為松弛變量 ? ?njxbxaxaxbxaxaxbxaxaxjmnmmmmmnnmmnnmm,2,1,022111,2211,221111,11??????????????????????????????????于是含有 m m單位矩陣，以 B 作為可行基。 ? ?????????????????111, 21????? mPPPB 將 (122)式每個(gè)等式移項(xiàng)得 令 xm+1=xm+2=…=xn=0， 由 (123)式可得 xi=bi (i=1,2,…,m) ? ?nmmmmmmnnmmnnmmxaxabxxaxabxxaxabx???????????????????????????????11,211,222111,111231得到一個(gè)初始基可行解 ? 又因 bi≥ 0(在 13節(jié)中已做過(guò)規(guī)定 )， 所以得到一個(gè)初始基可行解 ? X=(x1,x2,…,xm,0， …， 0)T nm個(gè) =(b1,b2,…,bm,0， …， 0)T nm個(gè) (3)