第一篇：?jiǎn)渭冃畏ê蛿M牛頓法

擬牛頓法(Quasi-Newton Methods)是求解非線性?xún)?yōu)化問(wèn)題最有效的方法之一，于20世紀(jì)50年代由美國(guó)Argonne國(guó)家實(shí)驗(yàn)室的物理學(xué)家W.C.Davidon所提出來(lái)。Davidon設(shè)計(jì)的這種算法在當(dāng)時(shí)看來(lái)是非線性?xún)?yōu)化領(lǐng)域最具創(chuàng)造性的發(fā)明之一。不久R.Fletcher和M.J.D.Powell證實(shí)了這種新的算法遠(yuǎn)比其他方法快速和可靠，使得非線性?xún)?yōu)化這門(mén)學(xué)科在一夜之間突飛猛進(jìn)。在之后的20年里，擬牛頓方法得到了蓬勃發(fā)展，出現(xiàn)了大量的變形公式以及數(shù)以百計(jì)的相關(guān)論文。

擬牛頓法和最速下降法(Steepest Descent Methods)一樣只要求每一步迭代時(shí)知道目標(biāo)函數(shù)的梯度。通過(guò)測(cè)量梯度的變化，構(gòu)造一個(gè)目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類(lèi)方法大大優(yōu)于最速下降法，尤其對(duì)于困難的問(wèn)題。另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時(shí)比牛頓法(Newton's Method)更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來(lái)解決無(wú)約束，約束，和大規(guī)模的優(yōu)化問(wèn)題。

擬牛頓法的基本思想如下。首先構(gòu)造目標(biāo)函數(shù)在當(dāng)前迭代$x_k$的二次模型：m_k(p)=f_k+g_k^T p+p^T B_k p/2，這里f_k=f(x_k)，g_k=▽f(x_k)，B_k是一個(gè)對(duì)稱(chēng)正定矩陣。于是我們?nèi)∵@個(gè)二次模型的最優(yōu)解p_k=-B_k^{-1} g_k作為搜索方向，并且得到新的迭代點(diǎn)x_{k+1}=x_k+a_k p_k，其中我們要求步長(zhǎng)a_k滿足Wolfe條件。這樣的迭代類(lèi)似與牛頓法，區(qū)別就在于用近似的Hesse矩陣B_k代替真實(shí)的Hesse矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣B_k的更新?，F(xiàn)在假設(shè)得到一個(gè)新的迭代x_{k+1}，并得到一個(gè)新的二次模型：m_{k+1}(p)=f_{k+1}+g_{k+1}^T p + p^T B_{k+1} p/2。我們盡可能地利用上一步的信息來(lái)選取B_{k+1}。具體地，我們要求g_{k+1}-g_k=a_k B_{k+1} p_k，從而得到B_{k+1}s_k=y_k，其中s_k=x_{k+1}-x_k，y_k=g_{k+1}-g_k。這個(gè)公式被稱(chēng)為割線方程。下面主要介紹這幾種方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

純形法，求解線性規(guī)劃問(wèn)題的通用方法。單純形是美國(guó)數(shù)學(xué)家G.B.丹齊克于1947年首先提出來(lái)的。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱(chēng)為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。根據(jù)單純形法的原理，在線性規(guī)劃問(wèn)題中，決策變量（控制變量）x1，x2，…x n的值稱(chēng)為一個(gè)解,滿足所有的約束條件的解稱(chēng)為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱(chēng)為最優(yōu)解。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問(wèn)題的目的就是要找出最優(yōu)解。

最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無(wú)窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒(méi)有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無(wú)限增大（或向負(fù)的方向無(wú)限增大）。

單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問(wèn)題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問(wèn)題無(wú)解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問(wèn)題的最優(yōu)解。⑤若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。

用單純形法求解線性規(guī)劃問(wèn)題所需的迭代次數(shù)主要取決于約束條件的個(gè)數(shù)。現(xiàn)在一般的線性規(guī)劃問(wèn)題都是應(yīng)用單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對(duì)于具有106個(gè)決策變量和104個(gè)約束條件的線性規(guī)劃問(wèn)題已能在計(jì)算機(jī)上解得

第二篇：?jiǎn)渭冃畏ɡ碚?/a>

單純形法

單純形法不用計(jì)算函數(shù)的導(dǎo)數(shù)，只需要計(jì)算目標(biāo)函數(shù)的函數(shù)值，因此計(jì)算比較簡(jiǎn)單，幾何概念也比較清晰，屬于直接法的無(wú)約束最優(yōu)化方法。所謂n維歐氏空間E中的單純形，是指在n維空間中由n?1個(gè)線性獨(dú)立的點(diǎn)構(gòu)成的簡(jiǎn)單圖形或凸多面體。

基本思想：根據(jù)問(wèn)題的維數(shù)n選取n?1個(gè)線性獨(dú)立的點(diǎn)，然后計(jì)算這n?1個(gè)點(diǎn)的函數(shù)值并進(jìn)行比較，確定其中的最大值的點(diǎn)及函數(shù)的下降方向，再設(shè)法找到一個(gè)新的好點(diǎn)替換函數(shù)值最大的點(diǎn)，從而構(gòu)成新的單純形。這個(gè)過(guò)程不斷進(jìn)行，新的單純形將向極小點(diǎn)收縮。經(jīng)過(guò)若干次迭代后，即可得到滿足收斂條件的極小點(diǎn)。

