【正文】 ，成為現(xiàn)代公認的較好的算法之一。 DFP法是基于牛頓法的思想又作了重要改進。這種算法僅用到梯度，不必計算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。 （ 2） 迭代過程1） 任選初始點 ，計算收斂精度 ，維數(shù) n；2） 給定變尺度矩陣初值 （ 單位矩陣 ） ，令 ，置 k=0；3） 求探索方向 和最優(yōu)步長因子4） 進行一維搜索，求下一個迭代點5） 檢驗是否滿足，若滿足 ，則 即為極小點，停止迭代。否則轉(zhuǎn)下一步；6） 檢查迭代次數(shù)，若 ，則 ，轉(zhuǎn)向步驟 2)，若 則進行下一步；7） 構(gòu)造新的探索方向為此應(yīng)計算 、 、然后令 轉(zhuǎn)步驟 3)。 線性規(guī)劃 —— 單純形法 線性規(guī)劃是應(yīng)用最廣的優(yōu)化技術(shù)之一，也可以說是一種最有效的優(yōu)化技術(shù)。目標函數(shù)和約束函數(shù)都是線性函數(shù)的最優(yōu)化問題，稱為線性規(guī)劃或線性優(yōu)化問題。線性規(guī)劃是數(shù)學規(guī)劃中的一個比較成熟的分支。在生產(chǎn)計劃、工程預算和經(jīng)濟管理領(lǐng)域內(nèi)應(yīng)用十分廣泛。同時，線性規(guī)劃算法也可作為求解非線性有約束優(yōu)化問題的子問題的工具，如可行方向法中可行方向的搜尋就是采用線性規(guī)劃方法。 下面是在工廠管理中出現(xiàn)的線性規(guī)劃例子： 1） 按進度表安排員工，使一周中每天的勞動人數(shù)都很充足，并且要讓工人的滿意程度和勞動生產(chǎn)率盡可能的高； 2） 選擇即將要生產(chǎn)的產(chǎn)品，充分利用現(xiàn)有的資源，并在當前的價格下獲取最大的利潤； 3） 找到一個工廠車間到倉庫的分配模式，在有限的能力下使成本最??； 4） 在考慮到利潤、競爭對手出標和操作約束條件的情況下，使競標成功。當用數(shù)學語言表述時，所有這些問題都隱含了許多變量、等式和不等式。一個解決方案不僅要滿足所有的約束條件，而且必須完成目標函數(shù)的極值要求，例如利潤最大或成本最小。利用現(xiàn)代軟件，可以建立并解決帶有數(shù)千個變量和約束條件的線性問題。1 線性規(guī)劃的標準形式與解 線性規(guī)劃的數(shù)學模型同樣由設(shè)計變量、目標函數(shù)和約束條件組成，不過其中的約束條件除變量非負性限制外都采用等式約束。線性規(guī)劃問題的一般形式為（ 145）其矩陣形式為（ 146）式中， AX=B—— 約束方程； B—— 常數(shù)向量； A—— 系數(shù)矩陣。 一般情況下，應(yīng)有 , 因為當 m=n時約束方程只有一個惟一的解，不存在可供選擇的其他解，不存在優(yōu)化問題。當時，約束方程有無窮多組解，線性規(guī)劃就是要從這無窮多組解中尋找一個使目標函數(shù)極小化的最優(yōu)解。在線性規(guī)劃的數(shù)學模型中，約束條件主要是等式約束，不等式約束僅限于變量的非負約束。對于其他形式的不等式約束，可以通過引入松弛變量的方法將其轉(zhuǎn)化為等式約束。例如 , 對于約束條件 可通過引人松弛變量 ， 變換為 如果原來問題中的某些變量并不要求非負，則可將其變換為兩個非負變量之差。經(jīng)過上述處理后 ,線性規(guī)劃問題總能變換為式 (132)或式 (133)所示的線性規(guī)劃的標準形式。 例 111某車間生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)甲種產(chǎn)品每件需要材料 9kg、 3個工時、 4kw電能，可獲利 60元。生產(chǎn)乙種產(chǎn)品每件需用材料 4kg 、 10個工時、 5kw電能，可獲利 120元。若每天能供應(yīng)材料 360kg， 有 300個工時，能供 200kw電能，則每天生產(chǎn)甲、乙兩種產(chǎn)品各多少件才能夠獲得最大的利潤。 設(shè)每天生產(chǎn)的甲、乙兩種產(chǎn)品分別為 、 件 , 則此問題的數(shù)學模型如下 引入松弛變量 、 、 ，將其轉(zhuǎn)換為標準形式該問題的解如圖 124所示。在約束方程中，若令 nm個變量為 0， 就可求得另外m個不全為 0的解。于是這 m個不全為 0的解和 nm個為 0的解共同組成一個解向量，稱為線性規(guī)劃問題的基本解。其中 m個不全為 0的變量稱為基本變量，其余 nm個為 0的變量稱為非基本變量。 在系數(shù)矩陣中，任取 m列可以構(gòu)成一個基本解，可知一個線性規(guī)劃問題的基本解的個數(shù)等于排列組合數(shù)圖 124二維線性規(guī)劃問題的圖解法由圖可以看出，線性規(guī)劃的約束邊界為一組直線或平面，由這些直線和平面構(gòu)成的可行域是一個封閉的凸多邊形或凸多面體。這個凸多邊形或凸多面體的每一個頂點對應(yīng)該線性規(guī)劃問題的一個基本可行解。因此線性規(guī)劃問題的最優(yōu)解必定在這些頂點上取得。實際上，線性規(guī)劃解法就是一種關(guān)于基本可行解的迭代算法，或者說是一種可行域頂點轉(zhuǎn)換的算法。2基本可行解及其轉(zhuǎn)換 既然線性規(guī)劃問題的最優(yōu)解必定在約束條件所圍成的凸多邊形或凸多面體的頂點上取得，而每一個頂點都 是線性規(guī)劃問題的一個基本可行解，則線性規(guī)劃問題的求解可歸結(jié)為找出目標函數(shù)值下降的基本可行解的過程。這樣，求解線性規(guī)劃問題需要解決以下兩個問題：① 基本可行解的求解；② 新的基本可行解應(yīng)使目標函數(shù)有較大的下降。（ 1） 基本解及其轉(zhuǎn)換1） 基本解的產(chǎn)生 根據(jù)基本解的定義，對由系數(shù)矩陣和常數(shù)向量組成的如下增廣矩陣（ 147） 進行一系列初等變換，將其中系數(shù)矩陣 的 m列依次變?yōu)榛蛄繒r，滿足約束方程的一個基本解便產(chǎn)生了。 若經(jīng) m次主元變換后，將增廣矩陣的前 m列變?yōu)槿缦聠挝蛔泳仃? （ 148） 約束方程變換為如下的正則方程 ＝ （ 149） 則 , 對應(yīng)的基本解為（ 150）其中，前 m個變量為基本變量，后 nm個變量為非基本變量。若變換后的常數(shù)項均為非負，即 ， 則此基本解是一個基本可行解?？梢?，得到一個基本解或基本可行解的方法，都是對增廣矩陣進行高斯消元變換。消元變換的基本公式為上式表明了對轉(zhuǎn)軸變量 以 為轉(zhuǎn)軸元素的轉(zhuǎn)軸變換或消元變換。2） 解的轉(zhuǎn)換 在式 (148)的增廣矩陣中，將某一非基本變量 對應(yīng)的任意一個系數(shù)作為轉(zhuǎn)軸變換的轉(zhuǎn)軸元素，進行另一次消元變換，又可得到一個新的增廣矩陣和相應(yīng)的基本解。這種變換實際上是一種非基本變量和基本變量的轉(zhuǎn)換，也是從一組基本解向另一組基本解的轉(zhuǎn)換。但是這樣的變換并不能保證變換后的常數(shù)向量為非負。也就是說，如果原來的解是一個基本可行解，不能保證變換后的解也是一個基本可行解。（ 2） 基本可行解的轉(zhuǎn)換 —— 規(guī)則 (選擇轉(zhuǎn)軸行 )要使變換后所得的基本解為可行解，還要研究這樣的方法，即如何使某個選定的變量 進入基本變量，來替換另一個現(xiàn)在還在基本變量中的 ， 形成新的基本可行解。 當已經(jīng)得到一組可行解，即 ， 若要求把 選進基本變量的下一組基本解是可行解的話，則在系數(shù)矩陣第 k列所有系數(shù)中不能取任何負值的 軸元素，否則將使轉(zhuǎn)軸變換后 的對應(yīng)元素 為負值，結(jié)果對應(yīng)的 必將是負的，它就不是可行解的一個元素。 因此，第一個要求是，若 ,則必需叫 才可選做轉(zhuǎn)軸元素進行轉(zhuǎn)軸運算，用 代替 這個過程是反復進行轉(zhuǎn)軸運算，直到 從某個正值變成 0， 而 從 0變成某個正值為止。根據(jù)原來的正則形式方程組 (149)， 由于要求 由非基本變量變成基本變量，其值將由 0變成某一正值 ，這將引起原來各基本變量取值的變化（ 152）如果式 （ 152） 是可行解，且 又是其中的一個基本變量 ,則在 中必然有一個 (假定它是 )是 0， 其余皆為正。當然這個變量 就應(yīng)從基本變量中排除出去。 這就是說，只有取式 （ 152） 中各差值的最小者為0時，才能保證使其余各差值皆為正。所以，由可知，只有保證 才能使 進入可行解的基本變量，將 置換出去。同時，由于 非負，對 又有 的要求。此時，上式中的 就是進行轉(zhuǎn)軸運算時應(yīng)取的轉(zhuǎn)軸元素。這就是所謂的選擇轉(zhuǎn)軸行的 規(guī)則。若想使 取代 成為可行解中的基本變量，所選的轉(zhuǎn)軸行 或轉(zhuǎn)軸元素 要滿足條件（ 153） 在例 111中， 可得一組可行解 、 為非基本變量， 、 、 為基本變量。考慮將 變換為基本變量，由于 最小者為 ，故取 調(diào)出行 (第 1行 )為轉(zhuǎn)軸行，取調(diào)出行與調(diào)入列 (第 1列 )相交處的元素 為轉(zhuǎn)軸元素，作轉(zhuǎn)軸變換，使 取代 成為基本變量，從而得到一組新的基本可行解。（ 3） 初始基本可行解的建立初始基本可行解可通過三種方法獲得：1） 通過對增廣矩陣進行消元變換得到，這是一種較繁瑣的方法；2） 當約束條件全部為不等式約束，且常數(shù)向量均大于零時，引入松弛變量，并選取松弛變量作為基本變量，就可得到一個基本可行解 （ 例 111） ；3） 如果除變量非負約束條件外，其他約束均為等式約束而無法引入松弛變量時 ，可引入人工變量，并構(gòu)造以人工變量之和為輔助目標函數(shù)的輔助線性規(guī)劃問題，即（ 154）式中， 為引入的人工變量。如果不等式約束條件右端項 是負值，它所對應(yīng)的松弛變量就不能作為基本可行解的基本變量，所以上述方法并不是總能成功的。這時需引入人工變量，經(jīng)過變換再將它從基本變量中替換出去，具體作法舉例說明如下。例 112 對線性規(guī)劃問題引入松弛變量 、 、 、 ，將問題變換為標準形式： 由于 中的系數(shù)為 1，而常數(shù)項為 3500， 所以 不能進入基本可行解的基本變量中。為此需引入一個非負的人工變量 ， 將約束條件變?yōu)橛纱艘鹨粋€問題，就是要保證最后能把 從最優(yōu)解中排除出去。為了做到這一點，可以給 一個很大的系數(shù) ， 對于極小值問題它應(yīng)取正值 (對于極大值問題取負值 )。而只要 F(X)還沒有達到極值，運算過程還可以繼續(xù)進 行下去。在給 一個很大的系數(shù) 后，目標函數(shù)中將增加一項給 因此，只要 還不為零，目標函數(shù)就沒有達到極小 (大 )值。這樣，該線性規(guī)劃問題變?yōu)?(取 =1000)。初始基本可行解為 對此輔助規(guī)劃問題進行消元變換，當輔助目標函數(shù)值等于 0時，所得輔助線性規(guī)劃問題的前 n個變量的值便構(gòu)成了線性規(guī)劃問題的一個初始基本可行解。3最優(yōu)解的搜索 —— 最速變化規(guī)則 (選擇轉(zhuǎn)軸列 )通過 規(guī)則可以實現(xiàn)從一個基本可行解到另一個基本可行解的變換。為了通過基本可行解的變換盡快找到最優(yōu)解，進行基本可行解變換應(yīng)向著目標函數(shù)值有較大下降的方向進行，這可通過最速變化規(guī)則來實現(xiàn)。對于由前 m個變量為基本變量組成的基本可行解（ 155）目標函數(shù)可以寫成（ 156）將上式對應(yīng)的基本可行解變換，得到另一組基本可行解，它的基本變量中包含有 ，即（ 157）其中的 ， 所對應(yīng)的目標函數(shù)為（ 158）令 （ 159）則 （ 160）式中 為相對價值系數(shù)。 （ 161） 顯然，對極小化問題，應(yīng)有 ，即 r是負值。只要 r仍是負值，則目標函數(shù) 還沒有達到極小值，還有下降的趨勢，就還可以進行轉(zhuǎn)軸運算，生成另一組可行解。一旦 r為正，即可停止轉(zhuǎn)軸運算，對應(yīng)的可行解就是最優(yōu)解。也可能有幾組 都為負值。對極小化問題應(yīng)?。?162）式中 ，這樣可以使目標函數(shù)獲得最大下降。根據(jù)式 （ 162） 的正負性判斷是否取得最優(yōu)解的方法稱為最速變化規(guī)則。在求解極小點過程中，先利用約束條件方程組解出可行解，再用最速變化規(guī)則對其檢驗，從中找出最優(yōu)解。計算時，也可以直接把目標函數(shù)和約束條件同時列為轉(zhuǎn)軸運算方程組。采用邊計算可行解，邊校驗?zāi)繕撕瘮?shù)值的變化情況的辦法來求最