第三講簡單優(yōu)化模型資料課件

1、2022/7/17優(yōu)化模型第四章 優(yōu)化模型2022/7/17優(yōu)化模型的一般意義簡單優(yōu)化模型舉例線性規(guī)劃模型舉例2022/7/17優(yōu)化模型是中國大學(xué)生建模競賽常見的類型，占很大的比重。92 年以來，優(yōu)化模型有：年（題） 題目 模型94（A）逢山開路設(shè)計費用最小路徑95（A）一個飛行管理問題線性規(guī)劃和非線性規(guī)劃96（A）最優(yōu)捕魚策略以微分方程為基礎(chǔ)的優(yōu)化模型96（B）節(jié)水洗衣機以用水量為目標函數(shù)優(yōu)化模型2022/7/17年（題） 題目 模型97（A）零件的參數(shù)設(shè)計隨機優(yōu)化模型97（B）截斷切割動態(tài)優(yōu)化模型98（A）投資的收益和風(fēng)險雙目標優(yōu)98（B）災(zāi)情巡視的最佳路線0-1線性規(guī)劃模型99（A）自動

2、化車床管理雙參數(shù)規(guī)劃模型99（B）鉆井布局非線性混合整數(shù)規(guī)劃模型2022/7/17年（題） 題目 模型00（B）鋼管訂購和運輸二次規(guī)劃模型01（B）公交車調(diào)度雙目標規(guī)劃模型02（A）車燈線光源的優(yōu)化設(shè)計規(guī)劃模型03（B）露天礦生產(chǎn)的車輛安排非線性規(guī)劃模型。04（B）電力市場的輸電阻塞管理雙目線性規(guī)劃模型2022/7/17年（題） 題目 模型05（B）DVD在現(xiàn)租賃0-1規(guī)劃模型。06（A）出版社的資源優(yōu)化配置線性規(guī)劃模型。07（B）乘公交，看奧運動態(tài)規(guī)劃模型08（B）高等教育學(xué)費標準探討多目標優(yōu)化模型。09（B）眼科病床的合理安排0-1優(yōu)化模型2022/7/17年（題） 題目 模型10（A）儲

3、油罐的變位識別與罐容表標定非線性規(guī)劃模型11（B）交巡警服務(wù)平臺的設(shè)置與調(diào)度 雙目標規(guī)劃模型12（B）太陽能小屋的設(shè)計雙目標優(yōu)化模型2022/7/17（一）優(yōu)化模型的數(shù)學(xué)描述下的最大值或最小值，其中設(shè)計變量（決策變量）目標函數(shù)求函數(shù)在約束條件和可行域一 優(yōu)化模型的一般意義2022/7/17“受約束于”之意2022/7/17（二）優(yōu)化模型的分類1.根據(jù)是否存在約束條件 有約束問題和無約束問題。2.根據(jù)設(shè)計變量的性質(zhì) 靜態(tài)問題和動態(tài)問題。3.根據(jù)目標函數(shù)和約束條件表達式的性質(zhì) 線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標規(guī)劃等。2022/7/17（1）非線性規(guī)劃目標函數(shù)和約束條件中，至少有一個非線性函數(shù)

4、。2022/7/17（2）線性規(guī)劃（LP）目標函數(shù)和所有的約束條件都是設(shè)計變量的線性函數(shù)。2022/7/17（3）二次規(guī)劃問題目標函數(shù)為二次函數(shù)，約束條件為線性約束2022/7/175. 根據(jù)變量具有確定值還是隨機值 確定規(guī)劃和隨機規(guī)劃。4. 根據(jù)設(shè)計變量的允許值整數(shù)規(guī)劃（0-1規(guī)劃）和實數(shù)規(guī)劃。2022/7/17（三）建立優(yōu)化模型的一般步驟1.確定設(shè)計變量和目標變量；2.確定目標函數(shù)的表達式；3.尋找約束條件。2022/7/17工廠定期訂購原料，存入倉庫供生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；商店成批購進各種商品，放在貨柜里以備零售；水庫在雨季蓄水，用于旱季的灌溉和發(fā)電。例

5、1 存貯模型二 簡單優(yōu)化模型舉例存貯量多少合適？存貯量過大，存貯費用太高；存貯量太小，會導(dǎo)致一次性訂購費用增加，或不能及時滿足需求。2022/7/17問題1 不允許缺貨的存貯模型 配件廠為裝配線生產(chǎn)若干種部件，輪換生產(chǎn)不同的部件時因更換設(shè)備要付生產(chǎn)準備費（與生產(chǎn)數(shù)量無關(guān)），同一部件的產(chǎn)量大于需求時因積壓資金、占用倉庫要付存貯費。今已知某一部件的日需求量100件，生產(chǎn)準備費5000元，存貯費每日每件1元。如果生產(chǎn)能力遠大于需求，并且不允許出現(xiàn)缺貨，試安排該產(chǎn)品的生產(chǎn)計劃，即多少天生產(chǎn)一次（稱為生產(chǎn)周期），每次產(chǎn)量多少，可使總費用最小。2022/7/171.確定設(shè)計變量和目標變量2.確定目標函數(shù)的

