1. 首頁 > 生活 > >

單純形法各個步驟詳解例子 單純形法各個步驟詳解視頻

小知識



文章插圖
單純形法各個步驟詳解例子 單純形法各個步驟詳解視頻

文章插圖
線性規劃（Linear Programming,簡稱LP）是運籌學中研究較早、發展較快、應用廣泛、方法較為成熟的一個重要分支 ， 它是輔助人們進行科學管理的一種數學方法 。對偶理論（Duality theory）就是研究線性規劃中原始問題與對偶問題之間關系的理論 。
1. 對偶問題的提出
對偶是對同一問題 ， 從兩種不同角度觀察 ， 有兩種擬似對立的表述 。例如“矩形面積與周長的關系”有如下兩種表述：
周長一定 ， 面積最大的矩形是正方形；面積一定 ， 周長最短的矩形是正方形 。
再比如 ， 生產計劃問題 ， 如圖一所示 ， 某工廠要生產兩種產品I和II ， 生產原料分別是A和B ， 且對總的生產設備臺時也有限制
那么 ， 分別生產多少件產品I和II ， 才能使生產的利益最大化 ， 很顯然 ， 從賣家的角度 ， 利用線性規劃 ， 得到的優化模型M1：
其中x1和x2分別是計劃生產產品I和II的件數 。換一個角度 ， 從買家的角度 ， 不買產品二是直接買生產原料 ， 從盈利的角度出發假設每件生產原料的價格跟別是y1、y2和y3 ， 買家希望購買的成本是最小的 ， 于是有了下面的優化模型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 最優性條件
4. 對偶單純性法
首先從大的概念上 ， 對原始單純形法和對偶單純形法做一下理解：
接下來推導對偶單純形法 ， 實際上對偶單純形法和單純形法主要的區別就在與進基和出基的策略不一樣 ， 下面具體介紹對偶單純形法進基和出基策略的推導 ， 需要強調的是 ， 對偶單純形法推導的前提是初始解滿足對偶可行性（原問題的檢驗數都大于0） 。
【單純形法各個步驟詳解例子 單純形法各個步驟詳解視頻】最后 ， 給出對偶單純形法的具體步驟：