第十二章
非線性規劃 Nonlinear Programming
作業研究 二版 2009
© 廖慶榮
章節大綱
1. 2. 3. 4. 5. 6. 7. 8. 前言 非線性規劃的應用 極大值與極小值 凸函數與凹函數 非線性規劃的類別 單變數無限制式最佳化 多變數無限制式最佳化 限制式最佳化的KKT條件
p.2/44
2 2
2
f (x) x 2 x1
f (x) x n x1
2
f (x) xnx2
2
f (x) x1 x n 2 f (x) x2xn 2 f (x) 2 xn
2
此為對稱的（symmetric）矩陣
p.12/44
作業研究 二版 Ch.12 非線性規劃
多變數
判斷關鍵點是極小值、極大值或鞍點
利用該點的赫斯矩陣（Hessian matrix）：
H (x) f (x) x1
2 2 2
f (x) x1 x 2 f (x) x2
定理 12.2：讓 x 是函數
d
2
f (x)
的關鍵點。若
f (x )
2
dx
0
則 x 是極小點。若
d
2
f (x )
2
dx
0
則 x 是極大點 若 d 2 f ( x ) / dx 2 點或鞍點。
0
，則無法判斷 x 是極小點、極大
p.9/44
作業研究 二版 Ch.12 非線性規劃
範例12.6
3 3

i 1 j 1
σ ij x i x
j
xV x (x 1 x
2
4 0 .2 x 3 ) 3 .8 8 .6
2
3 .8 1 .2 6 .8
8 .6 6 .8 ( x 1 x 1 6 .5
2
x 3)
NLP模式： M in
s .t .
f ( x ) 4 0 .2 x 1 2 3 .8 x 1 x
p.3/44
作業研究 二版 Ch.12 非線性規劃
12.2 非線性規劃的應用
範例12.1
a) 銷售量與單位售價、單位成本的關係 b) 銷售量與利潤的關係
p( x)
c(x)
利 潤 ( p ( x ) c ( x )) x
x (a )
(b )
x
p.4/44
作業研究 二版 Ch.12 非線性規劃
p.13/44
作業研究 二版 Ch.12 非線性規劃
NLP模式：
M a x Z 45 x 55 xy s .t. 7 0 x 5 0 y 8 0 0 x, y 0
p.5/44
作業研究 二版 Ch.12 非線性規劃
範例12.4
問題
/倉儲中心位置問題
分店
i
倉儲中心應設在何處 （x-y座標），才能使 由倉儲中心至各分店 的總來回距離最短？
範例12.3
問題
/變動人力問題
每輛貨車由1位司機和1~3位搬運工組成搬運小組 每小組每年賺 100+55(y-1) 萬元（y=搬運工人數） 公司每年支付每位司機70萬元、每位搬運工50萬元， 公司每年有800萬的人力費用預算 該搬家公司應聘僱幾位司機以及幾位搬運工，才能 獲得最大的利潤？
f (x)
x1
x2
x3
x4
x5
x
p.11/44
作業研究 二版 Ch.12 非線性規劃
多變數
定理 12.3： x 是函數 率向量 f
(x) f (x)
的關鍵點，若且唯若其斜
為零，即
f (x) x1 f (x) x2 f (x) 0 f (x) xn
考慮以下函數：
f (x) 2 x 3x 1
2
其關鍵點 x 可計算如下：
df (x) dx 4x 3 x 3 4
因
d
2
f (x )
2
dx
4 0
所以 x
3/4
是極小點（或稱極小值）
p.10/44
作業研究 二版 Ch.12 非線性規劃
局部極值與全域極值
局部極小值（極大值）與全域極小值（極大值）
2 2 2
= = =
2
2
3
4
(x - 7) + (y - 2)
2
x , y 吵 0, d i
作業研究 二版 Ch.12 非線性規劃
0 , i = 1, 2 , 3 , 4
p.6/44
範例12.5
/投資組合問題

問題：(1)股票9.8%、(2)債券4.6%、(3)基金5.3%
公司希望在達到每年6.0%的預期收益情況下，盡可 能降低投資組合的風險，其風險衡量如下：
1 2 3 4
2
每月平均 -y 座標 運貨次數 (0, 5) 35 ( 1, 3) 24 (1, 6) 18 (7, 2) 29
x
3
NLP模式:
M in s .t .
Z = 3 5d 1 + 2 4d d1 = d d d
2 2
+ 1 8d
+ 2 9d
2
4
( x - 0) + (y - 5) ( x + 1) + ( y - 3 ) ( x - 1) + ( y - 6 )
作業研究 二版 Ch.12 非線性規劃
12.3 極大值與極小值 /單變數
定理 12.1： x 是函數
dx
f (x)
的關鍵點，若且唯若
df (x )
0

關鍵點：極小點、極大點或鞍點（ saddle point）
p.8/44
作業研究 二版 Ch.12 非線性規劃
12.3 極大值與極小值 /單變數
作業研究 二版 Ch.12 非線性規劃
12.1 前言
非線性規劃（nonlinear programming；NLP）數學 模式： 極小化 f ( x ) 受限於 g i ( x ) 0 i 1, 2 , , m 其中
f (x)
與所有 g i ( x ) 至少有一個函數是非線性的
（nonlinear） 。 電腦軟體：LINGO，可由網站（） 免費下載
1 .2 x ( 9 .8 x 1 4 .6 x
2 2 2
2
2 8 .6 x 1 x
3
3 2 3
2 6 .8 x 2 x
1 6 .5 x
5 .3 x 3 ) / 5 0 0 0 6 .0
2
x1 x
x
3 3
5000 0
p.7/44
x 1, x 2, x