6、表達式總費用為目標變量生產(chǎn)周期和生產(chǎn)量為設(shè)計變量3.尋找約束條件尋找設(shè)計變量與目標變量之間的關(guān)系設(shè)計變量所受的限制問題分析2022/7/17若每天生產(chǎn)一次，每次100件，無存貯費，生產(chǎn)準備費5000元，每天費用5000元；若10天生產(chǎn)一次，每次1000件，存貯費900+800+100=4500元，生產(chǎn)準備費5000元，總計9500元，平均每天費用950元；若50天生產(chǎn)一次，每次5000件，存貯費4900+4800+100=122500元，生產(chǎn)準備費5000元，總計127500元，平均每天費用2550元；尋找合適的生產(chǎn)周期、產(chǎn)量，使得每天的費用最少。2022/7/171 連續(xù)化，即設(shè)生產(chǎn)周期 T

7、 和產(chǎn)量 Q 均為連續(xù)量；2 產(chǎn)品每日的需求量為常數(shù) r ；3 每次生產(chǎn)準備費 C1，每日每件產(chǎn)品存貯費 C2；4 生產(chǎn)能力為無限大（相對于需求量），當存貯量 降到零時，Q件產(chǎn)品立即生產(chǎn)出來供給需求，即 不允許缺貨。模型假設(shè)2022/7/17總費用與變量的關(guān)系總費用=生產(chǎn)準備費+存貯費存貯費=存貯單價*存貯量存貯量=？模型建立2022/7/17設(shè) t 時刻的存貯量為 q(t) ，則t = 0時生產(chǎn) Q 件，存貯量 q(0) = Q , q(t) 以需求速率 r 線性遞減，直至q(T) = 0，如圖。q(t) = Q- r t， Q = r T 。otqQTrA不允許缺貨模型的存貯量q(t) 存

8、貯量的計算一個周期內(nèi)生產(chǎn)量等于這個周期內(nèi)的需求量2022/7/17一個周期內(nèi)存貯量一個周期內(nèi)存貯費(A的面積)一個周期的總費用每天平均費用2022/7/17用微分法每天平均最小費用著名的 經(jīng)濟訂貨批量公式（EOQ公式）。模型求解2022/7/17當準備費 c1 增加時，生產(chǎn)周期和產(chǎn)量都變大；當存貯費 c2 增加時，生產(chǎn)周期和產(chǎn)量都變?。划斎招枨筚M r 增加時，生產(chǎn)周期變小而產(chǎn)量變大。這些定性結(jié)果符合常識，而定量關(guān)系（平方根，系數(shù)2 等）憑常識是無法得出的，只能由數(shù)學(xué)建模得到。結(jié)果解釋2022/7/17這里得到的費用C與前面計算得950元有微小差別，你能解釋嗎？在本例中2022/7/17討論參數(shù)

9、有微小變化時對生產(chǎn)周期T 影響。由相對變化量衡量對參數(shù)的敏感程度。T 對c1 的敏感程度記為敏感性分析2022/7/17意義是當準備費增加1%時，生產(chǎn)周期增加0.5% ；而存貯費增加1%時，生產(chǎn)周期減少0.5% ；日需求量增加1%時，生產(chǎn)周期減少0.5% 。當有微小變化對生產(chǎn)周期影響不太大。2022/7/17思考建模中未考慮生產(chǎn)費用（這應(yīng)是最大一筆費 用），在什么情況下才可以不考慮它？建模時作了“生產(chǎn)能力無限大”的簡化假設(shè)，如 果生產(chǎn)能力有限，是大于需求量的一個常數(shù)， 如何建模？ 敏感性分析：討論參數(shù)對結(jié)果的影響。 技巧：從所給數(shù)據(jù)出發(fā)，得到粗略結(jié)論。 注意2022/7/17模型假設(shè)1 連續(xù)化

10、，即設(shè)生產(chǎn)周期 T 和產(chǎn)量 Q 均為連續(xù)量；2 產(chǎn)品每日的需求量為常數(shù) r ；3 每次生產(chǎn)準備費 C1，每日每件產(chǎn)品存貯費 C2；4 生產(chǎn)能力為無限大（相對于需求量），允許缺 貨，每天每件產(chǎn)品缺貨損失費C3 ，但缺貨數(shù)量需 在下次生產(chǎn)（訂貨）時補足。問題2 允許缺貨的存貯模型2022/7/17模型建立總費用=生產(chǎn)準備費+存貯費+缺貨損失費存貯費=存貯單價*存貯量缺貨損失費=缺貨單價*缺貨量存貯量=？，缺貨量=？2022/7/17因存貯量不足造成缺貨，因此 q(t) 可取負值， q(t) 以需求速率 r 線性遞減，直至q(T1) = 0，如圖。q(t) = Q - r t， Q = r T1 。

