CAN-File-10-10-08-13-線性規(guī)劃_對偶.ppt

1、,第03章 線性規(guī)劃：對偶Linear Programming: duality,對偶理論 對偶問題 對偶定理 與單純形法的關系 互補松弛KKT條件 基于對偶的方法 對偶單純形法(概念、步驟、收斂性),對偶理論, 食譜問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？,對偶問題：舉例,n種食品，m種營養(yǎng)成份；第 j 種食品的單價,每單位第 j 種食品所含第 i 種營養(yǎng)的數(shù)量,為了健康，每天必須食用第i 種營養(yǎng)的數(shù)量, 模型：,對偶問題：經(jīng)濟解釋, 保健品公司：藥劑師、營養(yǎng)丸、定價問題, 對偶問題,對偶問題：對稱形式的對偶對,注：對偶是相互的，即對偶問題的對偶是原問題, 原始問題(primal)：,給

2、定數(shù)據(jù),原問題的變量,對偶問題：非對稱形式的對偶對,注：為了確定任一線性規(guī)劃問題的對偶，可以利用 對稱形式或非對稱形式的對偶對！, 原始問題(primal)：,給定數(shù)據(jù),原問題的變量,對偶問題：一般問題的對偶,給定數(shù)據(jù)c, A, b；記 A 的第 j 行為 aj，A 的第 i 列為 ai, 原問題(primal)：, 對偶問題(dual)：,對偶問題：例子,對偶定理：弱對偶定理,弱對偶定理. 設 和 分別是原始問題和對偶問題的可行 解，則,推論2. 如果原始問題與對偶問題之一無界，則另一個問題 沒有可行解.,對偶定理：強對偶定理,對于一般形式的線性規(guī)劃利用凸集分離定理證明！,強對偶定理. 如果

3、原始問題和對偶問題之一有解，則另一個問題也有解，且最優(yōu)值相等.,與單純形法的關系：定理,如何由原始問題的解得到對偶問題的解？,與單純形法的關系：例子,考慮問題,引入松弛變量標準形利用單純形法求解,對偶問題,與單純形法的關系：例子(續(xù)),原問題最優(yōu)解,對偶問題 最優(yōu)解,與單純形法的關系：單純形乘子, 與基 B 對應的單純形乘子(simplex multiplier), 經(jīng)濟解釋 記 A 的列向量為 aj，對應費用為 cj，j=1 , , n,解釋為單位向量 ei 的合成價格！,解釋為aj 的相對費用系數(shù), 最優(yōu)性：對所有的 i 有,與單純形法的關系：單純形乘子(續(xù)),靈敏度(sensitivit

4、y，工程上),假設該問題的最優(yōu)基是 B. 則,假設非退化！,問題：當向量 b 變化時，最優(yōu)值如何變化？,與單純形法的關系：單純形乘子(續(xù)),影子價格(shadow price，經(jīng)濟上),稱 為分量 所對應資源的邊際價格(marginal price) 或者影子價格(shadow price),互補松弛 Complementary Slackness,互補松弛定理,定理. 設 和 分別是對稱形式原始問題和對偶問題的可行解. 則它們是各自最優(yōu)解的充要條件是：對所有的 i 和 j 有,對偶單純形法 Dual Simplex Method,對偶單純形法：概述, 適用問題：標準形問題有一個不可行的基本解

5、，但 對應單純形乘子是對偶問題的可行解, 單純形表中的表現(xiàn)：, 第一張單純形表: 相對費用系數(shù)非負，但有基變量取負值！, 轉軸過程中：保持相對費用系數(shù)非負，直到基變量全部 取非負值！,則稱 x 是標準形問題的對偶可行基本解.,定義. 假設是 Ax=b 的基本解. 如果,基本解可行對偶可行最優(yōu)解,對偶單純形法：對偶可行基本解,是對偶問題的可行解，即,目的：找新的 使前m個等式中的某個與后n-m個不等式中的某個角色互換，同時使對偶問題的目標函數(shù)值增大！,對偶單純形法：推導I,對偶單純形法：推導II,令 ，其中 ui 是 B-1 的第 i 行，則,出基變量：取負值的基變量(*),進基變量：取到最小正

6、比值的非基變量(*),步0 給定對偶可行基本解對應的單純形表.,步1 若對每個 i 都有 ，停；當前DFBS是最優(yōu)的.,步2 選取 i 滿足 yi00 ，這時，第 i 個基變量出基.,步4 以 yiq 為轉軸元進行轉軸，更新單純形表，返步1.,對偶單純形法：計算步驟,步3 若 ，停，問題無可行解；否則， 選 q 滿足,引入盈余變量；并給等式兩邊同乘 -1；得初始表格,對偶單純形法：例子,對偶單純形法：例子(續(xù)),最優(yōu)解：,結論：由對偶可行基本解確定的單純形乘子集合與對偶問題可行集的極點是完全相同的。,對偶單純形法：進一步的理解,原 問 題,對偶單純形法：收斂性,定理. 如果標準形線性規(guī)劃問題的

7、任一對偶可行基本解所對應的非基變量的相對費用系數(shù)大于零，則對偶單純形法在有限步內(nèi)終止., 如果線性規(guī)劃問題可以用對偶單純形法求解，則必有界！ 其計算結果只能是不可行或者有解！, 如果線性規(guī)劃問題可以用單純形法求解，則其無界或有解！ 兩階段法可以求解任一線性規(guī)劃問題； 第I階段的結果分有可行解或者無可行解兩種； 對有可行解的，在第II階段可得問題無界或有解！, 典型情況(有顯然的對偶可行基本解), 一般情況, 已有一個標準形問題的最優(yōu)解和最優(yōu)基, 添加一個“不等式約束”后的新問題,對偶單純形法：啟動, “不等式約束”,后的新問題,線性規(guī)劃的應用： 博弈論(Game Theory ),石頭布剪刀(

8、Rock-Paper-Scissors),二人博弈,支付矩陣：行palyer給列player的支付(payoff),注：某個player利用任一確定性(純)策略，均可被另一個player擊敗.,二人零和博弈(Two-Person Zero-sum Games),給定 mn 矩陣 A,注：A的行代表rowboy的確定性策略，而A的列代表colgirl的確定性策略.,行player(rowboy)選擇策略 列player(colgirl)選擇策略 rowboy支付給colgirl aij 美元,確定性策略可能會很差！,隨機化策略(Randomized Strategies),假設 rowboy 選擇策略 i 的概率是 yi 假設colgirl選擇策略 j 的概率是 xj,如果使用隨機(混合)策略 y ，colgirl使用隨機策略 x，則rowboy向colgirl的期望支付是,Colgirl的分析,假設colgirl準備采取策略 x,則rowboy最好的防衛(wèi)是利用 y, 其求解問題,因此colgirl應該選取 x, 其極大化這種可能性,求解Max-Min問題(轉化成線性規(guī)劃問題),內(nèi)層優(yōu)化很容易：,引入標量變量 v 表示內(nèi)層極小化的值：,因此colgirl的問題是,Row