修正對(duì)偶ppt課件-閱讀頁(yè)
2025-05-21 03:05本頁(yè)面
【正文】 某個(gè)變量的值沒(méi)有非負(fù)限制 ， 則在對(duì)偶 DP問(wèn)題中與此變量對(duì)應(yīng)的那個(gè)約束為等式 。 上一頁(yè) 下一頁(yè) 返回 例 寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型 解 先將約束條件變形為 “ ≤ ” 形式 ， 再根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系 ， 寫出對(duì)偶規(guī)劃 ???????????????????????????沒(méi)有非負(fù)限制321432143143214321,0,0,1053042260272252375m a xxxxxxxxxxxxxxxxxxxz 上一頁(yè) 下一頁(yè) 返回 54321 510306025m i n yyyyyw ?????122 321 ????? yyy123 31 ??? yy5472 321 ???? yyy72 5421 ????? yyyy0, 5432 ?yyyy上一頁(yè) 下一頁(yè) 返回 定理 3.. 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題 . 定理 若 X , Y 分別為（ LP)和（ DP）的任意可行解，那么 CTX ≤ bTY. 3 對(duì)偶定理 證 : A X ≤b , X TATY ≤bT Y。 bTY(0) =CTX(0) ≤ bTY. 定理 3.. 若原問(wèn)題的目標(biāo)無(wú)界 ,則其對(duì)偶問(wèn)題必?zé)o可行解 . 證 : 若對(duì)偶問(wèn)題有可行解 Y(0),則 CTX ≤ bTY(0) 與原問(wèn)題的目標(biāo)無(wú)界矛盾 . 上一頁(yè) 下一頁(yè) 返回 的關(guān)系 定理 若 (LP)和 (DP)中有一個(gè)有最優(yōu)解 ,則另一個(gè)問(wèn)題也必存在最優(yōu)解 ,且兩個(gè)問(wèn)題的最優(yōu)解的目標(biāo)函數(shù)值必相等 . (1)兩個(gè)問(wèn)題都有可行解 ,從而都有最優(yōu)解 。 (3)兩個(gè)問(wèn)題都無(wú)可行解 . 上一頁(yè) 下一頁(yè) 返回 Max z = CT X . AX ≤ b X ≥ 0 證 Max z = C TX+CαTX α . AX +Iα X α = b X ≥ 0, X α ≥0 最優(yōu)解 X* =[X*0 , X* α ]T , X*B =B1b . X*0 為原問(wèn)題變量 σj ≥ 0, 即 σj = CBTB1Pj cj ≥0. j=1,2,…,n+1, …,n+m CBT B1 (p1 ,p2 ,…, pn pn+1 ,…, pn+m)(c1,c2 ,…, +1 ,…, +m )≥0 原問(wèn)題變量檢驗(yàn)數(shù) CBT B1 (p1 ,p2 ,…, pn )(c1,c2 ,…, )≥0(1) 松弛變量的檢驗(yàn)數(shù) CBT B1 (pn+1 ,…, pn+m)(+1 ,…, +m )≥0(2) 由 (1) CBTB1A CT≥0, 得 CBTB1A ≥ CT, 記 Y * =( CBTB1)T 則 A TY* ≥ C 即 Y* 滿足對(duì)偶問(wèn)題的約束 又由 (2)知 CBT B1 I (0,0…,0 ) ≥ 0 (3) 得 CBT B1 ≥ 0 ,即 Y * ≥ 0 , Y*滿足對(duì)偶問(wèn)題的非負(fù)條件 . Min f = bTY . ATY≥ C Y ≥ 0 上一頁(yè) 下一頁(yè) 返回 故 Y* = (CBTB1)T 為對(duì)偶問(wèn)題的可行解 . 且有 b TY* = (Y*Tb) T=(CBTB1 b)T = X*BT CB = CBT XB* (4) 下證兩個(gè)問(wèn)題的目標(biāo)最優(yōu)值相等 ,從而 Y*為最優(yōu)解 : 將原問(wèn)題最優(yōu)值 Z*按基變量 X*B與非基變量 X*N表示 : 將原問(wèn)題最優(yōu)值 Z*按最優(yōu)解 X* =[X0*, Xα* ]T表示 : 對(duì)偶問(wèn)題目標(biāo)函數(shù)在可行解 Y* =( CB B1)T的目標(biāo)值為 f* = bTY *,再由 (4)(5)有 : Z*= C X*0 = Y* b= f* , X*0 , Y * 分別為原問(wèn)題與對(duì)偶問(wèn)題的可行解且目標(biāo)值相等 ,由推論 , X*0 , Y *必為各自問(wèn)題的最優(yōu)解 . Z*= CBT X*B + CNT X*N = CBT X*B Z*= CT X*0 + CαTX*α = CT X*0 故 CBT X*B = CT X*0 (5) 上一頁(yè) 下一頁(yè) 返回 由上述證明過(guò)程可以得出 : 推論 1 若線性規(guī)劃原問(wèn)題有最優(yōu)解 ,最優(yōu)基為 B, 則 Y* = (CBT B1)T就是其對(duì)偶問(wèn)題的一個(gè)最優(yōu)解 . 推論 2 對(duì)于對(duì)稱形式的線性規(guī)劃原問(wèn)題 ,若有最優(yōu)解 ,則在其最優(yōu)單純形表中 ,松弛變量的檢驗(yàn)數(shù)就是對(duì)偶問(wèn)題的一個(gè)最優(yōu)解 . 上一頁(yè) 下一頁(yè) 返回 若 X*, W* 分別為（ LP）和（ DP）的最優(yōu)解， 那么， C X* = W*b 。稱 wi* 為 bi的影子價(jià)格。 對(duì)偶解的經(jīng)濟(jì)解釋 上一頁(yè) 下一頁(yè) 返回 Max z =2x1+3x2 . x1+2x2≤ 8 4x1≤ 16 4x2≤ 12 x1 ,x2 ≥0 x1* =4, x2* =2 z* =14 x1 x2 O x1+2x2 =8 x1 =4 x2 =8 2x1+3x2 =C A(4,2) Min f = 8w1+ 16w2 + 12w3 . w1+4w2 ≥2 2w1+4w3 ≥3 w1, w2 , w3 ≥ 0 上一頁(yè) 下一頁(yè) 返回 A 由互補(bǔ)定理 ,將 x1* , x2*代入第三個(gè)約束，為嚴(yán)格不等號(hào)，故 w*3 =0； 又 x1* , x2*嚴(yán)格大于零故對(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 上一頁(yè) 下一頁(yè) 返回 一、對(duì)偶單純形法的基本思想 (1)基本思想 從原問(wèn)題的一個(gè)基本解 (不一定是可行解 )出發(fā) ,它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非負(fù)），也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原問(wèn)題的基本解是否可行，即是否有負(fù)的分量，如果有負(fù)的分量，則求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非負(fù)）。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性，使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。≥0,則得到最優(yōu)解 ,停止 。k0,由 br180。 0}, 基變量 xr 為出基變量 , Ar 為主行 .轉(zhuǎn) 3 3) 若所有 arj≥0( j = 1,2,…, n )， 則原問(wèn)題無(wú)可行 解 ,停止
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1