基本過(guò)程包括：反射、擴(kuò)張和壓縮。下面以二維問(wèn)題為例來(lái)說(shuō)明單純形法的求優(yōu)過(guò)程。設(shè)二維函數(shù)f(X)在平面上有線性獨(dú)立的三個(gè)點(diǎn)Xh，Xl，Xg，構(gòu)成單純形（三角形），計(jì)算這三個(gè)點(diǎn)的函數(shù)值，若

nf(Xh)?f(Xg)?f(Xl)

則說(shuō)明Xh是最差點(diǎn)，Xl是最好點(diǎn)，Xg為次差點(diǎn)，迭代應(yīng)該找出好的點(diǎn)Xr來(lái)替換最差點(diǎn)Xh，構(gòu)成新的單純形。Xr在Xh與除去最差點(diǎn)Xh以后所有頂點(diǎn)的形心點(diǎn)Xc連線的延長(zhǎng)線上進(jìn)行選取。

Xr?Xc??(Xc?Xh)

式中：?——反射系數(shù)，一般取??1。

這個(gè)步驟稱(chēng)為反射。通常，反射點(diǎn)Xr的取法是使Xr點(diǎn)Xr點(diǎn)稱(chēng)為最差點(diǎn)Xh的反射點(diǎn)，至Xc點(diǎn)的距離等于Xc點(diǎn)到Xh的距離。

反射點(diǎn)Xr對(duì)新單純形構(gòu)造的影響，有以下幾種情況：（1）擴(kuò)張

1若反射點(diǎn)的函數(shù)值f(Xr)小于最好點(diǎn)的函數(shù)值f(Xl)，即當(dāng) ○f(Xr)?f(Xl)

時(shí)，說(shuō)明所取的方向是正確的，可進(jìn)一步擴(kuò)大效果，繼續(xù)沿XhXr向前進(jìn)行擴(kuò)張，在更遠(yuǎn)處取一點(diǎn)Xe，并滿足 Xe?Xc??(Xr?Xc)

式中：?——擴(kuò)張系數(shù)，??1.2~2.0，一般取??2.0。

如果f(Xe)?f(Xl)，說(shuō)明擴(kuò)張有利，就用Xe代替最差點(diǎn)Xh，構(gòu)成新的單純形。否則，說(shuō)明擴(kuò)張不利，舍棄Xe，仍以Xr代替最差點(diǎn)Xh，構(gòu)成新的單純形。

2若f(Xr)?f(Xl)不成立，則不能進(jìn)行擴(kuò)張，此時(shí)如果 ○f(Xr)?f(Xg)

則用反射點(diǎn)Xr替換最差點(diǎn)Xh，構(gòu)成新的單純形。（2）壓縮

1若反射點(diǎn)的函數(shù)值f(Xr)小于最差點(diǎn)的函數(shù)值f(Xh)，但大于次差點(diǎn)的函數(shù)值○f(Xg)，即當(dāng)

f(Xg)?f(Xr)?f(Xh)

時(shí)，則表示Xr點(diǎn)走得太遠(yuǎn)，需縮回一些，即進(jìn)行壓縮，并且得到的壓縮點(diǎn)應(yīng)為

Xs?Xc??(Xr?Xc)

式中：?——壓縮系數(shù)，常取??0.5。這時(shí)若f(Xs)?f(Xh)

則用壓縮點(diǎn)Xs代替最差點(diǎn)Xh，構(gòu)成新的單純形。

2若反射點(diǎn)的函數(shù)值f(Xr)大于最差點(diǎn)的函數(shù)值f(Xh)，即當(dāng) ○f(Xr)?f(Xh)

時(shí)，應(yīng)當(dāng)壓縮更加多些，即將新點(diǎn)壓縮至Xh與Xc之間，這時(shí)所得的壓縮點(diǎn)應(yīng)為

Xs??Xc??(Xc?Xh)?Xc??(Xh?Xc)

如果f(Xs?)?f(Xh)，說(shuō)明不能沿Xh的反射方向搜索，應(yīng)進(jìn)行縮邊。（3）縮邊

使單純形向最好點(diǎn)進(jìn)行收縮，即使最好點(diǎn)Xl不動(dòng)，其余各頂點(diǎn)皆向Xl移近為原距離的一半。

Xi?Xi?Xl

i?0,1,?,n 2從以上各步得到新的單純形后，再重復(fù)開(kāi)始各步，逐漸縮小單純形直至滿足精度要求為止。

初始單純形的形成：

構(gòu)成單純形的頂點(diǎn)應(yīng)是線性獨(dú)立的，否則，如二維問(wèn)題，三個(gè)點(diǎn)在一條直線上，就變成二維問(wèn)題了，即在一條直線上找極小點(diǎn)的問(wèn)題，稱(chēng)為退化。為防止退化，一般取成等邊三角形，因?yàn)樗侵荛L(zhǎng)一定前提下包圍面積最大的布點(diǎn)方式。

把二維等邊三角形推廣到n維的情況是n?1個(gè)點(diǎn)中任兩個(gè)點(diǎn)的距離都相等，這種單純形就稱(chēng)為正規(guī)單純形。選取正規(guī)單純形作初始單純形的方法如下：

給定一個(gè)初始點(diǎn)X0?[x1,x2,?,xn]T，其余n個(gè)點(diǎn)可取為：

