原問(wèn)題與對(duì)偶問(wèn)題ppt課件(編輯修改稿)
2025-06-02 18:02 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 102/152/14/14/1014/54/1xxxxxyyyyyyy???)( jj zc ??原問(wèn)題的變量 原問(wèn)題松弛變量 對(duì)偶問(wèn)題剩余變量 對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題用兩階段法求解的最終的單純形表 （ ） 32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxx???jj zc ?原問(wèn)題 的變量 原問(wèn)題松弛變量 對(duì)偶問(wèn)題 剩余變量 對(duì)偶問(wèn)題的變量 化為極小問(wèn)題 原問(wèn)題 最優(yōu)解 對(duì)偶問(wèn)題 最優(yōu)解 原問(wèn)題化為極小問(wèn)題，最終單純形表： ? 兩個(gè)問(wèn)題作一比較 : 原問(wèn)題最優(yōu)解 （決策變量） 對(duì)偶問(wèn)題最優(yōu)解 （決策變量） 14?? wz2/3,2/7 21 ?? xx 對(duì)偶問(wèn)題的松弛變量 2/1,4/1,0 321 ??? yyy 原問(wèn)題的松弛變量 從引例中可見(jiàn)： 原問(wèn)題與對(duì)偶問(wèn)題在某種意義上來(lái)說(shuō)，實(shí)質(zhì)上是一樣的，因?yàn)榈诙€(gè)問(wèn)題僅僅在第一個(gè)問(wèn)題的另一種表達(dá)而已。 理論證明： 原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系 在下面的討論中 , 假定線性規(guī)劃原問(wèn)題和對(duì)偶問(wèn)題分別如下 原問(wèn)題 對(duì)偶問(wèn)題 ??????????????),1(0),1(..m a x11njxmibxatsxczjnjijijnjjj????????????????),1(0),1(..m i n11miynjcyatsybwimijiijmiii??1. 弱對(duì)偶性 是其對(duì)偶問(wèn)題的可行解，則恒有 ),1( njx j ??),1( miy i ??若 是原問(wèn)題的可行解， imiijnjj ybxc ?????11證明： jmiinjijjnjimiij xyaxya ? ?? ?? ?? ???1 11 1)(? ?? ?? ?? ???mijinjijimijnjji xyayxa1 11 1)(jnjj xc??1imii yb??1從弱對(duì)偶性可得到以下重要結(jié)論： ? （ 1）極大化問(wèn)題（原問(wèn)題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的下界。 ? （ 2）極小化問(wèn)題（對(duì)偶問(wèn)題）的任一可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是原問(wèn)題最優(yōu)目標(biāo)函數(shù)值的上界。 ? （ 3）若原問(wèn)題可行，但其目標(biāo)函數(shù)值無(wú)界，則對(duì)偶問(wèn)題無(wú)可行解。 ? （ 4）若對(duì)偶問(wèn)題可行，但其目標(biāo)函數(shù)值無(wú)界，則原問(wèn)題無(wú)可行解。 ? （ 5）若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界。 ? （ 6）對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。 原問(wèn)題 對(duì)偶問(wèn)題 bYXC ?bYCX ?? ? ),1(?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1