運(yùn)籌學(xué)課件-對(duì)偶問(wèn)題

Chapter2對(duì)偶問(wèn)題DualProblem1.線(xiàn)性規(guī)劃的對(duì)偶模型

DualModelofLP2.對(duì)偶性質(zhì)

Dualproperty3.對(duì)偶單純形法

DualSimplexMethod4.靈敏度分析

SensitivityAnalysis運(yùn)籌學(xué)OperationsResearch

在線(xiàn)性規(guī)劃問(wèn)題中，存在一個(gè)有趣的問(wèn)題，即每一個(gè)線(xiàn)性規(guī)劃問(wèn)題都伴隨有另一個(gè)線(xiàn)性規(guī)劃問(wèn)題，稱(chēng)它為對(duì)偶線(xiàn)性規(guī)劃問(wèn)題。對(duì)偶問(wèn)題是對(duì)原問(wèn)題從另一角度進(jìn)行的描述，其最優(yōu)解與原問(wèn)題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線(xiàn)性規(guī)劃問(wèn)題最優(yōu)解的同時(shí)也就得到其對(duì)偶線(xiàn)性規(guī)劃的最優(yōu)解，反之也然。對(duì)偶理論就是研究線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題的理論，是線(xiàn)性規(guī)劃理論的重要內(nèi)容之一。2.1對(duì)偶理論

例2.1:某工廠(chǎng)擁有A、B、C三種類(lèi)型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示。求獲最大利潤(rùn)的方案。2.1.1對(duì)偶線(xiàn)性規(guī)劃問(wèn)題的提出

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）15002500

解】設(shè)x1，x2分別為產(chǎn)品甲，乙的產(chǎn)量，則線(xiàn)性規(guī)劃數(shù)學(xué)模型為：

現(xiàn)在從另一個(gè)角度來(lái)考慮企業(yè)的決策問(wèn)題。假如企業(yè)自己不生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源轉(zhuǎn)讓或出租給其它企業(yè)，那么資源的轉(zhuǎn)讓價(jià)格是多少才合理？?jī)r(jià)格太高對(duì)方不愿意接受，價(jià)格太低本單位收益又太少。合理的價(jià)格應(yīng)是對(duì)方用最少的資金購(gòu)買(mǎi)本企業(yè)的全部資源，而本企業(yè)所獲得的利潤(rùn)不應(yīng)低于自己用于生產(chǎn)時(shí)所獲得的利潤(rùn)。這一決策問(wèn)題應(yīng)考慮這樣幾個(gè)方面。（1）出賣(mài)資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利。即出賣(mài)能夠制造一件產(chǎn)品的設(shè)備所獲得的收入應(yīng)該不少于生產(chǎn)一件該產(chǎn)品所獲得的收入。

（2）價(jià)格應(yīng)盡量低，這樣才能有競(jìng)爭(zhēng)力。（如果客戶(hù)肯以更高的價(jià)格購(gòu)買(mǎi)，則企業(yè)獲得的利潤(rùn)更多，因此這樣制定出的價(jià)格可以作為談判中的低價(jià)，但不一定是實(shí)際成交的價(jià)格。）

（3）價(jià)格應(yīng)該是非負(fù)的。

若以分別表示三種設(shè)備的出售價(jià)格，則第一條要求可以表示為:3y1+2y2≥1500生產(chǎn)一件產(chǎn)品甲的設(shè)備的銷(xiāo)售收入應(yīng)該不少于不少于甲產(chǎn)品的利潤(rùn).

2y1+y2+3y3≥2500生產(chǎn)一件產(chǎn)品甲的設(shè)備的銷(xiāo)售收入應(yīng)該不少于不少于甲產(chǎn)品的利潤(rùn).出售所有設(shè)備所獲得的總收入為:65y1+40y2+75y3

Maxz=1500x1+2500x2

s.t.3x1+2x2≤65

2x1+x2≤40原問(wèn)題

3x2≤75

x1,x2≥0

由此有:

Minf=65y1+40y2+75y3

s.t.3y1+2y2≥1500

（不少于甲產(chǎn)品的利潤(rùn)）

2y1+y2+3y3≥2500對(duì)偶問(wèn)題

（不少于乙產(chǎn)品的利潤(rùn)）

y1,y2,y3≥0

