對偶及對偶單純形法

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

學習要點：

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

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

“對偶”，在不同的領域有著不同的詮釋。在詞語中，它是一種修辭方式，指兩個字數(shù)相等、結構相似的語句，旨表達出相關或相反的意思。如：“下筆千言，離題萬里”周長一定，面積最大的矩形是正方形；面積一定，周長最小的矩形是正方形。

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

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

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

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

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

甲

21402乙

22043設備可利用機時數(shù)（時）

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

付出的代價最小，且對方能接受。第六頁，共三十七頁，2022年，8月28日在市場競爭的時代，廠長的最佳決策應符合兩條：

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

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

特點：目標函數(shù)求極大值時，所有約束條件為≤號，變量非負;目標函數(shù)求極小值時，所有約束條件為≥號，變量非負.原始線性規(guī)劃問題對偶線性規(guī)劃問題對稱形式的線性規(guī)劃第十頁，共三十七頁，2022年，8月28日線性規(guī)劃的對偶模型例2寫出線性規(guī)劃問題的對偶問題解：由于若給出的線性規(guī)劃不是對稱形式，所以先將它化成對稱形式，然后再寫出相應的對偶問題。第十一頁，共三十七頁，2022年，8月28日解：首先將原問題變形為則對偶模型為：第十二頁，共三十七頁，2022年，8月28日線性規(guī)劃的對偶變換規(guī)則(單向)原問題（或?qū)ε紗栴}）對偶問題（或原問題）約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項目標函數(shù)max目標函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=第十三頁，共三十七頁，2022年，8月28日對偶問題的形成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原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)；原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)，用表示原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)，用表示第十四頁，共三十七頁，2022年，8月28日例4:寫出下列線性規(guī)劃問題的對偶問題.解：原問題的對偶問題為第十五頁，共三十七頁，2022年，8月28日定理6.1(對合性)

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

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

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

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

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

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

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

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

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

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

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

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

③④三個特點的單純形表;3）檢查右列元素，若全非負，即表格滿足①②

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

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

-5-2-2-101

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

-2111/20-1/2

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

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

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

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

用對偶單純形法求解：引入松弛變量得到標準型線性規(guī)劃解：第三十二頁，共三十七頁，2022年，8月28日構造對偶單純形表選取離基變量選取進基變量-2-1-4010

-2-2-20-401

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

-2-2-20-401

-31281612000-2-1-4010

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

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

2-1/2