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

關(guān)于運(yùn)籌學(xué)第二單純形法第一頁(yè)，共七十三頁(yè)，2022年，8月28日1一、基礎(chǔ)定理定理1若線性規(guī)劃問題存在最優(yōu)解，則問題的可行域是凸集。定理2線性規(guī)劃問題的基本可行解對(duì)應(yīng)線性規(guī)劃問題可行域（凸集）的頂點(diǎn)。定理3若線性規(guī)劃問題最優(yōu)解存在，則最優(yōu)解一定在可行域頂點(diǎn)處取得。由此可看出，最優(yōu)解要在基本可行解（可行域頂點(diǎn)）中找。第二頁(yè)，共七十三頁(yè)，2022年，8月28日2

若LP問題有最優(yōu)解的話，定在可行域的某頂點(diǎn)處達(dá)到，又，一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)基本可行解，一個(gè)自然的想法是：找出所有的基本可行解。因基本可行解的個(gè)數(shù)有限，通過“枚舉法”，從理論上講總能找出所有的基本可行解。而事實(shí)上隨著m，n的增大，解的個(gè)數(shù)迅速增大，致使此路行不通。第三頁(yè)，共七十三頁(yè)，2022年，8月28日3換一種思路：若從某一基本可行解（今后稱之為初始基本可行解）出發(fā)，每次總是尋找比上一個(gè)更“好”的基本可行解，逐步改善，直至最優(yōu)。這需要解決以下三個(gè)問題：1.如何找到一個(gè)初始的基本可行解。2.如何判別當(dāng)前的基本可行解是否已達(dá)到了最優(yōu)解。3.若當(dāng)前解不是最優(yōu)解，如何去尋找一個(gè)改善了的基本可行解。第四頁(yè)，共七十三頁(yè)，2022年，8月28日4定義：如何從一個(gè)可行基找另一個(gè)可行基？稱基變換。定義：兩個(gè)基本可行解稱為相鄰的，如果它們之間僅變換一個(gè)基變量。對(duì)應(yīng)的基稱為相鄰可行基。例LP問題二、思路解析第五頁(yè)，共七十三頁(yè)，2022年，8月28日5當(dāng)前可行基{}所對(duì)應(yīng)的基本可行解顯然不是最優(yōu)。因?yàn)閺慕?jīng)濟(jì)意義上講，意味著該廠不安排生產(chǎn)，因此沒有利潤(rùn)。相應(yīng)地，將代入目標(biāo)函數(shù)得從數(shù)學(xué)角度看，若讓非基變量取值從零增加，(對(duì)應(yīng)可行域的)第六頁(yè)，共七十三頁(yè)，2022年，8月28日6相應(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)為基變量，稱為進(jìn)基。又因?yàn)榛兞恐荒苡腥齻€(gè)，因此必須從原有的基變量中選一個(gè)離開基轉(zhuǎn)為非基變量，稱為出基。誰(shuí)出基？第七頁(yè)，共七十三頁(yè)，2022年，8月28日7又因?yàn)槿粤糇鞣腔兞?，故仍有?）式變?yōu)樵僮審牧阍黾?，能取得的最大值為此時(shí)，已經(jīng)從24降到了0，達(dá)到了非基的取值，變成非基變量。從而得到新的可行基。由此得到一個(gè)新的基本可行解：第八頁(yè)，共七十三頁(yè)，2022年，8月28日8目標(biāo)函數(shù)值：從目標(biāo)函數(shù)值明顯看出，比明顯地得到了改善。此基本可行解對(duì)應(yīng)可行域的將（2）式（2）可行基留在左邊，非基變量移到右邊第九頁(yè)，共七十三頁(yè)，2022年，8月28日9（3）用代入法得：（4）第十頁(yè)，共七十三頁(yè)，2022年，8月28日10代入目標(biāo)函數(shù)得：這一過程用增廣矩陣的行初等變換表示為：×1/6×（-1）×（2）按最小非負(fù)比值規(guī)則：主元素第十一頁(yè)，共七十三頁(yè)，2022年，8月28日11目標(biāo)函數(shù)系數(shù)行按最小非負(fù)比值規(guī)則：第十二頁(yè)，共七十三頁(yè)，2022年，8月28日12×3/2×（-5）×（-1/3）×（1/3）第十三頁(yè)，共七十三頁(yè)，2022年，8月28日13所對(duì)應(yīng)的LP問題第十四頁(yè)，共七十三頁(yè)，2022年，8月28日14可行基令非基變量為0，得到最優(yōu)解最優(yōu)值：第十五頁(yè)，共七十三頁(yè)，2022年，8月28日15總結(jié)：①在迭代過程中要保持常數(shù)列向量非負(fù)，這能保證基可行解的非負(fù)性。最小比值能做到這一點(diǎn)。②主元素不能為0。因?yàn)樾械某醯茸儞Q不能把0變成1。③主元素不能為負(fù)數(shù)。因?yàn)橛眯械某醯茸儞Q把負(fù)數(shù)變成1會(huì)把常數(shù)列中對(duì)應(yīng)的常數(shù)變成負(fù)數(shù)。此基本可行解對(duì)應(yīng)可行域的其結(jié)果與圖解法一致。第十六頁(yè)，共七十三頁(yè)，2022年，8月28日16例2解LP問題：對(duì)單純形矩陣作初等行變換，有：按最小非負(fù)比值原則：確定主元素?！粒?1）×（1）1、無窮多個(gè)解三、其他解的情況第十七頁(yè)，共七十三頁(yè)，2022年，8月28日17至此，檢驗(yàn)行已沒有負(fù)數(shù)，當(dāng)前解即為最優(yōu)解。此時(shí)對(duì)應(yīng)的LP問題為：0第十八頁(yè)，共七十三頁(yè)，2022年，8月28日18此時(shí)對(duì)應(yīng)的LP問題為：0第十九頁(yè)，共七十三頁(yè)，2022年，8月28日19此時(shí)對(duì)應(yīng)的LP問題為：01第二十頁(yè)，共七十三頁(yè)，2022年，8月28日20當(dāng)時(shí)，不管取何值，均有目標(biāo)函數(shù)取得最大值1。此時(shí)約束方程為：其中為基變量。用非基變量表示出基變量：其中，為自由變量。設(shè)為有:其中c是滿足非負(fù)性的任意常數(shù)。第二十一頁(yè)，共七十三頁(yè)，2022年，8月28日21再由的非負(fù)性，知：解出（其中）最優(yōu)解為：最優(yōu)值為：第二十二頁(yè)，共七十三頁(yè)，2022年，8月28日222、無最優(yōu)解的兩種情況：⑴無界解例3解LP問題：解：對(duì)單純形矩陣作初等行變換，有：第二十三頁(yè)，共七十三頁(yè)，2022年，8月28日23×1/2×（2）注意到－6所在的列無正元素，將基變量及目標(biāo)函數(shù)用非基變量表示為第二十四頁(yè)，共七十三頁(yè)，2022年，8月28日24從目標(biāo)函數(shù)看，若令非基變量無限增大，Z也無限性，即該LP問題所追求的目標(biāo)函數(shù)是無界的，即無最小值，于是該LP問題無最優(yōu)解。減小，且沒有影響的非負(fù)第二十五頁(yè)，共七十三頁(yè)，2022年，8月28日25⑵無可行解例4求解LP問題解：可行域?yàn)榭占?，無可行解。第二十六頁(yè)，共七十三頁(yè)，2022年，8月28日26下面先把此LP問題化為標(biāo)準(zhǔn)型，然后用單純形法求解。對(duì)單純形矩陣作初等行變換，有：第二十七頁(yè)，共七十三頁(yè)，2022年，8月28日27×1/2從最后一個(gè)矩陣可看出，此LP問題無可行基，當(dāng)然就無可行解。×（-1）×（-1）×（1）第二十八頁(yè)，共七十三頁(yè)，2022年，8月28日28LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（其系數(shù)矩陣為單位陣）。⑵檢驗(yàn)行的基變量系數(shù)=0。⑶檢驗(yàn)行的非基變量系數(shù)≥0。全部〉0?唯一解。存在=0?無窮多個(gè)解。⑷常數(shù)列向量≥0。下面的問題是：所給LP的標(biāo)準(zhǔn)型中約束矩陣中沒有現(xiàn)成的可行基怎么辦？第二十九頁(yè)，共七十三頁(yè)，2022年，8月28日29人工變量法（也稱大M法）針對(duì)標(biāo)準(zhǔn)形約束條件的系數(shù)矩陣中不含單位矩陣的處理方法。例6用單純形法求解LP問題

