數(shù)學(xué)建模培訓(xùn)之?dāng)?shù)學(xué)規(guī)劃模型課件

數(shù)學(xué)建模MathematicalModelling第一講

數(shù)學(xué)規(guī)劃模型優(yōu)化問題：

現(xiàn)實世界當(dāng)中經(jīng)常遇到的一類問題。最優(yōu)化方法：

解決優(yōu)化問題的數(shù)學(xué)方法。解決優(yōu)化問題的基本步驟：

1)建立優(yōu)化模型;2)利用優(yōu)化方法輔以計算機求解優(yōu)化模型。2)圖與網(wǎng)絡(luò)的優(yōu)化模型運輸問題指派問題最大匹配問題最小覆蓋問題最短路問題最小樹問題行遍性問題(旅行商問題/中國郵遞員問題)網(wǎng)絡(luò)流問題(最大流/最小費用流)計劃網(wǎng)絡(luò)圖優(yōu)化問題3)對策論（博弈論）4)排隊論5)存貯論參考書：▲運籌學(xué)(第3版)，《運籌學(xué)》教材編寫組編，清華大學(xué)出版社,2005▲優(yōu)化建模與LINDO/LINGO軟件，謝金星、薛毅編著，清華大學(xué)出版社,2006例1某公司的甲、乙兩個蔬菜生產(chǎn)基地，產(chǎn)量分別為1200kg和900kg，同時供應(yīng)A、B、C、D四個大型超市，其需要量分別為800kg、500kg、500kg、300kg，而從各基地到各超市運送蔬菜的費用為：試制定一個調(diào)運方案，使總的運費最小.運費(元/kg)

ABCD甲基地

0.210.250.170.15乙基地

0.470.370.160.28例2某食品廠有n種產(chǎn)品A1,A2,…,An，每種產(chǎn)品的單位利潤分別為r1,r2,…,

rn.而生產(chǎn)每種產(chǎn)品所需設(shè)備數(shù)分別為a1,a2,…,

an，所需原料的消耗分別為b1,b2,…,bn，所需勞動力分別為c1,c2,…,cn.該廠現(xiàn)有的設(shè)備、原料和勞動力的總數(shù)分別為a,b,c，產(chǎn)品在市場上的需求量分別不超過q1,q2,…,

qn

.該廠若要獲得最大利潤，應(yīng)如何制定生產(chǎn)計劃？數(shù)學(xué)規(guī)劃(MathematicalProgramming)線性規(guī)劃(LinearProgramming,LP)其中c=(c1,…,cn)T,x=(x1,…,xn)T，b=(b1,…,bm)T.標(biāo)準(zhǔn)形線性規(guī)劃的求解5x1+4x2=24Q2Q1Q3Q42x1+5x2=15x2-x1=1Ox1x25x1+10x2=z例1線性規(guī)劃的基本性質(zhì)（1）若LP存在可行域，則其可行域為凸集（凸多面體）；（2）x為LP的基可行解的充分必要條件是x為其可行域的極點（頂點）；（3）若LP存在最優(yōu)解，則其最優(yōu)解一定在其可行域的極點上得到。求解線性規(guī)劃：（1）求基可行解（可行域的極點）；（2）在基可行解中尋找最優(yōu)解。單純形算法從某個基可行解出發(fā)，通過迭代法沿目標(biāo)函數(shù)值下降最快的方向求另一個基可行解。經(jīng)有限次迭代，便可得到LP的最優(yōu)解。數(shù)學(xué)規(guī)劃其中x=(x1,…,xn)T,g(x)=(g1(x

),…,gm(x))T,而

S={x|g(x)0}

Rn為該數(shù)學(xué)規(guī)劃的可行域。非線性規(guī)劃(NonlinearProgramming,NLP)或設(shè)x*S，而xS有f(x)

f(x*)，則稱x*為NLP的全局最優(yōu)解，f(x*)為NLP的全局最優(yōu)值(全局極小值)。非線性規(guī)劃設(shè)x*S，若U(x*)使xU(x*)∩S，有f(x)

f(x*)，則稱x*為NLP的局部最優(yōu)解，f(x*)為NLP的局部最優(yōu)值(局部極小值)。

設(shè)SRn，x*S，f(x)在x*處取得局部極值的必要條件為

f(x*)==0；f(x)在x*處取得局部極小值的充分條件為

f(x*)=0，且2f(x*)=正定。數(shù)值迭代法無約束NLP的求解

