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

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

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

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

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

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

10/7/20237

MCM的發(fā)展歷程

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

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

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

建模的步驟

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

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

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

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

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

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

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

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

生物數(shù)學模型

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

地質數(shù)學模型

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

數(shù)學社會學模型

按是否考慮隨機因素分類

確定性模型

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

靜態(tài)模型

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

離散模型

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

幾何模型

微分方程模型

圖論模型

規(guī)劃論模型

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

白箱模型：

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

灰箱模型：

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

黑箱模型：

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

分析與設計

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

預報與決策

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

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

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

規(guī)劃與管理

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

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

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

88年：毒品走私船問題平板列車車廂的優(yōu)化裝載10/7/20231789年：最佳分類隔離飛機排隊模型90年：腦中多巴胺的分布鏟雪車的路徑問題；鏟雪效率問題91年：估計水塔的水流量尋找最優(yōu)Steiner樹92年：確定航空控制雷達系統(tǒng)的功效緊急修復系統(tǒng)的研制10/7/20231895年：一個飛行管理模型天車與冶煉爐的調度93年：混合物轉化為有機肥的最隹過程煤炭裝卸場的最優(yōu)操作94年:逢山開路鎖具裝箱10/7/20231997年：零件參數(shù)的設計截斷切割98年：災情巡視路線投資的收益與風險99年：自動化車床管理鉆探布點96年：最優(yōu)捕魚策略節(jié)水洗衣機 10/7/2023202000年：DNA序列分類鋼管訂購和運輸2001年：血管的三維重建公交車的調度2002年：車燈線光源的優(yōu)化設計彩票中的數(shù)學2003年：關于sars控制和預測礦山車輛調度2004年：奧運會臨時超市網(wǎng)點設計電力市場的輸電阻塞管理10/7/2023212005年：長江水質的評價和預測DVD在線租賃2006年：出版社的資源配置艾滋病療法的評價及療效的預測2007年：中國人口增長預測

乘公交，看奧運

2008年：數(shù)碼相機定位高等教育學費標準探討

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

1.線性規(guī)劃問題的數(shù)學模型2.兩個變量問題的圖解法3.線性規(guī)劃數(shù)學模型的標準形式及解的概念3.1標準形式3.2將非標準形式化為標準形式3.3有關解的概念10/7/202324運籌學

OperationalResearch運籌帷幄，決勝千里

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

10/7/202335

銷地運價產(chǎn)地

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

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

10/7/202338(三)、網(wǎng)絡問題一個網(wǎng)絡包括一些結點（用圓圈表示），每個結點由幾條?。ㄓ眉^表示）與其它結點相連，如圖：2154

20128915107

