《【數(shù)學(xué)建?！康?講_非線性規(guī)劃模型》由會(huì)員分享，可在線閱讀，更多相關(guān)《【數(shù)學(xué)建?！康?講_非線性規(guī)劃模型（36頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù) 學(xué) 建 模非 線 性 規(guī) 劃 模 型 1.非 線 性 規(guī) 劃 的 基 本 理 論 4.實(shí) 驗(yàn) 作 業(yè) 2.用 數(shù) 學(xué) 軟 件 求 解 非 線 性 規(guī) 劃 3 . 供 應(yīng) 與 選 址 以 及 生 產(chǎn) 安 排 計(jì) 劃 問(wèn) 題 *非 線 性 規(guī) 劃 的 基 本 解 法非 線 性 規(guī) 劃 的 基 本 概 念非 線 性 規(guī) 劃 返 回 定 義 如 果 目 標(biāo) 函 數(shù) 或 約 束 條 件 中 至 少 有 一 個(gè) 是 非 線 性 函 數(shù) ,則 最 優(yōu) 化 問(wèn) 題 就 叫 做 非 線 性 規(guī) 劃 問(wèn) 題 非 現(xiàn) 性 規(guī) 劃 的 基 本 概 念 一 般 形 式 : （ 1） 其 中 ， 是 定 義 在 Rn

2、 上 的 實(shí) 值 函數(shù) ， 簡(jiǎn) 記 : Xfmin ji hgf , 其 它 情 況 : 求 目 標(biāo) 函 數(shù) 的 最 大 值 ， 或 約 束 條 件 小 于 等 于 零兩 種 情 況 ， 都 可 通 過(guò) 取 其 相 反 數(shù) 化 為 上 述 一 般 形 式 1nj1ni1n R :h ,R :g ,R : RRRf nTn RxxxX = , 21L = = .,.,2,1 0 m;1,2,., 0. ljXh iXgts ji 定 義 1 把 滿 足 問(wèn) 題 （ 1） 中 條 件 的 解 稱 為 可 行 解 （ 或 可 行點(diǎn) ） ， 所 有 可 行 點(diǎn) 的 集 合 稱 為 可 行 集 （ 或

3、可 行 域 ） 記 為 D 即 問(wèn) 題 (1)可 簡(jiǎn) 記 為 XfDXmin定 義 2 對(duì) 于 問(wèn) 題 (1),設(shè) ,若 存 在 ,使 得 對(duì) 一 切 ,且 ,都 有 ,則 稱 X*是 f(X)在 D上 的局 部 極 小 值 點(diǎn) （ 局 部 最 優(yōu) 解 ） 特 別 地 ,當(dāng) 時(shí) ， 若 ,則 稱 X *是 f(X)在 D上 的 嚴(yán) 格 局 部 極 小 值 點(diǎn) （ 嚴(yán) 格 局 部 最優(yōu) 解 ） DX * 0DX *XX *XX XfXf * XfXf *定 義 3 對(duì) 于 問(wèn) 題 (1),設(shè) ,若 對(duì) 任 意 的 ,都 有則 稱 X*是 f(X)在 D上 的 全 局 極 小 值 點(diǎn) （ 全 局

