運(yùn)籌學(xué)第二單純形法PPT

1、關(guān)于運(yùn)籌學(xué)第二單純形法1第一張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月2一、基礎(chǔ)定理定理1 若線性規(guī)劃問(wèn)題存在最優(yōu)解，則問(wèn)題的可行域是凸集。定理2 線性規(guī)劃問(wèn)題的基本可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域（凸集）的頂點(diǎn)。定理3 若線性規(guī)劃問(wèn)題最優(yōu)解存在，則最優(yōu)解一定在可行域頂點(diǎn)處取得。由此可看出，最優(yōu)解要在基本可行解（可行域頂點(diǎn)）中找。第二張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月3 若LP問(wèn)題有最優(yōu)解的話，定在可行域的某頂點(diǎn)處達(dá)到，又，一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)基本可行解，一個(gè)自然的想法是：找出所有的基本可行解。因基本可行解的個(gè)數(shù)有限，通過(guò)“枚舉法”，從理論上講總能找出所有的基本可行解。而事實(shí)上隨著m，n的增大

2、，解的個(gè)數(shù)迅速增大，致使此路行不通。第三張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月4換一種思路：若從某一基本可行解（今后稱(chēng)之為初始基本可行解）出發(fā)，每次總是尋找比上一個(gè)更“好”的基本可行解，逐步改善，直至最優(yōu)。這需要解決以下三個(gè)問(wèn)題：1.如何找到一個(gè)初始的基本可行解。2.如何判別當(dāng)前的基本可行解是否已達(dá)到了最優(yōu)解。3.若當(dāng)前解不是最優(yōu)解，如何去尋找一個(gè)改善了的基本可行解。第四張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月5定義：如何從一個(gè)可行基找另一個(gè)可行基？稱(chēng)基變換。定義：兩個(gè)基本可行解稱(chēng)為相鄰的，如果它們之間僅變換一個(gè)基變量。對(duì)應(yīng)的基稱(chēng)為相鄰可行基。例 LP問(wèn)題二、思路解析第五張，PPT共七十

3、三頁(yè)，創(chuàng)作于2022年6月6當(dāng)前可行基 所對(duì)應(yīng)的基本可行解顯然不是最優(yōu)。因?yàn)閺慕?jīng)濟(jì)意義上講，意味著該廠不安排生產(chǎn)，因此沒(méi)有利潤(rùn)。相應(yīng)地，將 代入目標(biāo)函數(shù)得從數(shù)學(xué)角度看，若讓非基變量 取值從零增加，(對(duì)應(yīng)可行域的 )第六張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月7相應(yīng)的目標(biāo)函數(shù)值Z也將隨之減少。因此有可能找到一個(gè)新的基本可行解，使其目標(biāo)函數(shù)值有所改善。即進(jìn)行基變換，換一個(gè)與它相鄰的基。再注意到 前的系數(shù)2比 前的系數(shù)1小，即 每增加一個(gè)單位對(duì)Z的貢獻(xiàn)比 大。故應(yīng)讓 從非基變量轉(zhuǎn)為基變量，稱(chēng)為進(jìn)基。又因?yàn)榛兞恐荒苡腥齻€(gè)，因此必須從原有的基變量中選一個(gè)離開(kāi)基轉(zhuǎn)為非基變量，稱(chēng)為出基。誰(shuí)出基？第七張，

4、PPT共七十三頁(yè)，創(chuàng)作于2022年6月8又因?yàn)?仍留作非基變量，故仍有（2）式變?yōu)樵僮?從零增加，能取得的最大值為此時(shí)， 已經(jīng)從24降到了0，達(dá)到了非基的取值，變成非基變量。從而得到新的可行基 。由此得到一個(gè)新的基本可行解：第八張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月9目標(biāo)函數(shù)值：從目標(biāo)函數(shù)值明顯看出， 比 明顯地得到了改善。此基本可行解對(duì)應(yīng)可行域的將（2）式（2）可行基留在左邊，非基變量移到右邊第九張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月10（3）用代入法得：（4）第十張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月11代入目標(biāo)函數(shù)得：這一過(guò)程用增廣矩陣的行初等變換表示為：1/6（-1）（2）

