OR'演類例解

紐と滑車と錘 (2)一一数理計画の散歩道一一
柳井浩/(YI , Y2)=mlYI+m2Y2=max!

4. 紐の長さの配分による定式化(3)となるが，紐がピンと張った状態では，各部分で，滑ーその l

車を通る鉛直線に関して対称、となるから，前節までにおいては，錘やランプの高さを変数としYl=+ru芹a1(4)て問題を定式化してきた.この節以下では，紐が錘やY2=すぷ丈万(5)ランプにどのように配分きれるのかに着目して定式化することにしよう.こうすると，目的関数の形は以前となる.

したがって，目的関数は

仰1 幼)=す (mlM守+m21Ulマ)附より複雑なものになるが，そのかわり，許容領域は単となる.すなわち，体というきわめて単純な形の集合になる.

最大にするのが問題である.

(1)および(2)式の条件の下で(6)式を[例題 3] この例題では，図 4-1 のような仕掛けを前節の例題からも推察できるように， (2)式の条件が考える.すなわち，天井の 2 点 Poおよひrp 2 に両端を固問題になるのはきわめて特殊な場合なので，これは無定された長さ L の紐があり，線分 POP2上の 1 点に固定視しよう.そこで， Lagrange 乗数を λ として Lagrange

された滑車 P 1 にひっかけられている紐の ，〆'ーー、、POPl および

P 1 P2の間には，それぞれ動滑車Ql およびQ2 を介して錘ml およひr m2 が吊きれ，互いに引きあってバランスしている.その位置を求めたい.ここでも紐の目方はゼロ関数をsP(UI ， U2)=す (mlMヲ+m21Ul弓吉)(6一再)‑A(UI+U2‑L)と定義すればと考えよう.
天井に沿って POP2 を通過する水平な X軸を設ける.
線分POPl およびP 1 P 2 の長きをそれぞれ al およびぬとすr

よびめとすれば，紐の長きに関する条件はUI 十 U2= L，(1)Ul量~ a l,(2)U2 孟 a2となる.一方，目的関数は X 軸まわりのモーメントIIJしたがって，目的関数が最大になる条件は

mlUl、

(8)

夜宗士ZT-Am2UZ

U宗コ7=A(9)となる.図 4 ‑ 1 からも明らかなように，紐と鉛直線,uu//ft(10)(ll)+」'

式

町、

120d

万ヨゴ 3 ト卓

す4r400m2

三一つ出ヵ

mlu 一
一一aa==哨，〉』

pivpLVJt

曲伯尚のなす角度を各々 8 1 および&とすれば_,2c倒。l4-1(12)H_,

2cosfh図(7)、 l

L2 1Ulコlを得る.

紐の点目 -P 1 間および P 1 -P 2 聞の部分の長きを Ul お、112fT"2U2る .X軸と直交，下向きに Y軸をとり，動滑車 Ql およびQ2の U座標を仇およびY2 とする.

mlUl

grad 2'=12/たal(I司となる.これらの式は，この例題でもまた Lagrange 乗
数A が紐にかかる張カであることを示している.

ゃない
〒 223

ひろし慶応義塾大学理工学部
横浜市港北区日吉 3-14-1

2
16(44)(12)および(1司式では，求めるべき変数がcos 81 およびcosfh になっているから，制約条件(1) もこれらの変数© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

で表現しておかなければならない.図 4-1 からも明という関数のグラフを画き，これかららかなようにt(cos8)=L1u1sin81=a1infh=a2U2sという関係が成立するような COS 81 を求めればよい.

(15)

図 4-2 には，そのようなグラフの一例が示きれていという関係が成立するから，これを(1)式に代入すればる.また，図 4-2 ではさらに，これから仇および命が読みとれるようになっている.

L= -一一一+一一一一----ß:1.-.;,+---f!:1sin8 sinfh
1I

この図からもわかるように関数t(cos 81) は COS 81 の=士缶τγ+士告言0を得る.さらに， (12)および(13)式の関係を代入すれば，

L=。1)

