哈爾濱工業(yè)大學(xué)運籌學(xué)大作業(yè)-對偶單純形法對比-資料下載頁
2025-06-27 23:42本頁面
【正文】 純形法計算的。當(dāng)線性規(guī)劃問題具備下面條件時，可以用對偶單純形法求解：①問題標(biāo)準(zhǔn)化后，價值系數(shù)全非正；②所有約束全是不等式。 六、對偶單純形法的應(yīng)用，原問題是求最小值，并且目標(biāo)函數(shù)各項系數(shù)都不小于零。所以在轉(zhuǎn)化成標(biāo)準(zhǔn)型后各項系數(shù)不大于零，從而以松弛變量為基列出的單純形表滿足檢驗數(shù)都不大于零，是其對偶問題的一個可行解。如果原問題的標(biāo)準(zhǔn)形式中各項系數(shù)不都小于零，則不容易找到對偶問題的一個初始可行解，就不適合使用對偶單純形法求解。所以對偶單純形法適用于不易找到原方程的可行解而容易找到其對偶問題的可行解的線性規(guī)劃問題。，約束方程的數(shù)量對單純形法的計算過程要遠遠大于變量個數(shù)的影響。如果mn，那么對偶問題有n個約束方程，而原問題有m個約束方程，所以對偶問題有更少的約束方程數(shù)量，那么通過對偶單純形法的運用比起直接只用單純形法將會顯著的減少計算量。對偶問題可以用來對原問題的計劃方案進行評價。我們可以用一個對偶問題的可行解和目前原問題的計劃方案進行比較，如果兩個目標(biāo)函數(shù)值相等或比較接近，則可以說明原問題的計劃方案已經(jīng)是可以看做最優(yōu)了。七、單純形法和對偶單純形法的基本思想比較通過以上的分析可知，對偶單純形法其實相當(dāng)于單純形法的一種變形，只不過在運用對偶單純形法解線性規(guī)劃時需要將單純形表旋轉(zhuǎn)一下。單純形表中的b列實際上是對偶問題的非基變量的檢驗數(shù), 而原單純形表的檢驗數(shù)為對偶問題的基解, 這樣可以理解為通過旋轉(zhuǎn)90176。運用單純形法求解線性規(guī)劃。從求解思路上來說，單純形法是首先保證基解是原問題的基可行解（bi不小于零），然后通過變量的換入換出增大目標(biāo)函數(shù)值，直到其同時成為對偶問題的可行解，根據(jù)強對偶性原理，可知這個解就是最優(yōu)解。而對偶單純形法則是首先保證基解是對偶問題的可行解（檢驗數(shù)都不大于零），然后逐步減小對偶標(biāo)準(zhǔn)化的目標(biāo)函數(shù)值，使其成為原問題的可行解。兩種方法殊途同歸，其本質(zhì)是一樣的。8
高考資料相關(guān)推薦
鄂ICP備17016276號-1