對(duì)偶問(wèn)題和運(yùn)輸問(wèn)題(編輯修改稿)
2025-01-13 20:41 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 m 考慮檢驗(yàn)數(shù) ?j = cj ∑ cri arij j =1,2,……, n i = 1 1. 若 ck是非基變量的系數(shù)： 設(shè) ck變化為 ck + ?ck ?k’ = ck + ?ck ∑ cri arik = ?k+ ?ck 只要 ?k’ ≤ 0 , 即 ?ck ≤ ?k ， 則 最優(yōu)解不變；否則，將最優(yōu)單純形表 中的檢驗(yàn)數(shù) ?k 用 ?k’ 取代，繼續(xù)單 純形法的表格計(jì)算 。 例 : Max z = 2x1 3x2 4x3 . x12x2x3+x4 = 3 2x1+x23x3+x5 = 4 x1 ,x2 ,x3 ,x4 ,x5 ≥0 例：最優(yōu)單純形表 C I 2 3 4 0 0C B X B b X 1 X 2 X 3 X 4 X 53 X 2 2/5 0 1 1/ 5 2/ 5 1/52 X 1 11/5 1 0 7/5 1/ 5 2/ 5σ j 0 0 9/ 5 8/ 5 1/ 5C I 2 3 4 + Δ c30 0C B X B b X 1 X 2 X 3 X 4 X 53 X 2 2/5 0 1 1/ 5 2/ 5 1/52 X 1 11 /5 1 0 7/5 1/ 5 2/ 5σ j 0 0 9/ 5 + Δ c 3 8/ 5 1/ 5 從表中看到 σ 3= c3+Δ c3(c2 a13+c1 a23 ) 可得到 Δ c3 ≤ 9/5 時(shí)，原最優(yōu)解不變。 若 cs 是基變量的系數(shù)： 設(shè) cs 變化為 cs + ?cs ，那么 ?j’ = cj ∑cri arij ( cs + ?cs ) asj = ?j ?cs asj ， i ≠ s 對(duì)所有非基變量，只要對(duì)所有非基變量 ?j’ ≤ 0 ，即 ?j ≤ ?cs asj ， 則最優(yōu)解 不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù) ?j 用 ?j’ 取代，繼續(xù)單純形法的表格計(jì)算 。 Max{?j/asj?asj0}≤ ?cs≤Min{ ?j/asj?asj0} 例 : Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 . x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0 例 : 下表為最優(yōu)單純形表 ,考慮 基變量系數(shù) c2發(fā)生變化 C i2 3 0 0 0CBXBB X1X2X3X4X52 X14 1 0 0 1/ 4 00 X54 0 0 2 1/ 2 13 X22 0 1 1/ 2 1 / 8 0σj 0 0 1 / 8 0Ci2 3+ Δ C 2 0 0 0CBXBB X1X2X3X4X5211 0 4 00 54 0 2 1/ 2 13+ Δ C2 X 2 2 1 1/ 2 /σj 0 0 1 . 5 Δ C 2 /2 1 / 8 + Δ C 2 /8 0從表中看到 σ j=cj(c1 a1j+c5 a5j+(c2+Δ c2) a2j)j=3,4 可得到 3≤Δ c2≤1 時(shí)，原最優(yōu)解不變。 右端項(xiàng) b 發(fā)生變化 設(shè)分量 br 變化為 br + ?br ，根據(jù)第 1章的討論，最優(yōu)解的基變量 xB = B1b，那么只要保持 B1(b + ?b) ≥ 0 ，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對(duì)偶單純形法繼續(xù)計(jì)算。 對(duì)于問(wèn)題 (LP) Max z = cT x . Ax ≤ b x ≥ 0 最優(yōu)單純形表中含有 B1=( aij ） i=1,…, m。 j=n+1,…, n+m 那么 新的 xi=(B1b)i+?brair i=1,…, m 。 由此可得，最優(yōu)基不變的條件是 Max {bi/air?air0}≤ ?br≤ Min{bi/air?air0} 例 : 上例最優(yōu)單純形表如下 C i2 3 0 0 0CBX BB X 1X 2X 3X 4X 52 X 14 1 0 0 1/4 00 X 54 0 0 2 1/2 13 X 22 0 1 1/2 1/8 0σj0 0 1. 5 1/8 0 0 0 這里 B1 = 2 1 0 各列分別對(duì)應(yīng) b b b3 的單一變化 因此，設(shè) b1 增加 4，則 x1 ,x5 ,x2 分別變?yōu)椋? 4+0 4=4, 4+(2) 4=40, 2+ 4=4 用對(duì)偶單純形法進(jìn)一步求解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17 增加一個(gè)變量 增加變量 xn+1 則有相應(yīng)的pn+1 ,+1 。 那么 計(jì)算出 B1pn+1 , ?n+1=+1∑ cri ari n+1 填入最優(yōu)單純形表 , 若 ?n+1 ≤ 0 則 最優(yōu)解不變； 否則，進(jìn)一步用單純形法求解。 例 : 例 x6 , p6=( 2, 6, 3 )T, c6=5 計(jì)算得到 Ci2 3 0 0 0 5CBXBb X1X2X3X4X5X62 X14 1 0 0 1/ 4 0 0 X54 0 0 2 1/ 2 1 [ 2]3 X22 0 1 1/ 2 1/ 8 0 σj0 0 1/ 8 0 用單純形法進(jìn)一步求解，可得： x* = ( 1,0,0,0,2 )T f* = 增加一個(gè)約束 增加約束一個(gè)之后，應(yīng)把最優(yōu)解帶 入新的約束，若滿足則最優(yōu)解不變，否則 填入最優(yōu)單純形表作為新的一行，引入一 個(gè)新的非負(fù)變量（原約束若是小于等于形 式可引入非負(fù)松弛變量，否則引入非負(fù)人 工變量），并通過(guò)矩陣行變換把對(duì)應(yīng)基變 量的元素變?yōu)?0，進(jìn)一步用單純形法或?qū)? 偶單純形法求解。 例 : 例 3x1+ 2x2≤15 ，原最優(yōu)解不 滿足這個(gè)約束。 于是 C i 2 3 0 0 0 0 C B X B b X 1 X 2 X 3 X 4 X 5 X 6 2 X 1 4 1 0 0 1 /4 0 0 0 X 5 4 0 0 2 1 /2 1 0 3 X 2 2 0 1 1 /2 1 /8 0 0 0 X 6 1 0 0 1 1/ 2 0 1 σj 0 0 1 . 5 1 /8 0 0 經(jīng)對(duì)偶單純形法一步，可得最優(yōu)解為（ , , 0, 0, 3, 2 )T，最優(yōu)值為 13. 75 A中元素發(fā)生變化 (只討論 N 中某一列 變化情況） 與增加變量 xn+1 的情況類似，假設(shè) pj 變化 。那么，
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1