線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題

《線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題1線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型2線(xiàn)性規(guī)劃問(wèn)題的圖解法3單純形法4對(duì)偶問(wèn)題5EXCEL求解線(xiàn)性規(guī)劃6靈敏度分析1線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(1)線(xiàn)性規(guī)劃問(wèn)題例、生產(chǎn)組織與計(jì)劃問(wèn)題A,B各生產(chǎn)多少,可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉(cāng)庫(kù)AB123202單位利潤(rùn)4050306024解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1，x2可以建立如下的數(shù)學(xué)模型：MaxZ=40x1+50x2x1+2x2?303x1+2x2?602x2?24x1，x2?0s.t目標(biāo)函數(shù)約束條件可用資源煤勞動(dòng)力倉(cāng)庫(kù)AB123202單

2、位利潤(rùn)4050306024例某建筑設(shè)計(jì)院設(shè)計(jì)每萬(wàn)ｍ２辦公建筑和工業(yè)廠(chǎng)房需要的建筑師、結(jié)構(gòu)工程師、設(shè)備工程師和電氣工程師的平均人數(shù)列在表。問(wèn)該院應(yīng)如何安排設(shè)計(jì)任務(wù)，才能使設(shè)計(jì)費(fèi)收入最大?專(zhuān)業(yè)建筑物建筑結(jié)構(gòu)設(shè)備電器設(shè)計(jì)費(fèi)收入（萬(wàn)元/萬(wàn)ｍ２）辦公建筑532136工業(yè)廠(chǎng)房121220全院現(xiàn)有專(zhuān)業(yè)人數(shù)28261210解　設(shè)辦公建筑和工業(yè)廠(chǎng)房各承攬ｘ１、ｘ２萬(wàn)ｍ２。根據(jù)題意maxZ＝36x1＋20x25x1＋x2≤28s.t3x1＋2x2≤282x1＋x2≤12x1＋2x2≤10x1、x2≥02.9m鋼筋架子

3、100個(gè)，每個(gè)需用2.1m各1，原料長(zhǎng)7.4m1.5m求：如何下料，使得殘余料頭最少。解：首先列出各種可能的下料方案；計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余料頭長(zhǎng)度；確定決策變量；根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)；根據(jù)不同長(zhǎng)度鋼筋的需要量確定約束方程。例、合理下料問(wèn)題設(shè)按第i種方案下料的原材料為xi根組合方案123456782.9m211100002.1m021032101.5m10130234合計(jì)7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料長(zhǎng)7.4m7.4m7.4m7.4m

4、7.4m7.4m7.4m7.4m料頭0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m例、運(yùn)輸問(wèn)題工廠(chǎng)123庫(kù)存?zhèn)}121350222430庫(kù)334210需求401535運(yùn)輸單價(jià)求：運(yùn)輸費(fèi)用最小的運(yùn)輸方案。解：設(shè)xij為i倉(cāng)庫(kù)運(yùn)到j(luò)工廠(chǎng)的產(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=40x

5、12+x22+x32=15x13+x23+x33=35xij?0s.t(2)線(xiàn)性規(guī)劃問(wèn)題的特點(diǎn)決策變量：(x1…xn)T代表某一方案，決策者要考慮和控制的因素非負(fù)；目標(biāo)函數(shù)：Z=?(x1…xn)為線(xiàn)性函數(shù)，求Z極大或極小;約束條件：可用線(xiàn)性等式或不等式表示.具備以上三個(gè)要素的問(wèn)題就稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題。目標(biāo)函數(shù)約束條件(3)線(xiàn)性規(guī)劃模型一般形式隱含的假設(shè)比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比可加性：每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞窟B續(xù)性：每個(gè)決策變量取連續(xù)值確定性：線(xiàn)性

6、規(guī)劃中的參數(shù)aij,bi,cj為確定值2線(xiàn)性規(guī)劃問(wèn)題的圖解法定義1：滿(mǎn)足約束(2)的X=(X1…Xn)T稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的可行解，全部可行解的集合稱(chēng)為可行域。定義2：滿(mǎn)足(1)的可行解稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解。例1MaxZ=40X1+50X2X1+2X2?303X1+2X2?602X2?24X1,X2?0s.t解：(1)、確定可行域X1+2X2?303X1+2X2?602X2?24X1?0X2?02030100102030X2DABC2X2?24X1+2X2?303X1+2X2?60X1?0X2?

7、0可行域(2)、求最優(yōu)解最優(yōu)解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C點(diǎn)：X1+2X2=303X1+2X2=600203010102030X1X2DABC最優(yōu)解Z=975可行解Z=0等值線(xiàn)例2、MaxZ=40X1+80X2X1+2X2?303X1+2X2?602X2?24X1,X2?0s.t解：(1)、確定可行域與上例完全相同。(2)、求最優(yōu)解0203010102030DABC最優(yōu)解Z=1200最優(yōu)解：BC線(xiàn)段最優(yōu)解：BC線(xiàn)段

8、B點(diǎn)：X(1)=(6,12)C點(diǎn)：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+X2?8X1?0X2?0可行域無(wú)界無(wú)有限最優(yōu)解無(wú)有限最優(yōu)解可行域無(wú)上