對偶理論第三章線性規(guī)劃

對偶理論第三章線性規(guī)劃第一頁，共四十七頁，2022年，8月28日該問題的數(shù)學(xué)模型如果設(shè)A、B兩種產(chǎn)品生產(chǎn)的件數(shù)分別為,則這個問題可以歸結(jié)為求解下列線性規(guī)劃問題：第二頁，共四十七頁，2022年，8月28日其對偶問題的數(shù)學(xué)模型設(shè)分別表示設(shè)備甲、乙、丙每臺時的價格（或租金）,則第三頁，共四十七頁，2022年，8月28日

例2、每頭牲畜每日對各種維生素的需求量及飼料商提供的營養(yǎng)飼料M和N中各種維生素含量及定價如下表所示，牧場主在保證牲畜維生素需求條件下，每日為每頭牲畜購M、N各多少可使總費用最少？MN日需要量ABCD0.100.10.200.10.20.10.40.62.01.7定價104維生素營養(yǎng)飼料第四頁，共四十七頁，2022年，8月28日設(shè)每日每頭牲畜需營養(yǎng)飼料M、N分別為，則該問題的線性規(guī)劃模型為：第五頁，共四十七頁，2022年，8月28日已知條件同上例，某藥品商想提供畜用維生素A、B、C、D四種營養(yǎng)藥品，在滿足牲畜營養(yǎng)要求且可與飼料商競爭條件下，四種藥品如何定價可使總收入最大？第六頁，共四十七頁，2022年，8月28日第七頁，共四十七頁，2022年，8月28日第八頁，共四十七頁，2022年，8月28日對稱的對偶問題原問題對偶問題第九頁，共四十七頁，2022年，8月28日對稱的對偶問題原問題對偶問題第十頁，共四十七頁，2022年，8月28日非對稱的對偶問題原問題對偶問題第十一頁，共四十七頁，2022年，8月28日混合形式的對偶問題第十二頁，共四十七頁，2022年，8月28日原問題和對偶問題的關(guān)系

第十三頁，共四十七頁，2022年，8月28日

原問題（對偶問題）約束條件對偶問題（原問題）決策變量max約束≤為正向約束≥為反向約束＝為雙向變量≥0為正向變量≤0為反向變量無約束為雙向min約束≥為正向約束≤為反向約束＝為雙向原問題和對偶問題的關(guān)系第十四頁，共四十七頁，2022年，8月28日二、對偶問題的基本性質(zhì)

1.弱對偶性：若X和Y分別是原問題和對偶問題的任一可行解，則必有該性質(zhì)告訴我們，最大化問題的任一可行解的目標(biāo)函數(shù)值都是其對偶最小化問題目標(biāo)函數(shù)的下界；而最小化問題的任一可行解的目標(biāo)函數(shù)值都是其對偶最大化問題目標(biāo)函數(shù)的上界。2.強對偶性：若分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問題和對偶問題的目標(biāo)函數(shù)值相等，即，則分別為原問題和對偶問題的最優(yōu)解。（最優(yōu)性準(zhǔn)則）（對偶可行性）第十五頁，共四十七頁，2022年，8月28日二、對偶問題的基本性質(zhì)

（續(xù)）6.

若原問題的最優(yōu)解為3.無界性

若原問題（對偶問題）的目標(biāo)函數(shù)無界，則其對偶問題（原問題）必?zé)o可行解。該性質(zhì)說明，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。4.對偶定理

若原問題和對偶問題之一有最優(yōu)解，則另一個也也有最優(yōu)解，且兩者的最優(yōu)目標(biāo)函數(shù)值相等。5.

若原問題和對偶問題同時有可行解，則他們必都有最優(yōu)解。第十六頁，共四十七頁，2022年，8月28日7.根據(jù)原問題最優(yōu)單純形表中的檢驗數(shù)可以讀出對偶問題的最優(yōu)解。例1、原問題對偶問題第十七頁，共四十七頁，2022年，8月28日

