優(yōu)化模型舉例

2023/11/22數(shù)學(xué)建模方法2023/11/22建立數(shù)學(xué)模型的方法層次分析法最小二乘法差分法定性理論法優(yōu)化法變分法回歸分析法機(jī)理分析法統(tǒng)計分析法聚類分析法主成分分析法馬爾科夫猜測法系統(tǒng)分析法模糊數(shù)學(xué)法灰色系統(tǒng)法2023/11/22優(yōu)化模型2023/11/22優(yōu)化模型是中國大學(xué)生建模競賽常見的類型，占很大的比重。92年以來，優(yōu)化模型有：94年A題：“逢山開路”設(shè)計最短路徑。95年A題：“一個飛行治理問題”，線性規(guī)劃和非線性規(guī)劃模型。96年A題：“最優(yōu)捕魚策略”，以微分方程為根底的優(yōu)化模型。2023/11/2296年B題：“洗衣節(jié)水問題”，以用水量為目標(biāo)函數(shù)的優(yōu)化模型。97年A題：“零件的參數(shù)設(shè)計”，隨機(jī)優(yōu)化模型。97年B題：“截斷切割”，動態(tài)優(yōu)化模型。98年A題：“投資的收益和風(fēng)險”，雙目標(biāo)優(yōu)化模型。98年B題：“災(zāi)情巡察的最正確路線”，0-1線性規(guī)劃模型。2023/11/2299年A題：“自動化車床治理”，雙參數(shù)規(guī)劃模型。99年B題：“鉆井布局”，非線性混合整數(shù)規(guī)劃模型。00年B題：“鋼管訂購和運(yùn)輸”，二次規(guī)劃模型。01年B題：“公交車調(diào)度”，雙目標(biāo)規(guī)劃模型。02年A題：“車燈線光源的優(yōu)化設(shè)計”，規(guī)劃模型。2023/11/2203年B題：“露天礦生產(chǎn)的車輛安排”，非線性規(guī)劃模型。04年B題：“電力市場的輸電堵塞治理”，雙目標(biāo)線性規(guī)劃模型。05年B題：“DVD在現(xiàn)租賃”，0-1規(guī)劃模型。06年A題：“出版社的資源優(yōu)化配置”，線性規(guī)劃模型。2023/11/22〔一〕優(yōu)化模型的數(shù)學(xué)描述下的最大值或最小值，其中設(shè)計變量（決策變量）目標(biāo)函數(shù)將一個優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù)在約束條件和可行域2023/11/22“受約束于”之意2023/11/22〔二〕優(yōu)化模型的分類1.依據(jù)是否存在約束條件有約束問題和無約束問題。2.依據(jù)設(shè)計變量的性質(zhì)靜態(tài)問題和動態(tài)問題。3.依據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì)線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等。2023/11/22〔1〕非線性規(guī)劃目標(biāo)函數(shù)和約束條件中，至少有一個非線性函數(shù)。2023/11/22〔2〕線性規(guī)劃〔LP〕目標(biāo)函數(shù)和全部的約束條件都是設(shè)計變量的線性函數(shù)。2023/11/22〔3〕二次規(guī)劃問題目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束2023/11/225.依據(jù)變量具有確定值還是隨機(jī)值確定規(guī)劃和隨機(jī)規(guī)劃。4.依據(jù)設(shè)計變量的允許值整數(shù)規(guī)劃〔0-1規(guī)劃〕和實(shí)數(shù)規(guī)劃。2023/11/22〔三〕建立優(yōu)化模型的一般步驟1.確定設(shè)計變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；3.查找約束條件。2023/11/22最優(yōu)捕食策略運(yùn)輸問題點(diǎn)菜問題旅行商問題〔四〕線性規(guī)劃模型舉例2023/11/22實(shí)例1最優(yōu)捕食者策略假設(shè)存在一種捕食者，穴居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焦耳。假設(shè)捕食者每天不行超過120分鐘用于從巢穴到食物區(qū)來回行走，同時每天不行能花80分鐘以上搜尋食物。估量捕食者每天能獲得的最大熱量值是多少？2023/11/22一單位實(shí)物行走時間(分鐘)捕獲時間(分鐘)熱量(焦耳)X2225Y3130

