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

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

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

第13頁，共47頁，2023年，2月20日，星期一

原問題（對偶問題）約束條件對偶問題（原問題）決策變量max約束≤為正向約束≥為反向約束＝為雙向變量≥0為正向變量≤0為反向變量無約束為雙向min約束≥為正向約束≤為反向約束＝為雙向原問題和對偶問題的關系第14頁，共47頁，2023年，2月20日，星期一二、對偶問題的基本性質(zhì)

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

（續(xù)）6.

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

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

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

若原問題和對偶問題同時有可行解，則他們必都有最優(yōu)解。第16頁，共47頁，2023年，2月20日，星期一7.根據(jù)原問題最優(yōu)單純形表中的檢驗數(shù)可以讀出對偶問題的最優(yōu)解。例1、原問題對偶問題第17頁，共47頁，2023年，2月20日，星期一

原問題標準型第18頁，共47頁，2023年，2月20日，星期一xj

x1x2x3x4x5B-1bx3x1x2

0012-51001-1010-12253510-f

000-1-3-215xj

x1x2x3x4x5bx3x4x5

121002101011001908045-f

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

54000054第19頁，共47頁，2023年，2月20日，星期一常用單純形表的矩陣形式

XB

XN

XSbXS

BNIb

-f

CBCN00CBCN

0

0XB

IB-1NB-1B-1b

-f

0CN-CBB-1N

-CBB-1

-CBB-1bCB……第20頁，共47頁，2023年，2月20日，星期一對偶問題第21頁，共47頁，2023年，2月20日，星期一

y1y2y3y4y5B-1by2y3

-210-115011-213-g’

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

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

i

個約束條件的右端項

bi

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

*=CX*=Y*b=y1*b1+y2*b2+…+ym*bm現(xiàn)考慮在最優(yōu)解處，右端項bi的微小變動對目標函數(shù)值的影響，由上式，將f*對bi求偏導數(shù)：該式表明了，若原問題的某一個約束條件的右端項bi每增加一個單位，則由此引起的最優(yōu)目標函數(shù)值的增加量，就等于與該約束條件相對應的對偶變量的最優(yōu)解的值。第26頁，共47頁，2023年，2月20日，星期一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)濟意義。第27頁，共47頁，2023年，2月20日，星期一xj

x1x2x3x4x5x6B-1bx2x5x3

01020-0.820061-3.21/201-100.54016055-f

-100-20-0.2-790第28頁，共47頁，2023年，2月20日，星期一xj

x1x2x3x4x5x6B-1bx2x5x3

01020-0.820061-3.21/201-100.54016055-f

-100-20-0.2-790第29頁，共47頁，2023年，2月20日，星期一3.影子價格的作用①影子價格可以告訴管理人員，增加哪一種資源對增加經(jīng)濟效益最有益。②影子價格可以告訴管理人員，花多大的代價增加資源才是合算的。③影子價格在新產(chǎn)品開發(fā)決策中的應用。④影子價格在資源購銷決策中的應用。⑤利用影子價格分析工藝改變后對資源節(jié)約的收益。如在上例中，當工藝改進后，使原材料節(jié)約10%，則帶來的經(jīng)濟效益為：232010%=64（元）第30頁，共47頁，2023年，2月20日，星期一在利潤最大化的生產(chǎn)計劃中（1）邊際利潤大于0的資源沒有剩余（2）有剩余的資源邊際利潤等于0關于影子價格的幾點說明：第31頁，共47頁，2023年，2月20日，星期一影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0影子價格為0，資源并不一定有剩余影子價格是資源最優(yōu)配置下資源的理想價格，資源的影子價格與資源的緊缺度有關第32頁，共47頁，2023年，2月20日，星期一思路：(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。四、對偶單純形法第33頁，共47頁，2023年，2月20日，星期一舉例原問題對偶問題第34頁，共47頁，2023年，2月20日，星期一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第35頁，共47頁，2023年，2月20日，星期一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第36頁，共47頁，2023年，2月20日，星期一例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第37頁，共47頁，2023年，2月20日，星期一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第38頁，共47頁，2023年，2月20日，星期一例2.標準化找初始基變量第39頁，共47頁，2023年，2月20日，星期一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第40頁，共47頁，2023年，2月20日，星期一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(課本）第41頁，共47頁，2023年，2月20日，星期一練習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第42頁，共47頁，2023年，2月20日，星期一xi

x1x2x3x4x5B-1bx4x5

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

-2-3-4000x4x1

0-5