原問題標(biāo)準(zhǔn)型第十八頁，共四十七頁，2022年，8月28日xj

x1x2x3x4x5B-1bx3x1x2

0012-51001-1010-12253510-f

000-1-3-215xj

x1x2x3x4x5bx3x4x5

121002101011001908045-f

540000初始單純形表最優(yōu)單純形表原問題

54000054第十九頁，共四十七頁，2022年，8月28日常用單純形表的矩陣形式

XB

XN

XSbXS

BNIb

-f

CBCN00CBCN

0

0XB

IB-1NB-1B-1b

-f

0CN-CBB-1N

-CBB-1

-CBB-1bCB……第二十頁，共四十七頁，2022年，8月28日對偶問題第二十一頁，共四十七頁，2022年，8月28日

y1y2y3y4y5B-1by2y3

-210-115011-213-g’

-2500-35-10215對偶問題最優(yōu)單純形表：綜上所述，一對對偶問題的解必然是下列三種情況之一：1.原問題和對偶問題都有最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值相等。3.原問題和對偶問題都無可行解。2.一個問題具有無界解，則另一個問題無可行解。第二十二頁，共四十七頁，2022年，8月28日Cj58600CBXBX1X2X3X4X5B-1b58X1X21001202-1-1124λj00-4-2-3-42maxf=5X1+8X2+6X3X1+X2+2X3≤6X1+2X2+2X3≤10X1，X2,X2≥0第二十三頁，共四十七頁，2022年，8月28日例3已知線性規(guī)劃問題試用對偶理論證明上述問題無最優(yōu)解。第二十四頁，共四十七頁，2022年，8月28日三、對偶解的經(jīng)濟涵義——影子價格通過求解：原問題和對偶問題的最優(yōu)解分別為第二十五頁，共四十七頁，2022年，8月28日1.影子價格的定義對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價格（ShadowPrice）。

影子價格是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)?/p>

i

個約束條件的右端項

bi

增加一個單位時，目標(biāo)函數(shù)的變化量。由對偶定理可知，當(dāng)達到最優(yōu)解時，原問題與對偶問題的目標(biāo)函數(shù)值相等，即有f

*=CX*=Y*b=y1*b1+y2*b2+…+ym*bm現(xiàn)考慮在最優(yōu)解處，右端項bi的微小變動對目標(biāo)函數(shù)值的影響，由上式，將f*對bi求偏導(dǎo)數(shù)：該式表明了，若原問題的某一個約束條件的右端項bi每增加一個單位，則由此引起的最優(yōu)目標(biāo)函數(shù)值的增加量，就等于與該約束條件相對應(yīng)的對偶變量的最優(yōu)解的值。第二十六頁，共四十七頁，2022年，8月28日2.影子價格的求法

例4某工廠生產(chǎn)三種產(chǎn)品，三種產(chǎn)品對于原材料、勞動力、電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價格如下表所示：ABC資源限量原材料（kg）勞動力（人）電力（度）2652.5154810320640750單位價格（元）4610資源產(chǎn)品1.求最佳生產(chǎn)方案使總產(chǎn)值最大。2.求各資源的影子價格，并解釋其經(jīng)濟意義。第二十七頁，共四十七頁，2022年，8月28日xj

x1x2x3x4x5x6B-1bx2x5x3

01020-0.820061-3.21/201-100.54016055-f

-100-20-0.2-790第二十八頁，共四十七頁，2022年，8月28日xj

x1x2x3x4x5x6B-1bx2x5x3

01020-0.820061-3.21/201-100.54016055-f

