運籌學1.4單純形法進一步討論課件

1、1.4 單純形算法的進一步討論,(一)、大M法 (二)、兩階段法,初始基本可行解的求法,解: 令S= - S 加入松弛變量x4, 剩余變量x5,-M x6-M x7,再加入人工變量x6 ,x7,(一)、大M法 例,所有 j 0，X* = ( 4, 1, 9, 0, 0, 0, 0 )T Z = 2 Z= -2,判定無解條件： 當進行到最優(yōu)表時，仍有人工變量在基中，且0，則說明原問題無可行解。,例1.12用兩階段法求解L.P的最優(yōu)解:,解:加入松弛變量、剩余變量、 人工變量： x6 , x7 第一階段的L.P問題,min W= x6 +x7 = max W= - x6 -x7,(二)、兩階段法-

2、例,開始第二階段的計算,兩階段法步驟,第1階段：解輔助問題，當進行到最優(yōu)表時,、若W=0, 則得到原問題的一個基本可行 解，轉(zhuǎn)入第2階段。,第2階段：用求出的初始基可行解求最優(yōu)解。,、若W0, 則判定原問題無可行解,例:,原問題無可行解,第1階段 最優(yōu)基B* Min = *,(1)、 *0 原問題無可行解,(2)、 * =0 yi 0( i=1,2, ,m), B* 基變量無人工變量,進入第2階段,1) arj 全 =0 () 式多余方程,arj 有0 元，設為ars 0 以ars為主元，換基迭代，最后得到,兩階段法解的判別,例、求,0 0 0 0 1 1 1 CB XB b x1 x2 x3

3、 x4 y1 y2 y3 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 3/4 0 0 1 0 1 y3 0 3 6 0 4 0 0 1 -5 -5 5 -5/4 -10/3 0 0 0 1 y1 2 0 2 1/2 -4/3 1 0 -1/6 1 y2 3 0 3 3/4 2 0 1 -1/2 0 X1 0 1 -2 0 4/3 0 0 1/3 -5 0 -5 -4/5 10/3 0 0 5/3,第 一 階 段,一,二,的特殊情況:第1階段結(jié)束時,有人工變量在基中取0, 但xi系數(shù)全為0,此方程為多余方程。,例:求,x2 1 0 1 1/4 -2/3 1/2 0 -1/2 y2 0 0 0 -5/4 0 -3/2 1 -1/4 x1 2 1 0 1/2 0 1 0 1/6 0 0 0 5/4 0 5/2 0 5/4 x2 1 0 1 0 -2/3 1/5 1/5 -2/15 x3 0 0 0 1 0 1/5 -4/5 1/5 x1 2 1 0 0 0 2/5 2/5 1/15 0 0 0 0 0 1 1 1,第 一 階 段,三,四,的特殊情況，可將人工變量換出,arj 有0 元,以ars為主元，換基迭代，最后得到,(1)、L.P數(shù)學模型及標準型,(2)、L.P問題解的性質(zhì)：圖解法,總結(jié),(3)、單純形法：,1)、標準型中有