優(yōu)化模型舉例教材課件

2023/7/20數(shù)學建模方法2023/7/20建立數(shù)學模型的方法層次分析法最小二乘法差分法定性理論法優(yōu)化法變分法回歸分析法機理分析法統(tǒng)計分析法聚類分析法主成分分析法馬爾科夫預測法系統(tǒng)分析法模糊數(shù)學法灰色系統(tǒng)法2023/7/20優(yōu)化模型2023/7/20優(yōu)化模型是中國大學生建模競賽常見的類型，占很大的比重。92年以來，優(yōu)化模型有：94年A題：“逢山開路”設計最短路徑。95年A題：“一個飛行管理問題”，線性規(guī)劃和非線性規(guī)劃模型。96年A題：“最優(yōu)捕魚策略”，以微分方程為基礎(chǔ)的優(yōu)化模型。2023/7/2096年B題：“洗衣節(jié)水問題”，以用水量為目標函數(shù)的優(yōu)化模型。97年A題：“零件的參數(shù)設計”，隨機優(yōu)化模型。97年B題：“截斷切割”，動態(tài)優(yōu)化模型。98年A題：“投資的收益和風險”，雙目標優(yōu)化模型。98年B題：“災情巡視的最佳路線”，0-1線性

規(guī)劃模型。2023/7/2099年A題：“自動化車床管理”，雙參數(shù)規(guī)劃模型。99年B題：“鉆井布局”，非線性混合整數(shù)規(guī)劃模型。00年B題：“鋼管訂購和運輸”，二次規(guī)劃模型。01年B題：“公交車調(diào)度”，雙目標規(guī)劃模型。02年A題：“車燈線光源的優(yōu)化設計”，規(guī)劃模型。2023/7/2003年B題：“露天礦生產(chǎn)的車輛安排”，非線性規(guī)劃模型。04年B題：“電力市場的輸電阻塞管理”，雙目標線性規(guī)劃模型。05年B題：“DVD在現(xiàn)租賃”，0-1規(guī)劃模型。06年A題：“出版社的資源優(yōu)化配置”，線性規(guī)劃模型。2023/7/20（一）優(yōu)化模型的數(shù)學描述下的最大值或最小值，其中設計變量（決策變量）目標函數(shù)將一個優(yōu)化問題用數(shù)學式子來描述，即求函數(shù)在約束條件和可行域2023/7/20“受約束于”之意2023/7/20（二）優(yōu)化模型的分類1.根據(jù)是否存在約束條件有約束問題和無約束問題。2.根據(jù)設計變量的性質(zhì)靜態(tài)問題和動態(tài)問題。3.根據(jù)目標函數(shù)和約束條件表達式的性質(zhì)線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標規(guī)劃等。2023/7/20（1）非線性規(guī)劃目標函數(shù)和約束條件中，至少有一個非線性函數(shù)。2023/7/20（2）線性規(guī)劃（LP）

目標函數(shù)和所有的約束條件都是設計變量的線性函數(shù)。2023/7/20（3）二次規(guī)劃問題目標函數(shù)為二次函數(shù)，約束條件為線性約束2023/7/205.根據(jù)變量具有確定值還是隨機值

確定規(guī)劃和隨機規(guī)劃。4.根據(jù)設計變量的允許值整數(shù)規(guī)劃（0-1規(guī)劃）和實數(shù)規(guī)劃。2023/7/20（三）建立優(yōu)化模型的一般步驟1.確定設計變量和目標變量；2.確定目標函數(shù)的表達式；3.尋找約束條件。2023/7/20最優(yōu)捕食策略運輸問題點菜問題旅行商問題（四）線性規(guī)劃模型舉例2023/7/20實例1最優(yōu)捕食者策略

假設存在一種捕食者，穴居A處，在B和C處有兩個食物源X、Y。捕食者從巢穴A到區(qū)域B和C帶回一單位的食物所需的時間估計為2分鐘和3分鐘。捕食者在區(qū)域B平均花2分鐘捕獲一單位食物X，而在區(qū)域C只花1分鐘就捕獲一單位食物Y。一單位X所產(chǎn)生的熱量估計為25焦耳，一單位Y所產(chǎn)生的熱量估計為30焦耳。假設捕食者每天不可超過120分鐘用于從巢穴到食物區(qū)來回行走，同時每天不可能花80分鐘以上搜尋食物。估計捕食者每天能獲得的最大熱量值是多少？2023/7/20一單位實物行走時間(分鐘)捕獲時間(分鐘)熱量(焦耳)X2225Y3130

