運(yùn)籌學(xué)-(單純形法原理)(已修改)
2025-08-17 17:07 本頁面
【正文】 復(fù)習(xí) 由圖解法得到的啟示： ，解的情況有：唯一解；無窮多最優(yōu)解；無界解；無可行解。 ，則可行域是一個凸集。 ，則最優(yōu)解或最優(yōu)解之一（有無窮多最優(yōu)解）一定是可行域的凸集的某個頂點(diǎn)。 ，先找出凸集的任一頂點(diǎn)，計算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個值大，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。 單純形法的計算步驟 ? 單純形法的思路 找出一個初始可行解 是否最優(yōu) 轉(zhuǎn)移到另一個基本可行解 （找出更大的目標(biāo)函數(shù)值） 最優(yōu)解 是 否 循 環(huán) 核心是：變量迭代 結(jié)束 如何改善？ 如何判斷沒有有限最優(yōu)解？ 線性規(guī)劃問題的代數(shù)運(yùn)算形式 例：用單純形法的代數(shù)運(yùn)算形式求解下列線性規(guī)劃問題 ???????????????00155164122232m a x21212121xxxxxxxxz、求解步驟 （ 1）化為標(biāo)準(zhǔn)型 （ 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為關(guān)于可行基 B0的基變量， x1 、 x2 為關(guān)于可行基 B0的非基變量，為求初始基本可行解，令非基變量 x1 = x2 =0。從而有 x3 =12， x4 =16， x5 =15，于是得到初始基本可行解： ? ?????????????1000100015430 PPPBX （ 0） =（ 0， 0， 12， 16， 15） T 其對應(yīng)的目標(biāo)函數(shù)值 z0=2 0+3 0=0 （ 3）檢驗(yàn) X（ 0） 是否為最優(yōu)解。由目標(biāo)函數(shù)的表達(dá)式： z =2x1 +3x2 可知，非基變量 x1 和 x2 的系數(shù)為正，如果把非基變量 x1 或 x2轉(zhuǎn)換為基變量，則會使目標(biāo)函數(shù)的值增加。可見 X（ 0） 不是最優(yōu)解 （ 4）第一次迭代。 每一次迭代，得到一個新的基本可行解。因此，哪些變量作為基變量，哪些非基變量，就要發(fā)生變化。 由于目標(biāo)函數(shù)中 x2的系數(shù)大于 x1的系數(shù)，因此，可以選擇 x2使它作為基變量，而且讓它取盡可能大的值，同時， x1仍作為非基變量取值為零。從原來的基變量 x3 、 x4 、 x5中選出一個作為非基變量。 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必須滿足非負(fù)約束 ，從而 θ的值應(yīng)滿足： x3 = 12 – 2 θ ≥0 x4 = 16 ≥0 x5 = 15 – 5 θ ≥0 即： x2 = θ =min{12/2， ~， 15 /5}=3
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1