線性規(guī)劃的對偶理論ppt第1頁，課件共40頁，創(chuàng)作于2023年2月主要內(nèi)容原規(guī)劃與對偶規(guī)劃的轉(zhuǎn)換對偶定理影子價格的概念和經(jīng)濟(jì)學(xué)意義對偶單純形法靈敏度分析的目的和主要內(nèi)容第2頁，課件共40頁，創(chuàng)作于2023年2月問題的提出線性規(guī)劃對偶問題線性規(guī)劃有一個有趣的特性，就是對于任何一個求極大值的線性規(guī)劃問題都存在一個與其對應(yīng)的極小值線性規(guī)劃問題，而且二者之間聯(lián)系緊密，可以互相轉(zhuǎn)化。對偶性

（教材P53-54例題）從例子中可以看出：（1）原規(guī)劃問題為生產(chǎn)計劃問題，而其對偶問題為賦予該生產(chǎn)計劃可行性的潛在價值問題（2）原規(guī)劃的目標(biāo)函數(shù)是從資源擁有者的角度得出利潤最大化，而其對偶規(guī)劃的目標(biāo)函數(shù)是從想獲得該資源方的角度得出成本最小化

（3）兩個問題共用一套參數(shù)，但組合方式不同第3頁，課件共40頁，創(chuàng)作于2023年2月原問題和對偶問題的關(guān)系原問題（P）對偶問題（D）決策變量xi第i種產(chǎn)品數(shù)量yi第i個約束條件目標(biāo)函數(shù)約束條件對偶問題在解釋資源的影子價格、擴(kuò)大單純形法計算方法以及對問題進(jìn)行靈敏度分析等方面有很多應(yīng)用。從表中可以看出對稱形式的對偶關(guān)系具有如下的對應(yīng)關(guān)系：目標(biāo)函數(shù)最大最?。患s束條件不大于不小于約束矩陣：一個為另一個的轉(zhuǎn)置常數(shù)向量b和c互換目標(biāo)變量皆為非負(fù)線性規(guī)劃對偶問題對稱形式對偶問題第4頁，課件共40頁，創(chuàng)作于2023年2月原問題和對偶問題的關(guān)系非對稱形式的對偶問題

不具備對稱形式的一對線性規(guī)劃稱為非對稱形式的對偶問題轉(zhuǎn)換方式為：4、若原規(guī)劃中的某個變量沒有非負(fù)限制，則在對偶問題中對應(yīng)的那個約束為等式。1、將模型統(tǒng)一為規(guī)范形式，然后先按對稱形式轉(zhuǎn)換2、對等式約束按（3）或（4）處理3、若原規(guī)劃中某個約束為等式，則在對偶規(guī)劃中與此對應(yīng)的變量取值沒有非負(fù)約束教材P56例題線性規(guī)劃對偶問題第5頁，課件共40頁，創(chuàng)作于2023年2月原問題和對偶問題的關(guān)系原問題與對偶問題的轉(zhuǎn)換線性規(guī)劃對偶問題第6頁，課件共40頁，創(chuàng)作于2023年2月原問題和對偶問題的關(guān)系原問題與對偶問題的轉(zhuǎn)換線性規(guī)劃對偶問題第7頁，課件共40頁，創(chuàng)作于2023年2月原問題和對偶問題的關(guān)系原問題與對偶問題的轉(zhuǎn)換線性規(guī)劃對偶問題第8頁，課件共40頁，創(chuàng)作于2023年2月對偶理論從本章的第一個例子可以看出原規(guī)劃問題追求的是生產(chǎn)利潤最大化，而其對偶規(guī)劃考慮的是比生產(chǎn)更有利的可行性。線性規(guī)劃對偶問題前者的目標(biāo)函數(shù)值應(yīng)當(dāng)不大于后者的目標(biāo)函數(shù)值，即定理3.1（弱對偶性）：若對偶規(guī)劃（D）的可行解，則分別為原規(guī)劃（P）和證明：從原規(guī)劃的約束條件有從對偶規(guī)劃的約束條件有第9頁，課件共40頁，創(chuàng)作于2023年2月對偶理論線性規(guī)劃對偶問題定理3.1（弱對偶性）：若對偶規(guī)劃（D）的可行解，則分別為原規(guī)劃（P）和推論1（最優(yōu)性）：

