最優(yōu)化課件第二章解析

開始最優(yōu)化方法

（最優(yōu)化課件研制組）退出主講：張京最優(yōu)化方法2.基本容許解的改進(jìn)（1）Gauss-Jordan方程組假定是（2.21）的一個基。由得等價方程組記則（2.28）可寫成（2.28）（2.29）（2.29）稱為關(guān)于基的Gauss-Jordan方程組（G-J方程組）。典范線性規(guī)劃的主約束即是一個G-J方程組。G-J方程組的性質(zhì)：

ⅰ）一個基決定唯一的G-J方程組；ⅱ）若是容許基，則由其G-J方程組可得出關(guān)于的基本容許解

ⅲ）在G-J方程組中,基變量的系數(shù)向量構(gòu)成單位矩陣。性質(zhì)?。┱f明求新的基本容許解的過程實質(zhì)上就是不同基的G-J方程組間的轉(zhuǎn)化過程。這個轉(zhuǎn)化過程很容易實現(xiàn)。設(shè)是新基，是用非基向量替換中的得到的矩陣。

這時G-J方程組間的轉(zhuǎn)化過程就是要將非基變量的系數(shù)向量變?yōu)閱挝幌蛄浚ㄐ再|(zhì)ⅲ）.要實現(xiàn)這個過程，則必須有元素，稱為主元。轉(zhuǎn)化過程顯示如下：

關(guān)于基的Gauss-Jordan方程組

關(guān)于基的Gauss-Jordan方程組為保證解的改進(jìn)，替換須滿足以下兩個條件：第一，容許性條件。即保證的G-J方程組的右端項非負(fù)的條件。第二，下降性條件。即保證的基本容許解的目標(biāo)函的基本容許解的目標(biāo)函數(shù)值的條件。數(shù)值小于i）容許性條件由，即主元還必須為正。結(jié)論是：為保證的G-J方程組的右端項非負(fù)，

（2.36）主元必須是滿足的正數(shù)。如果主元不存在，則線性規(guī)劃解無界（定理2.12）。例2.6

考慮例2.5中的線性規(guī)劃

關(guān)于的G-J方程組試把和分別引入基，求新的基本容許解。ⅱ）下降性條件新解。

中只有其余分量皆為0。于是，由（2.26）式得（2.37）由于，所以只要，則特別當(dāng)時，只要，必有結(jié)論是：引入判別數(shù)為正的變量，將保證的基本的基本容許解的目標(biāo)函數(shù)值。容許解的目標(biāo)函數(shù)值不大于引理2.10定理2.11（單純形法基本定理）在標(biāo)準(zhǔn)線性規(guī)劃（2.21）中，假設(shè)：?。┦侨菰S基，關(guān)于的基本容許解；是非退化的，即ⅱ）非基變量的判別數(shù)；ⅲ），是用公式（2.36）確定的一個行標(biāo)；ⅳ）用替換中的，而其余基向量不變，構(gòu)成。矩陣那么，是容許基，且關(guān)于的基本容許解的目標(biāo)函數(shù)值小于關(guān)于的基本容許解的目標(biāo)函數(shù)值。