Step2對于第k次迭代解x(k)，確定一個搜索方向p(k)Rn，并在此方向上確定搜索步長tkR，令

x(k+1)=

x(k)+tkp(k)，使

f(x(k+1))

f(x(k))；若可行域S=Rn：無約束NLP；否則SRn：帶約束NLP。Step1選擇初始解x(0)；

Step3若x(k+1)滿足給定的迭代終止準(zhǔn)則，停止迭代，最優(yōu)解x*=x(k+1)；否則，轉(zhuǎn)Step2。非線性規(guī)劃帶約束NLP的求解兩種途徑：可行域內(nèi)直接尋優(yōu)約束問題化為無約束問題求解1.可行方向法：可行方向：設(shè)

xS，若0，使t[0,]均有x+t

pS,則方向p稱為x的一個可行方向；迭代時取p(k)為可行下降方向，即取p(k)同時滿足下降方向：設(shè)

xS，若0，使t[0,]均有

f(x+t

p)

f(x),則方向p稱為x的一個下降方向；f(x(k))Tp(k)0gj

(x(k))Tp(k)

0，j{j|gj

(x(k))=0,1

jm}2.罰函數(shù)法：利用目標(biāo)函數(shù)f(x)和約束函數(shù)g(x)構(gòu)造帶參數(shù)的“增廣”目標(biāo)函數(shù)，將約束NLP

轉(zhuǎn)化為一系列無約束NLP來求解：minF(x)=f(x)+Pk(x)其中Pk(x)為由g(x)構(gòu)成的“懲罰”函數(shù)。外部罰函數(shù)法：取Pk(x)=Mk內(nèi)部罰函數(shù)法：取Pk(x)=rk其中0M1M2

…

Mk

…為選取的單增趨于無窮的數(shù)列其中r1r2

…

rk

…

0

為選取的單減趨于0的數(shù)列現(xiàn)代優(yōu)化的計算方法：（除經(jīng)典的規(guī)劃求解方法外）局部搜索和禁忌搜索算法模擬退火算法遺傳算法蟻群算法人工神經(jīng)網(wǎng)絡(luò)基本假設(shè)

1.投資數(shù)額M相當(dāng)大；2.投資越分散總的風(fēng)險越?。?.總體風(fēng)險用所投資項目Si中最大的風(fēng)險來度量；4.n種資產(chǎn)Si之間相互獨立；5.在投資期間，ri,pi,qi為定值，不受意外因素影響；6.凈收益和總體風(fēng)險只受ri,pi,qi影響，不受其他因素干擾.風(fēng)險度

收益

x0x1

x2

x3x40.00600.20190.00000.24000.40000.10910.2212?例2.

洗衣機的節(jié)水設(shè)計(CUMCM96B).我國淡水資源有限，節(jié)約用水人人有責(zé)。洗衣在家庭用水中占有相當(dāng)大的份額，節(jié)約洗衣機的用水十分重要。假設(shè)在放入衣物和洗滌劑后洗衣機的運行過程為：加水－漂洗－脫水－加水－漂洗－脫水－…－加水－漂洗－脫水(稱“加水－漂洗－脫水”為運行“一輪”)。請為洗衣機設(shè)計一種程序(包括運行多少輪，每輪加水量等)，使得在滿足一定洗滌效果的條件下，總的用水量最少。選用合理的數(shù)據(jù)進行計算?；炯僭O(shè)1）僅考慮離散的洗滌方案，即“加水－漂洗－脫水”三個環(huán)節(jié)是分離的，這三個環(huán)節(jié)構(gòu)成一個洗滌周期，稱為“一輪”；2）節(jié)水洗滌程序設(shè)計只考慮洗滌的輪數(shù)和加水量；3）每輪用水量不能低于L，以保證洗衣機工作，不能高于H，否則水會溢出，顯然不節(jié)水；4）每輪漂洗時間足夠，以使衣物上的污物充分溶解水中，使每輪的加水被充分利用；5）每輪脫水時間足夠，以使污水充分脫出，即衣物中所含的污水量達到一個低限c，設(shè)0cL

；變量1）漂洗共進行n

輪，k=0,1,2,…n–1；2）第k輪用水量為uk，k=0,1,2,…n–1；3）衣物上的初始污物量為x0，第k輪脫水后衣物上附著的污物量為xk+1，k=0,1,2,…n–1.仿真計算數(shù)據(jù)：取=10–3，L/H=0.25，c/H=10–5結(jié)果：Q

