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

2023/2/3優(yōu)化模型西北大學(xué)數(shù)學(xué)系第三講優(yōu)化模型2023/2/3優(yōu)化模型的一般意義簡單優(yōu)化模型舉例線性規(guī)劃模型舉例2023/2/3優(yōu)化模型是中國大學(xué)生建模競賽常見的類型，占很大的比重。92年以來，優(yōu)化模型有：94年A題：“逢山開路”設(shè)計(jì)最短路徑。95年A題：“一個(gè)飛行管理問題”，線性規(guī)劃和非線性規(guī)劃模型。96年A題：“最優(yōu)捕魚策略”，以微分方程為基礎(chǔ)的優(yōu)化模型。西北大學(xué)數(shù)學(xué)系2023/2/396年B題：“洗衣節(jié)水問題”，以用水量為目標(biāo)函數(shù)的優(yōu)化模型。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ī)劃模型。西北大學(xué)數(shù)學(xué)系2023/2/399年A題：“自動(dòng)化車床管理”，雙參數(shù)規(guī)劃模型。99年B題：“鉆井布局”，非線性混合整數(shù)規(guī)劃模型。00年B題：“鋼管訂購和運(yùn)輸”，二次規(guī)劃模型。01年B題：“公交車調(diào)度”，雙目標(biāo)規(guī)劃模型。02年A題：“車燈線光源的優(yōu)化設(shè)計(jì)”，規(guī)劃模型。西北大學(xué)數(shù)學(xué)系2023/2/303年B題：“露天礦生產(chǎn)的車輛安排”，非線性規(guī)劃模型。04年B題：“電力市場的輸電阻塞管理”，雙目標(biāo)線性規(guī)劃模型。05年B題：“DVD在現(xiàn)租賃”，0-1規(guī)劃模型。06年A題：“出版社的資源優(yōu)化配置”，線性規(guī)劃模型。西北大學(xué)數(shù)學(xué)系2023/2/307年B題：“乘公交，看奧運(yùn)”，動(dòng)態(tài)規(guī)劃模型。08年B題：“高等教育學(xué)費(fèi)標(biāo)準(zhǔn)探討”，優(yōu)化模型。09年B題：醫(yī)院眼科病床的合理安排問題，2010年A題：

儲(chǔ)油罐的變位識別與罐容表標(biāo)定，非線性規(guī)劃2011年B題：交巡警服務(wù)平臺的設(shè)置與調(diào)度，多目標(biāo)非線性規(guī)劃給出小屋外表面光伏電池的鋪設(shè)方案，使小屋的全年太陽能光伏發(fā)電總量盡可能大，而單位發(fā)電量的費(fèi)用盡可能小。2013年B題：碎片復(fù)原問題，

0-1線性規(guī)劃2012年B題：太陽能小屋的設(shè)計(jì)

，雙目標(biāo)規(guī)劃2023/2/3（一）優(yōu)化模型的數(shù)學(xué)描述下的最大值或最小值，其中設(shè)計(jì)變量（決策變量）目標(biāo)函數(shù)求函數(shù)在約束條件和可行域一優(yōu)化模型的一般意義2023/2/3“受約束于”之意2023/2/3（二）優(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/3（1）非線性規(guī)劃目標(biāo)函數(shù)和約束條件中，至少有一個(gè)非線性函數(shù)。2023/2/3（2）線性規(guī)劃（LP）目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)。2023/2/3（3）二次規(guī)劃問題目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束2023/2/35.根據(jù)變量具有確定值還是隨機(jī)值

