2. 河豚號 > 生活百科 >

單純形法各個步驟詳解（簡述單純形法迭代的基本思路）

河豚俠 ? 生活百科 ? 2023-04-22 15:06:05 ?

線性規(guī)劃(Linear Programming,簡稱LP)是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較為成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法。對偶理論(Duality theory)就是研究線性規(guī)劃中原始問題與對偶問題之間關系的理論。

1. 對偶問題的提出

對偶是對同一問題，從兩種不同角度觀察，有兩種擬似對立的表述。例如“矩形面積與周長的關系”有如下兩種表述：

周長一定，面積最大的矩形是正方形;

面積一定，周長最短的矩形是正方形。

再比如，生產計劃問題，如圖一所示，某工廠要生產兩種產品I和II，生產原料分別是A和B，且對總的生產設備臺時也有限制

 

解析對偶理論與對偶單純性法

 

那么，分別生產多少件產品I和II，才能使生產的利益最大化，很顯然，從賣家的角度，利用線性規(guī)劃，得到的優(yōu)化模型M1：

 

解析對偶理論與對偶單純性法

 

其中x1和x2分別是計劃生產產品I和II的件數。換一個角度，從買家的角度，不買產品二是直接買生產原料，從盈利的角度出發(fā)假設每件生產原料的價格跟別是y1、y2和y3，買家希望購買的成本是最小的，于是有了下面的優(yōu)化模型M2：

 

解析對偶理論與對偶單純性法

 

以上是兩個說明對偶問題的例子。下面直接給出原問題和對偶問題的對應關系表：

 

解析對偶理論與對偶單純性法

 

這種對應關系是可以通過拉格朗日對偶推導得到的，這里不作具體介紹，感興趣的同學可以參考

https://www.zhihu.com/question/58584814。

2. LP標準問題的對偶問題

標準LP問題：

 

解析對偶理論與對偶單純性法

 

對偶問題：

 

解析對偶理論與對偶單純性法

 

對原問題與對偶問題解的關系做一些簡單的推導：

 

解析對偶理論與對偶單純性法

 

其中xB和xN分別對應基變量和非基變量，B和N是基變量和非基變量對應的矩陣，cB和cN對應代價系數。由以上的推導可以看出，對偶問題的解與原問題的檢驗數有對應關系，這個關系對于理解對偶單純形法非常重要。

3.對偶問題的性質

3.1 對稱性

 

解析對偶理論與對偶單純性法

 

3.2 弱對偶性

 

解析對偶理論與對偶單純性法

 

弱對偶性表明，只要找到原問題和對偶問題的一個可行解，則能夠確定彼此的上下界。由弱對偶性可以得到兩個重要的推論：

 

解析對偶理論與對偶單純性法
解析對偶理論與對偶單純性法

 

3.3 強對偶性

 

解析對偶理論與對偶單純性法

 

3.4 最優(yōu)性條件

 

解析對偶理論與對偶單純性法

 

4. 對偶單純性法

首先從大的概念上，對原始單純形法和對偶單純形法做一下理解：

 

解析對偶理論與對偶單純性法

 

接下來推導對偶單純形法，實際上對偶單純形法和單純形法主要的區(qū)別就在與進基和出基的策略不一樣，下面具體介紹對偶單純形法進基和出基策略的推導，需要強調的是，對偶單純形法推導的前提是初始解滿足對偶可行性(原問題的檢驗數都大于0)。

 

解析對偶理論與對偶單純性法
解析對偶理論與對偶單純性法

 

最后，給出對偶單純形法的具體步驟：

 

解析對偶理論與對偶單純性法

 

本文由網上采集發(fā)布，不代表我們立場，轉載聯系作者并注明出處：http://m.zmlzfb.cn/shbk/48729.html

相關推薦

聯系我們

在線咨詢：點擊這里給我發(fā)消息

微信號：15705946153

工作日：9:30-18:30，節(jié)假日休息