ヴァリニョンフレーム

ヴァリニョンフレーム

ヴァリニョンフレームは、ピエール・ヴァリニョンにちなんで名付けられた機械装置で、複数の店舗への商品の配送に最適な倉庫の位置を決定するために使用できます。最適とは、店舗から倉庫までの重み付き距離の合計が最小になることを意味します。フレームは、n 個の店舗に対応する n 個の穴が開いた板で構成され、n 本の紐が一方の端で結び目になっています。紐の端はそれぞれ 1 本ずつ穴に通され、板の下の重りに取り付けられています（図を参照）。摩擦や現実世界のその他の要因の影響を無視すると、紐は重りが穴に詰まるのを防ぐのに十分な長さがあり、また、どの重りも結び目を穴から引きずり出してテーブルの下に落とすほど重くない場合、結び目は平衡位置 になります。以下に示すように、その点は距離の 重み付き合計を最小にする最適な位置です。${\displaystyle \mathbf {x} _{1},...\mathbf {x} _{n}}$ ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {v} }$

（１）： .${\displaystyle \ D(\mathbf {x} )=\sum _{i=1}^{n}m_{i}\|\mathbf {x} _{i}-\mathbf {x} \|}$

最適化問題はウェーバー問題と呼ばれる。^[1]

機械問題 - 最適化問題

点ではすべての力の合計は0である${\displaystyle \mathbf {v} }$

穴の位置と錘の質量がの場合、i番目の弦に作用する力は大きさ（：重力定数）と方向（単位ベクトル）を持ちます。すべての力を合計し、共通項を消去すると、次の式が得られます。 ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$ ${\displaystyle m_{1},...,m_{n}}$ ${\displaystyle m_{i}\cdot g}$ ${\displaystyle g=9.81{\text{m/sec}}}$ ${\displaystyle {\tfrac {\mathbf {x} _{i}-\mathbf {v} }{\|\mathbf {x} _{i}-\mathbf {v} \|}}}$ ${\displaystyle g}$

（２）${\displaystyle \ \mathbf {F} (\mathbf {v} )=\sum _{i=1}^{n}m_{i}{\frac {\mathbf {x} _{i}-\mathbf {v} }{\|\mathbf {x} _{i}-\mathbf {v} \|}}=\mathbf {0} }$

（平衡点ではすべての力の合計はゼロになります！）

これは点の座標に対する非線形システムであり、ワイズフェルドアルゴリズム（下記参照）によって反復的に解くことができる^[2]${\displaystyle \mathbf {v} }$

式(1)と式(2)の関係は次の通りである。

（３） ${\displaystyle \ \mathbf {F} (\mathbf {x} )=\nabla D(\mathbf {x} )={\begin{bmatrix}{\frac {\partial D}{\partial x}}\\{\frac {\partial D}{\partial y}}\end{bmatrix}}.}$

したがって、関数は点で局所的極値を持ち、ヴァリニョンフレームは実験的に最適な位置を提供します。 ${\displaystyle D}$ ${\displaystyle \mathbf {v} }$

ヴァリニョンフレーム：例

レベルカーブ

例

次の例では、ポイントは

${\displaystyle \mathbf {x} _{1}=(0,0),\ \mathbf {x} _{2}=(40,0),\ \mathbf {x} _{3}=(50,40),}$

${\displaystyle \mathbf {x} _{4}=(10,50),\ \mathbf {x} _{5}=(-10,30)}$

そして重み

${\displaystyle m_{1}=10,\;m_{2}=10,\;m_{3}=20,\;m_{4}=10,\;m_{5}=5}$ 。

最適解（赤）の座標は であり、長さの最適な加重和は です。2番目の図は、和が等しいが最適ではない点からなる水準曲線を示しています。水準曲線は、加重和が一定レベルを超えない領域を割り当てるために使用できます。幾何学的には、これらは以下の方程式を持つ 暗黙の曲線です。${\displaystyle (32.5,30.1)}$ ${\displaystyle L_{\text{op}}=1679}$

${\displaystyle \;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;}$ （式（1）参照）。

ケースでは、レベル曲線は共焦点楕円である${\displaystyle n=2,m_{1}=m_{2}=1}$

特別なケース n=1 および n=2