單純形的進(jìn)一步討論第三十頁(yè)，共七十三頁(yè)，2022年，8月28日30解：先將其化為標(biāo)準(zhǔn)形式再?gòu)?qiáng)行加上人工變量，使其出現(xiàn)單位矩陣：第三十一頁(yè)，共七十三頁(yè)，2022年，8月28日31但這樣處理后：①不易接受。因?yàn)槭菑?qiáng)行引進(jìn)，稱為人工變量。它們與不一樣。稱為松弛變量和剩余變量，是為了將不等式改寫為等式而引進(jìn)的，而改寫前后兩個(gè)約束是等價(jià)的。②人工變量的引入一般來說是前后不等價(jià)的。只有當(dāng)最優(yōu)解中，人工變量都取值零時(shí)（此時(shí)人工變量實(shí)質(zhì)上就不存在了）才可認(rèn)為它們是等價(jià)的。處理辦法：把人工變量從基變量中趕出來使其變?yōu)榉腔兞?。為此，發(fā)明者建議把目標(biāo)函數(shù)作如下處理：第三十二頁(yè)，共七十三頁(yè)，2022年，8月28日32其中M為任意大的實(shí)數(shù)，“M”稱為“罰因子”。用意：只要人工變量取值大于零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最優(yōu)。對(duì)此單純形矩陣作初等行變換，有：第三十三頁(yè)，共七十三頁(yè)，2022年，8月28日33×－M×－M×（-1）×（-3）×（4M）×1/6第三十四頁(yè)，共七十三頁(yè)，2022年，8月28日34×3/2×（-1/3）×（3）第三十五頁(yè)，共七十三頁(yè)，2022年，8月28日35至此，檢驗(yàn)行已沒有負(fù)數(shù)，當(dāng)前解即為最優(yōu)解。最優(yōu)值為：去掉人工變量，即得原LP問題的最優(yōu)解：第三十六頁(yè)，共七十三頁(yè)，2022年，8月28日36⑴

