Exp08姜啟源數(shù)學(xué)建模課件第八章約束優(yōu)化高等教學(xué)

1、大學(xué)數(shù)學(xué)實(shí)驗(yàn)大學(xué)數(shù)學(xué)實(shí)驗(yàn)mathematical experiments 實(shí)驗(yàn)實(shí)驗(yàn)8 8 約束優(yōu)化約束優(yōu)化1優(yōu)化問(wèn)題三要素：優(yōu)化問(wèn)題三要素：決策變量決策變量；目標(biāo)函數(shù)目標(biāo)函數(shù)；約束條件約束條件約約束束條條件件決策變量決策變量?jī)?yōu)化問(wèn)題的一般形式優(yōu)化問(wèn)題的一般形式njidxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min當(dāng)最優(yōu)解在可行域邊界上取得時(shí)當(dāng)最優(yōu)解在可行域邊界上取得時(shí)不能用無(wú)約束優(yōu)化方法求解不能用無(wú)約束優(yōu)化方法求解目標(biāo)函數(shù)目標(biāo)函數(shù)2約束優(yōu)化的分類約束優(yōu)化的分類 線性規(guī)劃線性規(guī)劃(lp) 目標(biāo)和約束均為線性函數(shù)目標(biāo)和約束均為線性函數(shù) 非線性規(guī)劃非線性規(guī)劃(nlp)

2、 目標(biāo)或約束中存在非線性函數(shù)目標(biāo)或約束中存在非線性函數(shù) 二次規(guī)劃二次規(guī)劃(qp) 目標(biāo)為二次函數(shù)、約束為線性目標(biāo)為二次函數(shù)、約束為線性 整數(shù)規(guī)劃整數(shù)規(guī)劃(ip) 決策變量決策變量(部分部分)為整數(shù)為整數(shù) 整數(shù)整數(shù)線性線性規(guī)劃規(guī)劃(ilp) 整數(shù)整數(shù)非線性非線性規(guī)劃規(guī)劃(inlp) 0-1規(guī)劃規(guī)劃整數(shù)決策變量只取或整數(shù)決策變量只取或njidxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min連連續(xù)續(xù)優(yōu)優(yōu)化化離離散散優(yōu)優(yōu)化化數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃(math. prog.)3本實(shí)驗(yàn)基本內(nèi)容本實(shí)驗(yàn)基本內(nèi)容2. 基本原理和算法基本原理和算法3. matlab實(shí)現(xiàn)實(shí)現(xiàn)1. 問(wèn)題與模型問(wèn)

3、題與模型nlpnlplplpqpqp連續(xù)優(yōu)化連續(xù)優(yōu)化41桶桶牛奶牛奶 3千克千克a1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4千克千克a2或或獲利獲利12元元/千克千克獲利獲利8元元/千克千克 0.8千克千克b12小時(shí)小時(shí),1.5元元1千克千克獲利獲利22元元/千克千克 0.75千克千克b22小時(shí)小時(shí),1.5元元1千克千克獲利獲利16元元/千克千克 制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大 15元可增加元可增加1桶牛奶，應(yīng)否投資？桶牛奶，應(yīng)否投資？50桶牛奶桶牛奶, 480小時(shí)小時(shí) 至多至多100公斤公斤a1 b1，b2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？的波動(dòng)，對(duì)計(jì)

4、劃有無(wú)影響？實(shí)例實(shí)例1: 奶制品生產(chǎn)銷售計(jì)劃奶制品生產(chǎn)銷售計(jì)劃 聘用臨時(shí)工人增加勞動(dòng)時(shí)間，工資最多每小時(shí)幾元？聘用臨時(shí)工人增加勞動(dòng)時(shí)間，工資最多每小時(shí)幾元？51桶桶牛奶牛奶 3千克千克 a1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4千克千克 a2 或或獲利獲利12元元/千克千克 獲利獲利8元元/千克千克 0.8千克千克 b12小時(shí)小時(shí),1.5元元1千克千克獲利獲利22元元/千克千克 0.75千克千克 b22小時(shí)小時(shí),1.5元元1千克千克獲利獲利16元元/千克千克 出售出售x1 千克千克 a1, x2 千克千克 a2， x3千克千克 b1, x4千克千克 b2原料原料供應(yīng)供應(yīng) 勞動(dòng)勞動(dòng)時(shí)間時(shí)間 加工能力加工

