對偶理論和靈敏度分析-第5,6節(jié)運(yùn)籌學(xué)-東北大學(xué),鐘磊鋼-文庫吧資料
2025-05-23 07:19本頁面
【正文】 ? min(3,4)=4 ? 故 x5為換出變量。 因 b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。 例 6 用對偶單純形法求解 min ω=2x1+3x2+4x3 x1+2x2+x3≥3 2x1x2+3x3≥4 x1， x2， x3≥0 解 先將此問題化成下列形式，以便得到對偶問題的初始可行基 max z=2x13x24x3 x12x2x3+x4 =3 2x1+x23x3 +x5=4 xj≥0 ， j=1,2,…,5 例 6的初始單純形表，見表 26。 ? (4) 以 α lk為主元素 ， 按原單純形法在表中進(jìn)行迭代運(yùn)算 ， 得到新的計(jì)算表 。若所有 α lj≥ 0，則無可行解，停止 計(jì)算。 若檢查 b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算。 檢查 b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。 當(dāng)原問題得到可行解時(shí) ， 便得到了最優(yōu)解 。 若在 B1b中至少有一個(gè)負(fù)分量 ， 設(shè) (B1b)i＜ 0， 并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正 ，即對偶問題保持可行解 ， 它的各分量是 ? (1) 對應(yīng)基變量 x1， x2， …,xm的檢驗(yàn)數(shù)是 σ i=cizi=ciCBB1Pj=0， i=1,2,…,m ? (2) 對應(yīng)非基變量 xm+1， …， xn的檢驗(yàn)數(shù)是 σ j=cjzj=cjCBB1Pj≤0 ， j=m+1,…,n ? 每次迭代是將基變量中的負(fù)分量 xl取出 ，去替換非基變量中的 xk， 經(jīng)基變換 ， 所有檢驗(yàn)數(shù)仍保持非正 。 ? 方法如下： 設(shè)原問題 max z=CX AX=b X≥0 ? 又設(shè) B是一個(gè)基 。 根據(jù)對偶問題的對稱性 ? 可以這樣考慮：若保持對偶問題的解是基可行解，即 cjCBB1Pj≤0，而原問題在非可行解的基礎(chǔ)上，通過逐步迭代達(dá)到基可行解，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1