第三章線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶與靈敏度分析

第三章線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶與靈敏度分析第一頁(yè)，共二十八頁(yè)，2022年，8月28日線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題第三章線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶與靈敏度分析1對(duì)偶單純形法

2靈敏度分析

3第二頁(yè)，共二十八頁(yè)，2022年，8月28日某企業(yè)可生產(chǎn)A、B兩種產(chǎn)品，需消耗煤、電、油三種資源。有關(guān)數(shù)據(jù)如下表所示：試擬訂使總收入最大的生產(chǎn)方案。AB資源限量煤電油9445310360200300單位產(chǎn)品價(jià)格7123.1對(duì)偶問(wèn)題的提出第三頁(yè)，共二十八頁(yè)，2022年，8月28日AB資源限量煤電油9445310360200300單位產(chǎn)品價(jià)格712假若有另一家廠商提出要購(gòu)買(mǎi)其煤、電、油全部資源，并希望花費(fèi)盡量少，試建立購(gòu)買(mǎi)者的線(xiàn)性規(guī)劃模型。

第四頁(yè)，共二十八頁(yè)，2022年，8月28日原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系對(duì)稱(chēng)形式：原問(wèn)題：

對(duì)偶問(wèn)題：

第五頁(yè)，共二十八頁(yè)，2022年，8月28日原問(wèn)題對(duì)偶問(wèn)題目標(biāo)max型目標(biāo)min型有n個(gè)變量有n個(gè)約束有m個(gè)約束有m個(gè)變量目標(biāo)函數(shù)系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標(biāo)函數(shù)系數(shù)約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系(一)第六頁(yè)，共二十八頁(yè)，2022年，8月28日課堂練習(xí)請(qǐng)寫(xiě)出下述線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題：MaxZ=2x1+3x2s.t.x1+x2

≤350

x1≤1252x1+x2≤600x1,x2≥0第七頁(yè)，共二十八頁(yè)，2022年，8月28日非對(duì)稱(chēng)形式－不具備對(duì)稱(chēng)形式的一對(duì)線(xiàn)性規(guī)劃稱(chēng)為非對(duì)稱(chēng)形式的對(duì)偶規(guī)劃：例：s.t

第八頁(yè)，共二十八頁(yè)，2022年，8月28日原問(wèn)題對(duì)偶問(wèn)題第j個(gè)變量無(wú)限制第j個(gè)約束為等式約束第i個(gè)約束為等式約束第i個(gè)變量無(wú)限制原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系(二)第九頁(yè)，共二十八頁(yè)，2022年，8月28日原問(wèn)題對(duì)偶問(wèn)題目標(biāo)max型目標(biāo)min型有n個(gè)變量有n個(gè)約束有m個(gè)約束有m個(gè)變量目標(biāo)函數(shù)系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標(biāo)函數(shù)系數(shù)約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置原問(wèn)題對(duì)偶問(wèn)題第j個(gè)變量無(wú)限制第j個(gè)約束為等式約束第i個(gè)約束為等式約束第i個(gè)變量無(wú)限制關(guān)系(一)關(guān)系(二)第十頁(yè)，共二十八頁(yè)，2022年，8月28日課堂練習(xí)請(qǐng)寫(xiě)出下述線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題：MaxZ=4x1+5x2+2x3s.t.3x1+2x2+x3

≤204x1-

3x2

+3x3

≥

10x1+x2

+2x3=5x1,x3≥0第十一頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋?zhuān)Y源的影子價(jià)格

某工廠在計(jì)劃期內(nèi)安排Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需資源A、B、C如下表所示，并且該工廠每生產(chǎn)一單位產(chǎn)品Ⅰ可獲利50元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利100元，問(wèn)工廠應(yīng)分別生產(chǎn)多少產(chǎn)品和Ⅱ產(chǎn)品，才能使工廠獲利最多？

ⅠⅡ資源限量資源A11300資源B21400資源C01250第十二頁(yè)，共二十八頁(yè)，2022年，8月28日

ⅠⅡ資源限量資源A11300資源B21400資源C01250假如有另外一個(gè)工廠要求購(gòu)買(mǎi)該廠的資源A、B、C，那么應(yīng)該如何確定合理的價(jià)格呢？第十三頁(yè)，共二十八頁(yè)，2022年，8月28日影子價(jià)格的經(jīng)濟(jì)含義影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià)；影子價(jià)格表明資源增加對(duì)總效益產(chǎn)生的影響；第十四頁(yè)，共二十八頁(yè)，2022年，8月28日3.2對(duì)偶單純形法－單純形法回顧請(qǐng)用單純形法求解下述線(xiàn)性規(guī)劃問(wèn)題：MaxZ=2x1+x2s.t.3x1+5x2

