單純形法簡單例題詳解運(yùn)籌學(xué)單純形法

該賬號為華為云開發(fā)者社區(qū)官方運(yùn)營賬號，提供全面深入的云計(jì)算前景分析、豐富的技術(shù)干貨和程序樣本，分享華為云前沿信息動態(tài) 。
本文分享自華為云社區(qū)《對偶理論與對偶簡約定律》。原作者:井岡山_陽春。
線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，研究早、發(fā)展快、應(yīng)用廣、方法成熟。它是一種輔助人們進(jìn)行科學(xué)管理的數(shù)學(xué)方法。對偶理論是研究線性規(guī)劃中原始問題和對偶問題之間關(guān)系的理論。
1.提出對偶問題二元性是指同一個(gè)問題。從兩個(gè)不同的角度看，有兩種準(zhǔn)對立的表述。例如， “矩形面積和周長之間的關(guān)系”有以下兩個(gè)表達(dá)式:
有一定周長且面積最大的矩形是正方形；
具有一定面積和最短周長的矩形是正方形。
另一個(gè)例子是生產(chǎn)計(jì)劃問題。如圖1所示，一個(gè)工廠要生產(chǎn)兩個(gè)產(chǎn)品I和II ，原材料分別是A和B ，對生產(chǎn)設(shè)備總小時(shí)數(shù)也有限制。

文章插圖

文章插圖

那么，可以分別生產(chǎn)多少件產(chǎn)品一和二，使生產(chǎn)效益最大化。顯然，從賣方的角度出發(fā) ，利用線性規(guī)劃，我們得到了優(yōu)化模型M1:

文章插圖

文章插圖

X1和x2分別是計(jì)劃產(chǎn)品I和II的數(shù)量。從另一個(gè)角度來看，從買方的角度來看，第二種是直接購買原材料而不是產(chǎn)品。從利潤的角度來看，假設(shè)每種原材料的價(jià)格為y1、y2、y3 ，購買者想要購買的成本最小，那么下面的優(yōu)化模型M2是可用的:

文章插圖

文章插圖

這是兩個(gè)例子來說明對偶問題。下面直接給出了原問題和對偶問題的對應(yīng)關(guān)系表:

文章插圖

文章插圖

這種對應(yīng)關(guān)系可以通過拉格朗日對偶推導(dǎo)出來，這里不再詳細(xì)描述。感興趣的學(xué)生可以參考https://www.zhihu.com/question/58584814.
2.線性規(guī)劃標(biāo)準(zhǔn)問題的對偶問題標(biāo)準(zhǔn)LP問題:

文章插圖

文章插圖

二元性問題:

文章插圖

文章插圖

對原問題的解和對偶問題的解之間的關(guān)系做一些簡單的推導(dǎo):

文章插圖

文章插圖

其中xB和xN分別對應(yīng)基變量和非基變量， b和n是對應(yīng)基變量和非基變量的矩陣， cB和cN對應(yīng)成本系數(shù) 。從以上推導(dǎo)可以看出，對偶問題的解與原問題的檢驗(yàn)數(shù)之間存在對應(yīng)關(guān)系，這對理解對偶單純形法非常重要。
3.對偶問題的本質(zhì)3.1對稱性

文章插圖

文章插圖

3.2弱對偶

文章插圖

文章插圖

弱對偶表明，只要找到原問題和對偶問題的可行解，就可以確定彼此的上下界。從弱對偶可以得出兩個(gè)重要的推論:

文章插圖

文章插圖

3.3強(qiáng)二元性

文章插圖

文章插圖

3.4最佳條件

文章插圖

文章插圖

4.雙重簡化法首先，從大的概念出發(fā) ，理解本原單純形法和對偶單純形法:

文章插圖

文章插圖

接下來，我們推導(dǎo)對偶單純形法。事實(shí)上，對偶單純形法和對偶單純形法的主要區(qū)別在于它不同于基地進(jìn)入和基地退出的策略。在這里，我們將詳細(xì)介紹對偶單純形法的基入口和基出口策略的推導(dǎo) 。需要強(qiáng)調(diào)的是，對偶單純形法推導(dǎo)的前提是初始解滿足對偶可行性(原問題的檢驗(yàn)數(shù)大于0) 。