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

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

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

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

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

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

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

10/7/20237

MCM的發(fā)展歷程

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

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

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

建模的步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

按是否考慮隨機(jī)因素分類

確定性模型

隨機(jī)性模型按是否考慮模型的變化分類

靜態(tài)模型

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

離散模型

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

幾何模型

微分方程模型

圖論模型

規(guī)劃論模型

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

白箱模型：

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

灰箱模型：

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

黑箱模型：

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

分析與設(shè)計(jì)

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

預(yù)報(bào)與決策

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

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

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

規(guī)劃與管理

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

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

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

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

乘公交，看奧運(yùn)

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

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

1.線性規(guī)劃問題的數(shù)學(xué)模型2.兩個(gè)變量問題的圖解法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)解的概念10/7/202324運(yùn)籌學(xué)

OperationalResearch運(yùn)籌帷幄，決勝千里

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

10/7/202335

銷地運(yùn)價(jià)產(chǎn)地

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

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

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

20128915107

1410812313610/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=010/7/202340-x25-x45+x56+x57=0-x36-x56+x67=0-x47-x57-x67=-1（到達(dá)7的汽車為一輛）Xij=0,或1,i,j=1,2,…7.10/7/202341(四)、生產(chǎn)活動(dòng)問題例：某公司有m種資源B1，B2，…，Bm(如機(jī)器的可用工時(shí)，勞力，原材料等），生產(chǎn)n種不同的產(chǎn)品A1，A2，．．．Ａn.其單位消耗，單位利潤等如表．問如何安排生產(chǎn)使利潤最大．解設(shè)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變量。設(shè)第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為不同型號的兩臺(tái)機(jī)器的可用工時(shí)，而n種產(chǎn)品可在任一臺(tái)上加工，這時(shí)第1，2兩個(gè)約束條件就是互排斥的，只能選擇一個(gè)進(jìn)入模型。如果引入0–1變量10/7/202345

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

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

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

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

表一班次工作時(shí)間休息時(shí)間月工資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解為了便于建立模型，可用各班中途休息的起止時(shí)刻和上例之表中時(shí)間區(qū)間的起止時(shí)間分細(xì)，并求出各班工作的關(guān)聯(lián)表，見表二。表中j列的“1”表示該班次在相應(yīng)的時(shí)段內(nèi)工作，“0”表示不工作。10/7/202357表二時(shí)段班次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設(shè)xi表示第i班安排的人數(shù)（i=1,2,3,4)，則可得整數(shù)規(guī)劃模型：10/7/202359(八)、套裁下料問題例某車間接到制作100套鋼架的定單，每套鋼架要用長為2.9m,2.1m,1.5m的圓鋼各一根，已知原料長7.4m。問應(yīng)如何下料，可使所用原料最省解:可能截法

方法下料根數(shù)長度/m123456782.9211100002.1021032101.510130234合計(jì)料頭7.30.17.10.36.50.97.406.31.17.20.26.60.66.01.410/7/202360假設(shè)按方法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元，供應(yīng)量無限制。該廠加工1kg原料可產(chǎn)出0.5kg普通洗衣粉和0.3kg普通洗滌劑。工廠還可以對普通洗衣粉和普通洗滌劑進(jìn)行精加工。加工1kg普通洗衣粉可得0.5kg濃縮洗衣粉，加工1kg普通洗滌劑可產(chǎn)出0.25kg高級洗滌劑，加工示意圖下圖，市場售價(jià)為：每kg普通洗衣粉為8元；每kg濃縮洗衣粉為24元；每kg普通洗滌劑為12元；每kg高級洗滌劑為55元。每加工1kg原料的加工成本為1元，每1kg精加工產(chǎn)品的成本為3元，工廠設(shè)備每天最多可處理4t原料，而對精加工沒有限制。若市場對產(chǎn)品也沒有限制，問該廠應(yīng)如何安排生產(chǎn)能使每日利潤最大？10/7/202362

x1kg普通洗衣粉

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

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

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

年份項(xiàng)目12345AX1AX2AX3AX4ABX3BCX2CDX1DX2DX3DX4DX5D10/7/202375根據(jù)項(xiàng)目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項(xiàng)目收回的本金：1.06x2D,及從項(xiàng)目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ù)學(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)

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

1、和式10/7/202379

3、矩陣式10/7/202380

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

線性規(guī)劃問題的幾個(gè)特點(diǎn)：線性規(guī)劃問題的可性解的集合是凸集線性規(guī)劃問題的基礎(chǔ)可行解一般都對應(yīng)于凸集的極點(diǎn)凸集的極點(diǎn)的個(gè)數(shù)是有限的最優(yōu)解只可能在凸集的極點(diǎn)上，而不可能發(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ī)劃問題的標(biāo)準(zhǔn)形式為了使線性規(guī)劃問題的解法標(biāo)準(zhǔn)，就要把一般形式化為標(biāo)準(zhǔn)形式10/7/202386

1.2.3單純型表及其格式10/7/202387變換的方法：目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號。令f

