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

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

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

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

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

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

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

4/30/20247

MCM的發(fā)展歷程

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

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

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

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

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

建模的步驟

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

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

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

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

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

５）模型分析：對(duì)所得到的解答進(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)和完善。4/30/2024114/30/202412模型的分類按模型的應(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ī)劃論模型

馬氏鏈模型4/30/202413按人們對(duì)事物發(fā)展過(guò)程的了解程度分類

白箱模型：

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

灰箱模型：

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

黑箱模型：

指一些其內(nèi)部規(guī)律還很少為人們所知的現(xiàn)象。如生命科學(xué)、社會(huì)科學(xué)等方面的問(wèn)題。但由于因素眾多、關(guān)系復(fù)雜，也可簡(jiǎn)化為灰箱模型來(lái)研究。4/30/202414數(shù)學(xué)建模應(yīng)用今天，在國(guó)民經(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)過(guò)程中產(chǎn)品質(zhì)量指標(biāo)的預(yù)報(bào)、氣象預(yù)報(bào)、人口預(yù)報(bào)、經(jīng)濟(jì)增長(zhǎng)預(yù)報(bào)等等，都要有預(yù)報(bào)模型。使經(jīng)濟(jì)效益最大的價(jià)格策略、使費(fèi)用最少的設(shè)備維修方案，是決策模型的例子。

4/30/202415控制與優(yōu)化

電力、化工生產(chǎn)過(guò)程的最優(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ī)劃、水庫(kù)優(yōu)化調(diào)度，以及排隊(duì)策略、物資管理等，都可以用運(yùn)籌學(xué)模型解決。4/30/202416大學(xué)生數(shù)學(xué)建模競(jìng)賽試題題目

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

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

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

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

DVD在線租賃2006年：出版社的資源配置艾滋病療法的評(píng)價(jià)及療效的預(yù)測(cè)2007年：中國(guó)人口增長(zhǎng)預(yù)測(cè)

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

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

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

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

2.兩個(gè)變量問(wèn)題的圖解法

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)解的概念4/30/202424運(yùn)籌學(xué)

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

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

4/30/202435

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

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

...c1na1A2c21c22

...c2na2

...

...

...

...

...

...Amcm1cm2

...

cmnam需求量b1b2

...

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

設(shè)xij=0,否則

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

4/30/202438(三)、網(wǎng)絡(luò)問(wèn)題

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

2154

20128915107

141081231364/30/202439最短路問(wèn)題解：設(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ā)的汽車(chē)為一輛）-x12+x24+x25=0-x13+x34+x36=0-x24-x34+x45+x47=04/30/202440-x25-x45+x56+x57=0-x36-x56+x67=0-x47-x57-x67=-1（到達(dá)7的汽車(chē)為一輛）Xij=0,或1,i,j=1,2,…7.4/30/202441(四)、生產(chǎn)活動(dòng)問(wèn)題例：某公司有m種資源B1，B2，…，Bm(如機(jī)器的可用工時(shí)，勞力，原材料等），生產(chǎn)n種不同的產(chǎn)品A1，A2，．．．Ａn.其單位消耗，單位利潤(rùn)等如表．問(wèn)如何安排生產(chǎn)使利潤(rùn)最大．解設(shè)xj表示第j種產(chǎn)品的產(chǎn)量，則可得線性規(guī)劃模型：4/30/202442

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

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

b1b2...

bm單位利潤(rùn)

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

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

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

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

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

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

4/30/202450模型中，xi,yi已知，ui,vi,a,b為決策變量。原問(wèn)題化為含（2n+2)個(gè)決策變量，n個(gè)約束方程的一極小化問(wèn)題。4/30/202451(七)、人員安排問(wèn)題例某公司的營(yíng)業(yè)時(shí)間是上午8點(diǎn)到22點(diǎn)，以兩小時(shí)為一時(shí)段，各時(shí)段內(nèi)所需的服務(wù)人員數(shù)如下表，每個(gè)服務(wù)人員可在任一時(shí)段開(kāi)始上班，但要工作8小時(shí)，而工資都相同。問(wèn)應(yīng)如何安排服務(wù)人員使公司所付工資總數(shù)最少。4/30/202452序號(hào)時(shí)間區(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

54/30/202453解設(shè)xi為時(shí)段i開(kāi)始工作的人數(shù)（i=1,2,3,4).由于各班工資相同，要求公司所付的工資最少也就是要求服務(wù)人員最少。于是可得整數(shù)規(guī)劃模型：4/30/202454例某公司的營(yíng)業(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íng)業(yè)時(shí)間內(nèi)都有人上班，公司安排了四個(gè)班次，其班次和休息時(shí)間安排如下表一。各時(shí)段需求的人數(shù)如上例之表，只是第6、7段合并為18點(diǎn)到21點(diǎn)，需求人數(shù)為10人。問(wèn)應(yīng)如何安排服務(wù)人員既滿足需求又使公司所付工資總數(shù)最少。4/30/202455

