對(duì)偶及對(duì)偶單純形法

對(duì)偶及對(duì)偶單純形法第一頁(yè)，共三十七頁(yè)，2022年，8月28日本節(jié)主要內(nèi)容線性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)對(duì)偶單純形法

學(xué)習(xí)要點(diǎn)：

1.掌握線性規(guī)劃的對(duì)偶形式

2.掌握對(duì)偶單純形法的解題思路及求解步驟第二頁(yè)，共三十七頁(yè)，2022年，8月28日對(duì)偶現(xiàn)象普遍存在

“對(duì)偶”，在不同的領(lǐng)域有著不同的詮釋。在詞語(yǔ)中，它是一種修辭方式，指兩個(gè)字?jǐn)?shù)相等、結(jié)構(gòu)相似的語(yǔ)句，旨表達(dá)出相關(guān)或相反的意思。如：“下筆千言，離題萬(wàn)里”周長(zhǎng)一定，面積最大的矩形是正方形；面積一定，周長(zhǎng)最小的矩形是正方形。

數(shù)學(xué)上也有如下對(duì)偶例子：“橫眉冷對(duì)千夫指，俯首甘為孺子?！?/p>

“天高任鳥飛，海闊憑魚躍”

第三頁(yè)，共三十七頁(yè)，2022年，8月28日一、線性規(guī)劃的對(duì)偶模型

設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，生產(chǎn)每件產(chǎn)品所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表：表1.產(chǎn)品數(shù)據(jù)表

設(shè)備產(chǎn)品ABCD產(chǎn)品利潤(rùn)（千元／件）

甲

21402乙

22043設(shè)備可利用機(jī)時(shí)數(shù)（時(shí)）

1281612問：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？1.對(duì)偶問題的現(xiàn)實(shí)來源第四頁(yè)，共三十七頁(yè)，2022年，8月28日解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，最優(yōu)解為最優(yōu)值為如何安排生產(chǎn)，使獲利最多？則數(shù)學(xué)模型為：第五頁(yè)，共三十七頁(yè)，2022年，8月28日反過來問：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？出讓代價(jià)應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤(rùn)。

付出的代價(jià)最小，且對(duì)方能接受。第六頁(yè)，共三十七頁(yè)，2022年，8月28日在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策應(yīng)符合兩條：

（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。

（2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，機(jī)時(shí)總收費(fèi)盡可能低一些，以便爭(zhēng)取更多用戶，最終將設(shè)備出租出去。第七頁(yè)，共三十七頁(yè)，2022年，8月28日解：設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4元，用單純形法求得最優(yōu)解為最優(yōu)值為則新的線性規(guī)劃數(shù)學(xué)模型為：第八頁(yè)，共三十七頁(yè)，2022年，8月28日2.原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系原問題（對(duì)偶問題）對(duì)偶問題（原問題）原始規(guī)劃與對(duì)偶規(guī)劃是同一組數(shù)據(jù)參數(shù),只是位置有所不同,所描述的問題實(shí)際上是同一個(gè)問題從另一種角度去描述.第九頁(yè)，共三十七頁(yè)，2022年，8月28日線性規(guī)劃的對(duì)偶模型

特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù).原始線性規(guī)劃問題對(duì)偶線性規(guī)劃問題對(duì)稱形式的線性規(guī)劃第十頁(yè)，共三十七頁(yè)，2022年，8月28日線性規(guī)劃的對(duì)偶模型例2寫出線性規(guī)劃問題的對(duì)偶問題解：由于若給出的線性規(guī)劃不是對(duì)稱形式，所以先將它化成對(duì)稱形式，然后再寫出相應(yīng)的對(duì)偶問題。第十一頁(yè)，共三十七頁(yè)，2022年，8月28日解：首先將原問題變形為則對(duì)偶模型為：第十二頁(yè)，共三十七頁(yè)，2022年，8月28日線性規(guī)劃的對(duì)偶變換規(guī)則(單向)原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無(wú)約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無(wú)約束=第十三頁(yè)，共三十七頁(yè)，2022年，8月28日對(duì)偶問題的形成minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始問題變量的個(gè)數(shù)(3)等于對(duì)偶問題約束條件的個(gè)數(shù)(3)；原始問題約束條件的個(gè)數(shù)(4)等于對(duì)偶問題變量的個(gè)數(shù)(4)。原始問題變量的性質(zhì)影響對(duì)偶問題約束條件的性質(zhì)，用表示原始問題約束條件的性質(zhì)影響對(duì)偶問題變量的性質(zhì)，用表示第十四頁(yè)，共三十七頁(yè)，2022年，8月28日例4:寫出下列線性規(guī)劃問題的對(duì)偶問題.解：原問題的對(duì)偶問題為第十五頁(yè)，共三十七頁(yè)，2022年，8月28日定理6.1(對(duì)合性)

