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

線性規(guī)劃的對偶理論2023/6/51第一頁，共五十七頁，編輯于2023年，星期一第二章線性規(guī)劃的對偶理論

(DualLinearProgramming,DLP)原問題與對偶問題對偶問題的基本性質(zhì)影子價(jià)格對偶單純形法靈敏度分析參數(shù)線性規(guī)劃2023/6/52第二頁，共五十七頁，編輯于2023年，星期一§1對偶問題的提出

一、線性規(guī)劃單純形法的矩陣描述設(shè)有線性規(guī)劃問題的標(biāo)準(zhǔn)形式將系數(shù)矩陣表示成：初始單純形表初始解非基變量基變量0基可行解基變量非基變量0初等行變換后初始表中是I的位置，經(jīng)變換后成為2023/6/53第三頁，共五十七頁，編輯于2023年，星期一其中記則例：書P36例10，驗(yàn)證上述公式。

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

2023/6/54第四頁，共五十七頁，編輯于2023年，星期一例甲方生產(chǎn)計(jì)劃問題：

Ⅰ

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

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

例：P55例2，寫出下面規(guī)劃的對偶規(guī)劃2023/6/513第十三頁，共五十七頁，編輯于2023年，星期一解：將原問題模型變形則對偶問題是2023/6/514第十四頁，共五十七頁，編輯于2023年，星期一小結(jié)：對偶問題與原問題的關(guān)系：原問題對偶問題目標(biāo)函數(shù)：MAX約束條件：m個(gè)約束變量：n個(gè)變量目標(biāo)函數(shù)：MIN約束條件：n個(gè)約束變量：m個(gè)變量約束條件右端項(xiàng)價(jià)值系數(shù)價(jià)值系數(shù)約束條件右端項(xiàng)2023/6/515第十五頁，共五十七頁，編輯于2023年，星期一§3

對偶問題的基本性質(zhì)就上節(jié)所討論的一般的線性規(guī)劃問題及其對偶問題，有如下的性質(zhì)：1、弱對偶性 如果分別是原問題和對偶問題的可行解，則恒有考慮利用及代入。2、無界性 如果原問題（對偶問題）有無界解，則其對偶問題（原問題）無可行解。2023/6/516第十六頁，共五十七頁，編輯于2023年，星期一3、最優(yōu)性 如果分別是原問題和對偶問題的可行解，且有則分別是原問題和對偶問題的最優(yōu)解。證明 設(shè)分別是原問題和對偶問題的最優(yōu)解，則由弱對偶性，又，所以2023/6/517第十七頁，共五十七頁，編輯于2023年，星期一4、強(qiáng)對偶性

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

。初始解非基變量基變量0原問題與對偶問題存在一對互補(bǔ)基解，原問題的松弛變量與對偶問題的變量對應(yīng)；原問題的變量與對偶問題的剩余變量對應(yīng)?；パa(bǔ)的基解對應(yīng)的目標(biāo)函數(shù)值相等。2023/6/521第二十一頁，共五十七頁，編輯于2023年，星期一例書P59例32300023101/20-1/50400-214/53501001/500-10-1/52023/6/522第二十二頁，共五十七頁，編輯于2023年，星期一基1120-1/201/50-4/511/5-1/5040332023/6/523第二十三頁，共五十七頁，編輯于2023年，星期一1、對偶變量可理解為對一個(gè)單位第種資源的估價(jià)，稱為影子價(jià)格，但并非市場價(jià)格。2、對偶變量的值（即影子價(jià)格）表示第種資源數(shù)量變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量。因?yàn)椤?

影子價(jià)格假設(shè)有原問題和對偶問題如下：2023/6/524第二十四頁，共五十七頁，編輯于2023年，星期一資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化目標(biāo)函數(shù)等值線2023/6/525第二十五頁，共五十七頁，編輯于2023年，星期一3、影子價(jià)格可用于指導(dǎo)資源的購入與賣出。當(dāng)影子價(jià)格

>

市場價(jià)格時(shí)，買入；影子價(jià)格<

市場價(jià)格時(shí)，賣出.4、由互補(bǔ)松弛性可知，即影子價(jià)格為零，經(jīng)濟(jì)解釋：資源未用完，再增加對目標(biāo)函數(shù)也無貢獻(xiàn)。反之，表明該種資源用盡，再購進(jìn)用于擴(kuò)大生產(chǎn)可增加總利潤。2023/6/526第二十六頁，共五十七頁，編輯于2023年，星期一§5

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

