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