第三章 簡單的優(yōu)化模型6

1、第三章第三章 簡單的優(yōu)化模型簡單的優(yōu)化模型 本章主要介紹優(yōu)化模型的一般原理和形式，重點(diǎn)介紹如存儲模型、生豬銷售的最佳時機(jī)、梯子問題、森林救火問題等具有代表性的優(yōu)化模型。 通過該部分的學(xué)習(xí)，了解如何建立優(yōu)化模型（無約束），優(yōu)化模型的基本求解方法。課程學(xué)時：6學(xué)時一、優(yōu)化模型的數(shù)學(xué)描述一、優(yōu)化模型的數(shù)學(xué)描述下的最大值或最小值，其中下的最大值或最小值，其中.,.,)(mihi210 x.,.,),)()(piggii2100 xx 決策變量決策變量目標(biāo)函數(shù)目標(biāo)函數(shù)),.,(nxxxx321x將一個優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù)將一個優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù))(xfu 在約束條件在約束條

2、件和和x)(xf x 可行域可行域3.1 3.1 優(yōu)化模型的一般理論優(yōu)化模型的一般理論.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(max)min(ortosubjectts .“受約束于”之意1.1.根據(jù)是否存在約束條件根據(jù)是否存在約束條件 有約束問題和無約束問題。有約束問題和無約束問題。2.2.根據(jù)決策變量的性質(zhì)根據(jù)決策變量的性質(zhì) 靜態(tài)問題和動態(tài)問題。靜態(tài)問題和動態(tài)問題。3.3.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì)根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì) 線性規(guī)劃，非線性規(guī)劃，線性規(guī)劃，非線性規(guī)劃， 二次規(guī)劃，多目標(biāo)規(guī)劃等。二次規(guī)劃，多目標(biāo)規(guī)劃等

