国内精品自在自线在免费,欧美日韩国产天堂,А√天堂资源最新版在线官网

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

1. 對(duì)偶問(wèn)題的提出

對(duì)偶是對(duì)同一問(wèn)題，從兩種不同角度觀察，有兩種擬似對(duì)立的表述。例如“矩形面積與周長(zhǎng)的關(guān)系”有如下兩種表述：

周長(zhǎng)一定，面積最大的矩形是正方形;

面積一定，周長(zhǎng)最短的矩形是正方形。

再比如，生產(chǎn)計(jì)劃問(wèn)題，如圖一所示，某工廠要生產(chǎn)兩種產(chǎn)品I和II，生產(chǎn)原料分別是A和B，且對(duì)總的生產(chǎn)設(shè)備臺(tái)時(shí)也有限制

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

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

以上是兩個(gè)說(shuō)明對(duì)偶問(wèn)題的例子。下面直接給出原問(wèn)題和對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系表：

這種對(duì)應(yīng)關(guān)系是可以通過(guò)拉格朗日對(duì)偶推導(dǎo)得到的，這里不作具體介紹，感興趣的同學(xué)可以參考

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

2. LP標(biāo)準(zhǔn)問(wèn)題的對(duì)偶問(wèn)題

標(biāo)準(zhǔn)LP問(wèn)題：

對(duì)偶問(wèn)題：

對(duì)原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系做一些簡(jiǎn)單的推導(dǎo)：

其中xB和xN分別對(duì)應(yīng)基變量和非基變量，B和N是基變量和非基變量對(duì)應(yīng)的矩陣，cB和cN對(duì)應(yīng)代價(jià)系數(shù)。由以上的推導(dǎo)可以看出，對(duì)偶問(wèn)題的解與原問(wèn)題的檢驗(yàn)數(shù)有對(duì)應(yīng)關(guān)系，這個(gè)關(guān)系對(duì)于理解對(duì)偶單純形法非常重要。

3.對(duì)偶問(wèn)題的性質(zhì)

3.1 對(duì)稱性

3.2 弱對(duì)偶性

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

3.3 強(qiáng)對(duì)偶性

3.4 最優(yōu)性條件

4. 對(duì)偶單純性法

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

接下來(lái)推導(dǎo)對(duì)偶單純形法，實(shí)際上對(duì)偶單純形法和單純形法主要的區(qū)別就在與進(jìn)基和出基的策略不一樣，下面具體介紹對(duì)偶單純形法進(jìn)基和出基策略的推導(dǎo)，需要強(qiáng)調(diào)的是，對(duì)偶單純形法推導(dǎo)的前提是初始解滿足對(duì)偶可行性(原問(wèn)題的檢驗(yàn)數(shù)都大于0)。