數(shù)學建模最優(yōu)化理論

數(shù)學建模最優(yōu)化理論第一頁，共三十一頁，編輯于2023年，星期六生活何處不優(yōu)化最短路徑優(yōu)化最省時間優(yōu)化管理科學優(yōu)化工程設計優(yōu)化市場調度優(yōu)化城市建設優(yōu)化第二頁，共三十一頁，編輯于2023年，星期六建模真題之優(yōu)化問題1994年全國賽A題：逢山開路1996年全國賽A題：最優(yōu)捕魚策略2001年全國賽B題：公交車優(yōu)化調度2010年東三省A題：企業(yè)的營銷管理問題2010年東三省B題：周游全中國據(jù)統(tǒng)計，1992~2005年全國賽28個賽題中有關優(yōu)化問題有19個，最優(yōu)化方法是用的最多的方法之一。第三頁，共三十一頁，編輯于2023年，星期六旅行商問題這個問題稱為旅行商問題(TravelingSalesmanProblem)，簡稱TSP。一個商人擬到n個城市去推銷商品，已知每兩個城市和之間的距離為，如何選擇一條道路，使得商人每個城市走一遍后回到起點，且所走的路徑最短。第四頁，共三十一頁，編輯于2023年，星期六我們應該怎么做？第五頁，共三十一頁，編輯于2023年，星期六最優(yōu)化問題概述最優(yōu)化問題的定義最優(yōu)化問題的分類解決最優(yōu)化問題的方法最優(yōu)化模型的基本要素第六頁，共三十一頁，編輯于2023年，星期六最優(yōu)化問題的定義

最優(yōu)化問題就是在給定條件下尋找最佳方案的問題即在資源給定時尋找最好的目標，或在目標確定時使用最少的資源第七頁，共三十一頁，編輯于2023年，星期六最優(yōu)化問題的分類第八頁，共三十一頁，編輯于2023年，星期六解最優(yōu)化問題的方法 最優(yōu)化問題的求解方法一般可以分成解析法、直接法、數(shù)值計算法和其他方法 最優(yōu)化理論的三大非經(jīng)典算法：模擬退火算法、神經(jīng)網(wǎng)絡算法、遺傳算法第九頁，共三十一頁，編輯于2023年，星期六最優(yōu)化模型基本要素決策變量、目標函數(shù)和約束條件（1）決策變量是問題中有待確定的未知因素。（2）目標函數(shù)是指對問題所追求的目標的數(shù)學描述。（3）約束條件是指實現(xiàn)問題目標的限制因素。第十頁，共三十一頁，編輯于2023年，星期六旅行商問題問題類別：0-1規(guī)劃問題也是動態(tài)規(guī)劃問題決策變量：目標函數(shù)：約束條件：第十一頁，共三十一頁，編輯于2023年，星期六距離矩陣D：元素為決策矩陣X：元素為假設有n個城市，最短路徑的排序為1~n，則可以得到這樣兩個矩陣。第十二頁，共三十一頁，編輯于2023年，星期六線性規(guī)劃模型線性規(guī)劃 又稱線性最優(yōu)化,當目標函數(shù)和約束條件都是決策變量的線性函數(shù)時稱為線性規(guī)劃；否則稱為非線性規(guī)劃。一般形式

第十三頁，共三十一頁，編輯于2023年，星期六基金使用優(yōu)化模型某公司有100萬元的資金可供投資（要求全部用完)。該公司有六個可選的投資項目，其各種數(shù)據(jù)如表1－2所示。投資項目風險（%）紅利（%）增長率（%）信用度11842242657103109122447810512615468886該公司想達到的目標為：投資風險最小，每年紅利至少為6.5萬元，最低平均增長率為12%，最低平均信用度為7。請設計投資計劃。第十四頁，共三十一頁，編輯于2023年，星期六（1）決策變量

