線性規(guī)劃的對(duì)偶理論演示文稿2023/6/151當(dāng)前第1頁\共有55頁\編于星期二\13點(diǎn)（優(yōu)選）線性規(guī)劃的對(duì)偶理論2023/6/152當(dāng)前第2頁\共有55頁\編于星期二\13點(diǎn)§1對(duì)偶問題的提出

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

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

2023/6/154當(dāng)前第4頁\共有55頁\編于星期二\13點(diǎn)例甲方生產(chǎn)計(jì)劃問題：

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

例：P55例2，寫出下面規(guī)劃的對(duì)偶規(guī)劃2023/6/1513當(dāng)前第13頁\共有55頁\編于星期二\13點(diǎn)解：將原問題模型變形則對(duì)偶問題是2023/6/1514當(dāng)前第14頁\共有55頁\編于星期二\13點(diǎn)小結(jié)：對(duì)偶問題與原問題的關(guān)系：原問題對(duì)偶問題目標(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/1515當(dāng)前第15頁\共有55頁\編于星期二\13點(diǎn)§3

對(duì)偶問題的基本性質(zhì)就上節(jié)所討論的一般的線性規(guī)劃問題及其對(duì)偶問題，有如下的性質(zhì)：1、弱對(duì)偶性 如果分別是原問題和對(duì)偶問題的可行解，則恒有考慮利用及代入。2、無界性 如果原問題（對(duì)偶問題）有無界解，則其對(duì)偶問題（原問題）無可行解。2023/6/1516當(dāng)前第16頁\共有55頁\編于星期二\13點(diǎn)3、最優(yōu)性 如果分別是原問題和對(duì)偶問題的可行解，且有則分別是原問題和對(duì)偶問題的最優(yōu)解。證明 設(shè)分別是原問題和對(duì)偶問題的最優(yōu)解，則由弱對(duì)偶性，又，所以2023/6/1517當(dāng)前第17頁\共有55頁\編于星期二\13點(diǎn)4、強(qiáng)對(duì)偶性 如果原問題有最優(yōu)解，則其對(duì)偶問題也必有最優(yōu)解，且兩者最優(yōu)目標(biāo)函數(shù)值相等，即。證明 設(shè)有線性規(guī)劃問題經(jīng)單純形法計(jì)算后，令，最終表中所以,即：由此可知是對(duì)偶問題的可行解，又，就是最優(yōu)解。基可行解基變量非基變量2023/6/1518當(dāng)前第18頁\共有55頁\編于星期二\13點(diǎn)5、互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)偶變量一定為零。即若若證明 由弱對(duì)偶性知：又因在最優(yōu)解中，于是上式應(yīng)為等式，即有2023/6/1519當(dāng)前第19頁\共有55頁\編于星期二\13點(diǎn)而，故要使得上式成立，必有即后半部分是前一命體的逆否命題，自然成立。互補(bǔ)松弛性還可寫為對(duì)偶問題的相應(yīng)的互補(bǔ)松弛性見書P58。例書P76，習(xí)題2-42023/6/1520當(dāng)前第20頁\共有55頁\編于星期二\13點(diǎn)6、設(shè)原問題是：對(duì)偶問題是：則原問題的檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶問題的一個(gè)基解（不一定是可行解），對(duì)應(yīng)關(guān)系如下表

。初始解非基變量基變量0原問題與對(duì)偶問題存在一對(duì)互補(bǔ)基解，原問題的松弛變量與對(duì)偶問題的變量對(duì)應(yīng)；原問題的變量與對(duì)偶問題的剩余變量對(duì)應(yīng)。互補(bǔ)的基解對(duì)應(yīng)的目標(biāo)函數(shù)值相等。2023/6/1521當(dāng)前第21頁\共有55頁\編于星期二\13點(diǎn)例書P59例32300023101/20-1/50400-214/53501001/500-10-1/52023/6/1522當(dāng)前第22頁\共有55頁\編于星期二\13點(diǎn)基1120-1/201/50-4/511/5-1/5040332023/6/1523當(dāng)前第23頁\共有55頁\編于星期二\13點(diǎn)1、對(duì)偶變量可理解為對(duì)一個(gè)單位第種資源的估價(jià)，稱為影子價(jià)格，但并非市場(chǎng)價(jià)格。2、對(duì)偶變量的值（即影子價(jià)格）表示第種資源數(shù)量變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量。因?yàn)椤?

影子價(jià)格假設(shè)有原問題和對(duì)偶問題如下：2023/6/1524當(dāng)前第24頁\共有55頁\編于星期二\13點(diǎn)資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化目標(biāo)函數(shù)等值線2023/6/1525當(dāng)前第25頁\共有55頁\編于星期二\13點(diǎn)3、影子價(jià)格可用于指導(dǎo)資源的購入與賣出。當(dāng)影子價(jià)格

>

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

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

