高等數(shù)學(xué)課件 15-4 線性規(guī)劃的對(duì)偶理論

15-4線性規(guī)劃的對(duì)偶理論

設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表：產(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ì)偶問題的提出線性規(guī)劃的對(duì)偶模型解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：反過來問：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？線性規(guī)劃的對(duì)偶模型在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條：

（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。（2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶。設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學(xué)模型為：線性規(guī)劃的對(duì)偶模型把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。原問題與對(duì)偶問題對(duì)比表A（y1）

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

對(duì)偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（LP）必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，即任何一個(gè)求maxZ的LP都有一個(gè)求minZ的LP。其中的一個(gè)問題叫“原問題”，記為“P”，另一個(gè)稱為“對(duì)偶問題”，記為“D”。線性規(guī)劃的對(duì)偶模型2.原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系原問題-P對(duì)偶問題-D線性規(guī)劃的對(duì)偶模型23x1

x2

原問題12y1

22≤128y2

12≤816y340≤1612y404≤12對(duì)偶問題23線性規(guī)劃的對(duì)偶模型（1）對(duì)稱形式

特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù).原問題對(duì)偶問題目標(biāo)函數(shù)maxmin約束條件≤≥變量數(shù)量約束條件個(gè)數(shù)約束條件個(gè)數(shù)變量數(shù)量線性規(guī)劃的對(duì)偶模型例2.1寫出線性規(guī)劃問題的對(duì)偶問題解：首先將原問題變形為對(duì)稱形式

注意：以后不強(qiáng)調(diào)等式右段項(xiàng)b≥0，原因在對(duì)偶單純型表中只保證而不保證，故b可以是負(fù)數(shù)。線性規(guī)劃的對(duì)偶模型線性規(guī)劃的對(duì)偶模型(2)非對(duì)稱型對(duì)偶問題

若給出的線性規(guī)劃不是對(duì)稱形式，可以先化成對(duì)稱形式再寫對(duì)偶問題。也可直接按教材表2-2中的對(duì)應(yīng)關(guān)系寫出非對(duì)稱形式的對(duì)偶問題。線性規(guī)劃的對(duì)偶模型原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無約束=b約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)C目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)線性規(guī)劃的對(duì)偶模型例2.2寫出下列線性規(guī)劃問題的對(duì)偶問題.解：原問題的對(duì)偶問題為無約束線性規(guī)劃的對(duì)偶模型例2.3寫出下列線性規(guī)劃問題的對(duì)偶問題.解：原問題的對(duì)偶問題為線性規(guī)劃的對(duì)偶模型例2.4線性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)性質(zhì)1對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題minZ’=-CXs.t.-AX≤-b X≥0

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0對(duì)偶的定義對(duì)偶的定義maxW’=-Ybs.t.YA≥CY≤0對(duì)偶性質(zhì)性質(zhì)2

弱對(duì)偶原理(弱對(duì)偶性)：設(shè)和分別是問題(P)和(D)的可行解，則必有推論1:原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。推論2:

在一對(duì)對(duì)偶問題（P）和（D）中，若其中一個(gè)問題可行但目標(biāo)函數(shù)無界，則另一個(gè)問題無可行解；反之不成立。這也是對(duì)偶問題的無界性。對(duì)偶性質(zhì)無界（原）無可行解（對(duì)）關(guān)于無界性有如下結(jié)論：?jiǎn)栴}無界無可行解無可行解問題無界對(duì)偶問題原問題例2.5對(duì)偶性質(zhì)推論3：在一對(duì)對(duì)偶問題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行（如D），則該可行的問題目標(biāo)函數(shù)值無界。試估計(jì)它們目標(biāo)函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。（P）例2.6對(duì)偶性質(zhì)解：（D）

由觀察可知：=（1.1.1.1），=（1.1），分別是（P）和（D）的可行解。Z=10，W=40，故有，弱對(duì)偶定理成立。由推論⑴可知，W

的最小值不能小于10，Z

的最大值不能超過40。＜對(duì)偶性質(zhì)性質(zhì)3

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

例如:在一對(duì)對(duì)偶問題（P）和（D）中，可找到X*=（0.0.4.4），Y*=（1.2，0.2）,且Z=W28，則X*，Y*分別是P和D的最優(yōu)解。對(duì)偶性質(zhì)性質(zhì)4強(qiáng)對(duì)偶性：若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。

還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解。性質(zhì)5

互補(bǔ)松弛性：設(shè)X0和Y0分別是P問題和D問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量對(duì)偶性質(zhì)性質(zhì)5的應(yīng)用： 該性質(zhì)給出了已知一個(gè)問題最優(yōu)解求另一個(gè)問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊互補(bǔ)松弛條件由于松弛變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關(guān)系，建立對(duì)偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。對(duì)偶性質(zhì)例2.7

已知線性規(guī)劃的最優(yōu)解是X＊=(6,2,0)T,求其對(duì)偶問題的最優(yōu)解Y＊。解：寫出原問題的對(duì)偶問題，即標(biāo)準(zhǔn)化對(duì)偶性質(zhì)設(shè)對(duì)偶問題最優(yōu)解為Y＊＝(y1，y2),由互補(bǔ)松弛性定理可知，X＊和Y＊滿足：即：因?yàn)閄1=6≠0，X2=2≠0，所以對(duì)偶問題的第一、二個(gè)約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：解此線性方程組得y1=1,y2=1,從而對(duì)偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。對(duì)偶性質(zhì)例2.8已知線性規(guī)劃的對(duì)偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。解:對(duì)偶問題是標(biāo)準(zhǔn)化無約束對(duì)偶性質(zhì)設(shè)對(duì)偶問題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補(bǔ)松弛性定理可知，X＊和Y＊滿足：將Y＊=(0,-2)帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1?！遹2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，