非線性規(guī)劃多目標(biāo)規(guī)劃課件

1、非線性規(guī)劃多目標(biāo)規(guī)劃非線性規(guī)劃多目標(biāo)規(guī)劃非線性規(guī)劃多目標(biāo)規(guī)劃 由于非線性規(guī)劃問題在計(jì)算上常是困難的，理論上的討論也不能像線性規(guī)劃那樣給出簡(jiǎn)潔的結(jié)果形式和全面透徹的結(jié)論. 這點(diǎn)又限制了非線性規(guī)劃的應(yīng)用，所以，在數(shù)學(xué)建模時(shí)，要進(jìn)行認(rèn)真的分析，對(duì)實(shí)際問題進(jìn)行合理的假設(shè)、簡(jiǎn)化，首先考慮用線性規(guī)劃模型，若線性近似誤差較大時(shí)，則考慮用非線性規(guī)劃.第1頁，共55頁。 由于非線性規(guī)劃問題在計(jì)算上常是困難的，理論上的討論也不能像線性規(guī)劃那樣給出簡(jiǎn)潔的結(jié)果形式和全面透徹的結(jié)論. 這點(diǎn)又限制了非線性規(guī)劃的應(yīng)用，所以，在數(shù)學(xué)建模時(shí)，要進(jìn)行認(rèn)真的分析，對(duì)實(shí)際問題進(jìn)行合理的假設(shè)、簡(jiǎn)化，首先考慮用線性規(guī)劃模型，若線性近似誤

2、差較大時(shí)，則考慮用非線性規(guī)劃.第2頁，共55頁。 問題1 抽水費(fèi)用最小問題 某地區(qū)有3個(gè)泵站: 第 個(gè)泵站的抽水費(fèi)用為 其中 為抽水流量. 泵站與各灌溉地塊用渠道連接. 在一個(gè)灌溉周期中, 地塊 需流量 立方米/小時(shí). 泵站 的最大抽水能力為 由于滲透和蒸發(fā),從 泵站到 地塊的水量要打一折扣, 即乘上系數(shù) 稱為水的實(shí)用系數(shù). 問應(yīng)如何確定每一泵站的輸水量, 才能使總的抽水費(fèi)用為最小? 試建立相應(yīng)的數(shù)學(xué)模型.第3頁，共55頁。 設(shè)從泵站 到地塊 的輸水量為 分析 問題的關(guān)鍵是確立決策變量和目標(biāo)函數(shù).第4頁，共55頁。注: 在上面的問題中, 輸水費(fèi)用函數(shù) 一般不是的線性函數(shù). 因而相應(yīng)的規(guī)劃不是線

3、性規(guī)劃.第5頁，共55頁。 問題2 砂石運(yùn)輸問題 設(shè)有 立方米的砂石,要由甲地運(yùn)到乙地, 運(yùn)輸前需先裝入一個(gè)有底無蓋并在底部裝有滑行器的木箱中. 砂石運(yùn)到乙地后, 從箱中倒出,在繼續(xù)用空箱裝運(yùn). 不論箱子大小, 每裝運(yùn)一箱, 需0.1元, 箱底和兩端的材料費(fèi)為20元/米2, 箱子兩側(cè)的材料費(fèi)為5元/米2, 箱底的兩個(gè)滑行器與箱子同長(zhǎng), 材料費(fèi)為2.5元/米. 問木箱的長(zhǎng)寬高各為多少米,才能使運(yùn)費(fèi)與箱子的成本費(fèi)的總和為最小.第6頁，共55頁。 建模 設(shè)木箱的長(zhǎng)寬高分別為 運(yùn)費(fèi)與成本費(fèi)的總和為 則目標(biāo)函數(shù)為第7頁，共55頁。 若在上述問題中, 箱子的底與兩側(cè)使用廢料來做, 而廢料只有4平方米, 則