3、。二、優(yōu)化模型的分類二、優(yōu)化模型的分類（1）非線性規(guī)劃）非線性規(guī)劃目標(biāo)函數(shù)和約束條件中，至少有一個非線性函數(shù)。目標(biāo)函數(shù)和約束條件中，至少有一個非線性函數(shù)。.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(min.,.,.,.,.minnixnibxatsxcuinkikikniii2102111（2）線性規(guī)劃（）線性規(guī)劃（LP） 目標(biāo)函數(shù)和所有的約束條件都是決策變目標(biāo)函數(shù)和所有的約束條件都是決策變量的線性函數(shù)。量的線性函數(shù)。（3）二次規(guī)劃問題）二次規(guī)劃問題目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束1,111min

4、( )2,1,2,., . .0.1,2,., .nniiijijii jnijjijiuf xc xb x xa xb instxin5. 根據(jù)變量具有確定值還是隨機(jī)值根據(jù)變量具有確定值還是隨機(jī)值 確定規(guī)劃和隨機(jī)規(guī)劃。確定規(guī)劃和隨機(jī)規(guī)劃。4. 4. 根據(jù)決策變量的允許值根據(jù)決策變量的允許值整數(shù)規(guī)劃（整數(shù)規(guī)劃（0-1規(guī)劃）和實(shí)數(shù)規(guī)劃。規(guī)劃）和實(shí)數(shù)規(guī)劃。1.確定決策變量和目標(biāo)變量；確定決策變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；確定目標(biāo)函數(shù)的表達(dá)式；3.尋找約束條件。尋找約束條件。三、建立優(yōu)化模型的一般步驟三、建立優(yōu)化模型的一般步驟3.2 3.2 優(yōu)化模型的幾個案例優(yōu)化模型的幾個案例案例案例1

5、 1 存貯模型存貯模型問問 題題配件廠為裝配線生產(chǎn)若干種產(chǎn)品，輪換產(chǎn)品時因更換設(shè)配件廠為裝配線生產(chǎn)若干種產(chǎn)品，輪換產(chǎn)品時因更換設(shè)備要付備要付生產(chǎn)準(zhǔn)備費(fèi)生產(chǎn)準(zhǔn)備費(fèi)，產(chǎn)量大于需求時要付，產(chǎn)量大于需求時要付貯存費(fèi)貯存費(fèi)。該廠。該廠生產(chǎn)能力非常大，即所需數(shù)量可在很短時間內(nèi)產(chǎn)出。生產(chǎn)能力非常大，即所需數(shù)量可在很短時間內(nèi)產(chǎn)出。已知某產(chǎn)品日需求量已知某產(chǎn)品日需求量100件，生產(chǎn)準(zhǔn)備費(fèi)件，生產(chǎn)準(zhǔn)備費(fèi)5000元，貯存費(fèi)元，貯存費(fèi)每日每件每日每件1元。試安排該產(chǎn)品的生產(chǎn)計劃，即多少天生產(chǎn)元。試安排該產(chǎn)品的生產(chǎn)計劃，即多少天生產(chǎn)一次（生產(chǎn)周期），每次產(chǎn)量多少，使總費(fèi)用最小。一次（生產(chǎn)周期），每次產(chǎn)量多少，使總費(fèi)用最

6、小。要要 求求不只是回答問題，而且要建立生產(chǎn)周期、產(chǎn)量與不只是回答問題，而且要建立生產(chǎn)周期、產(chǎn)量與需求量、準(zhǔn)備費(fèi)、貯存費(fèi)之間的關(guān)系。需求量、準(zhǔn)備費(fèi)、貯存費(fèi)之間的關(guān)系。問題分析與思考問題分析與思考 每天生產(chǎn)一次每天生產(chǎn)一次，每次，每次100件，無貯存費(fèi)，準(zhǔn)備費(fèi)件，無貯存費(fèi)，準(zhǔn)備費(fèi)5000元。元。日需求日需求100件，準(zhǔn)備費(fèi)件，準(zhǔn)備費(fèi)5000元，貯存費(fèi)每日每件元，貯存費(fèi)每日每件1元。元。 10天生產(chǎn)一次天生產(chǎn)一次，每次，每次1000件，貯存費(fèi)件，貯存費(fèi)900+800+100 =4500元，準(zhǔn)備費(fèi)元，準(zhǔn)備費(fèi)5000元，總計元，總計9500元。元。 50天生產(chǎn)一次天生產(chǎn)一次，每次，每次5000件，貯存

7、費(fèi)件，貯存費(fèi)4900+4800+100 =122500元，準(zhǔn)備費(fèi)元，準(zhǔn)備費(fèi)5000元，總計元，總計127500元。元。平均每天費(fèi)用平均每天費(fèi)用950元元平均每天費(fèi)用平均每天費(fèi)用2550元元1010天生產(chǎn)一次平均每天費(fèi)用最小嗎天生產(chǎn)一次平均每天費(fèi)用最小嗎? ?每天費(fèi)用每天費(fèi)用5000元元 這是一個優(yōu)化問題，關(guān)鍵在建立目標(biāo)函數(shù)。這是一個優(yōu)化問題，關(guān)鍵在建立目標(biāo)函數(shù)。顯然不能用一個周期的總費(fèi)用作為目標(biāo)函數(shù)顯然不能用一個周期的總費(fèi)用作為目標(biāo)函數(shù)目標(biāo)函數(shù)目標(biāo)函數(shù)每天總費(fèi)用的平均值每天總費(fèi)用的平均值 周期短，產(chǎn)量小周期短，產(chǎn)量小 周期長，產(chǎn)量大周期長，產(chǎn)量大問題分析與思考問題分析與思考貯存費(fèi)少，準(zhǔn)備費(fèi)多貯

8、存費(fèi)少，準(zhǔn)備費(fèi)多準(zhǔn)備費(fèi)少，貯存費(fèi)多準(zhǔn)備費(fèi)少，貯存費(fèi)多存在最佳的周期和產(chǎn)量，使總費(fèi)用（二者之和）最小存在最佳的周期和產(chǎn)量，使總費(fèi)用（二者之和）最小模模 型型 假假 設(shè)設(shè)1. 產(chǎn)品每天的需求量為常數(shù)產(chǎn)品每天的需求量為常數(shù) r；2. 每次生產(chǎn)準(zhǔn)備費(fèi)為每次生產(chǎn)準(zhǔn)備費(fèi)為 c1, 每天每件產(chǎn)品貯存費(fèi)為每天每件產(chǎn)品貯存費(fèi)為 c2；3. T天生產(chǎn)一次（周期）天生產(chǎn)一次（周期）, 每次生產(chǎn)每次生產(chǎn)Q件，當(dāng)貯存量件，當(dāng)貯存量 為零時，為零時，Q件產(chǎn)品立即到來（生產(chǎn)時間不計）；件產(chǎn)品立即到來（生產(chǎn)時間不計）；建建 模模 目目 的的設(shè)設(shè) r, c1, c2 已知，求已知，求T, Q 使每天總費(fèi)用的平均值最小。使每天總

9、費(fèi)用的平均值最小。4. 為方便起見，時間和產(chǎn)量都作為連續(xù)量處理。為方便起見，時間和產(chǎn)量都作為連續(xù)量處理。模模 型型 建建 立立0tq貯存量表示為時間的函數(shù)貯存量表示為時間的函數(shù) q(t)TQ-rt=0生產(chǎn)生產(chǎn)Q件，件，q(0)=Q, q(t)以以需求速率需求速率r遞減，遞減，q(T)=0.一周期一周期總費(fèi)用總費(fèi)用TQccC221每天總費(fèi)用平均每天總費(fèi)用平均值（目標(biāo)函數(shù)）值（目標(biāo)函數(shù)）2)(21rTcTcTCTC離散問題連續(xù)化離散問題連續(xù)化AcdttqcT202)(一周期貯存費(fèi)為一周期貯存費(fèi)為A=QT/22221rTcc rTQ 模型求解模型求解Min2)(21rTcTcTC求求 T 使使0dT

10、dC212crcrTQ212rccT 模型分析模型分析QTc,1QTc,2QTr,模型應(yīng)用模型應(yīng)用c1=5000, c2=1，r=100T=10(天天), Q=1000(件件), C=1000(元元) 回答問題回答問題 經(jīng)濟(jì)批量訂貨公式經(jīng)濟(jì)批量訂貨公式（EOQ公式公式）212rccT 212crcrTQ每天需求量每天需求量 r，每次訂貨費(fèi)，每次訂貨費(fèi) c1,每天每件貯存費(fèi)每天每件貯存費(fèi) c2 ，用于訂貨、供應(yīng)、存貯情形用于訂貨、供應(yīng)、存貯情形不允許缺貨的存貯模型不允許缺貨的存貯模型 問：為什么不考慮生產(chǎn)費(fèi)用？在什么條件下才不考慮？問：為什么不考慮生產(chǎn)費(fèi)用？在什么條件下才不考慮？T天訂貨一次天訂

11、貨一次(周期周期), 每次訂貨每次訂貨Q件，當(dāng)貯存量降到件，當(dāng)貯存量降到零時，零時，Q件立即到貨。件立即到貨。允許缺貨的存貯模型允許缺貨的存貯模型AB0qQ-rT1t當(dāng)貯存量降到零時仍有需求當(dāng)貯存量降到零時仍有需求r, 出出現(xiàn)缺貨，造成損失?，F(xiàn)缺貨，造成損失。原模型假設(shè)：貯存量降到零時原模型假設(shè)：貯存量降到零時Q件件產(chǎn)品立即生產(chǎn)出來產(chǎn)品立即生產(chǎn)出來(或立即到貨或立即到貨)現(xiàn)假設(shè)：允許缺貨現(xiàn)假設(shè)：允許缺貨, 每天每件缺貨損失費(fèi)每天每件缺貨損失費(fèi) c3 , 缺貨需補(bǔ)足缺貨需補(bǔ)足T1rTQ AcdttqcT2021)(一周期一周期貯存費(fèi)貯存費(fèi)BcdttqcTT331)(一周期一周期缺貨費(fèi)缺貨費(fèi)周期周

12、期T, t=T1貯存量降到零貯存量降到零2)(2213121TTrcQTccC一周期總費(fèi)用一周期總費(fèi)用rTQrTcrTQcTcTCQTC2)(2),(232210,0QCTC每天總費(fèi)用每天總費(fèi)用平均值平均值（目標(biāo)函數(shù)）（目標(biāo)函數(shù)）213121)(2121TTrcQTccC一周期總費(fèi)用一周期總費(fèi)用Min),(QTC求求 T ,Q 使使332212cccrccT323212ccccrcQ為與為與不允許缺貨的存貯模型相不允許缺貨的存貯模型相比，比，T記作記作T , Q記作記作Q212rccT 212crcrTQ不允不允許缺許缺貨模貨模型型QQTT,332ccc 記記1QQTT,13cQQTT,332

13、212cccrccT323212ccccrcQ允許允許缺貨缺貨模型模型不不允允許許缺缺貨貨3c332212cccrccT323212ccccrcQ允許允許缺貨缺貨模型模型0qQ -rT1tT注意：缺貨需補(bǔ)足注意：缺貨需補(bǔ)足Q 每周期初的存貯量每周期初的存貯量R每周期的生產(chǎn)量每周期的生產(chǎn)量R （或訂貨量）（或訂貨量）332212ccccrcTrRQ不允許缺貨時的產(chǎn)量不允許缺貨時的產(chǎn)量(或訂貨量或訂貨量) QQR飼養(yǎng)場每天投入飼養(yǎng)場每天投入4元資金，用于飼料、人力、設(shè)元資金，用于飼料、人力、設(shè)備，備，估計估計可使可使80千克重的生豬體重增加千克重的生豬體重增加2公斤。公斤。問問題題市場價格目前為每

14、千克市場價格目前為每千克8元，但是元，但是預(yù)測預(yù)測每天會降每天會降低低 0.1元，問生豬應(yīng)何時出售。元，問生豬應(yīng)何時出售。如果如果估計估計和和預(yù)測預(yù)測有誤差，對結(jié)果有何影響。有誤差，對結(jié)果有何影響。分分析析投入資金使生豬體重隨時間增加，出售單價隨投入資金使生豬體重隨時間增加，出售單價隨時間減少，故存在最佳出售時機(jī)，使利潤最大。時間減少，故存在最佳出售時機(jī)，使利潤最大。案例案例2 2 生豬的最佳銷售時機(jī)生豬的最佳銷售時機(jī)( )(8)(80)4Q tgtrtt求求 t 使使Q(t)最大最大4402rgtrg10天后出售，可多得利潤天后出售，可多得利潤20元元建模及求解建模及求解生豬體重生豬體重 w

15、=80+rt出售價格出售價格 p=8-gt銷售收入銷售收入 R=pw資金投入資金投入 C=4t利潤利潤 Q=R-C=pw -C估計估計r=2，若當(dāng)前出售，利潤為若當(dāng)前出售，利潤為808=640（元）（元）t 天天出售出售=10Q(10)=660 640g=0.1敏感性分析敏感性分析研究研究 r, g變化時對模型結(jié)果的影響變化時對模型結(jié)果的影響 估計估計r=2， g=0.1 設(shè)設(shè)g=0.1不變不變 5 . 1,6040rrrtt 對對r 的（相對）敏感度的（相對）敏感度 rrttrtS/),(trdrdt3604060),(rrtS生豬每天體重增加量生豬每天體重增加量r 增加增加1%，出售時間推

16、遲，出售時間推遲3%。 1.522.5305101520rt敏感性分析敏感性分析估計估計r=2， g=0.1研究研究 r, g變化時對模型結(jié)果的影響變化時對模型結(jié)果的影響 設(shè)設(shè)r=2不變不變 15. 00,203gggtt 對對g的（相對）敏感度的（相對）敏感度 tgdgdtggttgtS/),(32033),(ggtS生豬價格每天的降低量生豬價格每天的降低量g增加增加1%，出售時間提前，出售時間提前3%。 0.060.080.10.120.140.160102030gt強(qiáng)健性分析強(qiáng)健性分析保留生豬直到利潤的增值等于每天的費(fèi)用時出售保留生豬直到利潤的增值等于每天的費(fèi)用時出售研究研究 r, g不

17、是常數(shù)時對模型結(jié)果的影響不是常數(shù)時對模型結(jié)果的影響 w=80+rt w = w(t)4)()()()(twtptwtpp=8-gt p =p(t) 0)( tQ每天利潤的增值每天利潤的增值 每天投入的資金每天投入的資金 ttwtptQ4)()()(n問題背景問題背景n一棟房子的后面是一個大花園，緊靠樓房的墻一棟房子的后面是一個大花園，緊靠樓房的墻壁有一個溫室。溫室高壁有一個溫室。溫室高3 3米，深入花園米，深入花園2 2米。在米。在溫室的上方有一些窗戶，現(xiàn)在的問題是工人要溫室的上方有一些窗戶，現(xiàn)在的問題是工人要打掃這些窗戶，他可以利用的工具只有一架長打掃這些窗戶，他可以利用的工具只有一架長為為

18、7 7米的梯子，問他能否成功？米的梯子，問他能否成功？n如果不行有什么解決辦法？如果不行有什么解決辦法？n試建立相應(yīng)的數(shù)學(xué)模型以解決上面問題。試建立相應(yīng)的數(shù)學(xué)模型以解決上面問題。案例案例3 3 梯子問題梯子問題()()我們先畫出問題的直觀圖我們先畫出問題的直觀圖( (右右圖圖).).在圖中我們把溫室頂部考慮成在圖中我們把溫室頂部考慮成弓型弓型( (因?yàn)檫@和現(xiàn)實(shí)比較接近因?yàn)檫@和現(xiàn)實(shí)比較接近) )但是但是這樣卻把問題復(fù)雜化了這樣卻把問題復(fù)雜化了, ,實(shí)際求解實(shí)際求解時時, ,為了簡化問題我們可以把它看為了簡化問題我們可以把它看成一個方體成一個方體. .問題分析問題分析()()工人能成功的條件是梯子

