單純形法-課件

1第二章單純形法

2.1單純形法原理1第二章單純形法

2.1單純形法原理2一、基礎(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)）中找。2一、基礎(chǔ)定理定理1若線性規(guī)劃問題存在最優(yōu)解，則問題的可3

若LP問題有最優(yōu)解的話，定在可行域的某頂點(diǎn)處達(dá)到，又，一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)基本可行解，一個(gè)自然的想法是：找出所有的基本可行解。因基本可行解的個(gè)數(shù)有限，通過“枚舉法”，從理論上講總能找出所有的基本可行解。而事實(shí)上隨著m，n的增大，解的個(gè)數(shù)迅速增大，致使此路行不通。3若LP問題有最優(yōu)解的話，定在可行域的某頂點(diǎn)處達(dá)4換一種思路：若從某一基本可行解（今后稱之為初始基本可行解）出發(fā)，每次總是尋找比上一個(gè)更“好”的基本可行解，逐步改善，直至最優(yōu)。這需要解決以下三個(gè)問題：1.如何找到一個(gè)初始的基本可行解。2.如何判別當(dāng)前的基本可行解是否已達(dá)到了最優(yōu)解。3.若當(dāng)前解不是最優(yōu)解，如何去尋找一個(gè)改善了的基本可行解。4換一種思路：若從某一基本可行解（今后稱之為初始基本可行解）5定義：如何從一個(gè)可行基找另一個(gè)可行基？稱基變換。定義：兩個(gè)基本可行解稱為相鄰的，如果它們之間僅變換一個(gè)基變量。對(duì)應(yīng)的基稱為相鄰可行基。例LP問題二、思路解析5定義：如何從一個(gè)可行基找另一個(gè)可行基？稱基變換。定義：兩個(gè)6當(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)可行域的)6當(dāng)前可行基{}所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)為基變量，稱為進(jìn)基。又因?yàn)榛兞恐荒苡腥齻€(gè)，因此必須從原有的基變量中選一個(gè)離開基轉(zhuǎn)為非基變量，稱為出基。誰(shuí)出基？7相應(yīng)的目標(biāo)函數(shù)值Z也將隨之減少。因此有可能找到一個(gè)新的基本8又因?yàn)槿粤糇鞣腔兞?，故仍有?）式變?yōu)樵僮審牧阍黾?，能取得的最大值為此時(shí)，已經(jīng)從24降到了0，達(dá)到了非基的取值，變成非基變量。從而得到新的可行基。由此得到一個(gè)新的基本可行解：8又因?yàn)槿粤糇鞣腔兞浚嗜杂校?）式變?yōu)樵僮?目標(biāo)函數(shù)值：從目標(biāo)函數(shù)值明顯看出，比明顯地得到了改善。此基本可行解對(duì)應(yīng)可行域的將（2）式（2）可行基留在左邊，非基變量移到右邊9目標(biāo)函數(shù)值：從目標(biāo)函數(shù)值明顯看出，比明10（3）用代入法得：（4）10（3）用代入法得：（4）11代入目標(biāo)函數(shù)得：這一過程用增廣矩陣的行初等變換表示為：×1/6×（-1）×（2）按最小非負(fù)比值規(guī)則：主元素11代入目標(biāo)函數(shù)得：這一過程用增廣矩陣的行初等變換表示為：×12目標(biāo)函數(shù)系數(shù)行按最小非負(fù)比值規(guī)則：12目標(biāo)函數(shù)系數(shù)行按最小非負(fù)比值規(guī)則：13×3/2×（-5）×（-1/3）×（1/3）13×3/2×（-5）×（-1/3）×（1/3）14所對(duì)應(yīng)的LP問題14所對(duì)應(yīng)的LP問題15可行基令非基變量為0，得到最優(yōu)解最優(yōu)值：15可行基令非基變量為0，得到最優(yōu)解最16總結(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é)果與圖解法一致。16總結(jié)：①在迭代過程中要保持常數(shù)列向量非負(fù)，這能保證基此基17人工變量法（也稱大M法）針對(duì)標(biāo)準(zhǔn)形約束條件的系數(shù)矩陣中不含單位矩陣的處理方法。例6用單純形法求解LP問題

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