假設(shè)捕食者每天能得到x單位的食物X和y單位的食物Y，則每天獲得的熱量值為2023/11/22xyo2x+y=802x+3y=12060404080P(30,20)U=25x+30yU=25*30+30*20=1350焦耳圖解法2023/11/22編制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/11/22設(shè)有某物資從m個發(fā)點(diǎn)A1,A2,…,Am輸送到n個收點(diǎn)B1,B2,…,Bn，其中每個發(fā)點(diǎn)發(fā)出量分別為每個收點(diǎn)輸入量分別為，并且滿足從發(fā)點(diǎn)A到收點(diǎn)B的距離〔或單位運(yùn)費(fèi)〕是的，設(shè)為。一個調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn)到收點(diǎn)的輸送量來描述。問題：尋求一個調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用到達(dá)最小。實(shí)例2運(yùn)輸問題2023/11/22B1B2….BnA1A2Ama1a2amb1b2….bn…..…..X11X12…..X1nX21X22….X2nXm1Xm2…..Xmn收點(diǎn)發(fā)點(diǎn)2023/11/22總的費(fèi)用A1的總費(fèi)用A2的總費(fèi)用2023/11/22s.t.數(shù)學(xué)模型求解：單純形方法。2023/11/22實(shí)例3點(diǎn)菜問題我們在餐館中點(diǎn)菜，需要包含某些養(yǎng)分成份，但同時又希望總價格最低。下表是這個餐館的局部菜單，請你供給合理的選菜方案。序號菜單價格(元)蛋白質(zhì)淀粉維生素礦物質(zhì)1菜肉蛋卷1810112炒豬肝21.501013色拉12.500104紅燒排骨2310005咖喱土豆10.501006清湯全雞3210012023/11/22建模設(shè)xi表示點(diǎn)序號為i的菜，則目標(biāo)函數(shù)：約束條件：2023/11/22注：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/11/22進(jìn)一步考慮假設(shè)至少點(diǎn)四個不同的菜，結(jié)果又如何？2023/11/22利用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/11/22點(diǎn)菜價格（元）點(diǎn)菜價格（元）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/11/22實(shí)例4旅行商問題(TravellingSalemanProblem〕TSP某商人由一城市動身，擬去已確定的n個城市推銷產(chǎn)品，最終回到動身城市。設(shè)任意兩城市間的距離都是的，要求找出一條每個城市都只到一次的旅行線路，使其總旅程最短。2023/11/22建模TSP又稱為貨郎擔(dān)問題。給這些城市編號。動身城市為0，擬訪問城市分別為1,2,…,n問題就轉(zhuǎn)化為：其中為城市到的距離，最小。求一個的排序使得2023/11/22TSP的數(shù)學(xué)規(guī)劃形式：表示進(jìn)入且僅進(jìn)入城j一次;表示離開且僅離開城i一次;保證連通性。其中表示假設(shè)該旅行商在訪問城i后接著訪問城j，則令，否則令〔P〕2023/11/22定理：0-1規(guī)劃問題(P)即為旅行商問題。證明：將n+1個城市看作頂點(diǎn)，可以作為一個完全圖〔即任意兩點(diǎn)均有邊相連圖〕，{1,2,…,n}的每一排序?qū)?yīng)于圖中一個由0點(diǎn)動身經(jīng)每一頂點(diǎn)一次最終回到0點(diǎn)的圖。現(xiàn)在只需證明是(P)的可行解的充分必要條件對應(yīng)的邊組成完全圖中的一個圈。2023/11/22(P)的可行解必構(gòu)成完全圖中的假設(shè)干回路〔由約束條件中的前兩個得知〕。假設(shè)不然，設(shè)城構(gòu)成不過0的回路由第三個條件得：上式兩邊相加得，沖突?，F(xiàn)證明這些回路必經(jīng)過0，從而只能是唯一的回路，即完全圖中的一個圈〔Hamilton圈〕。2023/11/22反之，對每一由城0動身過每城一次回到城0的圈均可找到一組，使得條件3成立。事實(shí)上，可如下取之?，F(xiàn)令，假設(shè)城i為第k個訪問的城市，則令，于是，當(dāng)時，，從而成立，證畢。2023/11/22模型求解1窮舉法的不同排序有個，當(dāng)n稍大時，很難找出最正確答案。這是個NP-完全問題。2近似算法貪欲算法西德曾對一個有318個點(diǎn)的問題找到了最優(yōu)方案。3利用數(shù)學(xué)軟件2023/11/22一個送報員從送報中心動身到五個小區(qū)送報，最終要回到送報中心。送報中心到各小區(qū)的距離及各小區(qū)間的距離均〔見表1〕，問送報員應(yīng)按怎樣的線路行駛較好？〔距離單位為千米〕送報線路安排2023/11/22表1送報中心及各小區(qū)間的距離01234500745861703109142430591035105014948991407561410970起終2023/11/2201234500745861703109142430591035105014948991407561410970貪欲算法送報中心及五個小區(qū)分別用0，1，2，3，4，5來記。算法的中心思想：每次查找最小距離。起終2023/11/2201234500745861703109142430591035105014948991407561410970起終2132023/11/2201234500745861703109142430591035105014948991407561410970起終021433052023/11/220214330501234500745861703109142430591035105014948991407561410970起終4572023/11/220214330501234500745861703109142430591035105014948991407561410970起終4572023/11/220214330501234500745861703109142430591035105014948991407561410970起終457992023/11/2201234500745861703109142430591035105014948991407561410970起終0214530439795總距離：37千米。2023/11/22應(yīng)用例子某類工件在加工時需在一些指定的位置上鉆孔。鉆頭從初始位置動身，到各處鉆孔，最終回到初始位置，以便連續(xù)對下一工件加工。問應(yīng)如何安排鉆孔的次序，使鉆頭在加工過程中移動的總距離最小。2023/11/22報童的訣竅問題：報童每天早晨從報社購進(jìn)報紙零售，晚上將沒有賣掉的報紙退回。設(shè)報紙每份的購進(jìn)價為b，零售價為a，退回價為c，假設(shè)a>b>c。即報童售出一份報紙賺a-b，退回一份賠b-c。報童每天購進(jìn)報紙?zhí)啵u不完會賠錢；購進(jìn)太少，不夠賣會少掙錢。試為報童籌劃一下每天購進(jìn)報紙的數(shù)量，以獲得最大收入。2023/11/221.確定設(shè)計變量和目標(biāo)變量2.確定目標(biāo)函數(shù)的表達(dá)式每天的總收入為目標(biāo)變量每天購進(jìn)報紙的份數(shù)為設(shè)計變量3.查找約束條件查找設(shè)計變量與目標(biāo)變量之間的關(guān)系設(shè)計變量所受的限制問題分析2023/11/22假設(shè)每天購進(jìn)0份，則收入為0。假設(shè)每天購進(jìn)1份，售出，則收入為a-b。退回，則收入為–(b-c)。假設(shè)每天購進(jìn)2份，售出1份，則收入為a-b–(b-c)

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

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