4、最 優(yōu) 解 ） 特 別 地 ,當(dāng) 時(shí) ， 若 ,則 稱 X*是 f(X)在 D上 的 嚴(yán) 格 全 局 極 小 值點(diǎn) （ 嚴(yán) 格 全 局 最 優(yōu) 解 ） DX * DX *XX XfXf * 返 回)( nRX nji RXXhXg XD = = ,0,0| ,Xf Xf * 非 線 性 規(guī) 劃 的 基 本 解 法SUTM外 點(diǎn) 法SUTM內(nèi) 點(diǎn) 法 （ 障 礙 罰 函 數(shù) 法 ）1 罰 函 數(shù) 法2 近 似 規(guī) 劃 法 返 回 罰 函 數(shù) 法 罰 函 數(shù) 法 基 本 思 想 是 通 過(guò) 構(gòu) 造 罰 函 數(shù) 把約 束 問(wèn) 題 轉(zhuǎn) 化 為 一 系 列 無(wú) 約 束 最 優(yōu) 化 問(wèn) 題 ，進(jìn) 而 用

5、無(wú) 約 束 最 優(yōu) 化 方 法 去 求 解 這 類 方 法稱 為 序 列 無(wú) 約 束 最 小 化 方 法 簡(jiǎn) 稱 為 SUMT法 其 一 為 SUMT外 點(diǎn) 法 ， 其 二 為 SUMT內(nèi) 點(diǎn)法 )2( ,0min, 1 21 2 = = lj jmi i XhMXgMXfMXT可 設(shè) ： R1 min , (3)nX T X M將 問(wèn) 題 （ ） 轉(zhuǎn) 化 為 無(wú) 約 束 問(wèn) 題 ： 其 中 T(X,M)稱 為 罰 函 數(shù) ， M稱 為 罰 因 子 ， 帶 M的 項(xiàng) 稱 為 罰 項(xiàng) ，這 里 的 罰 函 數(shù) 只 對(duì) 不 滿 足 約 束 條 件 的 點(diǎn) 實(shí) 行 懲 罰 :當(dāng) 時(shí) ， 滿 足各 ，

6、 故 罰 項(xiàng) 為 0， 不 受 懲 罰 當(dāng) 時(shí) ,必有 約 束 條 件 ， 故 罰 項(xiàng) 大 于 0， 要 受 懲 罰 DX 0,0 = XhXg ii DX 00 XhXg ii 或 SUTM外 點(diǎn) 法 min 0 1,2,., ; s.t. (1)0 1,2,., .ij f Xg X i mh X j l = = =對(duì) 一 般 的 非 線 性 規(guī) 劃 ： 罰 函 數(shù) 法 的 缺 點(diǎn) ： 每 個(gè) 近 似 最 優(yōu) 解 Xk往 往 不 是 容 許 解 ， 而只 能 近 似 滿 足 約 束 ， 在 實(shí) 際 問(wèn) 題 中 這 種 結(jié) 果 可 能 不 能 使 用 ； 在解 一 系 列 無(wú) 約 束 問(wèn) 題

7、 中 ， 計(jì) 算 量 太 大 ， 特 別 是 隨 著 Mk的 增 大 ，可 能 導(dǎo) 致 錯(cuò) 誤 1 任 意 給 定 初 始 點(diǎn) X0， 取 M11， 給 定 允 許 誤 差 ， 令 k=1；2 求 無(wú) 約 束 極 值 問(wèn) 題 的 最 優(yōu) 解 ， 設(shè) Xk=X(Mk)， 即 ；3 若 存 在 ， 使 ,則 取 MkM( ),令 k=k+1返 回 （ 2） ， 否 則 ， 停 止 迭 代 得 最 優(yōu) 解 計(jì) 算 時(shí) 也 可 將 收 斂 性 判 別 準(zhǔn) 則 改 為 0 Rmin ,nX T X M Rmin , ( , )n k kX T X M T X M = mii 1 ki Xg 10, 1

8、= MMk 0,0min1 2 =mi i XgM kXX * ki Xg SUTM外 點(diǎn) 法 (罰 函 數(shù) 法 )的 迭 代 步 驟 min (1)s.t. 0 1,2,.,if Xg X i m =考 慮 問(wèn) 題 ： 0 0| 0, 1,2, , iD X g X i m D= = L設(shè) 集 合 ， 是可 行 域 中 所 有 嚴(yán) 格 內(nèi) 點(diǎn) 的 集 合 . 0 1min , kk kX D I X r X r 這 樣 問(wèn) 題 （ ） 就 轉(zhuǎn) 化 為 求 一 系 列 極 值 問(wèn) 題 ：得 （ ） . SUTM內(nèi) 點(diǎn) 法 （ 障 礙 函 數(shù) 法 ） 為 障 礙 因 子 .為 障 礙 項(xiàng) ，或其

9、 中 稱 或 ：構(gòu) 造 障 礙 函 數(shù) rXgrXgr XgrXfrXIXgrXfrXIrXI mi imi i mi imi i = = = 11 11 1 ln 1)(),( ln, 內(nèi) 點(diǎn) 法 的 迭 代 步 驟 (1) 給 定 允 許 誤 差 0 ， 取 10,01 r ； 近 似 規(guī) 劃 法 的 基 本 思 想 ： 將 問(wèn) 題 (3)中 的 目 標(biāo) 函 數(shù) 和 約 束 條 件 近 似 為 線 性 函 數(shù) ， 并 對(duì) 變 量 的 取 值 范 圍 加 以 限 制 ， 從而 得 到 一 個(gè) 近 似 線 性 規(guī) 劃 問(wèn) 題 ， 再 用 單 純 形 法 求 解 之 ，把 其 符 合 原 始 條

10、 件 的 最 優(yōu) 解 作 為 (3)的 解 的 近 似 Xf 0 ( 1,., ); 0 ( 1, , )i jg X i m h X j l = = =L近 似 規(guī) 劃 法每 得 到 一 個(gè) 近 似 解 ， 都 從 這 點(diǎn) 出 發(fā) ， 重 復(fù) 以 上 步 驟 這 樣 ， 通 過(guò) 求 解 一 系 列 線 性 規(guī) 劃 問(wèn) 題 ， 產(chǎn) 生 一 個(gè)由 線 性 規(guī) 劃 最 優(yōu) 解 組 成 的 序 列 ， 經(jīng) 驗(yàn) 表 明 ， 這 樣 的 序列 往 往 收 斂 于 非 線 性 規(guī) 劃 問(wèn) 題 的 解 近 似 規(guī) 劃 法 的 算 法 步 驟 如 下 ： (3)在 上 述 近 似 線 性 規(guī) 劃 問(wèn) 題 的

11、基 礎(chǔ) 上 增 加 一 組 限 制 步 長(zhǎng) 的 線 性 約 束 條 件 因 為 線 性 近 似 通 常 只 在 展 開(kāi) 點(diǎn) 附 近 近 似 程 度 較 高 ， 故 需 要 對(duì) 變 量 的 取 值 范 圍 加 以 限 制 ， 所 增 加 的 約 束 條 件 是 ： njxx kjkjj ,1L= 求 解 該 線 性 規(guī) 劃 問(wèn) 題 ， 得 到 最 優(yōu) 解 1kX ； 返 回 用 MATLAB軟 件 求 解 ,其 輸 入 格 式 如 下 : 1x=quadprog(H,C,A,b); 2x=quadprog(H,C,A,b,Aeq,beq); 3x=quadprog(H,C,A,b,Aeq,beq

12、,VLB,VUB); 4x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options); 6x,fval=quaprog(); 7x,fval,exitflag=quaprog(); 8x,fval,exitflag,output=quaprog();1 二 次 規(guī) 劃 例 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x2 2 -x1+2x2 2 x1 0, x2 0 1 寫 成 標(biāo) 準(zhǔn) 形 式 ： 2 輸 入 命 令 ： H=2

