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

對(duì)偶及對(duì)偶單純形法第1頁(yè)，共37頁(yè)，2023年，2月20日，星期四本節(jié)主要內(nèi)容線(xiàn)性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)對(duì)偶單純形法

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

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

2.掌握對(duì)偶單純形法的解題思路及求解步驟第2頁(yè)，共37頁(yè)，2023年，2月20日，星期四對(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>

“天高任鳥(niǎo)飛，海闊憑魚(yú)躍”

第3頁(yè)，共37頁(yè)，2023年，2月20日，星期四一、線(xiàn)性規(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問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？1.對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源第4頁(yè)，共37頁(yè)，2023年，2月20日，星期四解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，最優(yōu)解為最優(yōu)值為如何安排生產(chǎn)，使獲利最多？則數(shù)學(xué)模型為：第5頁(yè)，共37頁(yè)，2023年，2月20日，星期四反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？出讓代價(jià)應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤(rùn)。

付出的代價(jià)最小，且對(duì)方能接受。第6頁(yè)，共37頁(yè)，2023年，2月20日，星期四在市場(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)取更多用戶(hù)，最終將設(shè)備出租出去。第7頁(yè)，共37頁(yè)，2023年，2月20日，星期四解：設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4元，用單純形法求得最優(yōu)解為最優(yōu)值為則新的線(xiàn)性規(guī)劃數(shù)學(xué)模型為：第8頁(yè)，共37頁(yè)，2023年，2月20日，星期四2.原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）原始規(guī)劃與對(duì)偶規(guī)劃是同一組數(shù)據(jù)參數(shù),只是位置有所不同,所描述的問(wèn)題實(shí)際上是同一個(gè)問(wèn)題從另一種角度去描述.第9頁(yè)，共37頁(yè)，2023年，2月20日，星期四線(xiàn)性規(guī)劃的對(duì)偶模型

特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù).原始線(xiàn)性規(guī)劃問(wèn)題對(duì)偶線(xiàn)性規(guī)劃問(wèn)題對(duì)稱(chēng)形式的線(xiàn)性規(guī)劃第10頁(yè)，共37頁(yè)，2023年，2月20日，星期四線(xiàn)性規(guī)劃的對(duì)偶模型例2寫(xiě)出線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題解：由于若給出的線(xiàn)性規(guī)劃不是對(duì)稱(chēng)形式，所以先將它化成對(duì)稱(chēng)形式，然后再寫(xiě)出相應(yīng)的對(duì)偶問(wèn)題。第11頁(yè)，共37頁(yè)，2023年，2月20日，星期四解：首先將原問(wèn)題變形為則對(duì)偶模型為：第12頁(yè)，共37頁(yè)，2023年，2月20日，星期四線(xiàn)性規(guī)劃的對(duì)偶變換規(guī)則(單向)原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）約束條件右端項(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ú)約束=第13頁(yè)，共37頁(yè)，2023年，2月20日，星期四對(duì)偶問(wèn)題的形成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原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)；原始問(wèn)題約束條件的個(gè)數(shù)(4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(4)。原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)，用表示原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)，用表示第14頁(yè)，共37頁(yè)，2023年，2月20日，星期四例4:寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.解：原問(wèn)題的對(duì)偶問(wèn)題為第15頁(yè)，共37頁(yè)，2023年，2月20日，星期四定理6.1(對(duì)合性)

對(duì)偶線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題是原始線(xiàn)性規(guī)劃問(wèn)題。對(duì)偶定義對(duì)偶定義二、對(duì)偶性質(zhì)（選讀）第16頁(yè)，共37頁(yè)，2023年，2月20日，星期四定理6.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-5-2-2-101

-6345000滿(mǎn)足①③④,但②不滿(mǎn)足第29頁(yè)，共37頁(yè)，2023年，2月20日，星期四0-1-5/21-1/2

-2111/20-1/2

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

210-21-1100111-11滿(mǎn)足①③④,但②不滿(mǎn)足滿(mǎn)足①②③④第30頁(yè)，共37頁(yè)，2023年，2月20日，星期四滿(mǎn)足①②③④是具有標(biāo)準(zhǔn)形式的LP的最優(yōu)解.

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

210-21-1100111-11第31頁(yè)，共37頁(yè)，2023年，2月20日，星期四例6.

用對(duì)偶單純形法求解：引入松弛變量得到標(biāo)準(zhǔn)型線(xiàn)性規(guī)劃解：第32頁(yè)，共37頁(yè)，2023年，2月20日，星期四構(gòu)造對(duì)偶單純形表選取離基變量選取進(jìn)基變量-2-1-4010

-2-2-20-401

-31281612000滿(mǎn)足①③④,但②不滿(mǎn)足第33頁(yè)，共37頁(yè)，2023年，2月20日，星期四-2-1-4010

-2-2-20-401

-31281612000-2-1-4010

-21/21/2010-1/43/46216003-9滿(mǎn)足①③④,但②不滿(mǎn)足第34頁(yè)，共37頁(yè)，2023年，2月20日，星期四-2-1-4010

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

2