林齊寧-數(shù)據(jù)、模型與決策一運(yùn)籌學(xué)(編輯修改稿)
2025-03-05 14:59 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 渡到運(yùn)籌學(xué)一些相對(duì)比較抽象和難的概念和原理。這是本 課程教學(xué) 力求的另一特點(diǎn)。 一、線性方程組的解 考慮如下線性方程組的解： (1) 852532121???????xxxx(2) 2121??????xx再考慮如下線性方程組的解： (3) 85253321321?????????xxxxxx (4)221333231???????????xxxxxx(5) 021321?????????xxx一、線性方程組的解 類似地，如果將方程組（ 3）中的變量 x2或 x1當(dāng)成常數(shù)，分別移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下兩組 通 解 及其特解 ： (6) 223222321??????????xxxxxx(8) 21212123111312??????????????xxxxxx(7) 02321???????xxx(9) 02123132???????????xxx一、線性方程組的解 仔細(xì)觀察和思考方程組（ 3）的三組通解（ 4）、（ 6）和（ 8）或三組特解（ 5）、（ 7）和（ 9）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性方程組克萊姆條件可知，能夠得到方程組（ 3）的通解（ 4）或特解（ 5）的條件是方程組（ 3）中的變量 x1和 x2的系數(shù)矩陣行列式不等于 0，即 015231B1 ???或變量 x1和 x2的系數(shù)矩陣 B1是非奇異矩陣或變量 x1和 x2的系數(shù)列向量是線性無(wú)關(guān)。顯然，這三個(gè)條件是等價(jià)的。 一、線性方程組的解 同樣，由于方程組組（ 3）中的變量 x1和 x3的系數(shù)矩陣行列式|B2|不等于 0與 變量 x2和 x3的系數(shù)矩陣行列式 |B3|不等于 0， 即 0112 11B 2 ??? 0115 13B 3 ??才能得到方程組（ 3）的通解或特解（ 6）或（ 7） 與 通解或特解（ 8）或（ 9） 。 將上面討論的方程組（ 3）加上一目標(biāo)函數(shù)和變量非負(fù)約束條件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如： (10 ) 0,0,085253..32)(321321321321?????????????????xxxxxxxxxtsxxxxMaxf一、線性方程組的解 對(duì)于 上述標(biāo)準(zhǔn)型線性規(guī)劃（ 10） ,稱 B1 、 B2和 B3為線性規(guī)劃（ 10）的基。因利用其中任何一個(gè)基 B1 或 B2或 B3，都能得到線性規(guī)劃（ 10）的一組通解和特解（見式（ 4） （ 9））。 ???????5231 211xxB變量 x1和 x2為基變量，變量 x3為非基變量，令 x3=0， 得 解（ 5）為線性規(guī)劃（ 10）的基礎(chǔ)解，但 因 該基礎(chǔ)解中 x1= 10，不滿足線性規(guī)劃（ 10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（ 5） 是線性規(guī)劃（ 10）的基礎(chǔ)非可行解。 ???????1211 312xx變量 x1和 x3為基變量，變量 x2為非基變量，令 x2=0， 得 解（ 7）為線性規(guī)劃（ 10）的基礎(chǔ)解 。 該基礎(chǔ)解中 x1和 x3均大于 0，滿足線性規(guī)劃（ 10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（ 7）是線性規(guī)劃（ 10）的基礎(chǔ)可行解。 ???????1513 323xxB變量 x2和 x3為基變量，變量 x1為非基變量，令 x1=0， 得 解（ 9）為線性規(guī)劃（ 10）的基礎(chǔ)解 .該基礎(chǔ)解中 x2和 x3均大于 0，滿足線性規(guī)劃（ 10）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（ 9）是線性規(guī)劃（ 10）的基礎(chǔ)可行解。 二、 標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 ? 標(biāo)準(zhǔn)型有 n+m 個(gè)變量， m 個(gè)約束行 ? “ 基 ”的概念 – 在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有 n+m 列，即 A = ( P1, P2 , … , Pn+m ) – A中線性獨(dú)立的 m 列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè) 基 ，即 B = ( P1 ?, P2 ? , … , Pm ?)， | B | ? 0 – P1 ?, P2 ? , … , Pm ?稱為 基向量 – 與 基向量 對(duì)應(yīng)的變量稱為 基變量 ，記為 XB = ( x1 ?, x2 ? , … , xm ? )T，其余的變量稱為 非基變量 ，記為 XN = ( xm+1 ?, xm+2 ?, … , xm+n ? ) T ， 故有 X = （ XB ， XN ) – 最多有 個(gè)基 m nmC ?二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 ? 可行解 與 非可行解 – 滿足約束條件和非負(fù)條件的解 X 稱為 可行解 ，不滿足約束條件或非負(fù)條件的解 X 稱為 非可行解 ? 基礎(chǔ)解 – 對(duì)應(yīng)某一基 B且令其 非基變量 XN = 0，求得 基變量 XB的值。稱 X = (XB , XN)T為 基礎(chǔ)解。 其中 ， XB = B?1 b， XN = 0 – XB 是 基礎(chǔ)解 必須滿足如下條件： ? 1） 非 0分量的個(gè)數(shù) ? m； ? m個(gè)基變量所對(duì)應(yīng)的系數(shù)矩陣為非奇異的； ? 滿足 m個(gè)約束條件。 二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 基礎(chǔ)可行解 與 基礎(chǔ)非可行解 基礎(chǔ)解 XB 的非零分量都 ? 0 時(shí)，稱為 基礎(chǔ)可行解 ，否則為 基礎(chǔ)非可行解。 退化 解 基礎(chǔ)可行解 的非零分量個(gè)數(shù) m 時(shí)，稱為 退化解 可行基 對(duì)應(yīng)于基礎(chǔ)可行解的基稱為 可行基 最優(yōu)解 使目標(biāo)函數(shù)達(dá)到最優(yōu)的 基礎(chǔ) 可行解稱為最優(yōu)解 無(wú)窮多最優(yōu)解 當(dāng)最優(yōu)解的基變量組成不止一個(gè)時(shí)，線性規(guī)劃有 無(wú)窮多最優(yōu)解 39 三、 線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系 約束方程的 解空間 基礎(chǔ)解 可行解 非可行解 基礎(chǔ) 可行解 退化解 四、線性規(guī)劃解的判定 對(duì)于某一線性規(guī)劃的任意一個(gè)解 X，我們?nèi)绾闻卸?X是基礎(chǔ)解、或是基礎(chǔ)可行解、或是基礎(chǔ)非可行解、或是非可行解、或是可行解呢？ 判定 步驟： 寫出給定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型線性規(guī)劃； 根據(jù)基礎(chǔ)解的三個(gè)條件判定 X是否是基礎(chǔ)解。當(dāng)三個(gè)條件均滿足時(shí)， X才是基礎(chǔ)解；否則 X不是基礎(chǔ)解。若 X是基礎(chǔ)解，轉(zhuǎn)3；否則，轉(zhuǎn) 4； X是否滿足非負(fù)約束，即其基變量值是否都大于 0？若是，X是基礎(chǔ)可行解；否則 X是基礎(chǔ)非可行解。 將 X代入給定線性規(guī)劃的所有約束方程，包括非負(fù)約束，若X滿足所有約束方程，則 X為可行解，否則 X為非可行解。 41 五、線性規(guī)劃解的判定舉例 ??????????????????0,78102..46)(max543215242132121xxxxxxxxxxxxxtsxxxf1187654322 x1876543O109x2A BCEDFGH123f(x)=36K非基變量 基變量 圖中的點(diǎn) 解 x1, x2 x3 = 1 0 x4 =8 x5 =7 O 基礎(chǔ)可行解 x1, x3 x2 = 1 0 x4 = 2 x5 = 3 F 基礎(chǔ)解 x1, x4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1