1410812313610/7/202339最短路問題解：設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=010/7/202340-x25-x45+x56+x57=0-x36-x56+x67=0-x47-x57-x67=-1（到達7的汽車為一輛）Xij=0,或1,i,j=1,2,…7.10/7/202341(四)、生產(chǎn)活動問題例：某公司有m種資源B1，B2，…，Bm(如機器的可用工時，勞力，原材料等），生產(chǎn)n種不同的產(chǎn)品A1，A2，．．．Ａn.其單位消耗，單位利潤等如表．問如何安排生產(chǎn)使利潤最大．解設xj表示第j種產(chǎn)品的產(chǎn)量，則可得線性規(guī)劃模型：10/7/202342產(chǎn)單品耗資源Ａ１，Ａ２，…,Ａn

資源量Ｂ１Ｂ２．．．Ｂma11a12…a1na21a22…a2n.....…...….am1am2…amnb1b2...bm單位利潤c1c2…cn10/7/202343注1若還要考慮固定成本，則需引入0–1變量。設第j種產(chǎn)品的固定成本為Mj，第j種產(chǎn)品的產(chǎn)量的上界為Lj引入0–1變量0,生產(chǎn)第j種產(chǎn)品，Yj=1，否則10/7/202344注2如果某些資源的使用是有選擇的，即有些約束條件是互相排斥的，可引入0–1變量將其統(tǒng)一在同一模型中。如b1,b2為不同型號的兩臺機器的可用工時，而n種產(chǎn)品可在任一臺上加工，這時第1，2兩個約束條件就是互排斥的，只能選擇一個進入模型。如果引入0–1變量10/7/202345

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

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

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

10/7/202350模型中，xi,yi已知，ui,vi,a,b為決策變量。原問題化為含（2n+2)個決策變量，n個約束方程的一極小化問題。10/7/202351(七)、人員安排問題例某公司的營業(yè)時間是上午8點到22點，以兩小時為一時段，各時段內(nèi)所需的服務人員數(shù)如下表，每個服務人員可在任一時段開始上班，但要工作8小時，而工資都相同。問應如何安排服務人員使公司所付工資總數(shù)最少。10/7/202352序號時間區(qū)間需求人數(shù)18：00—10：0020210：00—12：0025312：00—14：0010414：00—16：0030516：00—18：0020618：00—20：0010720：00—22：00510/7/202353解設xi為時段i開始工作的人數(shù)（i=1,2,3,4).由于各班工資相同，要求公司所付的工資最少也就是要求服務人員最少。于是可得整數(shù)規(guī)劃模型：10/7/202354例某公司的營業(yè)時間是上午8點到21點。服務人員中途需要1小時吃飯和休息時間，每人的工作時間為8小時。上午8點到17點工作的人員月工資為800元，中午12點到21點工作的人員月工資為900元。為保證營業(yè)時間內(nèi)都有人上班，公司安排了四個班次，其班次和休息時間安排如下表一。各時段需求的人數(shù)如上例之表，只是第6、7段合并為18點到21點，需求人數(shù)為10人。問應如何安排服務人員既滿足需求又使公司所付工資總數(shù)最少。10/7/202355

表一班次工作時間休息時間月工資18:00-17:0012:00-13:0080028:00-17:0013:00-14:00800312:00-21:0016:00-17:00900412:00-21:0017:00-18:0090010/7/202356解為了便于建立模型，可用各班中途休息的起止時刻和上例之表中時間區(qū)間的起止時間分細，并求出各班工作的關聯(lián)表，見表二。表中j列的“1”表示該班次在相應的時段內(nèi)工作，“0”表示不工作。10/7/202357表二時段班次1234需求人數(shù)8:00-10:0011002010:00-12:0011002512:00-13:0001111013:00-14:0010111014:00-16:0011113016:00-17:0011012017:00-18:0000102018:00-21:0000111010/7/202358設xi表示第i班安排的人數(shù)（i=1,2,3,4)，則可得整數(shù)規(guī)劃模型：10/7/202359(八)、套裁下料問題例某車間接到制作100套鋼架的定單，每套鋼架要用長為2.9m,2.1m,1.5m的圓鋼各一根，已知原料長7.4m。問應如何下料，可使所用原料最省解:可能截法

方法下料根數(shù)長度/m123456782.9211100002.1021032101.510130234合計料頭7.30.17.10.36.50.97.406.31.17.20.26.60.66.01.410/7/202360假設按方法1，2，…,8方式下料的原料根數(shù)分別為x1,x2,…,x8,則希望在得到長度為2.9m,2.1m,1.5m的圓鋼各為100根的情況下，使總料頭最小。模型為：10/7/202361(九)、生產(chǎn)工藝優(yōu)化問題例某日化廠生產(chǎn)洗衣粉和洗滌劑。生產(chǎn)原料由市場提供：每kg5元，供應量無限制。該廠加工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元，工廠設備每天最多可處理4t原料，而對精加工沒有限制。若市場對產(chǎn)品也沒有限制，問該廠應如何安排生產(chǎn)能使每日利潤最大？10/7/202362

x1kg普通洗衣粉

0.5x0kg洗衣粉x2kg濃縮洗衣粉X0kg原料x3kg普通洗滌劑0.3x0kg洗滌劑x4kg高級洗滌劑10/7/202363解設每日生產(chǎn)普通洗衣粉的產(chǎn)量為x1kg，生產(chǎn)濃縮洗衣粉x2kg，生產(chǎn)普通洗滌劑