19、的兩工人能成功的條件是梯子的兩端能分別搭在墻和花園端能分別搭在墻和花園, ,而且不能而且不能對溫室產(chǎn)生壓力對溫室產(chǎn)生壓力()()題目中的問題其實(shí)是求達(dá)到要求的題目中的問題其實(shí)是求達(dá)到要求的梯子的最短長度梯子的最短長度()()求達(dá)到要求的梯子的最短長度是一個平面幾何問題求達(dá)到要求的梯子的最短長度是一個平面幾何問題, ,我我們可以畫出該直觀圖的截面圖如下們可以畫出該直觀圖的截面圖如下xoydhL1L2剖面圖剖面圖1.溫室是長方體，并且緊靠樓房的墻壁沒有空隙2.花園足夠大并且平整3.溫室的長寬高都不超過樓房的相應(yīng)高度4.只考濾溫室上方的窗戶5.梯子與溫室最多只能挨著，不能產(chǎn)生壓力符號說明符號說明h-

20、溫室高度 d-溫室深入花園的距離L-梯子長度 -梯子與花園表面的夾角L1，L2-梯子在溫室上下方的長度模型假設(shè)模型假設(shè)xoydhL1L2模型建立及求解模型建立及求解由幾何知識可知由幾何知識可知 cos1Ldsin2LhcossincossinsincoshdhdL2sincos2cossinhdddL0ddL3tanhd 2/33/2332232)/(1(coscoscossincossincosmindhddddddL令得此時L最短21LLL模型的應(yīng)用與檢驗(yàn)?zāi)Ｐ偷膽?yīng)用與檢驗(yàn) 將將h=3h=3米米,d=2,d=2米米代入上面的式子有代入上面的式子有L L 7.023487.02348米米, ,

