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

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

2靈敏度分析

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

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

對偶問題：

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

≤350

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

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

≤204x1-

3x2

+3x3

≥

10x1+x2

+2x3=5x1,x3≥0第十一頁，共二十八頁，2022年，8月28日對偶問題的經(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第十二頁，共二十八頁，2022年，8月28日

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

≤156x1

+

2x2

≤

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

≥34x1

+

3x2

≥

6

x1

+

3x2

≥

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

≥4

x1

+

7x2

≥

7x1,x2≥0第十八頁，共二十八頁，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請用對偶單純形法求解下述線性規(guī)劃問題第十九頁，共二十八頁，2022年，8月28日3.3靈敏度分析已知某企業(yè)計劃生產(chǎn)3種產(chǎn)品A、B、C，其資源消耗與利潤如下表所示：

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

、

bi

、

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

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

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

bi

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

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

的變化量bi

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

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

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

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

≤12

x1

+

2x2

≤

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