非線性規劃 Nonlinear Programming

Slides:



Advertisements
Similar presentations
简单迭代法的概念与结论 简单迭代法又称逐次迭代法,基本思想是构造不动点 方程,以求得近似根。即由方程 f(x)=0 变换为 x=  (x), 然后建立迭代格式, 返回下一页 则称迭代格式 收敛, 否则称为发散 上一页.
Advertisements

手工加工全框眼镜技术 前调整确定加工基准制作模板割边 磨边磨安全角 (抛光) 装配 后调整检测.
Chap 3 微分的應用. 第三章 3.1 區間上的極值 3.2 Rolle 定理和均值定理 3.3 函數的遞增遞減以及一階導數的判定 3.4 凹面性和二階導數判定 3.5 無限遠處的極限 3.6 曲線繪圖概要 3.7 最佳化的問題 3.8 牛頓法 3.9 微分.
附加數學 / 純粹數學 Common Limits 常見極限. 附加數學 / 純粹數學 Derivatives of Functions 函數的導數.
Shan University 商用微積分 ( 一 ) 詹傑仲.
工職數學 第四冊 第一章 導 數 1 - 1 函數的極限與連續 1 - 2 導數及其基本性質 1 - 3 微分公式 1 - 4 高階導函數.
©2009 陳欣得 統計學 —e1 微積分基本概念 1 第 e 章 微積分基本概念 e.1 基本函數的性質 02 e.2 微分基本公式 08 e.3 積分基本公式 18 e.4 多重微分與多重積分 25 e.5 微積分在統計上的應用 32.
不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
大綱 1. 三角函數的導函數. 2. 反三角函數的導函數. 3. 對數函數的導函數. 4. 指數函數的導函數.
猜谜语 有个小娃娃,真是没 礼貌。 见到小树摇一摇,吓 得树叶哇哇叫。 见到小花逗一逗,摘 去她的太阳帽。 没人和它交朋友,只 好自已到外处跑。
2-1 極限的概念 2-2 無窮等比級數 2-3 多項式函數的導數導函數 2-4 微分公式 2-5 微分的應用 2-6 積分的概念與反導函數 信樺文化.
1.3 二项式定理. [ 题后感悟 ] 方法二较为简单,在展开二项式之前根据二项 式的结构特征进行适当变形,可使展开多项式的过程简化.记 准、记熟二项式 (a + b) n 的展开式,是解答好与二项式定理有关 问题的前提,对较复杂的二项式,有时可先化简再展开,会更 简便.
《公路纵断面设计》 —— 纵断面设计的要求 道桥系 二○○七年五月. 纵断面设计的一般要求 1 .纵坡设计必须满足《公路工程技术标准》中的各项规定。 2 .为保证汽车能以一定的车速安全舒顺地行驶,纵坡应具有 — 定 的平顺性,起伏不宜过大及过于频繁。尽量避免采用极限纵坡 值.缓和坡段应自然地配合地形设置,在连续采用极限长度的.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
黄帝内经 内经教研室 王黎.
专利技术交底书的撰写方法 ——公司知识产权讲座
個人理財規劃 第八章 投資規劃.
职官与科举 职官:在国家机构中担任一定职务的官吏,这里面有职官的名称、职权范围和品级地位等方面的内容。
保育员工作职责.
花开有日 芬芳天下 “国培计划(2012)” ——幼儿园骨干教师远程培训项目 山东幼儿园教师8班第4期简报 主办人:张瑞美     
《卖火柴的小女孩》 《海的女儿》 你 认 识 这 些 图 片 的 故 事 吗 《丑小鸭》 《拇指姑娘》 它们都来自于哪位作家笔下?
民主國家的政府體制 我國的中央政府體制 我國中央政府的功能 地方政府組織與功能
3-2 條件不等式 解一元 n 次不等式 二元一次不等式的圖解法 函數的極植.
銷售與顧客關係管理 巫立宇.邱志聖 著.
20、豆花庄的小家伙们.
CH11 心理疾病 李志鴻.
华 夏 之 祖 第 3 课.
法學緒論第六單元:法律適用 設計課程︰ 財經法律系 --楊東連 法學緒論-6.
四种命题 班级:C274 指导教师:钟志勤 任课教师:颜小娟.
CH1 . 集 合 与 命 题.
Ch19 創業精神 管理學:整合觀點與創新思維3/e.中山大學企管系 著.前程文化 出版.
以考试说明带动二轮复习 福州第三中学 张璐.
5.1 自然對數函數:微分 5.2 自然對數函數:積分 5.3 反函數 5.4 指數函數:微分與積分 5.5 一般底數的指數函數和應用 5.6 反三角函數:微分 5.7 反三角函數:積分 5.8 雙曲函數.
跨越海峡的生命桥.
LINGO.
Linear Programming: Introduction and Duality
Chapter 2 線性規劃.
Differentiation 微分 之一 微分的基本原理.
非線性規劃 Nonlinear Programming
本章大綱 9.1 Sequence數列 9.2 Infinite Series無窮級數
Chapter 17 投資決策經濟分析.
Differentiation 微分 之一 微分的基本原理.
偏導數的幾何意義 考慮一個由方程式 所決定的曲面。就如下面的圖3所顯示的,平面 與曲面相交於平面曲線 上,且這個值 就是這條曲線在點
第一章 直角坐標系 1-1 數系的發展.
網路遊戲版 幸福農場168號.
整數規劃 Integer Programming
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
第一章 直角坐標系 1-3 函數圖形.
15.3 極大與極小 附加例題 5 附加例題 6 © 文達出版 (香港 )有限公司.
Definition of Trace Function
CH1 我的第一個App與變數宣告.
微積分網路教學課程 應用統計學系 周 章.
圓的定義 在平面上,與一定點等距的所有點所形成的圖形稱為圓。定點稱為圓心,圓心至圓上任意一點的距離稱為半徑,「圓」指的是曲線部分的圖形,故圓心並不在圓上.
圖解配方法 張美玲老師製作.
第二章 三角函數 2-5 三角函數的圖形.
函數應用(二)與自定函數.
陣列與結構.
第十一單元 兩曲線圍出的面積.
( )下列何者正確? (A) 7< <8 (B) 72< <82 (C) 7< <8 (D) 72< <82 C 答 錯 對.
微積分 Chapter3 微分的應用 Good morning everyone. 國立高雄第一科技大學機械與自動化工程系.
第一章 直角坐標系 1-3 函數及其圖形.
補充 數值方法 數值方法.
線性規劃的其他演算法 Special Simplex Method
4-1 變數與函數 第4章 一次函數及其圖形.
天水圍循道衛理小學 建立家校合作的過程 一個信念 一些實踐 一點建議.
17.1 相關係數 判定係數:迴歸平方和除以總平方和 相關係數 判定係數:迴歸平方和除以總平方和.
ABC ( )已知 ,則下列哪些是x6-7x5-8x4 的因 式?(複選) (A) x+1 (B) 2x+2 (C) x3(x+1)
第三十單元 極大與極小.
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
Presentation transcript:

