第三講簡單優(yōu)化模型

2023/2/6優(yōu)化模型第四章優(yōu)化模型2023/2/6優(yōu)化模型的一般意義簡單優(yōu)化模型舉例線性規(guī)劃模型舉例2023/2/6優(yōu)化模型是中國大學(xué)生建模競(jìng)賽常見的類型，占很大的比重。92年以來，優(yōu)化模型有：年（題）題目模型94（A）逢山開路設(shè)計(jì)費(fèi)用最小路徑95（A）一個(gè)飛行管理問題線性規(guī)劃和非線性規(guī)劃96（A）最優(yōu)捕魚策略以微分方程為基礎(chǔ)的優(yōu)化模型96（B）節(jié)水洗衣機(jī)以用水量為目標(biāo)函數(shù)優(yōu)化模型2023/2/6年（題）題目模型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)化車床管理雙參數(shù)規(guī)劃模型99（B）鉆井布局非線性混合整數(shù)規(guī)劃模型2023/2/6年（題）題目模型00（B）鋼管訂購和運(yùn)輸二次規(guī)劃模型01（B）公交車調(diào)度雙目標(biāo)規(guī)劃模型02（A）車燈線光源的優(yōu)化設(shè)計(jì)規(guī)劃模型03（B）露天礦生產(chǎn)的車輛安排非線性規(guī)劃模型。04（B）電力市場(chǎng)的輸電阻塞管理雙目線性規(guī)劃模型2023/2/6年（題）題目模型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)化模型2023/2/6年（題）題目模型10（A）儲(chǔ)油罐的變位識(shí)別與罐容表標(biāo)定非線性規(guī)劃模型11（B）交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度雙目標(biāo)規(guī)劃模型12（B）太陽能小屋的設(shè)計(jì)雙目標(biāo)優(yōu)化模型2023/2/6（一）優(yōu)化模型的數(shù)學(xué)描述下的最大值或最小值，其中設(shè)計(jì)變量（決策變量）目標(biāo)函數(shù)求函數(shù)在約束條件和可行域一優(yōu)化模型的一般意義2023/2/6“受約束于”之意2023/2/6（二）優(yōu)化模型的分類1.根據(jù)是否存在約束條件有約束問題和無約束問題。2.根據(jù)設(shè)計(jì)變量的性質(zhì)靜態(tài)問題和動(dòng)態(tài)問題。3.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì)線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等。2023/2/6（1）非線性規(guī)劃目標(biāo)函數(shù)和約束條件中，至少有一個(gè)非線性函數(shù)。2023/2/6（2）線性規(guī)劃（LP）目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)。2023/2/6（3）二次規(guī)劃問題目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束2023/2/65.根據(jù)變量具有確定值還是隨機(jī)值

確定規(guī)劃和隨機(jī)規(guī)劃。4.根據(jù)設(shè)計(jì)變量的允許值整數(shù)規(guī)劃（0-1規(guī)劃）和實(shí)數(shù)規(guī)劃。2023/2/6（三）建立優(yōu)化模型的一般步驟1.確定設(shè)計(jì)變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；3.尋找約束條件。2023/2/6工廠定期訂購原料，存入倉庫供生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；商店成批購進(jìn)各種商品，放在貨柜里以備零售；水庫在雨季蓄水，用于旱季的灌溉和發(fā)電。例1存貯模型二簡單優(yōu)化模型舉例存貯量多少合適？存貯量過大，存貯費(fèi)用太高；存貯量太小，會(huì)導(dǎo)致一次性訂購費(fèi)用增加，或不能及時(shí)滿足需求。2023/2/6問題1不允許缺貨的存貯模型