表一班次工作時(shí)間休息時(shí)間月工資

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

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

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:000011104/30/202458設(shè)xi表示第i班安排的人數(shù)（i=1,2,3,4)，則可得整數(shù)規(guī)劃模型：4/30/202459(八)、套裁下料問(wèn)題例某車(chē)間接到制作100套鋼架的定單，每套鋼架要用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根，已知原料長(zhǎng)7.4m。問(wèn)應(yīng)如何下料，可使所用原料最省解:可能截法

方法下料根數(shù)長(zhǎng)度/m123456782.9211100002.1021032101.510130234合計(jì)料頭7.30.17.10.36.50.97.406.31.17.20.26.60.66.01.44/30/202460

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

x1kg普通洗衣粉

0.5x0kg洗衣粉x2kg濃縮洗衣粉

X0kg原料x(chóng)3kg普通洗滌劑

0.3x0kg洗滌劑x4kg高級(jí)洗滌劑4/30/202463解設(shè)每日生產(chǎn)普通洗衣粉的產(chǎn)量為x1kg

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

x3kg

，生產(chǎn)高級(jí)洗滌劑x4kg，每日加工原料x(chóng)0kg.

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

約束條件為加工過(guò)程中物流的平衡約束及原料供應(yīng)限制：4/30/202464

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

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

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

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

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

年份項(xiàng)目

1

2

3

4

5AX1AX2AX3AX4ABX3BCX2CDX1DX2DX3DX4DX5D4/30/202475根據(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萬(wàn)元資金，故有

x1A+x1D=10000.

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

x2A+x2C+x2D=1.06x1D.

第3年年初該投資者擁有資金從D項(xiàng)目收回的本金：1.06x2D,及從項(xiàng)目A中第1年投資收回的本金：1.15x1A,4/30/202476故有

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)

4/30/2024771線性規(guī)劃問(wèn)題及數(shù)學(xué)模型1.1問(wèn)題的提出(見(jiàn)前述模型)1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型4/30/202478

1、和式4/30/202479

3、矩陣式4/30/202480

1.1.3線性規(guī)劃的圖解法f(x)=364/30/202481

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

1.2.2單純型法的基本思路4/30/202483

1.2.3單純型表及其格式4/30/202484

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

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

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

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

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

，稱為松弛變量；同時(shí)令cn+i

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

，稱為剩余變量；同時(shí)令cn+i

=0若xj

0，令

xj=-xj

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

0若xj

不限，令

xj=xj

-

xj

，

xj

0，xj

0，代入非標(biāo)準(zhǔn)型4/30/202488

1.2.2單純型法的基本思路4/30/202489

1.2.3單純型表及其格式4/30/202490例1.2.2試列出下面線性規(guī)劃問(wèn)題的初始單純型表4/30/202491

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

B

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

個(gè)非基變量的機(jī)會(huì)成本如(4)式若有cj

zj>0,則未達(dá)到最優(yōu)4/30/202492表1.2.4例1.2.2單純型表的迭代過(guò)程答：最優(yōu)解為x1=20,x2=20,x3=0,OBJ=17004/30/202493

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

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

1b

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

1AN

得到，表示第j

個(gè)變量對(duì)第i

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

限額材料工時(shí)23322426利潤(rùn)

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

和

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

2.4.2線性規(guī)劃原問(wèn)題與對(duì)偶問(wèn)題的表達(dá)形式

1.對(duì)稱形式的對(duì)偶問(wèn)題4/30/2024103見(jiàn)問(wèn)題提出4/30/2024104原規(guī)劃(LP)對(duì)偶規(guī)劃(DP)4/30/2024105

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

行原問(wèn)題的價(jià)值系數(shù)C

變換為對(duì)偶問(wèn)題的右端項(xiàng)原問(wèn)題的右端項(xiàng)

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

xjyj

x1x2

