運籌學對偶單純形法-wenkub
2023-05-21 15:18:23 本頁面
【正文】 在保持對偶可行的前提下進行基變換 —— 每一次迭代過程中取出基變量中的一個負分量 作為換出變量 去替換某個非基變量 (作為換入變量 ), 使原始問題的非可行解向可行解靠近。 若 bi 0 , σ j ≤ 0 , 則用對偶單純形法 進行換基迭代 . 二 對偶單純形法的步驟： 第三步 先確定 換出 變量 解答列（ b 列）中的負元素對應(yīng)的基變量出基， 相應(yīng)的行為主元行。 CB 基 b x1 xl xm xm + 1 xk … xn c1 x1 1b 1 … 0 … 0 a 1 , m + 1 … a 1s … a 1n … … … … … … … … … cl xl lb 0 … 1 … 0 a l , m + 1 … alk … aln … … … … … … … … … cm xm mb 0 0 … 1 a m , m + 1 … a m k … a mn cj－ zj 0 … 0 0 c m + 1－ z m + 1 … ck－ zk … cn－ zn 若有： Min { cj – zj / α lj|α lj 0 , x j 為非基變量 } = ck – zk /α lk 則確定 xk 為換入 變量，相應(yīng)的列為主元列， 標出 主元素 α lk , 應(yīng)用矩陣的初等行變換得到新的單純形表。 初始可行基 例 : 用對偶單純形法求解線性規(guī)劃問題： 0y,y,y 1yy2y5 32132132??????321 y5y24y15wm i n ???0,y 125 26.5215321432????????yyyyyyyyyts?321 52415max yyyw ?????0,y 125 26.5215321432???????????yyyyyyyyyts?321 52415max yyyw ????對偶問題的 初始可行基 2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321??????????????????????????????yyyyyyyyyyybYCBB?jcjj zc ? 換出 4 2)1,2m i n (y? ????換出 min{σ j/α lj|α lj0} 4 5 y2換入變量 2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321??????????????????????????????yyyyyyyyyyybYCBBjj zc ?jj zc ?2/32/7002/152/32
高考資料相關(guān)推薦
鄂ICP備17016276號-1