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

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

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

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

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

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

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

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

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

9、有微小變化時(shí)對(duì)生產(chǎn)周期T 影響。由相對(duì)變化量衡量對(duì)參數(shù)的敏感程度。T 對(duì)c1 的敏感程度記為敏感性分析2022/7/17意義是當(dāng)準(zhǔn)備費(fèi)增加1%時(shí)，生產(chǎn)周期增加0.5% ；而存貯費(fèi)增加1%時(shí)，生產(chǎn)周期減少0.5% ；日需求量增加1%時(shí)，生產(chǎn)周期減少0.5% 。當(dāng)有微小變化對(duì)生產(chǎn)周期影響不太大。2022/7/17思考建模中未考慮生產(chǎn)費(fèi)用（這應(yīng)是最大一筆費(fèi) 用），在什么情況下才可以不考慮它？建模時(shí)作了“生產(chǎn)能力無(wú)限大”的簡(jiǎn)化假設(shè)，如 果生產(chǎn)能力有限，是大于需求量的一個(gè)常數(shù)， 如何建模？ 敏感性分析：討論參數(shù)對(duì)結(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)準(zhǔn)備費(fèi) C1，每日每件產(chǎn)品存貯費(fèi) C2；4 生產(chǎn)能力為無(wú)限大（相對(duì)于需求量），允許缺 貨，每天每件產(chǎn)品缺貨損失費(fèi)C3 ，但缺貨數(shù)量需 在下次生產(chǎn)（訂貨）時(shí)補(bǔ)足。問(wèn)題2 允許缺貨的存貯模型2022/7/17模型建立總費(fèi)用=生產(chǎn)準(zhǔn)備費(fèi)+存貯費(fèi)+缺貨損失費(fèi)存貯費(fèi)=存貯單價(jià)*存貯量缺貨損失費(fèi)=缺貨單價(jià)*缺貨量存貯量=？，缺貨量=？2022/7/17因存貯量不足造成缺貨，因此 q(t) 可取負(fù)值， q(t) 以需求速率 r 線性遞減，直至q(T1) = 0，如圖。q(t) = Q - r t， Q = r T1 。

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

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

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

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

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