≤156x1

+

2x2

≤

24x1,x2≥0第十五頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶單純形法適用條件（1）線(xiàn)性規(guī)劃問(wèn)題初始單純形表的b列中至少有一個(gè)基變量取值為負(fù)（2）在同一個(gè)表格的檢驗(yàn)數(shù)行中，全部檢驗(yàn)數(shù)非正第十六頁(yè)，共二十八頁(yè)，2022年，8月28日步驟例：請(qǐng)用對(duì)偶單純形法求解下述線(xiàn)性規(guī)劃問(wèn)題Minf=3x1+2x2s.t.3x1+x2

≥34x1

+

3x2

≥

6

x1

+

3x2

≥

2x1,x2≥0第十七頁(yè)，共二十八頁(yè)，2022年，8月28日課堂練習(xí)請(qǐng)用對(duì)偶單純形法求解下述線(xiàn)性規(guī)劃問(wèn)題Minf=x1+x2s.t.2x1+x2

≥4

x1

+

7x2

≥

7x1,x2≥0第十八頁(yè)，共二十八頁(yè)，2022年，8月28日課堂練習(xí)MinZ=3x1+2x2+

x3+4x4

s.t.2x1+4x2+5x3+x4

≥03x1-x2

+7x3-2x4

≥

25x1+2x2

+x3

+6x4

≥15x1~4≥0請(qǐng)用對(duì)偶單純形法求解下述線(xiàn)性規(guī)劃問(wèn)題第十九頁(yè)，共二十八頁(yè)，2022年，8月28日3.3靈敏度分析已知某企業(yè)計(jì)劃生產(chǎn)3種產(chǎn)品A、B、C，其資源消耗與利潤(rùn)如下表所示：

ABC資源限量資源甲11112資源乙12220利潤(rùn)586請(qǐng)問(wèn)，該企業(yè)應(yīng)該如何安排生產(chǎn)，才能使獲利最大？第二十頁(yè)，共二十八頁(yè)，2022年，8月28日3.3靈敏度分析背景：線(xiàn)性規(guī)劃模型的cj

、

bi

、

aij等系數(shù)是估計(jì)值：cj－市場(chǎng)條件；

bi－資源投入量；aij－工藝條件；第二十一頁(yè)，共二十八頁(yè)，2022年，8月28日任務(wù)：－系數(shù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解（基）保持不變；－若系數(shù)的變化使最優(yōu)解發(fā)生變化，如何最簡(jiǎn)便的求得新的最優(yōu)解；第二十二頁(yè)，共二十八頁(yè)，2022年，8月28日目標(biāo)函數(shù)系數(shù)cj的靈敏度分析－在保證最優(yōu)解的基變量不變的情況下，分析cj允許的變動(dòng)范圍cj

非基變量對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)變化，不影響其它檢驗(yàn)數(shù)；基變量對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)；第二十三頁(yè)，共二十八頁(yè)，2022年，8月28日約束條件右端項(xiàng)

bi

的靈敏度分析－分析bi允許的變動(dòng)范圍bi

設(shè)XB=B1b是最優(yōu)解，則有XB=B1b0；bi的變化不會(huì)影響檢驗(yàn)數(shù)；bi

的變化量bi

可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪?；第二十四?yè)，共二十八頁(yè)，2022年，8月28日增加新變量的靈敏度分析

ABC資源限量資源甲11112資源乙12220利潤(rùn)586若新開(kāi)發(fā)產(chǎn)品D，該產(chǎn)品需要消耗資源甲3個(gè)單位，乙2個(gè)單位，利潤(rùn)10元，請(qǐng)問(wèn)，投產(chǎn)D是否有利？第二十五頁(yè)，共二十八頁(yè)，2022年，8月28日增加新約束的靈敏度分析

ABC資源限量資源甲11112資源乙12220利潤(rùn)586若電力供應(yīng)緊張，最多供應(yīng)13個(gè)單位，而生產(chǎn)A、B、C每單位需要電力分別為2、1、3個(gè)單位，問(wèn)該企業(yè)的生產(chǎn)方案是否需要改變？第二十六頁(yè)，共二十八頁(yè)，2022年，8月28日已知LP問(wèn)題：

MaxZ=3x1+6x2s.t.-x1+2x2

≤12

x1

+

2x2

≤

7x1,x2≥0(1)分別對(duì)c1，c