5、能力 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù) 利潤(rùn)利潤(rùn)約束約束條件條件非負(fù)約束非負(fù)約束 0,61xx x5千克千克 a1加工加工b1， x6千克千克 a2加工加工b26543215 . 15 . 11622812xxxxxxzmax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x lp650萬(wàn)元基金用于投資三種股票萬(wàn)元基金用于投資三種股票a、b、c：a每股年期望收益每股年期望收益5元元(標(biāo)準(zhǔn)差標(biāo)準(zhǔn)差2元元)，目前市價(jià)，目前市價(jià)20元；元；b每股年期望收益每股年期望收益8元元(標(biāo)準(zhǔn)差標(biāo)準(zhǔn)差6元元)，目前市價(jià)，目

6、前市價(jià)25元；元；c每股年期望收益每股年期望收益10元元(標(biāo)準(zhǔn)差標(biāo)準(zhǔn)差10元元)，目前市價(jià)，目前市價(jià)30元；元；股票股票a、b收益的相關(guān)系數(shù)為收益的相關(guān)系數(shù)為5/24;股票股票a、c收益的相關(guān)系數(shù)為收益的相關(guān)系數(shù)為0.5;股票股票b、c收益的相關(guān)系數(shù)為收益的相關(guān)系數(shù)為0.25。實(shí)例實(shí)例2：投資組合問(wèn)題：投資組合問(wèn)題如期望今年得到至少如期望今年得到至少20%20%的投資回報(bào)，應(yīng)如何投資？的投資回報(bào)，應(yīng)如何投資？投資回報(bào)率與風(fēng)險(xiǎn)的關(guān)系如何？投資回報(bào)率與風(fēng)險(xiǎn)的關(guān)系如何？假設(shè)：假設(shè)：1、基金不一定要用完（不用不計(jì)利息或貶值）、基金不一定要用完（不用不計(jì)利息或貶值） 2、風(fēng)險(xiǎn)通常用收益的方差或標(biāo)準(zhǔn)差衡量

7、、風(fēng)險(xiǎn)通常用收益的方差或標(biāo)準(zhǔn)差衡量7決策變量決策變量 x1 、x2和和 x3 分別表示投資分別表示投資a、b、c的數(shù)量的數(shù)量（國(guó)內(nèi)股票通常以（國(guó)內(nèi)股票通常以“一手一手”（100股）為最小單位出售，股）為最小單位出售，這里以這里以100股為單位，期望收益以百元為單位）股為單位，期望收益以百元為單位） 實(shí)例實(shí)例2：投資組合問(wèn)題：投資組合問(wèn)題a、b、c每手每手(百股百股)的收益分別記為的收益分別記為s1,s2和和s3(百元百元)：es1=5, es2=8, es3=10，ds1=4, ds2=36, ds3=100，r12=5/24, r13=-0.5，r23=-0.25 總收益總收益 s=x1s1

8、+x2s2+x3s3 ：是一個(gè)隨機(jī)變量：是一個(gè)隨機(jī)變量15),cov(10),cov(25),cov(322332311331211221dsdsrssdsdsrssdsdsrss8投資風(fēng)險(xiǎn)（總收益的方差）為投資風(fēng)險(xiǎn)（總收益的方差）為 實(shí)例實(shí)例2：投資組合問(wèn)題：投資組合問(wèn)題總期望收益為總期望收益為 z1=es= x1es1+x2es2+x3es3=5x1+8x2+10 x3 總收益總收益 s=x1s1+x2s2+x3s3 ：是一個(gè)隨機(jī)變量：是一個(gè)隨機(jī)變量323121232221323231312121323222121332233112211332211332211230205100364),

