最優(yōu)化理論與方法-對偶原理ppt課件

1、第4章 對偶原理,4.1線性規(guī)劃中的對偶理論 4.2對偶單純形法,原問題與對偶問題,線性規(guī)劃中普遍存在著配對的現(xiàn)象，即對每一個線性規(guī)劃問題，都存在另一個與之密切聯(lián)系的線性規(guī)劃問題，其中之一稱為原問題，而另一個成為它的對偶問題。 對偶問題深刻揭示了每對問題中原問題與對偶問題的內(nèi)在聯(lián)系,例】原問題與對偶問題,某工廠擬生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源。有關(guān)數(shù)據(jù)如表所示,問題一：試擬訂使總收入最大的生產(chǎn)方案。 問題二：若廠家不再打算生產(chǎn)甲、乙產(chǎn)品，而是打算將其資源全部賣掉。廠家要求：其收入不低于生產(chǎn)產(chǎn)品時的收入；買方希望：原料價格越低越好。試擬定能夠保證賣方收入且使買方支出最小的定價方案,

2、問題二：試擬定能夠保證賣方收入且使買方支出最小的定價方案。 解：設(shè)煤、電、油三種資源的定價分別為y1, y2, y3 ，買方總支出為w,例】原問題與對偶問題,問題一：試擬訂使總收入最大的生產(chǎn)方案。 解：設(shè)擬生產(chǎn)甲、乙產(chǎn)品各x1,x2 單位，總收入為z,下面將會看到，這兩個問題互為對偶問題，其中一個稱為原問題，則另一問題就是它的對偶問題,對偶問題的表述對稱形式,原問題 對偶問題,其中 是 矩陣， 是m 維列向量， 是n 維行向量， 是由原問題的變量組成的n 維列向量， 是由對偶問題的變量組成的 m維行向量,對偶問題的表述 非對稱形式,對稱形式 原問題： 對偶問題,非對稱形式,對偶問題的表述（一般

3、形式,原問題,對偶問題,原問題與對偶問題間的相互轉(zhuǎn)換關(guān)系,對偶問題的基本性質(zhì),對偶問題的對偶是原問題,對偶定理（以對稱對偶形式敘述,定理4.1.1】若 和 分別是(4.1.1)和(4.1.2)的可行解，則 。（可得到以下重要推論：） 若 和 分別是(4.1.1)和(4.1.2)的可行解，且 則 和 分別是 (4.1.1)和 (4.1.2)的最優(yōu)解。 對偶規(guī)劃(4.1.1)和(4.1.2)有最優(yōu)解的充要條件是它們同時有可行解。 若原問題(4.1.1)的目標(biāo)函數(shù)值在可行域上無下界，則對偶問題(4.1.2)無可行解；反之，若對偶問題(4.1.2)的目標(biāo)函數(shù)值在可行域上無上界，則原問題(4.1.1)無

4、可行解,4.1.1,4.1.2,對偶定理（以對稱對偶形式敘述,定理4.1.2】設(shè)原問題或?qū)ε紗栴}中有一個問題存在最優(yōu)解，則另一個問題也存在最優(yōu)解，且兩個問題的目標(biāo)函數(shù)值相等。 【推論】若線性規(guī)劃(4.1.1)存在一個對應(yīng)基B的最優(yōu)基本可行解，則單純形乘子 是對偶問題(4.1.2)的一個最優(yōu)解。 根據(jù)這個推論，能夠從原問題的最優(yōu)單純形表中直接獲得對偶問題的一個最優(yōu)解,對偶問題的基本性質(zhì),互補(bǔ)松弛性質(zhì)（見教材） 對于對偶規(guī)劃，當(dāng)知道一個問題的最優(yōu)解時，根據(jù)互補(bǔ)松弛定理求出另一個問題的最優(yōu)解,對偶可行的基本解,考慮線性規(guī)劃問題 (4.2.1) 定義:設(shè) x(0) 是(4.2.1)式的一個基本解，它對

5、應(yīng)的基矩陣為B，記w = cBB-1，若 w 是 (4.2.1)式的對偶問題的可行解，即對所有j，成立 ，則稱 x(0) 為原問題的對偶可行的基本解,稱為方程組的一個基本解,對偶單純形法的基本思想,從原問題的一個對偶可行的基本解出發(fā)，求改進(jìn)的對偶可行的基本解，當(dāng)?shù)玫降膶ε伎尚械幕窘馐窃瓎栴}的可行解時，就達(dá)到最優(yōu)解。 這里改進(jìn)的對偶可行的基本解的含義是： 根據(jù)定義，對每個對偶可行的基本解 都對應(yīng)一個對偶問題的可行解w = cBB-1 ，相應(yīng)的對偶問題的目標(biāo)函數(shù)值為wb= cBB-1b 。所謂改進(jìn)的對偶可行的基本解，是指對于原問題的這個基本解，相應(yīng)的對偶問題的目標(biāo)函數(shù)值wb有改進(jìn),對偶單純形法的基本思想,求改進(jìn)的對偶可行的基本解的過程，也就是選擇離基變量和進(jìn)基變量，進(jìn)行主元消去的過程。這與單純形方法有類似之處。 與前面介紹的單純形法的區(qū)別在于：在單純形法的迭代過程中，始終保持右端列(目標(biāo)函數(shù)值除外)非負(fù)，即保持原問題