…

xn原關(guān)系minW

y1y2

ym

a11a12…

a1n

a21a22.…

a2n

am1am2…

amn

≤≤

≤b1b1

b1

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

c1c2

…

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

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

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

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

個(gè)約束行的右端項(xiàng)bi

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

2價(jià)值系數(shù)cj

的靈敏度分析cj

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

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

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

cj

cj

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

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

令cj

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

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

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

有一邊為空集如何處理

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

與對(duì)偶單純型法找入變量的公式一樣4/30/2024122

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)榉强尚薪?/30/2024123

4.右端項(xiàng)bi的靈敏度分析4/30/2024124以b2為例,x6是對(duì)應(yīng)的初始基變量，所以有4/30/2024125

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

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

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

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

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

，且資源bi已全部用完

aij=02、對(duì)應(yīng)基變量的aij

，但資源bi未用完

aij

xn+i

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

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

cj–zj

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

04/30/20241264/30/2024127x1,x3為非基變量，q1=0,q2=0.25,q3=1,故有x2,x4為基變量，x5=100,b1有剩余，故有4/30/2024128

6.新增決策變量的分析例2.4.2中，若新增產(chǎn)品x8，問(wèn)是否生產(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)行迭代4/30/2024129

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

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

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

節(jié)中

aij,bi,cj

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

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

i

第i種資源的單位費(fèi)用變化量，

i

不限

i

i變化對(duì)cj

的影響率4/30/2024136

例5資源b1變化量

1，

j=a1j4/30/2024137例6資源b1變化量

1與

c54/30/2024138

9

參數(shù)bi的變化分析例2.4.2中，將b1,b2,b3理解為三個(gè)車(chē)間的周工時(shí)資源。假設(shè)從第1向2車(chē)間調(diào)動(dòng)工人

個(gè)，每個(gè)工人的周工時(shí)為40小時(shí)，問(wèn)調(diào)動(dòng)多少工人不會(huì)破壞最優(yōu)產(chǎn)品組合4/30/2024139三、動(dòng)態(tài)規(guī)劃有許多決策過(guò)程是多階段的，即動(dòng)態(tài)的，動(dòng)態(tài)規(guī)劃就是一類多階段決策過(guò)程的最優(yōu)化方法。一、動(dòng)態(tài)規(guī)劃的基本概念和基本原理例最短路問(wèn)題。下圖給出了一路線網(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的最短路線。4/30/2024140AB1B2B3C1C2C3D1D2E243763244151463333343447611748114/30/2024141階段：根據(jù)時(shí)間和空間將問(wèn)題劃分成若干個(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.4/30/2024142狀態(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)}4/30/2024143報(bào)酬函數(shù)：當(dāng)過(guò)程處于狀態(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)對(duì)應(yīng)的策略4/30/2024144最優(yōu)化原理：從上例看出，

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

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

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

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

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

0

0.40

0.60

0.80

1

0.20

0.40

0.50

2

0.15

0.20

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

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

0

1

200.800.80

0

10.500.50

1

20.300.30

2S3=x34/30/2024155第二階段x2S2p2(s2)·f3*(s3)f2*(s2)X2*01200.480.48010.300.320.30020.180.200.160.162S2=x2+S34/30/2024156第一階段x1S1p1(x1)·f2*(s2)f1*(s1)x1*

0

1

2

20.0640.060.0720.06

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

背包問(wèn)題等同于車(chē)、船、飛機(jī)、人造衛(wèi)星等工具的裝載問(wèn)題,還可以用于解決機(jī)床加工中零件最優(yōu)加工、下料問(wèn)題,投資決策等.4/30/2024158解設(shè)xi為第i種物品裝入的件數(shù)，則下面用動(dòng)態(tài)規(guī)劃順序解法建模求解4/30/2024159階段k:將可裝入物品按1，2，…,n排序，每段裝一種物品，共劃分n個(gè)階段。K=1,2,…,n.狀態(tài)變量sk+1:在第k段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量。決策變量xk:裝入第k種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程：sk=sk+1-aksk允許決策集合：4/30/2024160最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示在背包中允許裝入物品的總重量不超過(guò)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ì)算得出。4/30/2024161三、設(shè)備更新問(wèn)題

企業(yè)中經(jīng)常會(huì)遇到因設(shè)備陳舊或損壞需要更新的問(wèn)題。從經(jīng)濟(jì)學(xué)上分析，一