對(duì)偶線性規(guī)劃的對(duì)偶問題是原始線性規(guī)劃問題。對(duì)偶定義對(duì)偶定義二、對(duì)偶性質(zhì)（選讀）第十六頁(yè)，共三十七頁(yè)，2022年，8月28日定理6.2

弱對(duì)偶原理(弱對(duì)偶性)：設(shè)和分別是問題(LP)和(DP)的可行解，則必有推論1:原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的上界；反之，對(duì)偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的下界。第十七頁(yè)，共三十七頁(yè)，2022年，8月28日推論2:

在一對(duì)對(duì)偶問題（LP）和（DP）中，若其中一個(gè)問題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問題無(wú)可行解；這也是對(duì)偶問題的無(wú)界性。推論3：在一對(duì)對(duì)偶問題（LP）和（DP）中，若一個(gè)有可行解，而另一個(gè)無(wú)可行解，則該可行的問題目標(biāo)函數(shù)值無(wú)界。第十八頁(yè)，共三十七頁(yè)，2022年，8月28日定理6.3

最優(yōu)性判定定理：如果是原問題的可行解，則是原問題的最優(yōu)解，是其對(duì)偶問題的最優(yōu)解。是其對(duì)偶問題的可行解，并且:定理6.4.

在一對(duì)對(duì)偶問題（LP）和（DP）中，若任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且對(duì)應(yīng)的最優(yōu)值相等。第十九頁(yè)，共三十七頁(yè)，2022年，8月28日定理6.6強(qiáng)對(duì)偶性：若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。推論4：（LP）與（DP）要么兩者都有最優(yōu)解，要么都無(wú)最優(yōu)解。定理6.7

互補(bǔ)松弛性：設(shè)X0和Y0分別是(LP)問題和(DP)問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs為松弛變量、Ys為剩余變量.互補(bǔ)松弛條件第二十頁(yè)，共三十七頁(yè)，2022年，8月28日對(duì)偶性質(zhì)的應(yīng)用

借助以上性質(zhì)可以證明，在用單純形法求解原問題的迭代過程中，單純形表右列中的元素對(duì)應(yīng)于原問題的基本可行解，底行中松弛變量對(duì)應(yīng)的元素恰好構(gòu)成對(duì)偶問題的基本解。逐次迭代下去，當(dāng)?shù)仔袑?duì)應(yīng)于對(duì)偶問題的解也變成基本可行解（底行元素全非負(fù)）時(shí)，原問題和對(duì)偶問題同時(shí)達(dá)到最優(yōu)解.即此時(shí)對(duì)偶問題的這個(gè)基本可行解就是它的最優(yōu)解。

用單純形方法求解原線性規(guī)劃的過程中，每次迭代都保證得到原問題的一個(gè)基本可行解，底行某些元素對(duì)應(yīng)于對(duì)偶問題的基本解.單純形法的迭代的過程既可以看作使原問題的基本可行解逐步變?yōu)樽顑?yōu)解（此時(shí)底行元素非負(fù))的過程，也可看作使對(duì)偶問題的基本解逐步變成基本可行解的過程。

第二十一頁(yè)，共三十七頁(yè)，2022年，8月28日根據(jù)性質(zhì)1（對(duì)偶問題的對(duì)偶是它本身），在用單純形法求解LP時(shí)也可這樣考慮：從對(duì)偶問題的某個(gè)基本可行解開始，每次迭代總保證得到對(duì)偶問題的一個(gè)基本可行解（底行元素均非負(fù)），通過逐步迭代，當(dāng)對(duì)偶問題達(dá)到最優(yōu)解時(shí)，根據(jù)對(duì)偶理論，對(duì)偶問題的對(duì)偶即原問題也達(dá)到最優(yōu)解。對(duì)偶單純形法

