運(yùn)籌學(xué)對偶問題ppt課件(2)-閱讀頁
2025-05-18 18:35本頁面
【正文】 b列最小的數(shù)對應(yīng)的變量為換出變量 ?確定換入變量 ：用檢驗(yàn)數(shù)去除以換出變量行的那些對應(yīng)的負(fù)系數(shù)，在除得的商中選取其中最小者對應(yīng)的變量為換入變量 例 用對偶單純形法求解如下的 LP問題 ??????????????0,1252652415m i n32132132321xxxxxxxxxxxz化成標(biāo)準(zhǔn)形式 ?????????????????0,1252652415m a x3215321432321xxxxxxxxxxxxxw?????????????????????0,1252652415m a x3215321432321xxxxxxxxxxxxxw將各約束條件兩端同乘“ 1”得 用對偶單純形法求解得 15 24 5 0 0Cb Xb b x1 x2 x3 x4 x50 x4 2 0 6 1 1 00 x5 1 5 2 1 0 115 24 5 0 024 x2 1/3 0 1 1/6 1/6 00 x5 1/3 5 0 2/3 1/3 115 0 1 4 024 x2 1/4 1 1/4 1 0 1/4 1/45 x3 1/2 7 1/2 0 1 1/2 1 1/27 1/2 0 0 3 1/2 1 1/2最優(yōu)解： x1=0, x2=1/4, x3=1/2, x4=0, x5=0 最優(yōu)目標(biāo)函數(shù)值： w*=（ z*=） 注：通常很少直接使用對偶單純形法求解線性規(guī)劃問題。 靈敏度分析的步驟 ? 將參數(shù)的改變計(jì)算反映到最終表上來。139。 1 bBb2 1 0 0 0Cb Xb b x1 x2 x3 x4 x50 x3 17 1/2 0 0 1 2 1/2 7 1/22 x1 5 1/2 1 0 0 1/4 1/21 x2 1/2 0 1 0 1/4 1 1/20 0 0 1/4 1/20 x3 12 1/2 0 10 1 0 7 1/22 x1 5 1 1 0 0 10 x4 2 0 4 0 1 60 1 0 0 2代入原最終表 （ 2）設(shè)現(xiàn)在每天調(diào)試工序的時(shí)間為 x，則最終表中 b列的數(shù)變?yōu)? ???????????????????????????????????????????????xxxxbBb2362162154524152/34/102/14/102/154/5139。就可得到所需的最優(yōu)解。5 1,58 21 ???? wyy將該最優(yōu)解代入對偶問題約束條件可知，第四個(gè)約束條件為嚴(yán)格不等式，因此在原問題最優(yōu)解中 .04 ?x而由于 0, 21 ?yy因此將原問題最優(yōu)解代入原問題約束條件，它們成為等式。于是原問題最優(yōu)解滿足方程組 ????????????????5/1953232232321321321xxxxxxxxx解方程組得原問題最優(yōu)解： 0,51,0,574321 ???? xxxx ??????????????????????0,0121222m i n321321321321321yyyyyyyyyyyyyyyw無約束，（ 2）直接觀察可知對偶問題有解 對應(yīng)于該解的目標(biāo)函數(shù)值 由弱對偶性，原問題的任何可行解的目標(biāo)函數(shù)值都滿足 0,1,0 321 ??? yyy1?w.1?? wz0,0,0 321 ??? xxx?????????????????.0,01122m i n2121212121yyyyyyyyyyw0, 21 ?yy 原問題顯然有可行解 。這說明這些約束條件不能同時(shí)成立。由弱對偶性，原問題目標(biāo)函數(shù)無
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1