某大學(xué)---運(yùn)籌學(xué)一-資料下載頁
2025-05-24 11:28本頁面
【導(dǎo)讀】數(shù)據(jù)、模型與決策課程（下）的學(xué)習(xí)！本講的主要內(nèi)容：?？茖W(xué)意義上的運(yùn)籌學(xué)公認(rèn)為產(chǎn)生于第二。次世界大戰(zhàn)期間。以英國為代表的科學(xué)。家做了奠基性的工作。四十年代之后，運(yùn)籌學(xué)取得全面的發(fā)展。1）運(yùn)籌學(xué)發(fā)展過程中面臨的一些問題：。題、體系厐雜等。運(yùn)籌學(xué)應(yīng)該在三個(gè)方面都應(yīng)有所發(fā)展：?；I學(xué)的數(shù)學(xué)理論。運(yùn)籌學(xué)發(fā)展到今天已經(jīng)形成了一個(gè)龐大的學(xué)科。3）與相關(guān)學(xué)科的關(guān)系：控制論、系統(tǒng)論、技。機(jī)系統(tǒng)，并使之最好地運(yùn)行的一門學(xué)科。助管理者科學(xué)地決定其策略和行動(dòng)。和運(yùn)輸問題研究所作的開拓性工作。線性規(guī)劃目前仍然還在發(fā)展，主要是：大型線性規(guī)劃
【正文】 ? 基本解 假設(shè) B為線性規(guī)劃問題的基，對(duì)約束系數(shù)矩陣 A、目標(biāo)函數(shù)系數(shù)向量 C、決策向量X進(jìn)行分塊處理，則有： 。 因此得： 。令非基變量的取值等于零，則得： 。一般稱： 為基 B下的基本解。 bNBXXNB ?))(,(NB NXBBX b 11 ?? ??bBX B 1??????????? ?01bBX43 三、基本解、基本可行解與可行基 ? 基本可行解：符合非負(fù)性要求的基本解，稱為基本可行解。 ? 可行基：基本可行解對(duì)應(yīng)的基，稱為可行基。 44 四、基本最優(yōu)解與最優(yōu)基 ? 基本最優(yōu)解：滿足目標(biāo)函數(shù)要求的基本解，稱為基本最優(yōu)解。 ? 最優(yōu)基：基本最優(yōu)解對(duì)應(yīng)的基，稱為最優(yōu)基。 45 線性規(guī)劃解之間的關(guān)系 ? 線性規(guī)劃解之間的關(guān)系： 可行解 基本解 非可行解 基本可行解 基本可行解 最優(yōu)解 46 五、退化基本可行解與退化基 ? 退化基本可行解：基本可行解中存在取零值的基變量，則稱該基本可行解為退化的基本可行解。 ? 退化基：退化的基本可行解對(duì)應(yīng)的基，稱為退化基。 47 六、線性規(guī)劃的幾何意義 ? 凸集：集合 C∈ En，從 C中任取兩點(diǎn) X、 Y，當(dāng) 0λ1時(shí)，仍有 λX+（ 1λ） Y∈ C，則稱 C為凸集。 凸集： 48 六、線性規(guī)劃的幾何意義 ? 凸集： 不是凸集： 49 六、線性規(guī)劃的幾何意義 ? 凸組合 設(shè) X1， X2， … ， Xk是 n維歐氏空間中的 k個(gè)點(diǎn) ， 若存在非負(fù)數(shù) λ1,λ2,… ,λk, 且 λ1+λ2+… +λk=1 ， 使得X=λ1X1+λ2X2+… +λKXK成立 ， 則稱 X是 X1，X2， … ， Xk的凸組合 。 如果 0＜ λ1,λ2,… ,λk＜ 1， 則稱 X是 X1， X2， … ， Xk的嚴(yán)格凸組合 。 50 六、線性規(guī)劃的幾何意義 ? 極點(diǎn) 假設(shè) C是凸集，若 C中不存在兩個(gè)不同的點(diǎn) X X2 ，使得 C中的點(diǎn) X可以表示為 X X2凸組合，則稱 X是 C中的極點(diǎn)。 51 七、線性規(guī)劃的基本定理 ? 線性規(guī)劃問題所有可行解組成的集合S= {X|AX=b,X≥0}是凸集。 ? 線性規(guī)劃問題的可行解 X是基本可行解的充要條件是 X的正分量對(duì)應(yīng)的約束系數(shù)矩陣的列向量是線性無關(guān)的。 ? X是線性規(guī)劃問題的基本可行解的充要條件是 X為可行域 S = {X|AX=b,X≥0} 的極點(diǎn)。 52 七、線性規(guī)劃的基本定理 ? 如果一個(gè)線性規(guī)劃問題存在可行解，則一定有基本可行解。 ? 若線性規(guī)劃問題存在最優(yōu)解，則一定存在最優(yōu)基本可行解。 ? 若線性規(guī)劃問題可行域有界，則最優(yōu)解一定在極點(diǎn)上取得到。 ? 線性規(guī)劃可行域的極點(diǎn)的個(gè)數(shù)是有限的。 53 線性規(guī)劃理論的小結(jié) ? 一般意義上說： （ 1）如果線性規(guī)劃問題有可行解，則一定有基本可行解。 （ 2）線性規(guī)劃問題如果有最優(yōu)解，則最優(yōu)解一定可以從基本可行解中找得到。 （ 3）由于基本可行解的個(gè)數(shù)有限，所以經(jīng)過有限次迭代，就一定能找到最優(yōu)解。 54 線性規(guī)劃理論的小結(jié) ? 從幾何意義上說： （ 1）線性規(guī)劃問題可行域中的每一個(gè)極點(diǎn)都對(duì)應(yīng)著一個(gè)基本可行解。 （ 2）由于最優(yōu)解必定要從基本可行解中尋找，所以所謂求解線性規(guī)劃問題，實(shí)際上就是比較極點(diǎn)處的目標(biāo)函數(shù)值的大小。 （ 3）極點(diǎn)的個(gè)數(shù)是有限的，那么只要經(jīng)過有限次尋找就一定能夠找到基本最優(yōu)解。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1