定理2.12在標(biāo)準(zhǔn)線性規(guī)劃（2.21）中，假設(shè)：?。┦侨菰S基；ⅱ）非基本變量的判別數(shù)；ⅲ）。那么線性規(guī)劃（2.21）存在可以使目標(biāo)函數(shù)值任意減小的容許解。（2）單純形表以上過程都可以清晰地在一張表——單純形表上進(jìn)行，稱之為表上作業(yè)法。假設(shè)已知（容許）基，那么關(guān)于的信息全部反映在以下兩個式子（線性規(guī)劃的兩個關(guān)鍵數(shù)學(xué)式）中，稱之為關(guān)于基的增廣G-J方程組。增廣G-J方程組其實可由線性規(guī)劃（2.21）的原始數(shù)據(jù)經(jīng)初等行變換得到。原有(2.45）式左乘即得（2.43）式，（2.43）式再左乘加到（2.46）式上便得（2.44）式。

隱去增廣G-J方程組中的變量和的系數(shù)向量，將其余數(shù)據(jù)列成表（2.51）稱為關(guān)于基的單純形表。若是最優(yōu)基，則稱為最優(yōu)表。單純形表是增廣G-J方程組的簡單表示。表稱為線性規(guī)劃的準(zhǔn)備表。類似前面的推導(dǎo)，由準(zhǔn)備表容易導(dǎo)出單純形表至此，含有標(biāo)準(zhǔn)基的線性規(guī)劃問題的求解徹底解決。歸納見（3）。例2.7求解例2.5中的線性規(guī)劃。P64-55（3）典范線性規(guī)劃的解法考慮典范線性規(guī)劃是標(biāo)準(zhǔn)容許基。

典范線性規(guī)劃含有標(biāo)準(zhǔn)容許基，它的準(zhǔn)備表既是單純形表，因此單純形法可以直接啟動。算法2.1（單純形法）P65單純形法本質(zhì)上是求解典范線性規(guī)劃的算法。定理2.13在使用單純形法（算法2.1）求解典范線性規(guī)劃時，若各次迭代出的基本容許解皆是非退化的，則算法在有限步終止。推論2.14典范線性規(guī)劃或者存在最優(yōu)基本容許解，或者解無界。對于如下形式的線性規(guī)劃其中。先引入非負(fù)變量將其化為典范形式然后就可以啟動單純形法。例2.8求解線性規(guī)劃P663.初始基本容許解的產(chǎn)生對于標(biāo)準(zhǔn)線性規(guī)劃（2.54）引入個人工變量

，求解輔助線性規(guī)劃——一個典范線性規(guī)劃（2.55）其中。顯然（2.55）不可能無解。設(shè)（2.55）的最優(yōu)值為，顯然。設(shè)最優(yōu)表對應(yīng)的G-J方程組為（2.56）注意：與等價。（2.54）與（2.55）的關(guān)系：若，則（2.54）無解；

若，則由（2.56）可得到（2.54）的一個初始基本容許解。以下討論在下進(jìn)行。分兩種情形：

（1）在最優(yōu)表中人工變量已全部退出基變量（表現(xiàn)為中不存在基向量）。

這時，與等價的中有了標(biāo)準(zhǔn)基，

表明（2.54）有了初始基本容許解，這時可以開始求解（2.54）（見下面的4.（1））。即（2）在最優(yōu)表中至少還有一個人工變量是基變量（表中有基向量）。

現(xiàn)為假設(shè)第個人工變量仍是基變量，那么它的取值為

。因為，所以?？紤]（2.56）的第個方程（2.58）以下分兩種情形：?。┤?，則（2.58）實質(zhì)上成為的第個方程是多余方程，

。這表明從而的第個方程也多余。

劃去第個方程，人工變量將徹底消失。ⅱ）若至少有一個不為0，不妨設(shè)