n

vkvk0.9921.95630.978232.72730.909143.32190.830553.78190.756464.14410.690774.43510.633684.67320.584294.87140.5413105.03860.5386Qnvkvk0.9921.95630.97820.9532.84210.94740.9033.65640.91350.8543.86900.96730.8054.68010.93600.7065.86100.97680.6087.71080.96380.50109.97640.9976隨機變量的概率分布

r項分布泊松分布超幾何分布幾何分布均勻分布指數(shù)分布正態(tài)分布（高斯分布）巴斯卡分布伽瑪分布貝塔分布對數(shù)正態(tài)分布威布爾分布概率分布的實例

一段時間內(nèi)，電話交換機接收到的用戶呼叫次數(shù)，公共汽車站來到的候車乘客數(shù)，超市中排隊等待付款的顧客數(shù)，隨機服務(wù)窗口接待的人數(shù)，某種放射性物質(zhì)放射的粒子數(shù)，顯微鏡下落在某區(qū)域的微生物數(shù)目，昆蟲的產(chǎn)卵數(shù)目，事故、故障、災(zāi)害性事件的數(shù)目，一個產(chǎn)品的疵點數(shù)等都服從泊松分布；泊松分布是二項分布的極限分布；貝努利概型是二項分布的實際背景，例如有限總體的有放回抽樣的次品數(shù)目服從二項分布；而不放回抽樣的次品數(shù)目服從超幾何分布；隨機到達車站的乘客的候車時間，定點數(shù)值計算中四舍五入的舍入誤差等服從均勻分布；貝努利試驗中事件A首次發(fā)生時的試驗次數(shù)服從幾何分布；無線電元器件和玻璃器皿等的壽命，動物的壽命，電話問題中的通話時長，隨機服務(wù)窗口的服務(wù)時間等服從指數(shù)分布；工業(yè)中機電產(chǎn)品（如軸承、刀具等）的壽命常服從威布爾分布；測量誤差，工業(yè)產(chǎn)品的尺寸、強度等質(zhì)量指標(biāo)，人體的身高、體重，農(nóng)作物的產(chǎn)量，炮彈的彈落點的分布，氣象中的月氣溫、月濕度、月降水量，考試的成績分布等都服從正態(tài)分布；二項分布的極限分布是正態(tài)分布；一般地，眾多獨立的影響因素的綜合作用結(jié)果往往服從或近似服從正態(tài)分布；絕緣材料的壽命，設(shè)備故障的維修時間，一個家庭中兩個孩子的年齡之差等服從對數(shù)正態(tài)分布；隨機變(向)量的特征數(shù)數(shù)學(xué)期望方差/標(biāo)準(zhǔn)差變異系數(shù)偏度系數(shù)峰度系數(shù)協(xié)方差相關(guān)系數(shù)特征數(shù)由分布決定，與分布的參數(shù)有關(guān)。例1自動化車床管理

一道工序用自動化車床連續(xù)加工某種零件，由于刀具損壞等原因該工序會出現(xiàn)故障，其中刀具損壞故障占95%,其它故障僅占5%。工序出現(xiàn)故障完全隨機,假定在生產(chǎn)任一零件時出現(xiàn)故障的機會均相同。工作人員通過檢查零件來確定工序是否出現(xiàn)故障?，F(xiàn)有100次刀具故障記錄，故障出現(xiàn)時該刀具完成的零件數(shù)如附表。假設(shè)在刀具加工一定件數(shù)后定期更換新刀具。已知生產(chǎn)工序的費用參數(shù)如下：故障時產(chǎn)出的零件損失費用200元/件；進行檢查的費用10元/次；發(fā)現(xiàn)故障進行調(diào)節(jié)使恢復(fù)正常的平均費用3000元/次(包括刀具費)；未發(fā)現(xiàn)故障時更換一把新刀具的費用1000元/次。假定工序故障時產(chǎn)出的零件均為不合格品，正常時產(chǎn)出的零件均為合格品,試對該工序設(shè)計效益最好的檢查間隔（生產(chǎn)多少零件檢查一次）和刀具更換策略。附:100次刀具故障記錄(完成的零件數(shù))

4593626245425095844337488155056124524349826407425657065936809266531644877346084281153593844527552513781474388824538862659775859755649697515628954771609402960885610292837473677358638699634555570844166061062484120447654564339280246687539790581621724531512577496468499544645764558378765666763217715310851例2彩票中的數(shù)學(xué)

