運籌學第二單純形法

關于運籌學第二單純形法12一、基礎定理定理1若線性規(guī)劃問題存在最優(yōu)解，則問題的可行域是凸集。定理2線性規(guī)劃問題的基本可行解對應線性規(guī)劃問題可行域（凸集）的頂點。定理3若線性規(guī)劃問題最優(yōu)解存在，則最優(yōu)解一定在可行域頂點處取得。由此可看出，最優(yōu)解要在基本可行解（可行域頂點）中找。第2頁,共73頁，星期六，2024年，5月3

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

前的系數－1小，即每增加一個單位對Z的貢獻比大。故應讓從非基變量轉為基變量，稱為進基。又因為基變量只能有三個，因此必須從原有的基變量中選一個離開基轉為非基變量，稱為出基。誰出基？第7頁,共73頁，星期六，2024年，5月8又因為仍留作非基變量，故仍有（2）式變?yōu)樵僮審牧阍黾樱苋〉玫淖畲笾禐榇藭r，已經從24降到了0，達到了非基的取值，變成非基變量。從而得到新的可行基。由此得到一個新的基本可行解：第8頁,共73頁，星期六，2024年，5月9目標函數值：從目標函數值明顯看出，比明顯地得到了改善。此基本可行解對應可行域的將（2）式（2）可行基留在左邊，非基變量移到右邊第9頁,共73頁，星期六，2024年，5月10（3）用代入法得：（4）第10頁,共73頁，星期六，2024年，5月11代入目標函數得：這一過程用增廣矩陣的行初等變換表示為：×1/6×（-1）×（2）按最小非負比值規(guī)則：主元素第11頁,共73頁，星期六，2024年，5月12目標函數系數行按最小非負比值規(guī)則：第12頁,共73頁，星期六，2024年，5月13×3/2×（-5）×（-1/3）×（1/3）第13頁,共73頁，星期六，2024年，5月14所對應的LP問題第14頁,共73頁，星期六，2024年，5月15可行基令非基變量為0，得到最優(yōu)解最優(yōu)值：第15頁,共73頁，星期六，2024年，5月16總結：①在迭代過程中要保持常數列向量非負，這能保證基可行解的非負性。最小比值能做到這一點。②主元素不能為0。因為行的初等變換不能把0變成1。③主元素不能為負數。因為用行的初等變換把負數變成1會把常數列中對應的常數變成負數。此基本可行解對應可行域的其結果與圖解法一致。第16頁,共73頁，星期六，2024年，5月17例2解LP問題：對單純形矩陣作初等行變換，有：按最小非負比值原則：確定主元素。×（-1）×（1）1、無窮多個解三、其他解的情況第17頁,共73頁，星期六，2024年，5月18至此，檢驗行已沒有負數，當前解即為最優(yōu)解。此時對應的LP問題為：0第18頁,共73頁，星期六，2024年，5月19此時對應的LP問題為：0第19頁,共73頁，星期六，2024年，5月20此時對應的LP問題為：01第20頁,共73頁，星期六，2024年，5月21當時，不管取何值，均有目標函數取得最大值1。此時約束方程為：其中為基變量。用非基變量表示出基變量：其中，為自由變量。設為有:其中c是滿足非負性的任意常數。第21頁,共73頁，星期六，2024年，5月22再由的非負性，知：解出（其中）最優(yōu)解為：最優(yōu)值為：第22頁,共73頁，星期六，2024年，5月232、無最優(yōu)解的兩種情況：⑴無界解例3解LP問題：解：對單純形矩陣作初等行變換，有：第23頁,共73頁，星期六，2024年，5月24×1/2×（2）注意到－6所在的列無正元素，將基變量及目標函數用非基變量表示為第24頁,共73頁，星期六，2024年，5月25從目標函數看，若令非基變量無限增大，Z也無限性，即該LP問題所追求的目標函數是無界的，即無最小值，于是該LP問題無最優(yōu)解。減小，且沒有影響的非負第25頁,共73頁，星期六，2024年，5月26⑵無可行解例4求解LP問題解：可行域為空集，無可行解。第26頁,共73頁，星期六，2024年，5月27下面先把此LP問題化為標準型，然后用單純形法求解。對單純形矩陣作初等行變換，有：第27頁,共73頁，星期六，2024年，5月28×1/2從最后一個矩陣可看出，此LP問題無可行基，當然就無可行解?！粒?1）×（-1）×（1）第28頁,共73頁，星期六，2024年，5月29LP當前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（其系數矩陣為單位陣）。⑵檢驗行的基變量系數=0。⑶檢驗行的非基變量系數≥0。全部〉0?唯一解。存在=0?無窮多個解。⑷常數列向量≥0。下面的問題是：所給LP的標準型中約束矩陣中沒有現成的可行基怎么辦？第29頁,共73頁，星期六，2024年，5月30人工變量法（也稱大M法）針對標準形約束條件的系數矩陣中不含單位矩陣的處理方法。例6用單純形法求解LP問題

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

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

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

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

無可行解判別：所有檢驗數≥

0；人工變量≠0(4)無界解判別定理：有一個非基變量的檢驗數＜0,但該數對應的列中沒有正元素；人工變量為0解的判別定理：第37頁,共73頁，星期六，2024年，5月38單純形法步驟一、構造初始可行基1、引入附加變量，化為標準型2、必要時引入人工變量3、目標函數中，附加變量系數為0，人工變量則為M二、求基本可行解1、用非基變量表示基變量和目標函數式2、求出一個基本可行解及相應Z值三、最優(yōu)性檢驗依據:檢驗數及判別定理四、基變換1、換入基的確定：檢驗數負值中最小的2、換出基的確定：最小非負比值規(guī)則返回步驟二第38頁,共73頁，星期六，2024年，5月392.2單純形法的表格形式

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

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

Minz

=

CX

s.t.

AX=b

X

≥0單純形法的矩陣形式第57頁,共73頁，星期六，2024年，5月58第58頁,共73頁，星期六，2024年，5月59第59頁,共73頁，星期六，2024年，5月60在單純形法的矩陣形式中我們可以發(fā)現，單純形表中的其它數字可利用和原始系數進行運算直接得到：這就是改進單純形法的出發(fā)點。令向量Y表示，即稱其為單純形乘子。第60頁,共73頁，星期六，2024年，5月61求解步驟1、第0次迭代：初始可行基檢驗數如不是最優(yōu)解，確定換入基，換出基。

2、計算：三種方法

3、計算第i＋1次迭代的常數列和檢驗數

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

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

6、確定第i＋1次迭代中換出基的下標，返回步2。①初等變換法②取主變換③逆的乘積形式第61頁,共73頁，星期六，2024年，5月62逆的乘積形式

的計算方法已知：；第i