運籌學-(單純形法原理)-文庫吧
2025-07-21 17:07 本頁面
【正文】 相應地有： x3 = 12 – 2 3=6 x4 = 16 x5 = 15 – 5 3=0 可見，從原來的基變量 x3 、 x4 、 x5中選出 x5作為非基變量，得第一次迭代后的基本可行解： X （ 1） =（ 0， 3， 6， 16， 0） T 其對應的目標函數(shù)值： z1=2 0+3 3=9 （ 5）檢驗 X （ 1） 是否為最優(yōu)解 將約束方程組改為用非基變量 x1 、 x5來表示基變量 x x3 、 x4的表達式?？捎酶咚瓜シǖ玫剑? 2x1 + x3 – 2 /5x5 = 6 4x1 + x4 = 16 x2 + 1 /5 x5 = 3 移項后得到： x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5 將上式代入目標函數(shù)，得目標函數(shù)用非基變量 x1 、 x5表示的表達式 z =9+2x1 – 3/5x5 由于非基變量 x1的系數(shù)是正數(shù)，如果把非基變量轉換為基變量， 則會使目標函數(shù)的值增加?？梢?X （ 1） 不是最優(yōu)解。 （ 6）第二次迭代 和第一次迭代同樣的道理，應選取非基變量 x1使它成為基變量，而且讓它取盡可能大的值，同時， x5仍作為非基變量取值為零。從原來的基變量 x2 、 x3 、 x4中選出一個作為非基變量。 x1的取值也按同樣的方法確定： x3 = 6 – 2x1 + 2/5x5 x4 = 16 – 4x1 x2 = 3 –1/5 x5 將 x1 = θ ， x5 = 0代入： x3 = 6 – 2 θ ≥0 x4 = 16 – 4 θ ≥0 x2 = 3 ≥0 即： x1 = θ =min{6/2， 16 /4 ， ~}=3 相應地有： 可見，從原來的基變量 x2 、 x3 、 x4中選出 x3作為非基變量，得第二次迭代后的基本可行解： X （ 2） =（ 3， 3， 0， 4， 0） T x3 = 6 – 2 3 =0 x4 = 16 – 4 3=4 x2 = 3 其對應的目標函數(shù)值： z1=2 3+3 3=15 （ 7）檢驗 X （ 2） 是否為最優(yōu)解 將約束方程組改為用非基變量 x3 、 x5來表示基變量 x x2 、 x4的表達式?？捎酶咚瓜シǖ玫剑? x1 + 1/2 x3 – 1/5x5 = 3 – 2 x3 + x4 + 4/5x5 = 4 x2 + 1/5 x5 = 3 移項后得到： x1 = 3 – 1/2 x3 + 1/5x5 x4 = 4 + 2 x3 – 4/5x5 x2 = 3 –1/5 x5 將上式代入目標函數(shù)，得目標函數(shù)用非基變量 x3 、 x5表示的表達式 z =15 – x3 – 1/5x5 這時 ,目標函數(shù)中非基變量的系數(shù)都不大于零 ， 可見目標函數(shù)的值不可能再繼續(xù)增大 ,目標函數(shù)已經(jīng)取得最大值 15 ， 故為 X （ 2） 最優(yōu)解。 總 結 通過以上例題的分析，可以歸納出單純形法的步驟： （ 1）建立實際問題的線性規(guī)劃數(shù)學模型； （ 2）把一般的線性規(guī)劃問題化為標準型； （ 3）確定初始基本可行解； （ 4）檢驗所得到的基本可行解是否為最優(yōu)解； （ 5）迭代，求得新的基本可行解。 單純形法的三個關鍵部分： （ 1）初始基本可行解的確定； （ 2）最優(yōu)性檢驗； （ 3）如何進行迭代 : 確定入基變量 ,出基變量 單純形法一般步驟 （ 觀察法 ） ； 121 0 00 1
范文總結相關推薦
鄂ICP備17016276號-1