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