數(shù)學(xué)建模優(yōu)化部分

大學(xué)生數(shù)學(xué)建模競賽張朝倫1/7/20231什么是數(shù)學(xué)建模？數(shù)學(xué)建模用數(shù)學(xué)去解決實際問題就一定要用數(shù)學(xué)的語言、方法去近似地刻劃該實際問題，而這種刻劃的數(shù)學(xué)表述就是一個數(shù)學(xué)模型，其過程就是數(shù)學(xué)建模的過程?！皩ΜF(xiàn)實的現(xiàn)象通過心智活動構(gòu)造出能抓住重要且有特征的表示，常常是形象化的或符號的表示”1/7/20232數(shù)學(xué)建模是指對現(xiàn)實世界的一特定對象,為了某特定目的,做出一些重要的簡化和假設(shè),用適當(dāng)?shù)臄?shù)學(xué)工具得到一個數(shù)學(xué)結(jié)構(gòu),用它來解釋特定現(xiàn)象的現(xiàn)實性態(tài),預(yù)測對象的未來狀況,提供處理對象的優(yōu)化決策和控制,設(shè)計滿足某種需要的產(chǎn)品等。從科學(xué)，工程，經(jīng)濟，管理等角度看數(shù)學(xué)建模就是用數(shù)學(xué)的語言和方法，通過抽象，簡化建立能近似刻畫并“解決”實際問題的一種強有力的數(shù)學(xué)工具。顧名思義，modelling一詞在英文中有“塑造藝術(shù)”的意思，從而可以理解從不同的側(cè)面，角度去考察問題就會有不盡的數(shù)學(xué)模型，從而數(shù)學(xué)建模的創(chuàng)造又帶有一定的藝術(shù)的特點。而數(shù)學(xué)建模最重要的特點是要接受實踐的檢驗，多次修改模型漸趨完善的過程。1/7/20233大學(xué)生數(shù)學(xué)建模競賽的由來

1985年在美國出現(xiàn)了一種叫做MCM的一年一度的大學(xué)生模型競賽。以前只有一種大學(xué)生數(shù)學(xué)競賽—普特南數(shù)學(xué)競賽：是由美國數(shù)學(xué)協(xié)會主持于每年12月的第一個星期六分兩試進行，每試6題，每試各為3小時。這是一個歷史悠久、影響很大的全美大學(xué)生數(shù)學(xué)競賽（1938年開始至今）。主要考核基礎(chǔ)知識和訓(xùn)練、邏輯推理的能力、思維敏捷、計算能力等。1/7/20234為什么會產(chǎn)生另一種數(shù)學(xué)模型競賽？1、參加普特南數(shù)學(xué)競賽是要有訓(xùn)練的，而很多學(xué)校的參賽隊員素質(zhì)差、受訓(xùn)時間時間短、沒有經(jīng)驗，因而成績差，影響了積極性。2、相當(dāng)多的學(xué)生對數(shù)學(xué)的實際應(yīng)用有興趣，因而對普特南數(shù)學(xué)競賽缺乏積極性。3、為了反對現(xiàn)行高校數(shù)學(xué)教學(xué)中過份強調(diào)純粹性、形式方法、缺乏應(yīng)用內(nèi)容的傾向。4、普特南數(shù)學(xué)競賽不用計算機。5、數(shù)學(xué)有如下幾個重要組成部分：應(yīng)用數(shù)學(xué)、計算數(shù)學(xué)、統(tǒng)計數(shù)學(xué)、純粹數(shù)學(xué)。1/7/20235MCM的宗旨、規(guī)則和獎勵

宗旨：鼓勵大學(xué)師生對范圍并不固定的各種實際問題給予闡明、分析并提出解法，通過這樣一種結(jié)構(gòu)鼓勵師生積極參與并強調(diào)實現(xiàn)完整的模型構(gòu)造的過程

規(guī)則：每個參賽隊（3人）有一名指導(dǎo)教師，他（或她）在比賽開始前負責(zé)對隊員的訓(xùn)練和戰(zhàn)術(shù)指導(dǎo)；并接受考題，然后即由自行參賽。指導(dǎo)教師不得參賽

比賽于每年二月或三月的某個周末（三天時間）。每次只有兩個考題（一般1/7/20236連續(xù)和離散各一題），每隊只需任選一題。

考題是由在政府部門或工業(yè)工作的數(shù)學(xué)家提出建義由命題組選擇的沒有固定范圍的實際問題。一般來源于工程技術(shù)和管理科學(xué)等方面經(jīng)過適當(dāng)簡化加工的實際問題，不要求參賽者預(yù)先掌握深入的專門知識，只需要學(xué)過普通高校的數(shù)學(xué)課程。題目有較大的靈活性供參賽者發(fā)揮其創(chuàng)造能力。參賽者應(yīng)根據(jù)題目要求，完成一篇包括模型假設(shè)、建立和求解、計算方法的設(shè)計和計算機實現(xiàn)、結(jié)果的分析和檢驗、模型的改進等方面的論文（即答卷）。競賽評獎以假設(shè)的合理性、建模的創(chuàng)造性、結(jié)果的正確性和文字表述的清晰程度為主要標(biāo)準(zhǔn)。

1/7/20237

MCM的發(fā)展歷程

1985年第一屆70所大學(xué)90個隊到1992年189所大學(xué)292個隊。

1989年我國開始組隊參加，到92年國內(nèi)有12所大學(xué)以致24個隊參賽。

1989年我國開始組隊參加，到92年國內(nèi)有12所大學(xué)24個隊參賽。上海市率先于1990年12月7—9日舉辦了“上海市大學(xué)生（數(shù)學(xué)類）數(shù)學(xué)建模競賽”。于1991年6月7日—9日舉辦了“上海市大學(xué)生（非數(shù)學(xué)類）數(shù)學(xué)建模競賽”。接下來是西安市。由中國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會舉辦了“1992年全國大學(xué)生數(shù)學(xué)模型聯(lián)賽”。CUMCM就這樣誕生了

從1994年開始CUMCM被國家教委高教司確定為面向全國大學(xué)生的一項競賽。1/7/20238數(shù)模競賽是由美國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會在1985年發(fā)起的一項大學(xué)生競賽活動，目的在于激勵學(xué)生學(xué)習(xí)數(shù)學(xué)的積極性，提高學(xué)生建立數(shù)學(xué)模型和運用計算機技術(shù)解決實際問題的綜合能力，鼓勵廣大學(xué)生踴躍參加課外科技活動，開拓知識面，培養(yǎng)創(chuàng)精神及合作意識，推動大學(xué)數(shù)學(xué)教學(xué)體系、教學(xué)內(nèi)容和方法的改革。我國大學(xué)生數(shù)學(xué)建模競賽是由教育部高教司和中國工業(yè)與數(shù)學(xué)學(xué)會主辦、面向全國高等院校的、每年一屆的通訊競賽。其宗旨是：創(chuàng)新意識、團隊精神、重在參與、公平競爭。１９９２年在中國創(chuàng)辦，自從創(chuàng)辦以來，得到了教育部高教司和中國工業(yè)與應(yīng)用數(shù)學(xué)協(xié)會的得力支持和關(guān)心，呈現(xiàn)出迅速的發(fā)展發(fā)展勢頭，就２００３年來說，報名階段須然受到“非典”影響，但是全國３０個省（市、自治區(qū)）及香港的637所院校就有5406隊參賽，在職業(yè)技術(shù)學(xué)院增加更快，

