資源描述：
《線性規(guī)劃及其對偶問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、線性規(guī)劃及其對偶問題1線性規(guī)劃問題及其數(shù)學模型2線性規(guī)劃問題的圖解法3單純形法4對偶問題5EXCEL求解線性規(guī)劃6靈敏度分析1線性規(guī)劃問題及其數(shù)學模型(1)線性規(guī)劃問題例、生產(chǎn)組織與計劃問題A,B各生產(chǎn)多少,可獲最大利潤?可用資源煤勞動力倉庫AB123202單位利潤4050306024解:設產(chǎn)品A,B產(chǎn)量分別為變量x1，x2可以建立如下的數(shù)學模型：MaxZ=40x1+50x2x1+2x2?303x1+2x2?602x2?24x1，x2?0s.t目標函數(shù)約束條件可用資源煤勞動力倉庫AB123202單位利潤4050306024例某建筑設計院設計每萬ｍ２辦公建筑
2、和工業(yè)廠房需要的建筑師、結(jié)構(gòu)工程師、設備工程師和電氣工程師的平均人數(shù)列在表。問該院應如何安排設計任務，才能使設計費收入最大?專業(yè)建筑物建筑結(jié)構(gòu)設備電器設計費收入（萬元/萬ｍ２）辦公建筑532136工業(yè)廠房121220全院現(xiàn)有專業(yè)人數(shù)28261210解 設辦公建筑和工業(yè)廠房各承攬ｘ１、ｘ２萬ｍ２。根據(jù)題意maxZ＝36x1＋20x25x1＋x2≤28s.t3x1＋2x2≤282x1＋x2≤12x1＋2x2≤10x1、x2≥02.9m鋼筋架子100個，每個需用2.1m各1，原料長7.4m1.5m求：如何下料，使得殘余料頭最少。解：首先列出各種可能的下料方案；計
3、算出每個方案可得到的不同長度鋼筋的數(shù)量及殘余料頭長度；確定決策變量；根據(jù)下料目標確定目標函數(shù)；根據(jù)不同長度鋼筋的需要量確定約束方程。例、合理下料問題設按第i種方案下料的原材料為xi根組合方案123456782.9m211100002.1m021032101.5m10130234合計7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料長7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料頭0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m例、運輸問題工廠123庫存?zhèn)}121350222430庫334210需求40153
4、5運輸單價求：運輸費用最小的運輸方案。解：設xij為i倉庫運到j工廠的產(chǎn)品數(shù)量其中：i＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13=50x21+x22+x23=30x31+x32+x33=10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij?0s.t(2)線性規(guī)劃問題的特點決策變量：(x1…xn)T代表某一方案，決策者要考慮和控制的因素非負；目標函數(shù)：Z=?(x1…xn)為線性函數(shù)，求Z極大或極小;約束條件：可用線性
5、等式或不等式表示.具備以上三個要素的問題就稱為線性規(guī)劃問題。目標函數(shù)約束條件(3)線性規(guī)劃模型一般形式隱含的假設比例性：決策變量變化引起目標的改變量與決策變量改變量成正比可加性：每個決策變量對目標和約束的影響獨立于其它變量連續(xù)性：每個決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij,bi,cj為確定值2線性規(guī)劃問題的圖解法定義1：滿足約束(2)的X=(X1…Xn)T稱為線性規(guī)劃問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(1)的可行解稱為線性規(guī)劃問題的最優(yōu)解。例1MaxZ=40X1+50X2X1+2X2?303X1+2X2?602X2?24X1,X
6、2?0s.t解：(1)、確定可行域X1+2X2?303X1+2X2?602X2?24X1?0X2?02030100102030X2DABC2X2?24X1+2X2?303X1+2X2?60X1?0X2?0可行域(2)、求最優(yōu)解最優(yōu)解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C點：X1+2X2=303X1+2X2=600203010102030X1X2DABC最優(yōu)解Z=975可行解Z=0等值線例2、MaxZ=40X1+80X2X1+2X2?303X1+2X2?602X2?24X1,X2?0s
7、.t解：(1)、確定可行域與上例完全相同。(2)、求最優(yōu)解0203010102030DABC最優(yōu)解Z=1200最優(yōu)解：BC線段最優(yōu)解：BC線段B點：X(1)=(6,12)C點：X(2)=(15,7.5)X=?X(1)+(1-?)X(2)(0???1)MaxZ=1200X1615X2127.5X==?+(1-?)X1=6?+(1-?)·15X2=12?+(1-?)·7.5X1=15-9?X2=7.5+4.5?(0???1)例3、MaxZ=2X1+4X22X1+X2?8-2X1+X2?2X1,X2?0s.tZ=08246X240X1-2X1+X2?22X1+X
8、2?8X1?0X2?0可行域無界無有限最優(yōu)解無有限最優(yōu)解可行域無上