9、cov(2),cov(2),cov(2),cov(2),cov(2),cov(2)()()()(xxxxxxxxxssxxssxxssxxdsxdsxdsxsxsxsxsxsxsxsxdsxdsxdsxsxsxdz9二次規(guī)劃（二次規(guī)劃（qp）模型）模型實(shí)例實(shí)例2：投資組合問(wèn)題：投資組合問(wèn)題s.t. 5x1 +8x2+10 x3 1000 20 x1+25x2+30 x3 5000 x1，x2，x3 0 323121232221230205100364minxxxxxxxxxz通過(guò)試探發(fā)現(xiàn)通過(guò)試探發(fā)現(xiàn) 從從0.00010.1以以0.0001的步長(zhǎng)變化的步長(zhǎng)變化就可以得到很好的近似結(jié)果就可以得到很

10、好的近似結(jié)果 min z =z2 - z1 s.t. 20 x1+25x2+30 x3 5000 x1，x2，x3 0 加權(quán)加權(quán)模型模型10 實(shí)例實(shí)例3 3：供應(yīng)與選址：供應(yīng)與選址某公司有6個(gè)建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里),水泥日用量di (單位：噸）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)現(xiàn)有 2 料場(chǎng)，位于 a (5, 1), b (2, 7),記(xj,yj),j=1,2, 日儲(chǔ)量 ej各有 20 噸。假設(shè)：假設(shè)：料場(chǎng)和工地之間有直線道路料場(chǎng)和工地之間有直線道路目標(biāo)：制定每天的供應(yīng)計(jì)劃，即從 a, b