X1?[x1?p,x2?q,x3?q?,xn?q]T

??

Xn?[x1?q,x2?q,x3?q?,xn?p]T

即第i個(gè)頂點(diǎn)的第i個(gè)坐標(biāo)分量比初始點(diǎn)增加p，其他分量增加q。設(shè)正規(guī)單純形任意兩頂點(diǎn)的距離等于c，這時(shí)p，q的公式推導(dǎo)如下。對(duì)于點(diǎn)X2和X1，有X2?X1?c即

(x1?q?x1?p)2?(x2?p?x2?q)2?(x3?q?x3?q)2???(xn?q?xn?q)2?c

2化簡(jiǎn)得

(q?p)2?(p?q)2?2(p?q)2?c2

對(duì)于X1和X0，有X1?X0?c，即

(x1?p?x1)2?(x2?q?x2)2?(x3?q?x3)2???(xn?q?xn)2?c2

化簡(jiǎn)得

p2?(n?1)q2?c2

聯(lián)立求解得 p?(n?1?n?1)c

n2(n?1?1)c

n2q?初始單純形也可以采用下面的方法：設(shè)目標(biāo)函數(shù)f(X)為n維向量，因此單純形應(yīng)有n?1個(gè)頂點(diǎn)X1，X2，?，Xn?1。構(gòu)造單純形時(shí)，現(xiàn)在n維空間中選取初始點(diǎn)X1(0)（盡量靠近最優(yōu)點(diǎn)），從X1(0)出發(fā)沿各坐標(biāo)軸方向ei、以步長(zhǎng)h找到其余n個(gè)頂點(diǎn)X(0)j（j?2，3，…，n?1）：

(0)X(0)?Xj1?hei

式中：ei——第i個(gè)坐標(biāo)軸的單位向量；

h——步長(zhǎng)，一般取值范圍為0.5~15.0，接近最優(yōu)點(diǎn)時(shí)要減小。構(gòu)成初始單純形的步長(zhǎng)可取1.6~1.7。

構(gòu)成初始單純形后，可按以下步驟進(jìn)行：

(k)(k)（1）計(jì)算各頂點(diǎn)的函數(shù)值并進(jìn)行比較，找出最好點(diǎn)Xl(k)，最差點(diǎn)Xh，次差點(diǎn)Xg，(k)(k)(k)以及除最差點(diǎn)外其它各點(diǎn)的形心Xn?2。求Xh對(duì)形心點(diǎn)Xn?2的反射點(diǎn)：

(k)(k)(k)(k)Xn?3?Xn?2??(Xn?2?Xh)

(k)(k)(k)(k)（2）比較Xn，如果反射點(diǎn)Xn還好，即進(jìn)行擴(kuò)張，得擴(kuò)張點(diǎn)?3和Xl?3比最好點(diǎn)Xl為：

(k)(k)(k)(k)Xn?4?Xn?2??(Xn?3?Xn?2)

(k)(k)(k)(k)(k)得到擴(kuò)張點(diǎn)Xn，否則?4后，若f(Xn?4)?f(Xl)，用Xn?4代替Xh，并轉(zhuǎn)步驟（5）(k)(k)用Xn代替。X?3h后轉(zhuǎn)入步驟（5）(k)(k)若f(Xn?3)?f(Xl)，即反射點(diǎn)比最好點(diǎn)差，則轉(zhuǎn)下一步。

(k)(k)（3）將反射點(diǎn)Xn?3與次差點(diǎn)Xg比較，如果f(Xn?3)?f(Xg)，則用Xn?3代替最(k)(k)(k)差點(diǎn)Xh，并轉(zhuǎn)步驟（5）；若f(Xg)?f(Xn?3)?f(Xh)，則用Xn代替X?3h后進(jìn)行

(k)(k)(k)(k)(k)(k)壓縮，否則直接進(jìn)行壓縮，得壓縮點(diǎn)為：(k)(k)(k)(k)Xn?5?Xn?2??(Xh?Xn?2)

(k)(k)(k)(k)(k)（4）求得壓縮點(diǎn)Xn后與最差點(diǎn)比較，若，則用Xf(X)?f(X)X?5hn?5hn?5代替(k)以后轉(zhuǎn)下一步；否則使單純形向最好點(diǎn)Xl(k)收縮，收縮后的單純形頂點(diǎn)為： XhX(jk)?Xl(k)?0.5(X(jk)?Xl(k))

j?1，2，…，n?1

然后轉(zhuǎn)下一步。

（5）進(jìn)行收斂性檢驗(yàn)。若

?1n?12?(k)(k)??f(X)?f(X)??jn?2???? ??n?1j?1?則停止迭代并輸出Xl(k)及f(Xl(k))，否則使k?k?1后轉(zhuǎn)第1步。式中?為任意的小(k)數(shù)，Xn?2為形心。

12例

試用單純形法求解目標(biāo)函數(shù)f(X)?4(x1?5)2?(x2?6)2的極小值。

Function f=fun(x)syms

x1

x2

f = 4*(x1-5)^2+(x2-6)^2;clear

x1= 0 x2= 0 z=0 e= [1;1] h=1.6 X0=[x1;x2] X1=X0 + h* e X2=X0 + h*e X3=X0 + h*e

第三篇：?jiǎn)渭冃畏ňC述

單純形法綜述

zy1415104-曹文亮