4、問題為:第8頁，共55頁。在上面問題中, 目標(biāo)函數(shù)與約束條件中的每一項(xiàng)可表達(dá)成 的形式（其中的 為整數(shù)） , 數(shù)學(xué)上將其成為廣義多項(xiàng)式, 相應(yīng)的規(guī)劃稱為幾何規(guī)劃.當(dāng)系數(shù)為正數(shù)時(shí), 規(guī)劃稱為正項(xiàng)幾何規(guī)劃.第9頁，共55頁。非線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：第10頁，共55頁。非線性規(guī)劃模型按約束條件可分為以下三類： 無約束非線性規(guī)劃模型： 等式約束非線性規(guī)劃模型：第11頁，共55頁。 不等式約束非線性規(guī)劃模型：針對(duì)上述三類非線性規(guī)劃模型，其常用求解的基本思路可歸納如下： 第12頁，共55頁。 1) 無約束的非線性規(guī)劃問題 無約束非線性規(guī)劃一般可寫成其中 解法 1.求 的梯度 2.令梯度 解出 的駐點(diǎn)3

5、.驗(yàn)證 在該點(diǎn)的Hessian矩陣是否為正（負(fù)）定的, 若成立, 則該點(diǎn)為函數(shù)的極?。ù螅┲迭c(diǎn).第13頁，共55頁。例7 求函數(shù) 的極小點(diǎn).解 的梯度為令 則駐點(diǎn)為 函數(shù)的Hessian陣為注意到該矩陣為正定陣, 因而該點(diǎn)為極小值點(diǎn).第14頁，共55頁。 注意到此方法只有對(duì)一些特殊的函數(shù)才有效. 一般情況下, 要求出函數(shù)的駐點(diǎn)是比較困難的. 下面我們簡(jiǎn)單介紹求解該類問題的數(shù)值解法.1.給出 的極小點(diǎn) 的一個(gè)初始估計(jì)值 稱為初始點(diǎn);2.如果 已求得, 并且不是極小點(diǎn), 設(shè)法選取一個(gè)方向 （該方向稱為搜索方向）, 使目標(biāo)函數(shù) 沿該方向是下降的（一般取梯度方向）;第15頁，共55頁。3.在射線 取適

6、當(dāng)?shù)牟介L(zhǎng), 記 由此確定點(diǎn) 其中的 一般取使得上式取到極小值的值.4.檢驗(yàn) 是否為函數(shù) 的極小值, 或者滿足精度的要求, 若不是, 再回到第二步.第16頁，共55頁。2) 只有等式約束的非線性規(guī)劃問題通?？捎孟?、拉格朗日乘子法或反函數(shù)法，將其化為無約束問題求解.3) 具有不等式約束的非線性規(guī)劃問題解起來很復(fù)雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(guī)劃問題化為線性規(guī)劃問題. 下面介紹一個(gè)簡(jiǎn)單的非線性規(guī)劃問題的例子，其中的一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日方法求解.第17頁，共55頁。 例8（石油最優(yōu)儲(chǔ)存方法）有一石油運(yùn)

7、輸公司，為了減少開支，希望作了節(jié)省石油的存儲(chǔ)空間.但要求存儲(chǔ)的石油能滿足客戶的要求.為簡(jiǎn)化問題，假設(shè)只經(jīng)營(yíng)兩種油，各種符號(hào)表示的意義如表4所示.其中供給率指石油公司供給客戶的速度.第18頁，共55頁。表4 各種符號(hào)表示意義表第i種油的存儲(chǔ)量第i種油的價(jià)格第i種油的供給率第i種油的每單位的存儲(chǔ)費(fèi)用第i種油的每單位的存儲(chǔ)空間總存儲(chǔ)公式第19頁，共55頁。由歷史數(shù)據(jù)得到的經(jīng)驗(yàn)公式為 :且提供數(shù)據(jù)如表5所示：第20頁，共55頁。表5 數(shù)據(jù)表已知總存儲(chǔ)空間第21頁，共55頁。代入數(shù)據(jù)后得到的模型為：模型求解：拉格朗日函數(shù)的形式為： 第22頁，共55頁。即:對(duì) 求各個(gè)變量的偏導(dǎo)數(shù)，并令它們等于零，得: 第

8、23頁，共55頁。解這個(gè)線性方程組得：從而可得最小值是 . 第24頁，共55頁。 非線性規(guī)劃解法例9 求解非線性規(guī)劃第25頁，共55頁。解1 圖解法第26頁，共55頁。解2 用Lingo軟件求解min=(x1-1.5)2+x22;x12+x22=1; Local optimal solution found. Objective value: 0.2500004 Extended solver steps: 5 Total solver iterations: 25 Variable Value Reduced Cost X1 0.9999996 0.000000 X2 0.000000 0.

