1、運(yùn) 籌 學(xué) 課 件,目 錄,運(yùn)籌學(xué)概論 第一章 線性規(guī)劃基礎(chǔ) 第二章 單純形法 第三章 LP對(duì)偶理論 第四章 靈敏度分析 第五章 運(yùn)輸問(wèn)題 第六章 整數(shù)規(guī)劃 第七章 動(dòng)態(tài)規(guī)劃 第八章 網(wǎng)絡(luò)分析,第二章 單純形法 (SM-Simplex Method),1947年，美國(guó)運(yùn)籌學(xué)家Dantzig提出，原理是代數(shù)迭代。 單純形法中的單純形的這個(gè)術(shù)語(yǔ)，與該方法毫無(wú)關(guān)系，它源于求解方法的早期階段所研究的一個(gè)特殊問(wèn)題，并延用下來(lái)。 n維空間的單純形，是指具有(n+1)個(gè)頂點(diǎn)的多面體，如果各棱長(zhǎng)相等，則稱為正規(guī)單純形，如二維空間中的三角形(正三角形)三維空間的四面體(正四面體)等,其一般表達(dá)式為：,如前述,當(dāng)

2、m=50,n=100時(shí)，枚舉法要枚舉 100!/(50!)21029 個(gè)50階50元的線性方程組；與之相比，單純形法只需約檢查100個(gè)基本可行解，就可得到最優(yōu)解。幾十年的計(jì)算實(shí)踐表明，單純形法只需很少的迭代次數(shù)就能得到LP問(wèn)題的最優(yōu)解，因此，它不僅成為L(zhǎng)P的最基本算法之一，而且已成為IP和NLP某些算法的基礎(chǔ)。,本章分以下幾節(jié)介紹,1 SM的基本原理 2 SM計(jì)算步驟及應(yīng)用舉例 作業(yè)二： P70 1.7中(2)題 3 初始基本可行解的確定 4 改進(jìn)單純形法 作業(yè)三： P70 1.8中(2)題,1 SM的基本原理,一、單純形法的基本思想 對(duì)于標(biāo)準(zhǔn)形式的LP問(wèn)題：,基于上述設(shè)想可以總結(jié)出單純形法的

3、基本思想如下： 從一個(gè)基本可行解出發(fā)迭代到另一個(gè)基本可行解，每次迭代使目標(biāo)函數(shù)值上升，反復(fù)迭代，逐步選優(yōu)，直到目標(biāo)函數(shù)取得最大值為止。 單純形法的實(shí)現(xiàn)形式： 方程組； 表格； 矩陣。,二、方程組形式的單純形法(單純形法引例),例：,解：首先將問(wèn)題化為標(biāo)準(zhǔn)形式：,觀察標(biāo)準(zhǔn)形式，易得初始基本可行解：,AB=(P3，P4，P5),基于X(0)，改寫(xiě)標(biāo)準(zhǔn)形式：,觀察上述形式，滿足： 基本可行解X(0)對(duì)應(yīng)的可行基是一個(gè)m階排列陣或單位陣； 目標(biāo)函數(shù)方程中所有基變量的系數(shù)全部為0。 我們將滿足上述兩個(gè)條件的方程組稱為典式(方程組典型形式)，這是單純形法下任何一個(gè)基本可行解必須滿足的。一般地將這兩個(gè)條件稱

4、為條典(典型條件)。,現(xiàn)在分析X(0)是否最優(yōu)：目標(biāo)函數(shù)中非基變量的系數(shù)(非基變量的系數(shù)可以作為檢驗(yàn)當(dāng)前基本可行解是否最優(yōu)的一個(gè)標(biāo)志，稱之為檢驗(yàn)數(shù))進(jìn)基變量離基變量。,檢驗(yàn)數(shù),因此，在下一個(gè)基本可行解中，若,對(duì)應(yīng)典式為：,即,稱為一次迭代(從圖解法看是相鄰頂點(diǎn)的轉(zhuǎn)移),比較迭代，可將其過(guò)程描述為：確定換入變量確定換出變量主元變換(初等變換) 典式新解,檢驗(yàn)數(shù),主元,繼續(xù)求解：,主元,檢驗(yàn)數(shù),觀察最后一個(gè)典式，所有檢驗(yàn)數(shù)均為非負(fù)，故其對(duì)應(yīng)的基本可行解為最優(yōu)解，即,說(shuō)明：?jiǎn)渭冃畏ǖ膸缀我饬x：相鄰頂點(diǎn)的迭代(路徑 統(tǒng)計(jì)規(guī)律)。 理論上缺陷：每次只換入一個(gè)變量，速度不 理想如何尋求快速算法。,去掉引入

