第三章對偶問題2023/6/21第一頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型 設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機時數(shù)列于下表：產(chǎn)品數(shù)據(jù)表設(shè)備產(chǎn)品ABCD產(chǎn)品利潤（元／件）

甲

21402乙

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

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

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

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

第五頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型原問題與對偶問題的對應(yīng)關(guān)系原問題（對偶問題）對偶問題（原問題）以上是依據(jù)經(jīng)濟問題推導(dǎo)出對偶問題，還可以用代數(shù)方法推導(dǎo)出對偶問題。第六頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型

二、對偶定義(1)對稱形式：互為對偶(LP)Maxz=CX

(DP)Minw=Ybs.t.AX≤bs.t.YA≥CX≥0Y≥0“Max--≤”“Min--≥”特點：目標(biāo)函數(shù)求極大值時，所有約束條件為≤號，變量非負(fù);目標(biāo)函數(shù)求極小值時，所有約束條件為≥號，變量非負(fù).對稱形式的線性規(guī)劃的對偶問題也是對稱形式。式中Y為行向量Y=(y1,y2,…ym)第七頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型例3.1寫出線性規(guī)劃問題的對偶問題解：首先將原問題變形為對稱形式第八頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型第九頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型(2)非對稱型對偶問題 若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。也可以根據(jù)對偶的基本定理，也可直接按教材表3-5中的對應(yīng)關(guān)系直接寫出非對稱形式的對偶問題。對偶的基本定理：若一個問題的某約束為等式，那么對應(yīng)的對偶問題的相應(yīng)變量無約束；反之，若一個問題的某變量無約束，那么對應(yīng)的對偶問題的相應(yīng)約束為等式。第十頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型原問題（或?qū)ε紗栴}）對偶問題（或原問題）約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=第十一頁，共三十八頁，編輯于2023年，星期四線性規(guī)劃的對偶模型例3.2寫出下列線性規(guī)劃問題的對偶問題.解：原問題的對偶問題為第十二頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)性質(zhì)1對稱性定理：對偶問題的對偶是原問題minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0設(shè)原問題是（記為LP）：對偶問題是（記為DP）：這里A是m×n矩陣，X是n×1列向量，Y是1×m行向量。假設(shè)Xs與Ys分別是（LP）與（DP）的松馳變量。第十三頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)性質(zhì)2

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

在一對對偶問題（P）和（D）中，若其中一個問題可行但目標(biāo)函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。第十四頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標(biāo)函數(shù)值無界。性質(zhì)3

最優(yōu)性定理：如果是原問題的可行解，是其對偶問題的可行解，并且:則是原問題的最優(yōu)解，是其對偶問題的最優(yōu)解。第十五頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)性質(zhì)4強對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。 還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。性質(zhì)5

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

已知線性規(guī)劃的最優(yōu)解是X＊=(6,2,0)T,求其對偶問題的最優(yōu)解Y＊。解：寫出原問題的對偶問題，即標(biāo)準(zhǔn)化第十八頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)設(shè)對偶問題最優(yōu)解為Y＊＝(y1，y2),由互補松弛性定理可知，X＊和Y＊滿足：即：因為X1≠0，X2≠0，所以對偶問題的第一、二個約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。第十九頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)例3.4已知線性規(guī)劃的對偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。解:對偶問題是標(biāo)準(zhǔn)化第二十頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)設(shè)對偶問題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補松弛性定理可知，X＊和Y＊滿足：將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1?！遹2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，x5分別帶入原問題約束方程中，得：解方程組得：x1=-5,x3=-1,所以原問題的最優(yōu)解為X＊=(-5,0,-1)，最優(yōu)值z=-12第二十一頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)例3.5分別求解下列2個互為對偶關(guān)系的線性規(guī)劃問題3分別用單純形法求解上述2個規(guī)劃問題，得到最終單純形表如下表：性質(zhì)6解的對應(yīng)關(guān)系：原線性規(guī)劃問題(LP)單純形表的檢驗數(shù)行對應(yīng)對偶問題(LD)的一個基解。第二十二頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)XBb原問題的變量原問題的松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000－1/4－1/2XBb對偶問題的變量對偶問題的剩余變量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原問題最優(yōu)表對偶問題最優(yōu)表第二十三頁，共三十八頁，編輯于2023年，星期四對偶性質(zhì)原問題與其對偶問題的變量與解的對應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量。第二十四頁，共三十八頁，編輯于2023年，星期四表2－3一個問題max另一個問題min有最優(yōu)解有最優(yōu)解性質(zhì)4無最優(yōu)解無最優(yōu)解無最優(yōu)解性質(zhì)4無界解（有可行解）無可行解性質(zhì)2無可行解無界解（有可行解）應(yīng)用已知最優(yōu)解通過解方程求最優(yōu)解性質(zhì)5已知檢驗數(shù)檢驗數(shù)乘以－1求得基本解性質(zhì)6對偶性質(zhì)原問題與對偶問題解的對應(yīng)關(guān)系小結(jié)第二十五頁，共三十八頁，編輯于2023年，星期四對偶問題的經(jīng)濟解釋－影子價格1.影子價格的數(shù)學(xué)分析：定義：在一對P和D中，若P的某個約束條件的右端項常數(shù)bi（第i種資源的擁有量）增加一個單位時，所引起目標(biāo)函數(shù)最優(yōu)值z*的改變量稱為第i種資源的影子價格，其值等于D問題中對偶變量yi*。由對偶問題的基本性質(zhì)可得：第二十六頁，共三十八頁，編輯于2023年，星期四對偶問題的經(jīng)濟解釋－影子價格2.影子價格的經(jīng)濟意義1）影子價格是一種邊際價格，表明資源增加對總效益產(chǎn)生的影響。