• 1つが取得された場合。${\displaystyle n=1}$ ${\displaystyle \mathbf {v} =\mathbf {x} _{1}}$
• および の場合はとなります。${\displaystyle n=2}$ ${\displaystyle m_{2}>m_{1}}$ ${\displaystyle \mathbf {v} =\mathbf {x} _{2}}$
• の場合、点は線分上の任意の点となります（図を参照）。この場合、等高線（同じ 最適ではない和を持つ点）は、 それらの点を共通の焦点とする共焦点楕円となります。${\displaystyle n=2}$ ${\displaystyle m_{2}=m_{1}}$ ${\displaystyle \mathbf {v} }$ ${\displaystyle {\overline {X_{1}X_{2}}}}$ ${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2}}$

ワイズフェルトアルゴリズムと不動点問題

例の固定点決定としての反復：開始点（緑）、開始点（青）は 質量の中心です${\displaystyle \mathbf {v} _{0}=(25,15)}$ ${\displaystyle \mathbf {v} _{m}}$

式（2）の分子のベクトルを に、分母のベクトルを に置き換えて方程式を1について解くと次のようになる。^[3]${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {v} _{k+1}}$ ${\displaystyle \mathbf {v} _{k}}$ ${\displaystyle \mathbf {v} _{k+1}}$

（4）${\displaystyle \quad \mathbf {v} _{k+1}=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{\|\mathbf {x} _{i}-\mathbf {v} _{k}\|}}\,{\Bigg /}\sum _{i=1}^{n}{\frac {m_{i}}{\|\mathbf {x} _{i}-\mathbf {v} _{k}\|}}}$

これは反復処理を記述する。適切な開始点は、質量が点にある重心である。 ${\displaystyle m_{i}}$ ${\displaystyle \mathbf {x} _{i}}$

${\displaystyle \mathbf {v} _{0}={\frac {\sum _{i=1}^{n}m_{i}\mathbf {x} _{i}}{\sum _{i=1}^{n}m_{i}}}}$ 。

このアルゴリズムは ワイスフェルトアルゴリズムと呼ばれています。^[4]

式（4）は関数の不動点を決定するための反復式として見ることができる。

（5）${\displaystyle \quad \mathbf {G} (\mathbf {x} )=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{\|\mathbf {x} _{i}-\mathbf {x} \|}}\,{\Bigg /}\sum _{i=1}^{n}{\frac {m_{i}}{\|\mathbf {x} _{i}-\mathbf {x} \|}}}$

不動点方程式

${\displaystyle \quad \mathbf {x} =G(\mathbf {x} )}$

（固定小数点を参照）

数値問題に関する注意:
ここで説明した反復アルゴリズムでは、点が いずれかの点に近い場合、数値問題が発生する可能性があります。 ${\displaystyle \mathbf {v} _{k}}$ ${\displaystyle \mathbf {x} _{1},...\mathbf {x} _{n}}$

参照

• フェルマー点（ケース ）${\displaystyle n=3,m_{1}=m_{2}=m_{3}=1}$
• ヴァリニョンの定理
• 幾何中央値

外部リンク

• MathePrisma Uni Wuppertal: GeoGebra による Lösung eines Standort の問題
• ヴァリニョンのフレーム：数学的処理

参考文献

1. Z. Drezner、HW Hamcher:施設の場所、Springer、2004、ISBN 3-540-21345-7、7ページ
2. Horst W. Hamcher: Mathematische Lösungsverfahren für planare Standortprobleme、Vieweg+Teubner-Verlag、2019、ISBN 978-3-663-01968-8、31ページ
3. Karl-Werner Hansmann : Industrielles Management、De Gruyter Verlag、2014、ISBN 9783486840827、S. 115
4. 施設の所在地については9ページを参照

• ウーヴェ ゲッツェ: Risikomanagement、Physica-Verlag HD、2013、ISBN 978-3-642-57587-7、S. 268
• アンドリュー・ウッド、スーザン・ロバーツ著『経済地理学』テイラー＆フランシス、2012年、ISBN 9781136899478、22ページ
• HA アイゼルト、カール-ルイ サンドブロム:オペレーション リサーチ、シュプリンガー ベルリン ハイデルベルク、2010 年、ISBN 9783642103261、239ページ
• ロバート・E・キューネ著『一般均衡経済学』、パルグレイブ・マクミランUK、1992年、ISBN 9781349127528、226ページ