資源描述：
《大M法和兩階段法.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、LP當前解已是最優(yōu)的四大特征：⑴存在一組(初始)可行基（其系數(shù)矩陣為單位陣）。⑵檢驗數(shù)行的基變量系數(shù)=0。⑶檢驗行的非基變量系數(shù)≤0。全部唯一解。存在無窮多個解。⑷常數(shù)列向量≥0。Q:所給LP的標準型中約束矩陣中沒有現(xiàn)成的可行基怎么辦？1.5.2單純形的進一步討論例解下列線性規(guī)劃解:先化為標準形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。x5可作為一個基變量，第一、三約束中分別加入人工變量x6、x7，得說明：①不易接受。因為是強行引進，稱為人工變量。它們與不一樣。稱為松弛變量和剩余變量，是為了將不等式改寫為等式而引進的，而
2、改寫前后兩個約束是等價的。②人工變量的引入一般來說是前后不等價的。只有當最優(yōu)解中，人工變量都取值零時（此時人工變量實質上就不存在了）才可認為兩個問題的最優(yōu)解是相同的。處理辦法：把人工變量從基變量中“趕”出去使其變?yōu)榉腔兞浚郧蟪鲈瓎栴}的初始基本可行解。結論1.若新LP的最優(yōu)解中，人工變量都處在非基變量位置（即取零值）時，原LP有最優(yōu)解。2.若新LP的最優(yōu)解中，包含有非零的人工變量，則原LP無可行解。3.若新LP的最優(yōu)解的基變量中，包含有人工變量，但該人工變量取值為零。這時可將某個非基變量引入基變量中來替換該人工變量，從而得到原
3、LP的最優(yōu)解。以X(0)作初始基本可行解進行迭代時，怎樣才能較快地將所有的人工變量從基變量中全部“趕”出去（如果能全部“趕”出去的話）。這會影響到得到最優(yōu)解的迭代次數(shù)。－－大M法與兩階段法例1-20用大M法解下列線性規(guī)劃1.大M法解:先化為標準形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。目標函數(shù)修改為：其中M為任意大的實數(shù)，“-M”稱為“罰因子”。Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M 0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2
4、M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3最優(yōu)解X＝（31/3，13，19/3，0，0)T；最優(yōu)值Z＝152/3例1-21求解線性規(guī)劃解:化為標準型加入人工變量x5，得用單純形法計算如下表所示。Cj5－800MbCBXBx1x2
5、x3x4x50Mx3x5[3]11－2100－1016→4λj5－M↑－8+2M0M05Mx1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0最優(yōu)解X=（2，0，0，0，2），Z=10+2M。大M法小結：（1）求極大值時，目標函數(shù)變?yōu)椋?）求極小值時，目標函數(shù)變?yōu)橛糜嬎銠C求解時，不容易確定M的取值，且M過大容易引起計算誤差。不足：最優(yōu)解中含有人工變量x5≠0說明這個解不是最優(yōu)解，是不可行的，因此原問題無可行解。2.兩階段法約束條件是加入人工變量后的約束方程。用大M法處理人工變量，
6、在計算機求解時，對M只能在計算機內(nèi)輸入一個機器最大字長的數(shù)字。這有時可能使計算結果發(fā)生錯誤。為克服這個困難，可以對添加人工變量的線性規(guī)劃問題分兩階段來求解——稱為兩階段法。將LP的求解過程分成兩個階段：第一階段：求解第一個LP：第一個LP的結果有三種可能情形：1.最優(yōu)值,且人工變量皆為非基變量。從第一階段的最優(yōu)解中去掉人工變量后，即為原LP的一個基本可行解。作為原LP的一個初始基本可行解，再求原問題，從而進入第二階段。2.最優(yōu)值,說明至少有一個人工變量不為零。原LP無可行解。不再需要進入第二個階段計算。3.最優(yōu)值,且存在人工變量
7、為基變量，但取值為零，把某個非基變量與該人工變量進行調換。兩階段法的第一階段求解的目的：1.判斷原LP有無可行解。2.若有，則可得原LP的一個初始基本可行解，再對原LP進行第二階段的計算。例1-22用兩階段單純形法求解例20的線性規(guī)劃。用單純形法求解，得到第一階段問題的計算表如下：目標函數(shù)為人工變量之和加入人工變量的約束條件第一階段問題為解:標準型為Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7－4123－1－212[1]－1000101000014101→λj2－1－2↑1000100x6x5x3－
8、6－32[5]3－2001－1000101003→81λj6－5↑0100000x2x5x3－6/53/5－2/5100001－1/53/5－2/50103/531/511/5λj00000最優(yōu)解為，最優(yōu)值w=0。原問題目標函數(shù)第二階段問題為說明找到了原問題的一