11、 兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。112 , 1, 6,.,1, 02 , 1,6,.,1,. .)()(min612121612/122jicjecidctsbyaxcijjijiiijjjiijijij線性規(guī)劃模型線性規(guī)劃模型決策變量：決策變量：ci j 12維維(料場(chǎng)料場(chǎng)j到到工地工地i運(yùn)量）運(yùn)量）122）改建兩個(gè)新料場(chǎng)，需要確定新料場(chǎng)位置(xj,yj)和運(yùn)量cij ，在其它條件不變下使總噸公里數(shù)最小。. 2 , 1, 6,.,1, 0, 2 , 1, 6,.,1,. .)()(min612121612/122jicjecidctsbyaxcijjijiiijjji

12、ijijij決策變量：決策變量：ci j，(xj,yj)16維維非線性規(guī)劃模型非線性規(guī)劃模型13求解線性規(guī)劃求解線性規(guī)劃(lp)的基本原理的基本原理基本模型基本模型0,. .,min)max(xbaxtsrxxczorntmnmnrbrarc,二維線性規(guī)劃的圖解法二維線性規(guī)劃的圖解法一般線性規(guī)劃的單純形算法一般線性規(guī)劃的單純形算法一般線性規(guī)劃的內(nèi)點(diǎn)算法一般線性規(guī)劃的內(nèi)點(diǎn)算法14二維線性規(guī)劃的圖解法二維線性規(guī)劃的圖解法x2x10l1l2l3z1=0z2=2z3=6z4=10z5=13grad zx*起作用約束：起作用約束：l2;l3最優(yōu)解（最優(yōu)解（4，1），最優(yōu)值），最優(yōu)值z(mì)max=13l1l2

13、l3221 xx15求解求解lp的基本思想的基本思想從可行域的某一頂點(diǎn)開(kāi)始，只需在有限多個(gè)頂點(diǎn)中從可行域的某一頂點(diǎn)開(kāi)始，只需在有限多個(gè)頂點(diǎn)中一個(gè)一個(gè)找下去，一定能得到一個(gè)一個(gè)找下去，一定能得到最優(yōu)解最優(yōu)解。lp的約束和目標(biāo)函數(shù)均為線性函數(shù)的約束和目標(biāo)函數(shù)均為線性函數(shù)2維維可行域可行域 線段組成的凸多邊形線段組成的凸多邊形目標(biāo)函數(shù)目標(biāo)函數(shù) 等值線為直線等值線為直線最優(yōu)解最優(yōu)解 凸多邊形的某個(gè)頂點(diǎn)凸多邊形的某個(gè)頂點(diǎn)n維維超平面組成的凸多面體超平面組成的凸多面體等值線是超平面等值線是超平面凸多面體的某個(gè)頂點(diǎn)凸多面體的某個(gè)頂點(diǎn)算法：怎樣從一點(diǎn)轉(zhuǎn)到下一點(diǎn)，盡快找到最優(yōu)解。算法：怎樣從一點(diǎn)轉(zhuǎn)到下一點(diǎn)，盡快

14、找到最優(yōu)解。16x2x10l1l2l3x2x10l1l2l3x2x10l1l2求解求解lplp的特殊情形的特殊情形l1l2l3無(wú)可行解無(wú)可行解無(wú)最優(yōu)解無(wú)最優(yōu)解(無(wú)界無(wú)界)最優(yōu)解不唯一最優(yōu)解不唯一3214123lxx3l無(wú)x2x10l1l2l3z=c221 xx321413lxx17線性規(guī)劃的標(biāo)準(zhǔn)形和基本性質(zhì)線性規(guī)劃的標(biāo)準(zhǔn)形和基本性質(zhì)nmraxbaxtsxcznmt,0,.min標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形加入松弛變量加入松弛變量/剩余變量將不等式變?yōu)榈仁绞Ｓ嘧兞繉⒉坏仁阶優(yōu)榈仁?,0,14230, 220003min215521442154321xxxxxxxxxxxxxxxz0, 2.3321xxxxts2

15、21 xx一般還假定一般還假定b0rank(a)=m180,1423, 222. .0003min5432152142132154321xxxxxxxxxxxxxxtsxxxxxz0,1423, 22254321521421321xxxxxxxxxxxxxx對(duì)標(biāo)準(zhǔn)形求解對(duì)標(biāo)準(zhǔn)形求解先求可行解先求可行解nmraxbaxtsxcznmt,0,.min0,xbax滿足再在有限個(gè)可行解中尋找最優(yōu)解再在有限個(gè)可行解中尋找最優(yōu)解191423222521421321xxxxxxxxx100230102100111a可逆， bnba,tnbtxxx,bnxbxaxnb54321pppppbbxxbn10 x2

16、x1otxpppb)14, 2 , 2 , 0 , 0(543txpppb) 8 , 0 , 4 , 0 , 2(531txpppb)16, 0 , 3 , 1, 0(532o點(diǎn)點(diǎn)q點(diǎn)點(diǎn)r點(diǎn)點(diǎn)qr基本可行解基本可行解x ：ax=b, x 0 (xb 0，xn=0)txpppb)0 , 0 , 5 , 1 , 4(321p點(diǎn)點(diǎn)pb: 基基(矩陣矩陣) x: 基基(本本)解解20可行域存在時(shí)，必是凸多面體可行域存在時(shí)，必是凸多面體(可能無(wú)界可能無(wú)界)；最優(yōu)解存在時(shí)，必在可行域的頂點(diǎn)取得最優(yōu)解存在時(shí)，必在可行域的頂點(diǎn)取得(可能無(wú)界可能無(wú)界)；基本可行解對(duì)應(yīng)于可行域的頂點(diǎn)基本可行解對(duì)應(yīng)于可行域的頂點(diǎn)(

17、極點(diǎn)極點(diǎn))。lplp基本性質(zhì)基本性質(zhì)最優(yōu)解只需在有限個(gè)可行解（基本可行解）中尋找最優(yōu)解只需在有限個(gè)可行解（基本可行解）中尋找單純形法的基本思路單純形法的基本思路從一個(gè)頂點(diǎn)轉(zhuǎn)換到另一個(gè)頂點(diǎn)（即構(gòu)成從一個(gè)頂點(diǎn)轉(zhuǎn)換到另一個(gè)頂點(diǎn)（即構(gòu)成xb和和xn的向量的向量pi間的轉(zhuǎn)換），使目標(biāo)函數(shù)逐步下降。間的轉(zhuǎn)換），使目標(biāo)函數(shù)逐步下降。lp的通常解法是單純形法的通常解法是單純形法(g. b. dantzig, 1947)21內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法(interior point method) 20世紀(jì)世紀(jì)80年代人們提出的一類新的算法年代人們提出的一類新的算法內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法也是迭代法，但不再?gòu)目尚杏虻囊粋€(gè)頂點(diǎn)轉(zhuǎn)換到