分別為原規(guī)劃（P）和對偶規(guī)劃（D）的可行解設(shè)若分別為P和D的最優(yōu)解則顯而易見推論2（無界性）：如原規(guī)劃（P）或其對偶規(guī)劃（D）具有無界解，則對偶規(guī)劃（D）或原規(guī)劃（P）無可行解。顯而易見注意：改推論不可逆，教材P58第10頁，課件共40頁，創(chuàng)作于2023年2月對偶理論線性規(guī)劃對偶問題推論3：若規(guī)劃（P）或（D）有可行解，則（P）或（D）有最優(yōu)解的充要條件是規(guī)劃（D）或（P）有可行解例試用對偶理論判斷下面線性規(guī)劃是否有最優(yōu)解解：此規(guī)劃存在可行解其對偶規(guī)劃為顯然無可行解所以…第11頁，課件共40頁，創(chuàng)作于2023年2月對偶理論線性規(guī)劃對偶問題例用對偶理論判斷下面線性規(guī)劃是否存在最優(yōu)解解此規(guī)劃存在可行解其對偶規(guī)劃為存在可行解因此原規(guī)劃存在最優(yōu)解第12頁，課件共40頁，創(chuàng)作于2023年2月對偶理論線性規(guī)劃對偶問題定理3.2（強(qiáng)對偶性，或稱對偶定理）：若原規(guī)劃（P）有最優(yōu)解，則對偶規(guī)劃（D）也有最優(yōu)解，反之亦然。且二者最優(yōu)解的目標(biāo)函數(shù)值相等。（證明：教材P58-59）在線性規(guī)劃問題的最優(yōu)解中，如果某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之，若如果約束條件取嚴(yán)格不等式，則其對偶變量一定為零。定理3.3（互補(bǔ)松弛性）：線性規(guī)劃問題的原問題和對偶問題存在一對互補(bǔ)的基本解，其中原問題的非基變量（松弛變量）對應(yīng)對偶問題的基變量，而對偶問題的非基變量（松弛變量）對應(yīng)原問題的基變量。定理3.4（互補(bǔ)基本解）：第13頁，課件共40頁，創(chuàng)作于2023年2月對偶理論線性規(guī)劃對偶問題線性規(guī)劃問題的原問題和對偶問題存在一對互補(bǔ)的基本解，其中原問題的非基變量（松弛變量）對應(yīng)對偶問題的基變量，而對偶問題的非基變量（松弛變量）對應(yīng)原問題的基變量。定理3.4（互補(bǔ)基本解）：在單純形法迭代的每一步：如果原問題是可行解，而對偶問題非可行解，則如果對偶問題是可行解，而原問題非可行解，則如果原問題和對偶問題同為可行解，則為最優(yōu)解第14頁，課件共40頁，創(chuàng)作于2023年2月影子價格線性規(guī)劃對偶問題考慮如下的互為對偶的線性規(guī)劃設(shè)為（D）的最優(yōu)解，則稱為規(guī)劃（P）的第i個約束對應(yīng)的影子價格（ShadowPrice）

換句話說，為第第i種資源（例如設(shè)備臺時）的一種估價

這個價格不是市場價格，而是針對具體企業(yè)在一定時期內(nèi)存在的一種特殊價格，它蘊含在追求最大利潤的生產(chǎn)計劃之中。資源的市場價格隨供求關(guān)系而變，而他的影子價格則有賴于資源的利用情況，隨企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化而改變。第15頁，課件共40頁，創(chuàng)作于2023年2月影子價格線性規(guī)劃對偶問題影子價格的經(jīng)濟(jì)含義

影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價，由此可以決定是否將既有資源出租或投資購買新資源。從這種意義上說，影子價格是一種機(jī)會成本。

影子價格是一種邊際價格，衡量資源變化對總效益的影響投資影子價格最高的資源可以讓總效益最大。但要注意，影子價格不是一成不變的，當(dāng)約束條件、產(chǎn)品利潤發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，資源增加有個度的問題，這在后面的靈敏度分析中會講到。定理3.3（互補(bǔ)松弛性）表明當(dāng)某種資源未得到充分利用時，即時，其影子價格為0。不為0，則說明該種資源已經(jīng)耗費完畢：而當(dāng)該資源的影子價格第16頁，課件共40頁，創(chuàng)作于2023年2月影子價格線性規(guī)劃對偶問題影子價格的經(jīng)濟(jì)含義

