對(duì)偶定理課件

返回繼續(xù)第二節(jié)對(duì)偶問(wèn)題的基本性質(zhì)對(duì)稱性弱對(duì)偶性最優(yōu)性互補(bǔ)松弛性對(duì)偶問(wèn)題的基本性質(zhì)一、對(duì)稱定理：定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。設(shè)原問(wèn)題（1）對(duì)偶問(wèn)題（2）二、弱對(duì)偶性定理：

——若和分別是原問(wèn)題（1）及對(duì)偶問(wèn)題（2）的可行解，則有證明：對(duì)偶問(wèn)題的基本性質(zhì)從弱對(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ù)值的上界。原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題的基本性質(zhì)定理三

最優(yōu)性準(zhǔn)則定理

若、分別為對(duì)稱形式對(duì)偶線性規(guī)劃的可行解，且兩者目標(biāo)函數(shù)的相應(yīng)值相等，C=b，則，分別為原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。C=bCX≤Yb弱對(duì)偶定理已知結(jié)論最優(yōu)解定義X=CX≤bY=特別取b≤YbCX≤CC≤Yb證明思路四、互補(bǔ)松弛性

——若分別是原問(wèn)題（1）與對(duì)偶問(wèn)題（2）的可行解，分別為（1）、（2）的松弛變量，則：即：為最優(yōu)解原問(wèn)題第i條約束

A的第i行

說(shuō)明：在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件為嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。另一方面：對(duì)偶問(wèn)題的第j條約束四、互補(bǔ)松弛性：

——若分別是原問(wèn)題（1）與對(duì)偶問(wèn)題（2）的可行解，分別為（1）、（2）的松弛變量，則：為最優(yōu)解原理：在一對(duì)互為對(duì)偶的線型的規(guī)劃問(wèn)題中，原問(wèn)題的變量和對(duì)偶問(wèn)題的約束是一一對(duì)應(yīng)的，原問(wèn)題的約束和對(duì)偶問(wèn)題的變量也是一一對(duì)應(yīng)的。解釋：互補(bǔ)松弛性描述了線型規(guī)劃問(wèn)題達(dá)到最優(yōu)時(shí)，原問(wèn)題（或?qū)ε紗?wèn)題）的變量取值和對(duì)偶問(wèn)題（或原問(wèn)題）約束的松緊性之間的對(duì)應(yīng)關(guān)系。書P52，例2已知：X=(x1，x2)T=(7/6，4/3)T判斷是否為最優(yōu)解？課堂練習(xí)：已知線型規(guī)劃問(wèn)題又已知其對(duì)偶問(wèn)題的最優(yōu)解為y1=4/5，y2=3/5，Z＝5。試用對(duì)偶理論解原問(wèn)題?；パa(bǔ)松弛定理應(yīng)用：（1）從已知的最優(yōu)對(duì)偶解，求原問(wèn)題最優(yōu)解，反之亦然。（2）證實(shí)原問(wèn)題可行解是否為最優(yōu)解。（3）從不同假設(shè)來(lái)進(jìn)行試算，從而研究原始、對(duì)偶