21、既既所需梯子的最短長度為所需梯子的最短長度為7.17.1米，但顯然米，但顯然L7L7米，所以梯米，所以梯子的長度不夠，即工人不能成功。子的長度不夠，即工人不能成功。他要繼續(xù)工作的話必須加長梯子的長度，或在梯子的他要繼續(xù)工作的話必須加長梯子的長度，或在梯子的下端墊一定高度的東西。下端墊一定高度的東西。模型的改進(jìn)方向模型的改進(jìn)方向1.1.考濾溫室頂端為弓型，這樣梯子的長度還要加長考濾溫室頂端為弓型，這樣梯子的長度還要加長 2.2.考慮梯子頂端下方的窗戶，此時由于梯子的傾角變考慮梯子頂端下方的窗戶，此時由于梯子的傾角變小，故梯長同樣加大。小，故梯長同樣加大。森林失火后，要確定派出消防隊員的數(shù)量。森林

22、失火后，要確定派出消防隊員的數(shù)量。隊員多，森林損失小，救援費(fèi)用大；隊員多，森林損失小，救援費(fèi)用大；隊員少，森林損失大，救援費(fèi)用小。隊員少，森林損失大，救援費(fèi)用小。綜合考慮損失費(fèi)和救援費(fèi)，確定隊員數(shù)量。綜合考慮損失費(fèi)和救援費(fèi)，確定隊員數(shù)量。問題問題分析分析問題問題記隊員人數(shù)記隊員人數(shù)x, 失火時刻失火時刻t=0, 開始救火時刻開始救火時刻t1, 滅火時刻滅火時刻t2, 時刻時刻t森林燒毀面積森林燒毀面積B(t). 損失費(fèi)損失費(fèi)f1(x)是是x的的減減函數(shù)函數(shù), 由燒毀面積由燒毀面積B(t2)決定決定. 救援費(fèi)救援費(fèi)f2(x)是是x的的增增函數(shù)函數(shù), 由隊員人數(shù)和救火時間由隊員人數(shù)和救火時間決定決

23、定.存在恰當(dāng)?shù)拇嬖谇‘?dāng)?shù)膞，使，使f1(x), f2(x)之和最小之和最小案例案例4 4 森林救火森林救火 關(guān)鍵是對關(guān)鍵是對B(t)作出合理的簡化假設(shè)作出合理的簡化假設(shè).問題問題分析分析失火時刻失火時刻t=0, 開始救火時刻開始救火時刻t1, 滅火時刻滅火時刻t2, 畫出時刻畫出時刻 t 森林燒毀面積森林燒毀面積B(t)的大致圖形的大致圖形t1t20tBB(t2)分析分析B(t)比較困難比較困難,轉(zhuǎn)而討論森林燒毀轉(zhuǎn)而討論森林燒毀速度速度dB/dt.模型假設(shè)模型假設(shè) 3）f1(x)與與B(t2)成正比，系數(shù)成正比，系數(shù)c1 (燒毀單位面積損失費(fèi)）燒毀單位面積損失費(fèi)） 1）0 t t1, dB/dt 與與 t成正比？成正比？，系數(shù)，系數(shù) (火勢蔓延速度）火勢蔓延速度） 2）t1 t t2, 降為降為 - x ( 為隊員的平均滅火為隊員的