線性規(guī)劃的對(duì)偶問(wèn)題.pptx

《線性規(guī)劃的對(duì)偶問(wèn)題.pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、1第三章線性規(guī)劃的對(duì)偶問(wèn)題對(duì)偶線性規(guī)劃對(duì)偶定理對(duì)偶單純形法第一節(jié)對(duì)偶問(wèn)題對(duì)偶問(wèn)題概念：任何一個(gè)線性規(guī)劃問(wèn)題都有一個(gè)與之相對(duì)應(yīng)的線性規(guī)劃問(wèn)題，如果前者稱為原始問(wèn)題，后者就稱為“對(duì)偶”問(wèn)題。對(duì)偶問(wèn)題是對(duì)原問(wèn)題從另一角度進(jìn)行的描述其最優(yōu)解與原問(wèn)題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶線性規(guī)劃的最優(yōu)解，反之亦然。對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問(wèn)題的理論，是線性規(guī)劃理論的重要內(nèi)容之一。3對(duì)偶問(wèn)題的提出例1、某工廠生產(chǎn)甲,乙兩種產(chǎn)品，這兩種產(chǎn)品需要在A,B,C三種不同設(shè)備上加工。每種甲、乙產(chǎn)品在不同設(shè)備上加工所需的臺(tái)時(shí)，它們銷售后所能獲得的利潤(rùn)，以及這三種設(shè)

2、備在計(jì)劃期內(nèi)能提供的有限臺(tái)時(shí)數(shù)均列于表。試問(wèn)如何安排生產(chǎn)計(jì)劃，即甲,乙兩種產(chǎn)品各生產(chǎn)多少噸，可使該廠所獲得利潤(rùn)達(dá)到最大。對(duì)偶線性規(guī)劃設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤(rùn)（元/噸）32304假設(shè)計(jì)劃期內(nèi)甲乙兩種產(chǎn)品各生產(chǎn)噸，設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤(rùn)（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計(jì)劃期內(nèi)甲產(chǎn)品生產(chǎn)噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤(rùn)達(dá)到最大，為元。5現(xiàn)在從另一個(gè)角度來(lái)考慮該工廠的生產(chǎn)問(wèn)題:假設(shè)該廠的決策者打算不再自己生產(chǎn)甲,乙產(chǎn)品，而是把各種設(shè)備的有限臺(tái)時(shí)數(shù)租讓給其他工廠使用，

3、這時(shí)工廠的決策者應(yīng)該如何確定各種設(shè)備的租價(jià)。設(shè)分別為設(shè)備A，B，C每臺(tái)時(shí)的租價(jià)，約束條件：把設(shè)備租出去所獲得的租金不應(yīng)低于利用這些設(shè)備自行生產(chǎn)所獲得的利潤(rùn)目標(biāo)函數(shù)：所獲租金總額盡量少．（價(jià)格應(yīng)該盡量低，這樣，才能有競(jìng)爭(zhēng)力）價(jià)格應(yīng)該是非負(fù)的6由此可得兩個(gè)對(duì)稱的線性規(guī)劃：設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤(rùn)（元/噸）32307矩陣形式：8可以得到另一個(gè)線性規(guī)劃：稱之為原線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，對(duì)偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問(wèn)題9101112若令線性規(guī)劃標(biāo)準(zhǔn)型的對(duì)偶規(guī)劃為：線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)型的對(duì)偶問(wèn)題考慮一個(gè)標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題由于

4、任何一個(gè)等式約束都可以用兩個(gè)不等式約束等價(jià)地表示，所以標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題可等價(jià)表示為：它的對(duì)偶規(guī)劃為：對(duì)偶問(wèn)題的特點(diǎn)（1）目標(biāo)函數(shù)在一個(gè)問(wèn)題中是求最大值在另一問(wèn)題中則為求最小值（2）一個(gè)問(wèn)題中目標(biāo)函數(shù)的系數(shù)是另一個(gè)問(wèn)題中約束條件的右端項(xiàng)（3）一個(gè)問(wèn)題中的約束條件個(gè)數(shù)等于另一個(gè)問(wèn)題中的變量數(shù)（4）原問(wèn)題的約束系數(shù)矩陣與對(duì)偶問(wèn)題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣minf=CTXs.t.AX≤bX≥0maxz=bTYs.t.ATY≤CY≤0其他形式問(wèn)題的對(duì)偶minf=CTXs.t.AX≥bX≥0maxz=bTYs.t.ATY≤CY≥0minf=CTXs.t.AX=bX≥0maxz=bTYs