5、按最小非負(fù)比值規(guī)則：主元素第十一張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月12目標(biāo)函數(shù)系數(shù)行按最小非負(fù)比值規(guī)則：第十二張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月133/2（-5）（-1/3）（1/3）第十三張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月14所對(duì)應(yīng)的 LP問(wèn)題第十四張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月15可行基令非基變量 為0，得到最優(yōu)解最優(yōu)值：第十五張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月16總結(jié)：在迭代過(guò)程中要保持常數(shù)列向量非負(fù)，這能保證基可行解的非負(fù)性。最小比值能做到這一點(diǎn)。主元素不能為0。因?yàn)樾械某醯茸儞Q不能把0變成1。主元素不能為負(fù)數(shù)。因?yàn)橛眯械某醯茸儞Q把負(fù)數(shù)變成1

6、會(huì)把常數(shù)列中對(duì)應(yīng)的常數(shù)變成負(fù)數(shù)。此基本可行解對(duì)應(yīng)可行域的其結(jié)果與圖解法一致。第十六張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月17例2 解LP問(wèn)題：對(duì)單純形矩陣作初等行變換，有：按最小非負(fù)比值原則：確定主元素。（-1）（1）1、無(wú)窮多個(gè)解三、其他解的情況第十七張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月18至此，檢驗(yàn)行已沒(méi)有負(fù)數(shù)，當(dāng)前解即為最優(yōu)解。此時(shí)對(duì)應(yīng)的LP問(wèn)題為：0第十八張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月19此時(shí)對(duì)應(yīng)的LP問(wèn)題為：0第十九張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月20此時(shí)對(duì)應(yīng)的LP問(wèn)題為：01第二十張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月21當(dāng)時(shí)，不管 取何值，均有

7、目標(biāo)函數(shù)取得最大值1。此時(shí)約束方程為：其中 為基變量。用非基變量表示出基變量：其中， 為自由變量。設(shè)為 有:其中c是滿足非負(fù)性的任意常數(shù)。第二十一張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月22再由的非負(fù)性，知：解出（其中 ）最優(yōu)解為：最優(yōu)值為：第二十二張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月232、無(wú)最優(yōu)解的兩種情況： 無(wú)界解例3 解LP問(wèn)題：解：對(duì)單純形矩陣作初等行變換，有：第二十三張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月241/2（2）注意到6所在的列無(wú)正元素，將基變量 及目標(biāo)函數(shù)用非基變量 表示為第二十四張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月25從目標(biāo)函數(shù)看，若令非基變量無(wú)限增大

8、，Z也無(wú)限性，即該LP問(wèn)題所追求的目標(biāo)函數(shù)是無(wú)界的，即無(wú)最小值，于是該LP問(wèn)題無(wú)最優(yōu)解。減小，且沒(méi)有影響 的非負(fù)第二十五張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月26 無(wú)可行解例4 求解LP問(wèn)題解：可行域?yàn)榭占?，無(wú)可行解。第二十六張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月27下面先把此LP問(wèn)題化為標(biāo)準(zhǔn)型，然后用單純形法求解。對(duì)單純形矩陣作初等行變換，有：第二十七張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月281/2從最后一個(gè)矩陣可看出，此LP問(wèn)題無(wú)可行基，當(dāng)然就無(wú)可行解。（-1）（-1）（1）第二十八張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月29LP當(dāng)前解已是最優(yōu)的四大特征： 存在一組(初始)可

9、行基（其系數(shù)矩陣為單位陣）。 檢驗(yàn)行的基變量系數(shù)=0。 檢驗(yàn)行的非基變量系數(shù) 0。全部0唯一解。存在=0無(wú)窮多個(gè)解。 常數(shù)列向量0。下面的問(wèn)題是：所給LP的標(biāo)準(zhǔn)型中約束矩陣中沒(méi)有現(xiàn)成的可行基怎么辦？第二十九張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月30人工變量法（也稱(chēng)大M法）針對(duì)標(biāo)準(zhǔn)形約束條件的系數(shù)矩陣中不含單位矩陣的處理方法。例6 用單純形法求解LP問(wèn)題 單純形的進(jìn)一步討論第三十張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月31解：先將其化為標(biāo)準(zhǔn)形式再?gòu)?qiáng)行加上人工變量，使其出現(xiàn)單位矩陣：第三十一張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月32但這樣處理后：不易接受。因?yàn)?是強(qiáng)行引進(jìn)，稱(chēng)為 人工變量