非線性規劃 Nonlinear Programming 第十二章 非線性規劃 Nonlinear Programming 作業研究 二版 2009 © 廖慶榮

章節大綱 前言 非線性規劃的應用 極大值與極小值 凸函數與凹函數 非線性規劃的類別 單變數無限制式最佳化 多變數無限制式最佳化 限制式最佳化的KKT條件 作業研究 二版 Ch.12 非線性規劃

12.1 前言 作業研究 二版 Ch.12 非線性規劃

12.2 非線性規劃的應用 範例12.1 銷售量與單位售價、單位成本的關係 銷售量與利潤的關係 作業研究 二版 Ch.12 非線性規劃

範例12.3 /變動人力問題 問題 NLP模式: 每輛貨車由1位司機和1~3位搬運工組成搬運小組 每小組每年賺 100+55(y-1) 萬元(y=搬運工人數) 公司每年支付每位司機70萬元、每位搬運工50萬元,公司每年有800萬的人力費用預算 該搬家公司應聘僱幾位司機以及幾位搬運工,才能獲得最大的利潤? NLP模式: 作業研究 二版 Ch.12 非線性規劃

範例12.4 /倉儲中心位置問題 問題 NLP模式: 倉儲中心應設在何處(x-y座標),才能使由倉儲中心至各分店的總來回距離最短? 作業研究 二版 Ch.12 非線性規劃