單純形法是1947年由George Bernard Dantzing(1914-2005)創(chuàng)建的，單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃問(wèn)題的誕生。線性規(guī)劃問(wèn)題是研究在線性約束條件下，求線性函數(shù)的極值問(wèn)題。然而，對(duì)這類(lèi)極值問(wèn)題，經(jīng)典的極值理論是無(wú)能為力的，只有單純形法才能有效解決這類(lèi)極值問(wèn)題的求解。線性規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)重要分支，也是最早形成的一個(gè)分支，線性規(guī)劃的理論與算法均非常成熟，在實(shí)際問(wèn)題和生產(chǎn)生活中的應(yīng)用非常廣泛；線性規(guī)劃問(wèn)題的誕生標(biāo)志著一個(gè)新的應(yīng)用數(shù)學(xué)分支——數(shù)學(xué)規(guī)劃時(shí)代的到來(lái)。過(guò)去的60年中，數(shù)學(xué)規(guī)劃已經(jīng)成為一門(mén)成熟的學(xué)科。其理論與方法被應(yīng)用到經(jīng)濟(jì)、金融、軍事等各個(gè)領(lǐng)域。數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)，其他重要分支的很多問(wèn)題是在線性規(guī)劃理論與算法的基礎(chǔ)上建立起來(lái)的，同時(shí)也是利用線性規(guī)劃的理論來(lái)解決和處理的。由此可見(jiàn)，線性規(guī)劃問(wèn)題在整個(gè)數(shù)學(xué)規(guī)劃和應(yīng)用數(shù)學(xué)領(lǐng)域中占有重要地位。因此，研究單純形法的產(chǎn)生與發(fā)展對(duì)于認(rèn)識(shí)整個(gè)數(shù)學(xué)規(guī)劃的發(fā)展有重大意義。

單純形法是從某一基可行解出發(fā)，連續(xù)地尋找相鄰的基可行解，直到達(dá)到最優(yōu)的迭代過(guò)程，其實(shí)質(zhì)是解線性方程組。

概述：

根據(jù)單純形法的原理，在線性規(guī)劃問(wèn)題中，決策變量（控制變量）x1，x2，…x n的值稱(chēng)為一個(gè)解,滿足所有的約束條件的解稱(chēng)為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱(chēng)為最優(yōu)解。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問(wèn)題的目的就是要找出最優(yōu)解。最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無(wú)窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒(méi)有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無(wú)限增大（或向負(fù)的方向無(wú)限增大）。

無(wú)最優(yōu)解與無(wú)可行解是兩個(gè)不同的概念。無(wú)可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問(wèn)題的可行域?yàn)榭占?無(wú)最優(yōu)解則是指線性規(guī)劃問(wèn)題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮?。o(wú)最優(yōu)解也稱(chēng)為無(wú)限最優(yōu)解，或無(wú)界解。

無(wú)最優(yōu)解判別定理：在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。

無(wú)窮多最優(yōu)解判別原理：若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。

退化與循環(huán)：如果在一個(gè)基本可行解的基變量中至少有一個(gè)分量為零，則稱(chēng)此基本可行解是退化的基本可行解。產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí)，有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值θ，那么在下次迭代中就會(huì)出現(xiàn)一個(gè)甚至多個(gè)基變量等于零。

退化可能出現(xiàn)以下情況：

① 進(jìn)行進(jìn)基、出基變換后，雖然改變了基，但沒(méi)有改變基本可行解（極點(diǎn)），目標(biāo)函數(shù)當(dāng)然也不會(huì)改進(jìn)。進(jìn)行若干次基變換后，才脫離退化基本可行解（極點(diǎn)），進(jìn)入其他基本可行解（極點(diǎn)）。這種情況會(huì)增加迭代次數(shù)，使單純形法收斂的速度減慢。

② 在特殊情況下，退化會(huì)出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形迭代將永遠(yuǎn)停留在同一極點(diǎn)上，因而無(wú)法求得最優(yōu)解。事實(shí)上，已經(jīng)有人給出了循環(huán)的例子。

單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問(wèn)題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問(wèn)題無(wú)解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問(wèn)題的最優(yōu)解。⑤若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。

用單純形法求解線性規(guī)劃問(wèn)題所需的迭代次數(shù)主要取決于約束條件的個(gè)數(shù)?，F(xiàn)在一般的線性規(guī)劃問(wèn)題都是應(yīng)用單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對(duì)于具有106個(gè)決策變量和104個(gè)約束條件的線性規(guī)劃問(wèn)題已能在計(jì)算機(jī)上解得。

求解步驟：

（1）確定初始基可行解

① 從線性規(guī)劃標(biāo)準(zhǔn)形的系數(shù)矩陣中能直接找出m個(gè)線性獨(dú)立的單位向量；

② 對(duì)約束條件全為“<=”連接的LP，化為標(biāo)準(zhǔn)形，左端添加松弛變量后即形成一個(gè)單位子矩陣；

③ 約束條件中含有“<=”或“=”連接的方程，在插入剩余變量后找不到單位矩陣，則必須采用“人造基”法，也稱(chēng)“人工變量”法。

（2）最優(yōu)性檢驗(yàn)及解的判別準(zhǔn)則

① 最優(yōu)性判定準(zhǔn)則 ② 多重最優(yōu)解判定準(zhǔn)則 ③ 無(wú)界最優(yōu)解判定準(zhǔn)則（3）換基迭代