x3kg，生產(chǎn)高級洗滌劑x4kg，每日加工原料x0kg.工廠利潤Z應是每日的產(chǎn)品銷售價減去原料成本與加工成本，故目標函數(shù)為：

約束條件為加工過程中物流的平衡約束及原料供應限制：10/7/202364整理化簡并加上非負約束條件可得數(shù)學模型：10/7/202365(十)、有配套約束的資源優(yōu)化問題例某公司計劃用資金60萬來購買A，B，C三種運輸汽車。已知A種汽車每輛為1萬元，每班需一名司機，可完成每公里2100噸。B種汽車每輛為2萬元，每班需兩名司機，可完成每公里3600噸。C種汽車每輛為2.3萬元，每班需兩名司機，可完成每公里3780噸。每輛汽車每天最多安排三班，每個司機每天最多安排一班。購買汽車數(shù)量不超過30輛、司機不超過145人。問：每種汽車應購買多少輛，可使公司今后每天可完成的公里噸數(shù)最大？10/7/202366解設購買A種汽車中，每天只安排一班的有x11輛，每天安排二班的有x12輛，每天安排三班的有x13輛；同樣設購買B種汽車依次有x21,x22,x23輛;購買C種汽車依次有x31,x32,x33輛.因此有10/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)成本最低？10/7/202368解設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ù)學模型為：代入具體數(shù)據(jù)，得數(shù)學模型如下：10/7/20236910/7/202370(十二)、投資問題投資者經(jīng)常會遇到投資項目的組合選擇問題，要考慮的因素有收益率、風險、增長潛力等條件，并進行綜合權衡，以求得一個最佳投資方案。例某投資公司有50萬元可用于長期投資，可供選擇的投資項目包括購買國庫券、購買公司債券、投資房地產(chǎn)、購買股票、銀行短期或長期儲蓄。各種投資方式的投資期限，年收益率，風險系數(shù)，增長潛力的具體參數(shù)見下表。若投資者希望投資組合的平均年限不超過5年，平均的期望收益率不低于13%，風險系數(shù)不超過4，收益的增長潛力不低于10%。問在滿足上述要求前提下，投機者該如何選擇投資組合使平均年平均收益率最高？10/7/202371序號投資方式投資期限（年）年收益率(%）風險系數(shù)增長潛力(%）1國庫券311102公司債券10153153房地產(chǎn)6258304股票2206205短期儲蓄110156長期儲蓄51221010/7/202372解設xi為第i種投資方式在總投資中所占的比利,則該數(shù)學模型為:10/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)每年初可購買公債,于當年畝歸還,并加利息6%.問該投資者應如何安排他的資金,確定給這些項目每年的投資額,使到第5年末能擁有的資金本利總額為最大?10/7/202374解記xiA,xiB,xiC,xiD(i=1,2,…5)分別表示第i年初給項目A,B,C,D的投資額,它們都是決策變量,為了便于書寫數(shù)學模型,列表如下:

年份項目12345AX1AX2AX3AX4ABX3BCX2CDX1DX2DX3DX4DX5D10/7/202375根據(jù)項目A，B，C，D的不同情況，在第5年末能收回的本利分別為：1.15x4A,1.25x3B,1.40x2C,及1.06x5D。因此目標函數(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,10/7/202376故有x3A+x3B+x3D=1.15x1A+1.06x2D.同理第4年、第5年有約束為：X4A+X4D=1.15X2A+1.06X3D,X5D=1.15X3A+1.06X4D.故本例數(shù)學模型經(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)

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

1、和式10/7/202379

3、矩陣式10/7/202380

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

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

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

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

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

1.2.3單純型表及其格式10/7/202387變換的方法：目標函數(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若xj0，令xj=-xj

，代入非標準型，則有xj

0若xj不限，令xj=xj

-

xj

，xj

0，xj

0，代入非標準型10/7/202388

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

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

關于檢驗數(shù)的數(shù)學解釋設

B

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

zj>0,則未達到最優(yōu)10/7/202392表1.2.4例1.2.2單純型表的迭代過程答：最優(yōu)解為x1=20,x2=20,x3=0,OBJ=170010/7/202393

單純型表中元素的幾點說明任何時候，基變量對應的列都構成一個單位矩陣當前表中的b列表示當前基變量的解值，通過變換B

1b

得到(資源已變成產(chǎn)品)當前非基變量對應的向量可通過變換B

1AN

得到，表示第j個變量對第i行對應的基變量的消耗率非基變量的機會成本由給出注意基變量所對應的行10/7/202394表1.3.1例1.3.1的單純型表迭代過程答：最優(yōu)解為x1=2,x2=2,x3=0,OBJ=3610/7/202395從圖解法作圖結果來分析,線性規(guī)劃應有以下幾種可能出現(xiàn)的結果:(1)有唯一最優(yōu)解(2)有無窮多最優(yōu)解(3)無界解(也稱無最優(yōu)解)10/7/2023962.4線性規(guī)劃的對偶理論及其應用窗含西嶺千秋雪，門泊東吳萬里船對偶是一種普遍現(xiàn)象10/7/2023972.4.1對偶問題的提出例1、某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的利潤、所消耗的材料、工時及每天的材料限額如下表，試問如何安排生產(chǎn)，使每天所得利潤最大？設每天生產(chǎn)甲、乙兩種產(chǎn)品分別為x1件,x2件甲乙限額材料工時23322426利潤4310/7/202398現(xiàn)在從另一種角度來討論.假設工廠考慮不安排生產(chǎn),而是出售材料,出租工時,部如何定價,可使工廠獲利不低于安排生產(chǎn)所獲得的收益,且又能使這些定價具有競爭力?設出售材料的定價為每單位y1元,出租工時定價為每工時y2元,從工廠考慮,這些定價的獲利不應低于安排生產(chǎn)所獲得的收益,否則工廠寧愿生產(chǎn),而不出售和出租.由此,工廠生產(chǎn)一件單產(chǎn)品所消耗的材料和工時的總價值不低于4元,即有同樣,從乙產(chǎn)品考慮,亦有為使這些定價有競爭力,目標函數(shù)為10/7/202399綜合起來,該問題的數(shù)學模型為:10/7/2023100任何線性規(guī)劃問題都有其對偶問題對偶問題有其明顯的經(jīng)濟含義假設有商人要向廠方購買資源A和B，問他們談判原料價格的模型是怎樣的？10/7/2023101例2設A、B資源的出售價格分別為y1和y2顯然商人希望總的收購價越小越好工廠希望出售資源后所得不應比生產(chǎn)產(chǎn)品所得少目標函數(shù)ming(y)=25y1+15y210/7/20231022.4.2線性規(guī)劃原問題與對偶問題的表達形式

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

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

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

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

x1x2

…xn原關系minWy1y2

yma11a12…

a1n

a21a22.…

a2n

am1am2…

amn≤≤

≤b1b1

b1

對偶關系≥≥…≥maxZc1c2

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

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

1.邊際值(影子價)qi以(max,)為例邊際值(影子價)qi是指在最優(yōu)解的基礎上，當?shù)趇個約束行的右端項bi減少一個單位時，目標函數(shù)的變化量10/7/2023116例110/7/2023117影子價格的說明影子價是資源最優(yōu)配置下資源的理想價格，資源的影子價與資源的緊缺度有關松弛變量增加一個單位等于資源減少一個單位剩余變量增加一個單位等于資源增加一個單位資源有剩余，在最優(yōu)解中就有對應松弛變量存在，且其影子價為0影子價為0，資源并不一定有剩余應用，郵電產(chǎn)品的影子價格10/7/2023118

2價值系數(shù)cj的靈敏度分析cj

變動可能由于市場價格的波動，或生產(chǎn)成本的變動cj的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj

允許的變動范圍

cj

cj的變化會引起檢驗數(shù)的變化，有兩種情況非基變量對應的價值系數(shù)變化，不影響其它檢驗數(shù)基變量對應的價值系數(shù)變化，影響所有非基變量檢驗數(shù)1、非基變量對應的價值系數(shù)的靈敏度分析10/7/2023119例210/7/20231202、基變量對應的價值系數(shù)的靈敏度分析由于基變量對應的價值系數(shù)在CB中出現(xiàn)，因此它會影響所有非基變量的檢驗數(shù)只有一個基變量的cj

發(fā)生變化，變化量為cj

令cj

在CB中的第k行，研究非基變量xj

機會成本的變化10/7/2023121設x4的價值系數(shù)增加

c4，對應k=2，

有一邊為空集如何處理

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

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

3.右端項bi的靈敏度分析設XB=B

1b是最優(yōu)解，則有XB=B

1b0b的變化不會影響檢驗數(shù)b的變化量b可能導致原最優(yōu)解變?yōu)榉强尚薪?0/7/20231234.右端項bi的靈敏度分析10/7/2023124以b2為例,x6是對應的初始基變量，所以有10/7/20231255.技術系數(shù)aij的靈敏度分析技術系數(shù)aij變化的影響比較復雜對應基變量的aij，且資源bi已全部用完對應基變量的aij，但資源bi未用完對應非基變量的aij，且資源bi全用完或未用完1、對應基變量的aij，且資源bi已全部用完

aij=02、對應基變量的aij，但資源bi未用完

aij

xn+i/xj上述兩個公式不充分，為什么？B–1發(fā)生變化，從而引起非基變量檢驗數(shù)cj–zj的變化3、對應非基變量的aij只影響對應非基變量xj的檢驗數(shù)cj–zj

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

010/7/202312610/7/2023127x1,x3為非基變量，q1=0,q2=0.25,q3=1,故有x2,x4為基變量，x5=100,b1有剩余，故有10/7/20231286.新增決策變量的分析例2.4.2中，若新增產(chǎn)品x8，問是否生產(chǎn)？已知c8=9,a18=5,a28=4,a38=3計算x8的檢驗數(shù)可知生產(chǎn)是否有利結論：生產(chǎn)x8有利。將B–1P8加入最優(yōu)單純型表中，以x8為入變量進行迭代10/7/20231297.新增約束條件的分析1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2、若不滿足，則當前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標準型3、利用對偶單純型法繼續(xù)迭代為什么可以利用對偶單純型法例2.4.2第2步10/7/202313010/7/2023131注意：最優(yōu)解的目標函數(shù)減少了25個單位10/7/20231328靈敏度分析舉例例3某工廠生產(chǎn)三種產(chǎn)品A,B,C，有五種生產(chǎn)組合方案。下兩表給出有關數(shù)據(jù)。規(guī)定每天供應A產(chǎn)品至少110個，求收益最大的生產(chǎn)方案。10/7/2023133例4解：設xj為已選定各種組合方案的組數(shù)(j=1,2,…,5)，x6為A產(chǎn)品的剩余變量，x7，x8分別為工人工時和機器工時的松弛變量。10/7/2023134

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

節(jié)中

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

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

i第i種資源的單位費用變化量，

i不限

i

i變化對cj的影響率10/7/2023136例5資源b1變化量

1，

j=a1j10/7/2023137例6資源b1變化量

1與c510/7/20231389參數(shù)bi的變化分析例2.4.2中，將b1,b2,b3理解為三個車間的周工時資源。假設從第1向2車間調動工人

個，每個工人的周工時為40小時，問調動多少工人不會破壞最優(yōu)產(chǎn)品組合10/7/2023139三、動態(tài)規(guī)劃有許多決策過程是多階段的，即動態(tài)的，動態(tài)規(guī)劃就是一類多階段決策過程的最優(yōu)化方法。一、動態(tài)規(guī)劃的基本概念和基本原理例最短路問題。下圖給出了一路線網(wǎng)絡，箭桿旁的數(shù)字為兩點間的路程?，F(xiàn)求從A到E的最短路。A到E有3×3×2×1=18條不同的路線，如果階段數(shù)增加，則路的條數(shù)也增加，用窮舉法顯然不可取，而用動態(tài)規(guī)劃方法只需計算其中一部分便可求A到E的最短路線，并且還可得出任何一點到終點F的最短路線。10/7/2023140AB1B2B3C1C2C3D1D2E2437632441514633333434476117481110/7/2023141階段：根據(jù)時間和空間將問題劃分成若干個互相有關聯(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.決策：當階段和狀態(tài)給定后，從該狀態(tài)到下一階段某狀態(tài)的選擇。描述決策的變量稱為決策變量，記為xk或x(sk)，它表示第k階段處于狀態(tài)sk時采取的決策，是狀態(tài)sk的函數(shù)。決策變量的取值范圍稱為允許決策集合，記為Xk或X(Sk)，即xk∈Xk.10/7/2023142狀態(tài)轉移方程：描述狀態(tài)轉移規(guī)律的函數(shù)關系sk=T(sk,xk)當sk和xk取定后，sk+1的取值就隨之確定。策略：各階段所確定的決策構成的決策序列。即{x1(s1),x2(s2),…,xn(sn)}目的是從眾多的策略中選擇最優(yōu)策略，記為{x1*(s1),x2*(s2),…,xn*(sn)}10/7/2023143報酬函數(shù)：當過程處于狀態(tài)sk，采取決策xk時所得的報酬（或費用），通常記為vk(sk,xk)。上例中的vk為第k階段到k+1階段兩點間的路程。目標（指標）函數(shù)：衡量策略好壞的函數(shù)從第k階段的sk出發(fā)到終點的目標函數(shù)記為vkn=vkn(sk,xk,…xn),最優(yōu)目標函數(shù)值記為fk*(sk)=optvkn(sk,xk,…xn)，上例是求f1*(A)對應的策略10/7/2023144最優(yōu)化原理：從上例看出，AB2C1D1E是A到E的最短路線，則B2C1D1E是B2出發(fā)到E的最短路。C1D1E是C1出發(fā)到E的最短路。

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

00.40

0.60

0.80

10.200.400.50

20.15

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

10/7/2023153若設由于sk,,xk均取幾個離散值,所以可將三個階段的計算過程分別列入下面三個表中新產(chǎn)品的補加研制費,則相應的動態(tài)規(guī)劃為表示分配給第k至第3種10/7/2023154第三階段（k=3)x3s3p3(x3)F3*(s3)X3*01200.800.80010.500.50120.300.302S3=x310/7/2023155第二階段x2S2p2(s2)·f3*(s3)f2*(s2)X2*01200.480.48010.300.320.30020.180.200.160.162S2=x2+S310/7/2023156第一階段x1S1p1(x1)·f2*(s2)f1*(s1)x1*01220.0640.060.0720.061S1=2=x1+S2于是得最優(yōu)解:都不成功的概率為0.0610/7/2023157二、背包問題背包問題的一般提法是：一旅行者攜帶背包去登山，已知他所能承受的背包重量限制為a千克，現(xiàn)有n種物品可供他選擇裝入背包,第i種物品的單件重量為ai千克,其價值(可以是表明本物品對登山的重要性的數(shù)量指標)是攜帶數(shù)量xi的函數(shù)ci(xi)(i=1...n).問旅行者如何選擇攜帶各種物品的件數(shù),以使總價值最大?背包問題等同于車、船、飛機、人造衛(wèi)星等工具的裝載問題,還可以用于解決機床加工中零件最優(yōu)加工、下料問題,投資決策等.10/7/2023158解設xi為第i種物品裝入的件數(shù)，則下面用動態(tài)規(guī)劃順序解法建模求解10/7/2023159階段k:將可裝入物品按1，2，…,n排序，每段裝一種物品，共劃分n個階段。K=1,2,…,n.狀態(tài)變量sk+1:在第k段開始時，背包中允許裝入前k種物品的總重量。決策變量xk:裝入第k種物品的件數(shù)。狀態(tài)轉移方程：sk=sk+1-aksk允許決策集合：10/7/2023160最優(yōu)指標函數(shù)fk(sk+1)表示在背包中允許裝入物品的總重量不超過sk+1千克，采用最優(yōu)策略只裝前k種物品時的最大使用價值。則可得到動態(tài)規(guī)劃的順序遞推方程為：用前向動態(tài)規(guī)劃方法逐步計算f1(s2),f2(s3),…,fn(sn+1)及相應的決策函數(shù)x1(s2),x2(s3),…,xn(sn+1),最后得到的fn(a)即為所求的最大值，相應的最優(yōu)策略則由反推計算得出。10/7/2023161三、設備更新問題

企業(yè)中經(jīng)常會遇到因設備陳舊或損壞需要更新的問題。從經(jīng)濟學上分析，一臺設備應該用多少年更新最合算，這就是設備更新問題。一般來說，一臺設備在比較新時，年運轉量大，經(jīng)濟收入高，故障少，維修費用少，但隨著使用年限的增加，年運轉量減少因而收入減少，故障增多維修費用增加。如果更新可提高凈收入，但是當年要支出一筆數(shù)額較大的購買費，為了比較不同決策的優(yōu)劣，常常要在一個較長的時間內(nèi)考慮更新決策問題。10/7/2023162設備更新問題一般提法是：在已知一臺設備的效益函數(shù)r(t),維修費用函數(shù)u(t)及更新費用函數(shù)c(t)的條件下，要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設備還是更換一臺新的，使n年總效益最大。

10/7/2023163四、復合系統(tǒng)工作可靠性問題某種機器的工作系統(tǒng)由n個部件組成，只要一個部件失靈，整個系統(tǒng)就不能正常工作。為提高系統(tǒng)的可靠性，在每個部件上都裝有主要元件備用件，并設計了備用元件自動投入裝置。顯然，備用元件越多，整個系統(tǒng)工作的可靠性越大，但備用元件增多也會導致系統(tǒng)的成本、重量、體積相應增大，工作精度降低。因此，在考慮上述限制條件下，如何選擇各部件的備用元件數(shù)，使整個系統(tǒng)可靠性最大。10/7/2023164

串聯(lián)系統(tǒng)可靠性問題例有A,B,C三部機器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計結果表明，機器A,B,C產(chǎn)生次品的概率分別為pA=30%,PB=40%,PC=20%,而產(chǎn)品必須經(jīng)過三部機器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進行技術改造，以便最大限度地提高產(chǎn)品的成品率指標。現(xiàn)提出如下四種改進方案：方案1:不撥款，機器保持原狀；方案2:加裝監(jiān)視設備，每部機器需款1萬元；方案3:加裝設備，每部機器需款2萬元；方案4:同時加裝監(jiān)視及控制設備，每部機器需款3萬元；采用各方案后，各部機器的次品率如下表。10/7/2023165

解：為三臺機器分配改造撥款，設撥款順序為A,B,C，階段序號反向編號為k，即第一階段計算給機器C撥款的效果。設sk

為第k

階段剩余款，則邊界條件為s3=5；設xk

為第k

階段的撥款額；狀態(tài)轉移方程為sk-1=sk-xk；目標函數(shù)為maxR=(1-PA)(1-PB)(1-PC)仍采用反向遞推第一階段：對機器C撥款的效果

R1(s1,x1)=d1(s1,x1)

R0(s0,x0)=d1(s1,x1)10/7/2023166第二階段最優(yōu)決策表第二階段：對機器B,C撥款的效果由于機器A最多只需3萬元，故s2

2遞推公式：R2(s2,x2)=d2(s2,x2)

R1(s1,x1*)例：R2(3,2)=d2(3,2)

R1(1,1)=(1-0.2)0.9=0.72得第二階段最優(yōu)決策表10/7/2023167第二階段最優(yōu)決策表第三階段：對機器A,

B,C