【正文】 ?? 0|m ax ，所對(duì)應(yīng)的非基變量kX 為換入變量，計(jì)算kPB1? ，若01 ?? kPB 那問(wèn)題無(wú)解，停止計(jì)算，否則進(jìn)行下一步。 43 線性規(guī)劃求解的人工變量法 對(duì)于如下線性規(guī)劃問(wèn)題 m a x z =c1 x1+ c2 x2+ …+ cn xn a11 x1+ a12 x2+ …+ a1nxn = 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ī)劃問(wèn)題的最優(yōu)目標(biāo)函數(shù)值不受影響，我們賦予人工變量一個(gè)很大的負(fù)價(jià)值系數(shù) M (M為任意大的正數(shù) )。也就是，給原問(wèn)題加入人工變量，構(gòu)造僅含人工變量的目標(biāo)函數(shù)，并要求最小化。 無(wú)界解的判斷 : 某個(gè) λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無(wú)界解 退化基本可行解的判斷 :存在某個(gè)基變量為零的基本可行解 。 （ 2 ） 應(yīng)用圖解法，對(duì)1?a 的一切值，求線性規(guī)劃以a表示的最優(yōu)值。 66 勃蘭特 (Bland)法 1974 年由勃蘭特 ( B l a nd) 提出了一個(gè)避免出現(xiàn)循環(huán)現(xiàn)象的簡(jiǎn)便規(guī)則： （ 1 ）選取0?σ j 中下標(biāo)最小的非基變量x k為換入變量，即取m i n ( | 0 )jkj ???； （ 2 ）按? 規(guī)則計(jì)算時(shí)，若出現(xiàn)兩個(gè)和兩個(gè)以上的最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量。 ????????????0,426385m i n21212121xxxxxxxxZ62 【 解 】 第一階段問(wèn)題為 ???????????????5,2,1,04263m i n54213215?jxxxxxxxxxwj用單純形法計(jì)算如下表： 63 Cj 0 0 0 0 1 b CB XB x1 x2 x3 x4 x5 0 1 x3 x5 [3] 1 1 － 2 1 0 0 － 1 0 1 6→ 4 λj － 1↑ 2 0 1 0 0 1 x1 x5 1 0 1/3 － 7/3 1/3 － 1/3 0 － 1 0 1 2 2 λj 0 7/3 1/3 1 0 λj≥0,得到第一階段的最優(yōu)解 X=(2,0,0,0,2)T,最優(yōu)目標(biāo)值 w=2≠0,x5仍在基變量中 ,從而原問(wèn)題無(wú)可行解。 但最優(yōu)解中含有人工變量 x5≠0說(shuō)明這個(gè)解是偽最優(yōu)解 ， 是不可行的 ， 因此原問(wèn)題無(wú)可行解 。然后，再通過(guò)基變換，使得基變量中不含非零的人工變量。 41 單純形法計(jì)算的矩陣描述 基于矩陣描述單純形法求解線性規(guī)劃問(wèn)題的一般計(jì)算步驟為： （ 1 ） 根據(jù)給出的線性規(guī)劃問(wèn)題，在加入松馳變量或人工變量后，得到初始基變量，求初始基矩陣 B 的逆陣 1?B 。 33 最優(yōu)解的判別定理 ? 定理 3 有無(wú)界解的判別定理 若? ? 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ī)劃問(wèn)題有無(wú)界解（或無(wú)有界最優(yōu)解）。 容易觀察到 ,系數(shù)矩陣中有一個(gè) 3階單位矩陣 ,x x x5為基變量。 當(dāng)目標(biāo)函數(shù)中有基變量 xi時(shí)，利用約束條件將目標(biāo)函數(shù)中的 xi消去即可求出檢驗(yàn)數(shù)。 ? 如果某一線性規(guī)劃問(wèn)題有最優(yōu)解，我們可以按照這樣的思路來(lái)求解：先找可行域中的一個(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ù)上述過(guò)程，直到找不到使目標(biāo)函數(shù)值更大的新頂點(diǎn)為止。 ? 簡(jiǎn)單、直觀的圖解法一般只適用于具有 兩個(gè)決策變量 的線性規(guī)劃問(wèn)題。令非基變量取值為零，便得到一基可行解。 ②找出或構(gòu)造一個(gè) m階單位矩陣作為初始可行基，建立初始單純形表。 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無(wú)界解 。 無(wú)界解的判斷 : 某個(gè) λk0且 aik≤０（ i=1， 2,…,m ）則線性規(guī)劃具有無(wú)界解 35 單純形法計(jì)算的矩陣描述 對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題 m a x0z C XAX bX????=≥ 假定存在基 B ，基變量為BX，非基變量為NX，則有 111111()()BNB B N N B N N NB N B NX B b B N Xz C X C X C B b B N X C XC B b C C B N X????????? ? ? ? ?? ? ? 36 單純形法計(jì)算的矩陣描述 與前面檢驗(yàn)數(shù)計(jì)算公式對(duì)照，可得非基變量檢驗(yàn)數(shù)計(jì)算公式 1N N BC C B N???? 另外，基變（向）量 XB的檢驗(yàn)數(shù)可寫(xiě)作 1 0B B BC C B B??? ? ? 所以可得標(biāo)準(zhǔn)形式的線性規(guī)劃模型檢驗(yàn)數(shù)計(jì)算的一般計(jì)算公式 1BC C B A???? 37 單純形法計(jì)算的矩陣描述 再考慮下列線性規(guī)劃問(wèn)題 m a x0z C XAX bX????≤≥ 上式加上松弛變量后為 m a x 00 , 0SSSz C X XA X I X bXX???????≥ ≥ 38 單純形法計(jì)算的矩陣描述 ? ?m a x z | 0SXCX??? ???? ? ??????????????0,|XXbXXIASS 式中，X S松馳變量，),( 21TxxxX mnnnS ???? ? ， I 為 nm ? 單位矩陣。 （ 4 ） 根據(jù) ?規(guī)則，求出：? ?11111( ) ( )m in 0( ) ( )ilkiilB b B bBPB P B Pkk??????????? ? ??????? 它對(duì)應(yīng)的基變量lX 為換出變量，于是可給出一組新的基變量以及新的基矩陣1B 。 ?由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而找到原問(wèn)題的一個(gè)可行基。 我們可以構(gòu)造如下輔助問(wèn)題 m in w = xn +1+ … + xn + m+0 x1+ … +0 xn a11 x1+ a12 x2+ … + a1 nxn+ xn +1 = b1 a21 x1+ a22 x2