18、另一個(gè)也是迭代法，但不再?gòu)目尚杏虻囊粋€(gè)頂點(diǎn)轉(zhuǎn)換到另一個(gè)頂點(diǎn)，而是直接從可行域的內(nèi)部逼近最優(yōu)解。頂點(diǎn)，而是直接從可行域的內(nèi)部逼近最優(yōu)解。 lplp其他算法其他算法有效集有效集(active set)方法方法 lp是是qp的特例（只需令所有二次項(xiàng)為零即可）的特例（只需令所有二次項(xiàng)為零即可） 可以用可以用qp的算法解的算法解lp(如如: 有效集方法，詳見(jiàn)下節(jié)有效集方法，詳見(jiàn)下節(jié)) 22x,fval,exitflag,output,lambda =linprog(c,a1,b1,a2,b2,v1,v2,x0,opt)matlab matlab 求解求解 lplp212211,. .minvxvbxab

19、xatsxczt輸入：輸入：x0 x0初始解初始解( (缺省時(shí)一般為缺省時(shí)一般為0)0)opt opt matlab matlab控制參數(shù)控制參數(shù)中間所缺參數(shù)項(xiàng)補(bǔ)中間所缺參數(shù)項(xiàng)補(bǔ)輸出：輸出：lambda lambda lagrangelagrange乘子，乘子，維維數(shù)等于約束個(gè)數(shù)，非零分量對(duì)數(shù)等于約束個(gè)數(shù)，非零分量對(duì)應(yīng)于起作用約束應(yīng)于起作用約束 lambda.ineqlin: 對(duì)應(yīng) a1xb1 lambda. eqlin : 對(duì)應(yīng) a2x = b2 lambda. lower : 對(duì)應(yīng) v1 x lambda. upper : 對(duì)應(yīng) x v2exam0802.m23matlab matlab

20、求解求解 lplpopt matlab控制參數(shù):三種三種算法選擇 缺省時(shí)采用大規(guī)模算法（是一種內(nèi)點(diǎn)算法）；缺省時(shí)采用大規(guī)模算法（是一種內(nèi)點(diǎn)算法）； 當(dāng)當(dāng)opt中中“l(fā)argescale”參數(shù)設(shè)置為參數(shù)設(shè)置為“off”時(shí)，采用中規(guī)模算法，時(shí)，采用中規(guī)模算法，該模式下缺省的算法是二次規(guī)劃的算法（一種有效集方法）；該模式下缺省的算法是二次規(guī)劃的算法（一種有效集方法）； 當(dāng)當(dāng)opt中中“l(fā)argescale”參數(shù)設(shè)置為參數(shù)設(shè)置為“off”，并且，并且“simplex”參參數(shù)設(shè)置為數(shù)設(shè)置為“on”時(shí)，采用單純形算法。時(shí)，采用單純形算法。只有有效集方法可以由用戶提供初始解只有有效集方法可以由用戶提供初始解