13、 -2; -2 4; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3 運(yùn) 算 結(jié) 果 為 ： x =08 1.2， z = -7.2T1 11 2 2 2 2 -2 21min ( , ) 2 4 62 x xz x x x x = 1212 1 1 21 2 200 xxxx s.t. 1 首 先 建 立M文 件fun.m,用 來(lái) 定 義 目 標(biāo) 函 數(shù) F（ X）:function f=fun(X);f=F(X);2 一 般 非 線 性 規(guī) 劃 其 中 X

14、為 n維 變 元 向 量 ， G(X)與 Ceq(X)均 為 非 線 性 函 數(shù) 組 成的 向 量 ， 其 他 變 量 的 含 義 與 線 性 規(guī) 劃 、 二 次 規(guī) 劃 中 相 同 用MATLAB求 解 上 述 問(wèn) 題 ， 基 本 步 驟 分 三 步 ： 3 建 立 主 程 序.求 解 非 線 性 規(guī) 劃 的 函 數(shù) 是fmincon,命 令 的 基 本格 式 如 下 ： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fm

15、incon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon() (7) x,fval,exitflag= fmincon() (8)x,fval,exitflag,output= fmincon()輸 出 極 值 點(diǎn) M文 件 迭 代 的 初 值 參 數(shù) 說(shuō) 明變 量 上 下 限 1 寫 成 標(biāo) 準(zhǔn) 形 式 ： s.t. 0054 632 21 21 xx xx 2100 xx 222121 21212min xxxxf

