數(shù)學(xué)建模規(guī)劃理論及模型公開(kāi)課一等獎(jiǎng)優(yōu)質(zhì)課大賽微課獲獎(jiǎng)?wù)n件

1、 5.非線(xiàn)性規(guī)劃模型 前面介紹了線(xiàn)性規(guī)劃問(wèn)題，即目標(biāo)函數(shù)和約束條件都是線(xiàn)性函數(shù)規(guī)劃問(wèn)題，但在實(shí)際工作中，還經(jīng)常會(huì)碰到另一類(lèi)更普通規(guī)劃問(wèn)題，即目標(biāo)函數(shù)和約束條件中最少有一個(gè)是非線(xiàn)性函數(shù)規(guī)劃問(wèn)題，即非線(xiàn)性規(guī)劃問(wèn)題. 第1頁(yè) 實(shí)際上，客觀世界中問(wèn)題許多是非線(xiàn)性，給予線(xiàn)性大多是近似，是在作了科學(xué)假設(shè)和簡(jiǎn)化后得到. 為了利用線(xiàn)性知識(shí)，許多非線(xiàn)性問(wèn)題常進(jìn)行線(xiàn)性化處理. 但在實(shí)際問(wèn)題中，有一些是不能進(jìn)行線(xiàn)性化處理，不然將嚴(yán)重影響模型對(duì)實(shí)際問(wèn)題近似可依賴(lài)型.第2頁(yè) 因?yàn)榉蔷€(xiàn)性規(guī)劃問(wèn)題在計(jì)算上常是困難，理論上討論也不能像線(xiàn)性規(guī)劃那樣給出簡(jiǎn)練結(jié)果形式和全方面透徹結(jié)論. 這點(diǎn)又限制了非線(xiàn)性規(guī)劃應(yīng)用，所以，在數(shù)學(xué)建模

2、時(shí)，要進(jìn)行認(rèn)真分析，對(duì)實(shí)際問(wèn)題進(jìn)行合理假設(shè)、簡(jiǎn)化，首先考慮用線(xiàn)性規(guī)劃模型，若線(xiàn)性近似誤差較大時(shí)，則考慮用非線(xiàn)性規(guī)劃.第3頁(yè)非線(xiàn)性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式為：第4頁(yè)非線(xiàn)性規(guī)劃模型按約束條件可分為以下三類(lèi)： 無(wú)約束非線(xiàn)性規(guī)劃模型： 等式約束非線(xiàn)性規(guī)劃模型：第5頁(yè) 不等式約束非線(xiàn)性規(guī)劃模型：1) 無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題.針對(duì)上述三類(lèi)非線(xiàn)性規(guī)劃模型，其慣用求解基本思緒可歸納以下： 第6頁(yè)第7頁(yè)第8頁(yè) 在下降迭代算法中，搜索方向起著關(guān)鍵作用，而當(dāng)搜索方向確定后，步長(zhǎng)又是決定算法好壞主要原因. 非線(xiàn)性規(guī)劃只含一個(gè)變量，即一維非線(xiàn)性規(guī)劃能夠用一維搜索方法求得最優(yōu)解，一維搜索方法主要有進(jìn)退法和黃金分割法. 二維非線(xiàn)性規(guī)

3、劃也能夠像解線(xiàn)性規(guī)劃那樣用圖形求解. 對(duì)于二維非線(xiàn)性規(guī)劃，使用搜索方法是要用到梯度概念，最慣用搜索方法就是最速下降法.第9頁(yè)2) 只有等式約束非線(xiàn)性規(guī)劃問(wèn)題通?？捎孟ā⒗窭嗜粘俗臃ɑ蚍春瘮?shù)法，將其化為無(wú)約束問(wèn)題求解.3) 含有不等式約束非線(xiàn)性規(guī)劃問(wèn)題解起來(lái)很復(fù)雜，求解這一類(lèi)問(wèn)題，通常將不等式化為等式約束，再將約束問(wèn)題化為無(wú)約束問(wèn)題，用線(xiàn)性迫近方法將非線(xiàn)性規(guī)劃問(wèn)題化為線(xiàn)性規(guī)劃問(wèn)題. 下面介紹一個(gè)簡(jiǎn)單非線(xiàn)性規(guī)劃問(wèn)題例子，其中一些約束條件是等式，這類(lèi)非線(xiàn)性規(guī)劃問(wèn)題可用拉格朗日方法求解.第10頁(yè) 例7（石油最優(yōu)儲(chǔ)存方法）有一石油運(yùn)輸企業(yè)，為了降低開(kāi)支，希望作了節(jié)約石油存放空間.但要求存放石油能滿(mǎn)