最優(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)的列中沒有正元素；人工變量為0解的判別定理：24⑴最優(yōu)解判別定理：所有檢驗(yàn)數(shù)≥0；人工變量為0⑵25單純形法步驟一、構(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ī)則返回步驟二25單純形法步驟一、構(gòu)造初始可行基26例2解LP問題：對(duì)單純形矩陣作初等行變換，有：按最小非負(fù)比值原則：確定主元素。×（-1）×（1）1、無(wú)窮多個(gè)解三、其他解的情況26例2解LP問題：對(duì)單純形矩陣作初等行變換，有：按最小27至此，檢驗(yàn)行已沒有負(fù)數(shù)，當(dāng)前解即為最優(yōu)解。此時(shí)對(duì)應(yīng)的LP問題為：027至此，檢驗(yàn)行已沒有負(fù)數(shù)，此時(shí)對(duì)應(yīng)的LP問題為：028此時(shí)對(duì)應(yīng)的LP問題為：028此時(shí)對(duì)應(yīng)的LP問題為：029此時(shí)對(duì)應(yīng)的LP問題為：0129此時(shí)對(duì)應(yīng)的LP問題為：0130當(dāng)時(shí)，不管取何值，均有目標(biāo)函數(shù)取得最大值1。此時(shí)約束方程為：其中為基變量。用非基變量表示出基變量：其中，為自由變量。設(shè)為有:其中c是滿足非負(fù)性的任意常數(shù)。30當(dāng)時(shí)，不管取何值，均有目標(biāo)函數(shù)取得最大值1。31再由的非負(fù)性，知：解出（其中）最優(yōu)解為：最優(yōu)值為：-131再由的非負(fù)性，知：解出（其中322、無(wú)最優(yōu)解的兩種情況：⑴無(wú)界解例3解LP問題：解：對(duì)單純形矩陣作初等行變換，有：322、無(wú)最優(yōu)解的兩種情況：⑴無(wú)界解例3解LP問題33×1/2×（2）注意到－6所在的列無(wú)正元素，將基變量及目標(biāo)函數(shù)用非基變量表示為33×1/2×（2）注意到－6所在的列無(wú)正元34從目標(biāo)函數(shù)看，若令非基變量無(wú)限增大，Z也無(wú)限性，即該LP問題所追求的目標(biāo)函數(shù)是無(wú)界的，即無(wú)最小值，于是該LP問題無(wú)最優(yōu)解。減小，且沒有影響的非負(fù)34從目標(biāo)函數(shù)看，若令非基變量無(wú)限增大，Z也無(wú)限性，即該LP35⑵無(wú)可行解例4求解LP問題解：可行域?yàn)榭占瑹o(wú)可行解。35⑵無(wú)可行解例4求解LP問題解：可行域?yàn)榭占瑹o(wú)可36下面先把此LP問題化為標(biāo)準(zhǔn)型，然后用單純形法大M求解。對(duì)單純形矩陣作初等行變換，有：36下面先把此LP問題化為標(biāo)準(zhǔn)型，然后用單純形法大M求解。對(duì)37從最后一個(gè)矩陣可看出，此LP問題無(wú)可行基，當(dāng)然就無(wú)可行解。37從最后一個(gè)矩陣可看出，此LP問題無(wú)可行基，當(dāng)然就無(wú)38LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（其系數(shù)矩陣為單位陣）。⑵檢驗(yàn)行的基變量系數(shù)=0。⑶檢驗(yàn)行的非基變量系數(shù)≥0。全部〉0?唯一解。存在=0?無(wú)窮多個(gè)解。⑷常數(shù)列向量≥0。下面的問題是：所給LP的標(biāo)準(zhǔn)型中約束矩陣中沒有現(xiàn)成的可行基怎么辦？38LP當(dāng)前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行392.2單純形法的表格形式

書例2.1P18表格：P25392.2單純形法的表格形式

書例2.1P40作業(yè)P791.3（2），1.7（1）40作業(yè)41大M法目標(biāo)是盡快把人工變量從基變量中全部“趕”出去（如果能全部“趕”出去的話）。所用方法除了大M法外，還有下面的兩階段法。

兩階段法用大M法處理人工變量時(shí)，若用計(jì)算機(jī)處理，必須對(duì)M給出一個(gè)較大的具體數(shù)據(jù)，并視具體情況對(duì)M值作適當(dāng)?shù)恼{(diào)整。為了克服這一麻煩，下面的兩階段法將問題拆成兩個(gè)LP問題分兩個(gè)階段來(lái)計(jì)算：2.3大M法和兩階段法41大M法目標(biāo)是盡快把人工變量從基變量中全部“趕”出去（如果42兩階段法的第一階段求解一個(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問題無(wú)可行解。42兩階段法的第一階段求解一個(gè)目標(biāo)中只包含人工變量的LP問題43第二階段：求解原線性規(guī)劃問題的最優(yōu)解。以第一階段的最終單純形表為基礎(chǔ)，去掉人工變量，目標(biāo)函數(shù)換為原問題的目標(biāo)函數(shù)，得到第二階段的初始表，繼續(xù)迭代求解。43第二階段：求解原線性規(guī)劃問題的最優(yōu)解。44⑴若求得的單純形矩陣中，所有人工變量都處在非基變量的位置。即及。則從第1階段去掉人工變量后，即為原問題的初始單純形矩陣。并進(jìn)入第2階段。第一階段求解第一個(gè)線性規(guī)劃：44⑴若求得的單純形矩陣中，所有人工變量都處在非基變量第45⑵若第一階段所求得的單純形中仍含有（解）非零的人工變量，則說明原問題無(wú)可行解。不再進(jìn)入第2階段。因此兩階段法的第1階段求解有兩個(gè)目的：一為判斷原問題有無(wú)可行解。二，若有，則得原問題的一個(gè)初始可行基，再對(duì)原問題進(jìn)行第2階段的計(jì)算。45⑵若第一階段所求得的單純形中仍含有（解）非零的人工因46對(duì)單純形矩陣作初等行變換，有：例：第1階段：46對(duì)單純形矩陣作初等行變換，有：例：第1階段：47×（-1）×（-1）47×（-1）×（-1）48×（-3）×（4）×1/6×（-1）48×（-3）×（4）×1/6×（-1）49×（-3）×（6）×2轉(zhuǎn)入第2階段：3-1×（-3）49×（-3）×（6）×2轉(zhuǎn)入第2階段：3-1×（-3）50×3/2×（-1/3）×（3）50×3/2×（-1/3）×（3）51書例：表格形式大M法:P25表2.2.1兩階段法:P27表2.3.1；2.3.251書例：表格形式大M法:P25表2.2.152作業(yè)P801.8（1）52作業(yè)532.5