【正文】 第二章 線性規(guī)劃的圖解法與單純形解法 1 線性規(guī)劃問(wèn)題的圖解法 2 線性規(guī)劃單純形法的原理與計(jì)算步驟 3 線性規(guī)劃單純形法的進(jìn)一步討論 4 線性規(guī)劃單純形法的改進(jìn) 5 線性規(guī)劃特例 — 運(yùn)輸問(wèn)題 線性規(guī)劃問(wèn)題的圖解法 ?圖解法是用作圖的方法求解線性規(guī)劃問(wèn)題，一般只適用于具有兩個(gè)決策變量的線性規(guī)劃問(wèn)題。 ?步驟 1 畫(huà)直角坐標(biāo)系 ?步驟 2 根據(jù)約束條件畫(huà)出可行域 ?步驟 3 畫(huà)過(guò)坐標(biāo)原點(diǎn)的目標(biāo)函數(shù)線 ?步驟 4 確定目標(biāo)函數(shù)的增大方向 ?步驟 5 讓目標(biāo)函數(shù)沿著增大方向平行移動(dòng)，與可行域相交且有最大目標(biāo)函數(shù)值的頂點(diǎn)，即為線性規(guī)劃問(wèn)題的最優(yōu)解。 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 ?? 線性規(guī)劃問(wèn)題的圖解法 用圖解法求解如下線性規(guī)劃問(wèn)題： 例題 12121212m a x 2 3 2 2 12 4 16 5 15 , 0 z x xxxxxxx???????????? ??（ 1 ）（ 2 ）（ 3 ）（ 4 ） 線性規(guī)劃問(wèn)題的圖解法 ?求解 Q3點(diǎn)為（ 3， 3），此時(shí) z=15 線性規(guī)劃問(wèn)題的圖解法 ? 本例中我們用圖解法得到的問(wèn)題的最優(yōu)解是惟一的。 但在線性規(guī)劃問(wèn)題的計(jì)算中 ,解的情況還可能出現(xiàn)下列幾種 : ? 1 無(wú)窮最優(yōu)解。如將本例的目標(biāo)函數(shù)改變?yōu)? 則目標(biāo)函數(shù)的圖形恰好與 (1)平行。因此該線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解 ,也稱具有多重最優(yōu)解 。 12m a x 3 3z x x?? 線性規(guī)劃問(wèn)題的圖解法 ?2. 無(wú)界解 (有可行解但無(wú)有界最優(yōu)解 )。 如果本例中約束條件只剩下 (2)和(4),其他條件 (1)、 (3)不再考慮。 用圖解法求解時(shí) , 可以看到變量的取值可以無(wú)限增大 , 因而目標(biāo)函數(shù)的值也可以一直增大到無(wú)窮。這種情況下稱問(wèn)題具有無(wú)界解或無(wú)最優(yōu)解。 其原因是由于在建立實(shí)際問(wèn)題的數(shù)學(xué)模型時(shí)遺漏了某些必要的資源約束。 12112m a x 2 3 4 16 , 0 z x xxxx????????? ??（ 2 ）（ 4 ） 線性規(guī)劃問(wèn)題的圖解法 ?3. 無(wú)可行解。如下述線性規(guī)劃模型： ?用圖解法求解時(shí)找不到滿足所有約束條件的公共范圍，這時(shí)問(wèn)題無(wú)可行解。其原因是模型本身有錯(cuò)誤 , 約束條件之間相互矛盾 , 應(yīng)檢查修正。 12m a x 2 3z x x??1212122 2 1 2. . 2 1 4,0xxs t x xxx???????? ??圖解法雖然只能用來(lái)求解只具有兩個(gè)變量的線性規(guī)劃問(wèn)題 , 但它的解題思路和幾何上直觀得到的一些概念判斷 , 對(duì)下面要講的求解一般線性規(guī)劃問(wèn)題的單純形法有很大啟示 : 線性規(guī)劃問(wèn)題求解的基本依據(jù)是：線性規(guī)劃問(wèn)題的最優(yōu)解總可在可行域的頂點(diǎn)中尋找，尋找線性規(guī)劃問(wèn)題的最優(yōu)解只需比較有限個(gè)頂點(diǎn)處的目標(biāo)函數(shù)值。 線性規(guī)劃問(wèn)題求解時(shí)可能出現(xiàn)四種結(jié)局： 唯一最優(yōu)解 無(wú)窮多個(gè)最優(yōu)解 無(wú)有界解 無(wú)解或無(wú)可行解 如果某一線性規(guī)劃問(wèn)題有最優(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ù)上述過(guò)程，直到找不到使目標(biāo)函數(shù)值更大的新頂點(diǎn)為止。 (1)可行解區(qū)域要畫(huà)正確 (2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò) (3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng) 從可行域中的一個(gè)基可行解出發(fā)，判別它是否已經(jīng)是最優(yōu)解，如果不是，尋找下一個(gè)基可行解，并且同時(shí)努力使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找到最優(yōu)解或判定問(wèn)題無(wú)解為止。 基本思想： 線性規(guī)劃單純形法的原理與計(jì)算步驟 3 尋找改進(jìn)的基可行解 2 最優(yōu)性檢驗(yàn)和解的判別 1 確定初始基可行解 【 例題 】 用單純形法求下列線性規(guī)劃的最優(yōu)解 ????????????0,30340243max21212121xxxxxxxxZ單純形法的計(jì)算步驟： ?步驟 1：求初始基可行解，列出初始單純形表。 ? 對(duì)非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題首先要化成 標(biāo)準(zhǔn)形式 。 由于我們總可以設(shè)法使約束方程的系數(shù)矩陣中包含一個(gè) 單位矩陣 [P1,P2,… ,Pm] ，以此作為基即可求得問(wèn)題的一個(gè)初始基可行解。首先經(jīng)過(guò)變化迭代可將線性規(guī)劃約束條件變成如下形式： 必須是標(biāo)準(zhǔn)形式 1 1 1 , 1 1 12 2 2 , 1 1 2, 1 11...... ...... 1 , 2... ,m m n nm m n nm m m m m m n nni i ij jjmx b a x a xx b a x a xx b a x a xx b a x i m????????? ? ? ?? ? ? ?? ? ? ?? ? ??即列出單純形表 c j c 1 c 2 … c m c m +1 … c m + k … c n c B X B x 1 x 2 … x m x m +1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ? 0 0 1 ? 0 … … … … 0 0 ? 1 a 1 , m +1 a 2 , m +1 ? a m , m +1 … … … a 1 , m + k a 2 , m + k ? a m , m + k … … ?… a 1n a 2n ? a mn b 1 b 2 ? b m θ 1 θ 2 ? θ m ????miijijj acc1? 0 0 … 0 σm +1 … σ m + k … σ n ???miii bcz1 單純形法全過(guò)程的計(jì)算 ， 可以用列表的方法計(jì)算更為簡(jiǎn)潔 ，這種表格稱為單純形表 。 判斷一個(gè)基可行解是否最優(yōu) ， 需計(jì)算相應(yīng)的檢驗(yàn)數(shù) 。 檢驗(yàn)數(shù)等于目標(biāo)函數(shù)價(jià)值系數(shù) c減去 c對(duì)應(yīng)的系數(shù)向量分量與基變量?jī)r(jià)值系數(shù)的乘積之和 。 基變量的檢驗(yàn)數(shù)一定為 0。 【 解 】 首先化為標(biāo)準(zhǔn)型 ， 加入松馳變量 x x4則標(biāo)準(zhǔn)型為 系數(shù)矩陣 A及可行基 B1 r(B1)=2， B1是單位矩陣作為初始基 ,x x4為基變量 ，x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知x3= x4=30得到初始基可行解 X(1)=(0,0,40,30)T ??????????????0,30340243m a x432142132121xxxxxxxxxxxxZ???????10310112A???????10011B單純形法的計(jì)算步驟： ?步驟 2 最優(yōu)性檢驗(yàn) ?在單純形表中，若所有的檢驗(yàn)數(shù) 表中的基可行解即為最優(yōu)解。若存在 并且有 ，則問(wèn)題無(wú)有界解。計(jì)算結(jié)束。否則轉(zhuǎn)入下一步。 ?步驟 3 從一個(gè)基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)更大的基可行解，列出新的單純形表。 0jP ?0j? ?0j? ??步驟 4 重復(fù)步驟 2和 3，一直到計(jì)算結(jié)束。 進(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 σ j 基變量 1 10 0 0 1/3 0 1/3 10 5/3 1 1/3 40 5/3 0 4/3 30 1 0 3/5 1/5 18 0 1 1/5 2/5 4 0 0 1 1 將 3化為 1 乘以1/3后得到 30 18 單純形算法的計(jì)算步驟 ①將線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型。 ②找出或構(gòu)造一個(gè) m階單位矩陣作為初始可行基，建立初始單純形表。 ③計(jì)算各非基變量 xj的檢驗(yàn)數(shù) ?j，若所有 ?j≤0，則問(wèn)題已得到最 ④在大于 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為換出變量。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄浚?aik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。 線性規(guī)劃單純形法的原理與計(jì)算步驟 ?單純形法計(jì)算中可能出現(xiàn)以下兩種情況： ?出現(xiàn)兩個(gè)以上 ，原則上可任取一 個(gè) 對(duì)應(yīng)的為換入基的變量； ?相持。 即計(jì)算值出現(xiàn)兩個(gè)以上相同 的最小值。則可任選其中一個(gè)基變量作為換出變量。 ? ?m ax j?jx?單純形法的計(jì)算 用單純形法求解線性規(guī)劃問(wèn)題： 例題 1 12121212m a x 2 32 2 124 16..