運籌學02對偶理論1線性規(guī)劃的對偶模型,對偶性質-全文預覽
【正文】 1)中 σ=(6， － 2， 1， 0， 0)， 則 Y(1)=(0， 0， 6， 2， － 1) 表 2－ 5(2)中 σ=(0， 1， － 5， － 3， 0)， 則 Y(2)=(3， 0， 0， － 1， 5) 表 3－ 5(3)中 σ=(0， 0， － 11， － 2， － 2)， 則 Y（ 3） =(2， 2， 0， 0， 11) 對偶性質 Dual property Chapter3 對偶理論 Dual Theory (3) 因為表 3－ 2(3)為最優(yōu)解 ， 故 Y（ 3） =(2， 2， 0， 0，11)為對偶問題最優(yōu)解； CB=(6， － 2)， 因而 (4) 表 3－ 2(3)中的最優(yōu)基 B1 為表 3－ 2(3)中 x4， x 5兩列的系數 ， 即 2110B???? ?????????????21101B)2,2(2110)2,6(),(121?????????????BCyyYB 對偶性質 Dual property Chapter3 對偶理論 Dual Theory 根據對偶性質；可將原問題與對偶問題解的對應關系列表如下： 表 3－ 6 一個問題 max 另一個問題 min 有最優(yōu)解 有最優(yōu)解 性質 4 無 無最優(yōu)解 無最優(yōu)解 性質 4 最 優(yōu) 無界解 (有可行解 ) 無可行解 性質 2 解 無可行解 無界解 (有可行解 ) 應用 已知最優(yōu)解 通過解方程 求最優(yōu)解 性質 5 已知檢驗數 檢驗數乘以－ 1 求得基本解 性質 6 對偶性質 Dual property Chapter3 對偶理論 Dual Theory 作業(yè)：教材 P80 (1) 線性規(guī)劃的對偶模型 Dual model of LP 1. 如何寫規(guī)范與非規(guī)范問題的對偶問題 。 反之 ， (DP)的檢驗數 (注意：不乘負號 )對應于 (LP)的一組基本解 。 ?????????643131xxxx因為 y2≠0，所以原問題第二個松弛變量 =0，由 y1=0、 y2=2知，松弛變量 故 x2=0，則原問題的約束條件為線性方程組： ,1,0 21 ?? SS yy2Sx 對偶性質 Dual property Chapter3 對偶理論 Dual Theory 【 例 】 證明該線性規(guī)劃無最優(yōu)解： ???????????????3,2,1,0324m i n32131321jxxxxxxxxxZj【 證 】 容易看出 X=(4， 0， 0) 是一可行解 。 【 例 】 已知線性規(guī)劃 ????????????????3,2,1,0162210243m a x321321321jxxxxxxxxxxzj的最優(yōu)解是 , 求對偶問題的最優(yōu)解 。 另一結論 ：若 (LP)與 (DP)都有可行解 ， 則兩者都有最優(yōu)解 ， 若一個問題無最優(yōu)解 ， 則另一問題也無最優(yōu)解 。 注意 : 上述結論 (2)及 (3)的條件不能少 。 (2)規(guī)范形式的線性規(guī)劃問題的對偶仍然是規(guī)范形式． Chapter3 對偶理論 Dual Theory 原問題 (或對偶問題 ) 對偶問題 (或原問題 ) 目標函數 max 目標函數系數 (資源限量 ) 約束條件系數矩陣 A(AT) 目標函數 min 資源限量 (目標函數系數 ) 約束條件系數矩陣 AT(A) 變 量 n個變量 第 j個變量 ≥0 第 j 個變量 ≤0 第 j個變量無約束 約 束 n個約束 第 j個約束為 ≥ 第 j個約束為 ≤ 第 j個約束為 = 約 束 m個約束 第 i個約束 ≤ 第 i個約束 ≥ 第 i個約束為 = 變 量 m個變量 第 i個變量 ≥0 第 i個變量 ≤0 第 i個變量無約束 線性規(guī)劃的對偶模型 Dual model of LP 問題 ：討論一般形式的線性規(guī)劃問題的對偶問題
試題試卷相關推薦
鄂ICP備17016276號-1