Vol.79 MI Lecture Notes|九州大学 マス・フォア・インダストリ研究所 math 5acd67e59a821

M

ISSN2188−1200

著者 :

神山直之・畔上秀幸

九州大学マス・フォア・インダストリ研究所

九州大学マス・フォア・インダストリ研究所

九州大学大学院 数理学府

著

者 _:

神

山

直

之

・

畔

上

秀

幸

最適化理論の基礎と応用

平成29年度 AIMaPチュートリアル

最

適

化

理

論

の

基

礎

と

応

平成

29

年度　

AIMaP

チュートリアル

最適化理論の基礎と応用

About MI Lecture Note Series

The Math-for-Industry (MI) Lecture Note Series is the successor to the COE Lecture

Notes, which were published for the 21st COE Program “Development of Dynamic

Mathematics with High Functionality,” sponsored by Japan’s Ministry of Education,

Culture, Sports, Science and Technology (MEXT) from 2003 to 2007. The MI

Lec-ture Note Series has published the notes of lecLec-tures organized under the following two

programs: “Training Program for Ph.D. and New Master’s Degree in Mathematics as

Required by Industry,” adopted as a Support Program for Improving Graduate School

Education by MEXT from 2007 to 2009; and “Education-and-Research Hub for

Mathematics-for-Industry,” adopted as a Global COE Program by MEXT from 2008 to

2012.

In accordance with the establishment of the Institute of Mathematics for Industry (IMI)

in April 2011 and the authorization of IMI’s Joint Research Center for Advanced and

Fundamental Mathematics-for-Industry as a MEXT Joint Usage / Research Center in

April 2013, hereafter the MI Lecture Notes Series will publish lecture notes and

pro-ceedings by worldwide researchers of MI to contribute to the development of MI.

October 2014

Yasuhide Fukumoto

Director

SEYQ

