【文章內(nèi)容簡介】 示Xr點(diǎn)走得太遠(yuǎn)，需縮回一些，即進(jìn)行壓縮，并且得到的壓縮點(diǎn)應(yīng)為Xs=Xc+b(XrXc)式中：b——壓縮系數(shù)，常取b=。這時(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)為Xs162。=Xcb(XcXh)=Xc+b(XhXc)如果f(Xs162。)f(Xh)，說明不能沿Xh的反射方向搜索，應(yīng)進(jìn)行縮邊。（3）縮邊使單純形向最好點(diǎn)進(jìn)行收縮，即使最好點(diǎn)Xl不動(dòng)，其余各頂點(diǎn)皆向Xl移近為原距離的一半。Xi=Xi+Xli=0,1,L,n 2從以上各步得到新的單純形后，再重復(fù)開始各步，逐漸縮小單純形直至滿足精度要求為止。初始單純形的形成：構(gòu)成單純形的頂點(diǎn)應(yīng)是線性獨(dú)立的，否則，如二維問題，三個(gè)點(diǎn)在一條直線上，就變成二維問題了，即在一條直線上找極小點(diǎn)的問題，稱為退化。為防止退化，一般取成等邊三角形，因?yàn)樗侵荛L一定前提下包圍面積最大的布點(diǎn)方式。把二維等邊三角形推廣到n維的情況是n+1個(gè)點(diǎn)中任兩個(gè)點(diǎn)的距離都相等，這種單純形就稱為正規(guī)單純形。選取正規(guī)單純形作初始單純形的方法如下：給定一個(gè)初始點(diǎn)X0=[x1,x2,L,xn]T，其余n個(gè)點(diǎn)可取為：X1=[x1+p,x2+q,x3+qL,xn+q]TLLXn=[x1+q,x2+q,x3+qL,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，有X2X1=c即(x1+qx1p)2+(x2+px2q)2+(x3+qx3q)2+L+(xn+qxnq)2=c2化簡得(qp)2+(pq)2=2(pq)2=c2對(duì)于X1和X0，有X1X0=c，即(x1+px1)2+(x2+qx2)2+(x3+qx3)2+L+(xn+qxn)2=c2化簡得p2+(n1)q2=c2聯(lián)立求解得 p=(n+1+n1)cn2(n+11)cn2q=初始單純形也可以采用下面的方法：設(shè)目標(biāo)函數(shù)f(X)為n維向量，因此單純形應(yīng)有n+1個(gè)頂點(diǎn)X1，X2，L，Xn+1。構(gòu)造單純形時(shí)，現(xiàn)在n維空間中選取初始點(diǎn)X1(0)（盡量靠近最優(yōu)點(diǎn)），從X1(0)出發(fā)沿各坐標(biāo)軸方向ei、以步長h找到其余n個(gè)頂點(diǎn)X(0)j（j=2，3，…，n+1）：(0)X(0)=Xj1+hei式中：ei——第i個(gè)坐標(biāo)軸的單位向量；h——步長，~，接近最優(yōu)點(diǎn)時(shí)要減小。~。構(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+a(Xn+2Xh)(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+g(Xn+3Xn+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)163。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+b(XhXn+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)+(X(jk)Xl(k))j=1，2，…，n+1然后轉(zhuǎn)下一步。（5）進(jìn)行收斂性檢驗(yàn)。若236。1n+12252。(k)(k)233。249。f(X)f(X)237。229。jn+2253。163。e 235。238。n+1j=1254。則停止迭代并輸出Xl(k)及f(Xl(k))，否則使k=k+1后轉(zhuǎn)第1步。式中e為任意的小(k)數(shù)，Xn+2為形心。12例試用單純形法求解目標(biāo)函數(shù)f(X)=4(x15)2+(x26)2的極小值。Function f=fun(x)symsx1x2f = 4*(x15)^2+(x26)^2。clearx1= 0 x2= 0 z=0 e= [1。1] h= X0=[x1。x2] X1=X0 + h* e X2=X0 + h*e X3=X0 + h*e第三篇：單純形法綜述單純形法綜述zy1415104曹文亮單純形法是1947年由George Bernard Dantzing(19142005)創(chuàng)建的，單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃問題的誕生。線性規(guī)劃問題是研究在線性約束條件下，求線性函數(shù)的極值問題。然而，對(duì)這類極值問題，經(jīng)典的極值理論是無能為力的，只有單純形法才能有效解決這類極值問題的求解。線性規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)重要分支，也是最早形成的一個(gè)分支，線性規(guī)劃的理論與算法均非常成熟，在實(shí)際問題和生產(chǎn)生活中的應(yīng)用非常廣泛；線性規(guī)劃問題的誕生標(biāo)志著一個(gè)新的應(yīng)用數(shù)學(xué)分支——數(shù)學(xué)規(guī)劃時(shí)代的到來。過去的60年中，數(shù)學(xué)規(guī)劃已經(jīng)成為一門成熟的學(xué)科。其理論與方法被應(yīng)用到經(jīng)濟(jì)、金融、軍事等各個(gè)領(lǐng)域。數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)，其他重要分支的很多問題是在線性規(guī)劃理論與算法的基礎(chǔ)上建立起來的，同時(shí)也是利用線性規(guī)劃的理論來解決和處理的。由此可見，線性規(guī)劃問題在整個(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)的迭代過程，其實(shí)質(zhì)是解線性方程組。概述：根據(jù)單純形法的原理，在線性規(guī)劃問題中，決策變量（控制變量）x1，x2，…x n的值稱為一個(gè)解,滿足所有的約束條件的解稱為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱為最優(yōu)解。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限增大）。無最優(yōu)解與無可行解是兩個(gè)不同的概念。無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問題的可行域?yàn)榭占?無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無窮大（或者無窮?。?。無最優(yōu)解也稱為無限最優(yōu)解，或無界解。無最優(yōu)解判別定理：在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題無最優(yōu)解。無窮多最優(yōu)解判別原理：若線性規(guī)劃問題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，