シンプレックス法をJavaScriptで

シンプレックス法をJavaScriptで:

（本記事は旧boiledorange73の記事です 2018年7月）

はじめに

線形計画問題とは、不等式で制約条件が課され、目的関数を最大化または最小化する変数を求める問題です。

線形計画法とは、線形計画問題を解く手法を言います（そのまんまです）。

線形計画法のプログラムをJavaScriptで書いてみました、というお話です。

シンプレックス法

線形計画法は複数ありますが、最もよく使われているのがシンプレックス法です。https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%B3%E3%83%97%E3%83%AC%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95 などを参照してみてください。

より具体的な実行手順として http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/Simplex_st.html をご覧ください。

二段階シンプレックス法

通常のシンプレックス法は、巡回する頂点の最初を原点としていますが、原点が制約条件を満たさない場合には、計算できないので、最適解かどうかはともかく、制約条件を満たす頂点から開始する必要があります。

これを実装したのが、二段階シンプレックス法です。

より具体的な実行として http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/TwoPhase.html をご覧ください。

ソース

https://github.com/boiledorange73/simplex.js にあります。2条項修正BSDライセンスです。

本記事のライセンス

この記事は クリエイティブ・コモンズ 表示 4.0 国際 ライセンスの下に提供されています。