① 確定換入變量 ② 確定換出變量 ③ 樞運(yùn)算（旋轉(zhuǎn)運(yùn)算）

單純形法-正文：

根據(jù)單純形法的原理，在線性規(guī)劃問(wèn)題中，決策變量（控制變量）x1，x2，…x n的值稱(chēng)為一個(gè)解,滿足所有的約束條件的解稱(chēng)為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱(chēng)為最優(yōu)解。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問(wèn)題的目的就是要找出最優(yōu)解。

可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無(wú)窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒(méi)有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無(wú)限增大（或向負(fù)的方向無(wú)限增大）。

要縮小對(duì)最優(yōu)解的搜索范圍，就必須認(rèn)識(shí)最優(yōu)解的一般性質(zhì)，最優(yōu)解如果存在的話，則它必然處于可行區(qū)域的邊界上。

任何一項(xiàng)約束條件的邊界方程是用“＝”號(hào)來(lái)替換該約束條件中的“≤”或“≥”號(hào)而得到的。每一個(gè)邊界方程確定一個(gè)超平面。因此，可行區(qū)域的邊界是由那些滿足一個(gè)或同時(shí)滿足幾個(gè)邊界方程（即處在作為邊界的一個(gè)或幾個(gè)超平面上）的可行解所組成，而且最優(yōu)解必在其中。最優(yōu)解不僅是在可行區(qū)域的邊界上，而且也在這個(gè)區(qū)域的一個(gè)隅角上。一個(gè)可行解，如果不處在由另兩個(gè)可行解連接起來(lái)的任何線段上，它就是一個(gè)角點(diǎn)可行解。如果連接兩個(gè)角點(diǎn)可行解的線段處在可行區(qū)域的邊界上，這兩個(gè)角點(diǎn)可行解就稱(chēng)為相鄰的角點(diǎn)可行解。角點(diǎn)可行解具有下列三個(gè)重要性質(zhì)：①如果存在著一個(gè)最優(yōu)解，那么它必定是角點(diǎn)可行解。如果存在有多個(gè)最優(yōu)解，那么至少有兩個(gè)最優(yōu)解必定是相鄰的角點(diǎn)可行解。②只存在有限個(gè)數(shù)的角點(diǎn)可行解。③如果一個(gè)角點(diǎn)可行解按目標(biāo)函數(shù)值來(lái)衡量時(shí)比其所有的相鄰角點(diǎn)可行解更好一些，那它就比所有其他角點(diǎn)可行解都更好，也就是最優(yōu)解。

上述這些性質(zhì)構(gòu)成單純形法的原理基礎(chǔ)。最后一個(gè)性質(zhì)的重要性在于它為一個(gè)角點(diǎn)可行解是否是最優(yōu)解提供了一種簡(jiǎn)便的檢驗(yàn)標(biāo)準(zhǔn)，因而毋需列舉所有的可行解。單純形法正是利用了這個(gè)性質(zhì)，只要檢查少數(shù)的角點(diǎn)可行解，并且一旦這個(gè)最優(yōu)性檢驗(yàn)獲得通過(guò)就可立即停止運(yùn)算。

單純形法的運(yùn)算步驟可歸結(jié)為：①起始步驟──在一個(gè)角點(diǎn)可行解上開(kāi)始。②迭代步驟──移動(dòng)至一個(gè)更好一些的相鄰角點(diǎn)可行解（根據(jù)需要反復(fù)進(jìn)行這一步驟）。③停止法則──在當(dāng)前角點(diǎn)可行解比所有相鄰角點(diǎn)可行解都更好些時(shí)停止。當(dāng)前角點(diǎn)可行解就是一個(gè)最優(yōu)解。

單純形法的優(yōu)點(diǎn)及其成功之處在于它只需要較少的有限次數(shù)的迭代，即可找到最優(yōu)解。

改進(jìn)單純形法：

原單純形法不是很經(jīng)濟(jì)的算法。1953年美國(guó)數(shù)學(xué)家G.B.丹齊克為了改進(jìn)單純形法每次迭代中積累起來(lái)的進(jìn)位誤差，提出改進(jìn)單純形法。其基本步驟和單純形法大致相同，主要區(qū)別是在逐次迭代中不再以高斯消去法為基礎(chǔ)，而是由舊基陣的逆去直接計(jì)算新基陣的逆，再由此確定檢驗(yàn)數(shù)。這樣做可以減少迭代中的累積誤差，提高計(jì)算精度，同時(shí)也減少了在計(jì)算機(jī)上的存儲(chǔ)量。

對(duì)偶單純形法：

（Dual Simplex Method）1954年美國(guó)數(shù)學(xué)家C.萊姆基提出對(duì)偶單純形法。單純形法是從原始問(wèn)題的一個(gè)可行解通過(guò)迭代轉(zhuǎn)到另一個(gè)可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對(duì)偶單純形法則是從滿足對(duì)偶可行性條件出發(fā)通過(guò)迭代逐步搜索原始問(wèn)題的最優(yōu)解。在迭代過(guò)程中始終保持基解的對(duì)偶可行性，而使不可行性逐步消失。設(shè)原始問(wèn)題為min{cx|Ax=b，x≥0}，則其對(duì)偶問(wèn)題（Dual Problem）為 max{yb|yA≤c}。當(dāng)原始問(wèn)題的一個(gè)基解滿足最優(yōu)性條件時(shí),其檢驗(yàn)數(shù)cBB-1A-c≤0。即知y=cBB-1（稱(chēng)為單純形算子）為對(duì)偶問(wèn)題的可行解。所謂滿足對(duì)偶可行性，即指其檢驗(yàn)數(shù)滿足最優(yōu)性條件。因此在保持對(duì)偶可行性的前提下，一當(dāng)基解成為可行解時(shí)，便也就是最優(yōu)解。