近年流行的彩票主要有“傳統(tǒng)型”和“樂透型”兩種類型?！皞鹘y(tǒng)型”采用“10選6+1”方案：先從6組0~9號球中搖出6個基本號碼，每組搖出一個，然后從0~4號球中搖出一個特別號碼，構(gòu)成中獎號碼。投注者從0~9十個號碼中任選6個基本號碼(可重復(fù))，從0~4中選一個特別號碼，構(gòu)成一注，根據(jù)單注號碼與中獎號碼相符的個數(shù)多少及順序確定中獎等級。以中獎號碼“abcdef+g”為例說明中獎等級，如表1(X表示未選中的號碼)。中獎等級10選6+1（6+1/10）基本號碼特別號碼說明一等獎abcdefg選7中（6+1）二等獎abcdef選7中（6）三等獎abcdeXXbcdef選7中（5）四等獎abcdXXXbcdeXXXcdef選7中（4）五等獎abcXXXXbcdXXXXcdeXXXXdef選7中（3）六等獎abXXXXXbcXXXXXcdXXXXXdeXXXXXef選7中（2）

“樂透型”有多種形式，比如“33選7”的方案：先從01~33個號碼中一個個地搖出7個基本號，再從剩余的26個號碼中搖出一個特別號碼。投注者從01~33個號碼中任選7個組成一注(不可重復(fù))，根據(jù)單注號碼與中獎號碼相符的個數(shù)多少確定相應(yīng)的中獎等級，不考慮號碼順序；又如“36選6+1”的方案，先從01~36個號碼球中一個個地搖出6個基本號，再從剩下的30個號碼球中搖出一個特別號碼。從01~36個號碼中任選7個組成一注(不可重復(fù))，根據(jù)單注號碼與中獎號碼相符的個數(shù)多少確定相應(yīng)的中獎等級，不考慮號碼順序。這兩種方案的中獎等級如表2。中獎等級33選7（7/33）36選6+1（6+1/36）基本號碼特別號碼說明基本號碼特別號碼說明一等獎●●●●●●●選7中（7）●●●●●●★選7中（6+1）二等獎●●●●●●○

★選7中（6+1）●●●●●●

選7中（6）三等獎●●●●●●○選7中（6）●●●●●○★選7中（5+1）四等獎●●●●●○○★選7中（5+1）●●●●●○選7中（5）五等獎●●●●●○○選7中（5）●●●●○○★選7中（4+1）六等獎●●●●○○○★選7中（4+1）●●●●○○選7中（4）七等獎●●●●○○○選7中（4）●●●○○○★選7中（3+1）根據(jù)這些方案的具體情況，綜合分析各種獎項出現(xiàn)的可能性、獎項和獎金額的設(shè)置以及對彩民的吸引力等因素評價各方案的合理性。例3.

零件的參數(shù)設(shè)計(CUMCM97A).

一件產(chǎn)品由若干零件組裝而成,標(biāo)志產(chǎn)品性能的某個參數(shù)取決于這些零件的參數(shù).零件參數(shù)包括標(biāo)定值和容差兩部分.進行成批生產(chǎn)時,標(biāo)定值表示一批零件的該參數(shù)的平均值,容差則給出了參數(shù)偏離其標(biāo)定值的容許范圍.若將零件參數(shù)視為隨機變量,則標(biāo)定值代表期望值,在生產(chǎn)部門無特殊要求時,容差通常規(guī)定為均方差的3倍.

進行零件參數(shù)設(shè)計,就是要確定其標(biāo)定值和容差.這時要考慮兩方面因素:一是當(dāng)各零件組裝成產(chǎn)品時,如果產(chǎn)品參數(shù)偏離預(yù)先設(shè)定的目標(biāo)值,就會造成質(zhì)量損失,偏離越大,損失越大;二是零件容差的大小決定了其制造成本,容差設(shè)計得越小,成本越高.

下面是一個具體的零件參數(shù)的設(shè)計問題.

粒子分離器的某參數(shù)(記作y

)由7個零件的參數(shù)(記作x1,

x2,…,x7

)決定,經(jīng)驗公式為

y

的目標(biāo)值(記作y0)為1.50.當(dāng)y

偏離y0±0.1時,產(chǎn)品為次品,質(zhì)量損失為1