哈爾濱工業(yè)大學(xué)運籌學(xué)大作業(yè)-對偶單純形法對比(編輯修改稿)
2025-07-24 23:42 本頁面
【文章內(nèi)容簡介】 一個問題中是基變量，則在另一問題中是非基變量；將這對互補的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有z=w。四、對偶單純形算法流程在上述的理論基礎(chǔ)上，可知用單純形法求解線性規(guī)劃問題時，在得到原問題的一個基可行解問題同時，在檢驗數(shù)行得到對偶問題的一個基解。單純形法的基本思想是保持原問題為可行解的基礎(chǔ)上，通過迭代增大目標(biāo)函數(shù)，當(dāng)其對偶問題也為可行解時，就達(dá)到了目標(biāo)函數(shù)的最優(yōu)值。而對偶單純形法的基本思想則是保持對偶問題為可行解的前提下（即單純性表最后一行檢驗數(shù)都小于零），通過迭代減小目標(biāo)函數(shù)，當(dāng)原問題也是可行解時，就得到了目標(biāo)函數(shù)的最優(yōu)解。故我們可以得到對偶單純形法求解過程如下： ，找到一個檢驗數(shù)都小于等于零的對偶問題的初始可行基。對于小于零的bi，找到最小的一個br，其對應(yīng)的xr為換出基的變量（1）為了使迭代后表中的第r行基變量為正值，因而只有對應(yīng)aij小于零的非基變量才可以作為換入基的變量；（2）為了使迭代后表中對偶問題仍為可行解，令θ=minjcjzjaijari0=cszsars稱ars為主元素，xs為換入基的變量。，得到一個新的基。再次檢查是否所有的bi 大于等于零。如果是，則找到了最優(yōu)解，如果否，則再次進(jìn)行變換。對偶單純形法的算法流程圖開始化原問題為標(biāo)準(zhǔn)型找出一個對偶問題的初始可行基B0，計算非基變量檢驗數(shù)（全部檢驗數(shù)σj≤0）并列出初始單純形表是bi 都≥0？否確定換出和換入的基變量： 換出最小的“右端項”bi所對應(yīng)的基變量； 按公式θ=min｛σj/a’ij，a’ij≤0｝=σs/a’ij計算最小比值θ，所對應(yīng)的基變量為換入計算檢驗數(shù)，列出新的單純形表已找到最優(yōu)解
高考資料相關(guān)推薦
鄂ICP備17016276號-1