5、變量，得原問(wèn)題的最優(yōu)解為：,迭代路徑:,最優(yōu)解,三、單純形法原理 由SM思想、引例可見(jiàn)，用SM求解標(biāo)準(zhǔn)形式的LP問(wèn)題，必須解決三個(gè)問(wèn)題： 初始基本可行解的確定； 解的最優(yōu)性檢驗(yàn)； 基本可行解的轉(zhuǎn)移規(guī)則。 這里先放一下，研究和，為此，先討論一下對(duì)應(yīng)基B的單純形表。,(一)對(duì)應(yīng)于基B的單純形表 討論單純形表結(jié)構(gòu)的目的：最優(yōu)性檢驗(yàn)；完成迭代；為以后討論奠定基礎(chǔ)。 對(duì)于標(biāo)準(zhǔn)形式的LP問(wèn)題：,若已知B是其一個(gè)可行基，不妨設(shè)B位于A的前m列，即,對(duì)A、X、C按基B進(jìn)行劃分，得,因此,得,上式表明基變量可以用非基變量表示。,對(duì)于z=CX，有,上式表明目標(biāo)函數(shù)可以用非基變量表示。,上述方程組的矩陣形式為,上式

6、的系數(shù)增廣陣稱為對(duì)應(yīng)于基B的單純形表：,如果B不是位于A的前m列，則有：,此時(shí)對(duì)應(yīng)于基B的單純形表為：,單純形表四部分內(nèi)容為：,目標(biāo)函數(shù)值,檢驗(yàn)數(shù),基變量取值,對(duì)應(yīng)基B的約束系數(shù)矩陣,因此，對(duì)應(yīng)于基B的單純形表可表示如下：,例：找出下列LP問(wèn)題的兩個(gè)基，并構(gòu)造相應(yīng)的單純形表。,解：取基B如下：,計(jì)算各部分如下：,對(duì)應(yīng)基B的單純形表如下：,取基B如下：,所以：,通過(guò)上例可見(jiàn)，當(dāng)取基B不同時(shí)，構(gòu)造相應(yīng)的單純形表的計(jì)算量是不同的，而當(dāng)基B是單位陣時(shí)，計(jì)算量較小，特別是當(dāng)基B是由引入的松弛變量對(duì)應(yīng)的列向量構(gòu)成時(shí)，其對(duì)應(yīng)的單純形表幾乎就是模型的原始數(shù)據(jù)。這一點(diǎn)為我們后續(xù)介紹的確定初始基本可行解提供了思路