2005年的759所院校就有8492隊參賽。2006年全國有31個省/市/自治區(qū)(包括香港)864所院校、9985個隊（其中甲組7682隊、乙組2303隊）、近3萬名來自各個專業(yè)的大學(xué)生參加競賽，是歷年來參賽人數(shù)最多的！可以說：數(shù)學(xué)建模已經(jīng)成為全國高校規(guī)模最大課外科技活動。1/7/20239

建模的步驟

建模是一種十分復(fù)雜的創(chuàng)造性勞動，現(xiàn)實世界中的事物形形色色，五花八門，不可能用一些條條框框規(guī)定出各種模型如何具體建立，這里只是大致歸納一下建模的一般步驟和原則：

1）模型準(zhǔn)備：首先要了解問題的實際背景，明確題目的要求，收集各種必要的信息．

2）模型假設(shè)：為了利用數(shù)學(xué)方法，通常要對問題做必要的、合理的假設(shè)，使問題的主要特征凸現(xiàn)出來，忽略問題的次要方面。

３）模型構(gòu)成：根據(jù)所做的假設(shè)以及事物之間的聯(lián)系，構(gòu)造各種量之間的關(guān)系把問題化

1/7/202310４）模型求解：利用已知的數(shù)學(xué)方法來求解上一步所得到的數(shù)學(xué)問題，此時往往還要作出進一步的簡化或假設(shè)。為數(shù)學(xué)問題，注意要盡量采用簡單的數(shù)學(xué)工具。

５）模型分析：對所得到的解答進行分析，特別要注意當(dāng)數(shù)據(jù)變化時所得結(jié)果是否穩(wěn)定。

６）模型檢驗：分析所得結(jié)果的實際意義，與實際情況進行比較，看是否符合實際，如果不夠理想，應(yīng)該修改、補充假設(shè)，或重新建模，不斷完善。

７）模型應(yīng)用：所建立的模型必須在實際應(yīng)用中才能產(chǎn)生效益，在應(yīng)用中不斷改進和完善。1/7/2023111/7/202312模型的分類按模型的應(yīng)用領(lǐng)域分類

生物數(shù)學(xué)模型

醫(yī)學(xué)數(shù)學(xué)模型

地質(zhì)數(shù)學(xué)模型

數(shù)量經(jīng)濟學(xué)模型

數(shù)學(xué)社會學(xué)模型

按是否考慮隨機因素分類

確定性模型

隨機性模型按是否考慮模型的變化分類

靜態(tài)模型

動態(tài)模型按應(yīng)用離散方法或連續(xù)方法

離散模型

連續(xù)模型按建立模型的數(shù)學(xué)方法分類

幾何模型

微分方程模型

圖論模型

規(guī)劃論模型

馬氏鏈模型1/7/202313按人們對事物發(fā)展過程的了解程度分類

白箱模型：

指那些內(nèi)部規(guī)律比較清楚的模型。如力學(xué)、熱學(xué)、電學(xué)以及相關(guān)的工程技術(shù)問題。

灰箱模型：

指那些內(nèi)部規(guī)律尚不十分清楚，在建立和改善模型方面都還不同程度地有許多工作要做的問題。如氣象學(xué)、生態(tài)學(xué)經(jīng)濟學(xué)等領(lǐng)域的模型。

黑箱模型：

指一些其內(nèi)部規(guī)律還很少為人們所知的現(xiàn)象。如生命科學(xué)、社會科學(xué)等方面的問題。但由于因素眾多、關(guān)系復(fù)雜，也可簡化為灰箱模型來研究。1/7/202314數(shù)學(xué)建模應(yīng)用今天，在國民經(jīng)濟和社會活動的以下諸多方面，數(shù)學(xué)建模都有著非常具體的應(yīng)用。

分析與設(shè)計

例如描述藥物濃度在人體內(nèi)的變化規(guī)律以分析藥物的療效；建立跨音速空氣流和激波的數(shù)學(xué)模型，用數(shù)值模擬設(shè)計新的飛機翼型。

預(yù)報與決策

生產(chǎn)過程中產(chǎn)品質(zhì)量指標(biāo)的預(yù)報、氣象預(yù)報、人口預(yù)報、經(jīng)濟增長預(yù)報等等，都要有預(yù)報模型。使經(jīng)濟效益最大的價格策略、使費用最少的設(shè)備維修方案，是決策模型的例子。

1/7/202315控制與優(yōu)化

電力、化工生產(chǎn)過程的最優(yōu)控制、零件設(shè)計中的參數(shù)優(yōu)化，要以數(shù)學(xué)模型為前提。建立大系統(tǒng)控制與優(yōu)化的數(shù)學(xué)模型，是迫切需要和十分棘手的課題。

規(guī)劃與管理

生產(chǎn)計劃、資源配置、運輸網(wǎng)絡(luò)規(guī)劃、水庫優(yōu)化調(diào)度，以及排隊策略、物資管理等，都可以用運籌學(xué)模型解決。1/7/202316大學(xué)生數(shù)學(xué)建模競賽試題題目

85年：動物群體的管理戰(zhàn)略物資儲備問題

86年：對海底地型的插值選取兩個應(yīng)急設(shè)施的最優(yōu)方案87年：鹽堆穩(wěn)定性問題停車場安排問題

88年：毒品走私船問題平板列車車廂的優(yōu)化裝載1/7/20231789年：最佳分類隔離飛機排隊模型90年：腦中多巴胺的分布鏟雪車的路徑問題；鏟雪效率問題91年：估計水塔的水流量尋找最優(yōu)Steiner樹92年：確定航空控制雷達系統(tǒng)的功效緊急修復(fù)系統(tǒng)的研制1/7/20231895年：一個飛行管理模型天車與冶煉爐的調(diào)度93年：混合物轉(zhuǎn)化為有機肥的最隹過程煤炭裝卸場的最優(yōu)操作94年:逢山開路

鎖具裝箱1/7/20231997年：零件參數(shù)的設(shè)計截斷切割98年：災(zāi)情巡視路線投資的收益與風(fēng)險99年：自動化車床管理鉆探布點96年：最優(yōu)捕魚策略節(jié)水洗衣機 1/7/2023202000年：DNA序列分類鋼管訂購和運輸2001年：血管的三維重建公交車的調(diào)度2002年：車燈線光源的優(yōu)化設(shè)計彩票中的數(shù)學(xué)2003年：關(guān)于sars控制和預(yù)測礦山車輛調(diào)度2004年：奧運會臨時超市網(wǎng)點設(shè)計電力市場的輸電阻塞管理1/7/2023212005年：長江水質(zhì)的評價和預(yù)測

