運籌學-(單純形法原理)-文庫吧資料
2024-08-18 17:07本頁面
【正文】 的目標函數值 z0=2 0+3 0=0 （ 3）檢驗 X（ 0） 是否為最優(yōu)解。比較周圍相鄰頂點的目標函數值是否比這個值大，如果為否，則該頂點就是最優(yōu)解的點或最優(yōu)解的點之一，否則轉到比這個點的目標函數值更大的另一頂點，重復上述過程，一直到找出使目標函數值達到最大的頂點為止。 ，則最優(yōu)解或最優(yōu)解之一（有無窮多最優(yōu)解）一定是可行域的凸集的某個頂點。復習 由圖解法得到的啟示： ，解的情況有：唯一解；無窮多最優(yōu)解；無界解；無可行解。 ，則可行域是一個凸集。 ，先找出凸集的任一頂點，計算在頂點處的目標函數值。 單純形法的計算步驟 ? 單純形法的思路 找出一個初始可行解 是否最優(yōu) 轉移到另一個基本可行解 （找出更大的目標函數值） 最優(yōu)解 是 否 循 環(huán) 核心是：變量迭代 結束 如何改善？ 如何判斷沒有有限最優(yōu)解？ 線性規(guī)劃問題的代數運算形式 例：用單純形法的代數運算形式求解下列線性規(guī)劃問題 ???????????????00155164122232m a x21212121xxxxxxxxz、求解步驟 （ 1）化為標準型 （ 2）找一個初始基本可行解 X（ 0） ???????????100500100400122A???????????0013P???????????0104P???????????1005P? ?121 2 31425m a x 2 32 2 124 165 150 1 , 2 , 5jz x xx x xxxxxxj??? ? ??????????? ???L ， B0為一個可行基， x3 、 x4 、 x5為關于可行基 B0的基變量， x1 、 x2 為關于可行基 B0的非基變量，為求初始基本可行解，令非基變量 x1 = x2 =0。由目標函數的表達式： z =2x1 +3x2 可知，非基變量 x1 和 x2 的系數為正，如果把非基變量 x1 或 x2轉換為基變量，則會使目標函數的值增加。 每一次迭代，得到一個新的基本可行解。 由于目標函數中 x2的系數大于 x1的系數，因此，可以選擇 x2使它作為基變量，而且讓它取盡可能大的值，同時， x1仍作為非基變量取值為零。 x2的取值不能任意地增加，它要受到約束方程的限制： 2x1 +2x2 + x3 = 12 4x1 + x4 = 16 5x2 + x5 = 15 x3 = 12 –2x1 – 2x2 x4= 16 – 4x1 x5 = 15 – 5x2 將 x1 = 0， x2 = θ代入上面約束方程 ，為了 讓 θ取盡可能大的值 ，同時又要考慮到 x3 、 x4 、 x5必須滿足非負約束 ，從而 θ的值應滿足： x3 = 12 – 2 θ ≥0 x4 = 16 ≥0 x5 = 15 – 5 θ ≥0 即： x2 = θ =min{12/2， ~， 15 /5}=3 相應地有： x3 = 12 – 2 3=6 x4 = 16 x5 = 15 – 5 3=0 可見，從原來的基變量 x3 、 x4 、 x5中選出 x5作為非基變量，得第一次迭代后的基本可行解： X （ 1） =（ 0， 3， 6， 16， 0） T 其對應的目標函數值： z1=2 0+3 3=9 （ 5）檢驗 X （ 1） 是否為最優(yōu)解 將約束方程組改為用非基變量 x1 、 x
范文總結相關推薦
鄂ICP備17016276號-1