一、對(duì)偶問(wèn)題

????每個(gè)線性規(guī)劃問(wèn)題都有一個(gè)與之對(duì)應(yīng)的對(duì)偶問(wèn)題。對(duì)偶問(wèn)題是以原問(wèn)題的約束條件和目標(biāo)函數(shù)為基礎(chǔ)構(gòu)造而來(lái)的。對(duì)偶問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題，因此可以采用單純形法（有關(guān)單純形法會(huì)在以后的筆記中補(bǔ)充）求解。對(duì)偶問(wèn)題的最優(yōu)解也可以通過(guò)原問(wèn)題的最優(yōu)解得到，反之亦然。而且，在某些情況下，利用對(duì)偶理論求解線性規(guī)劃問(wèn)題更為簡(jiǎn)單，而且有助于深入了解待求問(wèn)題的本質(zhì)。

二、對(duì)偶問(wèn)題的定義與表述

????考慮如下形式的線性規(guī)劃問(wèn)題：

mincTxst.Ax≥bx≥0
該問(wèn)題稱為原問(wèn)題，其相應(yīng)的對(duì)偶問(wèn)題定義為：
maxλTbst.λTA≤cTλ≥0
其中， λ∈Rm是對(duì)偶向量。在原問(wèn)題和對(duì)偶問(wèn)題中， b和c的作用是互逆的，這種對(duì)偶稱為對(duì)稱形式的對(duì)偶。

????為了定義任意線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，可首先將給定的線性規(guī)劃問(wèn)題轉(zhuǎn)換為與上述原問(wèn)題結(jié)構(gòu)形式相同的等價(jià)問(wèn)題；然后，根據(jù)對(duì)稱形式的對(duì)偶，得到等價(jià)問(wèn)題的對(duì)偶。

三、證明對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題

???? 將對(duì)偶問(wèn)題表示為：

minλT(?b)st.λT(?A)≥(?cT)λ≥0
則上述問(wèn)題的等價(jià)于：(將上式兩端同時(shí)轉(zhuǎn)置)
min(?bT)λst.(?AT)λ≤?cλ≥0
則上式的對(duì)偶問(wèn)題為：( x等價(jià)于對(duì)偶定義的 λ)
maxxT(?c)st.xT(?A)T≤?bTx≥0
對(duì)上式取轉(zhuǎn)置：
max(?cT)xst.(?A)x≤?bx≥0
整理后，就可以得到原問(wèn)題。

四、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

???? 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型約束為Ax=b,為了構(gòu)造相應(yīng)的對(duì)偶問(wèn)題，首先將上述等式變換為不等式：

Ax≥bAx≤b??Ax≥?b
那么，帶有等式的原問(wèn)題可以寫(xiě)為：
mincTxst.Ax≥b?Ax≥?bx≥0
上式的對(duì)偶問(wèn)題可以整理為：
maxλTbst.λTA≤cT
這種對(duì)偶關(guān)系稱為非對(duì)稱形式的對(duì)偶。

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

mincTx	maxλTb
st.Ax≥bx≥0	st.λTA≤cTλ≥0

表1 對(duì)稱形式對(duì)偶關(guān)系 原問(wèn)題對(duì)偶問(wèn)題

mincTx	maxλTb
st.Ax=bx≥0	st.λTA≤cT

表2 非對(duì)稱形式對(duì)偶關(guān)系

五、構(gòu)造任意線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

將原問(wèn)題轉(zhuǎn)換為與之等價(jià)的對(duì)稱形式對(duì)偶關(guān)系中的原問(wèn)題。

參照對(duì)稱形式對(duì)偶關(guān)系就可得到對(duì)偶問(wèn)題，整理后可得到非對(duì)稱形式的對(duì)偶問(wèn)題。

總結(jié)

以上是生活随笔為你收集整理的最优化学习笔记（十）——对偶线性规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。