DVD在線租賃2006年：出版社的資源配置艾滋病療法的評價及療效的預(yù)測2007年：中國人口增長預(yù)測

乘公交，看奧運

2008年：數(shù)碼相機定位高等教育學(xué)費標(biāo)準(zhǔn)探討

1/7/202322分以下幾個部分一、線性規(guī)劃二、靈敏度分析三、動態(tài)規(guī)劃四、圖及網(wǎng)絡(luò)五、多目標(biāo)規(guī)劃1/7/202323一、線性規(guī)劃

1.線性規(guī)劃問題的數(shù)學(xué)模型

2.兩個變量問題的圖解法

3.線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式及解的概念

3.1標(biāo)準(zhǔn)形式

3.2將非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式

3.3有關(guān)解的概念1/7/202324運籌學(xué)

OperationalResearch運籌帷幄，決勝千里史記《張良傳》1/7/202325目錄緒論第一章線性規(guī)劃問題及單純型解法第二章線性規(guī)劃的對偶理論及其應(yīng)用第三章運輸問題數(shù)學(xué)模型及其解法第四章整數(shù)規(guī)劃第五章動態(tài)規(guī)劃第六章圖與網(wǎng)路分析第七章隨機服務(wù)理論概論第八章生滅服務(wù)系統(tǒng)第九章特殊隨機服務(wù)系統(tǒng)第十章存儲理論1/7/202326緒論一、運籌學(xué)的起源與發(fā)展二、運籌學(xué)的特點及研究對象三、運籌學(xué)解決問題的方法步驟四、運籌學(xué)的發(fā)展趨勢1/7/202327一、運籌學(xué)的起源與發(fā)展起源于二次大戰(zhàn)的一門新興交叉學(xué)科與作戰(zhàn)問題相關(guān)如雷達的設(shè)置、運輸船隊的護航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等英國稱為OperationalResearch美國稱為OperationsResearch戰(zhàn)后在經(jīng)濟、管理和機關(guān)學(xué)校及科研單位繼續(xù)研究1952年，Morse和Kimball出版《運籌學(xué)方法》1948年英國首先成立運籌學(xué)會1952年美國成立運籌學(xué)會1959年成立國際運籌學(xué)聯(lián)合會(IFORS)我國于1982年加入IFORS，并于1999年8月組織了第15屆大會1/7/202328二、運籌學(xué)的特點及研究對象運籌學(xué)的定義為決策機構(gòu)對所控制的業(yè)務(wù)活動作決策時，提供以數(shù)量為基礎(chǔ)的科學(xué)方法——Morse和Kimball運籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個科學(xué)的系統(tǒng)模式，并運用這種模式預(yù)測，比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策——英國運籌學(xué)會運籌學(xué)是應(yīng)用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理——中國百科全書現(xiàn)代運籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為ManagementScience1/7/202329二、運籌學(xué)的特點及研究對象運籌學(xué)的分支數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、目標(biāo)規(guī)劃等圖論與網(wǎng)路理論隨機服務(wù)理論：排隊論存儲理論決策理論對策論系統(tǒng)仿真：隨機模擬技術(shù)、系統(tǒng)動力學(xué)可靠性理論金融工程1/7/202330三、運籌學(xué)解決問題的方法步驟明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果簡化？滿意？YesNoNo1/7/202331四、運籌學(xué)的發(fā)展趨勢運籌學(xué)的危機脫離實際應(yīng)用，陷入數(shù)學(xué)陷阱IT對運籌學(xué)的影響MIS,DSS,MRP-II,CIMS,ERPORDept.-->Dept.OfOR&IS運籌學(xué)與行為科學(xué)結(jié)合群決策和談判對策理論多層規(guī)劃合理性分析服務(wù)行業(yè)中的應(yīng)用金融服務(wù)業(yè)信息、電信服務(wù)業(yè)醫(yī)院管理1/7/202332四、運籌學(xué)的發(fā)展趨勢軟計算面向強復(fù)雜系統(tǒng)的計算、實時控制、知識推理智能算法：模擬退火、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、戒律算法等系統(tǒng)仿真面向問題后勤(Logistics)全球供應(yīng)鏈管理電子商務(wù)：集成特性隨機和模糊OR問題本身的不確定性人類知識的局限性1/7/2023331.2線性規(guī)劃問題的單純型解法1.2.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式為了使線性規(guī)劃問題的解法標(biāo)準(zhǔn)，就要把一般形式化為標(biāo)準(zhǔn)形式1/7/202334(一)、運輸問題例1、設(shè)某產(chǎn)品有m個產(chǎn)地A1,A2,…,Am,n個銷地B1，B2，…,Bn。各產(chǎn)地的產(chǎn)量，各銷地的銷量以及各產(chǎn)地運往各銷地的單位運價如下表,且設(shè)=.問在滿足各地需求以及生命能力的情況下，如何調(diào)運使總運費最小。

1/7/202335

銷地運價產(chǎn)地

B1B2...Bn產(chǎn)量A1c11c12

...c1na1A2c21c22

...c2na2

...

...

...

...

...

...Amcm1cm2

...

cmnam需求量b1b2

...

bn1/7/202336解設(shè)xij表示產(chǎn)地Ai運往銷地Bj的數(shù)量，則可得線性規(guī)劃模型如下：1/7/202337(二)、分派問題例設(shè)有工作m件，人員ｍ個,且一人做一件工作,第i人做j件工作的時間（或費用）為cij,，問如何分派這些人員使總時間（或費用）最少。解1，第i人做第j件工作，

設(shè)xij=0,否則

則得0-1規(guī)劃：

1/7/202338(三)、網(wǎng)絡(luò)問題

一個網(wǎng)絡(luò)包括一些結(jié)點（用圓圈表示），每個結(jié)點由幾條?。ㄓ眉^表示）與其它結(jié)點相連，如圖：

2154

20128915107

141081231361/7/202339最短路問題解：設(shè)1,有從i到期j的弧