最優(yōu)解判別定理：所有檢驗(yàn)數(shù)≥0；人工變量為0⑵

無窮多最優(yōu)解判別定理：所有檢驗(yàn)數(shù)≥

0；人工變量為0；存在某個(gè)非基變量的檢驗(yàn)數(shù)為0⑶

無可行解判別：所有檢驗(yàn)數(shù)≥

0；人工變量≠0(4)無界解判別定理：有一個(gè)非基變量的檢驗(yàn)數(shù)＜0,但該數(shù)對(duì)應(yīng)的列中沒有正元素；人工變量為0解的判別定理：第三十七頁(yè)，共七十三頁(yè)，2022年，8月28日37單純形法步驟一、構(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ī)則返回步驟二第三十八頁(yè)，共七十三頁(yè)，2022年，8月28日382.2單純形法的表格形式

書例2.1P18第三十九頁(yè)，共七十三頁(yè)，2022年，8月28日39作業(yè)P791.3（2），1.7（1）第四十頁(yè)，共七十三頁(yè)，2022年，8月28日40大M法目標(biāo)是盡快把人工變量從基變量中全部“趕”出去（如果能全部“趕”出去的話）。所用方法除了大M法外，還有下面的兩階段法。

兩階段法用大M法處理人工變量時(shí)，若用計(jì)算機(jī)處理，必須對(duì)M給出一個(gè)較大的具體數(shù)據(jù)，并視具體情況對(duì)M值作適當(dāng)?shù)恼{(diào)整。為了克服這一麻煩，下面的兩階段法將問題拆成兩個(gè)LP問題分兩個(gè)階段來計(jì)算：2.3大M法和兩階段法第四十一頁(yè)，共七十三頁(yè)，2022年，8月28日41兩階段法的第一階段求解一個(gè)目標(biāo)中只包含人工變量的LP問題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)（一般取1），在保持原問題約束不變的情況下求這個(gè)目標(biāo)函數(shù)極小化的解。顯然在第一階段中，當(dāng)人工變量取值為0時(shí)，目標(biāo)函數(shù)值也為0。這時(shí)候的最優(yōu)解就是原問題的一個(gè)基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原LP問題無可行解。第四十二頁(yè)，共七十三頁(yè)，2022年，8月28日42第二階段：求解原線性規(guī)劃問題的最優(yōu)解。以第一階段的最終單純形表為基礎(chǔ)，去掉人工變量，目標(biāo)函數(shù)換為原問題的目標(biāo)函數(shù)，得到第二階段的初始表，繼續(xù)迭代求解。第四十三頁(yè)，共七十三頁(yè)，2022年，8月28日43⑴若求得的單純形矩陣中，所有人工變量都處在非基變量的位置。即及。則從第1階段去掉人工變量后，即為原問題的初始單純形矩陣。并進(jìn)入第2階段。第一階段求解第一個(gè)線性規(guī)劃：第四十四頁(yè)，共七十三頁(yè)，2022年，8月28日44⑵若第一階段所求得的單純形中仍含有（解）非零的人工變量，則說明原問題無可行解。不再進(jìn)入第2階段。因此兩階段法的第1階段求解有兩個(gè)目的：一為判斷原問題有無可行解。二，若有，則得原問題的一個(gè)初始可行基，再對(duì)原問題進(jìn)行第2階段的計(jì)算。第四十五頁(yè)，共七十三頁(yè)，2022年，8月28日45對(duì)單純形矩陣作初等行變換，有：例：第1階段：第四十六頁(yè)，共七十三頁(yè)，2022年，8月28日46×（-1）×（-1）第四十七頁(yè)，共七十三頁(yè)，2022年，8月28日47×（-3）×（4）×1/6×（-1）第四十八頁(yè)，共七十三頁(yè)，2022年，8月28日48×（-3）×（6）×2轉(zhuǎn)入第2階段：3-1×（-3）第四十九頁(yè)，共七十三頁(yè)，2022年，8月28日49×3/2×（-1/3）×（3）第五十頁(yè)，共七十三頁(yè)，2022年，8月28日50書例：表格形式大M法:P25表2.2.1兩階段法:P27表；第五十一頁(yè)，共七十三頁(yè)，2022年，8月28日51作業(yè)P801.8（1）第五十二頁(yè)，共七十三頁(yè)，2022年，8月28日522.4退化問題退化問題：按最小比值θ來確定換出基變量時(shí)，有時(shí)出現(xiàn)兩個(gè)以上相同的最小比值，從而使下一個(gè)表的基可行解中出現(xiàn)一個(gè)或多個(gè)基變量等于零的退化解。循環(huán)問題：退化解出現(xiàn)的原因是模型中存在多余的約束，使多個(gè)基可行解對(duì)應(yīng)同一個(gè)頂點(diǎn)。當(dāng)存在退化解時(shí)，就有可能出現(xiàn)迭代計(jì)算的循環(huán)。即從一個(gè)可行基經(jīng)有限次迭代后又回到原來的可行基。盡管可能性及其微小（直到目前為止，還沒有見到一個(gè)實(shí)際應(yīng)用問題產(chǎn)生循環(huán)的例子），但在理論上講是存在的。第五十三頁(yè)，共七十三頁(yè)，2022年，8月28日53E.Beale曾給出一個(gè)循環(huán)的例子這個(gè)例子用單純形法經(jīng)過6次迭代后，又回到了初始狀態(tài)，得不到最優(yōu)解。有興趣的同學(xué)可自行用單純形法驗(yàn)證本題產(chǎn)生的循環(huán)現(xiàn)象。而實(shí)際上本題有最優(yōu)解。解決方法：攝動(dòng)法；勃蘭特法。第五十四頁(yè)，共七十三頁(yè)，2022年，8月28日542.5改進(jìn)單純形法單純形法計(jì)算的特點(diǎn)是每迭代一次，就要把整個(gè)單純形表重新計(jì)算一遍。從計(jì)算機(jī)的角度來講，單純形法并不是一種經(jīng)濟(jì)高效的方法。首先是要占用大量的存貯空間，其次，由于每次計(jì)算都利用上一次的單純形表，當(dāng)計(jì)算次數(shù)較多時(shí)，容易造成誤差的積累，直接影響計(jì)算精度和收斂速度。改進(jìn)單純形法的基本計(jì)算步驟和單純形法基本相同，但在上述兩方面有所改進(jìn)。第五十五頁(yè)，共七十三頁(yè)，2022年，8月28日55在單純形法的迭代過程中，我們實(shí)際需要的只有以下各項(xiàng)：1、檢驗(yàn)數(shù),以判斷是否最優(yōu)或確定換入基變量。2、換入變量所在列的各元素和基變量的值，根據(jù)決定換出基變量。第五十六頁(yè)，共七十三頁(yè)，2022年，8月28日56