(14)

戸 a1 ー+-----r= U2(1司Jl-(号r JlーほY

大部分の値に対してほぼ水平に寝た形状を示している.

したがって，水平な直線

t=L(22)との交点によって COS 81 を求めることは誤差を生じやすい.正確な値を求めるには相応の数値解析的配慮がという方程式を得るから，これを λ について解いて，こ必要になるのだが，本稿の範囲をこえるので，これ以れから仇および弘あるいは飢および U2 を求めればよ上は立入らない.

6)
このことの力学的な意味を考えてみよう.いま ， (し、.

/"ーー、、

式に (1)式の関係を代入して，目的関数を POP1 に配分きあるいはまた仰およひt(13)式から得られるように，

C回 fh

笠呈

C凶 81(18)れる紐の長き U1 だけの関数として書けばm1

サ似仰仰(ω
(U1仇昨1という関係があるから，これを(16)式に代入して=づ

U1E[a1 , L 一 a2]

a1 〒- + ‑ ‑ ‑ ‑ ; G ( 1 9 )v トt回 281

人1m2n ¥'となる.この関数の形状の一例をプロットしたのが図-,.
11 一 l 一一ιCOS :111JV ¥m1という式を導き，これから直接COS 81 を求めてもよい.
そのためには，t(c問。'1 )= r.一色? ^ +---,

ι-c回 2 I九人

a21m2,

司白側‘n ¥-,.
11 一 l 一~cos 仇 lym1ω)

4-3 である.

この図にも見るとおり，この関数はその定義域の中央においてきわめて平坦に広がる部分をもっている.
すなわち，この部必では U1 の値が変化しでも，系の 1次のモーメントはあまり変化しない.いいかえれば，紐がずれて，錘が‘最適な'位置を離れても，滑車Q1 ，P 1 および Q2 に Co岨10mbマサ、ソがあれば，その場所で止L(ﾀ)まってしまうことになる.

10

別のいい方をすれば，この機構を‘秤'として物の目方を測ろうとするのは無理である.確かに，側式からすれば，紐と鉛直線がなす角度から，それぞれの錘5の重きの比を知ることができるわけだが，上に述べた
COS81。

ψ(U1)

30'
L=1O.
8ー==460'890'
m1=1.0 m ,=1.2

a1=l.O a ,=1. 0-3.5
図1994 年 4 月号

Ujaj

L~a ，,

aj=l.O a =2.0
図4-2
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

L=4.8‑10.8
4-3(45)2
17

一G

LL

一α0司ら士か工一nu

一nua?十U 一一成 JJa脚色+C一2

L41A一nL

ぴ一

1aaτMA

つ出=mJ山

一ぬ一a

仇一+品山一+℃飢ーし=一一が=ぬ仏叫た仇

一島 m

(26)

=42ぬ‑.cos8=+~~~~
2a1+a2/Vー (a1 +a2)2v

図M(L ， m)=+mJI2ー (a1+ ω2一方，この性質を逆手にとって利用したのが，図 4-4 に示すランプの無定位懸垂装置である.筆者は，このような装置を 15年ほど以前に，東京世田谷のポロ市で見かけた.この装置が機構上図 4 一 1 のそれと等価であることは明らかであろう.この装置では，ランプを上下して，そっと手を放せば，ランプはその位置にとどまる.不均合があったとしても，滑車のもつ Cou10mbマサツがひきうけてくれる.

。113 の注意を与えておこう.
(18) 式において=8.
!
=:8となる.

ところで，図 4 ‑1 の機構は， ml= 聞の場合，図 4-5 の右の図の機構と力学的に等価であることに注意しよう.右の機構は天井の滑車 Pd: ，動滑車Q2 とその錘がとりはずされている.全体としての重きは半分になるわけだが，右の系の 1 次のモーメントもやはり

M1(L.m) → m';V ー (a1 +a2)2T=n‑m2c倒。

。却である.いいかえれば，これらの装置に葦をして中味(24)が成立する.さらに， (16) 式にこの関係を代入して整理すればが見えないようにすれば， P。あるいは Po' で紐をつまんでみるかぎり，両者の区別がつかない.

5. 組の長さの配分による定式化その 2sin8=竺生(25)が得られる.そこでこれを (U) および (15) 式に代入すれば、TI¥P

一勾配法と緩和法[例題 4] この例題では図 5 -1 のような仕掛けを考える.例題 3 と異なるのは，錘が 1 つふえたということだけである.

例題 3 と同様に定式化すれば，紐の長さに関する制
約条件は+U, +u
a=L, U1 ミ a" u，~~， ua ミlÞj

U1であり，目的関数は 4 節の (6)式と同様にして

図218(46)

削っとき，釣合いに必要な張カ T は共に~=~釣合いの位置では，まず，側となる.また，点 P。あるいは Po' で紐をはずし，指でもきて，図 4 ‑ 1 の装置において2，側となる.また，系がもっ 1 次のモーメントは4-4

理由から精度に難があり，使いものにならない.となる場合について

自国

図4-5

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

5-1

オペレーションズ・リサーチ(1)

るのは，この最終位置であるから，錘が準静的に動く州，ぃ)=七 mJlJヲ +m2Mヲ+m3/認=瓦(2)となる.

ものとして，これを追ってみよう.
図 5-2 の上で錘の動きを考えれば，錘の準静的な動きを見れば，局所的に見て目的関数(4)が，つねに一解法 A 勾配法

いま (2) 式において(1)式を用いて変数偽を消去すれば，
U1+t俗芸三 L 一ぬ.

番小きくなる方向を向いているはずである.したがって，錘の動きが図 5-2 上で作る軌跡は，

U1~ah(3)tぬ主主~の下で目的関数

告 =gradψ(5)あるいは，成分ごとに書けば山，め)=七 m必ヲ +m2必-a~
十 m3 .J (L-U1 一助)2_ a~(4)を最大化することになる. (4)式の一例について等高線図を画いたのが図 5-2 である.頂上は許容領域(3) の内部にあり，頂上部分は平たく広がった丘を作ってい12=[ 並 ldt

δ唱11(6)d笠豆ý!.-dt

δ唱ぬという微分方程式で表わされる.ここにt:時間に相当するパラメターるのが見える.

きて，図 5 ‑ 1 の仕掛けに戻って考えてみよう.紐をピンと張らせたまま3 つの錘に任意の位置をとらせて，指でおさえてしまおう. (明らかに 2 個をおさえれば錘はどれも動かない.)一一一指をはなせば，錘は動いて (4)式を最大化する位置に移る.だから，このときの動きを追っていけば，われわれの最大化問題の解が得られるはずである.

(7)である.きらに具体的に書けば

dU
1̲ 1r 倒的""1"'1
dt‑ 2L/玩亡苛

問
1""3 (L-U1-U2)¥.
LJ""'~/..， I/ (L‑U1‑U2)2-a~ J(8)1rm2n2fU2Ft2dt‑ 2L/瓦二 a~m3""
3 (L-U1¥L.
.
< "'1一ぬ)U"1I/ (L‑U1‑U2)2-a~ J(9)dぬflf‑となる.

この微分方程式を，たとえばRunge-Kutta法など適しかし，これを空気中(あるいは真空中)で行なえ切な数値的方法によって解けば，その解は等高線と直ば，その動き方は Newtonの法則に従い. 2 階の微分方

交しつつ目的関数の丘を登り，この数理計画問題の最程式によって記述されることになるので，これを追う適解に収束する.実際，そこではのはちょっと面倒である.そこで，装置全体を，たとえばシリコン・オイルのような粘性の高い流体の中につけたと考えて，おさえていた指を同時にはなせば，錘はゆっくりと‘準静的に'動いて，やはり (4)式を最大にする最終位置に近づく.われわれが興味の対象とすとなり，微分方程式(5) の右辺がゼロになっている.このようにして最適値を求める方法は. gradient法あるいは勾配法と呼ばれている.
図 5-2 の数値例について，いくつかの初期点から，上の微分方程式の数値解を計算し，解曲線を等高線図

1aj

mi6日 000 0.
9002 8.
000 0.
900310.000 1.200
L=33.0

U21(0)

grad~=O上に画いたのが図 5-3 である.解曲線がどれも目的
U2卜\
15.
0

15.
0ムト\¥r士 Eよミ 〉ミ ￨¥竹 トよ だ ~ ¥/ F、、 ノペtミミ 〉巴 卜\

10.
0

10.
08.
08.
0

1994 年 4 月号

u1phd

図nυ‑6.
0.
f

I ~ 、〉 ~ ぐ三た こヨ 二ト t¥

ドーー 内イ ，イ レノ

6.
010.
0
図5-2© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

¥i¥ ト\ノ￨¥15.
0U15-3(47)219関数の頂上に集まっていくことが見てとれよう.
ところで，この最終値を数値的に求めることだけに目標を絞れば，微分方程式の解曲線をていねいに追う必要はない.グラジエント方向に沿って進み，頂上で収束する趣旨にそって勾配法系のアルゴリズムにはい返せば，やがては系金体の 1 次のモーメントが最大化されるであろう.こんなやり方がうまく機能するかどうかを見てみることにしよう.

このため，3 変数UJ， U2 , U3が作る三角座標を用いることにしよう.図 5-4 に見るように許容領域(1)は，ろいろなヴァリエーションが考えられるし，また試みこれらの変数が作る 3 次元空間に浮んだ 1 枚の正三角られている.しかし，本稿ではこれらの取扱いには踏形である.そして，ある変数が一定値をとる点の集合み込まないことにする.

は，この正三角形上で平行な直線群をなし， Ul , U2 , tぬ解法 B 緩和法

前の解法では，錘をおさえていた指のそれが互いに 60。で交わってこの正三角形上の網目を同時にはなすことを考えた.しかし，錘を(滑車にを作る.これを切りとって紙面においたのが，すなわは触れないで)どれか 1 つだけ (mf とする)おさえてち，三角座標である.三角座標の目盛は，慣れないと他をはなしてみたらどうだろう?

読みにくいとはいうものの，もとの 3 次元空間を思い錘をおきえても，紐の方は許された範囲では自由に動き得るのだから，浮かべれば直ちにわかる.

紐の長きがL-Ufであるという条件の下で， mf以外の錘

図 5-5 に示すのは，目的関数(2)の等高線図を三角が作る 1 次のモーメントが最大になる.いいかえれば，座標上に示したものである.この図が結局のところ，前節の例題が‘解かれる'ことになる.

図 5-2 の等高線図を‘ちょっと引きのばして回転しそこで，錘を代わる代わるにおきえて，のこりの錘が作る系の 1 次のモーメントを最大化する操作を繰りたもの'であることは ， U l, U2 の許容領域(3)が，図 5-

4 上 UJ，U2平面上の小きな二等辺三角形であることからも容易にわかるであろう.

U3きてそこで， 1 つの変数めを固定し，他を動かして目L的関数を最大化するという操作は，三角座標上でいえば，座標軸のどれかに平行な直線を 1 つ選ぴ，これに沿って，目的関数の値が最大になる点を求めることに他ならない.
いま ， Ul を固定して，/kおよび鈎を動かして最適化したときのぬと偽の聞の関係を求めてみよう

Ul を固定してしまえば，の問題は 4 節問題と同じであるULag­

range 関数は,G2"(い)=す{mlMヲ+m2必ヲ,

u =6.0<:‑〆も<$>〆U3=a3't""''
1>ーーーーーーー

U2も1;

.
:
>

一『ーーーー~へ1;S
図5-4© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

もU2.
:
>
'"

図220(48)

u3=lO.Oも5-5

オベレーションズ・リサーチ

+開J函 -a~-À(U1+ ぬ+鈎 - L)}(11)となるが，ここで U1 は定数で，ぬと Zぬだけが変数であることに注意しておこう

U2および鈎で偏微分してゼロとおけば，それぞれ'"(12)

Ui‑ai=h(1司および12m1 ぬ2(2。

J(mi-mnui+aim~と，紐の全体の長さに関する条件から得られる.

定するときには偽=一定の直線とゐの交点を求めれば，

まれ、山問

す去、A

V4・フを固定した変数以外の変数が最適化されることになる.

m3Ua(14)万戸 a~ 一万戸 a~を得る.さらに整理すれば

三角座標上3 曲線 1"12•

13 を画き，この上で変数

U" U2. tぬを順に固定して他を最適化する操作を行なう

過程を示したのが図 5-6 である.次第に系全体とし

ua r;--;;--h 抑制金-1(瓦戸高奇克+a~m~(15)ての最適解に近づく様子が見られる.そしてこの過程
は，図 5 ‑ 1 の仕掛けにおいて，錘 mI， m2, m3 を順にという関係が得られる. (15)式によりぬが与えられればぬが得i られるし，ぬ m祉 U1

J(mi-mDui+aim~

U2 を固定するときには . U2= 一定の直線とら偽を固AU→制md 吟

尚一寸

つ Jv カる

一一一れ

1一2r一助ゐ

AM‑44'

べぴ可。日苛rYhU2ゐ:均一‑:ぬa2' 1 rYh ョ
τー =τ 「二手旦=;c -À=O
UU2

は，それぞれまた，おさえて他をはなすことに対応している.
このように，変数の一部を固定し，のこりの変数に

u1=L 一紘一ぬ(16)によって U1 カ寸専られる.こうして f辱られる Ul， U2， ぬを関する最適化を行なう操作を，固定する変数を取りかえつつ繰り返し，系全体の最適解を得ょうとする方法

三角座標上にプロットすれば 1 つの曲線になる.これを緩和法という.一般的にいって，緩和法が常に系全を体の最適解をもたらすという保証はないのだが，多く
1
1:U1 を固定した時の U2 およぴぬの間の関係を表わの実際的な問題については，大体においてうまくいく.

(1司

ところで，緩和法において固定する変数の選び方はと呼ぶことにしよう . U1 を固定して，ぬおよび偽の最適いろいろである.たとえば，この問題の場合についてす曲線値を求める操作は，三角座標上 U1 の値に対応する直線と曲線 A の交点を求めることになる.

POP3P
2Pl

全く同様にして，品々を固定したときのぬおよび偽の聞の関係を表わす曲線

ffi3(18)

13 :U3 を固定したときの U1 および U2の聞の関係を表(19)わす曲線

U3U2Ul

図5-6図1994 年 4 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

5-7(49)221U3G,

UU,
図5-9図 5-9 である.反復の回数は多少多くなるものの，最終的には最適解に近づくことが見てとれよう.
ヴァリエーション

緩和法については，さらにいろいろな変形や改良G図が考えられる.たとえば，図上の曲線 11，12. 13がほとんど直線をなしていることに着目して，このうち 1 本を選んで、これを特定しその上に沿って最適化を行な

5-8うという考え方も可能である.実際，共役勾配法といUl と偽だけを交互に固定しでもよい.これは，われる方法の中には、このような考え方にもとづくも

図 5 ‑ 1 において，滑車 P 1 およひ~P2 の所で交E に紐をのもあるが，本稿の範囲をこえるので，ここでは詳述おさえたりはなしたりする操作を繰り返すことに対応しないいえばしている.

222(50)(図 5 ‑ 8) これを三角図表上で試みたのが© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