配件廠為裝配線生產(chǎn)若干種部件，輪換生產(chǎn)不同的部件時(shí)因更換設(shè)備要付生產(chǎn)準(zhǔn)備費(fèi)（與生產(chǎn)數(shù)量無關(guān)），同一部件的產(chǎn)量大于需求時(shí)因積壓資金、占用倉庫要付存貯費(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)用最小。2023/2/61.確定設(shè)計(jì)變量和目標(biāo)變量2.確定目標(biāo)函數(shù)的表達(dá)式總費(fèi)用為目標(biāo)變量生產(chǎn)周期和生產(chǎn)量為設(shè)計(jì)變量3.尋找約束條件尋找設(shè)計(jì)變量與目標(biāo)變量之間的關(guān)系設(shè)計(jì)變量所受的限制問題分析2023/2/6若每天生產(chǎn)一次，每次100件，無存貯費(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)用最少。2023/2/61連續(xù)化，即設(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)能力為無限大（相對(duì)于需求量），當(dāng)存貯量降到零時(shí)，Q件產(chǎn)品立即生產(chǎn)出來供給需求，即不允許缺貨。模型假設(shè)2023/2/6總費(fèi)用與變量的關(guān)系總費(fèi)用=生產(chǎn)準(zhǔn)備費(fèi)+存貯費(fèi)存貯費(fèi)=存貯單價(jià)*存貯量存貯量=？模型建立2023/2/6設(shè)t時(shí)刻的存貯量為q(t)，則t=0時(shí)生產(chǎn)Q

件，存貯量q(0)=Q,q(t)以需求速率r線性遞減，直至q(T)=0，如圖。q(t)=Q-rt，

Q=rT

。otqQTrA不允許缺貨模型的存貯量q(t)

存貯量的計(jì)算一個(gè)周期內(nèi)生產(chǎn)量等于這個(gè)周期內(nèi)的需求量2023/2/6一個(gè)周期內(nèi)存貯量一個(gè)周期內(nèi)存貯費(fèi)(A的面積)一個(gè)周期的總費(fèi)用每天平均費(fèi)用2023/2/6用微分法每天平均最小費(fèi)用著名的經(jīng)濟(jì)訂貨批量公式（EOQ公式）。模型求解2023/2/6當(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í)是無法得出的，只能由數(shù)學(xué)建模得到。結(jié)果解釋2023/2/6這里得到的費(fèi)用C與前面計(jì)算得950元有微小差別，你能解釋嗎？在本例中2023/2/6討論參數(shù)有微小變化時(shí)對(duì)生產(chǎn)周期T影響。由相對(duì)變化量衡量對(duì)參數(shù)的敏感程度。T對(duì)c1

的敏感程度記為敏感性分析2023/2/6意義是當(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)周期影響不太大。2023/2/6思考建模中未考慮生產(chǎn)費(fèi)用（這應(yīng)是最大一筆費(fèi)用），在什么情況下才可以不考慮它？建模時(shí)作了“生產(chǎn)能力無限大”的簡化假設(shè)，如果生產(chǎn)能力有限，是大于需求量的一個(gè)常數(shù)，如何建模？

敏感性分析：討論參數(shù)對(duì)結(jié)果的影響。

技巧：從所給數(shù)據(jù)出發(fā)，得到粗略結(jié)論。注意2023/2/6模型假設(shè)1連續(xù)化，即設(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)能力為無限大（相對(duì)于需求量），允許缺貨，每天每件產(chǎn)品缺貨損失費(fèi)C3，但缺貨數(shù)量需在下次生產(chǎn)（訂貨）時(shí)補(bǔ)足。問題2允許缺貨的存貯模型2023/2/6模型建立總費(fèi)用=生產(chǎn)準(zhǔn)備費(fèi)+存貯費(fèi)+缺貨損失費(fèi)存貯費(fèi)=存貯單價(jià)*存貯量缺貨損失費(fèi)=缺貨單價(jià)*缺貨量存貯量=？，缺貨量=？2023/2/6因存貯量不足造成缺貨，因此q(t)可取負(fù)值，q(t)以需求速率r線性遞減，直至q(T1)=0，如圖。q(t)=Q-rt，Q=r

T1

。otqQTrA允許缺貨模型的存貯量q(t)

