運(yùn)籌學(xué)課件第1章線性規(guī)劃與單純形法-第3節(jié)(編輯修改稿)
2025-01-31 01:33 本頁面
【文章內(nèi)容簡介】 ?????????11,211,222111,111231得到一個初始基可行解 ? 又因 bi≥ 0(在 13節(jié)中已做過規(guī)定 )， 所以得到一個初始基可行解 ? X=(x1,x2,…,xm,0， …， 0)T nm個 =(b1,b2,…,bm,0， …， 0)T nm個 (3)加非負(fù)的人工變量 ? 對所有約束條件是 “ ≥ ” 形式的不等式及等式約束情況 ， 若不存在單位矩陣時 ，就采用人造基方法 。 ? 即對不等式約束減去一個非負(fù)的剩余變量后 ， 再加上一個非負(fù)的人工變量； ? 對于等式約束再加上一個非負(fù)的人工變量 ， 總能得到一個單位矩陣 。 關(guān)于這個方法將在本章第 5節(jié)中進(jìn)一步討論 。 ? 對線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況， ? 為此需要建立對解的判別準(zhǔn)則。一般情況下，經(jīng)過迭代后 (123)式變成 ? ? ? ?241,2,1,139。39。 ???? ???nmjjijii nixabx ? 將 代入目標(biāo) 函數(shù) (120)式，整理后得 ? ?251)(1 1 139。39。1139。1139。1139。1139。11 139。39。1 11????????????????????????? ? ??? ???????? ?? ??? ?? ????? ??????????? ??? ???minmjjmiijijiinmjjjnmjjijmiimiiinmjjjnmjjijmiimiiinmjjjminmjjijiiminmjjjiinjjjxaccbcxcxacbcxcxacbcxcxabcxcxcxcz??????nmjmijxijaibix1),2,1,39。39。( ?令 ? ?? ?????mimiijijii nmjaczbcz1 139。39。0 ,1, ?? ????????nmjjjj xzczz10 )261(于是nmjzc jjj ,1 ??????設(shè)? ?27110 ??? ???nmjjj xzz ? 1 最優(yōu)解的判別定理 ? 若 為對應(yīng)于基 B的一個基可行解，且對于一切 j=m+1,…,n ，有 σ j≤ 0，則 X(0)為最優(yōu)解。稱 σ j為檢驗(yàn)數(shù)。 ? ? ? ?TmbbbX 0,0, 39。39。239。10 ???? 當(dāng)所有非基變量的 σ j≤ 0時 ， 由 （ 127） 式可知已不存在任一可換入的非基變量 ， 使目標(biāo)函數(shù)繼續(xù)增大 。 所以以 σ j≤ 0， 為最優(yōu)解的判別準(zhǔn)則 。 ? 若 為一個基可行解 ， 對于一切 j=m+1， …,n， 有 σ j≤ 0，又存在某個非基變量的檢驗(yàn)數(shù) σ m+k=0， 則線性規(guī)劃問題有無窮多最優(yōu)解 。 ? 證 : 只需將非基變量 xm+k換入基變量中 ， 找到一個新基可行解 X(1)。 因 σ m+k=0， 由 (127)知 z=z0， 故 X(1)也是最優(yōu)解 。 由 定理 3可知 X(0)， X(1)連線上所有點(diǎn)都是最優(yōu)解 。 ? ? ? ?T39。m39。39。 ,b,b,bX 00210 ??? 3．無界解判別定理 若 為一基可行解 ， 有一個 σ m+k＞ 0， 并且對 i=1,2,…， m， 有 存在。 那么該線性規(guī)劃問題具有無界解 (或稱無最優(yōu)解 )。 ? ? ? ?TmbbbX 0,0, 39。39。239。10 ???039。 , ?? kmia證 : 構(gòu)造一個新的解 X(1)，它的分量為 ? ?? ?? ?? ?kmjnmjxxabxjkmkmiii???????????并且,1。001139。,39。1????? 因 ， 所以對任意的 λ ＞ 0都是可行解 ， 把 x(1)代入目標(biāo)函數(shù)內(nèi)得 z=z0+λσ m+k ? 因 σ m+k＞ 0， 故當(dāng) λ →+∞ ， 則 z→+∞ ，故該問題目標(biāo)函數(shù)無界 。 039。 , ?? kmia? 以上討論都是針對標(biāo)準(zhǔn)型，即求目標(biāo)函數(shù)極大化時的情況。當(dāng)求目標(biāo)函數(shù)極小化時，一種情況如前所述，將其化為標(biāo)準(zhǔn)型。 ? 如果不化為標(biāo)準(zhǔn)型，只需在上述 1， 2點(diǎn)中把 σ j≤ 0改為 σ j≥ 0，第 3點(diǎn)中將 ? σ m+k＞ 0改寫為 σ m+k＜ 0即可。 基變換 若初始基可行解 X(0)不是最優(yōu)解及不能判別無界時 ， 需要找一個新的基可行解 。 具體做法是從原可行解基中換一個列向量 (當(dāng)然要保證線性獨(dú)立 )， 得到一個新的可行基 ， 這稱為基變換 。 為了換基 ， 先要確定換入變量 ， 再確定換出變量 ， 讓它們相應(yīng)的系數(shù)列向量進(jìn)行對換 ， 就得到一個新的基可行解 。 由 (127)式看到 ， 當(dāng)某些 σj
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1