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