7、。,(二)最優(yōu)判別定理,根據(jù),通常稱,或,因此，最優(yōu)判別準(zhǔn)則為：若基本可行解對(duì)應(yīng)的檢驗(yàn)數(shù)都大于等于零，則相應(yīng)的基本可行解就是最優(yōu)解。 從單純形表上看，所有b0j0，則對(duì)應(yīng)的基本可行解就是最優(yōu)解。,為檢驗(yàn)數(shù)，記為：,(三)換基迭代(基于T(B) 根據(jù)最優(yōu)判別準(zhǔn)則，當(dāng)判定基B對(duì)應(yīng)的基本可行解不是最優(yōu)時(shí)，就要進(jìn)行換基迭代，尋求一個(gè)目標(biāo)函數(shù)值更大的新的基本可行解，具體過(guò)程如下：,(1)確定,(2)確定,上述兩種方法中第一種通常在手算中采用，第二種通常在計(jì)算機(jī)求解中采用。 當(dāng)同時(shí)有若干個(gè)非基變量可作為換入變量時(shí)，可任選其一。,若同時(shí)有若干個(gè)基變量可作為換出變量，可 任選其一。,換入變量所在列與換出變量所

8、在行交叉位置的元素，即為主元 。,從值確定可知，的值有三種情況：大于零、等于零或不存在(當(dāng)bis0,i=1,2,m)。 可以證明：當(dāng)0時(shí)，新的基本可行解使目標(biāo)函數(shù)值上升；當(dāng)=0時(shí)，目標(biāo)函數(shù)值不變；當(dāng)值不存在時(shí)，LP問(wèn)題無(wú)有限最優(yōu)解。 3、進(jìn)行(r,s)旋轉(zhuǎn)變換 將主元化為1，主元所在列的其余元素化為0。 即可確定新的基本可行解對(duì)應(yīng)的單純形表。 變換公式如下式所示：,將主元化為1:,主元所在列的其余元素化為0:,2 SM計(jì)算步驟及應(yīng)用舉例,一、計(jì)算步驟(參見(jiàn)書(shū)P18P21) 1、把LP問(wèn)題化成標(biāo)準(zhǔn)形式。 2、找到問(wèn)題的一個(gè)基本可行解，并構(gòu)造初始單純形表。 3、若所有檢驗(yàn)數(shù)j0，就得到一個(gè)基本最優(yōu)

9、解；此時(shí)若存在某個(gè)非基變量的檢驗(yàn)數(shù)為0，則最優(yōu)解可能不唯一，一般不再求其它的解，停止計(jì)算；否則轉(zhuǎn)4。,4、在所有j0中，只要有一個(gè)k0所對(duì)應(yīng)的系數(shù)列向量中各分量均小于等于零，即 bik0 , i=1,2, ,m 則該LP問(wèn)題無(wú)有限最優(yōu)解(或無(wú)最優(yōu)解)，停止計(jì)算；否則轉(zhuǎn)5。 5、按最小檢驗(yàn)數(shù)規(guī)則,一般地，稱換入變量所在列為主(元)列，換出變量所在的行為主(元)行，兩者交叉位置的元素brs稱為主元。 6、以brs為主元對(duì)當(dāng)前表格進(jìn)行一次換基運(yùn)算，得到一個(gè)新單純形表(同時(shí)，換入變量替代換出變量)，返3。 上述步驟中，1、2為預(yù)備步驟或第0次迭代，36為迭代步驟。,二、SM應(yīng)用舉例 例1：(說(shuō)明SM的

10、計(jì)算過(guò)程及換入或換出變量不唯一時(shí)的確定方法),解：(1)首先將問(wèn)題化 為標(biāo)準(zhǔn)形式：,(2)建立初始單純形表,根據(jù)前一節(jié)討論，可得初始單純形表如下:,(3)觀察上表，因檢驗(yàn)數(shù)中存在小于零的，所以當(dāng)前解不是最優(yōu)解。 (4)確定換入變量。因?yàn)椋?(5)確定換出變量。計(jì)算最小比值：,(6)以主元為中心進(jìn)行初等變換，即可得到新的單純形表。, ,由上表知，新的基本可行解為,重復(fù)上述(3) (6)得下表：,由于上表中所有檢驗(yàn)數(shù)均已非負(fù)，因此得到問(wèn)題的最優(yōu)解：,去掉引入變量，得原問(wèn)題的最優(yōu)解與最優(yōu)值為：,在實(shí)際運(yùn)算過(guò)程中，上述迭代過(guò)程可連續(xù)進(jìn)行。見(jiàn)下頁(yè)表。, ,例2：(無(wú)界解的判別),從上表最后一表可見(jiàn)，對(duì)1

11、=-2，它所對(duì)應(yīng)的列向量(-1，0，-1)T0，故目標(biāo)函數(shù)最優(yōu)值無(wú)上界，即問(wèn)題無(wú)最優(yōu)解。,實(shí)質(zhì)上，所謂無(wú)有限最優(yōu)解的判別，直觀上看就是對(duì)應(yīng)于換入變量，按最小比值法則找不出一個(gè)換出變量，亦即使SM迭代過(guò)程無(wú)法進(jìn)行。 對(duì)本例來(lái)說(shuō)，從第一個(gè)表中即可看出有無(wú)界解：如果選取1=-2對(duì)應(yīng)的變量x1為換入變量，此時(shí)就找不出換出變量，故可判定問(wèn)題無(wú)有限最優(yōu)解(或無(wú)最優(yōu)解)。,例3:(說(shuō)明有多重最優(yōu)解的情況的判定),解：首先將問(wèn)題化 為標(biāo)準(zhǔn)形式：, ,從最優(yōu)表可見(jiàn)，問(wèn)題的最優(yōu)解與最優(yōu)值為：,去掉引入變量，得原問(wèn)題的最優(yōu)解與最優(yōu)值為：,在SM計(jì)算步驟中曾講過(guò)，若在最優(yōu)表中，某個(gè)非基變量的檢驗(yàn)數(shù)為0，則此時(shí)最優(yōu)解可