10、。它們與 不一樣。 稱(chēng)為松弛變量和剩余變量，是為了將不等式改寫(xiě)為等式而引進(jìn)的，而改寫(xiě)前后兩個(gè)約束是等價(jià)的。人工變量的引入一般來(lái)說(shuō)是前后不等價(jià)的。只有當(dāng)最優(yōu)解中，人工變量都取值零時(shí)（此時(shí)人工變量實(shí)質(zhì)上就不存在了）才可認(rèn)為它們是等價(jià)的。處理辦法：把人工變量從基變量中趕出來(lái)使其變?yōu)榉腔兞俊榇?，發(fā)明者建議把目標(biāo)函數(shù)作如下處理：第三十二張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月33其中M為任意大的實(shí)數(shù)，“M”稱(chēng)為“罰因子”。用意：只要人工變量取值大于零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最優(yōu)。對(duì)此單純形矩陣作初等行變換，有：第三十三張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月34MM（-1）（-3）（4M）1/6第

11、三十四張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月353/2（-1/3）（3）第三十五張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月36至此，檢驗(yàn)行已沒(méi)有負(fù)數(shù)，當(dāng)前解即為最優(yōu)解。最優(yōu)值為：去掉人工變量 ，即得原LP問(wèn)題的最優(yōu)解：第三十六張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月37 最優(yōu)解判別定理：所有檢驗(yàn)數(shù)0；人工變量為0 無(wú)窮多最優(yōu)解判別定理：所有檢驗(yàn)數(shù) 0；人工變量為0；存在某個(gè)非基變量的檢驗(yàn)數(shù)為0 無(wú)可行解判別：所有檢驗(yàn)數(shù) 0；人工變量0 (4)無(wú)界解判別定理：有一個(gè)非基變量的檢驗(yàn)數(shù)0,但該數(shù)對(duì)應(yīng)的列中沒(méi)有正元素；人工變量為0解的判別定理：第三十七張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月3

12、8單純形法步驟一、構(gòu)造初始可行基1、引入附加變量，化為標(biāo)準(zhǔn)型2、必要時(shí)引入人工變量3、目標(biāo)函數(shù)中，附加變量系數(shù)為0，人工變量則為M二、求基本可行解1、用非基變量表示基變量和目標(biāo)函數(shù)式2、求出一個(gè)基本可行解及相應(yīng)Z值三、最優(yōu)性檢驗(yàn)依據(jù):檢驗(yàn)數(shù)及判別定理四、基變換1、換入基的確定：檢驗(yàn)數(shù)負(fù)值中最小的2、換出基的確定：最小非負(fù)比值規(guī)則返回步驟二第三十八張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月392.2 單純形法的表格形式書(shū)例2.1 P18第三十九張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月40作業(yè)P79 1.3（2），1.7（1）第四十張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月41大M法目標(biāo)是盡快把

13、人工變量從基變量中全部“趕”出去（如果能全部“趕”出去的話）。所用方法除了大M法外，還有下面的兩階段法。 兩階段法用大M法處理人工變量時(shí)，若用計(jì)算機(jī)處理，必須對(duì)M給出一個(gè)較大的具體數(shù)據(jù)，并視具體情況對(duì)M值作適當(dāng)?shù)恼{(diào)整。為了克服這一麻煩，下面的兩階段法將問(wèn)題拆成兩個(gè)LP問(wèn)題分兩個(gè)階段來(lái)計(jì)算：2.3 大M法和兩階段法第四十一張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月42兩階段法的第一階段求解一個(gè)目標(biāo)中只包含人工變量的LP問(wèn)題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)（一般取1），在保持原問(wèn)題約束不變的情況下求這個(gè)目標(biāo)函數(shù)極小化的解。顯然在第一階段中，當(dāng)人工變量取值為0時(shí)，目標(biāo)

14、函數(shù)值也為0。這時(shí)候的最優(yōu)解就是原問(wèn)題的一個(gè)基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原LP問(wèn)題無(wú)可行解。第四十二張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月43第二階段：求解原線性規(guī)劃問(wèn)題的最優(yōu)解。以第一階段的最終單純形表為基礎(chǔ)，去掉人工變量，目標(biāo)函數(shù)換為原問(wèn)題的目標(biāo)函數(shù)，得到第二階段的初始表，繼續(xù)迭代求解。第四十三張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月44 若求得的單純形矩陣中，所有人工變量都處在非基變量的位置。即 及 。則從第1階段去掉人工變量后，即為原問(wèn)題的初始單純形矩陣。并進(jìn)入第2階段。第一階段求解第一個(gè)線性規(guī)劃：第四十四張