對(duì)偶單純形法的基本原則：在保持對(duì)偶可行的前提下進(jìn)行基變換——每一次迭代過(guò)程中取出基變量中的一個(gè)負(fù)分量作為換出變量去替換某個(gè)非基變量（作為換入變量），使原始問(wèn)題的非可行解向可行解靠近。

第四篇：?jiǎn)渭冃畏╩atlab程序

算法實(shí)現(xiàn)與分析

算法1．單純形法 具體算例：

minz=?3x1+x2+2x3 3x1+2x2?3x3=6 x1?2x2+x3+x5=4

x1,x2,x3≥0標(biāo)準(zhǔn)化后：

min z=?3x1+x2+2x3+Mx4+Mx5

3x1+2x2?3x3+x4=6 x1?2x2+x3+x5=4

x1,x2,x3,x4,x5≥0用單純形法求解，程序如下： clear clc

M=1000000;

A=[3,2,-3,1,0;1,-2,1,0,1];%系數(shù)矩陣 C=[-3,1,2,M,M,0];%價(jià)值矩陣 B=[6;4];Xt=[4 5];

for i=1:length(C)-1 D=0;

for j=1:length(Xt)

D=D+A(j,i)*C(Xt(j));

end

xi(i)=C(i)-D;end s=[];

for i=1:length(xi)

if xi(i)<0 s=[s,i];

end end

f=length(s);h=1;

while(f)

for k=1:length(s)j=1;A x=[];

for i=1:length(Xt)

if A(i,s(k))>0 x(j)=i;j=j+1;

end end x

if(length(x)+1==1)break;end y=1 x

for i=1:length(x)

if B(x(i))/A(x(i),s(k))

end end y=x(y);end

y1=Xt(y);%??3?±?á? s k

aa=A(y,s(k))%s(k)?a??è?±?á? A(y,:)=A(y,:)./aa;B(y,:)=B(y,:)./aa;z=[];

for i=1:length(Xt)z=[z,i];end

z z(y)=[];z Xt

for i=1:length(z);yz=-A(z(i),s(k))

A(z(i),:)=A(z(i),:)+A(y,:).*yz B(z(i))B(y)yz

B(z(i))=B(z(i))+B(y).*yz end

for i=1:length(Xt)

if Xt(i)==y1 Xt(i)=s(k);break

end end Xt

disp('×a??oó')A=A B=B AB=[A,B];

for i=1:length(C)D=0;

for j=1:length(Xt)D=D+AB(j,i)*C(Xt(j));

end

xi(i)=C(i)-D;

end xi s=[];

for i=1:length(xi)-1

if xi(i)<0 s=[s,i];

end

end s

vpa([A,B;C]);f=length(s);h=h+1;

if h==5

break

end end

-xi(length(xi))

第五篇：?jiǎn)渭冃畏ㄕn程論文

最優(yōu)化方法課程論文

題目：?jiǎn)渭冃畏ǖ陌l(fā)展及其應(yīng)用系別：理學(xué)院專(zhuān)業(yè)：信息與計(jì)算科學(xué)姓名：班級(jí)：信息

101班

單純形法的發(fā)展及其應(yīng)用

一． 單純形法簡(jiǎn)介：

單純形法，求解線性規(guī)劃問(wèn)題的通用方法。單純形是美國(guó)數(shù)學(xué)家G.B.丹齊克于1947年首先提出來(lái)的。它的理論根據(jù)是：線性規(guī)劃問(wèn)題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱(chēng)為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。

二． 單純形法在線性規(guī)劃中的應(yīng)用 1.單純形法解線性規(guī)劃問(wèn)題

在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這些問(wèn)題，如生產(chǎn)計(jì)劃問(wèn)題，即如何合理利用有限的人、財(cái)、物等資源，以便得到最好的經(jīng)濟(jì)效果；材料利用問(wèn)題，即如何下料使用材最少；配料問(wèn)題，即在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)；勞動(dòng)力安排問(wèn)題，即如何用最少的勞動(dòng)力來(lái)滿足工作的需要；運(yùn)輸問(wèn)題，即如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最??；投資問(wèn)題，即從投資項(xiàng)目中選取方案，使投資回報(bào)最大等等。對(duì)于這些問(wèn)題，都能建立相應(yīng)的線性規(guī)劃模型。事實(shí)上，線性規(guī)劃就是利用數(shù)學(xué)為工具，來(lái)研究在一定條件下，如何實(shí)現(xiàn)目標(biāo)最優(yōu)化。單純形法是求解線性規(guī)劃問(wèn)題的通用方法。

(1)單純形法解線性規(guī)劃問(wèn)題的理論根據(jù)是：

線性規(guī)劃問(wèn)題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱(chēng)為基本可行解。

(2)單純形法的基本思想是：

先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。

(3)單純形法的一般解題步驟可歸納如下：

