數學建模規(guī)劃理論及模型市公開課獲獎課件

1、 5.非線性規(guī)劃模型 前面簡介了線性規(guī)劃問題，即目的函數和約束條件都是線性函數規(guī)劃問題，但在實際工作中，還經常會碰到另一類更普通規(guī)劃問題，即目的函數和約束條件中至少有一個是非線性函數規(guī)劃問題，即非線性規(guī)劃問題. 第1頁第1頁 事實上，客觀世界中問題許多是非線性，予以線性大多是近似，是在作了科學假設和簡化后得到. 為了利用線性知識，許多非線性問題常進行線性化處理. 但在實際問題中，有一些是不能進行線性化處理，不然將嚴重影響模型對實際問題近似可依賴型.第2頁第2頁 由于非線性規(guī)劃問題在計算上常是困難，理論上討論也不能像線性規(guī)劃那樣給出簡練結果形式和全面透徹結論. 這點又限制了非線性規(guī)劃應用，因此，

2、在數學建模時，要進行認真分析，對實際問題進行合理假設、簡化，首先考慮用線性規(guī)劃模型，若線性近似誤差較大時，則考慮用非線性規(guī)劃.第3頁第3頁非線性規(guī)劃問題原則形式為：第4頁第4頁非線性規(guī)劃模型按約束條件可分為下列三類： 無約束非線性規(guī)劃模型： 等式約束非線性規(guī)劃模型：第5頁第5頁 不等式約束非線性規(guī)劃模型：1) 無約束非線性規(guī)劃問題.針對上述三類非線性規(guī)劃模型，其慣用求解基本思緒可歸納下列： 第6頁第6頁第7頁第7頁第8頁第8頁 在下降迭代算法中，搜索方向起著關鍵作用，而當搜索方向擬定后，步長又是決定算法好壞主要原因. 非線性規(guī)劃只含一個變量，即一維非線性規(guī)劃能夠用一維搜索辦法求得最優(yōu)解，一維搜

3、索辦法主要有進退法和黃金分割法. 二維非線性規(guī)劃也能夠像解線性規(guī)劃那樣用圖形求解. 對于二維非線性規(guī)劃，使用搜索辦法是要用到梯度概念，最慣用搜索辦法就是最速下降法.第9頁第9頁2) 只有等式約束非線性規(guī)劃問題通?？捎孟?、拉格朗日乘子法或反函數法，將其化為無約束問題求解.3) 含有不等式約束非線性規(guī)劃問題解起來很復雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，用線性迫近辦法將非線性規(guī)劃問題化為線性規(guī)劃問題. 下面簡介一個簡樸非線性規(guī)劃問題例子，其中一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日辦法求解.第10頁第10頁 例7（石油最優(yōu)儲存辦法）有一石油運送公司

4、，為了減少開支，希望作了節(jié)約石油存儲空間.但要求存儲石油能滿足客戶要求.為簡化問題，假設只經營兩種油，各種符號表示意義如表4所表示.其中供應率指石油公司供應客戶速度.第11頁第11頁表4 各種符號表示意義表第i種油存儲量第i種油價格第i種油供應率第i種油每單位存儲費用第i種油每單位存儲空間總存儲公式第12頁第12頁由歷史數據得到經驗公式為 :且提供數據如表5所表示：第13頁第13頁表5 數據表已知總存儲空間第14頁第14頁代入數據后得到模型為：模型求解：拉格朗日函數形式為： 第15頁第15頁即:對 求各個變量偏導數，并令它們等于零，得: 第16頁第16頁解這個線性方程組得：從而可得最小值是 .

5、 第17頁第17頁6、多目的規(guī)劃模型 在許多實際問題中，衡量一個方案好壞原則往往不止一個，比如設計一個導彈，既要射程最遠，又要燃料最省，還要精度最高. 這一類問題統(tǒng)稱為多目的最優(yōu)化問題或多目的規(guī)劃問題. 我們先來看一個生產計劃例子.第18頁第18頁第19頁第19頁第20頁第20頁第21頁第21頁第22頁第22頁第23頁第23頁第24頁第24頁第25頁第25頁第26頁第26頁第27頁第27頁第28頁第28頁第29頁第29頁第30頁第30頁第31頁第31頁第32頁第32頁第33頁第33頁我們希望購買DVD總數量最小，即 :由此，能夠得到問題三雙目的整數線性規(guī)劃模型下列： 第34頁第34頁第35頁第

6、35頁第36頁第36頁第37頁第37頁第38頁第38頁表6 當 時最小購買量 值DVD編號D01D02D03D04D05D06D07D08D09D10至少購買量14211724121719212214DVD編號D11D12D13D14D15D16D17D18D19D20至少購買量18181717172418161823DVD編號D21D22D23D24D25D26D27D28D29D30至少購買量20182214181715121624DVD編號D31D32D33D34D35D36D37D38D39D40至少購買量19222019222213171717DVD編號D41D42D43D44D45

7、D46D47D48D49D50至少購買量32201621221620152020第39頁第39頁續(xù)上表DVD編號D51D52D53D54D55D56D57D58D59D60至少購買量24171917191819172021DVD編號D61D62D63D64D65D66D67D68D69D70至少購買量16191920171917212019DVD編號D71D72D73D74D75D76D77D78D79D80至少購買量21221520151412171917DVD編號D81D82D83D84D85D86D87D88D89D90至少購買量18101412211322151317DVD編號D91D

8、92D93D94D95D96D97D98D99D100至少購買量24171514251522201122第40頁第40頁 我們利用規(guī)劃模型求得每種DVD購置量后，需要對其進行可行性校驗，測試此結果是否能夠滿足一個月內百分比為95%會員得到他想看DVD，且含有盡也許大總體滿意度.第41頁第41頁校驗辦法： （一）依據訂單和求得DVD購買數量，利用問題二規(guī)劃模型進行第一次分派，對分派情況：租賃會員，DVD分派情況，剩余各種DVD數量作統(tǒng)計；同時將已租賃會員在滿意指數矩陣指數全變?yōu)?，即不考慮對其進行第二次分派. （二）隨機從第一次得到DVD會員中抽取60%，將這部分人所還回DVD與第一次分派余下DVD合在一起，作為第二次分派時各種DVD既有量.然后，利用問題二0-1線性規(guī)劃模型對第一次未分派到DVD會員進行第二次分派；第42頁第42頁 （三）統(tǒng)計出通過兩次分派后，得到DVD會員百分比，若不小于95%，則本次分派成功.利用這種算法進行多次隨機模擬，若大多數情況下能夠使得到DVD會員不小于95%，則認為模型三是合理.第43頁第43頁校驗結果： 由于每次檢查需時約1小時，我們只對問題