4、足客戶(hù)要求.為簡(jiǎn)化問(wèn)題，假設(shè)只經(jīng)營(yíng)兩種油，各種符號(hào)表示意義如表4所表示.其中供給率指石油企業(yè)供給客戶(hù)速度.第11頁(yè)表4 各種符號(hào)表示意義表第i種油存放量第i種油價(jià)格第i種油供給率第i種油每單位存放費(fèi)用第i種油每單位存放空間總存放公式第12頁(yè)由歷史數(shù)據(jù)得到經(jīng)驗(yàn)公式為 :且提供數(shù)據(jù)如表5所表示：第13頁(yè)表5 數(shù)據(jù)表已知總存放空間第14頁(yè)代入數(shù)據(jù)后得到模型為：模型求解：拉格朗日函數(shù)形式為： 第15頁(yè)即:對(duì) 求各個(gè)變量偏導(dǎo)數(shù)，并令它們等于零，得: 第16頁(yè)解這個(gè)線(xiàn)性方程組得：從而可得最小值是 . 第17頁(yè)6、多目標(biāo)規(guī)劃模型 在許多實(shí)際問(wèn)題中，衡量一個(gè)方案好壞標(biāo)準(zhǔn)往往不止一個(gè)，比如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程

5、最遠(yuǎn)，又要燃料最省，還要精度最高. 這一類(lèi)問(wèn)題統(tǒng)稱(chēng)為多目標(biāo)最優(yōu)化問(wèn)題或多目標(biāo)規(guī)劃問(wèn)題. 我們先來(lái)看一個(gè)生產(chǎn)計(jì)劃例子.第18頁(yè)第19頁(yè)第20頁(yè)第21頁(yè)第22頁(yè)第23頁(yè)第24頁(yè)第25頁(yè)第26頁(yè)第27頁(yè)第28頁(yè)第29頁(yè)第30頁(yè)第31頁(yè)第32頁(yè)第33頁(yè)我們希望購(gòu)置DVD總數(shù)量最小，即 :由此，能夠得到問(wèn)題三雙目標(biāo)整數(shù)線(xiàn)性規(guī)劃模型以下： 第34頁(yè)第35頁(yè)第36頁(yè)第37頁(yè)第38頁(yè)表6 當(dāng) 時(shí)最小購(gòu)置量 值DVD編號(hào)D01D02D03D04D05D06D07D08D09D10最少購(gòu)置量14211724121719212214DVD編號(hào)D11D12D13D14D15D16D17D18D19D20最少購(gòu)置量18

6、181717172418161823DVD編號(hào)D21D22D23D24D25D26D27D28D29D30最少購(gòu)置量20182214181715121624DVD編號(hào)D31D32D33D34D35D36D37D38D39D40最少購(gòu)置量19222019222213171717DVD編號(hào)D41D42D43D44D45D46D47D48D49D50最少購(gòu)置量32201621221620152020第39頁(yè)續(xù)上表DVD編號(hào)D51D52D53D54D55D56D57D58D59D60最少購(gòu)置量24171917191819172021DVD編號(hào)D61D62D63D64D65D66D67D68D69D70

7、最少購(gòu)置量16191920171917212019DVD編號(hào)D71D72D73D74D75D76D77D78D79D80最少購(gòu)置量21221520151412171917DVD編號(hào)D81D82D83D84D85D86D87D88D89D90最少購(gòu)置量18101412211322151317DVD編號(hào)D91D92D93D94D95D96D97D98D99D100最少購(gòu)置量24171514251522201122第40頁(yè) 我們利用規(guī)劃模型求得每種DVD購(gòu)置量后，需要對(duì)其進(jìn)行可行性校驗(yàn)，測(cè)試此結(jié)果是否能夠滿(mǎn)足一個(gè)月內(nèi)百分比為95%會(huì)員得到他想看DVD，且含有盡可能大總體滿(mǎn)意度.第41頁(yè)校驗(yàn)方法： （

8、一）依據(jù)訂單和求得DVD購(gòu)置數(shù)量，利用問(wèn)題二規(guī)劃模型進(jìn)行第一次分配，對(duì)分配情況：租賃會(huì)員，DVD分配情況，剩下各種DVD數(shù)量作統(tǒng)計(jì)；同時(shí)將已租賃會(huì)員在滿(mǎn)意指數(shù)矩陣指數(shù)全變?yōu)?，即不考慮對(duì)其進(jìn)行第二次分配. （二）隨機(jī)從第一次得到DVD會(huì)員中抽取60%，將這部分人所還回DVD與第一次分配余下DVD合在一起，作為第二次分配時(shí)各種DVD現(xiàn)有量.然后，利用問(wèn)題二0-1線(xiàn)性規(guī)劃模型對(duì)第一次未分配到DVD會(huì)員進(jìn)行第二次分配；第42頁(yè) （三）統(tǒng)計(jì)出經(jīng)過(guò)兩次分配后，得到DVD會(huì)員百分比，若大于95%，則此次分配成功.利用這種算法進(jìn)行屢次隨機(jī)模擬，若大多數(shù)情況下能夠使得到DVD會(huì)員大于95%，則認(rèn)為模型三是合理.第43頁(yè)校驗(yàn)結(jié)果： 因?yàn)槊看螜z驗(yàn)需時(shí)約1小時(shí)，我們只對(duì)問(wèn)題