算法合集之淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用-資料下載頁
2024-10-16 20:32本頁面
【正文】 問題的可行解，則恒有 c*x ≤ b*y ?最優(yōu)性 ?如果 x是原問題的可行解， y是其對(duì)偶問題的可行解，且有 c*x = b*y，則 x和 y是各自問題的最優(yōu)解 ?強(qiáng)最優(yōu)性（對(duì)偶定理） ?如果原問題及其對(duì)偶問題均有可行解，則兩者均有最優(yōu)解，且最優(yōu)解的目標(biāo)函數(shù)值相同 最大最小定理和線性規(guī)劃 ?二部圖最大匹配 ?每個(gè)變量 x對(duì)應(yīng)一條邊 ?對(duì)于每個(gè)頂點(diǎn) v， S(v)表示所有與 v關(guān)聯(lián)的邊的集合 ???????????????)(1),(}1,0{),(..m a xvSeeeEeexGVvxGEetsx最大最小定理和線性規(guī)劃 ?二部圖最小覆蓋 ?每個(gè)變量 y對(duì)應(yīng)一個(gè)點(diǎn) ????????????1),(),(}1,0{),(..min)(vuvGVvvyyGEvuyGVvtsy最大最小定理和線性規(guī)劃 ?弱對(duì)偶性： ?最大匹配的大小不超過最小覆蓋的大小 ?最優(yōu)性： ?如果一個(gè)匹配 M和一個(gè)覆蓋 S的大小相等，那么M就是最大匹配， S就是最小覆蓋 ?強(qiáng)對(duì)偶性 ?最大匹配等于最小覆蓋 弱對(duì)偶性的證明 ?????miiinjjj ybxc11? ?? ??? ?? ??? ?? ??? ?? ????????????????????minjijijiminjjijmiiiminjijijjnjmiiijnjjjyxAyxAybyxAxyAxc1 11 111 11 11證明 因?yàn)? 所以 ?????miiinjjj ybxc11最優(yōu)性的證明 ??????????niiinjjjniiinjjj ybxcybxc1111**，證明 設(shè) x*是原問題的最優(yōu)解， y*是其對(duì)偶問題的最優(yōu)解 ??????????niiimiiinjjjnjjj ybybxcxc1111** ，???????????niiiniiinjjjnjjj ybybxcxc1111**因?yàn)? 又知 所以
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1