【文章內(nèi)容簡介】 的目標函數(shù)w（通常人工變量在w中的系數(shù)一般取為1）和要求w的最小值，然后用單純型法求解。若求得wmin=0，則表明已知問題有可行解，進入第二階段，否則表明已知問題無可行解，計算結束。進入第二階段后，將第一階段得到的最終表去掉人工變量，并將目標函數(shù)還原為原線性規(guī)劃問題的目標函數(shù)（即修改最終表中的第一行和第一列），以此作為第二階段的初始表，繼續(xù)用單純形法求解。解：引入人工變量，轉化為：第一階段，求解線性規(guī)劃問題：先標準化：再用單純形法繼續(xù)計算如下：Cj00011CBBbX1X2X3X4X5θ1X431111031X541[2]0012σj231001X41[1/2]0111/220X221/21001/24σj1/20103/20X12102210X2101111σj00011在最終單純形表中，檢驗數(shù)全非正，且人工變量取值全為0，因此第一階段問題有唯一最優(yōu)解：結果表明已知問題有可行解，進入第二階段。先修改第一階段的最終表，再繼續(xù)計算：Cj2302X121023X21011σj001因此該問題有唯一最優(yōu)解：三、關于退化解的說明 在用單純形法計算時，可能出現(xiàn)以下兩種情況： 出現(xiàn)若干正檢驗數(shù)大小相同且都是最大。原則上可以任取一個對應的變量為換入變量，但通常會選其中一個下標最小的作為換入變量； 出現(xiàn)若干比值大小相同且都是最小。當任取一個對應的變量為換出變量時，則下一張表中有基變量的值等于0，這種現(xiàn)象稱為退化。當發(fā)生退化現(xiàn)象時，從理論上講有可能出現(xiàn)計算過程的死循環(huán)，始終求不到最優(yōu)解。為此人們已經(jīng)提出了三種避免出現(xiàn)死循環(huán)的方法，即攝動法、字典序法或最小下標法。然而千千萬萬例實際應用中從來沒遇見過出現(xiàn)死循環(huán)的問題，所以在實際計算時一般不必理會此事，可選其中一個下標最小的基變量為換出變量繼續(xù)計算即可。四、單純形法小結用最終單純形表判斷解的類型 用單純形法求解下列問題。解：在圖解法中已看到本例有無界解，用單純形法求解時，先化為標準形式列單純形表如下Cj230CBBbX1X2X3θ0X316401σj230表中最大的正檢驗數(shù)σ2=30，但x2的系數(shù)為0，使得θ不能被確定，從而z無限增大。故該問題有無界解。 用單純形法求解下列問題。解：在圖解法中已看到本例有無窮多最優(yōu)解，用單純形法求解時，先化為標準形式列單純形表如下cj22000CBBbX1X2X3X4X5θ0X3122210060X416[4]001040X51505001σj220000X340[2]11/2012X141001/400X515050013σj 0201/202X22011/21/402X141001/400X55005/25/41σj00100表中所有檢驗數(shù)均非正且無人工變量，得到最優(yōu)解X(1)=(4,2,0,0,5)T,zmax=12,進一步由于非基變量x4的檢驗數(shù)等于0，取x4作為換入變量，繼續(xù)用單純形法計算如下：cj22000CBBbX1X2X3X4X5θ2X22011/21/402X141001/40160X55005/2[5/4]14σj001002X2301001/52X13101/201/50X4400214/5σj00100表中所有檢驗數(shù)均非正且無人工變量，得到另一個最優(yōu)解X(2)=(4,2,0,0,5)T,zmax=12,連接X(1)和X(2)的線段上的點也都是最優(yōu)解。故此題有無窮多最優(yōu)解。 用單純形法求解下列問題。解：在圖解法中已看到本例無可行解，用單純形法求解時，先化為標準形式列單純形表如下cj2300MCBBbX1X2X3X4X5θ0X3122[2]1006MX514120117σj2+M2+2M0M03X26111/200MX5210111σj1M03/2MM0表中所有檢驗數(shù)均非正,但人工變量x5不等于0，使得此題無可行解。通過以上各例，我們歸納出利用最終單純形表判斷線性規(guī)劃問題解的類型的方法如下：解的類型最終表的特征無可行解有非0的人工變量有可行解唯一最優(yōu)解無非0的人工變量，非基變量的檢驗數(shù)全為負數(shù)無窮多最優(yōu)解無非0的人工變量，非基變量的檢驗數(shù)全非正，且有某個非基變量的檢驗數(shù)為0，同時該變量對應的系數(shù)列至少有一個正系數(shù)無界解無非0的人工變量，有某個非基變量的檢驗數(shù)為正數(shù)，但該變量對應的系數(shù)列全為非正數(shù)能夠用單純形法求解的線性規(guī)劃問題應首先化為標準形式，并可選擇一個單位矩陣作為基，常稱之為廣義標準形式。針對不同類型的線性規(guī)劃問題，應如何進行廣義標準化，具體方法（以大M法為例）參見表1，表中xs表示松弛變量，xa表示人工變量：表1模型決策變量約束條件目標函數(shù)特點個 數(shù)取 值右 端 項等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj ≤ 0 bi ≥0bi 0≤=≥maxZminZxs xa解法圖解法、單純形法單純形法不處理令xj =xj′ xj″ xj′ ≥0xj″ ≥0令 xj = xj不處理約束條件兩端同乘以1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′= ZminZ=－max z′0M經(jīng)過上述方法處理后可求出初始基可行解，列出初始單純形表，再用單純形法求解，對應的步驟框圖如下圖：唯一最優(yōu)解 否 否否 是是是添加松弛變量、人工變量 列出初始單純形表計算各列檢驗數(shù)бj所有бj163。0基變量中有非零的人工變量某非基變量檢驗數(shù)為零且有恰當?shù)摩葻o可行解無窮多最優(yōu)解某一бj≥0但系數(shù)列aik≤0無界解令бk=max{бj}xk為換入變量，對所有aik0計算θ 最小比值對應的變量xl為換出變量，alk為主元素1．xk替換xl2．列出新的單純形表，用矩陣的初等行變換①將主元素化為1②將主元素列的其它系數(shù)化為0第五節(jié) 線性規(guī)劃應用舉例學習運籌學的目的在于應用，而應用的第一步就是建立與實際問題對應的數(shù)學模型，正如緒論中曾經(jīng)講述的。建模時運籌學學習的核心和精髓。將經(jīng)濟管理領域的實際問題抽象為數(shù)學模型，這是一項極具創(chuàng)造性和技巧性的工作，既要求能熟練地掌握運用有關的數(shù)學知識，又要求對所研究經(jīng)濟對象的本質有深刻的理解，同時還需要相關方面的專業(yè)人員的互相配合和通力合作。當然對實際經(jīng)濟問題能給予深刻準確的數(shù)學描述以及把數(shù)學上的定理算法給予確切合理的經(jīng)濟解釋，都不是容易的事情。一般而言，一個經(jīng)濟、管理問題只有滿足以下條件時，才能建立對應的線性規(guī)劃模型。⑴等待求解問題的目標能用某種效益指標度量其大小，即能用數(shù)值指標來反映，且為線性函數(shù)；⑵.存在著多種可采取的方案；⑶.要求達到的目標是在一定條件下實現(xiàn)的，這些條件可用線性等式或不等式描述。下面舉例說明如何將實際問題歸結為線性規(guī)劃問題的數(shù)學模型。（混合配料問題） 某工廠要用三種原材料C、P、H混合調配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求、單價和原材料的供應量、單價。該廠應如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱規(guī)格要求單價(元/kg）A原材料C不少于50%原材料H不超過25%50B原材料C不少于25%原材料P不超過50%35D不限25原材料名稱每天最多供應量(kg)單價(元/kg)C10065P10025H6035解：用i=1,2,3表示產(chǎn)品A,B,D；用j=1,2,3表示原材料C,P,H；設xij為生產(chǎn)第i種產(chǎn)品中使用的第j種原料的質量(i,j=1,2,3)則該問題的數(shù)學模型為：用單純型法計算得結果:每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:C為100kg。P為50kg。H為50kg. 最大的總利潤收入Z=500元/天.（合理下料問題）現(xiàn)有一批某種型號的圓鋼長8米。問如何才能既滿足需要，又能使總的用料最少？解：設變量xj為使用第 j 種方式下料的圓鋼根數(shù)。下料方式毛坯1234需要根數(shù)32101000246200余料長度（米）則該問題的數(shù)學模型為：用單純型法計算得結果:注意：若考慮余料最少，則對應模型為：用單純型法計算得結果:（投資項目組合問題）興安公司有一筆30萬元的資金，考慮今后三年內(nèi)用于下列項目的投資：三年內(nèi)每年年初均可投資，每年獲利為投資額的20%，其本利可一起用于下一年投資；只允許第一年初投入，于第二年末收回，本利合計為投資額的150%,但此類投資限額不超過15萬元；允許于第二年初投入，于第三年末收回，本利合計為投資額的160%，但限額投資20萬元；允許于第三年初投入，年末收回，可獲利40%，但限額為10萬元.試為該公司確立一個使第三年末本利和最大的投資組合方案，請建立這個問題的線性規(guī)劃模型。解：用xij表示第i年初投放到第j個項目的資金數(shù)（注意只有6個決策變量x11,x12,x21,x23,x31,x34），則建立如下線性規(guī)劃模型：用單純形法求得：綜上投資組合方案如下：方案年初12341202031010單位：萬元第三年末本利和的最大值=58萬元。本章小結本章討論了線性規(guī)劃問題的數(shù)學模型，介紹了求解含有兩個變量的線性規(guī)劃問題的圖解法，詳細分析了單純形法的基本原理及基本步驟，并介紹了單純形法的進一步討論，同時對一些實際問題建立了線性規(guī)劃問題的數(shù)學模型。本章的學習重點是單純形法的步驟，難點是單純形法的原理及如何就一些簡單的實際問題建立線性規(guī)劃模型。練習題 把下列線性規(guī)劃化為標準形式： ，并指出其中的基可行解和最優(yōu)解。，并指出問題具有唯一最優(yōu)解、無窮最優(yōu)解、無界解還是無可行解。 ：（1）R1=｛(x1,x2)|x12+2x22≤2｝（2）R2=｛(x1,x2)|x12－2x2+3≥0,x2≥0,|x1|≤1｝（3）R3=｛(x1,x2)|x1x2≥1,x1≥1,x2≥0｝。 ，并指出屬于哪一類解。 ，其中x4，x5，x6是松弛變量。表112cj22CBXBbx1x2x3x4x5x62x5x2x1214112a21112a+8σj1（1）把表中缺少的項目填上適當?shù)臄?shù)或式子。（2）要使上表成為最優(yōu)表，a應滿足什么條件？（3）何時有無窮多最優(yōu)解？（4）何時無最優(yōu)解？（5）何時應以x3替換x1？ （如表1所示）和用單純形法迭代后得到的表（如表2所示）如下，試求括弧中未知數(shù)a～l的值。表1x1x2x3x4x5x46(b)(c)(d)10x5113(e)01cjzj(a)120