線性規(guī)劃的對偶理論

線性規(guī)劃的對偶理論2023/4/161第1頁，共57頁，2023年，2月20日，星期二第二章線性規(guī)劃的對偶理論

(DualLinearProgramming,DLP)原問題與對偶問題對偶問題的基本性質(zhì)影子價格對偶單純形法靈敏度分析參數(shù)線性規(guī)劃2023/4/162第2頁，共57頁，2023年，2月20日，星期二§1對偶問題的提出

一、線性規(guī)劃單純形法的矩陣描述設(shè)有線性規(guī)劃問題的標準形式將系數(shù)矩陣表示成：初始單純形表初始解非基變量基變量0基可行解基變量非基變量0初等行變換后初始表中是I的位置，經(jīng)變換后成為2023/4/163第3頁，共57頁，2023年，2月20日，星期二其中記則例：書P36例10，驗證上述公式。

上述公式對于靈敏度分析很有幫助。

2023/4/164第4頁，共57頁，2023年，2月20日，星期二例甲方生產(chǎn)計劃問題：

Ⅰ

Ⅱ能力設(shè)備A2212設(shè)備B4

016設(shè)備C0515利潤23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤?二、對偶問題的提出設(shè)有原問題乙方租借設(shè)備：甲方以何種價格將設(shè)備A、B、C租借給乙方比較合理？請為其定價。解：假設(shè)A、B、C的單位租金分別為。思路：就甲方而言，租金收入應不低于將設(shè)備用于自己生產(chǎn)時的利潤。2023/4/165第5頁，共57頁，2023年，2月20日，星期二而就乙方而言，希望甲方的租金收入在滿足約束的條件下越小越好，這樣雙方才可能達成協(xié)議。于是得到下述的線性規(guī)劃模型：所以：生產(chǎn)產(chǎn)品Ⅰ的資源用于出租時，租金收入應滿足：類似的，生產(chǎn)產(chǎn)品Ⅱ的資源用于出租時，租金收入應滿足：總的租金收入：2023/4/166第6頁，共57頁，2023年，2月20日，星期二原問題對偶問題用矩陣將上述原問題對偶問題寫出2023/4/167第7頁，共57頁，2023年，2月20日，星期二即：原問題對偶問題2023/4/168第8頁，共57頁，2023年，2月20日，星期二§2原問題與對偶問題對于一般的線性規(guī)劃問題，2023/4/169第9頁，共57頁，2023年，2月20日，星期二類似于前面的資源定價問題，每一個約束條件對應一個“對偶變量”，它就相當于給各資源的單位定價。于是我們有如下的對偶規(guī)劃：2023/4/1610第10頁，共57頁，2023年，2月20日，星期二對偶問題與原問題的關(guān)系：原問題對偶問題目標函數(shù)：MAX約束條件：m個約束變量：n個變量目標函數(shù)：MIN約束條件：n個約束變量：m個變量這是規(guī)范形式的原問題，由此寫出其對偶問題如右方所示，那么，當原問題不是規(guī)范形式時，應如何寫出其對偶問題？可以先將原問題化成規(guī)范的原問題，再寫出對偶問題。2023/4/1611第11頁，共57頁，2023年，2月20日，星期二例寫出下述規(guī)劃的對偶問題于是對偶問題即為：解先將該問題化為規(guī)范形式也即為：于是對偶問題的對偶是原問題。---------對稱性互為對偶2023/4/1612第12頁，共57頁，2023年，2月20日，星期二如何寫出非規(guī)范的原問題相應的對偶問題：目標函數(shù)MINMAX約束條件約束條件=?4.變量?

例：P55例2，寫出下面規(guī)劃的對偶規(guī)劃2023/4/1613第13頁，共57頁，2023年，2月20日，星期二解：將原問題模型變形則對偶問題是2023/4/1614第14頁，共57頁，2023年，2月20日，星期二小結(jié)：對偶問題與原問題的關(guān)系：原問題對偶問題目標函數(shù)：MAX約束條件：m個約束變量：n個變量目標函數(shù)：MIN約束條件：n個約束變量：m個變量約束條件右端項價值系數(shù)價值系數(shù)約束條件右端項2023/4/1615第15頁，共57頁，2023年，2月20日，星期二§3