①把線性規(guī)劃問(wèn)題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問(wèn)題無(wú)解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問(wèn)題的最優(yōu)解。⑤若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。(4)概述

根據(jù)單純形法的原理，在線性規(guī)劃問(wèn)題中，決策變量（控制變量）x1，x2，…x n的值稱(chēng)為一個(gè)解,滿足所有的約束條件的解稱(chēng)為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱(chēng)為最優(yōu)解。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問(wèn)題的目的就是要找出最優(yōu)解。

最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無(wú)窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒(méi)有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無(wú)限增大（或向負(fù)的方向無(wú)限增大）。

單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問(wèn)題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問(wèn)題無(wú)解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問(wèn)題的最優(yōu)解。⑤若迭代過(guò)程中發(fā)現(xiàn)問(wèn)題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。

用單純形法求解線性規(guī)劃問(wèn)題所需的迭代次數(shù)主要取決于約束條件的個(gè)數(shù)?，F(xiàn)在一般的線性規(guī)劃問(wèn)題都是應(yīng)用單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對(duì)于具有10^6個(gè)決策變量和10^4個(gè)約束條件的線性規(guī)劃問(wèn)題已能在計(jì)算機(jī)上解得。

2.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化

使用單純形法求解線性規(guī)劃時(shí)，首先要化問(wèn)題為標(biāo)準(zhǔn)形式 所謂標(biāo)準(zhǔn)形式是指下列形式：

maxz??cj?1njxj

?n??aijxj?bi(i?1,?,m)s?t??j?1

?x?0(j?1,2,?,n)?j當(dāng)實(shí)際模型非標(biāo)準(zhǔn)形式時(shí)，可以通過(guò)以下變換化為標(biāo)準(zhǔn)形式： ①當(dāng)目標(biāo)函數(shù)為minz??cjxj時(shí)，可令Z′=-Z，而將其寫(xiě)成為

j?1nminz????cjxj

j?1n求得最終解時(shí)，再求逆變換Z=-Z′即可。

②當(dāng)s·t·中存在ai1x1?ai2x2???ainxn?bi形式的約束條件時(shí)，可引進(jìn)變量

?xn?1?bi?(ai1x1?ai2x2???ainxn)??xn?1?0便寫(xiě)原條件成為

?ai1x1?ai2x2???ainxn?xn?1?bi ?x?0?n?1其中的xn+1稱(chēng)為松馳變量，其作用是化不等式約束為等式約束。同理，若該約束不是用“≤”號(hào)連接，而是用“≥”連接，則可引進(jìn)松馳變量

?xn?1?(ai1x1?ai2x2???ainxn)?bi ??xn?1?0使原條件寫(xiě)成

?ai1x1???ainxn?xn?1?bi ??xn?1?0

3.單純形法迭代原理（1）確定初始可行解

① 當(dāng)線性規(guī)劃問(wèn)題的所有約束條件均為≤號(hào)時(shí)，松弛變量對(duì)應(yīng)的系數(shù)矩陣即為單位矩陣，以松弛變量為基變量可確定基可行解。

② 對(duì)約束條件含≥號(hào)或=號(hào)時(shí)，可構(gòu)造人工基，人為產(chǎn)生一個(gè)m×m單位矩陣用大M法或兩階段法獲得初始基可行解。

（2）最優(yōu)性檢驗(yàn)與解的判別（目標(biāo)函數(shù)極大型）

① 當(dāng)所有變量對(duì)應(yīng)的檢驗(yàn)數(shù)均非正時(shí)，現(xiàn)有的基可行解即為最優(yōu)解。若存在某個(gè)非基變量的檢驗(yàn)數(shù)為零時(shí)，線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解；當(dāng)所有非基變量的檢驗(yàn)數(shù)均嚴(yán)格小于零時(shí)，線性規(guī)劃問(wèn)題具有唯一最優(yōu)解。② 若存在某個(gè)非基變量的檢驗(yàn)數(shù)大于零，而該非基變量對(duì)應(yīng)的系數(shù)均非正，則該線性規(guī)劃問(wèn)題具有無(wú)界解（無(wú)最優(yōu)解）。③ 當(dāng)存在某些非基變量的檢驗(yàn)數(shù)大于零，需要找一個(gè)新的基可行解，基要進(jìn)行基變換。

4.確定初始可行解

確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定，為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣Ａ中前m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，?Ｐm）為基變量x1，x2，?xm的系數(shù)列向量構(gòu)成的可行基，Ｎ=(Ｐm+1，Pm+2，?Pn)為非基變量xm+1，xm+2，?xn的系數(shù)列向量構(gòu)成的矩陣。

所以約束方程AX=b就可以表示為AX=(BN)??XB??=BXB+NXN=b ?XN?用可行基Ｂ的逆陣Ｂ-1左乘等式兩端，再通過(guò)移項(xiàng)可推得：XB=B-1b-B-1NXN

若令所有非基變量XN=0，則基變量XB=B-1b

?B?1b?由此可得初始的基本可行解X=??

?0?

5.最優(yōu)性檢驗(yàn)

?B?1b?假如已求得一個(gè)基本可行解X=?將這一基本可行解代入目?，?0??B?1b?-1標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值Z=CX=(CBCN)??=CBBb

?0?其中CB=(c1,c2,cm), CN=(cm+1,cm+2,cn)分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。

要判定Z=CBB-1b是否已經(jīng)達(dá)到最大值，只需將XB=B-1b-B-1NXN代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量表示，即：