21、x0，其他兩個(gè)算法則不，其他兩個(gè)算法則不需要（即使提供了也會(huì)被需要（即使提供了也會(huì)被matlab忽略）。忽略）。 exam0801.mx,fval,exitflag,output,lambda =linprog(c,a1,b1,a2,b2,v1,v2,x0,opt)24c=12 8 22 16 -1.5 -1.5;a1=4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0;b1=600 240 100;a2=0 0 1 0 -0.8 0;0 0 0 1 0 -0.75;b2=0 0;v1=0 0 0 0 0 0; x,z0,ef,out,lag=linprog(-c,a1,b

22、1,a2,b2,v1)lag.ineqlin, lag.eqlin 實(shí)例實(shí)例1: 奶制品生產(chǎn)銷售計(jì)劃奶制品生產(chǎn)銷售計(jì)劃6543215 . 15 . 11622812xxxxxxzmax50436251xxxx48022)(2)(4656251xxxxxx10051 xx08 . 053xx075. 064xx0654321x ,x ,x ,x ,x ,x60034346521xxxx2402326521xxxxx=(0,168,19.2,0,24,0) ; z = -z0 =1730.4; lag.ineqlin =(1.58;3.26; 0.00) ; 25 15元可增加元可增加1桶牛奶，應(yīng)

23、否投資？桶牛奶，應(yīng)否投資？實(shí)例實(shí)例1: 奶制品生產(chǎn)銷售計(jì)劃奶制品生產(chǎn)銷售計(jì)劃6543215 . 15 . 11622812xxxxxxzmax50436251xxxx48022)(2)(4656251xxxxxx10051 xx5380 x.x 64750 x.x 0654321x ,x ,x ,x ,x ,xx=(0,168,19.2,0,24,0) ; z = -z0 =1730.4lag.ineqlin =(1.58;3.26; 0.00) ; 60034346521xxxx601z1=1731.98dz=z1-z = 1731.98-1730.4=1.58dz=lag.ineqlin(

24、1) dz*12=1.58*12= 18.9615應(yīng)該投資！應(yīng)該投資！ “影子價(jià)格影子價(jià)格” 26實(shí)例實(shí)例1: 奶制品生產(chǎn)銷售計(jì)劃奶制品生產(chǎn)銷售計(jì)劃 聘用臨時(shí)工人增加勞動(dòng)時(shí)間，工資最多每小時(shí)幾元？聘用臨時(shí)工人增加勞動(dòng)時(shí)間，工資最多每小時(shí)幾元？6543215 . 15 . 11622812xxxxxxzmax50436251xxxx48022)(2)(4656251xxxxxx10051 xx5380 x.x 64750 x.x 0654321x ,x ,x ,x ,x ,xx=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.

25、26; 0.00) ; 60034346521xxxx2402326521xxxxlag.ineqlin(2)=3.26，所以1小時(shí)勞動(dòng)時(shí)間的影子價(jià)格應(yīng)為3.26/2=1.63，即單位勞動(dòng)時(shí)間增加的利潤(rùn)是1.63(元) 27 b1，b2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？實(shí)例實(shí)例1: 奶制品生產(chǎn)銷售計(jì)劃奶制品生產(chǎn)銷售計(jì)劃6543215 . 15 . 11622812xxxxxxzmax50436251xxxx48022)(2)(4656251xxxxxx10051 xx5380 x.x 64750 x.x 0654321x ,x ,x ,x ,x ,x

26、x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ;若每公斤若每公斤b1的獲利下降的獲利下降10%,應(yīng)將目標(biāo)函數(shù)中應(yīng)將目標(biāo)函數(shù)中x3的系數(shù)改的系數(shù)改為為19.8，重新計(jì)算發(fā)現(xiàn)最優(yōu)，重新計(jì)算發(fā)現(xiàn)最優(yōu)解和最優(yōu)值均發(fā)生了變化解和最優(yōu)值均發(fā)生了變化若若b2的獲利向上波動(dòng)的獲利向上波動(dòng)10%，原計(jì)劃也不再是最優(yōu)的原計(jì)劃也不再是最優(yōu)的matlab沒(méi)有給出這種沒(méi)有給出這種敏感性分析敏感性分析的結(jié)果的結(jié)果(lindo/lingo可以可以)28非線性規(guī)劃非線性規(guī)劃(nlp)(nlp)基本原理基本原理ljxgtsxfzjx

27、n,.,1, 0)(. .)(min g1dg2=0g1=0g3=0gj0ox設(shè)設(shè)x為可行解，為可行解，位于約束邊界位于約束邊界1, 0)(jjxgjj1起作用約束起作用約束(j=1)2, 0)(jjxgjj2不起作用約束不起作用約束(j=2,3)0 (0gdx可行方向可行方向下降方向下降方向 )0()()(0 xfdxf(g)1 ( )(0)(1jjdxgtj)2(0)(dxft)()()()(2odxgxgdxgtjjj不等式約束不等式約束29x為最優(yōu)解為最優(yōu)解不存在滿足不存在滿足(1),(2)的的d) 1 ()(0)(1jjdxgtj)2(0)(dxftg3(x)=0g1(x)=0g2(

28、x)=0g(gj0)xog1(x)g2(x) f(x)x0g1(x0)df(x)=cc g1(x0)若若x沿沿d方向既可行又下降，則方向既可行又下降，則x不是最優(yōu)解不是最優(yōu)解觀察觀察f 的梯度能表示成的梯度能表示成g1和和g2的梯度的非負(fù)的梯度的非負(fù)線性組合線性組合!最優(yōu)解的必要條件最優(yōu)解的必要條件300)()(1xgxfjljiljxgjj, 2 , 1, 0)(kkt條件條件互補(bǔ)性條件ljxgmixhtsxfjixn,.,1,0)(,.,1,0)(.)(min，和則存在線性無(wú)關(guān)，0)(,1jijijjgh0)()()(11xgxhxfjljimiiiljxgjj, 1, 0)(0,1l)(

29、)(1jjxgj且且線性無(wú)關(guān)，則存在線性無(wú)關(guān)，則存在若若x為最優(yōu)解，為最優(yōu)解，最優(yōu)解的必要條件最優(yōu)解的必要條件31kktkkt條件的幾何解釋條件的幾何解釋qp f- g1- g2 f- g1- g20)(04)(010)(. .) 3() 7()(min23212222112221xxgxxxgxxxgt sxxxf0)()(1xgxfjljiljxgjj, 2 , 1, 0)(x2x10最優(yōu)解在最優(yōu)解在p(3,1)取得取得0)(2)()(, 0, 2, 121321pgpgpfp(3,1)是是kkt點(diǎn)點(diǎn)其它點(diǎn)其它點(diǎn)(如如q)均不是均不是(7,3)32二次規(guī)劃二次規(guī)劃(qp)(qp)及有效集方

30、法及有效集方法baxtscxhxxxft. .21)(min當(dāng)h為對(duì)稱陣，稱二次規(guī)劃當(dāng)h正定時(shí)，稱凸二次規(guī)劃凸二次規(guī)劃性質(zhì)：最優(yōu)點(diǎn)kkt點(diǎn)；局部最優(yōu)解全局最優(yōu)解；mttrbaxcxhxxxl),(21),(最優(yōu)解方程最優(yōu)解方程00baxachxttl函數(shù)函數(shù)等式約束 下的lagrange乘子法bax 33解二次規(guī)劃的有效集方解二次規(guī)劃的有效集方法法基本思想：基本思想：對(duì)于不等式約束的二次規(guī)劃，在某可行點(diǎn)處將不起作用約束去掉，起作用約束視為等式約束起作用約束視為等式約束，通過(guò)求解等式約束的二次規(guī)劃來(lái)改進(jìn)可行點(diǎn)。 若x為(1)的最優(yōu)解，則它也是(2)的最優(yōu)解 若x為(1)的可行解，又是(2)的kk

31、t點(diǎn)，且l乘子非負(fù)，則它必是(1)的最優(yōu)解。baxtscxhxxxft. .21)(min(1)1,. .21)(minjjbxat scxhxxxfjjt)(列的第是jaaj(2)基本基本原理原理34*, 0. .)*()*()*(21)*(minjjdatsdxcdxhdxdxfjt若d*0，且x*+d*可行則繼續(xù);否則確定步長(zhǎng)*( 1)使ap(x*+*d*)=bp，pj*，則有效集修正為j*p。設(shè)(1)的可行點(diǎn)為x*，有效集記作j*，用l乘子法求解:基本步驟基本步驟得d*, * 若d*=0, 則x*為(2)最優(yōu)解; 當(dāng) *非負(fù)時(shí)x*是(1)最優(yōu)解若d*=0, 且( *)q 1 g = .

32、 % gradient of the function if nargout 2 h = . % hessianend41nlcon.m給出約束,gradconstr=on時(shí)還給出梯度,形式為21221121, 0)(, 0)(. .)(minvxvbxabxaxcxctsxfzfunction c1,c2,gc1,gc2 = nlcon(x)c1 = . % nonlinear inequalities at xc2 = . % nonlinear equalities at xif nargout 2 gc1 = . % gradients of c1 gc2 = . % gradients of c2endmatlabmatlab求解求解約束約束nlpnlp例例4exam0804.m) 12424(min22122211xxxxxex010, 05 . 1212121xxxxxx01221 xx42matlabmatlab優(yōu)化工具箱優(yōu)化工具箱能求解的優(yōu)化模型能求解的優(yōu)化模型優(yōu)化工具箱優(yōu)化工具箱3.0 (matlab 7.0 r14)連續(xù)優(yōu)化連續(xù)優(yōu)化離散優(yōu)化離散優(yōu)化無(wú)約束優(yōu)化無(wú)約束優(yōu)化非線性非線性極小極小fminunc非光滑非光滑(不可不可微微)優(yōu)化優(yōu)化fminsearch非線性