對偶問題的基本性質(zhì)就上節(jié)所討論的一般的線性規(guī)劃問題及其對偶問題，有如下的性質(zhì)：1、弱對偶性 如果分別是原問題和對偶問題的可行解，則恒有考慮利用及代入。2、無界性 如果原問題（對偶問題）有無界解，則其對偶問題（原問題）無可行解。2023/4/1616第16頁，共57頁，2023年，2月20日，星期二3、最優(yōu)性 如果分別是原問題和對偶問題的可行解，且有則分別是原問題和對偶問題的最優(yōu)解。證明 設(shè)分別是原問題和對偶問題的最優(yōu)解，則由弱對偶性，又，所以2023/4/1617第17頁，共57頁，2023年，2月20日，星期二4、強對偶性

如果原問題有最優(yōu)解，則其對偶問題也必有最優(yōu)解，且兩者最優(yōu)目標函數(shù)值相等，即。證明 設(shè)有線性規(guī)劃問題經(jīng)單純形法計算后，令，最終表中所以,即：由此可知是對偶問題的可行解，又，就是最優(yōu)解。基可行解基變量非基變量2023/4/1618第18頁，共57頁，2023年，2月20日，星期二5、互補松弛性：在線性規(guī)劃的最優(yōu)解中，如果對應某一約束條件的對偶變量值非零，則該約束條件取嚴格等式；反之，如果約束條件取嚴格不等式，則其對偶變量一定為零。即若若證明 由弱對偶性知：又因在最優(yōu)解中，于是上式應為等式，即有2023/4/1619第19頁，共57頁，2023年，2月20日，星期二而，故要使得上式成立，必有即后半部分是前一命體的逆否命題，自然成立。互補松弛性還可寫為對偶問題的相應的互補松弛性見書P58。例書P76，習題2-42023/4/1620第20頁，共57頁，2023年，2月20日，星期二6、設(shè)原問題是：對偶問題是：則原問題的檢驗數(shù)行對應對偶問題的一個基解（不一定是可行解），對應關(guān)系如下表

。初始解非基變量基變量0原問題與對偶問題存在一對互補基解，原問題的松弛變量與對偶問題的變量對應；原問題的變量與對偶問題的剩余變量對應。互補的基解對應的目標函數(shù)值相等。2023/4/1621第21頁，共57頁，2023年，2月20日，星期二例書P59例32300023101/20-1/50400-214/53501001/500-10-1/52023/4/1622第22頁，共57頁，2023年，2月20日，星期二基1120-1/201/50-4/511/5-1/5040332023/4/1623第23頁，共57頁，2023年，2月20日，星期二1、對偶變量可理解為對一個單位第種資源的估價，稱為影子價格，但并非市場價格。2、對偶變量的值（即影子價格）表示第種資源數(shù)量變化一個單位時，目標函數(shù)的增量。因為§4

影子價格假設(shè)有原問題和對偶問題如下：2023/4/1624第24頁，共57頁，2023年，2月20日，星期二資源增加一個單位時，最優(yōu)解及目標函數(shù)值的變化目標函數(shù)等值線2023/4/1625第25頁，共57頁，2023年，2月20日，星期二3、影子價格可用于指導資源的購入與賣出。當影子價格

>

市場價格時，買入；影子價格<

市場價格時，賣出.4、由互補松弛性可知，即影子價格為零，經(jīng)濟解釋：資源未用完，再增加對目標函數(shù)也無貢獻。反之，表明該種資源用盡，再購進用于擴大生產(chǎn)可增加總利潤。2023/4/1626第26頁，共57頁，2023年，2月20日，星期二§5

對偶單純形法在單純形表中，

列對應原問題的基可行解，行對應對偶問題的一個基解（不一定可行），當時，在檢驗數(shù)行就得到對偶問題的基可行解，此時兩個問題的目標函數(shù)值相等，由最優(yōu)性條件知，兩個問題都達到了最優(yōu)解。單純形法：找一個初始基可行解，保持b列為正，通過迭代找到下一個基可行解，使目標函數(shù)值不斷增大，當檢驗數(shù)行全部小于等于零時，達到最優(yōu)解。2023/4/1627第27頁，共57頁，2023年，2月20日，星期二對偶單純形法：找一個對偶問題的基可行解（保持行非正），原問題的解為基解（b列可以為負），通過迭代，當b列全部為正（原問題也達到了基可行解），即找到最優(yōu)解。3、檢查是否達最優(yōu)：b列非負時達最優(yōu)，否則繼續(xù)1、2。對偶單純形法計算步驟：1、確定出基變量：選擇b列中負值最小者對應變量出、基，即對應的為出基變量。2、確定進基變量：最小比值規(guī)則，即以對應的為進基變量，為主元素進行迭代。2023/4/1628第28頁，共57頁，2023年，2月20日，星期二1、