一般而言，線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定資源的恰當(dāng)估價。例如，用于公司內(nèi)部結(jié)算等。單純形法中各檢驗數(shù)的經(jīng)濟(jì)意義：某種產(chǎn)品的產(chǎn)值生產(chǎn)該產(chǎn)品的消耗資源的總和即隱含成本因此，當(dāng)檢驗數(shù)為正時，說明生產(chǎn)有利，可以在計劃中安排。第17頁，課件共40頁，創(chuàng)作于2023年2月影子價格線性規(guī)劃對偶問題例：某外貿(mào)公司準(zhǔn)備購進(jìn)兩種產(chǎn)品A1,A2。購進(jìn)產(chǎn)品A1,每件需要10元，占用5立方米的空間，待每件A1賣出后，可獲純利潤3元；購進(jìn)產(chǎn)品A2，每件需要15元，占用3立方米的空間，待每件A2賣出后，可獲純利潤4元。公司現(xiàn)有資金1400元，有430立方米的倉庫空間存放產(chǎn)品，根據(jù)這些條件，可以建立求最大的線性規(guī)劃模型：資源1資源2第18頁，課件共40頁，創(chuàng)作于2023年2月影子價格線性規(guī)劃對偶問題求解后的如下的最優(yōu)單純形表：cBxBb3400x1x2x3x44x260011/9-2/93x15010-1/151/3cj-zj00-11/45-1/9由表中可知最優(yōu)方案是分別購進(jìn)A1和A2產(chǎn)品50和60件，最大利潤為390元。假設(shè)公司現(xiàn)有閑余資金585元，準(zhǔn)備用于投資，增加每立方米倉庫需0.8元。問這筆資金是用來投資倉庫好呢還是購買產(chǎn)品好？第19頁，課件共40頁，創(chuàng)作于2023年2月影子價格線性規(guī)劃對偶問題cBxBb3400x1x2x3x44x260011/9-2/93x15010-1/151/3cj-zj00-11/45-1/9假設(shè)公司現(xiàn)有閑余資金585元，準(zhǔn)備用于投資，增加每立方米倉庫需0.8元。問這筆資金是用來投資倉庫好呢還是購買產(chǎn)品好？分析：

從表中個可以看出，對應(yīng)產(chǎn)品和倉庫的影子價格分別為11/45和1/9元。每投資1元用于倉庫的邊際效益為：1/9/0.8=0.14元每投資1元用于產(chǎn)品的邊際效益為11/45=0.24元應(yīng)該考慮購買產(chǎn)品將585元投資購買產(chǎn)品后，最大利潤增加為：585*11/45=143元可以通過新模型求解驗證，最優(yōu)解為第20頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題基本思路

從原規(guī)劃的一個基本解出發(fā)（未必為可行解），其對應(yīng)一個對偶可行解（檢驗數(shù)非正）。檢驗原規(guī)劃的基本解是否可行（即是否有負(fù)分量），如果有小于0的分量，則進(jìn)行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)非正）。如果得到的基本解的分量皆非負(fù)，則該解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解逐步變?yōu)榭尚?，并得到最?yōu)解。第21頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題主要步驟

建立初始單純形表。根據(jù)典式形式建立初始對偶單純形表，此表對應(yīng)原規(guī)劃一個基本解。要求：檢驗數(shù)行個元素皆非正，但原規(guī)劃基本解可以有小于零的分量。確定出基變量。若基本解的所有分量皆非負(fù)，則得到原規(guī)劃的最優(yōu)解。若基本解中有小于零的分量，且所在行所有系數(shù)，則原規(guī)劃無可行解。若，且存在，則確定最小的對應(yīng)變量為出基變量。

(3)確定進(jìn)基變量。計算確定為進(jìn)基變量

(4)迭代更新單純形表。以為中心元素，參照單純形法對表進(jìn)行迭代計算。(5)通過循環(huán)迭代找出最優(yōu)解。第22頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題例：用對偶單純形法求解下面的線性規(guī)劃（s.t.）第23頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題解：

(1)引入松弛變量 化為標(biāo)準(zhǔn)形,并在約束等式兩側(cè)同乘-1，得到 為基變量，此式即為典式形式，并且檢驗數(shù)皆非正，因此可構(gòu)造初始對偶單純形表。初始表中基本解的三個分量小于零，不是可行解，需進(jìn)行迭代求解新的基本解。第24頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題基本解分量<0，非可行最小x4為出基變量計算（與單純性表格計算反過來）確定x2為進(jìn)基變量因此，以a22=-3為中心元素，更新表格，并繼續(xù)迭代第25頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題仍然有負(fù)數(shù)，非可行最小x3為出基變量計算確定x1為進(jìn)基變量因此，以a11=-3/5為中心元素，更新表格，并繼續(xù)迭代第26頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題用對偶單純形法求解此問題，只經(jīng)過兩次迭代便得到了最優(yōu)解。如果仍采用單純形法求解的話，在化成標(biāo)準(zhǔn)形式后，為得到初始基本解，需要加3個人工變量。這樣，為了得到問題的最優(yōu)解，至少需要3次迭代，才能讓人工變量出基，顯然，計算量大大增加。第27頁，課件共40頁，創(chuàng)作于2023年2月對偶單純形法線性規(guī)劃對偶問題對于有些線性規(guī)劃問題，如果在開始時不能很快讓所有檢驗數(shù)非正，最好還是使用單純形法求解，免去使所有檢驗數(shù)非負(fù)所做的工作。對偶單純形法使用于如下形式的模型在引入松弛變量并華為標(biāo)準(zhǔn)形式后，約束等式兩邊同乘以-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接剪力初始對偶單純形表求解，非常方便。第28頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題在前面的線性規(guī)劃問題中都認(rèn)為線性規(guī)劃模型中的各個系數(shù)是確定的常數(shù)。

