【正文】 a39。mn θ mz f 0 ? 0 σm + 1? σn ci , bj發(fā)生變化 增加一約束或變量及 A中元素發(fā)生變化 — 通過例題學(xué)會處理 對于表格單純形法，通過計算得到最優(yōu)單純形表。 若 cs 是基變量的系數(shù)： 設(shè) cs 變化為 cs + ?cs ，那么 ?j’ = cj ∑cri arij ( cs + ?cs ) asj = ?j ?cs asj ， i ≠ s 對所有非基變量，只要對所有非基變量 ?j’ ≤ 0 ，即 ?j ≤ ?cs asj ， 則最優(yōu)解 不變；否則，將最優(yōu)單純形表中的檢驗數(shù) ?j 用 ?j’ 取代，繼續(xù)單純形法的表格計算 。 j=n+1,…, n+m 那么 新的 xi=(B1b)i+?brair i=1,…, m 。 例 : 例 3x1+ 2x2≤15 ，原最優(yōu)解不 滿足這個約束。 Min z=6 1+3 13+8 2+4 13+2 12+5 19=142 11 5 5 4 8 2 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH 。那么，重新計算出 B1pj ?j = cj ∑ cri ari j 填入最優(yōu)單純形表，若 ?j ≤ 0 則最 優(yōu)解不變；否則，進(jìn)一步用單純形法求解。 那么 計算出 B1pn+1 , ?n+1=+1∑ cri ari n+1 填入最優(yōu)單純形表 , 若 ?n+1 ≤ 0 則 最優(yōu)解不變； 否則，進(jìn)一步用單純形法求解。 右端項 b 發(fā)生變化 設(shè)分量 br 變化為 br + ?br ，根據(jù)第 1章的討論，最優(yōu)解的基變量 xB = B1b，那么只要保持 B1(b + ?b) ≥ 0 ，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。 價值系數(shù) c發(fā)生變化： m 考慮檢驗數(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)單純形表 中的檢驗數(shù) ?k 用 ?k’ 取代，繼續(xù)單 純形法的表格計算 。0 ? 1 a39。1n θ 1c2x2b239。 xi = bi’ i = 1 , … , m 是基本可行解 , 對應(yīng)的目標(biāo)函數(shù)典式為： z = f + ?m+1xm+1+…+ ?nxn 以下是初始單純形表： m m 其中： f = ∑ ci bi’ ?j = cj ∑ ci aij’ 為檢驗數(shù)。 除此之外 ，在對線性規(guī)劃進(jìn)行靈敏度分析中有時也要用到對偶單純形方法 ， 可以簡化計算 。 對偶單純形法求解線性規(guī)劃問題 過程： 例 ： 求解線性規(guī)劃問題： 標(biāo)準(zhǔn)化： Max z = 2x1 3x2 4x3 . x12x2x3+x4= 3 2x1+x23x3+x5= 4 x1,x2,x3,x4,x5 ≥ 0 Min f = 2x1 + 3x2 + 4x3 . x1 + 2x2 + x3 ≥ 3 2x1 x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 ? 表格對偶單純形法 CI2 3 4 0 0CBXBb X1X2X3X4X50 X43 1 2 1 1 00 X54 [ 2] 1 3 0 1σj2 3 4 0 00 X41 0 [ 5/2 ] 1/2 1 1/ 22 X12 1 1/ 2 3/2 0 1/ 2σj0 4 1 0 13 X22/5 0 1 1/ 5 2/ 5 1/52 X111/51 0 7/5 1/ 5 2/ 5σj0 0 9/ 5 8/ 5 1/ 5 單純形法和對偶單純形法步驟 是 是 是 是 否 否 否 否 所有 所有 得到 最優(yōu)解 計算 計算 典式對應(yīng)原規(guī)劃的基本解是可行的 典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù) 所有 所有 計算 計算 以為中心元素進(jìn)行迭代 以為中心元素進(jìn)行迭代 停 沒有最優(yōu)解 沒有最優(yōu)解 單純形法 對偶單純形法 0?j? 0?ib ? ?0max ??jjk ??? ?0m in ?? iie bbb 0?ika 0?ljaekeikikiabaab ??????? ?? 0m in?ekkejejiaa??? ??????????? ?? 0min 對偶單純形法的適用范圍 對偶單純形法適合于解如下形式的線性規(guī)劃問題 ? ????????????????njxmibxacxcfjnjijijnjjjj,2,1,0,2,10m in11?? 在引入松弛變量化為標(biāo)準(zhǔn)型之后 ， 約束等式兩側(cè)同乘 1， 能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解 ， 可以直接建立初始對偶單純形表進(jìn)行求解 ， 非常方便 。 注： 通過矩陣行變換運算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形表。 例 ： 求解線性規(guī)劃問題： 標(biāo)準(zhǔn)化： Max z = 2x1 3x2 4x3 . x12x2x3+x4= 3 2x1+x23x3+x5= 4 x1,x2,x3,x4,x5 ≥ 0 Min f = 2x1 + 3x2 + 4x3 . x1 + 2x2 + x3 ≥ 3 2x1 x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 對偶單純形法的基本思想 對偶單純形法的基本思想是：從原規(guī)劃的一個 基本解 出發(fā) ， 此基本解不一定可行 ， 但它對應(yīng)著一個 對偶可行解 （ 檢驗數(shù)非正 ） ， 所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行 ， 即是否有負(fù)的分量 ， 如果有小于零的分量 ，則進(jìn)行迭代 ， 求另一個基本解 ， 此基本解對應(yīng)著另一個對偶可行解 （ 檢驗數(shù)非正 ） 。 需要指出 ， 影子價格不是固定不變的 ， 當(dāng)約束條件 、 產(chǎn)品利潤等發(fā)生變化時 ， 有可能使影子價格發(fā)生變化 。 定理 32 (最優(yōu)性準(zhǔn)則定理 ) 若 x,y分別 (LP),(