12、能不唯一，即可能有多重最優(yōu)解。,對(duì)于本例， x4為非基變量且4=0，此時(shí)若在最優(yōu)表的基礎(chǔ)上選x4為換入變量，進(jìn)行單純形法強(qiáng)行迭代(如下表所示) ，雖不能使目標(biāo)函數(shù)值增加，但卻可得到另外一個(gè)基本可行解，即：,由圖解討論易知，在這兩個(gè)基本可行解邊線間的任意一點(diǎn)也必為最優(yōu)解。若記,則由,但是，在單純形表運(yùn)算過(guò)程中，只要找到一個(gè)最優(yōu)解就可以停止了。在實(shí)際應(yīng)用中，問(wèn)題若有多重最優(yōu)解可增加決策的選擇機(jī)會(huì)，做出更加合意的決策。,由多重最優(yōu)解的確定過(guò)程可知，若在最優(yōu)表中，某個(gè)非基變量的檢驗(yàn)數(shù)為0，相應(yīng)的列向量中不存在大于0的分量，則此時(shí)并不存在多重最優(yōu)解；換句話說(shuō)，當(dāng)檢驗(yàn)數(shù)為0的非基變量作為換入變量時(shí)，找不到

13、換出變量，此時(shí)最優(yōu)解仍唯一。 綜上，可以給出多重最優(yōu)解的判別條件是： 在最優(yōu)表中至少有一個(gè)非基變量的檢驗(yàn)數(shù)為0，且其對(duì)應(yīng)的列向量中至少有一個(gè)大于0的分量。,例4:(說(shuō)明SM的另一種表格形式),z行的數(shù)字可通過(guò)下述方法獲得：,z行的數(shù)字還可通過(guò)將目標(biāo)函數(shù)用非基變量表示后，取系數(shù)的相反數(shù)獲得，即,為了很容易地得到目標(biāo)函數(shù)行或檢驗(yàn)數(shù)行的數(shù)，當(dāng)目標(biāo)函數(shù)中含有基變量時(shí)，可采用另一種形式的單純形表。借助表的結(jié)構(gòu)，可直接在表上運(yùn)算就可得到目標(biāo)函數(shù)行的所有分量。,對(duì)于本例：,檢查問(wèn)題的初始單純形表，易知已得問(wèn)題的最優(yōu)解，其最優(yōu)解和最優(yōu)值分別為：,作業(yè)二,P70 1.7中(2)題,3 初始基本可行解的確定,現(xiàn)在

14、讓我們回過(guò)頭來(lái)考慮SM的第一階段問(wèn)題，即如何求得第一個(gè)基本可行解。 在前面的討論中，我們都假定約束方程組的系數(shù)矩陣中含有一個(gè)m階單位或存在一個(gè)可行基，所以一開(kāi)始就很容易地得到初始基本可行解。但是，在許多問(wèn)題中，往往不存在現(xiàn)行的可行基。而且當(dāng)問(wèn)題規(guī)模較大時(shí)，判斷m階矩陣是否滿秩的計(jì)算量都是很大的。那么如何才能快速得到一個(gè)可行基，使算法的迅速進(jìn)入迭代過(guò)程呢？,方法是通過(guò)引入人工(造)變量，即在 原問(wèn)題的約束方程中加入人工變量形成一個(gè)可作為基的單位陣，這樣的單位陣稱為人造基。 一般地，當(dāng)給定的LP問(wèn)題約束方程組的系數(shù)矩陣中不含有可作為基的單位陣時(shí)，則為每一個(gè)(或部分)約束方程引入一個(gè)人工變量，從而較

15、容易地得到一個(gè)初始基本可行解。,于是在新的約束方程組的系數(shù)矩陣中便得到一,因?yàn)槿斯ぷ兞渴菑?qiáng)行加入原約束方程組中的虛擬變量，它可能破壞約束條件的等式關(guān)系，影響所求LP問(wèn)題的解。為此，需要對(duì)目標(biāo)函數(shù)進(jìn)行相應(yīng)的修改，并構(gòu)造一個(gè)新的LP問(wèn)題，通過(guò)求解新問(wèn)題，來(lái)獲得原問(wèn)題的最優(yōu)解。根據(jù)對(duì)目標(biāo)函數(shù)處理方法的不同，形成了不同的解決問(wèn)題的方法，常用的有大M法和兩階段法實(shí)質(zhì)上都是SM的變形。 本部分內(nèi)容，我們主要介紹兩階段法。,兩階段法 一、兩階段法原理,對(duì)于標(biāo)準(zhǔn)形式的LP問(wèn)題：,構(gòu)造輔助LP問(wèn)題：,對(duì)于輔助LP問(wèn)題，顯然存在基本可行解，且對(duì)應(yīng)的單純形表易于構(gòu)造，如下表所示：,觀察輔助LP問(wèn)題，易知它一定有最優(yōu)

