單純形法-課件

1第二章單純形法

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

2.1單純形法原理2一、基礎(chǔ)定理定理1若線性規(guī)劃問題存在最優(yōu)解，則問題的可行域是凸集。定理2線性規(guī)劃問題的基本可行解對應線性規(guī)劃問題可行域（凸集）的頂點。定理3若線性規(guī)劃問題最優(yōu)解存在，則最優(yōu)解一定在可行域頂點處取得。由此可看出，最優(yōu)解要在基本可行解（可行域頂點）中找。2一、基礎(chǔ)定理定理1若線性規(guī)劃問題存在最優(yōu)解，則問題的可3

若LP問題有最優(yōu)解的話，定在可行域的某頂點處達到，又，一個頂點對應一個基本可行解，一個自然的想法是：找出所有的基本可行解。因基本可行解的個數(shù)有限，通過“枚舉法”，從理論上講總能找出所有的基本可行解。而事實上隨著m，n的增大，解的個數(shù)迅速增大，致使此路行不通。3若LP問題有最優(yōu)解的話，定在可行域的某頂點處達4換一種思路：若從某一基本可行解（今后稱之為初始基本可行解）出發(fā)，每次總是尋找比上一個更“好”的基本可行解，逐步改善，直至最優(yōu)。這需要解決以下三個問題：1.如何找到一個初始的基本可行解。2.如何判別當前的基本可行解是否已達到了最優(yōu)解。3.若當前解不是最優(yōu)解，如何去尋找一個改善了的基本可行解。4換一種思路：若從某一基本可行解（今后稱之為初始基本可行解）5定義：如何從一個可行基找另一個可行基？稱基變換。定義：兩個基本可行解稱為相鄰的，如果它們之間僅變換一個基變量。對應的基稱為相鄰可行基。例LP問題二、思路解析5定義：如何從一個可行基找另一個可行基？稱基變換。定義：兩個6當前可行基{}所對應的基本可行解顯然不是最優(yōu)。因為從經(jīng)濟意義上講，意味著該廠不安排生產(chǎn)，因此沒有利潤。相應地，將代入目標函數(shù)得從數(shù)學角度看，若讓非基變量取值從零增加，(對應可行域的)6當前可行基{}所7相應的目標函數(shù)值Z也將隨之減少。因此有可能找到一個新的基本可行解，使其目標函數(shù)值有所改善。即進行基變換，換一個與它相鄰的基。再注意到前的系數(shù)－2比

前的系數(shù)－1小，即每增加一個單位對Z的貢獻比大。故應讓從非基變量轉(zhuǎn)為基變量，稱為進基。又因為基變量只能有三個，因此必須從原有的基變量中選一個離開基轉(zhuǎn)為非基變量，稱為出基。誰出基？7相應的目標函數(shù)值Z也將隨之減少。因此有可能找到一個新的基本8又因為仍留作非基變量，故仍有（2）式變?yōu)樵僮審牧阍黾樱苋〉玫淖畲笾禐榇藭r，已經(jīng)從24降到了0，達到了非基的取值，變成非基變量。從而得到新的可行基。由此得到一個新的基本可行解：8又因為仍留作非基變量，故仍有（2）式變?yōu)樵僮?目標函數(shù)值：從目標函數(shù)值明顯看出，比明顯地得到了改善。此基本可行解對應可行域的將（2）式（2）可行基留在左邊，非基變量移到右邊9目標函數(shù)值：從目標函數(shù)值明顯看出，比明10（3）用代入法得：（4）10（3）用代入法得：（4）11代入目標函數(shù)得：這一過程用增廣矩陣的行初等變換表示為：×1/6×（-1）×（2）按最小非負比值規(guī)則：主元素11代入目標函數(shù)得：這一過程用增廣矩陣的行初等變換表示為：×12目標函數(shù)系數(shù)行按最小非負比值規(guī)則：12目標函數(shù)系數(shù)行按最小非負比值規(guī)則：13×3/2×（-5）×（-1/3）×（1/3）13×3/2×（-5）×（-1/3）×（1/3）14所對應的LP問題14所對應的LP問題15可行基令非基變量為0，得到最優(yōu)解最優(yōu)值：15可行基令非基變量為0，得到最優(yōu)解最16總結(jié)：①在迭代過程中要保持常數(shù)列向量非負，這能保證基可行解的非負性。最小比值能做到這一點。②主元素不能為0。因為行的初等變換不能把0變成1。③主元素不能為負數(shù)。因為用行的初等變換把負數(shù)變成1會把常數(shù)列中對應的常數(shù)變成負數(shù)。此基本可行解對應可行域的其結(jié)果與圖解法一致。16總結(jié)：①在迭代過程中要保持常數(shù)列向量非負，這能保證基此基17人工變量法（也稱大M法）針對標準形約束條件的系數(shù)矩陣中不含單位矩陣的處理方法。例6用單純形法求解LP問題

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

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

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

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

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

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

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

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

兩階段法用大M法處理人工變量時，若用計算機處理，必須對M給出一個較大的具體數(shù)據(jù)，并視具體情況對M值作適當?shù)恼{(diào)整。為了克服這一麻煩，下面的兩階段法將問題拆成兩個LP問題分兩個階段來計算：2.3大M法和兩階段法41大M法目標是盡快把人工變量從基變量中全部“趕”出去（如果42兩階段法的第一階段求解一個目標中只包含人工變量的LP問題，即令目標函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)（一般取1），在保持原問題約束不變的情況下求這個目標函數(shù)極小化的解。顯然在第一階段中，當人工變量取值為0時，目標函數(shù)值也為0。這時候的最優(yōu)解就是原問題的一個基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原LP問題無可行解。42兩階段法的第一階段求解一個目標中只包含人工變量的LP問題43第二階段：求解原線性規(guī)劃問題的最優(yōu)解。以第一階段的最終單純形表為基礎(chǔ)，去掉人工變量，目標函數(shù)換為原問題的目標函數(shù)，得到第二階段的初始表，繼續(xù)迭代求解。43第二階段：求解原線性規(guī)劃問題的最優(yōu)解。44⑴若求得的單純形矩陣中，所有人工變量都處在非基變量的位置。即及。則從第1階段去掉人工變量后，即為原問題的初始單純形矩陣。并進入第2階段。第一階段求解第一個線性規(guī)劃：44⑴若求得的單純形矩陣中，所有人工變量都處在非基變量第45⑵若第一階段所求得的單純形中仍含有（解）非零的人工變量，則說明原問題無可行解。不再進入第2階段。因此兩階段法的第1階段求解有兩個目的：一為判斷原問題有無可行解。二，若有，則得原問題的一個初始可行基，再對原問題進行第2階段的計算。45⑵若第一階段所求得的單純形中仍含有（解）非零的人工因46對單純形矩陣作初等行變換，有：例：第1階段：46對單純形矩陣作初等行變換，有：例：第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