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

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

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

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

，雙目標規(guī)劃2023/2/3（一）優(yōu)化模型的數(shù)學描述下的最大值或最小值，其中設(shè)計變量（決策變量）目標函數(shù)求函數(shù)在約束條件和可行域一優(yōu)化模型的一般意義2023/2/3“受約束于”之意2023/2/3（二）優(yōu)化模型的分類1.根據(jù)是否存在約束條件有約束問題和無約束問題。2.根據(jù)設(shè)計變量的性質(zhì)靜態(tài)問題和動態(tài)問題。3.根據(jù)目標函數(shù)和約束條件表達式的性質(zhì)線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標規(guī)劃等。2023/2/3（1）非線性規(guī)劃目標函數(shù)和約束條件中，至少有一個非線性函數(shù)。2023/2/3（2）線性規(guī)劃（LP）目標函數(shù)和所有的約束條件都是設(shè)計變量的線性函數(shù)。2023/2/3（3）二次規(guī)劃問題目標函數(shù)為二次函數(shù)，約束條件為線性約束2023/2/35.根據(jù)變量具有確定值還是隨機值

確定規(guī)劃和隨機規(guī)劃。4.根據(jù)設(shè)計變量的允許值整數(shù)規(guī)劃（0-1規(guī)劃）和實數(shù)規(guī)劃。2023/2/3（三）建立優(yōu)化模型的一般步驟1.確定設(shè)計變量和目標變量；2.確定目標函數(shù)的表達式；3.尋找約束條件。2023/2/3工廠定期訂購原料，存入倉庫供生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；商店成批購進各種商品，放在貨柜里以備零售；水庫在雨季蓄水，用于旱季的灌溉和發(fā)電。例1存貯模型二簡單優(yōu)化模型舉例存貯量多少合適？存貯量過大，存貯費用太高；存貯量太小，會導致一次性訂購費用增加，或不能及時滿足需求。2023/2/3問題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)量多少，可使總費用最小。2023/2/31.確定設(shè)計變量和目標變量2.確定目標函數(shù)的表達式總費用為目標變量生產(chǎn)周期和生產(chǎn)量為設(shè)計變量3.尋找約束條件尋找設(shè)計變量與目標變量之間的關(guān)系設(shè)計變量所受的限制問題分析2023/2/3若每天生產(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)量，使得每天的費用最少。2023/2/31連續(xù)化，即設(shè)生產(chǎn)周期T和產(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è)2023/2/3總費用與變量的關(guān)系總費用=生產(chǎn)準備費+存貯費存貯費=存貯單價*存貯量存貯量=？模型建立2023/2/3設(shè)t時刻的存貯量為q(t)，則t=0時生產(chǎn)Q

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

Q=rT

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

存貯量的計算一個周期內(nèi)生產(chǎn)量等于這個周期內(nèi)的需求量2023/2/3一個周期內(nèi)存貯量一個周期內(nèi)存貯費(A的面積)一個周期的總費用每天平均費用2023/2/3用微分法每天平均最小費用著名的經(jīng)濟訂貨批量公式（EOQ公式）。模型求解2023/2/3當準備費c1增加時，生產(chǎn)周期和產(chǎn)量都變大；當存貯費c2

增加時，生產(chǎn)周期和產(chǎn)量都變??；當日需求費r增加時，生產(chǎn)周期變小而產(chǎn)量變大。這些定性結(jié)果符合常識，而定量關(guān)系（平方根，系數(shù)2等）憑常識是無法得出的，只能由數(shù)學建模得到。結(jié)果解釋2023/2/3這里得到的費用C與前面計算得950元有微小差別，你能解釋嗎？在本例中2023/2/3討論參數(shù)有微小變化時對生產(chǎn)周期T影響。由相對變化量衡量對參數(shù)的敏感程度。T對c1

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

T1

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

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

制造計算機問題2023/2/3

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

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