列對應(yīng)原問題的基可行解，行對應(yīng)對偶問題的一個(gè)基解（不一定可行），當(dāng)時(shí)，在檢驗(yàn)數(shù)行就得到對偶問題的基可行解，此時(shí)兩個(gè)問題的目標(biāo)函數(shù)值相等，由最優(yōu)性條件知，兩個(gè)問題都達(dá)到了最優(yōu)解。單純形法：找一個(gè)初始基可行解，保持b列為正，通過迭代找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng)檢驗(yàn)數(shù)行全部小于等于零時(shí)，達(dá)到最優(yōu)解。2023/6/527第二十七頁，共五十七頁，編輯于2023年，星期一對偶單純形法：找一個(gè)對偶問題的基可行解（保持行非正），原問題的解為基解（b列可以為負(fù)），通過迭代，當(dāng)b列全部為正（原問題也達(dá)到了基可行解），即找到最優(yōu)解。3、檢查是否達(dá)最優(yōu)：b列非負(fù)時(shí)達(dá)最優(yōu)，否則繼續(xù)1、2。對偶單純形法計(jì)算步驟：1、確定出基變量：選擇b列中負(fù)值最小者對應(yīng)變量出、基，即對應(yīng)的為出基變量。2、確定進(jìn)基變量：最小比值規(guī)則，即以對應(yīng)的為進(jìn)基變量，為主元素進(jìn)行迭代。2023/6/528第二十八頁，共五十七頁，編輯于2023年，星期一1、

為何只考慮行中的元素對應(yīng)的變量進(jìn)基？為使迭代后的基變量取正值。2、為何采用最小比值規(guī)則選擇進(jìn)基變量？為了使得迭代后的多偶問題解仍為可行解（檢驗(yàn)數(shù)行仍為非正）3、原問題無可行解的判別準(zhǔn)則：當(dāng)對偶問題存在可行解時(shí)，若有某個(gè)，而所有，則原問題無可行解，對偶問題目標(biāo)值無界。因?yàn)榈趓行的約束方程即為：其中，，因此不可能存在使上式成立。也即原問題無可行解。2023/6/529第二十九頁，共五十七頁，編輯于2023年，星期一例、用對偶單純形法求解下述問題解將問題改寫為目標(biāo)最大化，并化為標(biāo)準(zhǔn)型2023/6/530第三十頁，共五十七頁，編輯于2023年，星期一列單純形表

-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達(dá)到最優(yōu)

2023/6/531第三十一頁，共五十七頁，編輯于2023年，星期一注意：1、使用對偶單純形法時(shí)，當(dāng)約束條件是時(shí)，可以不必添加人工變量。

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

2023/6/532第三十二頁，共五十七頁，編輯于2023年，星期一§6

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

C的變化只影響檢驗(yàn)數(shù)。例、設(shè)有如下的線性規(guī)劃模型試分析分別在什么范圍變化時(shí)，最優(yōu)解不變？2023/6/534第三十四頁，共五十七頁，編輯于2023年，星期一2300023101/20-1/50400-214/53301001/500-10-1/5解：問題的最終單純形表如下：30003101/20-1/50400-214/53301001/50002023/6/535第三十五頁，共五十七頁，編輯于2023年，星期一1、當(dāng)變化時(shí)，假設(shè)，則要使得問題的最優(yōu)解保持不變，則檢驗(yàn)數(shù)行即可，即要求2、當(dāng)變化時(shí)，假設(shè)，則要使得問題的最優(yōu)解保持不變，則檢驗(yàn)數(shù)行即可，即要求2023/6/536第三十六頁，共五十七頁，編輯于2023年，星期一二、b的變化分析

b的變化將只影響原問題的基可行解，即最終表中的b列數(shù)值。例、設(shè)有如下的線性規(guī)劃模型試分析分別在什么范圍變化時(shí)，最優(yōu)基不變？2023/6/537第三十七頁，共五十七頁，編輯于2023年，星期一解：將重新計(jì)算后填入問題的最終單純形表：1、當(dāng)變化時(shí)，假設(shè)，則問題的解變?yōu)樘钊胂卤?，?30002101/20-1/5000-214/5301001/500-10-1/52023/6/538第三十八頁，共五十七頁，編輯于2023年，星期一要使得最優(yōu)基保持不變，則b列數(shù)值

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

