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

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

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

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

甲

21402乙

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

1281612問：充分利用設備機時，工廠應生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？1.對偶問題的提出線性規(guī)劃的對偶模型解：設甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學模型為：反過來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機器用于接受外加工，只收加工費，那么４種機器的機時如何定價才是最佳決策？線性規(guī)劃的對偶模型在市場競爭的時代，廠長的最佳決策顯然應符合兩條：

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

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

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

x2

原問題12y1

22≤128y2

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

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

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

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

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

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

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

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

的最小值不能小于10，Z

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

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

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

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

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

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