為何只考慮行中的元素對應的變量進基？為使迭代后的基變量取正值。2、為何采用最小比值規(guī)則選擇進基變量？為了使得迭代后的多偶問題解仍為可行解（檢驗數(shù)行仍為非正）3、原問題無可行解的判別準則：當對偶問題存在可行解時，若有某個，而所有，則原問題無可行解，對偶問題目標值無界。因為第r行的約束方程即為：其中，，因此不可能存在使上式成立。也即原問題無可行解。2023/4/1629第29頁，共57頁，2023年，2月20日，星期二例、用對偶單純形法求解下述問題解將問題改寫為目標最大化，并化為標準型2023/4/1630第30頁，共57頁，2023年，2月20日，星期二列單純形表

-12-16-15000-2-2-40100-3-20[-5]01-12-16-15000-2[-2]-4010-153/52/50[1]0-1/5-6-1600-3-121[1]20-1/20-151/50-4/511/5-1/50-40-3-3達到最優(yōu)

2023/4/1631第31頁，共57頁，2023年，2月20日，星期二注意：1、使用對偶單純形法時，當約束條件是時，可以不必添加人工變量。

2、使用對偶單純形法時，初始單純形表中要保證對偶解為可行解常難以做到，所以一般不單獨使用，常與靈敏度分析結(jié)合使用。

2023/4/1632第32頁，共57頁，2023年，2月20日，星期二§6

靈敏度分析靈敏度分析：線性規(guī)劃問題中的某些參數(shù)發(fā)生變化，對解的影響。（C，A，b）靈敏度分析的一般步驟：1、將參數(shù)的改變經(jīng)計算后反映到最終單純形表中；2、檢查原問題和對偶問題是否仍為可行解；3、按照下表對應情況，決定下一步驟。原問題對偶問題結(jié)論或計算步驟可行解可行解仍是最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解非可行解引入人工變量，重新編單純形表，重新計算2023/4/1633第33頁，共57頁，2023年，2月20日，星期二一、C的變化分析

C的變化只影響檢驗數(shù)。例、設(shè)有如下的線性規(guī)劃模型試分析分別在什么范圍變化時，最優(yōu)解不變？2023/4/1634第34頁，共57頁，2023年，2月20日，星期二2300023101/20-1/50400-214/53301001/500-10-1/5解：問題的最終單純形表如下：30003101/20-1/50400-214/53301001/50002023/4/1635第35頁，共57頁，2023年，2月20日，星期二1、當變化時，假設(shè)，則要使得問題的最優(yōu)解保持不變，則檢驗數(shù)行即可，即要求2、當變化時，假設(shè)，則要使得問題的最優(yōu)解保持不變，則檢驗數(shù)行即可，即要求2023/4/1636第36頁，共57頁，2023年，2月20日，星期二二、b的變化分析

b的變化將只影響原問題的基可行解，即最終表中的b列數(shù)值。例、設(shè)有如下的線性規(guī)劃模型試分析分別在什么范圍變化時，最優(yōu)基不變？2023/4/1637第37頁，共57頁，2023年，2月20日，星期二解：將重新計算后填入問題的最終單純形表：1、當變化時，假設(shè)，則問題的解變?yōu)樘钊胂卤?，?30002101/20-1/5000-214/5301001/500-10-1/52023/4/1638第38頁，共57頁，2023年，2月20日，星期二要使得最優(yōu)基保持不變，則b列數(shù)值

即可，即要求同理可得的變化范圍是：

的變化范圍是：2023/4/1639第39頁，共57頁，2023年，2月20日，星期二三、增加一個變量的變化分析