以為主元在最優(yōu)表上進(jìn)行換基運(yùn)算，人工變量就會從基變量中消失。重復(fù)以上步驟，直到人工變量全部從基變量中消失，最終的G-J方程組為這時與等價的中也有了標(biāo)準(zhǔn)基，從而（2.54）也有了初始基本容許解，于是可以開始求解（2.54）（見下面的4.（2））。4.標(biāo)準(zhǔn)線性規(guī)劃的解法按3.求出（2.54）的初始基本容許解之后，接下來求解（2.54），與3.中的（1）、（2）對應(yīng)，分別為（1）求解線性規(guī)劃（2）求解線性規(guī)劃總結(jié)：一般來說，解線性規(guī)劃主要分為兩大步：第一步，化標(biāo)準(zhǔn)形（有時不需要）；第二步，啟動兩階段單純形法（當(dāng)標(biāo)準(zhǔn)形是典范線性規(guī)劃時，直接進(jìn)入第二階段）。例求解線性規(guī)劃例2.9求解線性規(guī)劃例2.10求解線性規(guī)劃2.4退化的處理在非退化假定下，單純形法（算法2.1）具有有限終止性（定理2.13）。取消非退化假定，情況會是怎么樣？第一，算法2.1可能發(fā)生無限循環(huán)，求不到最優(yōu)解；第二，適當(dāng)修改選主元的規(guī)則，則可以保證單純形法仍具有有限步終止性。1.選主元規(guī)則單純形法的核心是換基運(yùn)算，而換基運(yùn)算的首要步驟是選主元。選取主元列標(biāo)的規(guī)則稱為進(jìn)基規(guī)則；選取主行標(biāo)的規(guī)則稱為退基規(guī)則。進(jìn)基規(guī)則和退基規(guī)則合稱選主元規(guī)則。選主元規(guī)則有多種多樣，常用的進(jìn)基規(guī)則有以下兩種：?。┳畲笳袆e數(shù)進(jìn)基規(guī)則ⅱ）正判別數(shù)最小下標(biāo)進(jìn)基規(guī)則選取正判別數(shù)中最小的下標(biāo)作為主元的列標(biāo)。算法2.2和算法2.3就采用這種進(jìn)基規(guī)則。常用的退基規(guī)則是最小行標(biāo)退基規(guī)則。在使用公式（2.36）確定主元行標(biāo)，若最小比值在多行上取得，則從中選取最小的行標(biāo)作為主元的行標(biāo)。選取最大判別數(shù)的下標(biāo)作為主元的列標(biāo)。若同時有多個等值的最大正判別數(shù)，則選取其中最小的下標(biāo)為主元的列標(biāo)；最大正判別數(shù)進(jìn)基規(guī)則與最小行標(biāo)退基規(guī)則合稱Dantzig規(guī)則。算法2.1采用的就是這種規(guī)則。計算實踐表明，在各種選主元規(guī)則中，Dantzig規(guī)則效果較好，在求解同一線性規(guī)劃問題時，迭代次數(shù)相對較少。它的缺點(diǎn)是，在求解退化問題時，算法可能產(chǎn)生無限循環(huán)，求不到最優(yōu)解。2.避免循環(huán)的規(guī)則這里介紹一種最簡單的避免循環(huán)的規(guī)則—Bland規(guī)則。Bland規(guī)則設(shè)在單純形法的迭代過程中，當(dāng)前容許基是關(guān)于的基容許解不是最優(yōu)解，則主元列標(biāo)和行標(biāo)分別由如下兩個規(guī)則確定：?。〣land進(jìn)基規(guī)則采用正判別數(shù)最小下標(biāo)進(jìn)基規(guī)則，即主元列標(biāo)是由此確定進(jìn)基。ⅱ）Bland退基規(guī)則假定。設(shè)又設(shè)則主元行標(biāo)由式確定，由此確定退基。換句話說，在所有可能的退基向量中，選取下標(biāo)最小的向量退基。

Bland證明：使用帶有Bland規(guī)則的單純形法求解典范線性規(guī)劃，不會發(fā)生基的循環(huán)。2.5修正單純形法修正單純形法是計算機(jī)實現(xiàn)的單純形法。注意到，包含全部信息的單純形表中的數(shù)據(jù)完全由基（實際是）及原始數(shù)據(jù)決定?？梢跃陀幸磺?。說有舉例說明修正單純形法的概貌。例如求解解建立單純形表如下1、字體安裝與設(shè)置如果您對PPT模板中的字體風(fēng)格不滿意，可進(jìn)行批量替換，一次性更改各頁面字體。在“開始”選項卡中，點(diǎn)擊“替換”按鈕右側(cè)箭頭，選擇“替換字體”。（如下圖）在圖“替換”下拉列表中選擇要更改字體。（如下圖）在“替換為”下拉