xij=0,否則則得0-1規(guī)劃：Minz=20x12+14x13+15x24+12x25+10x34+13x36+8x45+9x47+8x56+10x57+12x67(總路程）S.t.X12+x13=1(從1出發(fā)的汽車為一輛）-x12+x24+x25=0-x13+x34+x36=0-x24-x34+x45+x47=01/7/202340-x25-x45+x56+x57=0-x36-x56+x67=0-x47-x57-x67=-1（到達7的汽車為一輛）Xij=0,或1,i,j=1,2,…7.1/7/202341(四)、生產(chǎn)活動問題例：某公司有m種資源B1，B2，…，Bm(如機器的可用工時，勞力，原材料等），生產(chǎn)n種不同的產(chǎn)品A1，A2，．．．Ａn.其單位消耗，單位利潤等如表．問如何安排生產(chǎn)使利潤最大．解設(shè)xj表示第j種產(chǎn)品的產(chǎn)量，則可得線性規(guī)劃模型：1/7/202342

產(chǎn)單品耗資源Ａ１，Ａ２，…,Ａn

資源量Ｂ１Ｂ２．．．Ｂma11a12…a1na21a22…a2n.....…...….am1am2…amn

b1b2...

bm單位利潤

c1c2…cn1/7/202343注1若還要考慮固定成本，則需引入0–1變量。設(shè)第j種產(chǎn)品的固定成本為Mj，第j種產(chǎn)品的產(chǎn)量的上界為Lj引入0–1變量

0,生產(chǎn)第j種產(chǎn)品，

Yj=1，否則1/7/202344注2如果某些資源的使用是有選擇的，即有些約束條件是互相排斥的，可引入0–1變量將其統(tǒng)一在同一模型中。如b1,b2為不同型號的兩臺機器的可用工時，而n種產(chǎn)品可在任一臺上加工，這時第1，2兩個約束條件就是互排斥的，只能選擇一個進入模型。如果引入0–1變量1/7/202345

0,在型號i的機器上加工Yi=（i=1,2)1,否則則可以用下述條件來將它們統(tǒng)一同一個模型中：1/7/202346(五)、選址問題例、某公司擬定在東、西、南三區(qū)建立門市部，擬議中有7個地址A1，A2，…,A7可供選擇，并規(guī)定：在東區(qū)，A1，A2，A3中至多選兩個；在西區(qū)，A4，A5中至少選一個；在南區(qū)，A6，A7中至少選一個；若選Ai,投資bi元，每年可獲利估計為ci元,總投資不超過b元.問如何選擇門市部的地址公司的年利潤最大.

1/7/202347解設(shè)1，選擇Ai,xi=0，否則則得0-1規(guī)劃模型：1/7/202348(六)、曲線擬合問題例已知變量y隨變量x變化，并且已知一組觀測值（xi,yi),I=1,2,…n.(1)擬合一條回歸直線,使回歸值與觀察值的絕對偏差之和最小;(2)擬合一條回歸直線,使回歸值與觀察值的最大偏差最小.1/7/202349解設(shè)所求回歸直線方程為

y=a+bx(1)據(jù)題意，應(yīng)求使最小的a,b。由于函數(shù)中帶有絕對值，不便用數(shù)學(xué)分析方法來處理，但用線性規(guī)劃方法來處理就變得較容易。令則得線性規(guī)劃模型

1/7/202350模型中，xi,yi已知，ui,vi,a,b為決策變量。原問題化為含（2n+2)個決策變量，n個約束方程的一極小化問題。1/7/202351(七)、人員安排問題例某公司的營業(yè)時間是上午8點到22點，以兩小時為一時段，各時段內(nèi)所需的服務(wù)人員數(shù)如下表，每個服務(wù)人員可在任一時段開始上班，但要工作8小時，而工資都相同。問應(yīng)如何安排服務(wù)人員使公司所付工資總數(shù)最少。1/7/202352序號時間區(qū)間需求人數(shù)1

8：00—10：00

202

10：00—12：00

25

3

12：00—14：00

10

4

14：00—16：00

30

5

16：00—18：00

20

6

18：00—20：00

10

7

20：00—22：00

51/7/202353解設(shè)xi為時段i開始工作的人數(shù)（i=1,2,3,4).由于各班工資相同，要求公司所付的工資最少也就是要求服務(wù)人員最少。于是可得整數(shù)規(guī)劃模型：1/7/202354例某公司的營業(yè)時間是上午8點到21點。服務(wù)人員中途需要1小時吃飯和休息時間，每人的工作時間為8小時。上午8點到17點工作的人員月工資為800元，中午12點到21點工作的人員月工資為900元。為保證營業(yè)時間內(nèi)都有人上班，公司安排了四個班次，其班次和休息時間安排如下表一。各時段需求的人數(shù)如上例之表，只是第6、7段合并為18點到21點，需求人數(shù)為10人。問應(yīng)如何安排服務(wù)人員既滿足需求又使公司所付工資總數(shù)最少。1/7/202355

表一班次工作時間休息時間月工資

18:00-17:0012:00-13:00

800

28:00-17:0013:00-14:00

800

312:00-21:0016:00-17:00

900

412:00-21:0017:00-18:00

9001/7/202356解為了便于建立模型，可用各班中途休息的起止時刻和上例之表中時間區(qū)間的起止時間分細，并求出各班工作的關(guān)聯(lián)表，見表二。表中j列的“1”表示該班次在相應(yīng)的時段內(nèi)工作，“0”表示不工作。1/7/202357表二時段班次

1234需求人數(shù)

8:00-10:00

11002010:00-12:0011002512:00-13:000111

1013:00-14:0010111014:00-16:0011113016:00-17:0011012017:00-18:0000102018:00-21:000011101/7/202358設(shè)xi表示第i班安排的人數(shù)（i=1,2,3,4)，則可得整數(shù)規(guī)劃模型：1/7/202359(八)、套裁下料問題例某車間接到制作100套鋼架的定單，每套鋼架要用長為2.9m,2.1m,1.5m的圓鋼各一根，已知原料長7.4m。問應(yīng)如何下料，可使所用原料最省解:可能截法

方法下料根數(shù)長度/m123456782.9211100002.1021032101.510130234合計料頭7.30.17.10.36.50.97.406.31.17.20.26.60.66.01.41/7/202360

假設(shè)按方法1，2，…,8方式下料的原料根數(shù)分別為x1,x2,…,x8,則希望在得到長度為2.9m,2.1m,1.5m的圓鋼各為100根的情況下，使總料頭最小。模型為：1/7/202361(九)、生產(chǎn)工藝優(yōu)化問題例某日化廠生產(chǎn)洗衣粉和洗滌劑。生產(chǎn)原料由市場提供：每kg5元，供應(yīng)量無限制。該廠加工1kg原料可產(chǎn)出0.5kg普通洗衣粉和0.3kg普通洗滌劑。工廠還可以對普通洗衣粉和普通洗滌劑進行精加工。加工1kg普通洗衣粉可得0.5kg濃縮洗衣粉，加工1kg普通洗滌劑可產(chǎn)出0.25kg高級洗滌劑，加工示意圖下圖，市場售價為：每kg普通洗衣粉為8元；每kg濃縮洗衣粉為24元；每kg普通洗滌劑為12元；每kg高級洗滌劑為55元。每加工1kg原料的加工成本為1元，每1kg精加工產(chǎn)品的成本為3元，工廠設(shè)備每天最多可處理4t原料，而對精加工沒有限制。若市場對產(chǎn)品也沒有限制，問該廠應(yīng)如何安排生產(chǎn)能使每日利潤最大？1/7/202362

x1kg普通洗衣粉

0.5x0kg洗衣粉x2kg濃縮洗衣粉

X0kg原料x3kg普通洗滌劑