RT1B2023/2/6一個(gè)周期內(nèi)缺貨損失費(fèi)一個(gè)周期內(nèi)存貯費(fèi)一個(gè)周期的總費(fèi)用每天平均費(fèi)用2023/2/6模型求解用微分法令每天平均最小費(fèi)用2023/2/6每個(gè)周期的供貨量與不允許缺貨模型相比較，有2023/2/6結(jié)果解釋即允許缺貨時(shí)，周期和供貨量增加，周期初的存貯量減少。2）缺貨損失費(fèi)愈大，愈小，愈接近，愈接近。1）3）不允許缺貨模型可視為允許缺貨模型的特例。2023/2/6例3森林救火問題森林失火了！消防站接到報(bào)警后派多少隊(duì)員前去救火？派的隊(duì)員越多，森林的損失越小，但是救援的開支會(huì)越大，所以需要綜合考慮森林損失費(fèi)和救援費(fèi)與消防隊(duì)員人數(shù)之間的關(guān)系，以總費(fèi)用最小來決定派出隊(duì)員的數(shù)目。2023/2/61.確定設(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ì)變量所受的限制問題分析2023/2/6總費(fèi)用損失費(fèi)：森林燒毀的面積，=損失費(fèi)+救援費(fèi)設(shè)時(shí)刻t森林燒毀的面積為則表示火勢(shì)蔓延的程度。損失費(fèi)與森林燒毀的面積成正比，比例系數(shù)表示燒毀單位面積的損失費(fèi)。2023/2/6救援費(fèi)：消防設(shè)備和消防用品消耗，消防隊(duì)員的補(bǔ)貼每個(gè)消防隊(duì)員單位時(shí)間的費(fèi)用，每個(gè)隊(duì)員的救火費(fèi)用是；每個(gè)隊(duì)員的一次性補(bǔ)貼為。共派出消防隊(duì)員名。2023/2/6總費(fèi)用=損失費(fèi)+救援費(fèi)自由蔓延時(shí)段救火時(shí)段2023/2/6火勢(shì)以失火點(diǎn)為中心，以均勻速度向四周呈圓形蔓延，所以蔓延的半徑r與時(shí)間t成正比。而燒毀面積B與r2

成正比，故B與t2

成正比，從而與t成正比。2023/2/6模型假設(shè)1時(shí)刻t森林燒毀的面積為2損失費(fèi)與森林燒毀的面積成正比，比例系數(shù)表示燒毀單位面積的損失費(fèi)。3從失火到開始救火這段時(shí)間內(nèi)，火勢(shì)蔓延程度與時(shí)間t成正比，比例系數(shù)表示火勢(shì)蔓延速度?？山忉屓缦拢簞t表示火勢(shì)蔓延的程度。2023/2/6派出消防隊(duì)員x

名，開始救火以后火勢(shì)蔓延速度降為其中可視為每個(gè)隊(duì)員的平均滅火速度。顯然，。每個(gè)消防隊(duì)員單位時(shí)間的費(fèi)用，每個(gè)隊(duì)員的救火費(fèi)用是；每個(gè)隊(duì)員的一次性補(bǔ)貼為?；饎?shì)以失火點(diǎn)為中心，以均勻速度向四周呈圓形蔓延，所以蔓延的半徑r與時(shí)間t成正比。而燒毀面積B與r2

成正比，故B與t2

成正比，從而與t成正比。2023/2/6模型構(gòu)成損失費(fèi)=火勢(shì)自由蔓延時(shí)的損失費(fèi)+有滅火時(shí)的損失費(fèi)根據(jù)假設(shè)，與t的關(guān)系，如圖ott1t2b森林損失費(fèi)2023/2/6救援費(fèi)=救火費(fèi)+消防隊(duì)員個(gè)人補(bǔ)貼費(fèi)救火費(fèi)=消防隊(duì)員個(gè)人補(bǔ)貼費(fèi)=救火總費(fèi)用歸結(jié)為求x的值，使得2023/2/6模型求解用微分法，得應(yīng)派出的隊(duì)員人數(shù)為使得，總損失最小為結(jié)果解釋應(yīng)派出的隊(duì)員數(shù)目由兩部分組成，其中一部分為是為了把火撲滅的最低限度。2023/2/6結(jié)果解釋另一部分是在最低限度之上的人數(shù)，與問題的各個(gè)參數(shù)有關(guān)。當(dāng)隊(duì)員滅火速度和救援補(bǔ)貼費(fèi)用系數(shù)減少時(shí)，隊(duì)員數(shù)增加；當(dāng)火勢(shì)蔓延速度、開始救火時(shí)的火勢(shì)b及損失費(fèi)用系數(shù)c1增加時(shí)，隊(duì)員