11、otqQTrA允許缺貨模型的存貯量q(t) RT1B2022/7/17一個周期內(nèi)缺貨損失費一個周期內(nèi)存貯費一個周期的總費用每天平均費用2022/7/17模型求解用微分法 令每天平均最小費用2022/7/17每個周期的供貨量與不允許缺貨模型相比較，有2022/7/17結(jié)果解釋即允許缺貨時，周期和供貨量增加，周期初的存貯量減少。2）缺貨損失費愈大， 愈小， 愈接近 ， 愈接近 。1）3）不允許缺貨模型可視為允許缺貨模型的特例。2022/7/17例3 森林救火問題森林失火了！消防站接到報警后派多少隊員前去救火？派的隊員越多，森林的損失越小，但是救援的開支會越大，所以需要綜合考慮森林損失費和救援費與消

12、防隊員人數(shù)之間的關(guān)系，以總費用最小來決定派出隊員的數(shù)目。2022/7/171.確定設(shè)計變量和目標變量2.確定目標函數(shù)的表達式總費用為目標變量消防隊員的人數(shù)為設(shè)計變量3.尋找約束條件尋找設(shè)計變量與目標變量之間的關(guān)系設(shè)計變量所受的限制問題分析2022/7/17總費用損失費：森林燒毀的面積，=損失費+ 救援費設(shè)時刻 t 森林燒毀的面積為則表示火勢蔓延的程度。損失費與森林燒毀的面積成正比，比例系數(shù) 表示燒毀單位面積的損失費。2022/7/17救援費：消防設(shè)備和消防用品消耗，消防隊員的補貼 每個消防隊員單位時間的費用 ，每個隊員 的救火費用是 ；每個隊員的一次性補 貼為 。共派出消防隊員 名。2022/

13、7/17總費用=損失費+ 救援費自由蔓延時段救火時段2022/7/17火勢以失火點為中心，以均勻速度向四周呈圓形蔓延，所以蔓延的半徑 r 與時間 t 成正比。而燒毀面積B與 r2 成正比，故 B與 t2 成正比，從而與 t 成正比。2022/7/17模型假設(shè)1 時刻 t 森林燒毀的面積為2 損失費與森林燒毀的面積成正比，比例系數(shù) 表示燒毀單位面積的損失費。3 從失火到開始救火這段時間 內(nèi)，火 勢蔓延程度與時間 t 成正比，比例系數(shù) 表示 火勢蔓延速度?？山忉屓缦拢簞t表示火勢蔓延的程度。2022/7/17派出消防隊員 x 名，開始救火以后 火 勢蔓延速度降為 其中 可視為每 個隊員的平均滅火速度

14、。顯然， 。每個消防隊員單位時間的費用 ，每個隊員 的救火費用是 ；每個隊員的一次性補 貼為 。火勢以失火點為中心，以均勻速度向四周呈圓形蔓延，所以蔓延的半徑 r 與時間 t 成正比。而燒毀面積B與 r2 成正比，故 B與 t2 成正比，從而與 t 成正比。2022/7/17模型構(gòu)成損失費 = 火勢自由蔓延時的損失費 + 有滅火時的損失費根據(jù)假設(shè)，與 t 的關(guān)系，如圖ott1t2b森林損失費2022/7/17救援費 =救火費 + 消防隊員個人補貼費救火費 =消防隊員個人補貼費 =救火總費用歸結(jié)為求x的值，使得2022/7/17模型求解用微分法，得應(yīng)派出的隊員人數(shù)為使得，總損失最小為結(jié)果解釋應(yīng)派

15、出的隊員數(shù)目由兩部分組成，其中一部分為是為了把火撲滅的最低限度。2022/7/17結(jié)果解釋另一部分是在最低限度之上的人數(shù)，與問題的各個參數(shù)有關(guān)。當隊員滅火速度和救援補貼費用系數(shù)減少時，隊員數(shù)增加；當火勢蔓延速度、開始救火時的火勢b及損失費用系數(shù)c1增加時，隊員數(shù)目增加。考慮：c2增加時，隊員數(shù)目也增加，是否合理？2022/7/17思考在森林救火模型中，如果考慮消防隊員的滅火速度 與開始救火時的火勢b有關(guān)，試假設(shè)一個合理的函數(shù)關(guān)系，重新求解模型。2022/7/17課堂討論 制造計算機問題2022/7/17 一家制造計算機的公司計劃生產(chǎn)兩種產(chǎn)品：兩種計算機使用相同的微機處理芯片，但一種使用27英寸的顯示器，而另一種使用31英寸的顯示器。除了400000美元的固定費用外，每臺27英寸顯示器的計算機花費1950美元，而31 英寸的需要花費2250美元。制造商建議每臺27英寸顯示器的計算機零售價格為3390美元，而31 英寸的