16、 = 222121 21212min xxxxf = 2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0 例 2 2 先 建 立M-文 件 fun3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23 再 建 立 主 程 序youh2m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4 運(yùn) 算 結(jié) 果 為 ： x = 0 7647 1 0588 fval = -2

17、0294 1 先 建 立M文 件fun4m定 義 目 標(biāo) 函 數(shù): function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);1 2 21 2 1 2 2( ) e (4 2 4 2 1)xf x x x x x x= x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0 例 3 2 再 建 立 M文 件 mycon m定 義 非 線 性 約 束 ： function g,ceq=mycon(x) g=15+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;

18、 ceq=; 3 主 程 序youh3m為 :x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon)4 運(yùn) 算 結(jié) 果 為 ： x = -12250 12250 fval = 18951 例 4 1 22 21 1 22 22 1 21 2 min 2s.t. 25 0 7 0 0 5, 0 10f X x xg X x xg X x xx x= = = 1 先 建 立M文 件funm定 義 目 標(biāo) 函 數(shù): function f=fun(x); f=-2*x(1)-x(2

19、);2 再 建 立 M文 件mycon2m定 義 非 線 性 約 束 ：function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7; ceq=; 3 主 程 序fxxm為 : x0=3;25; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0, VLB,VUB,mycon2) 4 運(yùn) 算 結(jié) 果 為 : x = 40000 30000fval =-110000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1

20、algorithm: 1x44 char firstorderopt: cgiterations: 返 回 應(yīng) 用 實(shí) 例 ： 供 應(yīng) 與 選 址 某 公 司 有 6個(gè) 建 筑 工 地 要 開(kāi) 工 ， 每 個(gè) 工 地 的 位 置 （ 用 平 面 坐 標(biāo) 系a， b表 示 ， 距 離 單 位 ： km） 及 水 泥 日 用 量 d(t)由 下 表 給 出 目 前 有兩 個(gè) 臨 時(shí) 料 場(chǎng) 位 于 A(5,1)， B(2,7)， 日 儲(chǔ) 量 各 有 20t 假 設(shè) 從 料 場(chǎng) 到工 地 之 間 均 有 直 線 道 路 相 連 （ 1） 試 制 定 每 天 的 供 應(yīng) 計(jì) 劃 ， 即 從 A， B兩

21、 料 場(chǎng) 分 別 向 各 工 地 運(yùn)送 多 少 水 泥 ， 可 使 總 的 噸 千 米 數(shù) 最 小 （ 2） 為 了 進(jìn) 一 步 減 少 噸 千 米 數(shù) ， 打 算 舍 棄 兩 個(gè) 臨 時(shí) 料 場(chǎng) ， 改 建 兩個(gè) 新 的 ， 日 儲(chǔ) 量 各 為 20t， 問(wèn) 應(yīng) 建 在 何 處 ， 節(jié) 省 的 噸 千 米 數(shù) 有 多 大 ？ （ 一 ） 建 立 模 型 記 工 地 的 位 置 為 (ai， bi)， 水 泥 日 用 量 為 di， i=1,6;料 場(chǎng) 位 置 為(xj， yj)， 日 儲(chǔ) 量 為 ej， j=1,2； 料 場(chǎng) j向 工 地 i的 運(yùn) 送 量 為 Xij當(dāng) 用 臨 時(shí) 料 場(chǎng)