9、000000 Row Slack or Surplus Dual Price 1 0.2500004 -1.000000 2 0.8162711E-06 0.5000006 3 0.9999992 0.000000第27頁，共55頁。6、多目標(biāo)規(guī)劃模型 在許多實(shí)際問題中，衡量一個(gè)方案的好壞標(biāo)準(zhǔn)往往不止一個(gè)，例如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高. 這一類問題統(tǒng)稱為多目標(biāo)最優(yōu)化問題或多目標(biāo)規(guī)劃問題. 我們先來看一個(gè)生產(chǎn)計(jì)劃的例子.第28頁，共55頁。第29頁，共55頁。第30頁，共55頁。第31頁，共55頁。第32頁，共55頁。第33頁，共55頁。第34頁，共55頁。第35頁

10、，共55頁。第36頁，共55頁。第37頁，共55頁。第38頁，共55頁。第39頁，共55頁。第40頁，共55頁。第41頁，共55頁。第42頁，共55頁。第43頁，共55頁。我們希望購買DVD的總數(shù)量最小，即 :由此，可以得到問題三的雙目標(biāo)整數(shù)線性規(guī)劃模型如下： 第44頁，共55頁。第45頁，共55頁。第46頁，共55頁。第47頁，共55頁。第48頁，共55頁。表6 當(dāng) 時(shí)最小購買量的 值DVD編號(hào)D01D02D03D04D05D06D07D08D09D10最少購買量14211724121719212214DVD編號(hào)D11D12D13D14D15D16D17D18D19D20最少購買量18181

11、717172418161823DVD編號(hào)D21D22D23D24D25D26D27D28D29D30最少購買量20182214181715121624DVD編號(hào)D31D32D33D34D35D36D37D38D39D40最少購買量19222019222213171717DVD編號(hào)D41D42D43D44D45D46D47D48D49D50最少購買量32201621221620152020第49頁，共55頁。續(xù)上表DVD編號(hào)D51D52D53D54D55D56D57D58D59D60最少購買量24171917191819172021DVD編號(hào)D61D62D63D64D65D66D67D68D69

12、D70最少購買量16191920171917212019DVD編號(hào)D71D72D73D74D75D76D77D78D79D80最少購買量21221520151412171917DVD編號(hào)D81D82D83D84D85D86D87D88D89D90最少購買量18101412211322151317DVD編號(hào)D91D92D93D94D95D96D97D98D99D100最少購買量24171514251522201122第50頁，共55頁。 我們利用規(guī)劃模型求得每種DVD的購買量后，需要對(duì)其進(jìn)行可行性校驗(yàn)，測(cè)試此結(jié)果是否可以滿足一個(gè)月內(nèi)比例為95%的會(huì)員得到他想看的DVD，且具有盡可能大的總體滿意度

13、.第51頁，共55頁。校驗(yàn)方法： （一）根據(jù)訂單和求得的DVD購買數(shù)量，利用問題二的規(guī)劃模型進(jìn)行第一次分配，對(duì)分配情況：租賃的會(huì)員，DVD的分配情況，剩余的各種DVD數(shù)量作記錄；同時(shí)將已租賃的會(huì)員在滿意指數(shù)矩陣的指數(shù)全變?yōu)?，即不考慮對(duì)其進(jìn)行第二次分配. （二）隨機(jī)從第一次得到DVD的會(huì)員中抽取60%，將這部分人所還回的DVD與第一次分配余下的DVD合在一起，作為第二次分配時(shí)各種DVD的現(xiàn)有量.然后，利用問題二的0-1線性規(guī)劃模型對(duì)第一次未分配到DVD的會(huì)員進(jìn)行第二次分配；第52頁，共55頁。 （三）統(tǒng)計(jì)出經(jīng)過兩次分配后，得到DVD的會(huì)員的比例，若大于95%，則此次分配成功.利用這種算法進(jìn)行多次隨機(jī)模擬，若大多