適用情況：當(dāng)原問題沒有初始的基本可行解，但是對(duì)偶問題有初始的基本可行解（初始表格容易滿足①③④）時(shí)，用此方法。

優(yōu)點(diǎn)：當(dāng)原問題沒有初始的基本可行解，不需要借助大M法或二階段法構(gòu)造新的模型.對(duì)偶單純形法的基本思想第二十二頁(yè)，共三十七頁(yè)，2022年，8月28日三、對(duì)偶單純形法注意：它并不是求解對(duì)偶問題的單純形法，而是一個(gè)直接求解原LP問題的新算法。

對(duì)偶單純形法是求解LP問題的另一個(gè)基本方法。它是根據(jù)對(duì)偶理論和單純形法原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。第二十三頁(yè)，共三十七頁(yè)，2022年，8月28日對(duì)偶單純形法找出一個(gè)DP的基本可行解LP是否可行保持DP為基本可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解最優(yōu)解是否循環(huán)結(jié)束第二十四頁(yè)，共三十七頁(yè)，2022年，8月28日1.對(duì)偶單純形法的迭代步驟1）將原問題化為標(biāo)準(zhǔn)形,寫出相應(yīng)的表格;2）利用容許的運(yùn)算建立滿足①

③④三個(gè)特點(diǎn)的單純形表;3）檢查右列元素，若全非負(fù)，即表格滿足①②

③④四個(gè)特點(diǎn)，結(jié)束運(yùn)算；否則，進(jìn)去第4）步；4）確定離基變量.取右列中最小的負(fù)元素所在的行設(shè)是第行.第二十五頁(yè)，共三十七頁(yè)，2022年，8月28日5)確定進(jìn)基變量所在列對(duì)應(yīng)的變量取為進(jìn)基變量;觀察該行豎線左邊的元素若所有則無(wú)可行解，結(jié)束運(yùn)算;否則，按如下規(guī)則從負(fù)系數(shù)中選擇一個(gè)記為第二十六頁(yè)，共三十七頁(yè)，2022年，8月28日6)進(jìn)行旋轉(zhuǎn)運(yùn)算利用容許的運(yùn)算將變?yōu)?,該列其它元素變?yōu)?,從而實(shí)現(xiàn)將變?yōu)榛兞康哪康?7）觀察得到的新表(滿足①

③④).若右列元素均非負(fù),則已得最優(yōu)解,結(jié)束運(yùn)算;否則,返回第4)步.第二十七頁(yè)，共三十七頁(yè)，2022年，8月28日例5.（教材P79例5.4）用對(duì)偶單純形法求解：引入松弛變量得到標(biāo)準(zhǔn)型線性規(guī)劃解：第二十八頁(yè)，共三十七頁(yè)，2022年，8月28日構(gòu)造對(duì)偶單純形表選取離基變量選取進(jìn)基變量-1-2-310

-5-2-2-101

-6345000滿足①③④,但②不滿足第二十九頁(yè)，共三十七頁(yè)，2022年，8月28日0-1-5/21-1/2

-2111/20-1/2

3017/203/2-9015/2-11/2

210-21-1100111-11滿足①③④,但②不滿足滿足①②③④第三十頁(yè)，共三十七頁(yè)，2022年，8月28日滿足①②③④是具有標(biāo)準(zhǔn)形式的LP的最優(yōu)解.

略去松弛變量得原LP問題的最優(yōu)解為最優(yōu)值為015/2-11/2

210-21-1100111-11第三十一頁(yè)，共三十七頁(yè)，2022年，8月28日例6.

用對(duì)偶單純形法求解：引入松弛變量得到標(biāo)準(zhǔn)型線性規(guī)劃解：第三十二頁(yè)，共三十七頁(yè)，2022年，8月28日構(gòu)造對(duì)偶單純形表選取離基變量選取進(jìn)基變量-2-1-4010

-2-2-20-401

-31281612000滿足①③④,但②不滿足第三十三頁(yè)，共三十七頁(yè)，2022年，8月28日-2-1-4010

-2-2-20-401

-31281612000-2-1-4010

-21/21/2010-1/43/46216003-9滿足①③④,但②不滿足第三十四頁(yè)，共三十七頁(yè)，2022年，8月28日-2-1-4010

-21/21/2010-1/43/46216003-92140-10

2-1/2