運籌學第二章ppt課件-資料下載頁

　　

【正文】 15 y1 + 24y2 + 5y3 min y1 , y2 , y3 ≥ 0 st . z39。= 15 y1 24y2 5y3 max st . 6y2 + y3 – y4 = 2 5y1 + 2y2 + y3 – y5 1 = y1, y2, y3, y4, y5 = 0 C 15 24 5 0 0 CB YB b y1 y2 y3 y4 y5 0 0 y4 y5 2 1 0 6 1 1 0 5 2 1 0 1 σ 15 24 5 0 0 C 15 24 5 0 0 CB YB b y1 y2 y3 y4 y5 1/3 1/3 0 1 1/6 –1/6 0 5 0 2/3 –1/3 1 σ 1/4 1/2 5/4 1 0 1/4 1/4 15/2 0 1 1/2 3/2 σ 15 0 1 4 0 y2 y5 24 0 24 5 y2 y3 15 0 0 7/2 –3/2 對偶單純形法優點 初始解可以是非可行解，當檢驗數都為負數時，就可以進行基的變換，這時不需要加入人工變量，因此可以簡化計算。 當變量個數多于約束條件個數，對這樣的線性規劃問題，用對偶單純形法可以減少計算的工作量。因此對變量較少而約束條件很多的線性規劃問題，可以先將它變為對偶問題，然后用對偶單純形法求解。 在靈敏度分析中 ,有時需要用對偶單純形法，可使問題的處理簡化。對偶單純形法的局限性主要是對大多數線性規劃問題，很難找到一個初始可行基，因而這方法很少單獨使用。 第五節 靈敏度分析 靈敏度分析是指對系統或事物因周圍條件變化顯示出來的敏感程度的分析。 當線性規劃問題的系數發生變化時，最優解一般要發生變化，主要有以下幾種情況： 當線性規劃問題的系數發生變化時，最優解一般要發生變化，主要有以下幾種情況： 原問題 對偶問題 結論或繼續計算的步驟 可 行 解 可 行 解 非可行解 非可行解 可 行 解 非可行解 可 行 解 非可行解 表中的解仍然為最優解 用單純形法繼續迭代求最優解 用對偶單純形法迭代求最優解 引進人工變量，編制新的單純形表，求最優解 第五節 靈敏度分析 靈敏度分析是指對系統或事物因周圍條件變化顯示出來的敏感程度的分析。 一、目標函數中價值系數 cj的變化分析 可以分別就 cj時對應的非基變量和基變量兩種情況來討論。 （ 1） 若 cj是非基變量 xj的系數，這時他在計算表中所對應的檢驗數是 當 cj變化 Δcj 時，要保證最終表中這個檢驗數仍然小于或等于零，即 σj ’=cj+Δcj CBB1Pj≤0 那么 cj+Δcj≤YPj, 即 Δcj 的值必需小于或等于YPjcj,才可以滿足原最優解條件，這可以確定 Δcj 的變化范圍了。 下面就各種情況分別進行討論。 j1= mj ij iic a y??? ?1j j B j = c C B P?? ? (2)若 cr是基變量 xr的系數。因 cr∈C B,當 cr變化 Δcr時，就引起 CB的變化，這時 ? (CB+ΔCB)B 1A=CB B1A+(0,… , Δcr, … ,0) B1A ? = CB B1A+Δcr(ar1,ar2, … ,arn) ? 可見當 cr變化 Δcr 時，最終表中的檢驗數是 ? σj ’=cj CBB1AΔcjarj ’,j=1,2,… ,n ? 若要求原最優解不變，即必需滿足 σ j’≤0 。于是得到 ? 當 arj’0， Δc r≤σ j/a rj’ ? arj’0， Δc r≥σ j/a rj’ j=1,2,… ,n ? Δc r可變化的范圍是 ? 例題見書 P64 }0|/{min}0|/{m a x ??????? rjrjjjrrjrjjj aacaa ??二、資源數量 bj變化的分析 資源數量變化是指系數 br發生變化，即 br’=br+Δb 設問題的其它系數都不變。這樣使原問題的解變為 XB’=B1(b+Δb) 這里 Δb= （ 0， … ， Δb r， 0， … ， 0） XB’ ≥0 ，最終表的檢驗數不變，則最優基不變，但最優解的值發生了變化，所以 XB’為新的最優解。 新的最優解的值可允許變化的范圍用以下方法確定。 B1(b+Δb)= B1b+ B1Δb = B1b+ B1 ， B1 ?????????????????00??rb???????????????????????????????????????????????????????????????mrirrrrmrrirrrraaabbababab??????1100這時在最終表中求得的 b列的所有元素 ， 由此得 當 例題見 P65 mibab riri ,2,1,0 ?????mibba irir ,2,1, ?????于是得到時， 。/0 iririr abba ????。/0 iririr abba ???? 時，}0|/{m i n}0|/{m a x ??????? iririiriririiaabbaab三、 技術系數 aij的變化 分兩種情況來討論技術系數 aij的變化。 例題見 P70 四、增減約束條件 例題見 P69