《高等運籌第四講(劉巍)大連海事大學(xué)》由會員分享，可在線閱讀，更多相關(guān)《高等運籌第四講(劉巍)大連海事大學(xué)（81頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、高等運籌學(xué)大連海事大學(xué)劉巍 第二篇 運籌學(xué)中的數(shù)學(xué)規(guī)劃第四章 線性規(guī)劃第五章 非線性規(guī)劃第六章 錐規(guī)劃、矩陣規(guī)劃及變分不等式第七章 整數(shù)規(guī)劃第八章 動態(tài)規(guī)劃第九章 向量優(yōu)化（多目標(biāo)優(yōu)化） 第五章 非線性規(guī)劃（續(xù)） 本 節(jié) 課 討 論 n元 函 數(shù) 的 無 約 束 非 線 性 規(guī) 劃 問 題 ：nTn Rxxxxxf ).,(),(min 21其 中求 解 此 類 模 型 (UMP)的 方 法 稱 為 無 約 束 最 優(yōu) 化 方 法 。無 約 束 最 優(yōu) 化 方 法 通 常 有 兩 類 ：解 析 法 ： 要 使 用 導(dǎo) 數(shù) 的 方 法 ；直 接 法 ： 無 須 考 慮 函 數(shù) 是 否 可 導(dǎo) ，

2、 直 接 使 用 函 數(shù) 值 。 退 出前 一 頁 后 一 頁 4.4無約束最優(yōu)化方法 1.無 約 束 問 題 的 最 優(yōu) 性 條 件 處 可 微 ，在 點設(shè) nn RxRRf : 使若 存 在 ,nRp0)( pxf T 處 的 下 降 方 向在 點是則 向 量 xfp定 理 1定 理 2 ,* 可 微在 點設(shè) nRxf 的 局 部 最 優(yōu) 解是若 )(min* xfx0)( * xf則梯 度 為 0的 點 稱 為 函 數(shù) 的 駐 點 。駐 點 可 能 是 極 小 點 ， 也 可 能 是 極 大 點 ， 也 可 能 即 不 是 極 大也 不 是 極 小 ， 這 時 稱 為 函 數(shù) 的 鞍 點

3、 。定 理 2說 明 ： UMP問 題 的 局 部 最 優(yōu) 解 必 是 目 標(biāo) 函 數(shù) 的 駐 點 。注 ： 退 出前 一 頁 后 一 頁 定 理 3 存 在 ，矩 陣處 的在 點設(shè) )( *2* xfHesseRxf n 正 定并 且若 )(,0)( *2* xfxf 的 嚴(yán) 格 局 部 最 優(yōu) 解是則 )(min* xfx定 理 4 上 的 可 微 凸 函 數(shù)是設(shè) nnn RfRxRRf ,: *1 ， 則若 0)( * xf 的 整 體 最 優(yōu) 解是則 )(min* xfx 退 出前 一 頁 后 一 頁 例 1232221321 24),(min xxxxxxxf 題求 無 約 束 非

4、線 性 規(guī) 劃 問解 ：1.先 求 出 目 標(biāo) 函 數(shù) 的 全 部 駐 點 ；2.利 用 充 分 條 件 判 斷 駐 點 是 不 是 最 優(yōu) 點 。 退 出前 一 頁 后 一 頁 關(guān) 于 梯 度 的 復(fù) 習(xí) ：梯 度 是 一 個 向 量 。 n元 函 數(shù) f(x1 ,x2 ,xn)在 某 點 x處 的梯 度 為 ： Tnxfxfxf ),.,( 21 梯 度 的 方 向 與 函 數(shù) f的 等 值 線 的 一 個 法 線 方 向 相 同 ，從 較 低 的 等 值 線 指 向 較 高 的 等 值 線 。梯 度 的 方 向 就 是 函 數(shù) f的 值 增 加 最 快 的 方 向 ， 其 相 反方 向

5、就 是 函 數(shù) 值 降 低 最 快 的 方 向 。2.最 速 下 降 法 退 出前 一 頁 后 一 頁 最 速 下 降 法 又 稱 為 梯 度 法 ， 由 Cauchy于 1847年 給 出 。最 速 下 降 法 解 決 的 是 具 有 連 續(xù) 可 微 的 目 標(biāo) 函 數(shù) 的UMP問 題 。最 速 下 降 法 的 基 本 思 想 ： 從 當(dāng) 前 點 xk出 發(fā) 尋 找 使 得目 標(biāo) 函 數(shù) 下 降 最 快 的 方 向 ， 即 負 梯 度 方 向 。 退 出前 一 頁 后 一 頁 最 速 下 降 法 計 算 步 驟 ：選 區(qū) 初 始 點 x0和 精 度 計 算 )( 0 xf |)(| 0 xf

6、 是 否 停 止 ， 輸 出 x 0求 p0= )( 0 xf計 算 t0,使 )(min 000 tpxft 計 算 x1= x0+ t0 p0 退 出前 一 頁 后 一 頁 例 60 222121 10,)22( 25),(min 終 止 誤 差，初 始 點用 最 速 下 降 法 解 Tx xxxxf解 ： Txxxf )50,2()(1 21、 目 標(biāo) 函 數(shù) 的 梯 度 尋 找 下 一 個 點、 ,|)(|2 0 xf Txfp )100,4()(3 00 、 構(gòu) 造 負 梯 度 方 向 020037.0),(min4 000 ttpxf 得、 解 一 維 搜 索 問 題 003070

7、.0919878.15 0001 ptxx、 得 到 第 二 個 點、 回 到 第 二 步6 的 精 度 。輪 循 環(huán) ， 即 可 達 到 需 要、 經(jīng) 過 107 退 出前 一 頁 后 一 頁 說 明 ：觀 察 P119的 圖 ， 可 以 發(fā) 現(xiàn) x1 x0垂 直 于 目 標(biāo) 函 數(shù) 的等 值 線 （ 圖 中 的 虛 線 ） 在 x0的 切 線 ；最 速 下 降 方 法 相 鄰 的 兩 個 搜 索 方 向 是 相 互 垂 直 的 ，即 x1 x0垂 直 x1 x2；最 速 下 降 法 解 決 UMP的 缺 陷 ： 迭 代 點 越 靠 近 最優(yōu) 解 則 目 標(biāo) 函 數(shù) 下 降 的 速 度 越

8、慢 ；優(yōu) 點 ： 迭 代 點 列 總 是 收 斂 的 ， 而 且 計 算 過 程 簡 單 。 退 出前 一 頁 后 一 頁 本 節(jié) 課 討 論 約 束 非 線 性 規(guī) 劃 問 題 MP qjxh pixgts xfji ,1 ,0)( ,1 ,0)( . )( min 其 中 ,x=(x1 ,x2, xn)T， f(x),gi(x),hj(x)為 x的 實 值 函 數(shù)求 解 此 類 模 型 (MP)的 方 法 稱 為 約 束 最 優(yōu) 化 方 法 。 退 出前 一 頁 后 一 頁 4.5約束最優(yōu)化方法 1.約 束 最 優(yōu) 化 問 題 的 最 優(yōu) 性 條 件 qjxh pixgRxXx iin ,

9、1,0)( ,1,0)(* 設(shè)對 于 MP問 題 ： qjxh pixgts xfji ,1 ,0)( ,1 ,0)( . )( min qjxhpixg ji ,1,0)(,1,0)( * ，則 退 出前 一 頁 后 一 頁 有 兩 種 情 況 ：pixgi ,1,0)( * 0)(2 * xgi、 0)(1 * xgi、 若 x*有 變 化 ， 則 約 束 條 件 可 能 沒 有 破 壞若 x*有 變 化 ， 則 約 束 條 件 一 定 被 破 壞的 積 極 約 束稱 為的 約 束 條 件使 * 0)(0)( xxgxg ii 令 J表 示 MP的 全 部 等 式 約 束 的 下 標(biāo) 集

10、合 ， 即 J=1,2q,I表 示 MP的 全 部 不 等 式 約 束 的 下 標(biāo) 集 合 ， 即 I=1,2p,0)(|)( * IixgixI i 記 x *的 積 極 約 束 的 下 標(biāo) 集 合退 出前 一 頁 后 一 頁 定 理 1 qjxh pixgts xfji ,1 ,0)( ,1 ,0)( . )( min 對 于 線 性 無 關(guān)，、 處 連 續(xù) 可 微在、 處 連 續(xù)在 處 可 微在、 JjxhxIixg xJjxh xxIIi xxIixg jiji ),()(),(3 ),(2 )( )()(1 * * * *若 x*是 局 部 最 優(yōu) 解 ,則 使 得兩 組 實 數(shù) J

11、jxIi ji ,),(, * * *,0 0)( *xIi xhxgxfi xIi Jj jjii 退 出前 一 頁 后 一 頁 定 理 1的 說 明 ： 稱 為 約 束 規(guī) 范 條 件 。線 性 無 關(guān)、 ,),(),(),( 1 * JjxhxIixg ji 2、 稱 下 述 表 達 式 為 MP的 Kuhn-Tucker條 件 ， 簡 稱 K-T條 件 * *,0 0)( *xIi xhxgxfi xIi Jj jjii 滿 足 K-T條 件 的 點 稱 為 MP的 K-T點 ， 定 理 1說 明 MP的 局 部 最優(yōu) 解 一 定 是 MP的 K-T點 。為 了 求 出 MP的 最 優(yōu)

12、 解 ， 可 以 先 找 出 MP的 K-T點 ， 再 做 進 一步 的 判 斷 。 退 出前 一 頁 后 一 頁 3、 定 理 1的 實 例 說 明 01)( 0)( 0)( 02)( . )2()1(),( min 211 23 12 211 222121 xxxh xxg xxg xxxgts xxxxf定 理 1表 明 ： 若 (x1,x2)T是 局 部 最 優(yōu) 解 ， g1和 g2為 積 極 約 束 ， 則 ：xx 1 1 2 121 22( 1) 1 1 1 02( 2) 1 0 1, 0 * *,0 0)( *xIi xhxgxfi xIi Jj jjii 退 出前 一 頁 后

13、一 頁 是 其 局 部 最 優(yōu) 解 ， 則若對 于 *,0)( . )(min xxgts xfi 使 得實 數(shù) )(, * xIii * *,0 0)( *xIi xgxfi xIi ii 0 )( * * ixIi ii xgxf 4.定 理 1的 特 例 1 退 出前 一 頁 后 一 頁 是 局 部 最 優(yōu) 解 ， 則， 若對 于 *0)( . )( min xxhts xfj 使 得 ：Jjj ,* 0)( * Jj jj xhxf Jj jj xhxf *)( 生 成 的 空 間 中 。 落 在 由 向 量則局 部 最 優(yōu) 解若 Jjxhxfx j ),()(, *5.定 理 1的

14、特 例 2 退 出前 一 頁 后 一 頁 6.定 理 1的 改 進 ： 線 性 無 關(guān)，、 處 連 續(xù) 可 微在、 處 可 微在，、 JjxhxIixg xJjxh xIixg jiji ),()(),(3 ),(2 )(1 * qjxh pixgts xfji ,1 ,0)( ,1 ,0)( . )( min 對 于若 x*是 局 部 最 優(yōu) 解 ,則 使 得兩 組 實 數(shù) JjIi ji , * Ii Iixg xhxgxfi ii Ii Jj jjii,0 ,0 0)(* * * 互 補 松 緊 條 件 退 出前 一 頁 后 一 頁 7.實 例 說 明 改進 后 的 定 理 1： 01)