22、時(shí) 決 策 變 量 為 ： X ij，當(dāng) 不 用 臨 時(shí) 料 場(chǎng) 時(shí) 決 策 變 量 為 ： Xij， xj， yj （ 二 ） 使 用 臨 時(shí) 料 場(chǎng) 的 情 形 使 用 兩 個(gè) 臨 時(shí) 料 場(chǎng) A(5,1)， B(2,7) 求 從 料 場(chǎng) j向 工 地 i的 運(yùn) 送量 Xij . 在 各 工 地 用 量 必 須 滿 足 和 各 料 場(chǎng) 運(yùn) 送 量 不 超 過(guò) 日 儲(chǔ) 量 的 條件 下 ， 使 總 的 噸 千 米 數(shù) 最 小 ， 這 是 線 性 規(guī) 劃 問(wèn) 題 線 性 規(guī) 劃 模型 為 ： = = 21 61 ),(min j i ijXjiaaf 2,1 , 6,2,1 , s.t. 61

23、21 = = jeX idX ji ij ij ijL設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編 寫 程 序gying1m 計(jì) 算 結(jié) 果 為 ：x = 3 0000 5 0000 0 0000 7 0000 0 0000 1 0000 0 0000 0 0000 4 0000 0 0000 6 0000 10 0000fval = 136 2275 （ 三 ） 改 建 兩 個(gè) 新 料 場(chǎng) 的 情

24、 形 改 建 兩 個(gè) 新 料 場(chǎng) ， 要 同 時(shí) 確 定 料 場(chǎng) 的 位 置 (xj,yj)和 運(yùn) 送 量Xij， 在 同 樣 條 件 下 使 總 噸 千 米 數(shù) 最 小 這 是 非 線 性 規(guī) 劃 問(wèn)題 非 線 性 規(guī) 劃 模 型 為 ： 設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16 （ 1） 先 編 寫 M文 件liaochm定 義 目

25、 標(biāo) 函 數(shù) MATLAB（ liaoch）(2) 取 初 值 為 線 性 規(guī) 劃 的 計(jì) 算 結(jié) 果 及 臨 時(shí) 料 場(chǎng) 的 坐 標(biāo) : x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編 寫 主 程 序gying2mMATLAB（ gying2） (3) 計(jì) 算 結(jié) 果 為 ：x= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867fval = 1054626exitflag = 1 (4) 若 修 改 主 程 序 gying2 m, 取 初 值 為 上 面

26、 的 計(jì) 算 結(jié) 果 :x0= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867 則 得 結(jié) 果 為 :x=30000 50000 03094 70000 00108 06798 0 0 36906 0 59892 103202 55369 49194 58291 72852fval =1034760exitflag = 1總 的 噸 千 米 數(shù) 比 上 面 結(jié) 果 略 優(yōu) (5) 若 再 取 剛 得 出 的 結(jié) 果 為 初 值 , 卻 計(jì) 算 不 出 最 優(yōu) 解 (6) 若 取 初

27、 值 為 : x0=3 5 4 7 1 0 0 0 0 0 5 11 5 6348 4 8687 7 2479 7 7499, 則 計(jì) 算 結(jié) 果 為 :x=3 0000 5 0000 4 0000 7 0000 1 0000 0 0 0 0 0 5 0000 11 0000 5 6959 4 9285 7 2500 7 7500fval =89 8835exitflag = 1總 的 噸 千 米 數(shù) 89 8835比 上 面 結(jié) 果 更 好 通 過(guò) 此 例 可 看 出fmincon函 數(shù) 在 選 取 初 值 上 的 重 要 性 返 回 某 廠 向 用 戶 提 供 發(fā) 動(dòng) 機(jī) ， 合 同 規(guī)

28、定 ， 第 一 、 二 、三 季 度 末 分 別 交 貨 40臺(tái) 、 60臺(tái) 、 80臺(tái) 每 季 度 的 生產(chǎn) 費(fèi) 用 為 （ 單 位 :元 ） , 其 中 x是 該 季 度 生產(chǎn) 的 臺(tái) 數(shù) 若 交 貨 后 有 剩 余 ， 可 用 于 下 季 度 交 貨 ，但 需 支 付 存 儲(chǔ) 費(fèi) ， 每 臺(tái) 每 季 度 c元 已 知 工 廠 每 季 度最 大 生 產(chǎn) 能 力 為 100臺(tái) ， 第 一 季 度 開(kāi) 始 時(shí) 無(wú) 存 貨 ， 設(shè)a=50、 b=0.2、 c=4， 問(wèn) :工 廠 應(yīng) 如 何 安 排 生 產(chǎn) 計(jì) 劃 ，才 能 既 滿 足 合 同 又 使 總 費(fèi) 用 最 低 討 論 a、 b、 c變 化對(duì) 計(jì) 劃 的 影 響 ， 并 作 出 合 理 的 解 釋 2bxaxxf =生 產(chǎn) 計(jì) 劃 安 排 問(wèn) 題 練 習(xí) 返 回