?X?Z=CX=(CBCN)?B??XN?=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

CBB-1b+σNXN?CBB-1b+(σm+1,σm+1,?xm+1???xm+2? σn)?????x?n?其中?N=CN-CBB-1N=(?m+1,?m+1,?n)稱(chēng)為非基變量ＸN的檢驗(yàn)向量，它的各個(gè)分量稱(chēng)為檢驗(yàn)數(shù)。若σN的每一個(gè)檢驗(yàn)數(shù)均小于等于0，即σN≤0，那么現(xiàn)在的基本可行解就是最優(yōu)解。

6.解的判別

定理1：最優(yōu)解判別定理

對(duì)于線性規(guī)劃問(wèn)題maxZ=CX,D=?X?Rn/AX=b,X?0?，若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量?N=CN-CBB-1N?0，則這個(gè)基本可行解就是最優(yōu)解。

定理2：無(wú)窮多最優(yōu)解判別定理

?B?1b?若X=??是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量?0??N=CN-CBB-1N?0，其中存在一個(gè)檢驗(yàn)數(shù)σm+k=0，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。定理3：無(wú)最優(yōu)解判別定理

?B?1b?若X=??是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)?m+k?0，但是?0?B-1Pm+k?0，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。

7.基本可行解的改進(jìn)

如果現(xiàn)行的基本可行解Ｘ不是最優(yōu)解，即在檢驗(yàn)向量?N=CN-CBB-1N中存在正的檢驗(yàn)數(shù)，則需在原基本可行解Ｘ的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：

（1）先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值）。

（2）再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。

?xm+1???xm+2?σn)?????x?n?由此可得一個(gè)新的基本可行解，由Z?CBB-1b+(σm+1,σm+1,可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。

8.換入變量的確定--最大增加原則

把基檢驗(yàn)數(shù)大于0的非基變量定為入基變量。若有兩個(gè)以上的σj＞0，則選其中的σj最大者的非基變量為入基變量。

從最優(yōu)解判別定理知道，當(dāng)某個(gè)σj＞0時(shí)，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱(chēng)之為入基變量）。若有兩個(gè)以上的σj＞0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的σj最大者的非基變量為入基變量。

9.換出變量的確定--最小比值原則

把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。

即若

?b?bxk?min?i|aik?0??l?aik?alk

則應(yīng)令xl出基。其中bi是目前解的基變量取值，aik是進(jìn)基變量xk所在列的各個(gè)系數(shù)分量，要求僅對(duì)正分量做比，（這由前述作法可知，若aik≤0，則對(duì)應(yīng)的xi不會(huì)因xk的增加減值而成為出基變量）。

10.兩階段法

用大M法求解含人工變量的LP時(shí)，用手工計(jì)算不會(huì)碰到麻煩，但用電子計(jì)算機(jī)求解時(shí)，對(duì)M就只能在計(jì)算機(jī)內(nèi)輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字，這就可能造成一種計(jì)算上的誤差，為克服這個(gè)困難，對(duì)添加人工變量后的LP分兩個(gè)階段來(lái)計(jì)算，稱(chēng)為兩階段法。

第一階段：不考慮原問(wèn)題是否存在基可行解，給原LP加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)Minw,然后用單純形法求解，若得w=0，說(shuō)明原LP存在基可行解，可進(jìn)行第二階段計(jì)算，否則，停止計(jì)算。

第二階段：將第一階段計(jì)算得到的最終單純形表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換成原LP的目標(biāo)函數(shù)，作為第二階段計(jì)算的初始表。然后按照前面的方法進(jìn)行計(jì)算。

11.大M法

大M法首先將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。

為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-Ｍ。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。

以后的計(jì)算與單純形表解法相同，Ｍ只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問(wèn)題的初始基本可行解。

三． 結(jié)論 單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃的誕生。單純形法的創(chuàng)建統(tǒng)一了以往運(yùn)輸問(wèn)題和營(yíng)養(yǎng)問(wèn)題等的算法，同時(shí)推進(jìn)線性規(guī)劃理論的發(fā)展。反過(guò)來(lái)，理論的發(fā)展也刺激算法的更新。線性規(guī)劃在這樣理論與算法相互促進(jìn)和相互作用中發(fā)展。單純形法有效地提升了數(shù)學(xué)規(guī)劃的應(yīng)用。很多重大理論誕生之初遭到人們的質(zhì)疑和反對(duì)，但是線性規(guī)劃不一樣，一誕生就得到人們的青睞。這是因?yàn)?，單純形算法的?jì)算簡(jiǎn)潔明了，計(jì)算結(jié)果精確有效。它求出的是最優(yōu)解，超乎很多人的期望和想象力。因此被各個(gè)領(lǐng)域頻頻應(yīng)用來(lái)提高工作效率、節(jié)

約能量和減少損失，使利潤(rùn)最大化。線性規(guī)劃加速了數(shù)學(xué)規(guī)劃的普及。線性規(guī)劃是有史以來(lái)傳播速度最快的學(xué)科之一。誕生后很快就普及五大洲，并幾乎應(yīng)用到所有的行業(yè)，故后興起的整數(shù)規(guī)劃、二次規(guī)劃和非線性規(guī)劃等倍受關(guān)注、期待和歡迎。從而，促進(jìn)了數(shù)學(xué)規(guī)劃的普及。