土木計画学
第１２回（１月１４日）
計画における代替案の作成２
担当：榊原 弘之
本日の内容
計画における代替案の作成２
非線形計画問題(Nonlinear Programming)とその解法
・非線形計画問題
・キューン・タッカー条件
非線形計画問題
Objective Function
z (x)
Minimize（最小化）
Constraints 制約条件
g i ( x)  0
(i  1,..., m)
x  ( x1 , x2 ,..., xn )
（１）変数が一つの場合
( x  2) 2
最小化
a xb
a
2
内点解
b
制約条件
x
2 a
b
x
端点解
a b 2
x
目的関数が凸関数でない場合は？
局所的最適解
全域的（大域的）
最適解
x
局所的最適解の条件
2
dz
d z
 0,
0
2
dx
dx
（２）変数が2つ以上の場合（制約条件なし）
局所的最適解の条件
 z

 x1
z   :
 z
 x
 n



0



ヘシアン行列
ベクトル
かつ
y Hy  0
t
 2z

 x 2
 1
H  :
 2z

 xn x1

非負定値
2
 z 

x1xn 


: 
2z 


2
xn 


（３）変数が2つ以上の場合（制約条件あり）
x2
g ( x1 , x2 )  z ( x1 , x2 )
（λは適当な実数）
 g g 

g ( x1 , x2 )  
,
 x1 x2 
実行可能領域
 z z 

z ( x1 , x2 )  
,
 x1 x2 
g i ( x)  0
x1
x2
g i ( x)  0
 z z 
  0
z ( x1 , x2 )  
,
 x1 x2 
実行可能領域
x1
x2
g i ( x)  0
g ( x1 , x2 )  z ( x1 , x2 )
実行可能領域
 z z 

z ( x1 , x2 )  
,
 x1 x2 
 g g 

g ( x1 , x2 )  
,
 x1 x2 
x1
x2
g1 ( x1 , x2 )  (1   )g 2 ( x1 , x2 )  z( x1 , x2 )
 g1 g1 

g1 ( x1 , x2 )  
,
 x1 x2 
 g 2 g 2 

g 2 ( x1 , x2 )  
,
 x1 x2 
実行可能領域
 z z 

z ( x1 , x2 )  
,
 x1 x2 
g1 ( x)  0
g 2 ( x)  0
x1
非線形計画問題の解の条件はばらばら？
キューン・タッカー条件
最適解のための必要条件（一般に十分条件ではない）
z (x)
最小化
g i ( x)  0
(i  1,..., m)
 
m


g

z
i   0,
 xk 


i
  xk
xk 
i 1

 


i g i  0,


z

xk
gi  0
m

i 1
g i
i
 0, xk  0
xk
(k  1,..., n)
i  0
  z
g i

 i
 xk 
  xk
xk
  g  0,
i i


g i
z
  0,
 i
 0, xk  0

xk
xk

gi  0
i  0
g i
z
 i
0
i g i ( x1 , x2 )  z( x1 , x2 )
xk
xk
x2
 g g 

g ( x1 , x2 )  
,
 x1 x2 
 z z 

z ( x1 , x2 )  
,
 x1 x2 
g i ( x)  0
x1
  z
g i
 i
 xk 
  xk
xk
  g  0,
i i


g i
z
  0,
 i
 0, xk  0

xk
xk

gi  0
i  0
x2
g i ( x)  0
 z z 
  0
z ( x1 , x2 )  
,
 x1 x2 
x1
  z
g i

 i
 xk 
  xk
xk
  g  0,
i i


g i
z
  0,
 i
 0, xk  0

xk
xk

gi  0
i  0
x2
g ( x1 , x2 )  z ( x1 , x2 )
g i ( x)  0
 g g
g ( x1 , x2 )  
,
 x1 x2
 z z 

z ( x1 , x2 )  
,
x x
x1



 
m
m

g i 
g i
z
 x  z 
i
 0,

i
 0, xk  0
k

  xk
xk 
xk
xk
i 1
i 1

 

i gi  0,
gi  0
i  0


{ag1 ( x1 , x2 )  (1   )bg 2 ( x1 , x2 )}  z ( x1 , x2 )
x2
a  1 , (1   )b  2
 g g 
g1 ( x1 , x2 )   1 , 1 
 x1 x2 
 g g 
g 2 ( x1 , x2 )   2 , 2 
 x1 x2 
 z z 

z ( x1 , x2 )  
,
 x1 x2 
g1 ( x)  0
g ( x)  0
x1
ラグランジュ未定乗数法
ラグランジュ関数
L( x )  z ( x ) 
m
  g ( x)
i
i
i 1
キューン・タッカー条件は次のように書き換えられる．
L
L

 xk x  0, x  0, xk  0
k
k


(k  1,..., n)

L
L
 0,
 0 i  0
 i

i
i
例題
( x1  10)  ( x2  8)
2
2
最小化
x1  x2  5  0
L( x)  ( x1  10) 2  ( x2  8) 2   ( x1  x2  5)
 x12( x1  10)    0

 x2 2( x2  8)    0
  ( x1  x2  5)  0

2( x1  10)    0, x1  0

2( x2  8)    0, x2  0
 x1  x2  5  0,   0


包絡線の定理（Envelope Theorem） (1) （消費者の効用最大化の条件

フロントラインスタッフ名簿 1996．11．14

解答例（必須分）