非線性規劃 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 非線性規劃