MBA數(shù)據(jù)模型與決策：非線性規(guī)劃

非線性規(guī)劃

§10.1非線性規(guī)劃的數(shù)學(xué)模型

在線性規(guī)劃模型中,活動(dòng)對(duì)目標(biāo)函數(shù)的貢獻(xiàn)(或?qū)Y源的消耗)與活動(dòng)水平成比例關(guān)系,因而目標(biāo)函數(shù)(或約束函數(shù))是決策變量的線性函數(shù)。而在實(shí)際問題中,往往遇到活動(dòng)對(duì)目標(biāo)函數(shù)的貢獻(xiàn)(或?qū)Y源的消耗)與活動(dòng)水平不成比例關(guān)系的情形,即目標(biāo)函數(shù)(或約束函數(shù))不是決策變量的線性函數(shù),而是非線性函數(shù),我們稱此類問題為非線性規(guī)劃問題。

例1.

在第二章資源分配問題例1中,若甲乙兩產(chǎn)品的單位純利潤(rùn)和與該產(chǎn)品產(chǎn)量與有關(guān),=4-=3-,其中4和3為產(chǎn)品的毛利潤(rùn)，而0.2和0.1分別代表每銷售單位甲、乙產(chǎn)品所需要的營(yíng)銷成本。

數(shù)學(xué)模型為:Max由于目標(biāo)函數(shù)是非線性函數(shù),此問題是一個(gè)非線性規(guī)劃問題,非線性規(guī)劃的建模過程與線性規(guī)劃是完全一樣的,一般模型為:1利用Lingo求解非線性規(guī)劃問題

同線性規(guī)劃一樣，我們可以使用Lingo在計(jì)算機(jī)上求解非線性規(guī)劃問題。圖1中（文件NLP1.lng）包含了例1的表述和輸出。由Value列中可以看出，Lingo已經(jīng)求出了，這個(gè)解的目標(biāo)函數(shù)值是22.418。不能保證Lingo求出的解就是最優(yōu)解。有可能是全局最優(yōu)解，也可能是局部最優(yōu)解。2利用Excel求解非線性規(guī)劃問題在運(yùn)用Excel求解任何非線性規(guī)劃問題時(shí)，千萬要確保沒有選擇假設(shè)線性的選項(xiàng)。3非線性規(guī)劃與線性規(guī)劃的區(qū)別如果線性規(guī)劃問題有一個(gè)最優(yōu)解，那么一定是可行域中的一個(gè)極點(diǎn)。非線性規(guī)劃的可行域就不一定是凸集了，即使可行域是凸集，最優(yōu)解也未必是可行域中的極點(diǎn)了。實(shí)際上，非線性規(guī)劃問題的最優(yōu)解也許不在可行域的邊界上。圖10-3作圖法求解例1的非線性規(guī)劃模型l3:2x1+3x2=18l2:x2=4l1:x1=67465321100654321879x2x1可行域3非線性規(guī)劃與線性規(guī)劃的區(qū)別例2：

這個(gè)非線性規(guī)劃模型的最優(yōu)解是。顯然當(dāng)然不在可行域的邊界上。。

x2x1§10.2一維最優(yōu)化

與例2只有一個(gè)變量的f(x)的最優(yōu)化問題maxf(x)。當(dāng)用迭代法求函數(shù)的極大點(diǎn)時(shí)，常常用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極大點(diǎn)。

考慮一維極小化問題

若是區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短的長(zhǎng)度，來搜索得近似最優(yōu)解

最常用的一維搜索試探法是黃金分割法，又稱0.618法。要求插入點(diǎn)a1、a2的位置相對(duì)于區(qū)間[a,b]兩端點(diǎn)具有對(duì)稱性。除對(duì)稱要求外，黃金分割法還要求在保留下來的區(qū)間再插入一點(diǎn)所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。1黃金分割搜索法（又稱0.618法）2所謂的“黃金分割”是指將一線段分成兩段的方法，使整段長(zhǎng)與較長(zhǎng)段的長(zhǎng)度比值等于較長(zhǎng)段與較短段的比值，即2使用Excel執(zhí)行黃金分割搜索

例3：使用黃金分割搜索法求§10.3計(jì)算機(jī)求解非線性規(guī)劃問題的應(yīng)用舉例

例4：設(shè)施選址問題：

圖10-9設(shè)施選址問題的規(guī)劃求解1圖10-11設(shè)施選址問題的規(guī)劃求解2例５：輪胎的生產(chǎn)：Rubber公司通過混合３種材料生產(chǎn)輪胎用的橡膠，這3種材料是橡膠、石油和炭黑。這三種材料每千克的成本分別為4，1，7（單位為元）。汽車輪胎所用橡膠的硬度必須在25-35之間，彈性至少要達(dá)到16，抗拉強(qiáng)度至少要達(dá)到12。要生產(chǎn)一組汽車輪胎（4個(gè)），需要100千克輪胎用橡膠。用于生產(chǎn)一組輪胎的汽車用橡膠必須含有25-60千克的橡膠和至少50千克炭黑。如果R代表用于生產(chǎn)一組輪胎的混合物中的橡膠量，O代表用于生產(chǎn)一組輪胎的混合物中的石油量，C表示生產(chǎn)一組輪胎的混合物中的炭黑量。由統(tǒng)計(jì)分析可知，100千克橡膠、石油和炭黑的混合物的硬度、彈性和抗拉強(qiáng)度公式如下：抗拉強(qiáng)度彈性硬度如何安排3種材料的生產(chǎn)使得用于生產(chǎn)一組汽車輪胎的橡膠產(chǎn)品費(fèi)用最少。例6：投資組合問題

§10.4可分離規(guī)劃

例7：某公司生產(chǎn)產(chǎn)品A和B，由于接到了特別訂單，需要調(diào)出一部分工人，這樣剩余工人為了最大限度的利用生產(chǎn)能力就必須加班工作。管理層曾考慮過使用臨時(shí)工來避免加班造成額外的費(fèi)用，但是如果工人缺乏經(jīng)驗(yàn)，會(huì)降低工作效率，就必須對(duì)臨時(shí)工培訓(xùn)，從而增加培訓(xùn)費(fèi)用。同時(shí)在完成額外訂單后，工廠就恢復(fù)正常生產(chǎn)，不需要臨時(shí)工。所以管理層最后還是決定采取加班的措施。有關(guān)數(shù)據(jù)如下表：供電部門最多只能提供1200單位的電力,加工每單位產(chǎn)品A消耗一個(gè)單位的電力，加工每單位產(chǎn)品