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

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

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

第十三頁(yè)，共四十七頁(yè)，2022年，8月28日

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

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

（續(xù)）6.

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

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

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

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

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

x1x2x3x4x5B-1bx3x1x2

0012-51001-1010-12253510-f

000-1-3-215xj

x1x2x3x4x5bx3x4x5

121002101011001908045-f

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

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

XB

XN

XSbXS

BNIb

-f

CBCN00CBCN

0

0XB

IB-1NB-1B-1b

-f

0CN-CBB-1N

-CBB-1

-CBB-1bCB……第二十頁(yè)，共四十七頁(yè)，2022年，8月28日對(duì)偶問(wèn)題第二十一頁(yè)，共四十七頁(yè)，2022年，8月28日

y1y2y3y4y5B-1by2y3

-210-115011-213-g’

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

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

i

個(gè)約束條件的右端項(xiàng)

bi

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

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

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

x1x2x3x4x5x6B-1bx2x5x3

01020-0.820061-3.21/201-100.54016055-f

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

x1x2x3x4x5x6B-1bx2x5x3

01020-0.820061-3.21/201-100.54016055-f

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

-CBB-1

A不全

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

-CBB-1

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

-CBB-1

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

-CBB-1

A0，使B-1b0。四、對(duì)偶單純形法第三十三頁(yè)，共四十七頁(yè)，2022年，8月28日舉例原問(wèn)題對(duì)偶問(wèn)題第三十四頁(yè)，共四十七頁(yè)，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第三十五頁(yè)，共四十七頁(yè)，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第三十六頁(yè)，共四十七頁(yè)，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第三十七頁(yè)，共四十七頁(yè)，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第三十八頁(yè)，共四十七頁(yè)，2022年，8月28日例2.標(biāo)準(zhǔn)化找初始基變量第三十九頁(yè)，共四十七頁(yè)，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第四十頁(yè)，共四十七頁(yè)，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(課本）第四十一頁(yè)，共四十七頁(yè)，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第四十二頁(yè)，共四十七頁(yè)，2022年，8月28日xi

x1x2x3x4x5B-1bx4x5

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

-2-3-4000x4x1

0-5/2