對偶理論和靈敏度分析-第5,6節(jié)運籌學(xué)-東北大學(xué),鐘磊鋼(參考版)
2025-05-19 07:19本頁面
【正文】 。 ? (3) 在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時需要用對偶單純形法，這樣可使問題的處理簡化。 表 28 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 3 2 x 2 x 1 2/5 11/5 0 1 1 0 1/5 7/2 2/5 1/5 1/5 2/5 c j z j 0 0 3/5 8/5 1/5 表 28中 ， b列數(shù)字全為非負(fù) ， 檢驗數(shù)全為非正 ， 故問題的最優(yōu)解為 X*=(11/5， 2/5， 0， 0， 0)T 若對應(yīng)兩個約束條件的對偶變量分別為 y1和 y2， 則對偶問題的最優(yōu)解為 Y*=(y1*,y2*)=(8/5,1/5) 從以上求解過程可以看到對偶單純形法有以下優(yōu)點： ? (1) 初始解可以是非可行解，當(dāng)檢驗數(shù)都為負(fù)數(shù)時就可以進(jìn)行基的變換，這時不需要加入人工變量，因此可以簡化計算。 12234,22m i n ?????????????????表 27 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 2 x 4 x 1 1 2 0 1 [ 5/2] 1/2 1/2 3/2 1 0 1/2 1/2 c j z j 0 4 1 0 1 由表 2 7 看出，對偶問題仍是可行解，而 b 列中仍有負(fù)分量。 換入 、 換出變量的所在列 、 行的交叉處 “ 2”為主元素 。若所有 α lj≥ 0， 則無可行解 ， 停止 計算 。 計算
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1