本問題的決策變量是在每種投資項目上的投資額。設xi為項目i的投資額（萬元）（i=1,2,,6）（2）目標函數(shù)本問題的目標為總投資風險最小，即第十五頁，共三十一頁，編輯于2023年，星期六（3）約束條件本問題共有五個約束條件:①各項目投資總和為100萬元;②每年紅利至少為6.5萬元;③最低平均增長率為12%;④最低平均信用度為7;⑤非負約束。第十六頁，共三十一頁，編輯于2023年，星期六于是，可以建立線性規(guī)劃數(shù)學模型：這是個典型的線性規(guī)劃模型，為了解這個模型，我們可以借助LINGO、MATLAB等軟件或者直接用單純形法來解決。第十七頁，共三十一頁，編輯于2023年，星期六多目標規(guī)劃模型 在多指標的最優(yōu)化問題背景下所建立起來的數(shù)學規(guī)劃問題即為多目標規(guī)劃問題。（多目標決策） 在實際問題中，可能會同時考慮幾個方面都達到最優(yōu)，比如企業(yè)可能會要求產(chǎn)量最高，成本最低，質量最好，利潤最大，環(huán)境達標，運輸滿足等。多目標規(guī)劃能更好地兼顧統(tǒng)籌處理多種目標的關系，求得更切合實際要求的解。 多目標規(guī)劃可以按照實際情況分主次，輕重緩急來考慮問題。第十八頁，共三十一頁，編輯于2023年，星期六多目標規(guī)劃的解法一、將多目標轉化為單目標優(yōu)選法線形加權法平方和加權法乘除法分層序列法二、直接用數(shù)學方法求非劣解第十九頁，共三十一頁，編輯于2023年，星期六假定要求個目標的最優(yōu)值，約束條件為。如果其中一個目標比較關鍵，如希望它取極小值，使其他目標滿足一定條件，如使

1.優(yōu)選法（使主要目標優(yōu)化兼顧其它目標）而把問題轉化為單目標規(guī)劃問題第二十頁，共三十一頁，編輯于2023年，星期六

當個目標都要求最小時，可以給每個目標相應的權系數(shù)，且，構成新的目標函數(shù)然后使這個新的目標函數(shù)取極小值。這里的權系數(shù)大小根據(jù)每個目標函數(shù)的相對重要性來確定。2.線性加權法第二十一頁，共三十一頁，編輯于2023年，星期六 首先確定各個目標的希望目標值，要求所有的目標值和相應的希望目標值盡可能接近。此時采用下列評價函數(shù)：然后求。

3.平方和加權法第二十二頁，共三十一頁，編輯于2023年，星期六式中，為加權系數(shù)，可按各目標被重視的程度給出。如果對其中不同的目標重視程度不同，則可采用加權的平方和作為評價函數(shù)，即求：第二十三頁，共三十一頁，編輯于2023年，星期六4.乘除法設有個目標。式中，有個要求極小值，例如設，而余下的要求其極大值，并假定。這時，采用以下評價函數(shù)：作為單目標問題求極小值。第二十四頁，共三十一頁，編輯于2023年，星期六5.分層序列法

將目標按重要性的次序分成最重要目標、次重要目標，如。然后按順序將一個多目標規(guī)劃問題轉化為一系列單目標優(yōu)化問題來求解。第二十五頁，共三十一頁，編輯于2023年，星期六

最后所求出的為最優(yōu)解。步驟：主要目標的最優(yōu)集合為，再在集合內(nèi)求次重要目標的最優(yōu)解，設此時的最優(yōu)解集合為，如此繼續(xù)進行，直到求出最后一個目標函數(shù)的最優(yōu)解。第一步第二步第步第二十六頁，共三十一頁，編輯于2023年，星期六某公司計劃購進一批新卡車，可供選擇的卡車有如下4種類型：A1，A2，A3，A4?，F(xiàn)考慮6個方案屬性：維修期限f1(年)，每100升汽油所跑路程f2(里)，最大載重f3(噸)，價格f4(萬元)，可靠性f5，靈敏性f6。這4種型號的卡車分別關于目標屬性的指標值fij如下表所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般線性加權法解多目標規(guī)劃問題第二十七頁，共三十一頁，編輯于2023年，星期六首先對不同度量單位和不同數(shù)量級的指標值進行標準化處理。先將定性指標定量化：效益型指標很低低一般高很高13579很高高一般低很低成本型指標可靠性和靈敏性都屬于效益型指標，其打分如下可靠性一般低高很高5379靈敏性高一般很高一般7595第二十八頁，共三十一頁，編輯于2023年，星期六按以下公式作無量綱的標準化處理其中：變換后的指標值矩陣為：第二十九頁，共三十一頁，編輯于2023年，星期六a