0.3x0kg洗滌劑x4kg高級洗滌劑1/7/202363解設(shè)每日生產(chǎn)普通洗衣粉的產(chǎn)量為x1kg

，生產(chǎn)濃縮洗衣粉x2kg，生產(chǎn)普通洗滌劑

x3kg

，生產(chǎn)高級洗滌劑x4kg，每日加工原料x0kg.

工廠利潤Z應(yīng)是每日的產(chǎn)品銷售價減去原料成本與加工成本，故目標(biāo)函數(shù)為：

約束條件為加工過程中物流的平衡約束及原料供應(yīng)限制：1/7/202364

整理化簡并加上非負約束條件可得數(shù)學(xué)模型：1/7/202365(十)、有配套約束的資源優(yōu)化問題例某公司計劃用資金60萬來購買A，B，C三種運輸汽車。已知A種汽車每輛為1萬元，每班需一名司機，可完成每公里2100噸。B種汽車每輛為2萬元，每班需兩名司機，可完成每公里3600噸。C種汽車每輛為2.3萬元，每班需兩名司機，可完成每公里3780噸。每輛汽車每天最多安排三班，每個司機每天最多安排一班。購買汽車數(shù)量不超過30輛、司機不超過145人。問：每種汽車應(yīng)購買多少輛，可使公司今后每天可完成的公里噸數(shù)最大？1/7/202366解設(shè)購買A種汽車中，每天只安排一班的有x11輛，每天安排二班的有x12輛，每天安排三班的有x13輛；同樣設(shè)購買B種汽車依次有x21,x22,x23輛;購買C種汽車依次有x31,x32,x33輛.因此有1/7/202367(十一)、多周期動態(tài)生產(chǎn)計劃問題例某柴油機廠接到今年1至4季度柴油機生產(chǎn)訂單分別為：3000臺，4500臺，3500臺，5000臺。該廠每季度正常生產(chǎn)量為3000臺，若加班可多生產(chǎn)1500臺，正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加成本每臺1500元。庫存成本為每臺每季度200元，問該柴油機廠該如何組織生產(chǎn)才能使生產(chǎn)成本最低？1/7/202368解設(shè)xi1為第i個季度正常生產(chǎn)的柴油機臺數(shù)，xi2為第i個季度加班生產(chǎn)的柴油機臺數(shù)，xi3為第i個季度初庫存數(shù)。i=1,2,3,4.第一季度初及年底的庫存數(shù)均產(chǎn)零，若記di為第i季度的需求量；c1,c2,c3分別為正常生產(chǎn)、加班生產(chǎn)、庫存（每季度）每臺柴油機的成本。則其數(shù)學(xué)模型為：代入具體數(shù)據(jù)，得數(shù)學(xué)模型如下：1/7/2023691/7/202370(十二)、投資問題投資者經(jīng)常會遇到投資項目的組合選擇問題，要考慮的因素有收益率、風(fēng)險、增長潛力等條件，并進行綜合權(quán)衡，以求得一個最佳投資方案。例某投資公司有50萬元可用于長期投資，可供選擇的投資項目包括購買國庫券、購買公司債券、投資房地產(chǎn)、購買股票、銀行短期或長期儲蓄。各種投資方式的投資期限，年收益率，風(fēng)險系數(shù)，增長潛力的具體參數(shù)見下表。若投資者希望投資組合的平均年限不超過5年，平均的期望收益率不低于13%，風(fēng)險系數(shù)不超過4，收益的增長潛力不低于10%。問在滿足上述要求前提下，投機者該如何選擇投資組合使平均年平均收益率最高？1/7/202371序號投資方式投資期限（年）年收益率(%）風(fēng)險系數(shù)增長潛力(%）1國庫券311102公司債券10153153房地產(chǎn)6258304股票2206205短期儲蓄110156長期儲蓄5122101/7/202372解設(shè)xi為第i種投資方式在總投資中所占的比利,則該數(shù)學(xué)模型為:1/7/202373例某投資者有資金10萬元,考慮在今后5年內(nèi)給下列4個項目進行投資,已知:

項目A：從第1年到第4年每年年初需要投資，并于次年末回收本利115%.

項目B:第3年初需要投資,到第5年末能回收本利125%,但規(guī)定投資額不超過4萬元項目C:第2年初需要投資,到第5年末能回收本利140%,但規(guī)定最大投資額不超過3萬元.

項目D:5年內(nèi)每年初可購買公債,于當(dāng)年畝歸還,并加利息6%.

問該投資者應(yīng)如何安排他的資金,確定給這些項目每年的投資額,使到第5年末能擁有的資金本利總額為最大?1/7/202374解記xiA,xiB,xiC,xiD(i=1,2,…5)分別表示第i年初給項目A,B,C,D的投資額,它們都是決策變量,為了便于書寫數(shù)學(xué)模型,列表如下:

年份項目

1

2

3

4

5AX1AX2AX3AX4ABX3BCX2CDX1DX2DX3DX4DX5D1/7/202375根據(jù)項目A，B，C，D的不同情況，在第5年末能收回的本利分別為：1.15x4A,1.25x3B,1.40x2C,及1.06x5D。因此目標(biāo)函數(shù)為：

maxz=1.15x4A+1.25x3B+1.40x2C+1.06x5D.約束條件是每年年初的投資額等于該投資者年初所擁有的資金。第1年年初該投資者擁有10萬元資金，故有

x1A+x1D=10000.

第2年年初該投資者手中擁有資金只有（1+6%）x1D,故有

x2A+x2C+x2D=1.06x1D.

第3年年初該投資者擁有資金從D項目收回的本金：1.06x2D,及從項目A中第1年投資收回的本金：1.15x1A,1/7/202376故有

x3A+x3B+x3D=1.15x1A+1.06x2D.同理第4年、第5年有約束為：

X4A+X4D=1.15X2A+1.06X3D,X5D=1.15X3A+1.06X4D.故本例數(shù)學(xué)模型經(jīng)化間后為maxz=1.15x4A+1.25x3B+1.40x2C+1.06x5D

x1A+x1D=10000x2A+x2C+x2D=1.06x1D

x3A+x3B+x3D=1.15x1A+1.06x2DX4A+X4D=1.15X2A+1.06X3DX5D=1.15X3A+1.06X4D

xiA,XiB,xiC,XiD>=0(I=1,2,3,4,5)

1/7/2023771線性規(guī)劃問題及數(shù)學(xué)模型1.1問題的提出(見前述模型)1.2線性規(guī)劃問題的數(shù)學(xué)模型1/7/202378

1、和式1/7/202379

3、矩陣式1/7/202380

1.1.3線性規(guī)劃的圖解法f(x)=361/7/202381

線性規(guī)劃問題的幾個特點：線性規(guī)劃問題的可性解的集合是凸集線性規(guī)劃問題的基礎(chǔ)可行解一般都對應(yīng)于凸集的極點凸集的極點的個數(shù)是有限的最優(yōu)解只可能在凸集的極點上，而不可能發(fā)生在凸集的內(nèi)部1/7/202382

1.2.2單純型法的基本思路1/7/202383

1.2.3單純型表及其格式1/7/202384

例1.2.2試列出下面線性規(guī)劃問題的初始單純型表1/7/2023851.2線性規(guī)劃問題的單純型解法1.2.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式為了使線性規(guī)劃問題的解法標(biāo)準(zhǔn)，就要把一般形式化為標(biāo)準(zhǔn)形式1/7/202386

1.2.3單純型表及其格式1/7/202387變換的方法：目標(biāo)函數(shù)為min型，價值系數(shù)一律反號。令f(x)=-f(x)=-CX,有minf(x)=-max[-

f(x)]=-maxf(x)第i個約束的bi

為負值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向第i個約束為型，在不等式左邊增加一個非負的變量xn+i

，稱為松弛變量；同時令cn+i

=0第i個約束為型，在不等式左邊減去一個非負的變量xn+i

，稱為剩余變量；同時令cn+i

=0若xj

0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

0若xj

不限，令

xj=xj-

xj，

xj

0，xj0，代入非標(biāo)準(zhǔn)型1/7/202388

1.2.2單純型法的基本思路1/7/202389

1.2.3單純型表及其格式1/7/202390例1.2.2試列出下面線性規(guī)劃問題的初始單純型表1/7/202391

關(guān)于檢驗數(shù)的數(shù)學(xué)解釋設(shè)

B

是初始可行基，則目標(biāo)函數(shù)可寫為兩部分(1)約束條件也寫為兩部分，經(jīng)整理得XB的表達式(2)，注意XB中含有非基變量作參數(shù)把XB代入目標(biāo)函數(shù)，整理得到(3)式第j

個非基變量的機會成本如(4)式若有cjzj>0,則未達到最優(yōu)1/7/202392表1.2.4例1.2.2單純型表的迭代過程答：最優(yōu)解為x1=20,x2=20,x3=0,OBJ=17001/7/202393

單純型表中元素的幾點說明任何時候，基變量對應(yīng)的列都構(gòu)成一個單位矩陣當(dāng)前表中的b

列表示當(dāng)前基變量的解值，通過變換B1b

得到(資源已變成產(chǎn)品)當(dāng)前非基變量對應(yīng)的向量可通過變換B1AN

得到，表示第j

個變量對第i

行對應(yīng)的基變量的消耗率非基變量的機會成本由給出注意基變量所對應(yīng)的行1/7/202394表1.3.1例1.3.1的單純型表迭代過程答：最優(yōu)解為x1=2,x2=2,x3=0,OBJ=361/7/202395從圖解法作圖結(jié)果來分析,線性規(guī)劃應(yīng)有以下幾種可能出現(xiàn)的結(jié)果:(1)有唯一最優(yōu)解(2)有無窮多最優(yōu)解(3)無界解(也稱無最優(yōu)解)1/7/2023962.4線性規(guī)劃的對偶理論及其應(yīng)用窗含西嶺千秋雪，門泊東吳萬里船對偶是一種普遍現(xiàn)象1/7/2023972.4.1對偶問題的提出例1、某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的利潤、所消耗的材料、工時及每天的材料限額如下表，試問如何安排生產(chǎn)，使每天所得利潤最大？設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為x1件,x2件甲乙

限額材料工時23322426利潤

431/7/202398現(xiàn)在從另一種角度來討論.假設(shè)工廠考慮不安排生產(chǎn),而是出售材料,出租工時,部如何定價,可使工廠獲利不低于安排生產(chǎn)所獲得的收益,且又能使這些定價具有競爭力?設(shè)出售材料的定價為每單位y1元,出租工時定價為每工時y2元,從工廠考慮,這些定價的獲利不應(yīng)低于安排生產(chǎn)所獲得的收益,否則工廠寧愿生產(chǎn),而不出售和出租.由此,工廠生產(chǎn)一件單產(chǎn)品所消耗的材料和工時的總價值不低于4元,即有同樣,從乙產(chǎn)品考慮,亦有為使這些定價有競爭力,目標(biāo)函數(shù)為1/7/202399綜合起來,該問題的數(shù)學(xué)模型為:1/7/2023100任何線性規(guī)劃問題都有其對偶問題對偶問題有其明顯的經(jīng)濟含義假設(shè)有商人要向廠方購買資源A和B，問他們談判原料價格的模型是怎樣的？1/7/2023101例2設(shè)A、B資源的出售價格分別為y1

和

y2顯然商人希望總的收購價越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少目標(biāo)函數(shù)ming(y)=25y1+15y21/7/2023102

2.4.2線性規(guī)劃原問題與對偶問題的表達形式

1.對稱形式的對偶問題1/7/2023103見問題提出1/7/2023104原規(guī)劃(LP)對偶規(guī)劃(DP)1/7/2023105

對稱形式的兩個互為對偶問題進行比較可以看出:目標(biāo)函數(shù)由max型變?yōu)閙in型對應(yīng)原問題每個約束行有一個對偶變量yi，i=1,2,…,m對偶問題約束為型，有n

行原問題的價值系數(shù)C

變換為對偶問題的右端項原問題的右端項

b變換為對偶問題的價值系數(shù)原問題的技術(shù)系數(shù)矩陣A轉(zhuǎn)置后成為對偶問題的技術(shù)系數(shù)矩陣矩陣原問題與對偶問題互為對偶對偶問題可能比原問題容易求解對偶問題還有很多理論和實際應(yīng)用的意義1/7/2023106

xjyj

x1x2

…

xn原關(guān)系minW

y1y2

ym

a11a12…

a1n

a21a22.…

a2nam1am2…

amn

≤≤

≤b1b1

b1

對偶關(guān)系≥≥…≥maxZ

c1c2

…

cn這些關(guān)系可用下表表示：1/7/20231072.非對稱形式的對偶問題設(shè)線性規(guī)劃問題由于（1）故（1）可改寫為1/7/2023108從而對偶問題為：即：又令顯然Y無約束，得（1）對偶問題：1/7/2023109表2.13對偶變換的規(guī)則約束條件的類型與非負條件對偶非標(biāo)準(zhǔn)的約束條件類型對應(yīng)非正常的非負條件對偶變換是一一對應(yīng)的1/7/2023110

非對稱形式的對偶問題1/7/2023111例2試求下述問題的對偶問題：（1）（2）1/7/2023112解的對偶規(guī)劃為：（1）1/7/2023113（2）的對偶規(guī)劃為：1/7/2023114二、靈敏度分析線性規(guī)劃是靜態(tài)模型參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu)哪些參數(shù)容易發(fā)生變化C,b,A每個參數(shù)發(fā)生多大的變化不會破壞最優(yōu)解靈敏度越小，解的穩(wěn)定性越好1/7/2023115