確定規(guī)劃和隨機(jī)規(guī)劃。4.根據(jù)設(shè)計(jì)變量的允許值整數(shù)規(guī)劃（0-1規(guī)劃）和實(shí)數(shù)規(guī)劃。2023/2/3（三）建立優(yōu)化模型的一般步驟1.確定設(shè)計(jì)變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；3.尋找約束條件。2023/2/3工廠定期訂購原料，存入倉庫供生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；商店成批購進(jìn)各種商品，放在貨柜里以備零售；水庫在雨季蓄水，用于旱季的灌溉和發(fā)電。例1存貯模型二簡單優(yōu)化模型舉例存貯量多少合適？存貯量過大，存貯費(fèi)用太高；存貯量太小，會(huì)導(dǎo)致一次性訂購費(fèi)用增加，或不能及時(shí)滿足需求。2023/2/3問題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/31.確定設(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/3若每天生產(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/31連續(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)能力為無限大（相對于需求量），當(dāng)存貯量降到零時(shí)，Q件產(chǎn)品立即生產(chǎn)出來供給需求，即不允許缺貨。模型假設(shè)2023/2/3總費(fèi)用與變量的關(guān)系總費(fèi)用=生產(chǎn)準(zhǔn)備費(fèi)+存貯費(fèi)存貯費(fèi)=存貯單價(jià)*存貯量存貯量=？模型建立2023/2/3設(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/3一個(gè)周期內(nèi)存貯量一個(gè)周期內(nèi)存貯費(fèi)(A的面積)一個(gè)周期的總費(fèi)用每天平均費(fèi)用2023/2/3用微分法每天平均最小費(fèi)用著名的經(jīng)濟(jì)訂貨批量公式（EOQ公式）。模型求解2023/2/3當(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é)果符合常識，而定量關(guān)系（平方根，系數(shù)2等）憑常識是無法得出的，只能由數(shù)學(xué)建模得到。結(jié)果解釋2023/2/3這里得到的費(fèi)用C與前面計(jì)算得950元有微小差別，你能解釋嗎？在本例中2023/2/3討論參數(shù)有微小變化時(shí)對生產(chǎn)周期T影響。由相對變化量衡量對參數(shù)的敏感程度。T對c1

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

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

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

T1

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

RT1B2023/2/3一個(gè)周期內(nèi)缺貨損失費(fèi)一個(gè)周期內(nèi)存貯費(fèi)一個(gè)周期的總費(fèi)用每天平均費(fèi)用2023/2/3模型求解用微分法令每天平均最小費(fèi)用2023/2/3每個(gè)周期的供貨量與不允許缺貨模型相比較，有2023/2/3結(jié)果解釋即允許缺貨時(shí)，周期和供貨量增加，周期初的存貯量減少。2）缺貨損失費(fèi)愈大，愈小，愈接近，愈接近。1）3）不允許缺貨模型可視為允許缺貨模型的特例。2023/2/3課堂討論

制造計(jì)算機(jī)問題2023/2/3

一家制造計(jì)算機(jī)的公司計(jì)劃生產(chǎn)兩種產(chǎn)品：兩種計(jì)算機(jī)使用相同的微機(jī)處理芯片，但一種使用27英寸的顯示器，而另一種使用31英寸的顯示器。除了400000美元的固定費(fèi)用外，每臺27英寸顯示器的計(jì)算機(jī)花費(fèi)1950美元，而31英寸的需要花費(fèi)2250美元。制造商建議每臺27英寸顯示器的計(jì)算機(jī)零售價(jià)格為3390美元，而31英寸的計(jì)算機(jī)零售價(jià)格為3990美元。課堂討論制造計(jì)算機(jī)問題2023/2/3

銷售人員估計(jì)，在銷售這些計(jì)算機(jī)的市場上，一種類型的計(jì)算機(jī)每賣出一臺，零售價(jià)格就下降0.1美元。此外，一種類型的計(jì)算機(jī)的銷售也會(huì)影響另一種類型的銷售：每銷售一臺31英寸顯示器的計(jì)算機(jī)，估計(jì)27英寸顯示器的計(jì)算機(jī)零售價(jià)格下降0.03美元；每銷售一臺27英寸顯示器的計(jì)算機(jī)，估計(jì)31英寸顯示器的計(jì)算機(jī)零售價(jià)格下降0.04美元。假設(shè)制造的所有計(jì)算機(jī)都可以售出，那么該公司應(yīng)該生產(chǎn)每種計(jì)算機(jī)多少臺，才能使利潤最大？2023/2/3優(yōu)化模型決策變量：生產(chǎn)兩類計(jì)算機(jī)的數(shù)量，記為目標(biāo)函數(shù)：目標(biāo)變量：計(jì)算機(jī)零售的總利潤，記為總收入減去總支出表示售出27英寸顯示器的計(jì)算機(jī)的零售價(jià)格表示售出31英寸顯示器的計(jì)算機(jī)的零售價(jià)格2023/2/3