-100-20-0.2-790第二十九頁，共四十七頁，2022年，8月28日3.影子價格的作用①影子價格可以告訴管理人員，增加哪一種資源對增加經(jīng)濟效益最有益。②影子價格可以告訴管理人員，花多大的代價增加資源才是合算的。③影子價格在新產(chǎn)品開發(fā)決策中的應(yīng)用。④影子價格在資源購銷決策中的應(yīng)用。⑤利用影子價格分析工藝改變后對資源節(jié)約的收益。如在上例中，當(dāng)工藝改進后，使原材料節(jié)約10%，則帶來的經(jīng)濟效益為：232010%=64（元）第三十頁，共四十七頁，2022年，8月28日在利潤最大化的生產(chǎn)計劃中（1）邊際利潤大于0的資源沒有剩余（2）有剩余的資源邊際利潤等于0關(guān)于影子價格的幾點說明：第三十一頁，共四十七頁，2022年，8月28日影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0影子價格為0，資源并不一定有剩余影子價格是資源最優(yōu)配置下資源的理想價格，資源的影子價格與資源的緊缺度有關(guān)第三十二頁，共四十七頁，2022年，8月28日思路：(max型)單純形法：找基B，滿足B-1b0，但檢驗數(shù)C

-CBB-1

A不全

0。迭代保持B-1b0，使C

-CBB-1

A0。對偶單純形法：找基B，滿足C

-CBB-1

A0，但B-1b不全0。迭代保持C

-CBB-1

A0，使B-1b0。四、對偶單純形法第三十三頁，共四十七頁，2022年，8月28日舉例原問題對偶問題第三十四頁，共四十七頁，2022年，8月28日xj

x1x2x3x4x5B-1bx3x4x5

05100620101100115245-f

210000x3x1x5

0510011/301/6002/30-1/611541-f

01/30-1/30-8x3x1x2

0015/4-15/21001/4-1/2010-1/43/215/27/23/2-f

000-1/4-1/2-17/2第三十五頁，共四十七頁，2022年，8月28日yi

y1y2y3y4y5B-1by4y5

0-6-110-5-2-101-2-1-f

-15-24-5000y2y5

011/6-1/60-50-2/3-1/311/3-1/3-f

-150-1-40-8y2y3

-5/410-1/41/415/2011/2-3/21/41/2-f-15/200-7/2-3/2-17/2第三十六頁，共四十七頁，2022年，8月28日例1maxf=2x1

+x2x1+x2+x3=

52x2+x354x2+6x3

9x1,x2,x30maxf=2x1+x2x1+x2+x3=

52x2+x3+x4=5-4x2–6x3+x5=-9x1…x5

0第三十七頁，共四十七頁，2022年，8月28日xj

x1x2x3x4x5B-1bx1x4x5

11100021100-4-60155-9-f

0-1-200-10210000200x1x4x2

10-1/201/400-21-1/2013/20-1/411/41/29/4-f

00-1/20-1/4-31/4201第三十八頁，共四十七頁，2022年，8月28日例2.標(biāo)準(zhǔn)化找初始基變量第三十九頁，共四十七頁，2022年，8月28日xj

x1x2x3x4x5bix3x4x5

22100-3-2010120013-41-f

-1-30000xj

x1x2x3x4x5B-1bx3x1x5

-f02/312/301/312/30-1/304/304/301/31-1/30-7/30-1/304/3第四十頁，共四十七頁，2022年，8月28日Xj

x1x2x3x4x5B-1bx3x4x5

-2-1100-3-2010-1-2001-3-4-1-f

-1-30000x3x1x5

01/31-2/3012/30-1/300-4/30-1/31-1/34/31/3-f

0-7/30-1/304/3x4x1x5

0-1/2-3/21011/2-1/2000-3/2-1/2011/23/21/2-f

0-5/2-1/2003/2例3(課本）第四十一頁，共四十七頁，2022年，8月28日練習(xí)minf=2x1+3x2+4x3

x1+2x2+x3

32x1-x2+3x34x1,x2,x30minf=2x1+3x2+4x3

-x1–2x2-x3+x4=-

3-2x1+x2–3x3+x5=-

4x1…x5

0第四十二頁，共四十七頁，2022年，8月28日xi

x1x2x3x4x5B-1bx4x5

-1-2-110-21-301-3-4-f

-2-3-4000x4x1

0-5/2