優(yōu)化建模與lingo第01章62500

《優(yōu)化建模與lingo第01章62500》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、優(yōu)化建模與LINDO/LINGO軟件第1章　　引　　言［原書相關(guān)信息］謝金星,薛毅編著,清華大學(xué)出版社,2005年7月第1版.http://faculty.math.tsinghua.edu.cn/~jxie/lindo內(nèi)容提要1.優(yōu)化模型的基本概念2.優(yōu)化問題的建模實(shí)例3.LINDO/LINGO軟件簡(jiǎn)介1.優(yōu)化模型的基本概念最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會(huì)生活中經(jīng)常遇到的問題,如:優(yōu)化模型和算法的重要意義結(jié)構(gòu)設(shè)計(jì)資源分配生產(chǎn)計(jì)劃運(yùn)輸方案解決優(yōu)化問題的手段經(jīng)驗(yàn)積累，主觀判斷作試驗(yàn)，比優(yōu)劣建立數(shù)學(xué)模型，

2、求解最優(yōu)策略最優(yōu)化:在一定條件下，尋求使目標(biāo)最大(小)的決策優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件約束條件決策變量?jī)?yōu)化問題的一般形式無約束優(yōu)化(沒有約束)與約束優(yōu)化(有約束)可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值)目標(biāo)函數(shù)局部最優(yōu)解與整體最優(yōu)解局部最優(yōu)解(LocalOptimalSolution,如x1)整體最優(yōu)解(GlobalOptimalSolution,如x2)x*f(x)x1x2o優(yōu)化模型的簡(jiǎn)單分類線性規(guī)劃(LP)目標(biāo)和約束均為線性函數(shù)非線性規(guī)劃(NLP)目標(biāo)或約束中存在非線性函數(shù)二次規(guī)劃(QP

3、)目標(biāo)為二次函數(shù)、約束為線性整數(shù)規(guī)劃(IP)決策變量(全部或部分)為整數(shù)整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP)純整數(shù)規(guī)劃(PIP),混合整數(shù)規(guī)劃(MIP)一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學(xué)規(guī)劃優(yōu)化模型的簡(jiǎn)單分類和求解難度優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃問題求解的難度增加2.優(yōu)化問題的建模實(shí)例1桶牛奶3公斤A112小時(shí)8小時(shí)4公斤A2或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若

4、買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天：線性規(guī)劃模型－例1.1:奶制品生產(chǎn)計(jì)劃1桶牛奶3公斤A112小時(shí)8小時(shí)4公斤A2或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1x2桶牛奶生產(chǎn)A2獲利24×3x1獲利16×4x2原料供應(yīng)勞動(dòng)時(shí)間加工能力決策變量目標(biāo)函數(shù)每天獲利約束條件非負(fù)約束線性規(guī)劃模型(LP)時(shí)間480小時(shí)至多加工100公斤A150桶牛奶每天模型分析與假設(shè)比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對(duì)約束

5、條件的“貢獻(xiàn)”與xi取值成正比xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān)xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線性規(guī)劃模型模型求解圖解法x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù)Z=0Z=2400Z=3600z=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解

6、目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。求解LP的基本思想思路：從可行域的某一頂點(diǎn)開始，只需在有限多個(gè)頂點(diǎn)中一個(gè)一個(gè)找下去，一定能得到最優(yōu)解。LP的約束和目標(biāo)函數(shù)均為線性函數(shù)2維可行域線段組成的凸多邊形目標(biāo)函數(shù)等值線為直線最優(yōu)解凸多邊形的某個(gè)頂點(diǎn)n維超平面組成的凸多面體等值線是超平面凸多面體的某個(gè)頂點(diǎn)LP的通常解法是單純形法(G.B.Dantzig,1947)內(nèi)點(diǎn)算法(Interiorpointmethod)20世紀(jì)80年代人們提出的一類

7、新的算法——內(nèi)點(diǎn)算法也是迭代法，但不再從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)換到另一個(gè)頂點(diǎn)，而是直接從可行域的內(nèi)部逼近最優(yōu)解。LP其他算法有效集(ActiveSet)方法LP是QP的特例（只需令所有二次項(xiàng)為零即可）可以用QP的算法解QP(如:有效集方法)線性規(guī)劃模型的解的幾種情況線性規(guī)劃問題有可行解(Feasible)無可行解（Infeasible）有最優(yōu)解（Optimal）無最優(yōu)解(Unbounded)假設(shè)A產(chǎn)銷平衡假設(shè)Bp隨x(兩種牌號(hào))增加而減小，呈線性關(guān)系某廠生產(chǎn)兩個(gè)牌號(hào)的同一種產(chǎn)品，如何確定產(chǎn)量使利潤(rùn)最大二次規(guī)劃模型－

8、例1.2：產(chǎn)銷計(jì)劃問題目標(biāo)利潤(rùn)最大=（100-x1-0.1x2-2）x1+（280-0.2x1-2x2-3）x2=98x1+277x2－x12－0.3x1x2－2x22約束x1+x2≤100x1≤2x2x1,x2≥0二次規(guī)劃模型(QP)若還要求產(chǎn)量為整數(shù)，則是整數(shù)二次規(guī)劃模型(IQP)非線性規(guī)劃模型－例1.3：選址問題某公司有6個(gè)建筑工地，位置坐標(biāo)為(ai,bi)(單位：公里),水泥日