【正文】 , x5,按照上述方法將問題化為如下標(biāo)準(zhǔn)形式：二、 線性規(guī)劃的基可行解的概念 已知線性規(guī)劃的標(biāo)準(zhǔn)形式： ()A=(aij)為約束方程組的mn階系數(shù)矩陣(設(shè)nm)，則稱B是線性規(guī)劃問題的一個基矩陣（簡稱為基）。代入模型，顯然xq39。=xp,代入模型，顯然xp39。這樣增加的決策變量x4取非負(fù)值，加到原約束條件中把“≥”約束轉(zhuǎn)化為等式約束，故稱為剩余變量（也可稱為剩余變量）。=z，即轉(zhuǎn)化為2. 約束條件為不等式。第2節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)形式和解的性質(zhì) 線性規(guī)劃的標(biāo)準(zhǔn)形式\在不同情況下，歸結(jié)出來的線性規(guī)劃問題可能多種多樣，在目標(biāo)函數(shù)和約束條件上也可能各有不同。(4) 解題思路：先找出凸集的任一頂點，計算其目標(biāo)函數(shù)值。盡管圖解法只能解決含有兩個決策變量的線性規(guī)劃問題，但從它的解題思路和幾何直觀上得到了線性規(guī)劃問題的若干規(guī)律，對之后介紹求解一般線性規(guī)劃問題的代數(shù)方法——單純形法很有啟示：(1) 求解線性規(guī)劃問題時，解有四種情況：唯一最優(yōu)解、無窮多最優(yōu)解（也稱為多重最優(yōu)解）、無界解（也稱為有可行解但無最優(yōu)解）和無可行解。 用圖解法求解下列線性規(guī)劃問題。解 用圖解法求解，如圖14所示，該問題的可行域上方無邊界，目標(biāo)函數(shù)等值線沿著優(yōu)化方向可以無限延伸，使得目標(biāo)函數(shù)值無限增大。 用圖解法求解下列線性規(guī)劃問題。此時唯一切點即為最優(yōu)解，這個切點是凸五邊形的一個頂點，如圖12所示。圖解法的步驟是：先在平面直角坐標(biāo)系中畫出約束條件所確定的可行域；再對任意確定的z，畫出目標(biāo)函數(shù)所代表的一族直線（常稱為目標(biāo)函數(shù)等值線）；最后沿優(yōu)化方向平移目標(biāo)函數(shù)等值線，確定最優(yōu)解（如果有的話）。注意在實際意義中決策變量的取值一般為非負(fù)實數(shù)。于是線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成()一個線性規(guī)劃問題有解，是指能找出一組xj(j＝1,...,n)的值既滿足()中的約束條件，又滿足決策變量的取值要求，此時稱X=(x1,x2,...,xn)T為該問題的可行解。一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型有n個決策變量，分別用xj（j=1,2…,n）表示。通常用x1，x2，…，xn表示；（2）目標(biāo)函數(shù)，即問題要達到的目標(biāo)要求，表示為決策變量的函數(shù)。同理得到類似的不等式；。對于B、C設(shè)備也可列出類似的不等式：4 x1≤16；5 x2≤15。第一節(jié) 線性規(guī)劃的基本概念 線性規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃問題通常有兩大類型：一類是在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最大的經(jīng)濟效益（如產(chǎn)量最多或利潤最大等）；另一類是當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原材料、人工或時間等）去完成給定的任務(wù)或目標(biāo)。第1章 線性規(guī)劃與單純形法 .生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃論要解決的問題?，F(xiàn)各舉一例如下：常山機器廠生產(chǎn) I、II 兩型產(chǎn)品。該廠的目標(biāo)是在各種設(shè)備允許的情況下，使總的利潤收入z=2 x1+3 x2為最大。該飼料廠的目標(biāo)是在滿足動物生長需求的情況下，使總的費用為最小。通常用 z=f(x1，x2，…，xn)表示，按優(yōu)化目標(biāo)分別在這個函數(shù)前面加上max或min；（3）約束條件，即決策變量取值時受到各種可用資源的限制，通常表示為含決策變量的等式或不等式。目標(biāo)函數(shù)中變量系數(shù)用cj表示, 通常cj稱為價值系數(shù)。全部可行解的集合稱為可行域．特別的，能使目標(biāo)函數(shù)達到最優(yōu)的可行解稱為最優(yōu)解。在單純數(shù)學(xué)意義下也可以有決策變量取非正實數(shù)。 用圖解法求例1的最優(yōu)解。此問題有唯一最優(yōu)解當(dāng) x1=x2=3 時，Zmax = 15。 解 用圖解法求解，如圖13所示，沿優(yōu)化方向平移時目標(biāo)函數(shù)等值線與可行域在整個線段上相切，即該問題的最優(yōu)解為此線段上的所有點。此時問題有可行解但目標(biāo)函數(shù)值無界，故無最優(yōu)解，常稱之為無界解。解 用圖解法求解時該問題的可行域是空集，如圖15所示。(2) 若線性規(guī)劃問題的可行域不是空集，則可行域為凸集。再與周圍相鄰頂點的目標(biāo)函數(shù)值比較是否比這個值更優(yōu)。為了討論問題的方便，規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形式如下：（）標(biāo)準(zhǔn)形式的線性規(guī)劃問題中，目標(biāo)函數(shù)為求極大值（有些書上規(guī)定是求極小值），約束條件全為等式，約束條件右端常數(shù)全為非負(fù)值，決策變量的取值必須非負(fù)。當(dāng)約束條件為“≤”時，例如2 x1+2 x2≤12，可令x3=122 x12 x2,得2 x1+2 x2+x3=12,顯然x3≥0。松弛變量或剩余變量在實際問題中表示未被利用的資源數(shù)或短缺的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引入到模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。≥0.5. =xq39。、xq39。不失一般性，設(shè)基為將B中每個列向量即P1,P2,… ,Pm稱為基向量，與基向量Pj對應(yīng)的變量xj稱為基變量(常記為XB)，除基本量以外的其它變量稱為非基變量(常記為XN)?；尚薪?滿足變量非負(fù)取值的基解稱為基可行解(或基本可行解)。，列出全部基、基解、基可行解，并指出最優(yōu)解。設(shè)E是n維向量的集合，X1和X2是E的任意兩點，若X1和X2連線段上的點X=aX1+(1a)X2 (0≤a≤1)仍屬于集合E，則稱E為凸集。證明：設(shè) max z=CX st. AX=b X179。0，X2179。C，即C為凸集。,0)T，若X為基可行解，顯然，由基可行解定義可知x1, x2, X為基可行解若A的秩為m，則X的正分量的個數(shù)k163。,xk的系數(shù)列向量P1,P2,當(dāng)km時，則必定可再找出mk個列向量與P1,P2,定理2 線性規(guī)劃模型的基可行解對應(yīng)其可行域的頂點。,Pm線性相關(guān)，即有d1P1+d2P2++ (xm+ mdm)Pm=b由 (1)(2)得 (x1 md1)P1+ (x2 md2)P2+xm mdm ，0， mdj179。證明：設(shè) X0=(x10, x20, z2 ，∴ z1 = z2 = z0 ，即 X1 、 X2也為最優(yōu)解。 證明：設(shè)X(1)，X(2)，…， X(k)是可行域D的頂點，若X(0)不是頂點，且目標(biāo)函數(shù)在X(0)處達到最大值Z＊＝C X(0)。所以只有CX(0)= CX(r) 。一、單純形法的解題思路 因為線性規(guī)劃問題若有最優(yōu)解，則一定可以在基可行解中找到，所以用單純形法求解線性規(guī)劃的基本思想是：先找到一個初始基可行解，若不是最優(yōu)解，則設(shè)法轉(zhuǎn)換到另一個基可行解，并使目標(biāo)函數(shù)值不斷增大，直到找到最優(yōu)解為止（如果有的話）。,bm)T注意：用這個方法確定初始基可行解，必須保證約束條件全是“≤” 。, 0)T ，且前m個分量為正值。 +165。一個含有n個決策變量m個約束條件的標(biāo)準(zhǔn)線性規(guī)劃問題，對應(yīng)的單純形表中第一行稱為價值行，用Cj表示，列出每個決策變量在目標(biāo)函數(shù)中的系數(shù)；第二行稱為變量行，列出n個決策變量；最后一行稱為檢驗數(shù)行，列出每個決策變量的檢驗數(shù)（易見基變量的檢驗數(shù)為0）；第一列稱為基價值列，用CB表示，列出每個基變量在目標(biāo)函數(shù)中的系數(shù)；第二列稱為基列（或基變量列），用B或XB表示,列出m個基變量；第三列稱為基解列，用b表示，即每個基變量的取值；最后一列稱為比值列；而中心位置m行n列的矩陣為約束條件的系數(shù)矩陣，注意基變量對應(yīng)的系數(shù)矩陣是m階的單位矩陣。） ①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。⑥將aik′稱為主元素或主元，常用方括號[ ]標(biāo)記，利用主元進行迭代，即通過矩陣的初等行變換，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄浚粗髟猘ik′變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③ 步。利用初等行變換將[5]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表18）表18cj23000CBBbX1X2X3X4X5θ0X36[2]0102/530X4164001043X2301001/5σj20003/5注意表中x1為換入變量；依照比值的計算規(guī)則，只有x1的正系數(shù)才有對應(yīng)的比值，即故變量x3為換出變量，從而元素2為主元（用[]標(biāo)記），再將[2]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表19）表19cj23000CBBbX1X2X3X4X5θ2X13101/201/50X4400214/53X2301001/5σj00101/5表19中所有檢驗數(shù)均非正，得到最優(yōu)解X=(3,3,0,4,0)T,zmax=15,進一步由于非基變量的檢驗數(shù)全小于0，該問題是唯一最優(yōu)解。這種人為添加的變量稱為人工變量，由此構(gòu)成的可行基稱為人工基，這種用人工變量作橋梁的求解方法稱為人工變量法。對應(yīng)的約束方程組為：為使兩個方程組等價，常稱為罰因子（其中M為任意大的正數(shù)）。采用大M法求解線性規(guī)劃模型時，當(dāng)模型中各個系數(shù)與M的值非常接近或相差甚遠時，若用手工計算，不會出現(xiàn)問題。第一階段的作用是判斷原線性規(guī)劃問題是否存在可行解。當(dāng)任取一個對應(yīng)的變量為換出變量時，則下一張表中有基變量的值等于0，這種現(xiàn)象稱為退化。四、單純形法小結(jié)用最終單純形表判斷解的類型 用單純形法求解下列問題。解：在圖解法中已看到本例有無窮多最優(yōu)解，用單純形法求解時，先化為標(biāo)準(zhǔn)形式列單純形表如下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)解。通過以上各例，我們歸納出利用最終單純形表判斷線性規(guī)劃問題解的類型的方法如下：解的類型最終表的特征無可行解有非0的人工變量有可行解唯一最優(yōu)解無非0的人工變量，非基變量的檢驗數(shù)全為負(fù)數(shù)無窮多最優(yōu)解無非0的人工變量，非基變量的檢驗數(shù)全非正，且有某個非基變量的檢驗數(shù)為0，同時該變量對應(yīng)的系數(shù)列至少有一個正系數(shù)無界解無非0的人工變量，有某個非基變量的檢驗數(shù)為正數(shù)，但該變量對應(yīng)的系數(shù)列全為非正數(shù)能夠用單純形法求解的線性規(guī)劃問題應(yīng)首先化為標(biāo)準(zhǔn)形式，并可選擇一個單位矩陣作為基，常稱之為廣義標(biāo)準(zhǔn)形式。將經(jīng)濟管理領(lǐng)域的實際問題抽象為數(shù)學(xué)模型，這是一項極具創(chuàng)造性和技巧性的工作，既要求能熟練地掌握運用有關(guān)的數(shù)學(xué)知識，又要求對所研究經(jīng)濟對象的本質(zhì)有深刻的理解，同時還需要相關(guān)方面的專業(yè)人員的互相配合和通力合作。下面舉例說明如何將實際問題歸結(jié)為線性規(guī)劃問題的數(shù)學(xué)模型。P為50kg。解：用xij表示第i年初投放到第j個項目的資金數(shù)（注意只有6個決策變量x11,x12,x21,x23,x31,x34），則建立如下線性規(guī)劃模型：用單純形法求得：綜上投資組合方案如下：方案年初12341202031010單位：萬元第三年末本利和的最大值=58萬元。 ，并指出其中的基可行解和最優(yōu)解。 ，其中x4，x5，x6是松弛變量。112a2111表1x1x2x3x4x5x46(b)(c)(d)10x5113(e)01cjzj(a)1200表2x1x2x3x4x5x1(f)(g)211/20x54(h)(i)11/21cjzj07(j)(k