Ľĺ“žðŠĜÛ±2ÿžbtx‰mscw|/k‚‰{ƒrszf/3 ("

""#('#"$#)%*'!'& '#%!S+2ÿž-ÿŏ“žO-Ô±OR®īQ[^cw

|/k‚‰đéRIYR½ªĔü{‡iƒ0Œñ.ÿž®ī{‡iƒ3Ġ§£.Īºÿŏ½ªí

įħ1NÆğC_Ivrsˆ/h¶½ª¦ĴaŒ<¹=+ľă įħ[]

į¢:?Mÿž-ÿŏ“žOļŊ-Ô±OR®īaþüF^Đ÷ĤPâ]ĐXNF,´åęž~m-zfb-c‰p

ms„½ªí01; Û«ĦOP]+ĎË Rÿž-ÿŏ“ž§£O®ŕĖāağ<+-Ô

±™QĊÐF^ÿž-ÿŏ“žVRu/naĆ²ĤQıµDM+ň옻QUC`D7ÿž-ÿŏ“ž½

ªÞOR®īQ[^½ªaĔüF^ÖĐXaÆğF^AOaŇĶODM7WF,

ĨÛ±R‹¡ODM+ į ¼ ĭQ q/s„b…2ÎĥŏŘR¦ďOŽō3a›

Í7IDWDI,A_S

Û±OËő½ª›ıłý“ž¨êø°§Æ01ORŗ¸¥•2-C<;?- ÊĬk‰}ld4ÿžyˆ/;Ā™aĿ8^ 53 į ¼ ĭRì

ĭQÜÙC_IZRNF,³įOXQèŎĂaēDM7^ÎĥŏŘOHRÔ±VRŽōQL7M+Ń

q/s„b…NS̋ċNŸŋĠR ŅR½ªÞQĵĉʼn’Â?RĮʼnĤÈ©aÇKM7IJ<W

DI,AR†hq€/w/sS+ёÞRXP\GĵёÞQėDMZ+ĨœļŊR¦ďÛÉRŀžQ¬

D+WI+ĈĞĤõŁaģ¬F^IY+È©ÚŔaO]WOYIZRNF,

q/s„b…RčIJQS+ŐÓÎĥŏŘRàã̋ýÞN+řĹ×Ģ½ªíO­ĬNHRݗÜĒ

Nę<Pă”a6@M7^ûÒġİë¯ä0´åęž~m-zfb-c‰pms„½ªí1Q2ċ·º•

łĮʼn3OěDMċ·º•łRŏŘĤ¦ď9[TĉōozsdebaŸōDI¾ÜĤPňěR˜łaB

ò–7IJ<WDI,ÀIJS+ºÕ§aōDI·öÎĥŏŘRycgbubN+ąĸćºVRŽōN

ę<Pă”a6@MA\_Iijóæįä0Ņ¿ęžõŁž½ª“1QBĝĨ7IJ<WDI,2·ö

ÎĥŏŘOąĸćºVRŽō3ODM+·öÎĥRŏŘĤĕņOñąĸĩRćºVRÜČĤPŽ

ōQL7MBÈ©7IJ<+HRÀ+ёÞRyoj‰aō7IozsdebŸōRÜçaÇKM7I

J<WDI,Ń½ª—;ÌÀRÿž-Žōÿž½ª9[TļŊ-Ô±VRŽōR‹ïOP^AOa

¤KM7WF,

Ńq/s„b…S+ RB®ŕRZO+ Û±0Ľĺ“žð1;áÍ7IDWDI,›ÍQ

ÏDMS+ĭŃÿž—+ĭюōÿŏž—+Īº£ŗž—ŗÊQBÀ7IJ<WDI,ÈØańYM>

JCKIœĈĄ+›ÍQB®ŕ7IJ7IšŌQ+ARôa9ß]DMù>ÁŖúDó@WF,

Û± Ęķ ĻŃ Åæ

´å ž~m-zfb-c‰pms„½ªí-í

B7 D 2 B.

); BG-"%#% *@)+8

Đsiw‘š±ÉµÙ±<œ}²=|TVÃÑ Ï

$"

¡Î

?/1(FCH

˜Ÿ8ªž ¾È ’¢¹‹ qd7m_[7\yfdiu•¥

‰Ý8

7±“”…غN¿Ž@TPÜá khix9`mw9

7±“”…غNßãÀŒ³ ŒÕ¿ß6»ÂˆLqhgyaM@DWÜ6´¸¬

7±“”…غYˆCHSN 2-")( Nt\ntu . N¦†

,0

/<5A'JL=E>1&I

˜Ÿ8ʧ £—:֖€¹‹ ¹‹{¨Ò‹•„;

‰Ý8

7˱“”…غLGKRHLBN›Á¯”غNǽLˆÔ

7›Á¯”غN⶷“©›Á‚غQNŠ¼

7­Í¯”QNÜáN¦†

7+YÜ?H ¤: ¤MƒFXWÓOlebyYEÜzCIF?5;

34!%9:6K

7ÌÝmZ\v

+8  TVf]yw9jG4\ydi9vGKCIF?5

"--*000 + ')+! )0(&)*"*

+s\yp9c8

"--*000 + ')+!

 ¤owatr8N•‡]^np9cM>Wuy`AUf]yw9jGKCIF?5

"--*,#'*#'#%2.,"..$*0*/(- %

:mZ\vQN¾®uy`8

目次

線形計画法入門

神山

直之

(

九州大学

マス・フォア・インダストリ研究所

)

形状最適化理論と製品設計への応用

畔上

秀幸（名古屋大学

大学院情報学研究科）

・・・・・・・・・　1

線形計画法入門

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

線形計画法入門

神山 直之

最適化問題

？

最適化問題

？

最適化問題

=

「

入力

」

+

「

目的

」

入力

：解 候補集合

F

目的関数

f

:

F

→

R

目的

：

f

(

x

)

最小化

x

∈

F

見

例１：

F

=

{

x

∈

R

| −

1

≤

x

≤

1

}

,

f

(

x

) =

x

2

−

x

例２：

F

=

{

X

_⊆

N

_|

∑

i

∈

X

c

(

i

)

_≤

B

}

,

f

(

X

) =

B

₋

∑

i

∈

X

c

(

i

)

N

=

有限集合

,

B

_∈

Z

+

,

c

:

N

→

Z

+

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

線形計画問題

？

線形計画問題

？

f

F

「線形」

最適化問題

f

=

x

1

+

x

2

x

1

x

2

F

f

=

x

1

+

x

2

x

1

x

2

F

x

∗

本講義

：線形計画問題 基礎 理論的応用

最適化問題

？

最適化問題 形式的

以下

書

Minimize

f

(

x

)

subject to

x

_∈

F

- “Minimize”

最小化 表

横 目的関数 書

- “subject to”

制約 書

集合

幾

式

f

(

x

)

最小値 達成

x

∗

∈

F

最適解

最適解

x

∗

対

f

(

x

∗

)

最適値

注意

：実 色々細

最適解 存在性

線形計画問題 例

必要 栄養

食事 考

問題

食品

A

：価格

= 2

,

栄養

1

= 3

,

栄養

2

= 2

食品

B

：価格

= 3

,

栄養

1

= 2

,

栄養

2

= 6

必要 栄養量：栄養

1

= 5

,

栄養

2

= 8

=

⇒

最小 価格 必要 栄養 確保

？

以下

線形計画問題

Minimize

2

x

1

+ 3

x

2

subject to

3

x

1

+ 2

x

2

≥

5

2

x

1

+ 6

x

2

≥

8

x

1

≥

0

, x

2

≥

0

線形計画問題 例

必要 栄養

食事 考

問題

食品

A

：価格

= 2

,

栄養

1

= 3

,

栄養

2

= 2

食品

B

：価格

= 3

,

栄養

1

= 2

,

栄養

2

= 6

必要 栄養量：栄養

1

= 5

,

栄養

2

= 8

=

⇒

最小 価格 必要 栄養 確保

？

x

1

=

食品

A

量 表 変数

x

2

=

食品

B

量 表 変数

最小化

価格

= 2

x

1

+ 3

x

2

制約

=

栄養

1

：

3

x

1

+ 2

x

2

≥

5

,

栄養

2

：

2

x

1

+ 6

x

2

≥

8

線形計画問題

線形計画問題

入力

：

m

_×

n

行列

A

_∈

Q

m

×

n

n

次元

c

_∈

Q

n

m

次元

b

∈

Q

m

目的

：

以下 最適化問題 最適解 求

Minimize

c

⊤

x

subject to

Ax

≥

b

x

_∈

R

n

+

行列 用

表現

以下 線形計画問題

Minimize

2

x

1

+ 3

x

2

subject to

3

x

1

+ 2

x

2

≥

5

2

x

1

+ 6

x

2

≥

8

x

1

≥

0

, x

2

≥

0

行列 用

表現

以下

Minimize

(

2

3

)

⊤

·

(

x

1

x

2

)

subject to

(

3 2

2 6

) (

x

1

x

2

)

≥

(

5

8

)

(

x

1

x

2

)

≥

(

0

0

)

線形計画問題 対

本講演 前提

線形計画法 理論・実用的 効率的 解

理論的

-

単体法，楕円体法，内点法

本講演

̸

=

解説

本講演

=

問題自体 理論的基礎・理論的応用

- CPLEX, Gurobi , GLPK

- PuLP (Python)

線形計画問題 基本性質

x

∈

R

n

線形計画問題 実行可能解

def

⇐⇒

x

_∈

R

n

+

Ax

≥

b

満

定理

任意 線形計画問題 対

以下 一

成 立

1

実行可能解 存在

2

実行可能解 存在 目的関数 値 下界

3

実行可能解 存在 目的関数 値 下界

下界 達成

実行可能解 存在

証明 省略

Python

PuLP

線形計画問題 解

PuLP

-

正確

Python

仕方 例

sudo pip install pulp

以下

次 線形計画問題

PuLP

解

Minimize

8

x

+ 19

y

subject to

2

x

+ 7

y

≥

40

6

x

+ 3

y

_≥

50

x

≥

0

y

≥

0

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

PuLP

使用方法

制約 定義

problem += 2*x + 7*y >= 40

problem += 6*x + 3*y >= 50

problem += x >= 0

problem += y >= 0

問題 解

状況 確認

解 出力

status = problem.solve()

print(pulp.LpStatus[status])

print(pulp.value(problem.objective))

print(x.value())

print(y.value())

PuLP

使用方法

PuLP

import pulp

問題

作

problem = pulp.LpProblem("P",pulp.LpMinimize)

変数 定義

x = pulp.LpVariable("x")

y = pulp.LpVariable("y")

目的関数 定義

problem += 8*x + 19*y

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

全体

import pulp

problem = pulp.LpProblem("P", pulp.LpMinimize)

x = pulp.LpVariable("x")

y = pulp.LpVariable("y")

problem += 8*x + 19*y

problem += 2*x + 7*y >= 40

problem += 6*x + 3*y >= 50

problem += x >= 0

problem += y >= 0

status = problem.solve()

print(pulp.LpStatus[status])

print(pulp.value(problem.objective))

print(x.value())

最大流問題

最大流問題

∑

a

∈

δ

(

s

)

f

(

a

)

最大化

s-t

実行可能

求

最大流問題 以下 線形計画問題 定式化

Minimize

₋

∑

a

∈

δ

(

s

)

f

(

a

)

subject to

∑

a

∈

δ

(

v

)

f

(

a

) =

∑

a

∈

ϱ

(

v

)

f

(

a

) (

v

_∈

V

_{\ {}

s, t

_}

)

f

(

a

)

≤

c

(

a

) (

a

∈

A

)

f

∈

R

A

+

有向

有向

D

= (

V, A

)

V

:=

点集合 呼

有限集合

,

A

⊆

V

×

V

特別 点

s, t

_∈

V

関数

c

:

A

_→

Q

+

対

-

関数

f

:

A

→

R

+

実行可能

s

-

t

def

⇐⇒

∀

a

∈

A

:

f

(

a

)

≤

c

(

a

)

∀

v

_∈

V

_{\ {}

s, t

_}

:

∑

_a

_∈

_ϱ

₍

_v

₎

f

(

a

) =

∑

_a

_∈

_δ

₍

_v

₎

f

(

a

)

s

t

s

t

Python

実装例

problem += - x1 - x2

problem += x1 - x3 - x4 == 0

problem += x2 + x3 - x5 - x6 == 0

problem += x4 + x5 - x7 - x8 == 0

problem += x6 + x7 - x9 == 0

problem += x1 <= 1

problem += x2 <= 1

problem += x3 <= 1

problem += x4 <= 1

problem += x5 <= 1

problem += x6 <= 1

problem += x7 <= 1

problem += x8 <= 1

problem += x9 <= 1

Python

実装例

import pulp

problem = pulp.LpProblem("P", pulp.LpMinimize)

x1 = pulp.LpVariable("x1")

x2 = pulp.LpVariable("x2")

x3 = pulp.LpVariable("x3")

x4 = pulp.LpVariable("x4")

x5 = pulp.LpVariable("x5")

x6 = pulp.LpVariable("x6")

x7 = pulp.LpVariable("x7")

x8 = pulp.LpVariable("x8")

x9 = pulp.LpVariable("x9")

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

Python

実装例

status = problem.solve()

print(pulp.LpStatus[status])

print(pulp.value(problem.objective))

print(x1.value())

print(x2.value())

print(x3.value())

print(x4.value())

print(x5.value())

print(x6.value())

print(x7.value())

print(x8.value())

print(x9.value())

答

−

2

出

正解

NetworkX

辺 加

G.add edge(’s’, ’1’, capacity=1)

G.add edge(’s’, ’2’, capacity=1)

G.add edge(’1’, ’2’, capacity=1)

G.add edge(’1’, ’3’, capacity=1)

G.add edge(’2’, ’3’, capacity=1)

G.add edge(’2’, ’4’, capacity=1)

G.add edge(’3’, ’4’, capacity=1)

G.add edge(’3’, ’t’, capacity=1)

G.add edge(’4’, ’t’, capacity=1)

最大流問題 解

flow value, flows = nx.maximum flow(G, ’s’, ’t’)

結果 表示

print(flow value)

NetworkX

仕方 例

sudo pip install networkx

Networkx

import networkx as nx

空

用意

G = nx.DiGraph()

点 加

G.add node(’s’)

G.add node(’1’)

G.add node(’2’)

G.add node(’3’)

G.add node(’4’)

G.add node(’t’)

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

全体

import networkx as nx

G = nx.DiGraph()

G.add node(’s’)

G.add node(’1’)

G.add node(’2’)

G.add node(’3’)

G.add node(’4’)

G.add node(’t’)

G.add edge(’s’, ’1’, capacity=1)

G.add edge(’s’, ’2’, capacity=1)

G.add edge(’1’, ’2’, capacity=1)

G.add edge(’1’, ’3’, capacity=1)

G.add edge(’2’, ’3’, capacity=1)

G.add edge(’2’, ’4’, capacity=1)

G.add edge(’3’, ’4’, capacity=1)

G.add edge(’3’, ’t’, capacity=1)

G.add edge(’4’, ’t’, capacity=1)

flow value, flows = nx.maximum flow(G, ’s’, ’t’)

print(flow value)

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

端点解

線形計画問題 実行可能解

x

端点解

⇐⇒

def

以下 満

x

異

実行可能解

y, z

存在

∃

ε

∈

R

s.t

0

< ε <

1 : (1

−

ε

)

y

+

εz

=

x

定理（証明略）

最適解 存在

端点最適解 常 存在

f

=

x

+

x

x

x

F

f

=

x

+

x

x

x

F

x

最大

問題

応用

二部

上 最大

問題

入力：二部

G

= (

A, B

;

E

)

目的：要素数 最大

線形計画問題

定式化

(

整数計画問題

)

Minimize

₋

∑

e

∈

E

x

(

e

)

subject to

∑

e

∈

E

:

v

∈

e

x

(

e

)

_≤

1

(

v

_∈

A

_∪

B

)

x

∈ {

0

,

1

}

E

注意：

x

∈ {

0

,

1

}

制約

問題 一般

難

最大

問題

応用

二部

G

= (

A, B

;

E

)

-

A

∩

B

=

∅

満

有限 点集合

A, B

-

以下 満

有限 辺集合

E

∀

e

_∈

E

:

e

_⊆

V,

_|

e

_∩

A

_|

=

_|

e

_∩

B

_|

= 1

M

_⊆

E

_⇐⇒

def

任意

v

_∈

A

_∪

B

対

_|{

e

_∈

M

_|

v

_∈

e

_{}| ≤}

1

証明

任意 端点解 任意 要素 整数

示

整数

要素 含 端点解

x

存在

仮定

F

def

=

_{

e

_∈

E

_|

0

< x

(

e

)

<

1

_}

以下 場合 分

証明

-

F

中

“

”C

場合

=

_⇒

2

部

C

長

偶数

-

F

中

“

”

場合

最大

問題

応用

x

(

e

)

∈ {

0

,

1

}

0

≤

x

(

e

)

≤

1

緩和

Minimize

−

∑

e

∈

E

x

(

e

)

subject to

∑

e

∈

E

:

v

∈

e

x

(

e

)

≤

1

(

v

∈

A

∪

B

)

x

(

e

)

_≤

1

(

e

_∈

E

)

x

∈

R

E

+

=

⇒

問題 変

線形計画問題

定理

緩和

最適解 目的関数値 変

証明：

F

中 閉路

場合

F

中 任意 極大

“

”

P

(

u

w

仮定

)

v

_{∈ {}

u, w

_}

1

F

辺 入

=

⇒

辺

δ

F

(v)

書

1

−

x(δ

F

(v))

<

1

α

def

= min

{

x(e)

|

e

∈

P

}

,

β

def

= min

{

1

−

x(e)

|

e

∈

P

}

ε

def

= min

{

α, β

}

x

+

_{, x}

−

def

₌

_x

_交互

_M

_{足 ・引}

=

⇒

x

+

_{, x}

−

実行可能解

_x

₌

1

2

(x

+

+

x

−

)

=

⇒

x

端点解

矛盾

ε

₋

ε

ε

₋

ε

ε

₋

ε

証明：

F

中 閉路

C

場合

α

def

= min

_{

x(e)

_|

e

_∈

C

_}

β

def

= min

_{

1

₋

x(e)

_|

e

_∈

C

_}

ε

def

= min

_{

α, β

_}

x

+

_{, x}

−

def

₌

_x

交互

_M

足 ・引

=

_⇒

x

+

_{, x}

−

実行可能解

_x

₌

1

2

(x

+

+

x

−

)

=

_⇒

x

端点解

矛盾

ε

ε

−

ε

−

ε

−

ε

₋

ε

ε

ε

線形計画問題 書 換

行列

A

i

行

j

列

a

ij

b

b

def

= (

b

1

, b

2

, . . . , b

m

)

⊤

定義

c

c

def

= (

c

1

, c

2

, . . . , c

n

)

⊤

定義

記法 使

線形計画問題 以下

Minimize

c

1

x

1

+

c

2

x

2

+

· · ·

+

c

n

x

n

subject to

a

1

,

1

x

1

+

a

1

,

2

x

2

+

· · ·

+

a

1

,n

x

n

≥

b

1

a

2

,

1

x

1

+

a

2

,

2

x

2

+

· · ·

+

a

2

,n

x

n

≥

b

2

...

a

m,

1

x

1

+

a

m,

2

x

2

+

· · ·

+

a

m,n

x

n

≥

b

m

x

1

, x

2

, . . . , x

n

≥

0

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

緩和

他 制約 緩和

(

y

j

≥

0

)

Minimize

c

1

x

1

+

· · ·

+

c

n

x

n

+

m

∑

j

=1

y

j

(

b

j

−

a

j,

1

x

1

− · · · −

a

j,n

x

n

)

subject to

x

1

, x

2

, . . . , x

n

≥

0

項 並 替

Minimize

b

1

y

1

+

· · ·

+

b

m

y

m

+

n

∑

i

=1

x

i

(

c

i

−

a

1

,i

y

1

− · · · −

a

m,i

y

m

)

subject to

x

1

, x

2

, . . . , x

n

≥

0

緩和

先

線形計画問題

緩和

制約式

a

1

,

1

x

1

+

· · ·

+

a

1

,n

x

n

≥

b

1

取 除

b

1

−

a

1

,

1

x

1

− · · · −

a

1

,n

x

n

≤

0

=

_⇒

y

1

≥

0

掛

目的関数 足

Minimize

c

1

x

1

+

· · ·

+

c

n

x

n

+

y

1(

b

1

−

a

1

,

1

x

1

− · · · −

a

1

,n

x

n

)

subject to

a

2

,

1

x

1

+

a

2

,

2

x

2

+

· · ·

+

a

2

,n

x

n

≥

b

2

...

a

m,

1

x

1

+

a

m,

2

x

2

+

· · ·

+

a

m,n

x

n

≥

b

m

x

1

, x

2

, . . . , x

n

≥

0

双対問題

以下 問題 元 問題 「双対問題」

Maximize

b

1

y

1

+

b

2

y

2

+

· · ·

+

b

m

y

m

subject to

a

1

,

1

y

1

+

a

2

,

1

y

2

+

· · ·

+

a

m,

1

y

m

≤

c

1

a

1

,

2

y

1

+

a

2

,

2

y

2

+

· · ·

+

a

m,

2

y

m

≤

c

2

...

a

1

,n

y

1

+

a

2

,n

y

2

+

· · ·

+

a

m,n

y

m

≤

c

n

y

1

, y

2

, . . . , y

m

≥

0

行列 使

表現 以下

Maximize

b

⊤

y

subject to

A

⊤

y

≤

c

y

_∈

R

m

+

双対問題

問題 元 問題 「緩和」

最適解 目的関数 値 下

=

_⇒

元 問題 最適解 目的関数 値 下界

良 下界 欲

b

1

y

1

+

· · ·

+

b

m

y

m

最大化

y

1

, y

2

, . . . , y

m

x

i

≥

0

c

i

−

a

1

,i

y

1

− · · · −

a

m,i

y

m

≥

0

意味

⇐

=

目的関数 値 小

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

双対定理

x

∈

R

n

+

def

=

元 問題 実行可能解

(x

∗

def

=

最適解

)

y

_∈

R

m

+

def

=

双対問題 実行可能解

(y

∗

def

₌

最適解

₎

定理：弱双対定理

c

⊤

x

≥

b

⊤

y

証明

c

⊤

x

_≥

(

y

⊤

A

)

x

=

y

⊤

(

Ax

)

_≥

y

⊤

b

=

b

⊤

y

□

定理：強双対定理（証明 省略）

c

⊤

x

∗

=

b

⊤

y

∗

和

利得 定義：

(R

戦略

_{

x

i

}

, C

戦略

{

y

i

}

)

- R

利得

:=

m

∑

i

=1

n

∑

j

=1

a

i,j

x

i

y

j

- C

損害

:=

m

∑

i

=1

n

∑

j

=1

a

i,j

x

i

y

j

目的：

- R

目的

:= max

{

xi

}

min

{

yj

}

m

∑

i

=1

n

∑

j

=1

a

i,j

x

i

y

j

- C

目的

:= min

{

yj

}

max

{

xi

}

m

∑

i

=1

n

∑

j

=1

a

i,j

x

i

y

j

和

入力：

-

行列

A

= (

a

i,j

)

i

=1

,...,m,j

=1

,...,n

-

行

R

列

C

-

a

i,j

= C

R

払 金額

考

：

- R

戦略

=

⇒

行集合

{

1

,

2

, . . . , m

}

上 確率分布

- C

戦略

=

_⇒

列集合

_{

1

,

2

, . . . , n

_}

上 確率分布

von Neumann

最大最小定理

先

線形計画問題 双対問題 以下

Minimize

α

subject to

n

∑

j

=1

a

ij

y

j

≤

α

(i

∈ {

1,

2, . . . , m

}

)

n

∑

j

=1

y

j

= 1

y

j

≥

0 (j

∈ {

1,

2, . . . , n

}

)

定理 右辺 求

問題

強双対定理

右辺 左辺 一致

□

von Neumann

最大最小定理

定理

max

{

xi

}

min

{

yj

}

m

∑

i

=1

n

∑

j

=1

a

i,j

x

i

y

j

= min

{

yj

}

max

{

xi

}

m

∑

i

=1

n

∑

j

=1

a

i,j

x

i

y

j

左辺 問題 以下

書

Maximize

z

subject to

m

∑

i

=1

a

ij

x

i

≥

z

(

j

∈ {

1

,

2

, . . . , n

}

)

m

∑

i

=1

x

i

= 1

x

i

≥

0 (

i

∈ {

1

,

2

, . . . , m

}

)

課題

課題

1

講演 紹介

線形計画問題 例

解

課題

2

以下 問題

Maximize

z

subject to

∑

m

_i

₌₁

a

ij

x

i

≥

z

(

j

∈ {

1

,

2

, . . . , n

}

)

∑

m

i

=1

x

i

= 1

x

i

≥

0 (

i

∈ {

1

,

2

, . . . , m

}

)

双対問題 導

概要

1

線形計画問題

2

Python

PuLP

3

最大流問題

4

Python

NetworkX

5

端点解

6

最大

問題

7

双対問題

8

和

9

演習

課題

2

解答

上界 求

min

β

z

自由

∑

n

_j

₌₁

y

j

−

1 = 0

x

i

≥

0

意味

∑

n

_j

₌₁

a

ij

y

j

−

β

≤

0

以上

Minimize

β

subject to

n

∑

j

=1

a

ij

y

j

≤

β

(i

∈ {

1,

2, . . . , m

}

)

n

∑

j

=1

y

j

= 1

y

j

≥

0 (j

∈ {

1,

2, . . . , n

}

)

課題

2

解答

各

j

= 1,

2, . . . , n

対

変数

y

j

≥

0

用意

変数

β

用意

問題 緩和

max

z

+

n

∑

j

=1

y

j

(

m

∑

i

=1

a

ij

x

i

−

z) +

β(1

−

m

∑

i

=1

x

i

)

整理

max

β

+

z(1

₋

m

∑

j

=1

y

j

) +

m

∑

i

=1

x

i

(

n

∑

j

=1

a

ij

y

j

−

β)

形状最適化理論と製品設計への応用

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ͸͡Ίʹ

͸͡Ίʹ

■

ܗঢ়࠷దԽ໰୊

φ

₍

_θ

₎

D

Γ

Γ

p

b

(

θ

)

u

Γ

Γ

Ω

Ω(

φ

)

x

(

i

+

φ

)(

x

)

Γ(

x

)

(a)

ີ౓มಈ

ϕ

(

θ

)

,

ઃܭม਺

θ

:

D

→

R

(b)

ྖҬมಈ

(

ઃܭม਺

)

ϕ

:

R

→

R

ਤ

1.1:

d

∈ {

2

,

3

}

࣍ݩͷྖҬ

D,

Ω

⊂

R

ͱઃܭม਺

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻

൞্ ल޾

໊ݹ԰େֶ ৘ใֶݚڀՊ ෳࡶܥՊֶઐ߈

AIMaP

νϡʔτϦΞϧʮ࠷దԽཧ࿦ͷجૅͱԠ༻ʯ

೔ຊڮϥΠϑαΠΤϯεϏϧσΟϯά

, 2018

೥

1

݄

19

೔

1

_{਺ֶΞυόϯετΠϊϕʔγϣϯϓϥοτϑΥʔϜ}

_{, Advanced Innovation powered by}

Mathematics Platform

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷಛ௃

§

1

࠷దઃܭ໰୊ͷಛ௃

■

ஈ͖ͭ

1

࣍ݩઢܗ஄ੑମͷஅ໘ੵ࠷దԽ໰୊

[1, 1.1

અ

]

அ໘ੵ

a

= (

a

, a

)

͕༩͑ΒΕͨͱ͖ɼ֎ྗ

p

= (

p

, p

)

Λط஌ͱͯ͠ɼ

มҐ

u

= (

u

, u

)

͸

e

l

(

a

+

a

−

a

−

a

a

) (

u

u

)

=

(

p

p

)

(1.1)

ΑΓٻΊΒΕΔɽ͜͜Ͱɼ

a

Λ

ઃܭม਺

ɼ

u

Λ

ঢ়ଶม਺

ͱΈͳ͢ɽ

p

u

u

a

l

a

p

l

x

Γ

_Γ

2

Γ

ਤ

1.1:

2

ͭͷஅ໘ੵΛ΋ͭ

1

࣍ݩઢܗ஄ੑମ

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ͸͡Ίʹ

■

֓ཁ

•

ඇઢܗܭը໰୊ͱͯ͠Έͨͱ͖ͷ

࠷దઃܭ໰୊

ͷಛ௃

(

_§

1)

ͱղ๏

(

_§

2)

•

࠷దઃܭ໰୊ͷ

࿈ଓମܗঢ়࠷దԽ໰୊

΁ͷ֦ு

(

§

3,

§

4,

§

5,

§

6)

•

੡඼ઃܭ΁ͷԠ༻ྫͷ঺հ

(

_§

7

_{∼ §}

11)

•

FreeFEM++

Λ༻͍࣮ͨश

(

§

12)

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷಛ௃

ઃܭม਺ͷೖΔઢܗۭؒ

Λ

X

=

R

ͱ͓͖ɼ͞Βʹɼઃܭू߹Λ

D

=

_{

a

_∈

X

_|

a

_≥

a

}

ͱ͓͘ɽͨͩ͠ɼ

a

= (

a

, a

)

>

0

Λఆ਺ϕΫτϧͱ͢Δɽ·ͨɼ

ঢ়ଶม

਺ͷೖΔઢܗۭؒ

Λ

U

=

R

ͱ͓͘ɽ

໰୊

1.2 (

ฏۉίϯϓϥΠΞϯε࠷খԽ໰୊

)

X

=

R

_͓Αͼ

_U

₌

_R

_{ͱ͓͘ɽ͜ͷͱ͖ɼ}

min

(a,u)∈D×U

{

f

(

u

)

|

f

(

a

)

≤

0

,

໰୊

1.1

}

Λຬͨ͢

a

ΛٻΊΑɽ

࠷దઃܭ໰୊ͷಛ௃

࠷దઃܭ໰୊͸ɼ

ঢ়ଶܾఆ໰୊͕౳੍ࣜ໿ͱͯ͠ՃΘͬͨ

ෆ౳͖ࣜͭඇઢܗ࠷

దԽ໰୊ͷΫϥεͱΈͳ͢͜ͱ͕Ͱ͖Δɽ

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷಛ௃

໰୊

1.1 (

ঢ়ଶܾఆ໰୊

)

ਤ

2.4

ͷ

1

࣍ݩઢܗ஄ੑମʹରͯ͠ɼ௕͞

l

, Young

཰

e

,

p

∈

R

͓Αͼ

a

_∈

R

_{͕༩͑ΒΕͨͱ͖ɼ}

K

(

a

)

u

=

p

(1.2)

Λຬͨ͢

u

_∈

R

_{ΛٻΊΑɽͨͩ͠ɼࣜ}

_(1.2)

_͸ࣜ

_(1.1)

_{Λද͢͜ͱʹ͢Δɽ}

໰୊

1.1

ͷղ

u

ʹରͯ͠ɼ

໨తؔ਺

ͱ

੍໿ؔ਺

(

͋Θͤͯ

ධՁؔ਺

ͱΑͿ

)

Λ

f

(

u

) =

(

p

p

)

(

u

u

)

=

p

_·

u

,

f

(

a

) =

l

(

a

+

a

)

−

c

=

(

l

l

)

(

a

a

)

−

c

ͱ͓͘ɽf

͸ฏۉίϯϓϥΠΞϯεɼf

͸ମੵ੍໿ؔ਺ͱΑ͹ΕΔɽ

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

§

2

࠷దઃܭ໰୊ͷղ๏

■

ޯ഑๏ͱ

Newton

๏

[1, 3.3

અ

, 3.5

અ

]

࠷ॳʹ੍໿ͳ͠ͷ໰୊Λߟ͑Δɽ

໰୊

2.1 (

੍໿ͳ͠࠷దԽ໰୊

)

X

=

R

_ɼf

_:

_X

_→

_R

_ʹରͯ͠ɼ

min

x∈X

f

(

x

)

Λຬͨ͢

x

ΛٻΊΑɽ

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷಛ௃

ྫ୊

1.3 (

ฏۉίϯϓϥΠΞϯε࠷খԽ໰୊ͷ਺஋ྫ

)

໰୊

1.2

ʹ͓͍ͯ

l

= 1

,

e

= 1

,

c

= 1

,

p

= (1

,

1)

,

a

= (0

.

1

,

0

.

1)

ͱ͓͍ͯɼ

a

ͷ࠷খ఺ΛٻΊΑɽ

0 0

1 15

a

1

a

f

(a

,1–

a

)

f

(a

,

a

)

˜

˜

10

5

ਤ

1.2:

ઃܭม਺ͷू߹ʹ͓͚ΔฏۉίϯϓϥΠΞϯε

(

f

(

u

(

a

))

Λ

f

˜

(

a

)

ͱ͔͘

)

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

ࣜ

(2.1)

͸ɼ

q

(

y

) = min

y∈X

{

q

(

y

) =

1

2

y

·

(

Ay

) +

g

·

y

+

f

(

x

)

}

Λຬͨ͢

y

∈

X

ΛٻΊΔ͜ͱͱಉ஋Ͱ͋Δɽ

g

X

f

y,

�

y

�

=1

X

�

g

_�

x

R

ਤ

2.1:

ޯ഑

g

ͷఆٛ

X

g

X

f

yg

R

q

x

¯

ਤ

2.2:

ޯ഑๏

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

ධՁؔ਺

f

ͷࢼߦ఺

x

पΓͷ

Taylor

ల։

f

(

x

+

y

) =

f

(

x

) +

g

·

y

+

o

(

∥

y

∥

)

ʹ͓͍ͯɼ

ޯ഑

g

͕ܭࢉ͞Εͨͱ͖ɼޯ഑๏͸ɼ

y

·

(

Ay

) =

−

g

·

y

∀

y

∈

X

⇔

y

=

−

A

g

(2.1)

Λຬͨ͢Α͏ʹ୳ࡧϕΫτϧ

y

∈

X

ΛٻΊΔํ๏Ͱ͋Δɽͨͩ͠ɼ

A

∈

R

͸ਖ਼ఆ஋ରশߦྻͱ͢Δɽ͢ͳΘͪɼ

A

=

A

,

∃

α >

0 :

y

·

(

Ay

)

≥

α

∥

y

∥

∀

y

∈

X.

࣮ࡍɼ

f

(

x

+

ϵ

y

)

−

f

(

x

) =

−

ϵ

y

·

(

Ay

) +

o

(

ϵ

)

≤ −

ϵα

∥

y

∥

+

o

(

ϵ

)

.

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

■

౳੍ࣜ໿͖ͭ໰୊ʹ͓͚Δ

f

ͷޯ഑ͱ

Hesse

ߦྻ

[1, 2.6

અ

]

࠷దԽཧ࿦

•

ઃܭม਺Λ

x

∈

X

=

R

ͱ͢Δɽ

•

౳੍ࣜ໿Λ

h

= (

h

,

· · ·

, hn

)

:

X

→

R

(

n < d

)

ͱ͔͘ɽ

࠷దઃܭཧ࿦

•

ઃܭม਺Λ

x

= (

ϕ

,

u

)

∈

X

=

R

= Ξ

×

U

=

R

×

R

₍

_{n < d}

₎

_ͱ͢Δɽ

ϕ

_∈

Ξ

Λ

ઃܭม਺

ɼ

u

_∈

U

Λ

ঢ়ଶม਺

ͱΑͿɽ

•

౳੍ࣜ໿Λ

h

= (

h

,

· · ·

, hn

)

:

X

→

R

=

U

ͱ͓͘ɽ

໰୊

2.2 (

౳੍ࣜ໿͖ͭ࠷దԽ໰୊

)

X

=

R

_ɼf

_:

_X

_→

_R

_,

_h

_{= (}

_h

1

,

· · ·

, h

)

:

X

→

R

(

n < d

)

ʹରͯ͠ɼ࣍Λຬ

ͨ͢

x

= (

ϕ

,

u

)

ΛٻΊΑɽ

min

x∈X

{

f

(

x

)

|

h

(

x

) =

0

}

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

ޯ഑

g

ͷࢼߦ఺

x

पΓͷ

Taylor

ల։

g

(

x

+

y

) =

g

+

Hy

+

o

(

∥

y

∥

)

Λຬͨ͢

ޯ഑

g

ͱ

Hesse

ߦྻ

H

͕ܭࢉ͞Εͨͱ͖ɼ

Newton

๏͸ɼ

g

(

x

+

y

) =

g

+

Hy

=

0

ͱ͓͘͜ͱʹΑΓ୳ࡧϕΫτϧ

y

∈

X

ΛٻΊΔํ๏Ͱ͋Δɽ͢ͳΘͪɼ

y

·

(

Hy

) =

−

g

·

y

∀

y

∈

X .

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

■

Lagrange

৐਺๏

(

ਵ൐ม਺๏

)

ʹΑΔޯ഑ͷٻΊํ

x

= (

ϕ

,

u

)

_∈

X

= Ξ

_×

U

ʹ஫ҙͯ͠ɼ໰୊

2.2

ʹର͢Δ

Lagrange

ؔ਺Λ

L

(

ϕ

,

u

,

v

) =

f

(

ϕ

,

u

) +

L

(

ϕ

,

u

,

v

) =

f

(

ϕ

,

u

) +

v

·

h

(

ϕ

,

u

)

ͱ͓͘ɽ

v

_∈

U

͸

Lagrange

৐਺Ͱ͋Δɽ

L

ͷશඍ෼ʹରͯ͠ɼ

L

(

ϕ

,

u

,

v

) [

φ

,

u

ˆ

,

v

ˆ

]

=

f

(

ϕ

,

u

) [

φ

] +

L

(

ϕ

,

u

,

v

) [

φ

]

+

f

(

ϕ

,

u

) [ ˆ

u

] +

L

(

ϕ

,

u

,

v

) [ ˆ

u

] (= 0

⇐

f

+

L

(

ϕ

,

u

,

v

) =

0

)

+

L

(

ϕ

,

u

,

v

) [ˆ

v

]

(= 0

⇐

h

(

ϕ

,

u

) =

0

)

=

g

·

φ

= ˜

f

(

ϕ

) [

φ

]

∀

(

φ

,

u

ˆ

,

v

ˆ

)

∈

Ξ

×

U

×

U

͕੒Γཱͭɽͨͩ͠ɼf

(

ϕ

,

u

(

ϕ

))

Λ

_f

˜

₍

_ϕ

₎

_ͱ͔͍ͨɽ

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

໰୊

2.2

ʹର͢Δ

Lagrange

ؔ਺

Λ

L

(

x

,

λ

) =

f

(

x

) +

λ

_·

h

(

x

)

ͱఆٛ͢Δɽ

λ

= (

λ

,

· · ·

, λ

)

∈

R

͸

Lagrange

৐਺

ͱΑ͹ΕΔɽ

ఆཧ

2.3 (

ۃখ఺

1

࣍ͷඞཁ৚݅

[1,

ఆཧ

2.6.4])

f

_∈

C

₍

_X

_;

_R

₎

_ɼ

_h

_∈

_C

₍

_X

_;

_R

₎

_͓Αͼ

_x

_{= (}

_ϕ

_,

_u

₎

_∈

_X

_ʹ͓͍ͯ

h

(

x

)

∈

R

͕ਖ਼ଇߦྻͱ͢Δɽ͜ͷͱ͖ɼ

x

͕໰୊

2.2

ͷۃখ఺ͳΒ͹ɼ

L

(

x

,

λ

) =

0

,

L

(

x

,

λ

) =

h

(

x

) =

0

Λຬͨ͢

λ

∈

R

_{͕ଘࡏ͢Δɽ}

ఆཧ

2.3

ͷ৚݅͸ɼ࣍ͷΑ͏ʹ͔͚Δɽ

L

(

x

,

λ

)

[

y

,

λ

ˆ

]

=

L

(

x

,

λ

) [

y

] +

L

(

x

,

λ

)

[

ˆ

λ

]

= 0

_∀

(

y

,

λ

ˆ

)

_∈

X

_×

U.

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

ఆཧ

2.4 (

ۃখ఺

2

࣍ͷඞཁ৚݅

[1,

ఆཧ

2.6.6])

໰୊

2.2

ʹ͓͍ͯɼf

∈

C

₍

_X

_;

_R

₎

_͓Αͼ

_h

_∈

_C

₍

_X

_;

_U

₎

_ͱ͢Δɽ

x

= (

ϕ

,

u

)

∈

S

ʹ͓͍ͯ

∂X

h

(

x

)

,

. . .

,

∂X

hn

(

x

)

͕

1

࣍ಠཱͱ͢Δɽ͜ͷͱ

͖ɼ

x

͕ۃখ఺ͳΒ͹ɼ͕࣍੒Γཱͭɽ

L

(

x

,

λ

) [

y

,

y

]

≥

0

∀

y

∈

TS

(

x

)

ఆཧ

2.5 (

ۃখ఺

2

࣍ͷे෼৚݅

[2, Theorem 2.3])

໰୊

2.2

ʹ͓͍ͯɼf

∈

C

₍

_X

_;

_R

₎

_͓Αͼ

_h

_∈

_C

₍

_X

_;

_U

₎

_ͱ͢Δɽ

_x

_∈

_X

_ʹ͓͍

ͯ

∂X

h

(

x

)

,

. . .

,

∂X

hn

(

x

)

͕

1

࣍ಠཱͱ͢Δɽ͜ͷͱ͖ɼ

x

͕ఆཧ

2.3

ͷ৚݅

Λຬͨ͠ɼ

L

(

x

,

λ

) [

y

,

y

]

>

0

∀

y

∈

TS

(

x

)

Λຬͨ͢

(

x

,

λ

)

͕ଘࡏ͢ΔͳΒ͹ɼ

x

͸໰୊

2.2

ͷۃখ఺Ͱ͋Δɽ

ܗঢ়࠷దԽཧ࿦ͱ੡඼ઃܭ΁ͷԠ༻ ࠷దઃܭ໰୊ͷղ๏

■

Lagrange

৐਺๏

(

ਵ൐ม਺๏

)

ʹΑΔ

Hesse

ߦྻͷٻΊํ

ڐ༰ू߹

ͱ

ڐ༰ํ޲ू߹

͋Δ͍͸

઀໘

Λ࣍ͷΑ͏ʹఆٛ͢Δɽ

S

=

_{

x

_∈

X

_|

h

(

x

) =

0

}

,

TS

(

x

) =

{

y

∈

X

|

h

(

x

) [

y

] =

0

}

.

h

(

x

)

T

(

x

)

S

x

x

x

x

y

ਤ

2.3:

ڐ༰ू߹

S

ͱڐ༰ํ޲ू߹

T

(

x

)

(

X

=

R

,

n

= 1

)