的變化范圍是：2023/6/539第三十九頁，共五十七頁，編輯于2023年，星期一三、增加一個(gè)變量的變化分析

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

2023/6/540第四十頁，共五十七頁，編輯于2023年，星期一例、設(shè)有如下的線性規(guī)劃模型現(xiàn)增加變量，其對應(yīng)系數(shù)列為，價(jià)值系數(shù)，請問最優(yōu)解是否改變？

解：最終表2300023101/20-1/50400-214/53301001/500-10-1/52023/6/541第四十一頁，共五十七頁，編輯于2023年，星期一新變量的檢驗(yàn)數(shù)及系數(shù)列分別為：填入表中，易知未達(dá)最優(yōu)，繼續(xù)迭代求解。2023/6/542第四十二頁，共五十七頁，編輯于2023年，星期一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已達(dá)最優(yōu)。最優(yōu)解為

最優(yōu)目標(biāo)值2023/6/543第四十三頁，共五十七頁，編輯于2023年，星期一四、增加一個(gè)約束條件的變化分析

增加一個(gè)約束條件，相當(dāng)于增加一道工序。分析方法:1）先將原最優(yōu)解帶入此新約束，若滿足條件，說明此約束未起作用，原最優(yōu)解不變；2）否則，將新約束加入到最終表中，繼續(xù)分析。例、在上例中添加新約束，分析最優(yōu)解的變化情況。解：因?yàn)閷⒃顑?yōu)解帶入此約束，不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。2023/6/544第四十四頁，共五十七頁，編輯于2023年，星期一2300023101/20-1/50400-214/53301001/50143200000-10-1/500001023101/20-1/50400-214/53301001/50-100-3/201/500-10-1/5000106x2023/6/545第四十五頁，共五十七頁，編輯于2023年，星期一28/31000-1/10016/300018/153301001/502/30010-2/150000-2/51/3-4/30-2/3-2/3已達(dá)最優(yōu)。最優(yōu)解為

最優(yōu)目標(biāo)值2023/6/546第四十六頁，共五十七頁，編輯于2023年，星期一§7參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃：研究參數(shù)連續(xù)變化時(shí)最優(yōu)解的變化以及目標(biāo)函數(shù)值隨參數(shù)變化的情況。注：當(dāng)多個(gè)參數(shù)同時(shí)變化時(shí)，可以引入一個(gè)參數(shù)來表示這種變化。如：b列多個(gè)值發(fā)生變化時(shí)，可表示成求解參數(shù)線性規(guī)劃的步驟：1、令求解得最終單純形表；2、將參數(shù)的變化反映到最終單純形表中；3、找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界點(diǎn)處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分析目標(biāo)函數(shù)值隨參數(shù)變化的情況。2023/6/547第四十七頁，共五十七頁，編輯于2023年，星期一例：求解下述參數(shù)線性規(guī)劃問題:解：求得時(shí)最終單純形表并將參數(shù)的變化填入表中：0003101/20-1/50400-214/5301001/50002023/6/548第四十八頁，共五十七頁，編輯于2023年，星期一2、是臨界點(diǎn)，當(dāng)時(shí)，所以選擇作為進(jìn)基變量，迭代一步得到：0000620[1]0-2/501640010301001/50001、由表可知，當(dāng)

時(shí)，即最優(yōu)解不變。目標(biāo)函數(shù)值是：2023/6/549第四十九頁，共五十七頁，編輯于2023年，星期一3、由上表可知，當(dāng)

時(shí)，即最優(yōu)解不變。目標(biāo)函數(shù)值是4、是臨界點(diǎn)，當(dāng)時(shí)，所以選擇作為進(jìn)基變量，迭代一步得到：00001222100016400100150500[1]0002023/6/550第五十頁，共五十七頁，編輯于2023年，星期一5、由上表可知，當(dāng)時(shí)，最優(yōu)解不再變化。目標(biāo)函數(shù)值是6、是臨界點(diǎn)，當(dāng)時(shí)，所以選擇作為進(jìn)基變量，迭代一步得到：00041001/400500-5/25/412011/2-1/40000此時(shí)無論如何增加，檢驗(yàn)數(shù)始終為負(fù)，最優(yōu)解不再變化。目標(biāo)函數(shù)值是2023/6/551第五十一頁，共五十七頁，編輯于2023年，星期一1524341-12-2-3342023/6/552第五十二頁，共五十七頁，編輯于2023年，星期一例：某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習(xí)本三種產(chǎn)