假設捕食者每天能得到x單位的食物X和y單位的食物Y，則每天獲得的熱量值為2023/7/20xyo2x+y=802x+3y=12060404080P(30,20)U=25x+30yU=25*30+30*20=1350焦耳圖解法2023/7/20編制Matlab程序：f=[-25,-30];Aeq=[];Beq=[];A=[2,3;2,1];B=[120;80];xm=[0;0];xM=[Inf;Inf];ff=optimset;ff.Tolx=1e-15;ff.TolFun=1e-20;TolCon=1e-20;[x,f_opt,key,c]=linprog(f,A,B,Aeq,Beq,xm,xM,[0;0],ff)2023/7/20設有某物資從m個發(fā)點A1,A2,…,Am輸送到n個收點B1,B2,…,Bn，其中每個發(fā)點發(fā)出量分別為每個收點輸入量分別為，并且滿足從發(fā)點A到收點B的距離（或單位運費）是已知的，設為。一個調(diào)運方案主要由一組從發(fā)點到收點的輸送量來描述。問題：尋求一個調(diào)運方案，使總運輸費用達到最小。實例2運輸問題2023/7/20B1B2….BnA1A2Ama1a2amb1b2….bn…..…..X11X12…..X1nX21X22….X2nXm1Xm2…..Xmn收點發(fā)點2023/7/20總的費用A1的總費用A2的總費用2023/7/20s.t.數(shù)學模型求解：單純形方法。2023/7/20實例3點菜問題

我們在餐館中點菜，需要包含某些營養(yǎng)成份，但同時又希望總價格最低。下表是這個餐館的部分菜單，請你提供合理的選菜方案。序號菜單價格(元)蛋白質(zhì)淀粉維生素礦物質(zhì)1菜肉蛋卷1810112炒豬肝21.501013色拉12.500104紅燒排骨2310005咖喱土豆10.501006清湯全雞3210012023/7/20建模設xi

表示點序號為i的菜，則目標函數(shù)：約束條件：2023/7/20注：0-1規(guī)劃問題可用Matlab求解（薛定宇PP189），對于簡單問題亦可使用窮舉法。下面用Matlab軟件，求得結(jié)果：f=[18,21.5,12.5,23.0,10.5,32.0];Aeq=[];Beq=[];A=[-100-10-1;0-100-10;-10-1000;-1-1000-1;];B=[-1;-1;-1;-1];x=bintprog(f,A,B,[],[])‘x=100010;fopt=28.52023/7/20進一步考慮如果至少點四個不同的菜，結(jié)果又如何？2023/7/20利用matlab

軟件，得f=[18,21.5,12.5,23.0,10.5,32.0];Aeq=[];Beq=[];A=[-100-10-1;0-100-10;-10-1000;-1-1000-1;];[-1-1-1-1-1-1];B=[-1;-1;-1;-1;-4];x=bintprog(f,A,B,[],[])‘x=111010Fopt=62.52023/7/20點菜價格（元）點菜價格（元）1,2,3,6844,5,3,267.54,2,1,694.54,5,3,6784,5,1,2736,5,1,2824,5,1,683.56,5,3,1734,5,3,1646,5,3,276.51,2,3,562.5也可利用窮舉法，得2023/7/20實例4旅行商問題(TravellingSalemanProblem）TSP

某商人由一城市出發(fā)，擬去已確定的n個城市推銷產(chǎn)品，最后回到出發(fā)城市。設任意兩城市間的距離都是已知的，要求找出一條每個城市都只到一次的旅行線路，使其總旅程最短。2023/7/20建模TSP又稱為貨郎擔問題。給這些城市編號。出發(fā)城市為0，擬訪問城市分別為1,2,…,n問題就轉(zhuǎn)化為：其中為城市到的距離，最小。求一個的排序使得2023/7/20TSP的數(shù)學規(guī)劃形式：表示進入且僅進入城j一次;表示離開且僅離開城i一次;保證連通性。其中表示若該旅行商在訪問城i后接著訪問城j，則令，否則令（P）2023/7/20定理：0-1規(guī)劃問題(P)即為旅行商問題。證明：將n+1個城市看作頂點，可以作為一個完全圖（即任意兩點均有邊相連圖），{1,2,…,n}的每一排序?qū)趫D中一個由0點出發(fā)經(jīng)每一頂點一次最后回到0點的圖?，F(xiàn)在只需證明是(P)的可行解的充分必要條件對應的邊組成完全圖中的一個圈。2023/7/20(P)的可行解必構(gòu)成完全圖中的若干回路（由約束條件中的前兩個得知）。假設不然，設城構(gòu)成不過0的回路由第三個條件得：上式兩邊相加得，矛盾?，F(xiàn)證明這些回路必經(jīng)過0，從而只能是唯一的回路，即完全圖中的一個圈（Hamilton圈）。2023/7/20反之，對每一由城0出發(fā)過每城一次回到城0的圈均可找到一組，使得條件3成立。事實上，可如下取之?，F(xiàn)令，若城i為第k個訪問的城市，則令