但實際中由于種種原因，這些系數(shù)很難確定，一般只是估值。對問題求解后需要最這些估值進(jìn)行一些分析以決定是否需要調(diào)整。另外，周圍環(huán)境的變化也會使系數(shù)發(fā)生變化，影響最優(yōu)解。因此，還需要研究最優(yōu)解對數(shù)據(jù)變化的反應(yīng)程度，以使決策者全面地考慮問題，以適應(yīng)各種偶然變化第29頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題（1）變量變化對最優(yōu)解的影響靈敏度分析研究的內(nèi)容：（2）增加變量或約束對最優(yōu)解的影響靈敏度分析采用的方法：不必重新求解，而是從已經(jīng)得到的最優(yōu)解出發(fā)，通過對變化數(shù)據(jù)進(jìn)行一些簡單的計算，便可迅速得到所需要的結(jié)果，以及變化后的最優(yōu)解。靈敏度分析的步驟：（教材P67）第30頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題由前面的講述我們知道，對于線性規(guī)劃模型

s.t.有代入如果基本解的矩陣表示

時的基解第31頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題

檢驗數(shù)的向量表示

由前知檢驗數(shù)可以用如下的形式表示出來：其中B為可行基，分別為基變量和非基變量的目標(biāo)函數(shù)系數(shù)向量和

展開第32頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題

檢驗數(shù)的向量表示

因此得到檢驗數(shù)的向量表示為若令檢驗數(shù)的另一表達(dá)方式第33頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題

目標(biāo)函數(shù)系數(shù)（cj）的變化

假設(shè)只有一個cj發(fā)生變化，分兩種情況：研究最優(yōu)解受數(shù)據(jù)變化的影響情況主要考慮兩個方面:一是解的最優(yōu)性，即檢驗數(shù)是否仍然非正;一是解的可行性，即基本解的各個分量是否非負(fù)。下面的討論將圍繞這兩個方面展開。（1）ck是非基變量只需考慮其對應(yīng)的的變化是否會引起最優(yōu)解的改變只要滿足則最優(yōu)解不變；否則，最優(yōu)解將發(fā)生變化，需繼續(xù)迭代求出最優(yōu)解。第34頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題

目標(biāo)函數(shù)系數(shù)（cj）的變化

（1）ck是非基變量（2）ck是基變量當(dāng)基變量的系數(shù)發(fā)生變化時，檢驗數(shù)計算式的第二項發(fā)生了變化，從而所有的檢驗數(shù)將發(fā)生變化。對某一非基變量對應(yīng)的已有的檢驗數(shù)，有原對應(yīng)列第35頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題

目標(biāo)函數(shù)系數(shù)（cj）的變化

（1）ck是非基變量（2）ck是基變量滿足所有的可保證最優(yōu)解不變，否則需要重新迭代尋求最優(yōu)解。（例子：教材P67-68）第36頁，課件共40頁，創(chuàng)作于2023年2月靈敏度分析線性規(guī)劃對偶問題

目標(biāo)函數(shù)系數(shù)（cj）的變化

右端常數(shù)（bi）的變化

bi的變化不會引起檢驗數(shù)的變化，但將影響解的可行性若則最優(yōu)基保持不變，只需將變化后的b1代入計算即可得到最優(yōu)解；若出現(xiàn)負(fù)值則最優(yōu)解將發(fā)生變化，需要繼續(xù)迭代。（例子：教材P69）增加新的變量

對某一新增變量對應(yīng)的約束系數(shù)列，由 有如果滿足所有的則最優(yōu)解不變增加一個約束條件

看教材其實，還有約束系數(shù)變動的情形第37頁，課件共40頁，創(chuàng)作于2023年2月本章小結(jié)線性規(guī)劃對偶問題

線性規(guī)劃問題的特性就是對于任何一個求極大值的線性規(guī)劃問題都有一個與之對應(yīng)的求最小值的線性規(guī)劃問題，這兩個問題互為對偶，存在密切關(guān)系。線性規(guī)劃的對偶性在經(jīng)濟(jì)學(xué)的角度看可以認(rèn)為是一個問題的兩個方面，即優(yōu)化生產(chǎn)組織和提高資源利用率。本章首先引人了線性規(guī)劃的對偶問題，分析了線性規(guī)劃問題及對偶問題的特征及在形式上相互轉(zhuǎn)換的規(guī)則，并