1.邊際值(影子價)qi以(max,)為例邊際值(影子價)qi

是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)趇

個約束行的右端項bi

減少一個單位時，目標(biāo)函數(shù)的變化量1/7/2023116例11/7/2023117影子價格的說明影子價是資源最優(yōu)配置下資源的理想價格，資源的影子價與資源的緊缺度有關(guān)松弛變量增加一個單位等于資源減少一個單位剩余變量增加一個單位等于資源增加一個單位資源有剩余，在最優(yōu)解中就有對應(yīng)松弛變量存在，且其影子價為0影子價為0，資源并不一定有剩余應(yīng)用，郵電產(chǎn)品的影子價格1/7/2023118

2價值系數(shù)cj

的靈敏度分析cj

變動可能由于市場價格的波動，或生產(chǎn)成本的變動cj

的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj

允許的變動范圍cj

cj

的變化會引起檢驗數(shù)的變化，有兩種情況非基變量對應(yīng)的價值系數(shù)變化，不影響其它檢驗數(shù)基變量對應(yīng)的價值系數(shù)變化，影響所有非基變量檢驗數(shù)1、非基變量對應(yīng)的價值系數(shù)的靈敏度分析1/7/2023119例21/7/20231202、基變量對應(yīng)的價值系數(shù)的靈敏度分析由于基變量對應(yīng)的價值系數(shù)在CB中出現(xiàn)，因此它會影響所有非基變量的檢驗數(shù)只有一個基變量的cj發(fā)生變化，變化量為cj令cj在CB中的第k行，研究非基變量xj