(x)=-f(x)=-CX,有minf(x)=-max[-

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

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

=0第i個(gè)約束為型，在不等式左邊減去一個(gè)非負(fù)的變量xn+i，稱為剩余變量；同時(shí)令cn+i

=0若xj0，令xj=-xj

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

0若xj不限，令xj=xj

-

xj

，xj

0，xj

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

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

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

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

B

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

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

單純型表中元素的幾點(diǎn)說明任何時(shí)候，基變量對應(yīng)的列都構(gòu)成一個(gè)單位矩陣當(dāng)前表中的b列表示當(dāng)前基變量的解值，通過變換B

1b

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

1AN

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

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

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

變換為對偶問題的右端項(xiàng)原問題的右端項(xiàng)

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

x1x2

…xn原關(guān)系minWy1y2

yma11a12…

a1n

a21a22.…

a2n

am1am2…

amn≤≤

≤b1b1

b1

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

…cn這些關(guān)系可用下表表示：10/7/20231072.非對稱形式的對偶問題設(shè)線性規(guī)劃問題由于（1）故（1）可改寫為10/7/2023108從而對偶問題為：即：又令顯然Y無約束，得（1）對偶問題：10/7/2023109表2.13對偶變換的規(guī)則約束條件的類型與非負(fù)條件對偶非標(biāo)準(zhǔn)的約束條件類型對應(yīng)非正常的非負(fù)條件對偶變換是一一對應(yīng)的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每個(gè)參數(shù)發(fā)生多大的變化不會(huì)破壞最優(yōu)解靈敏度越小，解的穩(wěn)定性越好10/7/2023115

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

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

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

允許的變動(dòng)范圍

cj

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

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

令cj

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

機(jī)會(huì)成本的變化10/7/2023121設(shè)x4的價(jià)值系數(shù)增加

c4，對應(yīng)k=2，

有一邊為空集如何處理

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

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

3.右端項(xiàng)bi的靈敏度分析設(shè)XB=B

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

1b0b的變化不會(huì)影響檢驗(yàn)數(shù)b的變化量b可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪?0/7/20231234.右端項(xiàng)bi的靈敏度分析10/7/2023124以b2為例,x6是對應(yīng)的初始基變量，所以有10/7/20231255.技術(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未用完

aij

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

若aij>0，不會(huì)破壞最優(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計(jì)算x8的檢驗(yàn)數(shù)可知生產(chǎn)是否有利結(jié)論：生產(chǎn)x8有利。將B–1P8加入最優(yōu)單純型表中，以x8為入變量進(jìn)行迭代10/7/20231297.新增約束條件的分析1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2、若不滿足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標(biāo)準(zhǔn)型3、利用對偶單純型法繼續(xù)迭代為什么可以利用對偶單純型法例2.4.2第2步10/7/202313010/7/2023131注意：最優(yōu)解的目標(biāo)函數(shù)減少了25個(gè)單位10/7/20231328靈敏度分析舉例例3某工廠生產(chǎn)三種產(chǎn)品A,B,C，有五種生產(chǎn)組合方案。下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應(yīng)A產(chǎn)品至少110個(gè)，求收益最大的生產(chǎn)方案。10/7/2023133例4解：設(shè)xj為已選定各種組合方案的組數(shù)(j=1,2,…,5)，x6為A產(chǎn)品的剩余變量，x7，x8分別為工人工時(shí)和機(jī)器工時(shí)的松弛變量。10/7/2023134

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

節(jié)中

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

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

i第i種資源的單位費(fè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理解為三個(gè)車間的周工時(shí)資源。假設(shè)從第1向2車間調(diào)動(dòng)工人

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

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

00.40

0.60

0.80

10.200.400.50

20.15

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

10/7/2023153若設(shè)由于sk,,xk均取幾個(gè)離散值,所以可將三個(gè)階段的計(jì)算過程分別列入下面三個(gè)表中新產(chǎn)品的補(bǔ)加研制費(fèi),則相應(yīng)的動(dòng)態(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千克,其價(jià)值(可以是表明本物品對登山的重要性的數(shù)量指標(biāo))是攜帶數(shù)量xi的函數(shù)ci(xi)(i=1...n).問旅行者如何選擇攜帶各種物品的件數(shù),以使總價(jià)值最大?背包問題等同于車、船、飛機(jī)、人造衛(wèi)星等工具的裝載問題,還可以用于解決機(jī)床加工中零件最優(yōu)加工、下料問題,投資決策等.10/7/2023158解設(shè)xi為第i種物品裝入的件數(shù)，則下面用動(dòng)態(tài)規(guī)劃順序解法建模求解10/7/2023159階段k:將可裝入物品按1，2，…,n排序，每段裝一種物品，共劃分n個(gè)階段。K=1,2,…,n.狀態(tài)變量sk+1:在第k段開始時(shí)，背包中允許裝入前k種物品的總重量。決策變量xk:裝入第k種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程：sk=sk+1-aksk允許決策集合：10/7/2023160最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示在背包中允許裝入物品的總重量不超過sk+1千克，采用最優(yōu)策略只裝前k種物品時(shí)的最大使用價(jià)值。則可得到動(dòng)態(tài)規(guī)劃的順序遞推方程為：用前向動(dòng)態(tài)規(guī)劃方法逐步計(jì)算f1(s2),f2(s3),…,fn(sn+1)及相應(yīng)的決策函數(shù)x1(s2),x2(s3),…,xn(sn+1),最后得到的fn(a)即為所求的最大值，相應(yīng)的最優(yōu)策略則由反推計(jì)算得出。10/7/2023161三、設(shè)備更新問題

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

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

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

解：為三臺(tái)機(jī)器分配改造撥款，設(shè)撥款順序?yàn)锳,B,C，階段序號反向編號為k，即第一階段計(jì)算給機(jī)器C撥款的效果。設(shè)sk

為第k

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

為第k

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

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

R0(s0,x0)=d1(s1,x1)10/7/2023166第二階段最優(yōu)決策表第二階段：對機(jī)器B,C撥款的效果由于機(jī)器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)決策表第三階段：對機(jī)器A,

B,C