15、( 0)( 0)( 02)( . )2()1(),( min 211 23 12 211 222121 xxxh xxg xxg xxxgts xxxxf定 理 1改 進 后 表 明 ： 若 (x1,x2)T是 局 部 最 優(yōu) 解 ， 則 ： Ii Iixg xhxgxfi ii Ii Jj jjii,0 ,0 0)(* * * 退 出前 一 頁 后 一 頁 xxx xxx1 1 2 3 121 1 22 13 2 1 2 3 2( 1) 1 1 0 1 02( 2) 1 0 1 1( 2) 0( ) 0( ) 0, , 0 互 補 松 緊 條 件 退 出前 一 頁 后 一 頁 定 理 2 q

16、jxh pixgts xfji ,1 ,0)( ,1 ,0)( . )( min 對 于 處 連 續(xù) 可 微在、 *,1 xhgf ji 條 件 ，處 滿 足、 可 行 點 在 TKx *2 是 線 性 函 數(shù) ，是 凸 函 數(shù)、 ji hxIigf ,)(,3 * 問 題 的 整 體 最 優(yōu) 解是則 MPx*注 ： 定 理 2表 明 ， 在 凸 性 條 件 下 ， K-T點 是 整 體 最 優(yōu) 解 。 退 出前 一 頁 后 一 頁 例 ： 寫 出 K-T條 件 ;求 出 相 應(yīng) 的 K-T點 ;判 斷 K-T點 是 不 是問 題 的 最 優(yōu) 解 01)( 0)( 0)( 02)( . )2(

17、)1(),( min 211 23 12 211 222121 xxxh xxg xxg xxxgts xxxxf解 ： 由 于 全 部 函 數(shù) 都 是 連 續(xù) 可 微 的 ， 所 以 應(yīng) 用 以 下 K-T條 件 Ii Iixg xhxgxfi ii Ii Jj jjii,0 ,0 0)(* * * 退 出前 一 頁 后 一 頁 0, 00 0)2( 0)2(2 0)1(2 321 23 12 211 1312 1211 xx xxxx首 先 寫 出 原 MP問 題 的 K-T條 件 ：根 據(jù) 定 理 1,K-T點 還 應(yīng) 該 滿 足 原 問 題 的 約 束 條 件 01 0,0 0221

18、21 21 xx xx xx 互 補 松 緊 條 件 退 出前 一 頁 后 一 頁 利 用 互 補 松 緊 條 件 ， 可 以 求 出 K-T點 ：Tx )23,21(*利 用 定 理 2， 由 于 全 部 函 數(shù) 都 連 續(xù) 可 微 ， 并 且 f和 g都 是 凸 函 數(shù) ， h是 線 性 函 數(shù) ， 所 以 K-T點 就 是 整 體 最優(yōu) 解 。 退 出前 一 頁 后 一 頁 2.懲 罰 函 數(shù) 法懲 罰 函 數(shù) 法 的 基 本 思 想 ： 利 用 原 問 題 的 中 的 約束 函 數(shù) 構(gòu) 造 適 當(dāng) 的 懲 罰 函 數(shù) ， 并 和 原 問 題 的 目 標(biāo)函 數(shù) 相 加 ， 得 到 帶 參

19、 數(shù) 的 增 廣 目 標(biāo) 函 數(shù) ， 從 而 將原 問 題 題 轉(zhuǎn) 換 為 一 系 列 無 約 束 非 線 性 規(guī) 劃 問 題 。懲 罰 函 數(shù) 法 的 分 類 ： 罰 函 數(shù) 法 （ 外 部 懲 罰 法 ） ，障 礙 函 數(shù) 法 （ 內(nèi) 部 懲 罰 法 ） 退 出前 一 頁 后 一 頁 (1) 罰 函 數(shù) 法罰 函 數(shù) 法 基 本 原 理 ： Jjxh IixgRxX iin ,0)( ,0)( Jjxh Iixgts xfji ,0)( ,0)( . )( min考 慮 ：構(gòu) 造 懲 罰 函 數(shù) ： Xxc Xxxp , ,0)( 很 大 的 正 數(shù)無 約 束 最 優(yōu) 化 問 題 min

20、F(x)=f(x)+p(x)的 最 優(yōu) 解 必 定是 原 問 題 的 最 優(yōu) 解 。 退 出前 一 頁 后 一 頁 可 選 的 懲 罰 函 數(shù) ： qj jpi ic xhcxgcxp 1 21 2 )(2)0),(max()(懲 罰 函 數(shù) 法 的 經(jīng) 濟 解 釋 ：f(x)為 產(chǎn) 品 成 本 ， 約 束 條 件 為 產(chǎn) 品 質(zhì) 量 約 束 ；如 果 違 反 質(zhì) 量 約 束 ， 就 給 予 一 定 的 懲 罰 p(x)；追 求 的 目 標(biāo) 就 是 成 本 f(x)和 懲 罰 量 p(x)的 總 和 最 ?。?即 構(gòu) 造 的 無 約 束 最 優(yōu) 化 問 題 ） ；如 果 懲 罰 條 件 很 苛

21、 刻 ， 最 好 的 結(jié) 果 就 是 不 違 反 質(zhì) 量約 束 （ 無 約 束 最 優(yōu) 化 問 題 的 最 優(yōu) 解 為 MP的 最 優(yōu) 解 ） 退 出前 一 頁 后 一 頁 (2) 障 礙 函 數(shù) 法障 礙 函 數(shù) 法 基 本 原 理 ：構(gòu) 造 一 個 新 的 目 標(biāo) 函 數(shù) ， 它 在 可 行 區(qū) 域 的 邊 界 筑起 一 道 墻 ；當(dāng) 迭 代 點 靠 近 邊 界 時 ， 新 的 目 標(biāo) 函 數(shù) 迅 速 增 加 ；迭 代 點 被 檔 在 可 行 區(qū) 域 的 內(nèi) 部 ；迭 代 得 到 的 點 列 就 只 可 能 在 可 行 區(qū) 域 的 內(nèi) 部 。 退 出前 一 頁 后 一 頁 可 選 的 懲

22、罰 函 數(shù) ： IixgRxX in ,0)(| Iixgts xfi ,0)( . )( min考 慮 ：構(gòu) 造 最 優(yōu) 化 問 題 ： 0,)(1)()(min 1 kpi ik dxgdxfxF或 ： pi kik dxgdxfxF 1 0),(ln)()(min當(dāng) x靠 近 邊 界 時 ， 至 少 有 一 個 gi(x)趨 近 于 零 ， 則 F(x)將無 限 增 大 ， 從 而 使 得 迭 代 點 保 持 在 可 行 區(qū) 域 的 內(nèi) 部 。 退 出前 一 頁 后 一 頁 應(yīng) 用 實 例 ： 供 應(yīng) 與 選 址 某 公 司 有 6個 建 筑 工 地 要 開 工 ， 每 個 工 地 的

23、位 置 （ 用 平 面 坐 標(biāo) 系a， b表 示 ， 距 離 單 位 ： 千 米 ） 及 水 泥 日 用 量 d(噸 )由 下 表 給 出 。 目前 有 兩 個 臨 時 料 場 位 于 A(5,1)， B(2,7)， 日 儲 量 各 有 20噸 。 假 設(shè) 從料 場 到 工 地 之 間 均 有 直 線 道 路 相 連 。 （ 1） 試 制 定 每 天 的 供 應(yīng) 計 劃 ， 即 從 A， B兩 料 場 分 別 向 各 工 地 運送 多 少 噸 水 泥 ， 使 總 的 噸 千 米 數(shù) 最 小 。 （ 2） 為 了 進 一 步 減 少 噸 千 米 數(shù) ， 打 算 舍 棄 兩 個 臨 時 料 場 ，

24、 改 建 兩個 新 的 ， 日 儲 量 各 為 20噸 ， 問 應(yīng) 建 在 何 處 ， 節(jié) 省 的 噸 千 米 數(shù) 有 多 大 ？ 工 地 位 置 （ a， b） 及 水 泥 日 用 量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7 6 11 （ 一 ） 、 建 立 模 型 記 工 地 的 位 置 為 (ai， bi)， 水 泥 日 用 量 為 di， i=1,6;料 場 位 置 為(xj， yj)， 日 儲 量 為 ej， j=1,2； 從 料 場 j向 工 地 i的 運 送 量

25、 為 Xij。 目 標(biāo) 函 數(shù) 為 ： 21 61 22 )()(min j i ijijij byaxXf 約 束 條 件 為 ： 2,1 , 6,2,1 ,6121 jeX idX ji ij ij ij 當(dāng) 用 臨 時 料 場 時 決 策 變 量 為 ： Xij，當(dāng) 不 用 臨 時 料 場 時 決 策 變 量 為 ： Xij， xj， yj。 （ 二 ） 使 用 臨 時 料 場 的 情 形 使 用 兩 個 臨 時 料 場 A(5,1)， B(2,7).求 從 料 場 j向 工 地 i的 運 送 量為 Xij， 在 各 工 地 用 量 必 須 滿 足 和 各 料 場 運 送 量 不 超 過

26、 日 儲 量 的條 件 下 ， 使 總 的 噸 千 米 數(shù) 最 小 ， 這 是 線 性 規(guī) 劃 問 題 . 線 性 規(guī) 劃 模型 為 ： 21 61 ),(min j i ijXjiaaf 2,1 , 6,2,1 , s.t. 6121 jeX idX ji ij ij ij 其 中 22 )()(),( ijij byaxjiaa ， i=1,2,6,j=1,2,為 常 數(shù) 。 設(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

27、, X62= X 12 編 寫 程 序 gying1.m MATLAB（ gying1） cleara=1.25 8.75 0.5 5.75 3 7.25;b=1.25 0.75 4.75 5 6.5 7.75;d=3 5 4 7 6 11;x=5 2;y=1 7;e=20 20;for i=1:6 for j=1:2 aa(i,j)=sqrt(x(j)-a(i)2+(y(j)-b(i)2); endend CC=aa(:,1); aa(:,2);A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1;B=20;20;Aeq=1 0 0 0 0 0

28、1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 ;beq=d(1);d(2);d(3);d(4);d(5);d(6);VLB=0 0 0 0 0 0 0 0 0 0 0 0;VUB=;x0=1 2 3 0 1 0 0 1 0 1 0 1;xx,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0) 計 算 結(jié) 果 為 ：x = 3.0000 5.0000 0

29、.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval = 136.2275 即 由 料 場 A、 B向 6個 工 地 運 料 方 案 為 ： 1 2 3 4 5 6 料 場 A 3 5 0 7 0 1 料 場 B 0 0 4 0 6 10 總 的 噸 千 米 數(shù) 為 136.2275。 （ 三 ） 改 建 兩 個 新 料 場 的 情 形 改 建 兩 個 新 料 場 ， 要 同 時 確 定 料 場 的 位 置 (xj,yj)和 運 送 量Xij， 在 同 樣 條 件 下 使 總 噸 千 米 數(shù) 最 小

30、。 這 是 非 線 性 規(guī) 劃 問 題 。非 線 性 規(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文 件 liaoch.m定 義 目 標(biāo) 函 數(shù) 。 MATLAB（ liaoch）function f=liaoch(x)a=1.25 8.75 0.5 5.75 3 7.25;b=1.25 0

31、.75 4.75 5 6.5 7.75;d=3 5 4 7 6 11;e=20 20;f1=0;for i=1:6 s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2); f1=s(i)*x(i)+f1; endf2=0;for i=7:12 s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2); f2=s(i)*x(i)+f2;endf=f1+f2; (2) 取 初 值 為 線 性 規(guī) 劃 的 計 算 結(jié) 果 及 臨 時 料 場 的 坐 標(biāo) : x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編 寫 主 程 序 gying2

32、.m. MATLAB（ gying2）x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0;B=20;20;Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

33、 0 1 0 0 0 0 0 1 0 0 0 0;beq=3 5 4 7 6 11; vlb=zeros(12,1);-inf;-inf;-inf;-inf;vub=;x,fval,exitflag=fmincon(liaoch,x0,A,B,Aeq,beq,vlb,vub) (3) 計 算 結(jié) 果 為 ：x =3,4.9994,4,7,1.0006,0,0,0.0006,0,0,4.9994,11,5.6774,4.9055 7.2499,7.7500fval = 89.8851exitflag = 1 (4) 若 修 改 主 程 序 gying2.m, 取 初 值 為 上 面 的 計 算

34、結(jié) 果 :x0=3,4.9994,4,7,1.0006,0,0,0.0006,0,0,4.9994,11,5.6774, 4.9055,7.2499,7.7500得 結(jié) 果 為 :x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6958 4.9283 7.2500 7.7500fval =89.8835exitflag = 1總 的 噸 千 米 數(shù) 比 上 面 結(jié) 果 略 優(yōu) . MATLAB（ gying2） (5) 若 取 初 值 為 上 面 的 計 算 結(jié) 果 : x0=3.0000 5.0000 4.000

35、0 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6958 4.9283 7.2500 7.7500 則 計 算 結(jié) 果 為 :x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6958 4.9283 7.2500 7.7500fval =89.8835exitflag = 0總 的 噸 千 米 數(shù) 89.8835與 上 面 結(jié) 果 一 樣 . 第六章 錐規(guī)劃錐規(guī)劃是線性空間中凸錐上的數(shù)學(xué)規(guī)劃，它是線性規(guī)劃與非線性規(guī)劃的推廣。自20世紀(jì)90年代中期開始，它一直是國際優(yōu)化領(lǐng)域的研究熱

36、點。相關(guān)的研究帶動了數(shù)學(xué)規(guī)劃學(xué)科的深入發(fā)展，促進代數(shù)、群論、拓撲學(xué)、幾何學(xué)、非線性分析等分支在數(shù)學(xué)規(guī)劃中的融合，及優(yōu)化理論與技術(shù)在工程、交通、經(jīng)濟與金融、管理等領(lǐng)域的廣泛應(yīng)用。 研究成果主要包括以下四個方面 (1)二階錐優(yōu)化和半定優(yōu)化。 (2)對稱錐優(yōu)化。 (3)齊次錐優(yōu)化 (4)雙曲錐優(yōu)化。 一、二階錐優(yōu)化和半定優(yōu)化二階錐規(guī)劃： 約束條件是二階錐的凸優(yōu)化 半定規(guī)劃： 半定規(guī)劃是指線性函數(shù)在對稱矩陣的仿射組合半正定的約束下的極小問題,它實際上是凸優(yōu)化問題 線性二階錐優(yōu)化和半定優(yōu)化已經(jīng)得到了很好的發(fā)展，并且廣泛地應(yīng)用于各種實際問題。近些年，人們開始致力于非線性二階錐優(yōu)化和非線性半定優(yōu)化的理論與算

37、法的研究. 1.二階錐規(guī)劃 二階錐規(guī)劃是在有限個二階錐的笛卡兒乘積與仿射子空間的交集上求一個線性目標(biāo)函數(shù)的最小值問題。二階錐規(guī)劃是錐規(guī)劃的一個分支，它既是線性規(guī)劃的推廣，又是半定規(guī)劃的特例，是一種具有優(yōu)美結(jié)構(gòu)的對稱錐規(guī)劃。這類規(guī)劃應(yīng)用廣泛，比如在設(shè)施選址、圖論控制優(yōu)化、天線陣列設(shè)計、投資組合問題等方面以及金融、工程設(shè)計、數(shù)字信號處理、聲學(xué)、力學(xué)、民航、電氣等領(lǐng)域都有所應(yīng)用。因此，研究二階錐規(guī)劃問題的理論和算法具有重要的理論意義和應(yīng)用價值。 二階錐規(guī)劃問題的研究起源于17世紀(jì)，但直至最近十幾年才進入活躍階段，2003年有了對其理論和算法研究的階段性綜述文章，對二階錐規(guī)劃的算法研究主要分為內(nèi)點法和

38、非內(nèi)點法兩大類。原始-對偶內(nèi)點法是一類重要的內(nèi)點法，包含“可行內(nèi)點法”和“不可行內(nèi)點法”兩種，前者的初始點和迭代點均要求可行，后者的初始點和迭代點只需滿足二階錐約束，可行內(nèi)點法主要有原始-對偶路徑跟蹤算法，基于核函數(shù)的原始-對偶內(nèi)點算法等。不可行內(nèi)點法常見的有不可行內(nèi)點預(yù)估-校正算法，非精確不可行內(nèi)點算法等。非內(nèi)點法主要有光滑牛頓法，非內(nèi)點（內(nèi)部）連續(xù)化方法，序列二次規(guī)劃法等。 二階錐規(guī)劃（SOCP）問題是在有限個二階錐的笛卡兒乘積與仿射子空間的交集上求一個線性目標(biāo)函數(shù)的最小值，其標(biāo)準(zhǔn)形式為（文1）: ,.,2,1, )1.1.1(.min 01 1 rIix bxAts xcini iri

39、iri iTi 是 二 階 錐 。 表 示其 中 ， |);(),.,( ,)(, 00)1(10 0 iiniiTniiiin nininminim xxRxxxxxx xIikxRARcRb iii iiii 二階錐規(guī)劃因其優(yōu)美的幾何結(jié)構(gòu)和廣泛的應(yīng)用性引起了人們濃厚的研究興趣，對二階錐規(guī)劃問題的討論由來已久，最早可追溯到17世紀(jì)。1634年，法國數(shù)學(xué)家費馬（Fermat P.D.）提出問題（文2）：對平面上任意給定的三個點，如何求出一個點，使得該點到這三點的距離之和為最小。這個問題后來被瑞士數(shù)學(xué)家斯坦納（Steiner J.）推廣到給定n個點的情形。之后，德國經(jīng)濟學(xué)家韋伯（Weber A.

40、）在1909年發(fā)表的工業(yè)區(qū)位理論（Theory of the Location of Industries）中提出工廠選址問題，可表達成：求一點B，使得 最小，其中， 表示固定地點， 這幾個問題都屬于求?？偤妥钚〉念愋?，可轉(zhuǎn)化為二階錐規(guī)劃問題求解。近十幾年來的應(yīng)用主要有：| BAa ii iA.0ia 設(shè)施選址（facility location）斯坦納樹（Steiner tree）問題圖論控制優(yōu)化（grasping force optimization） 魯棒陣列插值（robust array interpolation） 魯棒多級有價證券（robust multistage portfol

41、io）優(yōu)化無風(fēng)險約束的投資組合優(yōu)化（portfolio optimization with loss risk constraints）構(gòu)架（truss）設(shè)計天線陣列（antenna array）設(shè)計脈沖響應(yīng)濾子（impulse response filter）設(shè)計等工程設(shè)計問題 2. 半定規(guī)劃（半定優(yōu)化）半定規(guī)劃是指線性函數(shù)在對稱矩陣的仿射組合半正定的約束下的極小問題,可視為線性規(guī)劃(簡稱LP)的推廣.半定規(guī)劃與線性規(guī)劃有著緊密的聯(lián)系,但又有重大區(qū)別.對于半定規(guī)劃的研究,要追溯到20世紀(jì)40年代.從60年代開始,涌現(xiàn)了許多關(guān)于半定規(guī)劃的理論和最優(yōu)性條件的文章.1984年,Kar-markar

42、把內(nèi)點法引入到線性規(guī)劃,雖然其基本原理不是新的,但是其算法和隨后發(fā)展起來的內(nèi)點法在實踐中具有良好的表現(xiàn),且具有多項式時間復(fù)雜性,所以Karmarkar的文章在當(dāng)時具有巨大的沖擊力. 1988年,Nesterov和Nemirovsky獲得了一個重大突破,他們證明了解線性規(guī)劃的內(nèi)點法原則上可以推廣到一切凸優(yōu)化問題,其關(guān)鍵在于對具有自協(xié)調(diào)性質(zhì)的函數(shù)的認識.而半定規(guī)劃是一類重要的凸優(yōu)化問題,它具有易于計算的自協(xié)調(diào)障礙函數(shù),因而內(nèi)點法適用.1992年,Nesterov和Nemirovsky把內(nèi)點法推廣到半定規(guī)劃.自20世紀(jì)90年代初開始,人們對半定規(guī)劃的興趣逐漸增加.目前半定規(guī)劃已成為優(yōu)化方面最熱門的領(lǐng)

43、域.這一研究活動之所以被激發(fā)起來,是由于半定規(guī)劃在一些領(lǐng)域的新應(yīng)用的發(fā)現(xiàn)以及新的有效算法的產(chǎn)生 2.1 半定規(guī)劃(SDP)具 有 實 對 稱 矩 陣 F 的 二 次 型 = Tf z Fz， 如 果 對 任 何 非 零 向 量 z 都 有 0Tz Fz成 立 ， 且 具 有 非 零 向 量 0z， 使 得 0 0=0Tz Fz ， 則 稱 = Tf z Fz 為 半 正 定 二 次 型 ， 矩 陣F 稱 為 半 正 定 矩 陣 ， 簡 稱 半 定 矩 陣 ， 記 為 。給 定 1, , n ， 對 于 任 何 一 組 實 數(shù) 1, , nx x ， 表 達 式 1 1 n nx x 稱 為 1

44、, , n 的 一 個 線 性 組 合 ，F(xiàn) O設(shè) ( 0,1, , ) n niF i n R 為 實 對 稱 矩 陣 ， ( )F x 是 0 1, , , nF F F的 一 個 線 性 組 合 。則 稱 不 等 式 ( )F x O 為 線 性 對 稱 矩 陣 不 等 式 。求 一 組 變 量 1( , , )nX X簡 稱 半 定 規(guī) 劃 ， 記 為 SDP。有 可 能 受 限 于 線 性 不 等 式 ， 線 性 對 稱 矩 陣 不 等 式 ，的 最 小 （ 最 大 ） 的 一 類 問 題 稱 為 半 定 規(guī) 劃 問 題 ，其 一 般 標(biāo) 準(zhǔn) 形 式 為 ：半 定 約 束 的 線 性

45、 函 數(shù) 0minim ( 1, , ), np pize A Xsubject to A X b p m O X S 其 中 nS 是 n 階 全 體 實 對 稱 矩 陣 的 線 性 空 間 ， npA S 是 n 階 實 對 稱 矩 陣 ，( 1, , )pb p m 是 實 數(shù) ， nX S 是 n 階 對 稱 矩 陣 變 元 ，11 12 14 21 22 241 1 2( , , ) ( )(1 ) nn ij n n nnij ji X X XX X XX X X X SX X XX X R i j nX O X 是 一 個 半 定 矩 陣 1 1= n nP p ij iji j

46、A X A X ( 0,1 , )p m ， 0A X 稱 為 目 標(biāo) 函 數(shù) ， 1, ,p pA X b p m （ ） 稱 為 第 p 個 約 束 條 件 。 設(shè) 是 一 個 集 合 ， 若 F = 1, , p pF X X A X b p m O且則 F 為 半 定 規(guī) 劃 的 可 行 域 ， 也 稱 曲 面 體 。 若 X F ， 則 稱 X 為 可 行 解 。設(shè) * ,X F 若 *0 0min ,X FA X A X 則 稱 *X 為 最 優(yōu) 解 ， *0A X 為 最 優(yōu) 值 。例 3 11 12 22 11 12 2211 1211 1212 22 211 11 22 12

47、min 2 52X 3 710, 0.mize X X xsubject to X XX XX X OX XX X X X 即 或 簡 記 為 ： 1 211 12 021 221 212 213, 2, 7, 1 1 1, 1 52 1.5 2 0.5,1.5 1 0.5 0n m b bX XX AX XA AX X 例 3是 把 例 1中 的 非 負 約 束 變 成 半 定 約 束 ， 這 是 半 定 規(guī) 劃 與 線 性 規(guī) 劃 的 不 同 之 處 。 例 4 12 1312, 13 23 12 2313 231( , ) 1 1T Y YF Y Y Y Y y OY Y 為 凸 多 面

48、 體 如 下 圖 所 示 ： 例 5 22 11 22minim 11ize X Xsubject to OX 11 22 11 11 22= , 0 1TF X X X X X ，可 行 域 為上 述 問 題 在 可 行 域 上 取 不 到 最 小 值 ， 因 為 0是目 標(biāo) 函 數(shù) 的 下 界 ， 且 可 行 域 不 是 凸 多 面 體 ， 而為 曲 面 體 。 即 該 問 題 不 可 行 。 22X 11X022 22=X X 21 111=X X上 述 例 題 討 論 的 是 半 定 規(guī) 劃 的 可 行 性 問 題 。 2,2 線性規(guī)劃(LP)與半定規(guī)劃(SDP)的對比0minim 1

49、, , , 0 np pize a xsubject to a x b p m x R （ ）LP:SDP: 0minim ( 1, , ), np pize A Xsubject to A X b p m O X S 線 性 目 標(biāo) ， 線 性 約 束 ， 向 量 變 元 且 為 非 負 實 向 量線 性 目 標(biāo) ， 線 性 約 束 ， 對 稱 矩 陣 變 元 且 為 半 定 實 矩 陣SDP可 視 為 LP的 推 廣 ， LP的 向 量 分 量 不 等 式 被 矩 陣 不 等 式 代 替 。 根 據(jù) 半 定 矩 陣 的定 義 知 ， SDP也 可 視 為 一 個 線 性 約 束 的 關(guān) 于

50、 變 量 的 無 限 集 的 LP， 解 LP的 原 始 -對 偶 內(nèi) 點 法 可 以 推 廣 到 SDP。根 據(jù) 前 面 兩 個 的 圖 形 ， LP的 可 行 域 為 有 有 限 個 頂 點 的 凸 多 面 體 ， 故 LP有 簡 單 易 行且 高 效 的 單 純 形 法 ； 而 SDP的 可 行 域 為 一 個 曲 面 體 ， 故 SDP尚 無 直 接 的 ， 適 用 的單 純 形 法 。 例 6 11 12 2211 12 2211 1211 12 22min 2 52 3 7=10 0 0.mize x x xsubject to x x xx xx x x ， ，線 性 規(guī) 劃 ：

51、轉(zhuǎn) 化 為 半 定 規(guī) 劃 ： 0minim ( 1,2), np pize A Xsubject to A X b p O X S 11 12 022 1 2 1 20 0 1 0 00 0 , 0 2 00 0 0 0 52 0 0 1 0 00 3 0 , 0 1 0 7, 10 0 1 0 0 0 xX x AxA A b b ， 2.3 連續(xù)性最優(yōu)化問題的分類 非 線 性 規(guī) 劃 是 具 有 非 線 性 約 束 條 件 或 目 標(biāo) 函 數(shù) 的 數(shù) 學(xué) 規(guī) 劃 。 凸 規(guī) 劃 是 指 約 束 集 為 凸 的 和 目 標(biāo) 函 數(shù) 為 約 束 集 上 凸 函 數(shù) 的 數(shù) 學(xué) 規(guī) 劃 。 2

52、.4 為 什 么 凸 在 最 優(yōu) 化 中 重 要 的一 個 凸 函 數(shù) 沒 有 不 為 全 局 極 小 的 局 部 極 小 值一 個 非 凸 函 數(shù) 可 以 被 “ 凸 化 的 ” 同 時 保 持 全 局 極 小 值 的 最 優(yōu) 性一 個 凸 集 有 非 空 的 相 對 內(nèi) 部一 個 凸 集 在 任 何 點 具 有 可 行 方 向 凸 函 數(shù) 的 極 小 值 的 存 在 可 以 非 常 方 便 地 用 收 縮 方 向 進 行 刻 畫一 個 多 面 體 凸 集 可 用 它 的 極 值 點 和 極 值 方 向 來 刻 畫 二、對稱錐優(yōu)化 20世紀(jì)末國際優(yōu)化專家開始致力于這一領(lǐng)域的研究工作，主要集中

53、在求解對稱錐上線性優(yōu)化問題的內(nèi)點算法方面。近幾年，人們開始探討對稱錐上的非線性優(yōu)化問題和非凸優(yōu)化問題的理論與各種算法。 三、 齊次錐優(yōu)化齊次錐的理論早在1963年就有相關(guān)研究，但齊次錐優(yōu)化間題的研究最近才開始。 四、 雙曲錐優(yōu)化這方面目前只有很少的理論研究，需要尋求合適的工具開展其理論與算法的研究。 相關(guān)博士碩士論文 內(nèi)容相關(guān) 題目相關(guān) 錐規(guī)劃 371篇 14 錐優(yōu)化 160篇 4 半定規(guī)劃 389篇 63對稱錐優(yōu)化 58篇 14齊次錐優(yōu)化 18篇 1雙曲錐優(yōu)化 6篇 0 第七章 矩陣規(guī)劃 在眾多的科學(xué)領(lǐng)域與社會經(jīng)濟中，很多優(yōu)化問題的決策變量是一個具有特殊結(jié)構(gòu)的矩陣，這樣的優(yōu)化間題被稱為矩陣優(yōu)

54、化或者矩陣規(guī)劃。矩陣規(guī)劃的早期研究可以追溯到1981年，然而真正的研究是在20世紀(jì)90年代，它以被譽為21世紀(jì)的線性規(guī)劃，以半定規(guī)劃為研究起點。 至今，線性半定規(guī)劃的理論趨于完善，人們正在發(fā)掘它在實際中的應(yīng)用。然而，目前的數(shù)值軟件只能有效地求解矩陣維數(shù)小于500的小規(guī)模線性半定規(guī)劃間題，因此，開展大規(guī)模半定規(guī)劃的數(shù)值方法研究是當(dāng)前一項十分迫切而又重要的課題。 此外，由著名華裔數(shù)學(xué)家陶哲軒等人在2006年提出的壓縮傳感理論而引發(fā)的低秩矩陣間題，其理論與算法研究是當(dāng)今優(yōu)化領(lǐng)域與信息科學(xué)領(lǐng)域(例如，信號處理、圖像恢復(fù)與重建)共同關(guān)心的熱點研究課題。在未來一段時期里，矩陣(錐)優(yōu)化理論與算法、張量(錐

55、)優(yōu)化理論與算法、多項式優(yōu)化理論與算法研究等方向必將引起人們的關(guān)注。 第八章 變分不等式與互補問題 變分不等式與互補問題是一類具有普遍意義的均衡優(yōu)化模型。它不僅為非線性優(yōu)化、極大極小、博弈論、非線性方程、微分方程等提供了一個統(tǒng)一的理論框架，而且在力學(xué)工程、交通、經(jīng)濟、管理等實際部門有廣泛的應(yīng)用。 互補問題首先由丹齊格和科特爾于1963年提出。次年，科特爾在他的博士論文中第一次提出求解它的非線性規(guī)劃算法。變分不等式問題首先被哈特曼和斯塔姆巴切在1966年提出。后來發(fā)現(xiàn)，變分不等式是互補問題的一個推廣，且其數(shù)學(xué)性質(zhì)和應(yīng)用有驚人的相似之處。所以，它們經(jīng)常在文獻中成對出現(xiàn)。 變分不等式與互補問題被提出

56、后，很快引起了當(dāng)時運籌學(xué)界和應(yīng)用數(shù)學(xué)界的廣泛關(guān)注和濃厚興趣，許多人參與了這類問題的研究。經(jīng)過40余年的探索，特別是20世紀(jì)最后10年的研究，人們在理論與算法方面取得了豐富、系統(tǒng)的成果，并在科技與經(jīng)濟中得到了廣泛的應(yīng)用。 當(dāng)前主要是對于廣義變分不等式和錐互補問題的研究，而對于不確定信息下變分不等式和互補問題的研究無疑是發(fā)展的必然。歸納起來，對它們的研究可分為理論與算法兩方面:前者主要研究解的存在性、唯一性、穩(wěn)定性與靈敏度分析、以及它們與其他數(shù)學(xué)問題的聯(lián)系等;后者則主要建立有效的求解方法及相應(yīng)的理論和數(shù)值分析。 變分不等式實際上是一種偏微分不等式組設(shè) 為H一實Hilbert空間，C 為一非空閉凸集，F(xiàn): CH 為一非線性算子，變分不等式問題的一般提法是：尋求 x* C，使得 0 x C 文獻關(guān)于變分不等式研究的文獻 1281篇關(guān)于變分不等式研究的博士碩士論文206篇 推薦變分不等式書籍變分不等式簡介：基本理論、數(shù)值分析及應(yīng)用韓渭敏高等教育出版社 第四講結(jié)束