修正對(duì)偶ppt課件-資料下載頁
2025-05-06 03:05本頁面
【正文】 大于零故對(duì)應(yīng)的對(duì)偶約束為等號(hào) w*1+4w*2 = 2, 2w*1+4w*3 = 3 解得 w*1 = ,w*2 = , w*3 =0 x1 x2 O B(4,),z=,比原目標(biāo)增 C B x1+2x2 =8 C(,),z=,比原目標(biāo)增 x2 =3 4x2 =13 2x1+3x2 =C 4x1 =16 上一頁 下一頁 返回 一、對(duì)偶單純形法的基本思想 (1)基本思想 從原問題的一個(gè)基本解 (不一定是可行解 )出發(fā) ,它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非負(fù)），也可以說是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原問題的基本解是否可行，即是否有負(fù)的分量，如果有負(fù)的分量，則求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非負(fù)）。 如果得到的基本解的分量皆非負(fù)，則該基本解為最優(yōu)解。也就是說，對(duì)偶單純形法在迭代過程中始終保持對(duì)偶解的可行性，使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。 上一頁 下一頁 返回 (2)離基變量與進(jìn)基變量的選擇 c 1 c 2 … c m … c k … c n C B X B b x1 x 2 … x j … x k … x n Z Z 0 σ1 σ 2 … σ j … σ k … σ n c 1 x 1 b 1 a 1 1 a 1 2 … a 1 j … a 1 k … a 1 n ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ c r x r b r a r 1 a r 2 … a r j … ( a r k ) … a r n ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ c m x m b m a m 1 a m 2 … a m j … a m k … a mn 選取負(fù)值的基變量出基 :br =min{bi0 }, xr為出基變量 上一頁 下一頁 返回 1) 若第 r 行所有元素 arj ? 0 則原問題無可行解 . xr =br – (ar1 x1 …+ arj xj + …), j?JN 2) 若第 r行有 ark 0 , k?JN， 則相應(yīng)的非基變量可能成為基變量 , 此時(shí) br /= br / ark 0,有利于向可行解轉(zhuǎn)化 ,但還需考慮保證對(duì)偶解的可行性 ,即新檢驗(yàn)數(shù) ? j/ ≥ 0 ,于是取 ?k /ark = max{?j /arj | arj 0, j?JN } 則 ?j/ = ?j –(arj /ark ) ?k = ?j –(?k/ark ) arj ≥ ?j –(?j /arj ) arj =0 此 時(shí) xr為出基變量 . 上一頁 下一頁 返回 1) 建立初始對(duì)偶單純形表 ,對(duì)應(yīng)一個(gè)基本解 ,所有檢驗(yàn)數(shù)均非負(fù) ,轉(zhuǎn) 2； 二、對(duì)偶單純形法求解線性規(guī)劃問題步驟 2) 若 b180?！?,則得到最優(yōu)解 ,停止 。否則 ,若有 b180。k0,由 br180。 =min{bk180。 0}, 基變量 xr 為出基變量 , Ar 為主行 .轉(zhuǎn) 3 3) 若所有 arj≥0( j = 1,2,…, n )， 則原問題無可行 解 ,停止 。否則 ,若有 arj0 ， 則選 ?=max{?j / arj┃ arj0}=?k/ark 那么 xk為進(jìn)基變量 , Pk為主列 , 轉(zhuǎn) 4； 4) 以 ark為主元 ,作矩陣行變換使其變?yōu)?1,該列其它元變?yōu)?0,轉(zhuǎn) 2. 上一頁 下一頁 返回 對(duì)偶單純形法優(yōu)缺點(diǎn) ： 優(yōu)點(diǎn) : 1)原問題的初始解可以是非可行解 .當(dāng)檢驗(yàn)數(shù)都是非負(fù)時(shí) ,就可以進(jìn)行基變換 ,不需要加入人工變量 ,因此可以簡化計(jì)算 2)當(dāng)變量多于約束條件個(gè)數(shù) ,用對(duì)偶單純形法可以減少工作量 3)在靈敏度分析中有時(shí)用對(duì)偶單純形法較簡單 缺點(diǎn) : 對(duì)偶單純形法要求滿足對(duì)偶問題有可行性解 .該條件不是總能滿足 ,因此這個(gè)方法很少單獨(dú)使用 . 上一頁 下一頁 返回 例：求解線性規(guī)劃問題： 解 Max Z = 2x1 3x2 4x3 x12x2x3+x4= 3 2x1+x23x3+x5= 4 x1,x2,x3,x4,x5 ≥ 0 Min z= 2x1 + 3x2 + 4x3 . x1 + 2x2 + x3 ≥ 3 2x1 x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 上一頁 下一頁 返回 2 3 4 0 0 Z 0 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x 4 3 1 2 1 1 0 0 x 5 4 [ 2 ] 1 3 0 1 1 3 / 4 Z 4 0 4 1 0 x 4 1 0 [ 5/2 ] 1/2 1 1/2 2 x 1 2 1 1/2 3/2 0 1/2 8/5 2 上一頁 下一頁 返回 最優(yōu)解 :(11/5,2/5,0,0,0) 最優(yōu)值 : Z*= 28/5, z*=28/5 Z 2 8 /5 0 0 9 /5 8 /5 1 /5 3 x 2 2 /5 0 1 1 /5 2 /5 1 /5 2 x 1 1 1 /5 1 0 7 /5 1 /5 2 /5 Z 4 0 4 1 0 1 0 x 4 1 0 [ 5 /2 ] 1 /2 1 1 /2 2 x 1 2 1 1 /2 3 /2 0 1 /2 8 /5 2 上一頁 下一頁 返回 是 是 是 是 否 否 否 否 所有 所有 得到 最優(yōu)解 計(jì)算 計(jì)算 典式對(duì)應(yīng)原規(guī)劃的基本解是可行的 典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù) 所有 所有 計(jì)算 計(jì)算 以 為主元素進(jìn)行迭代 以 為主元素進(jìn)行迭代 停 沒有最優(yōu)解 沒有可行解 ,最優(yōu)解 單純形法 對(duì)偶單純形法 單純形法和對(duì)偶單純形法步驟
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1