在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量yi就是第i種資源的影子價格。即：影子價格反映的是不同的局部或個體的增量可以獲得不同的整體經(jīng)濟效益。如果為了擴大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。第二十七頁，共三十八頁，編輯于2023年，星期四對偶問題的經(jīng)濟解釋－影子價格2）影子價格是一種機會成本 影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。在引例中，企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設(shè)備用于外加工或出租，若租費高于某設(shè)備的影子價格，可考慮出租該設(shè)備，否則不宜出租。第二，是否將投資用于購買設(shè)備，以擴大生產(chǎn)能力，若市價低于某設(shè)備的影子價格，可考慮買進(jìn)該設(shè)備，否則不宜買進(jìn)。第二十八頁，共三十八頁，編輯于2023年，星期四對偶問題的經(jīng)濟解釋－影子價格3）影子價格在資源利用中的應(yīng)用根據(jù)對偶理論的互補松弛性定理:Y*Xs=0,YsX*=0表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為0；若當(dāng)資源的影子價格不為0時，表明該種資源在生產(chǎn)中已耗費完。第二十九頁，共三十八頁，編輯于2023年，星期四對偶單純形法對偶單純形法基本思路：

對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)非正）。如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校?dāng)同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解。第三十頁，共三十八頁，編輯于2023年，星期四對偶單純形法找出一個DP的可行基LP是否可行（XB≥0）保持DP為可行解情況下轉(zhuǎn)移到LP的另一個基本解最優(yōu)解是否循環(huán)結(jié)束第三十一頁，共三十八頁，編輯于2023年，星期四例3.5用對偶單純形法求解min

w=2x1

+

3x2

+

4x3x1

+

2x2

+

x3

≥

12x1

-

x2

+

3x3

≥

4x1,x2,x3

≥

0解：max

z=-2x1

-

3x2

-

4x3

+

0x4

+

0x5-x1

-

2x2

-

x3

+

x4

=-1-2x1

+

x2

-

3x3

+

x5=-4x1,x2,x3,x4,x5

≥

0對偶單純形法第三十二頁，共三十八頁，編輯于2023年，星期四-2-3-400CBXBbx1x2x3x4X50x4-10x5-4出出出∵x4,x5<0∴非最優(yōu)0x410-5/21/21-1/2-2x121-1/23/20-1/2-2-3-400CBXBbx1x2x3x4X50x4-1-1-2-1100x5-4-21-301-2-3-400CBXBbx1x2x3x4X50x4-1-1-2-1100x5-4-21-301σj-2-3-400θ1--4/30x410-5/21/21-1/2-2x121-1/23/20-1/2σj0-4-10-1∵x1,x4>0∴最優(yōu)最優(yōu)解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目標(biāo)值：w*=-z*=4對偶單純形法cj第三十三頁，共三十八頁，編輯于2023年，星期四對偶單純形法對偶單純形法應(yīng)注意的問題：

用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準(zhǔn)則最小比值中的絕對值是使得比值非負(fù)，在極小化問題σj≥0，分母aij<0這時必須取絕對值。在極大化問題中，σ

j≤0，分母aij<0，總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫成這里σj≤0在求θk時就可以不帶絕對值符號。第三十四頁，共三十八頁，編輯于2023年，星期四對偶單純形法對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進(jìn)基變量；普通單純形法的最