16、解，且,輔助LP問(wèn)題：,下面我們看一看輔助LP問(wèn)題與原LP問(wèn)題解之間的關(guān)系。,(此結(jié)論用反證法易證),結(jié)論2：原問(wèn)題有可行解的充要條件是,輔助LP問(wèn)題：,綜上，兩階段法的過(guò)程是： 第一階段：求解輔助LP問(wèn)題。,第二階段：求解原問(wèn)題。,二、兩階段法基本步驟,對(duì)于一般的LP問(wèn)題(標(biāo)準(zhǔn)形式)而言，兩階段法通過(guò)引入人工變量將問(wèn)題的求解分為兩個(gè)階段。 階段：求解輔助LP問(wèn)題。判明原問(wèn)題是否存在可行解，若存在就找出一個(gè)初始基本可行解。 用SM求解輔助LP問(wèn)題，最終單純形表可能出現(xiàn)以下幾種情況：,階段：求解原問(wèn)題。 首先，建立原問(wèn)題的初始單純形表。只需把階段的最終單純形表修改如下：,(1)刪去人工變量諸列；

17、 (2)采用第二種形式的單純形表，把cj行與CB列的數(shù)字添上； (3)用z替代w，并計(jì)算原問(wèn)題相應(yīng)基本可行解的目標(biāo)函數(shù)值和檢驗(yàn)數(shù)； 這樣就得到原問(wèn)題的初始單純形表。 然后，進(jìn)行單純形法迭代，直到運(yùn)算結(jié)束。此過(guò)程中，可判定問(wèn)題有無(wú)界解或有多重最優(yōu)解。 下面舉例說(shuō)明兩階段法的應(yīng)用。,三、兩階段法應(yīng)用舉例,解：(1)首先將問(wèn)題化 為標(biāo)準(zhǔn)形式：,例：用單純形法求解下列問(wèn)題：,(2)構(gòu)造輔助LP問(wèn)題，并求其最優(yōu)解： 觀察該問(wèn)題的約束系數(shù)矩陣，并不存在可作為基的單位陣，因此需引入人工變量構(gòu)造輔助LP問(wèn)題。但構(gòu)造輔助LP問(wèn)題時(shí)，并不需要每個(gè)約束方程均需引入人工變量。因此，可構(gòu)造如下輔助LP問(wèn)題：,求解輔助L

18、P問(wèn)題的過(guò)程如下表所示：,初始表,最優(yōu)表,由輔助LP問(wèn)題最優(yōu)表可見(jiàn)，其最優(yōu)值為0，且最優(yōu)基變量中不含有人工變量，因此得到原問(wèn)題的一個(gè)基本可行解。這樣我們就可以構(gòu)造原問(wèn)題的初始單純形表，從而進(jìn)入第二階段求解。,(3)構(gòu)造原問(wèn)題的初始單純形表，并求其最優(yōu)解。如下表所示：,根據(jù)上表，得原問(wèn)題的最優(yōu)解與最優(yōu)值為：,去掉引入變量，得原始問(wèn)題的最優(yōu)解與最優(yōu)值為：,關(guān)于單純形法的計(jì)算效率 許多從事數(shù)學(xué)規(guī)劃研究的人員都曾指出：SM從理論上看并不是有效的算法。因?yàn)檫@種算法只是在相鄰基本可行解之間迭代。于是人們產(chǎn)生這樣一種想法：要是使SM能同時(shí)考察非相鄰的基本可行解，那么達(dá)到最優(yōu)就會(huì)快些。但是，對(duì)于單純形法改革的許多方案，在總的計(jì)算時(shí)間方面并未產(chǎn)生顯著的效果，所以上述的單純形法仍被認(rèn)為是求解LP的最好方法。 SM的計(jì)算效率依賴于：(1)達(dá)到最優(yōu)解前的迭代次數(shù)；(2)解決問(wèn)題總的計(jì)算時(shí)間。,計(jì)算數(shù)以千計(jì)的LP實(shí)際問(wèn)題積累的實(shí)踐經(jīng)驗(yàn)表明，具有m個(gè)約束條件和n個(gè)變量的標(biāo)準(zhǔn)形式的LP問(wèn)題的迭代次數(shù)介于m與3m之間，平均為2m。迭代次數(shù)的實(shí)際上限是2(m+n)。 總的計(jì)算時(shí)間大約與約束條件個(gè)數(shù)的立方(m3)成正比。即若問(wèn)題的約束條件個(gè)數(shù)是問(wèn)題的2倍，則問(wèn)題