對偶理論和靈敏度分析-第5,6節(jié)運籌學-東北大學,鐘磊鋼(編輯修改稿)
2025-06-20 07:19 本頁面
【文章內(nèi)容簡介】 XB=B1b。 若在 B1b中至少有一個負分量 ， 設 (B1b)i＜ 0， 并且在單純形表的檢驗數(shù)行中的檢驗數(shù)都為非正 ，即對偶問題保持可行解 ， 它的各分量是 ? (1) 對應基變量 x1， x2， …,xm的檢驗數(shù)是 σ i=cizi=ciCBB1Pj=0， i=1,2,…,m ? (2) 對應非基變量 xm+1， …， xn的檢驗數(shù)是 σ j=cjzj=cjCBB1Pj≤0 ， j=m+1,…,n ? 每次迭代是將基變量中的負分量 xl取出 ，去替換非基變量中的 xk， 經(jīng)基變換 ， 所有檢驗數(shù)仍保持非正 。 從原問題來看 ，經(jīng)過每次迭代 ， 原問題由非可行解往可行解靠近 。 當原問題得到可行解時 ， 便得到了最優(yōu)解 。 對偶單純形法的計算步驟如下： ? (1) 根據(jù)線性規(guī)劃問題，列出初始單純形表。 檢查 b列的數(shù)字，若都為非負，檢驗數(shù)都為非正，則已得到最優(yōu)解。停止計算。 若檢查 b列的數(shù)字時，至少還有一個負分量，檢驗數(shù)保持非正，那么進行以下計算。 (2) 確定換出變量 ? 按 min｛ (B1b)i｜ (B1b)i＜ 0＝ (B1b)l對應的基變量xi為換出變量 (3) 確定換入變量 ? 在單純形表中檢查 xl所在行的各系數(shù) α lj(j=1,2,… ，n)。若所有 α lj≥ 0，則無可行解，停止 計算。 若存在 α lj＜ 0 (j=1,2,… ， n), 計算 lkkkljljjjj azcaazc ????????????? 0m i n?按 θ 規(guī)則所對應的列的非基變量 xk為換入變量， 這樣才能保持得到的對偶問題解仍為可行解。 ? (4) 以 α lk為主元素 ， 按原單純形法在表中進行迭代運算 ， 得到新的計算表 。 ? 重復步驟 (1)～ (4)。 例 6 用對偶單純形法求解
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1