增加一個變量，在方程組（矩陣A）中就要增加一個系數(shù)列，在原來的最終表中也要添加一列，檢驗數(shù)也要計算，其余部分不受影響。如果檢驗數(shù)行仍，則最優(yōu)解不變，否則繼續(xù)迭代尋找最優(yōu)。一般分析步驟：1、計算增加的新變量系數(shù)列在原最終表中的結(jié)果；2、計算新變量對應的檢驗數(shù)；3、根據(jù)的符號判斷是否仍是最優(yōu)解，若是，最優(yōu)解不變；若不是，繼續(xù)求解。

2023/4/1640第40頁，共57頁，2023年，2月20日，星期二例、設(shè)有如下的線性規(guī)劃模型現(xiàn)增加變量，其對應系數(shù)列為，價值系數(shù)，請問最優(yōu)解是否改變？

解：最終表2300023101/20-1/50400-214/53301001/500-10-1/52023/4/1641第41頁，共57頁，2023年，2月20日，星期二新變量的檢驗數(shù)及系數(shù)列分別為：填入表中，易知未達最優(yōu)，繼續(xù)迭代求解。2023/4/1642第42頁，共57頁，2023年，2月20日，星期二2300023101/20-1/50400-214/53301001/500-10-1/523101/20-1/50100-1/21/41/532011/2-1/4000-1/2-1/4-2/5010000411已達最優(yōu)。最優(yōu)解為

最優(yōu)目標值2023/4/1643第43頁，共57頁，2023年，2月20日，星期二四、增加一個約束條件的變化分析

增加一個約束條件，相當于增加一道工序。分析方法:1）先將原最優(yōu)解帶入此新約束，若滿足條件，說明此約束未起作用，原最優(yōu)解不變；2）否則，將新約束加入到最終表中，繼續(xù)分析。例、在上例中添加新約束，分析最優(yōu)解的變化情況。解：因為將原最優(yōu)解帶入此約束，不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。2023/4/1644第44頁，共57頁，2023年，2月20日，星期二2300023101/20-1/50400-214/53301001/50143200000-10-1/500001023101/20-1/50400-214/53301001/50-100-3/201/500-10-1/5000106x2023/4/1645第45頁，共57頁，2023年，2月20日，星期二28/31000-1/10016/300018/153301001/502/30010-2/150000-2/51/3-4/30-2/3-2/3已達最優(yōu)。最優(yōu)解為

最優(yōu)目標值2023/4/1646第46頁，共57頁，2023年，2月20日，星期二§7參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃：研究參數(shù)連續(xù)變化時最優(yōu)解的變化以及目標函數(shù)值隨參數(shù)變化的情況。注：當多個參數(shù)同時變化時，可以引入一個參數(shù)來表示這種變化。如：b列多個值發(fā)生變化時，可表示成求解參數(shù)線性規(guī)劃的步驟：1、令求解得最終單純形表；2、將參數(shù)的變化反映到最終單純形表中；3、找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界點處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分析目標函數(shù)值隨參數(shù)變化的情況。2023/4/1647第47頁，共57頁，2023年，2月20日，星期二例：求解下述參數(shù)線性規(guī)劃問題:解：求得時最終單純形表并將參數(shù)的變化填入表中：0003101/20-1/50400-214/5301001/50002023/4/1648第48頁，共57頁，2023年，2月20日，星期二2、是臨界點，當時，所以選擇作為進基變量，迭代一步得到：0000620[1]0-2/501640010301001/50001、由表可知，當

時，即最優(yōu)解不變。目標函數(shù)值是：2023/4/1649第49頁，共57頁，2023年，2月20日，星期二3、由上表可知，當

時，即最優(yōu)解不變。目標函數(shù)值是4、是臨界點，當時，所以選擇作為進基變量，迭代一步得到：00001222100016400100150500[1]0002023/4/1650第50頁，共57頁，2023年，2月20日，星期二5、由上表可知，當時，最優(yōu)解不再變化。目標函數(shù)值是6、是臨界點，當時，所以選擇作為進基變量，迭代一步得到：00041001/400500-5/25/412011/2-1/40000此時無論如何增加，檢驗數(shù)始終為負，最優(yōu)解不再變化。目標函數(shù)值是2023/4/1651第51頁，共57頁，2023年，2月20日，星期二1524341-12-2-3342023/4/1652第52頁，共57頁，2023年，2月20日，星期二例：某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習本