5、.t.ATY≤CY：unr15對(duì)偶線性規(guī)劃的求法從任何一個(gè)線性規(guī)劃出發(fā)，都可以求出相應(yīng)的對(duì)偶規(guī)劃，在實(shí)際求解過(guò)程中，通常不通過(guò)求標(biāo)準(zhǔn)型，而是利用如下反映原始問(wèn)題與對(duì)偶問(wèn)題對(duì)應(yīng)關(guān)系的原始─對(duì)偶表：目標(biāo)函數(shù)變量系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)變量系數(shù)約束條件個(gè)數(shù)：n個(gè)變量個(gè)數(shù)：n個(gè)變量個(gè)數(shù)：m個(gè)約束條件個(gè)數(shù)：m個(gè)目標(biāo)函數(shù)minW目標(biāo)函數(shù)maxZ對(duì)偶問(wèn)題（或原問(wèn)題）原問(wèn)題（或?qū)ε紗?wèn)題）16解：對(duì)偶規(guī)劃：例2寫出下列線性規(guī)劃的對(duì)偶問(wèn)題17例3寫出下列線性規(guī)劃的對(duì)偶問(wèn)題解：上述問(wèn)題的對(duì)偶規(guī)劃：18本節(jié)討論幾條重要的對(duì)偶定理，這些定理揭示了原始問(wèn)題的解和對(duì)偶問(wèn)題的解之間的基本關(guān)系

6、。定理1：（對(duì)稱性）對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。證明：設(shè)原問(wèn)題為　　　　　　　　對(duì)偶問(wèn)題為改寫對(duì)偶問(wèn)題為　　　對(duì)偶問(wèn)題的對(duì)偶為第二節(jié)對(duì)偶定理19定理2：弱對(duì)偶定理若　　是原（極小化）問(wèn)題的可行解，　　是對(duì)偶（極大化）問(wèn)題的可行解，那么證明：因?yàn)椤　∈菍?duì)偶問(wèn)題的可行解，所以滿足約束條件又因?yàn)椤　∈窃瓎?wèn)題的可行解，可得　　　，,所以　　　　　　　　　。注：原（極小化）問(wèn)題的最優(yōu)目標(biāo)函數(shù)值以對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值為下界。對(duì)偶（極大化）問(wèn)題的最優(yōu)目標(biāo)函數(shù)值以原問(wèn)題任一可行解的目標(biāo)函數(shù)值為上界。推論1：如果原問(wèn)題沒(méi)有下界（即minZ→－∞），則對(duì)偶問(wèn)題不可行。如果對(duì)偶問(wèn)題沒(méi)有上界（

7、即maxW→＋∞），則原問(wèn)題不可行。若原問(wèn)題與對(duì)偶問(wèn)題之一無(wú)界，則另一個(gè)無(wú)可行解。20證明：由弱對(duì)偶定理，對(duì)于原始問(wèn)題的所有可行解，都有　　　　　　　因此　是原問(wèn)題的最優(yōu)解。同理，對(duì)于對(duì)偶問(wèn)題的所有可行解，都有所以是對(duì)偶問(wèn)題的最優(yōu)解。推論2：最優(yōu)性定理若　　是原問(wèn)題的可行解，　是對(duì)偶問(wèn)題的可行解，而且兩者的目標(biāo)函數(shù)值相等，即　　　　，則　　和分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。21證明：設(shè)　　是原問(wèn)題(min)的最優(yōu)解，則對(duì)應(yīng)的基Ｂ必有。若定義　　　　，則　　　　，因此　　　　為對(duì)偶問(wèn)題的可行解，而且