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

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

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

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

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

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

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

7、 中 ， 計 算 量 太 大 ， 特 別 是 隨 著 Mk的 增 大 ，可 能 導 致 錯 誤 1 任 意 給 定 初 始 點 X0， 取 M11， 給 定 允 許 誤 差 ， 令 k=1；2 求 無 約 束 極 值 問 題 的 最 優(yōu) 解 ， 設 Xk=X(Mk)， 即 ；3 若 存 在 ， 使 ,則 取 MkM( ),令 k=k+1返 回 （ 2） ， 否 則 ， 停 止 迭 代 得 最 優(yōu) 解 計 算 時 也 可 將 收 斂 性 判 別 準 則 改 為 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外 點 法 (罰 函 數(shù) 法 )的 迭 代 步 驟 min (1)s.t. 0 1,2,.,if Xg X i m =考 慮 問 題 ： 0 0| 0, 1,2, , iD X g X i m D= = L設 集 合 ， 是可 行 域 中 所 有 嚴 格 內 點 的 集 合 . 0 1min , kk kX D I X r X r 這 樣 問 題 （ ） 就 轉 化 為 求 一 系 列 極 值 問 題 ：得 （ ） . SUTM內 點 法 （ 障 礙 函 數(shù) 法 ） 為 障 礙 因 子 .為 障 礙 項 ，或其

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

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

11、基 礎 上 增 加 一 組 限 制 步 長 的 線 性 約 束 條 件 因 為 線 性 近 似 通 常 只 在 展 開 點 附 近 近 似 程 度 較 高 ， 故 需 要 對 變 量 的 取 值 范 圍 加 以 限 制 ， 所 增 加 的 約 束 條 件 是 ： njxx kjkjj ,1L= 求 解 該 線 性 規(guī) 劃 問 題 ， 得 到 最 優(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 寫 成 標 準 形 式 ： 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 運 算 結 果 為 ： 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,用 來 定 義 目 標 函 數(shù) F（ X）:function f=fun(X);f=F(X);2 一 般 非 線 性 規(guī) 劃 其 中 X

14、為 n維 變 元 向 量 ， G(X)與 Ceq(X)均 為 非 線 性 函 數(shù) 組 成的 向 量 ， 其 他 變 量 的 含 義 與 線 性 規(guī) 劃 、 二 次 規(guī) 劃 中 相 同 用MATLAB求 解 上 述 問 題 ， 基 本 步 驟 分 三 步 ： 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()輸 出 極 值 點 M文 件 迭 代 的 初 值 參 數(shù) 說 明變 量 上 下 限 1 寫 成 標 準 形 式 ： 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 運 算 結 果 為 ： x = 0 7647 1 0588 fval = -2

17、0294 1 先 建 立M文 件fun4m定 義 目 標 函 數(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 運 算 結 果 為 ： 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定 義 目 標 函 數(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 運 算 結 果 為 : x = 40000 30000fval =-110000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1

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

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

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

23、21 = = jeX idX ji ij ij ijL設 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 計 算 結 果 為 ：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 （ 三 ） 改 建 兩 個 新 料 場 的 情

24、 形 改 建 兩 個 新 料 場 ， 要 同 時 確 定 料 場 的 位 置 (xj,yj)和 運 送 量Xij， 在 同 樣 條 件 下 使 總 噸 千 米 數(shù) 最 小 這 是 非 線 性 規(guī) 劃 問題 非 線 性 規(guī) 劃 模 型 為 ： 設 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、 標 函 數(shù) MATLAB（ liaoch）(2) 取 初 值 為 線 性 規(guī) 劃 的 計 算 結 果 及 臨 時 料 場 的 坐 標 : x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編 寫 主 程 序gying2mMATLAB（ gying2） (3) 計 算 結 果 為 ：x= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867fval = 1054626exitflag = 1 (4) 若 修 改 主 程 序 gying2 m, 取 初 值 為 上 面

26、 的 計 算 結 果 :x0= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867 則 得 結 果 為 :x=30000 50000 03094 70000 00108 06798 0 0 36906 0 59892 103202 55369 49194 58291 72852fval =1034760exitflag = 1總 的 噸 千 米 數(shù) 比 上 面 結 果 略 優(yōu) (5) 若 再 取 剛 得 出 的 結 果 為 初 值 , 卻 計 算 不 出 最 優(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, 則 計 算 結 果 為 :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比 上 面 結 果 更 好 通 過 此 例 可 看 出fmincon函 數(shù) 在 選 取 初 值 上 的 重 要 性 返 回 某 廠 向 用 戶 提 供 發(fā) 動 機 ， 合 同 規(guī)

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