2023/11/22經(jīng)濟(jì)進(jìn)展問題2023/11/22環(huán)保問題2023/11/22新一輪全國性房價上漲已經(jīng)開頭，土地也隨之成了搶手貨。令地產(chǎn)商犯難的是，拿不到地，很可能會被淘汰出局，但多拿了地，又意味著要擔(dān)當(dāng)諸多風(fēng)險。房價問題2023/11/22股票問題依照機(jī)構(gòu)樂觀的分析，2023年股票市場整體時機(jī)大于風(fēng)險，但股指整體在高位運(yùn)行，市場預(yù)期震蕩幅度加大。2023/11/22煤礦治理問題2023/11/22高校本科評估就是一場鬧劇高校

高校本科評估問題2023/11/22價格將走向何方?石油價格問題2023/11/22洞庭湖鼠患問題20億田鼠洞庭“跑馬圈地”2023/11/22某效勞部一周中的每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人?，F(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作五天，試確定聘用方案，即周一到周日每天聘用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少。課后作業(yè)1效勞員的聘用問題2023/11/22優(yōu)化問題決策變量：周一到周日每天聘請的人數(shù)，記為目標(biāo)函數(shù)：聘用總?cè)藬?shù)約束條件：每天需要的人數(shù)，由于每人連續(xù)工作5天，所以周一的雇員應(yīng)是周四到周一聘用的，依據(jù)需要至少有50人，于是2023/11/22優(yōu)化模型2023/11/22求解模型用LINDO求解美國芝加哥大學(xué)的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/11/22用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/11/22結(jié)果輸出主要結(jié)果OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUE

x10.000000x24.000000x340.000000x4