【正文】 性規(guī)劃問(wèn)題存在可行域，則其可行域一定是凸集。0并設(shè)其可行域?yàn)镃，若XX2為其可行解，且X1≠X2 ，則 X1206。C， 即AX1=b，AX2=b，X1179。0，又 X為XX2連線上一點(diǎn)，即 X=aX1+(1a)X2206。0， ∴ X 206。 引理 線性規(guī)劃問(wèn)題的可行解X為基可行解的充要條件，X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的證明：①必要性：X基可行解222。,xk,0,0,xk所對(duì)應(yīng)的系數(shù)列向量P1,P2,②充分性： X的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立222。m；當(dāng)k=m時(shí)，則x1,x2,Pk恰好構(gòu)成基， ∴ X為基可行解。,Pk一起構(gòu)成基， ∴ X為基可行解。證明：（用反證法） 等價(jià)于證明 X非基可行解219。 X非凸集頂點(diǎn)不失一般性，設(shè)X=(x1,x2,0)T，為非基可行解，∵ X為可行解，又 X是非基可行解， ∴ P1,P2,+dmPm=0， 其中d1，d2，+mdmPm=0 （2）由 (1)+(2)得 (x1+ md1)P1+ (x2+ md2)P2++ (xm mdm)Pm=b令X1=(x1+ md1，x2+ md2，0)T X2=(x1 md1，x2 md2，0)T取m充分小,使得 xj177。0， 則 XX2均為可行解，但 X=+()X2， ∴ X是XX2連線上的點(diǎn)，故X非凸集頂點(diǎn)。 X非基可行解設(shè)X＝(x1,x2,…,xr,0,…,0)T不是可行域的頂點(diǎn)，因而可以找到可行域內(nèi)另外兩個(gè)不同點(diǎn)Y和Z，使得定理3 若線性規(guī)劃模型有最優(yōu)解，則一定存在一個(gè)基可行解為最優(yōu)解。 z1 ， z0 = zmax 179。若XX2仍不是頂點(diǎn)，可如此遞推，直至找出一個(gè)頂點(diǎn)為最優(yōu)解。定理3 若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)。 因X(0)不是頂點(diǎn)，所以它可以用D的頂點(diǎn)凸組合表示為：在所有的頂點(diǎn)中必然能找到某一個(gè)頂點(diǎn)X(r),使CX(r)是所有CX(i)中的最大者。 根據(jù)假設(shè)CX(0)是最大值。即目標(biāo)函數(shù)在頂點(diǎn)X(r)處也達(dá)到了最大值。有人認(rèn)為，求解線性規(guī)劃的單純形算法可與求解線性方程組的高斯消元法相媲美。 單純形法的要點(diǎn) 確定初始基可行解已知線性規(guī)劃問(wèn)題形如：注意：約束條件全為≤。,0, b1,b2,若非這種情況，則需要添加人工變量，將在后面討論。, xm0,0, 因?yàn)閄（0）是基可行解，所以滿足約束方程組：又因?yàn)镻1,P2,…,Pm是一組基向量，非基變量xj ( j≥m+1 )的系數(shù)列向量 Pj 可以用這組基向量線性表示：將上式乘以一個(gè)正數(shù)θ得到：上式與①式相加得：從而找到了滿足約束方程組的另一個(gè)解：只需要取注意：若某個(gè)基變量xi0=0，則允許θ=0 最優(yōu)性檢驗(yàn)和解的判別將基可行解X（0）和X（1）分別代入目標(biāo)函數(shù)中：又q 0，得到如下結(jié)論：(1) 若對(duì)所有j≥m+1，有sj ＜ 0 ，則z（1）＜ z （0） ，即z （0）為最優(yōu)函數(shù)值，X（0）為唯一最優(yōu)解；(2) 若對(duì)所有j ≥m+1 ，有sj ≤0，且存在某個(gè)非基變量的檢驗(yàn)數(shù)sk=0，則將Pk作為新的基向量得出新的基可行解X（1） ，滿足z（1） = z （0） ，故z（1） 也為最優(yōu)函數(shù)值，從而 X（1）也為最優(yōu)解，∴ X（0） 、X（1） 連線上所有點(diǎn)均為最優(yōu)解，因此該線性規(guī)劃模型具有無(wú)窮多最優(yōu)解；(3) 若存在某個(gè)sj ＞ 0，但對(duì)應(yīng)的第j列系數(shù)全非正，即aij≤0，則q不受限制，可以任意取值，故當(dāng) q174。時(shí)，有z（1） 174?！? 該線性規(guī)劃模型具有無(wú)界解。 單純形表和單純形法的基本步驟 為書(shū)寫(xiě)規(guī)范和便于計(jì)算，對(duì)單純形法的計(jì)算設(shè)計(jì)了一種專門(mén)的表格，稱為單純形表（見(jiàn)表15）。不難看出從表中可以方便的計(jì)算出每個(gè)非基變量的檢驗(yàn)數(shù)，即用變量的價(jià)值減去基價(jià)值與變量的系數(shù)乘積之和，即表15CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1nq1CB2xB2b2a21a22…a2j…a2nq2………………………CBnxBnbmam1am2…amj…amnqm檢驗(yàn)數(shù)sjs1s2…sj…sn每一次迭代對(duì)應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。（注意此處考慮的是有可行解的線性規(guī)劃問(wèn)題。②構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表。注意在有最優(yōu)解，即所有檢驗(yàn)數(shù)σj 163。④在大于0的檢驗(yàn)數(shù)中，若某個(gè)sk所對(duì)應(yīng)的系數(shù)列向量Pk′≤0，則此問(wèn)題是無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入下一步。建立新的單純形表，此時(shí)基變量中xk取代了xBl的位置。 上述這種利用單純形表求解線性規(guī)劃問(wèn)題的方法稱為單純形法（simplex method）。令非基變量x1=x2=0,得到基變量x3=12,x4=16,x5=15,從而得到初始基可行解X=(0,0,12,16,15)T，列出初始單純形表，如表17：表17cj23000CBBbX1X2X3X4X5θ0X3122210060X416400100X5150[5]0013σj23000注意變量x1,x2的 檢驗(yàn)數(shù)大于0，選擇正檢驗(yàn)數(shù)中最大的對(duì)應(yīng)變量x2為換入變量；依照比值的計(jì)算規(guī)則，只有x2的正系數(shù)才有對(duì)應(yīng)的比值，即故變量x5為換出變量，從而元素5為主元（用[]標(biāo)記），上述計(jì)算過(guò)程可直接在表中進(jìn)行。四、關(guān)于單純形法的補(bǔ)充說(shuō)明單純形法在實(shí)際應(yīng)用中非常有效，已被廣泛采用，但在理論上不是多項(xiàng)式時(shí)間算法，但這并不影響我們使用該方法解決實(shí)際中的相關(guān)問(wèn)題。 第四節(jié) 初始可行基的求法人工變量法在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。一、大M法 。于是該問(wèn)題新增加了兩個(gè)變量：x4和x5，稱為人工變量。一旦人工變量取值不為0，則目標(biāo)函數(shù)無(wú)法極大化。0 ，但存在非0的人工變量 ，則該模型無(wú)可行解。但是若利用計(jì)算機(jī)求解，只能用很大的數(shù)代替M,則容易使機(jī)器判斷出錯(cuò)，從而使大M法失效。二、兩階段法 兩階段法，顧名思義是將線性規(guī)劃問(wèn)題分成兩個(gè)階段來(lái)處理。為此，不考慮原問(wèn)題是否存在可行解，給原線性規(guī)劃問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)w（通常人工變量在w中的系數(shù)一般取為1）和要求w的最小值，然后用單純型法求解。進(jìn)入第二階段后，將第一階段得到的最終表去掉人工變量，并將目標(biāo)函數(shù)還原為原線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)（即修改最終表中的第一行和第一列），以此作為第二階段的初始表，繼續(xù)用單純形法求解。解：引入人工變量，轉(zhuǎn)化為：第一階段，求解線性規(guī)劃問(wèn)題：先標(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，因此第一階段問(wèn)題有唯一最優(yōu)解：結(jié)果表明已知問(wèn)題有可行解，進(jìn)入第二階段。原則上可以任取一個(gè)對(duì)應(yīng)的變量為換入變量，但通常會(huì)選其中一個(gè)下標(biāo)最小的作為換入變量； 出現(xiàn)若干比值大小相同且都是最小。當(dāng)發(fā)生退化現(xiàn)象時(shí)，從理論上講有可能出現(xiàn)計(jì)算過(guò)程的死循環(huán)，始終求不到最優(yōu)解。然而千千萬(wàn)萬(wàn)例實(shí)際應(yīng)用中從來(lái)沒(méi)遇見(jiàn)過(guò)出現(xiàn)死循環(huán)的問(wèn)題，所以在實(shí)際計(jì)算時(shí)一般不必理會(huì)此事，可選其中一個(gè)下標(biāo)最小的基變量為換出變量繼續(xù)計(jì)算即可。解：在圖解法中已看到本例有無(wú)界解，用單純形法求解時(shí)，先化為標(biāo)準(zhǔn)形式列單純形表如下Cj230CBBbX1X2X3θ0X316401σj230表中最大的正檢驗(yàn)數(shù)σ2=30，但x2的系數(shù)為0，使得θ不能被確定，從而z無(wú)限增大。 用單純形法求解下列問(wèn)題。故此題有無(wú)窮多最優(yōu)解。解：在圖解法中已看到本例無(wú)可行解，用單純形法求解時(shí)，先化為標(biāo)準(zhǔn)形式列單純形表如下cj2300MCBBbX1X2X3X4X5θ0X3122[2]1006MX514120117σj2+M2+2M0M03X26111/200MX5210111σj1M03/2MM0表中所有檢驗(yàn)數(shù)均非正,但人工變量x5不等于0，使得此題無(wú)可行解。針對(duì)不同類(lèi)型的線性規(guī)劃問(wèn)題，應(yīng)如何進(jìn)行廣義標(biāo)準(zhǔn)化，具體方法（以大M法為例）參見(jiàn)表1，表中xs表示松弛變量，xa表示人工變量：表1模型決策變量約束條件目標(biāo)函數(shù)特點(diǎn)個(gè) 數(shù)取 值右 端 項(xiàng)等式或不等式極大或極小新加變量系數(shù)兩個(gè)三個(gè)以上x(chóng)j≥0xj無(wú)約束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)過(guò)上述方法處理后可求出初始基可行解，列出初始單純形表，再用單純形法求解，對(duì)應(yīng)的步驟框圖如下圖：唯一最優(yōu)解 否 否否 是是是添加松弛變量、人工變量 列出初始單純形表計(jì)算各列檢驗(yàn)數(shù)бj所有бj163。建模時(shí)運(yùn)籌學(xué)學(xué)習(xí)的核心和精髓。當(dāng)然對(duì)實(shí)際經(jīng)濟(jì)問(wèn)題能給予深刻準(zhǔn)確的數(shù)學(xué)描述以及把數(shù)學(xué)上的定理算法給予確切合理的經(jīng)濟(jì)解釋，都不是容易的事情。⑴等待求解問(wèn)題的目標(biāo)能用某種效益指標(biāo)度量其大小，即能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)；⑵.存在著多種可采取的方案；⑶.要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些條件可用線性等式或不等式描述。（混合配料問(wèn)題） 某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。該廠應(yīng)如何安排生產(chǎn)使利潤(rùn)最大？產(chǎn)品名稱規(guī)格要求單價(jià)(元/kg）A原材料C不少于50%原材料H不超過(guò)25%50B原材料C不少于25%原材料P不超過(guò)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)則該問(wèn)題的數(shù)學(xué)模型為：用單純型法計(jì)算得結(jié)果:每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:C為100kg。H為50kg. 最大的總利潤(rùn)收入Z=500元/天.（合理下料問(wèn)題）現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米。下料方式毛坯1234需要根數(shù)32101000246200余料長(zhǎng)度（米）則該問(wèn)題的數(shù)學(xué)模型為：用單純型法計(jì)算得結(jié)果:注意：若考慮余料最少，則對(duì)應(yīng)模型為：用單純型法計(jì)算得結(jié)果:（投資項(xiàng)目組合問(wèn)題）興安公司有一筆30萬(wàn)元的資金，考慮今后三年內(nèi)用于下列項(xiàng)目的投資：三年內(nèi)每年年初均可投資，每年獲利為投資額的20%，其本利可一起用于下一年投資；只允許第一年初投入，于第二年末收回，本利合計(jì)為投資額的150%,但此類(lèi)投資限額不超過(guò)15萬(wàn)元；允許于第二年初投入，于第三年末收回，本利合計(jì)為投資額的160%，但限額投資20萬(wàn)元；允許于第三年初投入，年末收回，可獲利40%，但限額為10萬(wàn)元.試為該公司確立一個(gè)使第三年末本利和最大的投資組合方案，請(qǐng)建立這個(gè)問(wèn)題的線性規(guī)劃模型。本章小結(jié)本章討論了線性規(guī)劃問(wèn)題的數(shù)學(xué)模型，介紹了求解含有兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法，詳細(xì)分析了單純形法的基本原理及基本步驟，并介紹了單純形法的進(jìn)一步討論，同時(shí)對(duì)一些實(shí)際問(wèn)題建立了線性規(guī)劃問(wèn)題的數(shù)學(xué)模型。練習(xí)題