範例12.5 /投資組合問題 問題:(1)股票9.8%、(2)債券4.6%、(3)基金5.3% NLP模式: 公司希望在達到每年6.0%的預期收益情況下,盡可能降低投資組合的風險,其風險衡量如下: NLP模式: 作業研究 二版 Ch.12 非線性規劃

12.3 極大值與極小值 /單變數 作業研究 二版 Ch.12 非線性規劃

12.3 極大值與極小值 /單變數 作業研究 二版 Ch.12 非線性規劃

範例12.6 考慮以下函數: 作業研究 二版 Ch.12 非線性規劃

局部極值與全域極值 局部極小值(極大值)與全域極小值(極大值) 作業研究 二版 Ch.12 非線性規劃

多變數 作業研究 二版 Ch.12 非線性規劃

多變數 判斷關鍵點是極小值、極大值或鞍點 利用該點的赫斯矩陣(Hessian matrix): 此為對稱的(symmetric)矩陣 作業研究 二版 Ch.12 非線性規劃

赫斯矩陣定性的判斷方式 作業研究 二版 Ch.12 非線性規劃

判斷多變數的關鍵點 作業研究 二版 Ch.12 非線性規劃

範例12.7 /以赫斯矩陣判斷關鍵點 考慮以下函數: 作業研究 二版 Ch.12 非線性規劃

12.4 凸函數與凹函數 作業研究 二版 Ch.12 非線性規劃

凸函數與凹函數的圖形 嚴格凸的 嚴格凹的 作業研究 二版 Ch.12 非線性規劃

凸函數與凹函數的圖形 凸的 凹的 作業研究 二版 Ch.12 非線性規劃

凸函數與凹函數的圖形 非凸非凹的 若 f 是凸的,則 –f 是凹的 作業研究 二版 Ch.12 非線性規劃

判斷凸函數與凹函數 /單變數 作業研究 二版 Ch.12 非線性規劃

判斷凸函數與凹函數 /多變數 作業研究 二版 Ch.12 非線性規劃

範例12.8 /單變數 作業研究 二版 Ch.12 非線性規劃

範例12.9 /多變數 作業研究 二版 Ch.12 非線性規劃

12.5 非線性規劃的類別 無限制式NLP 線性限制式NLP 二次規劃(quadratic programming) 12.5 非線性規劃的類別 無限制式NLP 僅有目標函數,而無任何限制式 線性限制式NLP 所有限制式都是線性的 二次規劃(quadratic programming) 線性限制式NLP的特例,當f(x)僅能是線性或二次 凸規劃(convex programming) 對min問題,f(x)是凸的;對max問題,f(x)是凹的 對於≦限制式,g(x)是凸的;對於≧限制式,g(x)是凹的;對於=限制式,g(x)是線性的 作業研究 二版 Ch.12 非線性規劃

12.5 非線性規劃的類別 非凸規劃(nonconvex programming) 可分離規劃(separable programming) 12.5 非線性規劃的類別 非凸規劃(nonconvex programming) 不是凸規劃的所有其他NLP 可分離規劃(separable programming) 當f(x)及所有g(x)均為可分離函數 可分離函數 幾何規劃(geometric programming) 若f(x)及所有g(x)均為正多項式,且為min問題 正多項式(posynomial): 分數規劃(fractional programming) f(x)呈分數的形式 作業研究 二版 Ch.12 非線性規劃

