數(shù)學建模課件規(guī)劃理論及模型

數(shù)學建模課件規(guī)劃理論及模型第1頁，共45頁，2023年，2月20日，星期五

事實上，客觀世界中的問題許多是非線性的，給予線性大多是近似的，是在作了科學的假設和簡化后得到的.為了利用線性的知識，許多非線性問題常進行線性化處理.但在實際問題中，有一些是不能進行線性化處理的，否則將嚴重影響模型對實際問題近似的可依賴型.第2頁，共45頁，2023年，2月20日，星期五

由于非線性規(guī)劃問題在計算上常是困難的，理論上的討論也不能像線性規(guī)劃那樣給出簡潔的結果形式和全面透徹的結論.這點又限制了非線性規(guī)劃的應用，所以，在數(shù)學建模時，要進行認真的分析，對實際問題進行合理的假設、簡化，首先考慮用線性規(guī)劃模型，若線性近似誤差較大時，則考慮用非線性規(guī)劃.第3頁，共45頁，2023年，2月20日，星期五非線性規(guī)劃問題的標準形式為：第4頁，共45頁，2023年，2月20日，星期五非線性規(guī)劃模型按約束條件可分為以下三類：⑴無約束非線性規(guī)劃模型：⑵等式約束非線性規(guī)劃模型：第5頁，共45頁，2023年，2月20日，星期五⑶不等式約束非線性規(guī)劃模型：1)

無約束的非線性規(guī)劃問題.針對上述三類非線性規(guī)劃模型，其常用求解的基本思路可歸納如下：第6頁，共45頁，2023年，2月20日，星期五第7頁，共45頁，2023年，2月20日，星期五第8頁，共45頁，2023年，2月20日，星期五

在下降迭代算法中，搜索方向起著關鍵的作用，而當搜索方向確定后，步長又是決定算法好壞的重要因素.非線性規(guī)劃只含一個變量，即一維非線性規(guī)劃可以用一維搜索方法求得最優(yōu)解，一維搜索方法主要有進退法和黃金分割法.二維的非線性規(guī)劃也可以像解線性規(guī)劃那樣用圖形求解.對于二維非線性規(guī)劃，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法.第9頁，共45頁，2023年，2月20日，星期五2)

只有等式約束的非線性規(guī)劃問題通常可用消元法、拉格朗日乘子法或反函數(shù)法，將其化為無約束問題求解.3)

具有不等式約束的非線性規(guī)劃問題解起來很復雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(guī)劃問題化為線性規(guī)劃問題.下面介紹一個簡單的非線性規(guī)劃問題的例子，其中的一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日方法求解.第10頁，共45頁，2023年，2月20日，星期五

例7．（石油最優(yōu)儲存方法）有一石油運輸公司，為了減少開支，希望作了節(jié)省石油的存儲空間.但要求存儲的石油能滿足客戶的要求.為簡化問題，假設只經營兩種油，各種符號表示的意義如表4所示.其中供給率指石油公司供給客戶的速度.第11頁，共45頁，2023年，2月20日，星期五表4各種符號表示意義表第i種油的存儲量第i種油的價格第i種油的供給率第i種油的每單位的存儲費用第i種油的每單位的存儲空間總存儲公式第12頁，共45頁，2023年，2月20日，星期五由歷史數(shù)據得到的經驗公式為:且提供數(shù)據如表5所示：第13頁，共45頁，2023年，2月20日，星期五表5數(shù)據表已知總存儲空間第14頁，共45頁，2023年，2月20日，星期五代入數(shù)據后得到的模型為：模型求解：拉格朗日函數(shù)的形式為：

第15頁，共45頁，2023年，2月20日，星期五即:對求各個變量的偏導數(shù)，并令它們等于零，得:第16頁，共45頁，2023年，2月20日，星期五解這個線性方程組得：從而可得最小值是

.第17頁，共45頁，2023年，2月20日，星期五6、多目標規(guī)劃模型