，于是，當時，，從而成立，證畢。2023/7/20模型求解1窮舉法的不同排序有個，當n稍大時，很難找出最佳答案。這是個NP-完全問題。2近似算法貪婪算法西德曾對一個有318個點的問題找到了最優(yōu)方案。3利用數(shù)學軟件2023/7/20

一個送報員從送報中心出發(fā)到五個小區(qū)送報，最后要回到送報中心。送報中心到各小區(qū)的距離及各小區(qū)間的距離均已知（見表1），問送報員應按怎樣的線路行駛較好？（距離單位為千米）送報線路安排2023/7/20表1送報中心及各小區(qū)間的距離01234500745861703109142430591035105014948991407561410970起終2023/7/2001234500745861703109142430591035105014948991407561410970貪婪算法送報中心及五個小區(qū)分別用0，1，2，3，4，5來記。算法的中心思想：每次尋找最小距離。起終2023/7/2001234500745861703109142430591035105014948991407561410970起終2132023/7/2001234500745861703109142430591035105014948991407561410970起終021433052023/7/200214330501234500745861703109142430591035105014948991407561410970起終4572023/7/200214330501234500745861703109142430591035105014948991407561410970起終4572023/7/200214330501234500745861703109142430591035105014948991407561410970起終457992023/7/2001234500745861703109142430591035105014948991407561410970起終0214530439795總距離：37千米。2023/7/20應用例子

某類工件在加工時需在一些指定的位置上鉆孔。鉆頭從初始位置出發(fā)，到各處鉆孔，最后回到初始位置，以便繼續(xù)對下一工件加工。問應如何安排鉆孔的次序，使鉆頭在加工過程中移動的總距離最小。2023/7/20報童的訣竅問題：報童每天清晨從報社購進報紙零售，晚上將沒有賣掉的報紙退回。設報紙每份的購進價為b，零售價為a，退回價為c，假設a>b>c。即報童售出一份報紙賺a-b，退回一份賠b-c。報童每天購進報紙?zhí)?，賣不完會賠錢；購進太少，不夠賣會少掙錢。試為報童籌劃一下每天購進報紙的數(shù)量，以獲得最大收入。2023/7/201.確定設計變量和目標變量2.確定目標函數(shù)的表達式每天的總收入為目標變量每天購進報紙的份數(shù)為設計變量3.尋找約束條件尋找設計變量與目標變量之間的關(guān)系設計變量所受的限制問題分析2023/7/20若每天購進0份，則收入為0。若每天購進1份，售出，則收入為a-b。退回，則收入為–(b-c)。若每天購進2份，售出1份，則收入為a-b–(b-c)

。退回，則收入為–2(b-c)。售出2份，則收入為2(a-b)