機會成本的變化1/7/2023121設(shè)x4的價值系數(shù)增加c4，對應(yīng)k=2，

有一邊為空集如何處理

為什么akj=0不出現(xiàn)在任何一邊的集合中

與對偶單純型法找入變量的公式一樣1/7/2023122

3.右端項bi的靈敏度分析設(shè)XB=B1b是最優(yōu)解，則有XB=B1b0b的變化不會影響檢驗數(shù)b的變化量b可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪?/7/2023123

4.右端項bi的靈敏度分析1/7/2023124以b2為例,x6是對應(yīng)的初始基變量，所以有1/7/2023125

5.技術(shù)系數(shù)aij

的靈敏度分析技術(shù)系數(shù)aij變化的影響比較復(fù)雜對應(yīng)基變量的aij

，且資源bi已全部用完對應(yīng)基變量的aij

，但資源bi未用完對應(yīng)非基變量的aij

，且資源bi全用完或未用完1、對應(yīng)基變量的aij

，且資源bi已全部用完aij=02、對應(yīng)基變量的aij

，但資源bi未用完

aijxn+i

/xj上述兩個公式不充分，為什么？B–1發(fā)生變化，從而引起非基變量檢驗數(shù)cj–zj

的變化3、對應(yīng)非基變量的aij只影響對應(yīng)非基變量xj的檢驗數(shù)

cj–zj

若aij>0，不會破壞最優(yōu)解若aij<0，必須保證cj–zj

01/7/20231261/7/2023127x1,x3為非基變量，q1=0,q2=0.25,q3=1,故有x2,x4為基變量，x5=100,b1有剩余，故有1/7/2023128

6.新增決策變量的分析例2.4.2中，若新增產(chǎn)品x8，問是否生產(chǎn)？已知c8=9,a18=5,a28=4,a38=3計算x8的檢驗數(shù)可知生產(chǎn)是否有利結(jié)論：生產(chǎn)x8有利。將B–1P8加入最優(yōu)單純型表中，以x8為入變量進行迭代1/7/2023129

7.新增約束條件的分析1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2、若不滿足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標(biāo)準(zhǔn)型3、利用對偶單純型法繼續(xù)迭代為什么可以利用對偶單純型法例2.4.2第2步1/7/20231301/7/2023131注意：最優(yōu)解的目標(biāo)函數(shù)減少了25個單位1/7/2023132

8靈敏度分析舉例例3某工廠生產(chǎn)三種產(chǎn)品A,B,C，有五種生產(chǎn)組合方案。下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應(yīng)A產(chǎn)品至少110個，求收益最大的生產(chǎn)方案。1/7/2023133例4解：設(shè)xj為已選定各種組合方案的組數(shù)(j=1,2,…,5)，x6為A產(chǎn)品的剩余變量，x7，x8分別為工人工時和機器工時的松弛變量。1/7/2023134

最優(yōu)解的B–1是什么產(chǎn)品A的影子價為多少第II組方案的生產(chǎn)費用提高2元，是否要調(diào)整生產(chǎn)組別若工人加班費為1元/小時，是否要采取加班措施若通過租借機器增加工時，租費的上限應(yīng)為多少A產(chǎn)品的訂購合同是否有利若要選用第IV組方案，該組的生產(chǎn)費用應(yīng)降低多少若工人加班費為0.3元/小時，最多允許加班時間多少若機器租費低于44元/小時，問租幾部機器才合適(每天8小時計)若第III組方案使機器工時減少0.5小時，能否被選入1/7/20231357.參數(shù)線性規(guī)劃2.4

節(jié)中

aij,bi,cj

只有一個發(fā)生變化，多個同時發(fā)生變化則很難解析但在一些特殊情況下，用參數(shù)表示變化量，也可以用來進行多個系數(shù)的靈敏度分析

2.5.1參數(shù)cj的變化分析i

第i種資源的單位費用變化量，i不限ii變化對cj

的影響率1/7/2023136

例5資源b1變化量1，j=a1j1/7/2023137例6資源b1變化量1與c51/7/2023138

9

參數(shù)bi的變化分析例2.4.2中，將b1,b2,b3理解為三個車間的周工時資源。假設(shè)從第1向2車間調(diào)動工人個，每個工人的周工時為40小時，問調(diào)動多少工人不會破壞最優(yōu)產(chǎn)品組合1/7/2023139三、動態(tài)規(guī)劃有許多決策過程是多階段的，即動態(tài)的，動態(tài)規(guī)劃就是一類多階段決策過程的最優(yōu)化方法。一、動態(tài)規(guī)劃的基本概念和基本原理例最短路問題。下圖給出了一路線網(wǎng)絡(luò)，箭桿旁的數(shù)字為兩點間的路程?，F(xiàn)求從A到E的最短路。

A到E有3×3×2×1=18條不同的路線，如果階段數(shù)增加，則路的條數(shù)也增加，用窮舉法顯然不可取，而用動態(tài)規(guī)劃方法只需計算其中一部分便可求A到E的最短路線，并且還可得出任何一點到終點F的最短路線。1/7/2023140AB1B2B3C1C2C3D1D2E243763244151463333343447611748111/7/2023141階段：根據(jù)時間和空間將問題劃分成若干個互相有關(guān)聯(lián)的階段，用k表示階段變量，n表示總的階段數(shù)。狀態(tài)：某階段出發(fā)的位置。它既是該段某支路的起點，又是前一段某支路的終點。通常一個階段包含若干個狀態(tài)。如上題中四個階段的狀態(tài)集合分別為{A}，{B1，B2，B3}，{C1，C2，C3}，{D1，D2}