在許多實際問題中，衡量一個方案的好壞標準往往不止一個，例如設計一個導彈，既要射程最遠，又要燃料最省，還要精度最高.這一類問題統(tǒng)稱為多目標最優(yōu)化問題或多目標規(guī)劃問題.我們先來看一個生產計劃的例子.第18頁，共45頁，2023年，2月20日，星期五第19頁，共45頁，2023年，2月20日，星期五第20頁，共45頁，2023年，2月20日，星期五第21頁，共45頁，2023年，2月20日，星期五第22頁，共45頁，2023年，2月20日，星期五第23頁，共45頁，2023年，2月20日，星期五第24頁，共45頁，2023年，2月20日，星期五第25頁，共45頁，2023年，2月20日，星期五第26頁，共45頁，2023年，2月20日，星期五第27頁，共45頁，2023年，2月20日，星期五第28頁，共45頁，2023年，2月20日，星期五第29頁，共45頁，2023年，2月20日，星期五第30頁，共45頁，2023年，2月20日，星期五第31頁，共45頁，2023年，2月20日，星期五第32頁，共45頁，2023年，2月20日，星期五第33頁，共45頁，2023年，2月20日，星期五我們希望購買DVD的總數(shù)量最小，即

:由此，可以得到問題三的雙目標整數(shù)線性規(guī)劃模型如下：第34頁，共45頁，2023年，2月20日，星期五第35頁，共45頁，2023年，2月20日，星期五第36頁，共45頁，2023年，2月20日，星期五第37頁，共45頁，2023年，2月20日，星期五第38頁，共45頁，2023年，2月20日，星期五表6當時最小購買量的值DVD編號D01D02D03D04D05D06D07D08D09D10最少購買量14211724121719212214DVD編號D11D12D13D14D15D16D17D18D19D20最少購買量18181717172418161823DVD編號D21D22D23D24D25D26D27D28D29D30最少購買量20182214181715121624DVD編號D31D32D33D34D35D36D37D38D39D40最少購買量19222019222213171717DVD編號D41D42D43D44D45D46D47D48D49D50最少購買量32201621221620152020第39頁，共45頁，2023年，2月20日，星期五續(xù)上表DVD編號D51D52D53D54D55D56D57D58D59D60最少購買量24171917191819172021DVD編號D61D62D63D64D65D66D67D68D69D70最少購買量16191920171917212019DVD編號D71D72D73D74D75D76D77D78D79D80最少購買量21221520151412171917DVD編號D81D82D83D84D85D86D87D88D89D90最少購買量18101412211322151317DVD編號D91D92D93D94D95D96D97D98D99D100最少購買量24171514251522201122第40頁，共45頁，2023年，2月20日，星期五

我們利用規(guī)劃模型求得每種DVD的購買量后，需要對其進行可行性校驗，測試此結果是否可以滿足一個月內比例為95%的會員得到他想看的DVD，且具有盡可能大的總體滿意度.第41頁，共45頁，2023年，2月20日，星期五校驗方法：

（一）根據訂單和求得的DVD購買數(shù)量，利用問題二的規(guī)劃模型進行第一次分配，對分配情況：租賃的會員，DVD的分配情況，剩余的各種DVD數(shù)量作記錄；同時將已租賃的會員在滿意指數(shù)矩陣的指數(shù)全變?yōu)?，即不考慮對其進行第二次分配.

（二）隨機從第一次得到DVD的會員中抽取60%，將這部分人所還回的DVD與第一次分配余下的DVD合在一起，作為第二次分配時各種DVD的現(xiàn)有量.然后，利用問題二的0-1線性規(guī)劃模型對第一次未分配到DVD的會員進行第二次分配；第42頁，共45頁，2023年，2月20日，星期五

（三）統(tǒng)計出經過兩次分配后，得到DVD的會員的比例，若大于95%，則此次分配成功.利用這種算法進行多次隨機模擬，若大多數(shù)情況下可以使得到DVD的會員大于95%，則認為模型三是合理的.第43頁，共45頁，2023年，2月20日，星期五校驗結果：

因為每次檢驗需時約1小時，我們只對問題三求得的結果進行了7次