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

第三章線性規(guī)劃問題的對偶與靈敏度分析第1頁，共28頁，2023年，2月20日，星期三線性規(guī)劃的對偶問題第三章線性規(guī)劃問題的對偶與靈敏度分析1對偶單純形法

2靈敏度分析

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

第4頁，共28頁，2023年，2月20日，星期三原問題與對偶問題的對應(yīng)關(guān)系對稱形式：原問題：

對偶問題：

第5頁，共28頁，2023年，2月20日，星期三原問題對偶問題目標max型目標min型有n個變量有n個約束有m個約束有m個變量目標函數(shù)系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標函數(shù)系數(shù)約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置原問題與對偶問題的對應(yīng)關(guān)系(一)第6頁，共28頁，2023年，2月20日，星期三課堂練習請寫出下述線性規(guī)劃的對偶問題：MaxZ=2x1+3x2s.t.x1+x2

≤350

x1≤1252x1+x2≤600x1,x2≥0第7頁，共28頁，2023年，2月20日，星期三非對稱形式－不具備對稱形式的一對線性規(guī)劃稱為非對稱形式的對偶規(guī)劃：例：s.t

第8頁，共28頁，2023年，2月20日，星期三原問題對偶問題第j個變量無限制第j個約束為等式約束第i個約束為等式約束第i個變量無限制原問題與對偶問題的對應(yīng)關(guān)系(二)第9頁，共28頁，2023年，2月20日，星期三原問題對偶問題目標max型目標min型有n個變量有n個約束有m個約束有m個變量目標函數(shù)系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標函數(shù)系數(shù)約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置原問題對偶問題第j個變量無限制第j個約束為等式約束第i個約束為等式約束第i個變量無限制關(guān)系(一)關(guān)系(二)第10頁，共28頁，2023年，2月20日，星期三課堂練習請寫出下述線性規(guī)劃的對偶問題：MaxZ=4x1+5x2+2x3s.t.3x1+2x2+x3

≤204x1-

3x2

+3x3

≥

10x1+x2

+2x3=5x1,x3≥0第11頁，共28頁，2023年，2月20日，星期三對偶問題的經(jīng)濟解釋－資源的影子價格

某工廠在計劃期內(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第12頁，共28頁，2023年，2月20日，星期三

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

≤156x1

+

2x2

≤

24x1,x2≥0第15頁，共28頁，2023年，2月20日，星期三對偶單純形法適用條件（1）線性規(guī)劃問題初始單純形表的b列中至少有一個基變量取值為負（2）在同一個表格的檢驗數(shù)行中，全部檢驗數(shù)非正第16頁，共28頁，2023年，2月20日，星期三步驟例：請用對偶單純形法求解下述線性規(guī)劃問題Minf=3x1+2x2s.t.3x1+x2

≥34x1

+

3x2

≥

6

x1

+

3x2

≥

2x1,x2≥0第17頁，共28頁，2023年，2月20日，星期三課堂練習請用對偶單純形法求解下述線性規(guī)劃問題Minf=x1+x2s.t.2x1+x2

≥4

x1

+

7x2

≥

7x1,x2≥0第18頁，共28頁，2023年，2月20日，星期三課堂練習MinZ=3x1+2x2+

x3+4x4

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

≥03x1-x2

+7x3-2x4

≥

25x1+2x2

+x3

+6x4

≥15x1~4≥0請用對偶單純形法求解下述線性規(guī)劃問題第19頁，共28頁，2023年，2月20日，星期三3.3靈敏度分析已知某企業(yè)計劃生產(chǎn)3種產(chǎn)品A、B、C，其資源消耗與利潤如下表所示：

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

、

bi

、

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

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

非基變量對應(yīng)的目標函數(shù)系數(shù)變化，不影響其它檢驗數(shù)；基變量對應(yīng)的目標函數(shù)系數(shù)變化，影響所有非基變量檢驗數(shù)；第23頁，共28頁，2023年，2月20日，星期三約束條件右端項

bi

的靈敏度分析－分析bi允許的變動范圍bi

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

的變化量bi

可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪猓坏?4頁，共28頁，2023年，2月20日，星期三增加新變量的靈敏度分析

ABC資源限量資源甲11112資源乙12220利潤586若新開發(fā)產(chǎn)品D，該產(chǎn)品需要消耗資源甲3個單位，乙2個單位，利潤10元，請問，投產(chǎn)D是否有利？第25頁，共28頁，2023年，2月20日，星期三增加新約束的靈敏度分析

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

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

≤12

x1

+

2x2

≤

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