描述狀態(tài)的變量稱為狀態(tài)變量，記為sk.決策：當(dāng)階段和狀態(tài)給定后，從該狀態(tài)到下一階段某狀態(tài)的選擇。描述決策的變量稱為決策變量，記為xk或x(sk)，它表示第k階段處于狀態(tài)sk時采取的決策，是狀態(tài)sk的函數(shù)。決策變量的取值范圍稱為允許決策集合，記為Xk

或X(Sk)，即xk∈Xk.1/7/2023142狀態(tài)轉(zhuǎn)移方程：描述狀態(tài)轉(zhuǎn)移規(guī)律的函數(shù)關(guān)系

sk=T(sk,xk)當(dāng)sk和xk取定后，sk+1的取值就隨之確定。策略：各階段所確定的決策構(gòu)成的決策序列。即

{x1(s1),x2(s2),…,xn(sn)}

目的是從眾多的策略中選擇最優(yōu)策略，記為

{x1*(s1),x2*(s2),…,xn*(sn)}1/7/2023143報酬函數(shù)：當(dāng)過程處于狀態(tài)sk，采取決策xk時所得的報酬（或費用），通常記為vk(sk,xk)。上例中的vk為第k階段到k+1階段兩點間的路程。目標(biāo)（指標(biāo)）函數(shù)：衡量策略好壞的函數(shù)從第k階段的sk出發(fā)到終點的目標(biāo)函數(shù)記為

vkn=vkn(sk,xk,…xn),最優(yōu)目標(biāo)函數(shù)值記為

fk*(sk)=optvkn(sk,xk,…xn)，上例是求f1*(A)對應(yīng)的策略1/7/2023144最優(yōu)化原理：從上例看出，

AB2C1D1E是A到E的最短路線，則

B2C1D1E是B2出發(fā)到E的最短路。

C1D1E是C1出發(fā)到E的最短路。

1/7/2023145即作為整個過程的最優(yōu)策略具有如下性質(zhì)：無論過去的狀態(tài)和決策如何，對前面所形成的某確定狀態(tài)而言，余下的決策必須構(gòu)成最優(yōu)子策略。利用此原理，可以把多階段決策問題的求解過程看成是一個連續(xù)的遞推過程，由后向前逐步推算。這相當(dāng)于把原問題劃成了許多相互聯(lián)系的比原問題簡單的子問題，在求解每個子問題時，均利用它的后部子問題的最優(yōu)結(jié)果，依次從后向前推進，最后一個子問題的解就是原問題的最優(yōu)解。1/7/2023146第4階段：得最優(yōu)策略得最優(yōu)策略第3階段得最優(yōu)策略1/7/2023147得最優(yōu)策略得最優(yōu)策略1/7/2023148同理可推得第2階段和1階段的最小優(yōu)決策。第2階段：1/7/2023149第1階段最后，由第1階段到第4階段的最優(yōu)決策，可得出最短路三條：最短路程1/7/2023150一、一維資源分配問題例某工廠擬在一年中進行三種新產(chǎn)品試制，估價不成功的概率分別為40,0.60,0.80.為了促進三種新產(chǎn)品的研制,廠領(lǐng)導(dǎo)決定撥2萬元補加研制費.假若這些補加研制費(以萬元為單位)分配給不同新產(chǎn)品時,估計不成功的概率分別為下表所示.問如何分配這些補加研制費,使這三種新產(chǎn)品都不成功的概率最小1/7/2023151

產(chǎn)品研制費不成功的概率ABC

0

0.40

0.60

0.80

1

0.20

0.40

0.50

2

0.15

0.20

0.301/7/2023152解設(shè)xk為分配給第k種新產(chǎn)品(依次為A,B,C)的補加研制,k=1,2,3.pk(xk)表示分配xk萬元補加研制費給第k種新產(chǎn)品時不成功的概率(k=1,2,3).則得非線性規(guī)劃模型:

1/7/2023153若設(shè)由于sk,,xk均取幾個離散值,所以可將三個階段的計算過程分別列入下面三個表中新產(chǎn)品的補加研制費,則相應(yīng)的動態(tài)規(guī)劃為表示分配給第k至第3種1/7/2023154第三階段（k=3)x3s3p3(x3)F3*(s3)X3*

0

1

200.800.80

0

10.500.50

1

20.300.30

2S3=x31/7/2023155第二階段x2S2p2(s2)·f3*(s3)f2*(s2)X2*01200.480.48010.300.320.30020.180.200.160.162S2=x2+S31/7/2023156第一階段x1S1p1(x1)·f2*(s2)f1*(s1)x1*

0

1

2

20.0640.060.0720.06

1S1=2=x1+S2于是得最優(yōu)解:都不成功的概率為0.061/7/2023157二、背包問題背包問題的一般提法是：一旅行者攜帶背包去登山，已知他所能承受的背包重量限制為a千克，現(xiàn)有n種物品可供他選擇裝入背包,第i種物品的單件重量為ai千克,其價值(可以是表明本物品對登山的重要性的數(shù)量指標(biāo))是攜帶數(shù)量xi的函數(shù)ci(xi)(i=1...n).問旅行者如何選擇攜帶各種物品的件數(shù),以使總價值最大?

背包問題等同于車、船、飛機、人造衛(wèi)星等工具的裝載問題,還可以用于解決機床加工中零件最優(yōu)加工、下料問題,投資決策等.1/7/2023158解設(shè)xi為第i種物品裝入的件數(shù)，則下面用動態(tài)規(guī)劃順序解法建模求解1/7/2023159階段k:將可裝入物品按1，2，…,n排序，每段裝一種物品，共劃分n個階段。K=1,2,…,n.狀態(tài)變量sk+1:在第k段開始時，背包中允許裝入前k種物品的總重量。決策變量xk:裝入第k種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程：sk=sk+1-aksk允許決策集合：1/7/2023160最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示在背包中允許裝入物品的總重量不超過sk+1千克，采用最優(yōu)策略只裝前k種物品時的最大使用價值。則可得到動態(tài)規(guī)劃的順序遞推方程為：用前向動態(tài)規(guī)劃方法逐步計算f1(s2),f2(s3),…,fn(sn+1)及相應(yīng)的決策函數(shù)x1(s2),x2(s3),…,xn(sn+1),最后得到的fn(a)即為所求的最大值，相應(yīng)的最優(yōu)策略則由反推計算得出。1/7/2023161三、設(shè)備更新問題

企業(yè)中經(jīng)常會遇到因設(shè)備陳舊或損壞需要更新的問題。從經(jīng)濟學(xué)上分析，一臺設(shè)備應(yīng)該用多少年更新最合算，這就是設(shè)備更新問題。一般來說，一臺設(shè)備在比較新時，年運轉(zhuǎn)量大，經(jīng)濟收入高，故障少，維修費用少，但隨著使用年限的增加，年運轉(zhuǎn)量減少因而收入減少，故障增多維修費用增加。如果更新可提高