12.6 單變數無限制式最佳化 求解方法 一維搜尋法 若f (x) 是一個簡單的函數,則可用11.3節的導數方式求得最佳解 12.6 單變數無限制式最佳化 求解方法 若f (x) 是一個簡單的函數,則可用11.3節的導數方式求得最佳解 若f (x) 較為複雜而無法用導數求解時,須使用一維搜尋法(one dimensional search method)。 一維搜尋法 二分搜尋法 黃金搜尋法 平分搜尋法 若 f (x) 是凸函數,則一維搜尋法所找到的解即為全域極小值,否則所找的解僅是局部極小值 作業研究 二版 Ch.12 非線性規劃

二分搜尋法 二分搜尋法(dichotomous search method) 步驟(對min問題) 作法:將包含最佳解的不確定區間分割為兩部分,然後捨棄較差的部分並繼續分割保留的部分,直到不確定區間達到所指定的容許範 步驟(對min問題) 作業研究 二版 Ch.12 非線性規劃

二分搜尋法的圖示 作業研究 二版 Ch.12 非線性規劃

範例12.10 /二分搜尋法的應用 考慮無限制式NLP: 選擇 、 作業研究 二版 Ch.12 非線性規劃

黃金分割法 黃金分割法(golden section method) 基本概念:如圖所示 作業研究 二版 Ch.12 非線性規劃

黃金分割法 作業研究 二版 Ch.12 非線性規劃

黃金分割法 作業研究 二版 Ch.12 非線性規劃

範例12.11 /黃金分割法的應用 考慮以下 NLP: 設定 作業研究 二版 Ch.12 非線性規劃

平分搜尋法 平分搜尋法(bisection search method) 基本概念 作法 若一個可微分的(differentiable)函數 f(x) 是凸函數或凹函數,則最佳解的必要且充分條件為: 作法 藉由判斷不確定區間中間點(midpoint)之導數的正負號,來決定捨棄左半部或右半部,直到不確定區間達到所選擇的容許範圍為止 作業研究 二版 Ch.12 非線性規劃

平分搜尋法 步驟(f(x) 是可微分的凸函數;對min問題): 作業研究 二版 Ch.12 非線性規劃

範例12.12 /平分搜尋法的應用 考慮以下無限制式的NLP: 作業研究 二版 Ch.12 非線性規劃

12.7 多變數無限制式最佳化 最陡峭遞降法(steepest descent method): 基本概念 12.7 多變數無限制式最佳化 最陡峭遞降法(steepest descent method): 屬斜率搜尋法(gradient search method) 基本概念 沿著能減少 f(x) 值最快的方向移動 因為斜率向量 是指向該函數值增加最快的方向,所以沿著斜率向量的反方向 移動 至於要移動多少,則是一個單變數無限制式最佳化的問題 作業研究 二版 Ch.12 非線性規劃

最陡峭遞降法 作業研究 二版 Ch.12 非線性規劃

範例12.13 /最陡峭遞降法的應用 考慮多變數NLP: 其斜率向量: 選擇 作業研究 二版 Ch.12 非線性規劃

12.8 限制式最佳化的KKT條件 KKT條件(KKT condition) 標準形式: 限制式NLP之最佳解的必要條件 亦為凸規劃最佳解的充分條件 標準形式: 定理12.7:對於標準形式, 為最佳解的必要條件: 存在 使得 作業研究 二版 Ch.12 非線性規劃

範例12.14 /以KKT條件求解最佳解 考慮以下NLP: 轉換為標準形式如下: 作業研究 二版 Ch.12 非線性規劃

範例12.14 此NLP的KKT條件如下: 作業研究 二版 Ch.12 非線性規劃

範例12.14 作業研究 二版 Ch.12 非線性規劃