上述兩個(gè)線(xiàn)性規(guī)劃模型是在同一企業(yè)的資源狀況和生產(chǎn)技術(shù)條件下產(chǎn)生的，是同一問(wèn)題從不同角度來(lái)觀(guān)察所產(chǎn)生的。我們稱(chēng)這兩個(gè)線(xiàn)性規(guī)劃問(wèn)題為互為對(duì)偶的兩個(gè)線(xiàn)性規(guī)劃問(wèn)題。其中一個(gè)問(wèn)題是另一個(gè)問(wèn)題的對(duì)偶問(wèn)題。2.1.2對(duì)偶問(wèn)題的定義對(duì)于線(xiàn)性規(guī)劃問(wèn)題：(1)我們稱(chēng)(2)是（1）的對(duì)偶問(wèn)題，也稱(chēng)（1）是（2）的對(duì)偶問(wèn)題。這種對(duì)偶關(guān)系稱(chēng)為對(duì)稱(chēng)形式的對(duì)偶關(guān)系，用矩陣可以表示為：對(duì)稱(chēng)形式的對(duì)偶問(wèn)題的特點(diǎn)為:(1)若原問(wèn)題目標(biāo)是求極大化,則對(duì)偶問(wèn)題的目標(biāo)是極小化,反之也然.原問(wèn)題的目標(biāo)函數(shù)系數(shù)成為對(duì)偶問(wèn)題的右端常數(shù),其右端常數(shù)成為對(duì)偶問(wèn)題的目標(biāo)函數(shù)系數(shù).(2)原問(wèn)題的約束系數(shù)矩陣與對(duì)偶問(wèn)題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣。

（3）極大化問(wèn)題的每個(gè)約束對(duì)應(yīng)于極小化問(wèn)題的一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)約束。極大化問(wèn)題的每個(gè)約束為的形式，對(duì)應(yīng)于極小化問(wèn)題的變量。極大化問(wèn)題的變量，對(duì)應(yīng)于極小化問(wèn)題的約束為的形式?！纠?.2】寫(xiě)出下列線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題【解】這是一個(gè)對(duì)稱(chēng)形式的線(xiàn)性規(guī)劃，它的對(duì)偶問(wèn)題求最小值，有三個(gè)變量且非負(fù)，有兩個(gè)“≥”約束，即【例2.3】寫(xiě)出下列線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題【解】這是一個(gè)對(duì)稱(chēng)形式的線(xiàn)性規(guī)劃，設(shè)Y=（y1，y2），則有從而對(duì)偶問(wèn)題為對(duì)偶變量yi也可寫(xiě)成xi的形式。

對(duì)于一般的線(xiàn)性規(guī)劃問(wèn)題，也可以定義其對(duì)偶線(xiàn)性規(guī)劃問(wèn)題。具體的定義方法如下：

稱(chēng)（22）是（21）的對(duì)偶問(wèn)題，也稱(chēng)（21）是（22）的對(duì)偶問(wèn)題。將上述原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系列于表2－1

原問(wèn)題（或?qū)ε紗?wèn)題）

對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)（maxZ）目標(biāo)函數(shù)系數(shù)（資源限量）約束條件系數(shù)矩陣A（AT）目標(biāo)函數(shù)（minW）資源限量（目標(biāo)函數(shù)系數(shù)）約束條件系數(shù)矩陣ATA）變

量n個(gè)變量第j個(gè)變量≥0第j

個(gè)變量≤0第j個(gè)變量無(wú)約束約

束n個(gè)約束第j個(gè)約束為≥第j

個(gè)約束為≤第j個(gè)約束為=約

束m個(gè)約束第i個(gè)約束≤第i個(gè)約束≥第i個(gè)約束為=變

量m個(gè)變量第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量無(wú)約束

表2－1例如，原問(wèn)題是求最小值，按表2-1有下列關(guān)系：

1.第i個(gè)約束是“≤”約束時(shí)，第i個(gè)對(duì)偶變量yj≤02．第i個(gè)約束是“=”約束時(shí)，第i個(gè)對(duì)偶變量yi無(wú)約束；3．當(dāng)xj≤0時(shí)，第j個(gè)對(duì)偶約束為“≥”約束，當(dāng)xj無(wú)約束時(shí)，第j個(gè)對(duì)偶約束為“=”約束。

其中若原問(wèn)題是極大化問(wèn)題，則按表格從左往右查，若原問(wèn)題是極小化問(wèn)題，則按表格從右往左查。【例2.4】寫(xiě)出此線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題

【解】目標(biāo)函數(shù)求最小值，應(yīng)將表2－1