對(duì)偶單純形法在單純形表中，列對(duì)應(yīng)原問題的基可行解，行對(duì)應(yīng)對(duì)偶問題的一個(gè)基解（不一定可行），當(dāng)時(shí)，在檢驗(yàn)數(shù)行就得到對(duì)偶問題的基可行解，此時(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/1527當(dāng)前第27頁\共有55頁\編于星期二\13點(diǎn)對(duì)偶單純形法：找一個(gè)對(duì)偶問題的基可行解（保持行非正），原問題的解為基解（b列可以為負(fù)），通過迭代，當(dāng)b列全部為正（原問題也達(dá)到了基可行解），即找到最優(yōu)解。3、檢查是否達(dá)最優(yōu)：b列非負(fù)時(shí)達(dá)最優(yōu)，否則繼續(xù)1、2。對(duì)偶單純形法計(jì)算步驟：1、確定出基變量：選擇b列中負(fù)值最小者對(duì)應(yīng)變量出、基，即對(duì)應(yīng)的為出基變量。2、確定進(jìn)基變量：最小比值規(guī)則，即以對(duì)應(yīng)的為進(jìn)基變量，為主元素進(jìn)行迭代。2023/6/1528當(dāng)前第28頁\共有55頁\編于星期二\13點(diǎn)1、

為何只考慮行中的元素對(duì)應(yīng)的變量進(jìn)基？為使迭代后的基變量取正值。2、為何采用最小比值規(guī)則選擇進(jìn)基變量？為了使得迭代后的多偶問題解仍為可行解（檢驗(yàn)數(shù)行仍為非正）3、原問題無可行解的判別準(zhǔn)則：當(dāng)對(duì)偶問題存在可行解時(shí)，若有某個(gè)，而所有，則原問題無可行解，對(duì)偶問題目標(biāo)值無界。因?yàn)榈趓行的約束方程即為：其中，，因此不可能存在使上式成立。也即原問題無可行解。2023/6/1529當(dāng)前第29頁\共有55頁\編于星期二\13點(diǎn)例、用對(duì)偶單純形法求解下述問題解將問題改寫為目標(biāo)最大化，并化為標(biāo)準(zhǔn)型2023/6/1530當(dāng)前第30頁\共有55頁\編于星期二\13點(diǎn)列單純形表-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/1531當(dāng)前第31頁\共有55頁\編于星期二\13點(diǎn)注意：1、使用對(duì)偶單純形法時(shí)，當(dāng)約束條件是時(shí)，可以不必添加人工變量。

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

2023/6/1532當(dāng)前第32頁\共有55頁\編于星期二\13點(diǎn)§6

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

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

b的變化將只影響原問題的基可行解，即最終表中的b列數(shù)值。例、設(shè)有如下的線性規(guī)劃模型試分析分別在什么范圍變化時(shí)，最優(yōu)基不變？2023/6/1537當(dāng)前第37頁\共有55頁\編于星期二\13點(diǎn)解：將重新計(jì)算后填入問題的最終單純形表：1、當(dāng)變化時(shí)，假設(shè)，則問題的解變?yōu)樘钊胂卤恚?30002101/20-1/5000-214/5301001/500-10-1/52023/6/1538當(dāng)前第38頁\共有55頁\編于星期二\13點(diǎn)要使得最優(yōu)基保持不變，則b列數(shù)值即可，即要求同理可得的變化范圍是：的變化范圍是：2023/6/1539當(dāng)前第39頁\共有55頁\編于星期二\13點(diǎn)三、增加一個(gè)變量的變化分析

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

2023/6/1540當(dāng)前第40頁\共有55頁\編于星期二\13點(diǎn)例、設(shè)有如下的線性規(guī)劃模型現(xiàn)增加變量，其對(duì)應(yīng)系數(shù)列為，價(jià)值系數(shù)，請(qǐng)問最優(yōu)解是否改變？

解：最終表2300023101/20-1/50400-214/53301001/500-10-1/52023/6/1541當(dāng)前第41頁\共有55頁\編于星期二\13點(diǎn)新變量的檢驗(yàn)數(shù)及系數(shù)列分別為：填入表中，易知未達(dá)最優(yōu)，繼續(xù)迭代求解。2023/6/1542當(dāng)前第42頁\共有55頁\編于星期二\13點(diǎn)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/1543當(dāng)前第43頁\共有55頁\編于星期二\13點(diǎn)四、增加一個(gè)約束條件的變化分析

增加一個(gè)約束條件，相當(dāng)于增加一道工序。分析方法:1）先將原最優(yōu)解帶入此新約束，若滿足條件，說明此約束未起作用，原最優(yōu)解不變；2）否則，將新約束加入到最終表中，繼續(xù)分析。例、在上例中添加新約束，分析最優(yōu)解的變化情況。解：因?yàn)閷⒃顑?yōu)解帶入此約束，不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。2023/6/1544當(dāng)前第44頁\共有55頁\編于星期二\13點(diǎn)2300023101/20-1/50400-214/53301001/50143200000-10-1/500001023101/20-1/50400-214/53301001/50-100-3/201/500-10-1/5000106x2023/6/1545當(dāng)前第45頁\共有55頁\編于星期二\13點(diǎn)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/1546當(dāng)前第46頁\共有55頁\編于星期二\13點(diǎn)§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/1547當(dāng)前第47頁\共有55頁\編于星期二\13點(diǎn)例：求解下述參數(shù)線性規(guī)劃問題:解：求得時(shí)最終單純形表并將參數(shù)的變化填入表中：0003101/20-1/50400-214/5301001/50002023/6/1548當(dāng)前第48頁\共有55頁\編于星期二\13點(diǎn)2、是臨界點(diǎn)，當(dāng)時(shí)，所以選擇作為進(jìn)基變量，迭代一步得到：0000620[1]0-2/501640010301001/50001、由表可知，當(dāng)

時(shí)，即最優(yōu)解不變。目標(biāo)函數(shù)值是：2023/6/1549當(dāng)前第49頁\共有55頁\編于星期二\13點(diǎn)3、由上表可知，當(dāng)

時(shí)，即最優(yōu)解不變。目標(biāo)函數(shù)值是4、是臨界點(diǎn)，當(dāng)時(shí)，所以選擇作為進(jìn)基變量，迭代一步得到：0000122210001640010015