對偶單純形法(對偶單純形法例題)

對偶單純形法是什么?

對偶單純形法是指從對偶可行性逐步搜索出原始問題最優解的方法。

由線性規劃問題的對偶理論，原始問題的檢驗數對應于對偶問題的一組基本可行解或最優解；原始問題的一組基本可行解或最優解對應于對偶問題的檢驗數；原始問題約束方程的系數矩陣的轉置是對偶問題約束條件方程的系數矩陣。所以，在求解常數項小于零的線性規劃問題時，可以把原始問題的常數項視為對偶問題的檢驗數，原始問題的檢驗數視為對偶問題的常數項。

優缺點：

對偶單純形法的優點： 不需要人工變量；當變量多于約束時，用對偶單純形法可減少迭代次數；在靈敏度分析中，有時需要用對偶單純形法處理簡化。

對偶單純形法缺點： 在初始單純形表中對偶問題是基可行解，這點對多數線性規劃問題很難做到。 因此，對偶單純形法一般不單獨使用。

對偶單純形法怎么回事啊？

對偶單純形法 　1954年美國數學家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解通過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發通過迭代逐步搜索原始問題的最優解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設原始問題為min{cx|Ax=b，x≥0}，則其對偶問題為 max{yb|yA≤c}。當原始問題的一個基解滿足最優性條件時,其檢驗數cBB-1A-c≤0。即知y＝cBB-1（稱為單純形算子）為對偶問題的可行解。所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。因此在保持對偶可行性的前提下，一當基解成為可行解時，便也就是最優解。

對偶單純形法的計算步驟

單純形法的一般解題步驟可歸納如下：

①把線性規劃問題的約束方程組表達成典范性方程組，找出基本可行解作為初始基本可行解。

②若基本可行解不存在，即約束條件有矛盾，則問題無解。

③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。

④按步驟3進行迭代直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。

⑤若迭代過程中發現問題的目標函數值無界，則終止迭代。

基本信息：

單純形法是從原始問題的一個可行解通過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發通過迭代逐步搜索原始問題的最優解。

在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設原始問題為min{cx|Ax=b，x≥0}，則其對偶問題（Dual Problem）為max{yb|yA≤c}。

當原始問題的一個基解滿足最優性條件時，其檢驗數cBB-1A-c≤0。即知y=cBB-1（稱為單純形算子）為對偶問題的可行解。所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。因此在保持對偶可行性的前提下，一當基解成為可行解時，便也就是最優解。

對偶單純形法前提條件

始終保持對偶問題的解的可行性，并不斷改善原問題解的可行性，直至滿足原問題。

所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。只要保持檢驗數滿足最優性條件前提下，一旦基解成為可行解時，對偶問題和原問題均可行，由強對偶性證明，二者均有最優解。

對偶單純形法的優點：

1、不需要人工變量；

2、當變量多于約束時，用對偶單純形法可減少迭代次數；

3、在靈敏度分析中，有時需要用對偶單純形法處理簡化。

擴展資料

為了用選代法求出線性規劃的最優解，需要解決以下三個問題；

1、最優解判別準則，即迭代終止的判別標準；

2、換基運算，即從一個基可行解迭代出另一個基可行解的方法；

3、進基列的選擇，即選擇合適的列以進行換基運算，可以使目標函數值有較大下降。

參考資料來源：百度百科——單純形法

參考資料來源：百度百科——對偶單純形法

對偶單純形法和單純形法的區別

單純形法是求解線性規劃問題的主要方法，而對偶單純形方法是將單純形方法應用于對偶問題的計算，對偶單純性方法則提高了對求解線性規劃問題的效率。
初始基解可以是非可行解，當檢驗數都為負值時，就可以進行基的變換，不需加入人工變量，從而簡化計算。
對于變量多于約束條件的線性規劃問題，用對偶單純形法可以減少計算量，在靈敏度分析及求解整數規劃的割平面法中，有時適宜用對偶規劃單純形法。

對偶單純形法檢驗數大于0怎么辦

1、對偶單純形法檢驗數大于0就找到檢驗數大于0的，且最大的。
2、單純形法在整個迭代過程中，始終保持原問題的可行性，即常數列大于等于0。
3、對偶單純形法則是在整個迭代過程中，始終保持對偶問題的可行性，即全部檢驗數大于等于0。