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

第三章線性規(guī)劃問題的對(duì)偶與靈敏度分析第一頁，共二十八頁，編輯于2023年，星期四線性規(guī)劃的對(duì)偶問題第三章線性規(guī)劃問題的對(duì)偶與靈敏度分析1對(duì)偶單純形法

2靈敏度分析

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

第四頁，共二十八頁，編輯于2023年，星期四原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系對(duì)稱形式：原問題：

對(duì)偶問題：

第五頁，共二十八頁，編輯于2023年，星期四原問題對(duì)偶問題目標(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)置原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系(一)第六頁，共二十八頁，編輯于2023年，星期四課堂練習(xí)請(qǐng)寫出下述線性規(guī)劃的對(duì)偶問題：MaxZ=2x1+3x2s.t.x1+x2

≤350

x1≤1252x1+x2≤600x1,x2≥0第七頁，共二十八頁，編輯于2023年，星期四非對(duì)稱形式－不具備對(duì)稱形式的一對(duì)線性規(guī)劃稱為非對(duì)稱形式的對(duì)偶規(guī)劃：例：s.t

第八頁，共二十八頁，編輯于2023年，星期四原問題對(duì)偶問題第j個(gè)變量無限制第j個(gè)約束為等式約束第i個(gè)約束為等式約束第i個(gè)變量無限制原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系(二)第九頁，共二十八頁，編輯于2023年，星期四原問題對(duì)偶問題目標(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)置原問題對(duì)偶問題第j個(gè)變量無限制第j個(gè)約束為等式約束第i個(gè)約束為等式約束第i個(gè)變量無限制關(guān)系(一)關(guān)系(二)第十頁，共二十八頁，編輯于2023年，星期四課堂練習(xí)請(qǐng)寫出下述線性規(guī)劃的對(duì)偶問題：MaxZ=4x1+5x2+2x3s.t.3x1+2x2+x3

≤204x1-

3x2

+3x3

≥

10x1+x2

+2x3=5x1,x3≥0第十一頁，共二十八頁，編輯于2023年，星期四對(duì)偶問題的經(jīng)濟(jì)解釋－資源的影子價(jià)格

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

ⅠⅡ資源限量資源A11300資源B21400資源C01250第十二頁，共二十八頁，編輯于2023年，星期四

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

≤156x1

+

2x2

≤

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

≥34x1

+

3x2

≥

6

x1

+

3x2

≥

2x1,x2≥0第十七頁，共二十八頁，編輯于2023年，星期四課堂練習(xí)請(qǐng)用對(duì)偶單純形法求解下述線性規(guī)劃問題Minf=x1+x2s.t.2x1+x2

≥4

x1

+

7x2

≥

7x1,x2≥0第十八頁，共二十八頁，編輯于2023年，星期四課堂練習(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ì)偶單純形法求解下述線性規(guī)劃問題第十九頁，共二十八頁，編輯于2023年，星期四3.3靈敏度分析已知某企業(yè)計(jì)劃生產(chǎn)3種產(chǎn)品A、B、C，其資源消耗與利潤如下表所示：

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

、

bi

、

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

bi－資源投入量；aij－工藝條件；第二十一頁，共二十八頁，編輯于2023年，星期四任務(wù)：－系數(shù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解（基）保持不變；－若系數(shù)的變化使最優(yōu)解發(fā)生變化，如何最簡便的求得新的最優(yōu)解；第二十二頁，共二十八頁，編輯于2023年，星期四目標(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ù)；第二十三頁，共二十八頁，編輯于2023年，星期四約束條件右端項(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)榉强尚薪猓坏诙捻?，共二十八頁，編輯?023年，星期四增加新變量的靈敏度分析

ABC資源限量資源甲11112資源乙12220利潤586若新開發(fā)產(chǎn)品D，該產(chǎn)品需要消耗資源甲3個(gè)單位，乙2個(gè)單位，利潤10元，請(qǐng)問，投產(chǎn)D是否有利？第二十五頁，共二十八頁，編輯于2023年，星期四增加新約束的靈敏度分析

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

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

≤12

x1

+

2x2

≤

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