15、，PPT共七十三頁(yè)，創(chuàng)作于2022年6月45 若第一階段所求得的單純形中仍含有（解）非零的人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。不再進(jìn)入第2階段。因此兩階段法的第1階段求解有兩個(gè)目的：一為判斷原問(wèn)題有無(wú)可行解。二，若有，則得原問(wèn)題的一個(gè)初始可行基，再對(duì)原問(wèn)題進(jìn)行第2階段的計(jì)算。第四十五張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月46對(duì)單純形矩陣作初等行變換，有：例：第1階段：第四十六張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月47（-1）（-1）第四十七張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月48（-3）（4）1/6（-1）第四十八張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月49（-3）（6）2轉(zhuǎn)入第2

16、階段：3-1（-3）第四十九張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月503/2（-1/3）（3）第五十張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月51書(shū)例：表格形式大M法:P25 表2.2.1 兩階段法:P27 表2.3.1；2.3.2第五十一張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月52作業(yè)P80 1.8（1）第五十二張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月532.4 退化問(wèn)題退化問(wèn)題：按最小比值來(lái)確定換出基變量時(shí)，有時(shí)出現(xiàn)兩個(gè)以上相同的最小比值，從而使下一個(gè)表的基可行解中出現(xiàn)一個(gè)或多個(gè)基變量等于零的退化解。循環(huán)問(wèn)題：退化解出現(xiàn)的原因是模型中存在多余的約束，使多個(gè)基可行解對(duì)應(yīng)同一個(gè)頂點(diǎn)。當(dāng)

17、存在退化解時(shí)，就有可能出現(xiàn)迭代計(jì)算的循環(huán)。即從一個(gè)可行基經(jīng)有限次迭代后又回到原來(lái)的可行基。盡管可能性及其微?。ㄖ钡侥壳盀橹?，還沒(méi)有見(jiàn)到一個(gè)實(shí)際應(yīng)用問(wèn)題產(chǎn)生循環(huán)的例子），但在理論上講是存在的。第五十三張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月54E.Beale曾給出一個(gè)循環(huán)的例子這個(gè)例子用單純形法經(jīng)過(guò)6次迭代后，又回到了初始狀態(tài)，得不到最優(yōu)解。有興趣的同學(xué)可自行用單純形法驗(yàn)證本題產(chǎn)生的循環(huán)現(xiàn)象。而實(shí)際上本題有最優(yōu)解。解決方法：攝動(dòng)法；勃蘭特法。第五十四張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月552.5 改進(jìn)單純形法單純形法計(jì)算的特點(diǎn)是每迭代一次，就要把整個(gè)單純形表重新計(jì)算一遍。從計(jì)算機(jī)的角度來(lái)

18、講，單純形法并不是一種經(jīng)濟(jì)高效的方法。首先是要占用大量的存貯空間，其次，由于每次計(jì)算都利用上一次的單純形表，當(dāng)計(jì)算次數(shù)較多時(shí)，容易造成誤差的積累，直接影響計(jì)算精度和收斂速度。改進(jìn)單純形法的基本計(jì)算步驟和單純形法基本相同，但在上述兩方面有所改進(jìn)。第五十五張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月56在單純形法的迭代過(guò)程中，我們實(shí)際需要的只有以下各項(xiàng)：1、檢驗(yàn)數(shù) ,以判斷是否最優(yōu)或確定換入基變量。2、換入變量所在列的各元素 和基變量的值 ，根據(jù) 決定換出基變量。第五十六張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月57 Min z = CX s.t. AX=b X 0單純形法的矩陣形式第五十七張，PP

19、T共七十三頁(yè)，創(chuàng)作于2022年6月58第五十八張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月59第五十九張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月60在單純形法的矩陣形式中我們可以發(fā)現(xiàn)，單純形表中的其它數(shù)字可利用 和原始系數(shù)進(jìn)行運(yùn)算直接得到：這就是改進(jìn)單純形法的出發(fā)點(diǎn)。令向量Y表示 ，即 稱(chēng)其為單純形乘子。第六十張，PPT共七十三頁(yè)，創(chuàng)作于2022年6月61求解步驟1、第0次迭代：初始可行基 檢驗(yàn)數(shù) 如不是最優(yōu)解，確定換入基，換出基。 2、計(jì)算 ：三種方法 3、計(jì)算第i1次迭代的常數(shù)列和檢驗(yàn)數(shù) 4、最優(yōu)性檢驗(yàn)：如最優(yōu)，結(jié)束。否則下一步。 5、計(jì)算第i1次迭代中的換入列 6、確定第i1次迭代中換出基的下標(biāo)，返回步2。初等變換法取