。收入還與每天的需求量有關(guān)，而需求量是隨機變量則收入也是隨機變量，通常用均值，即期望表示。2023/7/20數(shù)學期望離散型隨機變量X的概率分布為則隨機變量X的數(shù)學期望值為連續(xù)型隨機變量X的概率密度函數(shù)為則隨機變量X的數(shù)學期望值為期望值反映了隨機變量取值的“平均”意義！2023/7/201設每天購進n份，日平均收入為G(n)3每天需求量為r的概率f(r),r=0,1,2…2售出一份賺a-b；退回一份賠b-c模型假設與符號說明2023/7/20求n使G(n)最大每天的收入函數(shù)記為U(n)，則收入函數(shù)的期望值為建模2023/7/20將r視為連續(xù)變量模型求解2023/7/20使報童日平均收入達到最大的購進量應滿足上式。因為2023/7/20售完的概率因為當購進份報紙時，是需求量不超過的概率是需求量超過的概率售不完的概率上式意義為：購進的份數(shù)之比，恰好等于賣出一份賺的錢與退回一份賠的錢之比。應該使賣不完與賣完的概率2023/7/20根據(jù)需求量的概率密度的圖形可以確定購進量在圖中用分別表示曲線下的兩塊面積，則Onr當報童與報社簽訂的合同使報童每份賺錢與賠錢之比越大時，報童購進的份數(shù)就應該越多。結(jié)論求解的幾何意義2023/7/20注意求解技巧：連續(xù)化建模方法：從特殊到到一般歸納抽象1998年B題災情巡視路線單旅行商到多旅行商1999年B題鉆井布局網(wǎng)格的平行移動到旋轉(zhuǎn)運動2000年B題鋼管的訂購與運輸線形到樹形2000年C題飛越北極球形到橢球形人口模型，戰(zhàn)爭模型隨機變量的目標函數(shù)：期望值航空公司的超額訂票模型2023/7/20社會熱點問題

2023/7/20經(jīng)濟發(fā)展問題2023/7/20環(huán)保問題2023/7/20新一輪全國性房價上漲已經(jīng)開始，土地也隨之成了搶手貨。令地產(chǎn)商為難的是，拿不到地，很可能會被淘汰出局，但多拿了地，又意味著要承擔諸多風險。

房價問題2023/7/20

股票問題

依照機構(gòu)樂觀的分析，2007年股票市場整體機會大于風險，但股指整體在高位運行，市場預期震蕩幅度加大。2023/7/20煤礦管理問題2023/7/20高校本科評估就是一場鬧劇高校

高校本科評估問題2023/7/20中國石油價格將走向何方?

石油價格問題2023/7/20洞庭湖鼠患問題20億田鼠洞庭“跑馬圈地”2023/7/20某服務部一周中的每天需要不同數(shù)目的雇員：

周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人?，F(xiàn)規(guī)定應聘者需連續(xù)工作五天，試確定聘用方案，即周一到周日每天聘用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少。課后作業(yè)1

服務員的聘用問題2023/7/20優(yōu)化問題決策變量：周一到周日每天聘請的人數(shù)，記為目標函數(shù)：聘用總?cè)藬?shù)約束條件：每天需要的人數(shù)，由于每人連續(xù)工作5天，所以周一的雇員應是周四到周一聘用的，按照需要至少有50人，于是2023/7/20優(yōu)化模型2023/7/20求解模型用LINDO求解

美國芝加哥大學的linusSchrage教授于1980年前后開發(fā)的一套專門用于求解優(yōu)化問題的軟件包。包括4種主要產(chǎn)品：LINDO，LINGO，LINDOAPI，Wath’sBest!LINDO：linearInteractiveandDiscreteOptimizer.交互式的線性和離散優(yōu)化求解器LINDGO：linearInteractiveandGeneralOptimizer.交互式的線性和通用優(yōu)化求解器用以求解線性規(guī)劃（LP）和二次規(guī)劃（QP）問題用以求解非線性規(guī)劃問題2023/7/20用LINDO求解TITLE服務員聘用問題的LINDO模型MINx1+x2+x3+x4+x5+x6+x7SUBJECTTOMON)x1++x4+x5+x6+x7>=50TUE)x1+x2++x5+x6+x7>=50WED)x1+x2+x3++x6+x7>=50THU)x1+x2+x3+x4++x7>=50FRI)x1+x2+x3+x4+x5>=80SAT)x2+x3+x4+x5+x6>=90SUN)x3+x4+x5+x6+x7>=90ENDGIN7GeneralInteger求解模型2023/7/20結(jié)果輸出主要結(jié)果OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUE

x10.000000x24.000000x340.000000x42.000000