Minz

=

CX

s.t.

AX=b

X

≥0單純形法的矩陣形式第五十七頁(yè)，共七十三頁(yè)，2022年，8月28日57第五十八頁(yè)，共七十三頁(yè)，2022年，8月28日58第五十九頁(yè)，共七十三頁(yè)，2022年，8月28日59在單純形法的矩陣形式中我們可以發(fā)現(xiàn)，單純形表中的其它數(shù)字可利用和原始系數(shù)進(jìn)行運(yùn)算直接得到：這就是改進(jìn)單純形法的出發(fā)點(diǎn)。令向量Y表示，即稱其為單純形乘子。第六十頁(yè)，共七十三頁(yè)，2022年，8月28日60求解步驟1、第0次迭代：初始可行基檢驗(yàn)數(shù)如不是最優(yōu)解，確定換入基，換出基。

2、計(jì)算：三種方法

3、計(jì)算第i＋1次迭代的常數(shù)列和檢驗(yàn)數(shù)

4、最優(yōu)性檢驗(yàn)：如最優(yōu)，結(jié)束。否則下一步。

5、計(jì)算第i＋1次迭代中的換入列

6、確定第i＋1次迭代中換出基的下標(biāo)，返回步2。①初等變換法②取主變換③逆的乘積形式第六十一頁(yè)，