スタートページ＞ JavaScript＞ ライブラリ目次

数理計画法 JavaScript関数ライブラリ(mp.js)の利用解説書

ご利用にあたって

線形計画法や動的計画法などの分野での基礎的な計算手法を JavaScript のライブラリとしてまとめたものです。
別シリーズ「Ｗｅｂテキスト」での活用を目的としたもので、小規模の素直な問題に限定されています。
単に結果を戻す「Return]タイプと、結果までの処理経過を示す「Trace」タイプがあります。

ソースコードを公開しています。ご利用は自由ですが、信頼性や効率性への保証はありません。

採録関数

mpLP 線形計画法（シンプレックス法)基準形
　　mpLPTrace(表示場所, 基幹変数名, 制約式名, 係数表, 定数項, 目的関数, MinMax); 　コード表示
　　var [最終タブロー, 基底変数名, 感度分析表]
　　　 = mpLP(基幹変数名, 制約式名, 係数表, 定数項, 目的関数, MinMax); 　コード表示

• ごく小規模なＬＰ（線形計画法）問題をシンプレックス法により解を求め、感度分析表も作成します
• 比較子はすべて"<"、定数項は非負でなければなりません。
• 計算誤差の影響や不定解の処理などは一切考慮していません。

ケース１

次の制約条件
　制約１：　４*製品Ａ + １*製品Ｂ ≦ ７２
　制約２：　２*製品Ａ + ２*製品Ｂ ≦ ４８
　制約３：　１*製品Ａ + ３*製品Ｂ ≦ ４８
の下で、目的関数
　　　　　　３*製品Ａ + ２*製品Ｂ　→　max
のモデルを次のように記述します。

ケース２

mpLP1 線形計画法（シンプレックス法)罰金法
　　mpLP1Trace(表示場所, 基幹変数名, 制約式名, 係数表, 比較子, 定数項, 目的関数, MinMax); 　コード表示
　　var [最終タブロー, 基底変数名, 感度分析表]
　　　 = mpLP1(基幹変数名, 制約式名, 係数表, 比較子, 定数項, 目的関数, MinMax); 　コード表示

• ごく小規模なＬＰ（線形計画法）問題をシンプレックス法により解を求め、感度分析表も作成します
• 比較子に"<","=",">" 、負の定数項が使えます。そのとき罰金法が適用されます。
• 計算誤差の影響や不定解の処理などは一切考慮していません。

●比較子に "＝" がある場合、感度分析表は不完全です。Infinity と表示されても、有限値であることがあります。

ケース１（基準形　比較子がすべて＜）

次の制約条件
　制約１：　４*製品Ａ + １*製品Ｂ ≦ ７２
　制約２：　２*製品Ａ + ２*製品Ｂ ≦ ４８
　制約３：　１*製品Ａ + ３*製品Ｂ ≦ ４８
の下で、目的関数
　　　　　　３*製品Ａ + ２*製品Ｂ　→　max
のモデルを次のように記述します。

ケース２（罰金法　比較子に＝や＞がある）

次の制約条件
　制約１：　４*製品Ａ + １*製品Ｂ ≦ ７２
　制約２：　２*製品Ａ + ２*製品Ｂ ＝ ４８
　制約３：　１*製品Ａ + ３*製品Ｂ ≧ ２４
の下で、目的関数
　　　　　　３*製品Ａ + ２*製品Ｂ　→　max
のモデルは次のようになります。
　　var 基幹変数名 = ["製品Ａ","製品Ｂ"];
　　var 制約式名 = ["制約１","制約２","制約３"];
　　var 係数表 = [[4,1],[2,2],[1,3]];
　　var 比較子 = ["<","=", ">"];
　　var 定数項 = [72,48,24];
　　var 目的関数 = [3,2];
　　var MinMax = "max";
Trace Return

ケース３

mpLP2 線形計画法（シンプレックス法)二段階法
　　mpLP2Trace(表示場所, 基幹変数名, 制約式名, 係数表, 比較子, 定数項, 目的関数, MinMax); 　コード表示
　　var [最終タブロー, 基底変数名, 感度分析表]
　　　 = mpLP2(基幹変数名, 制約式名, 係数表, 比較子, 定数項, 目的関数, MinMax); 　コード表示

• ごく小規模なＬＰ（線形計画法）問題をシンプレックス法により解を求め、感度分析表も作成します
• 比較子に"<","=",">" 、負の定数項が使えます。そのとき二段階法が適用されます。
• 計算誤差の影響や不定解の処理などは一切考慮していません。

●比較子に "＝" がある場合、感度分析表は不完全です。Infinity と表示されても、有限値であることがあります。

ケース１（基準形　比較子がすべて＜）

次の制約条件
　制約１：　４*製品Ａ + １*製品Ｂ ≦ ７２
　制約２：　２*製品Ａ + ２*製品Ｂ ≦ ４８
　制約３：　１*製品Ａ + ３*製品Ｂ ≦ ４８
の下で、目的関数
　　　　　　３*製品Ａ + ２*製品Ｂ　→　max
のモデルを次のように記述します。

ケース２（二段階法　比較子に＝や＞がある）

次の制約条件
　制約１：　４*製品Ａ + １*製品Ｂ ≦ ７２
　制約２：　２*製品Ａ + ２*製品Ｂ ＝ ４８
　制約３：　１*製品Ａ + ３*製品Ｂ ≧ ２４
の下で、目的関数
　　　　　　３*製品Ａ + ２*製品Ｂ　→　max
のモデルは次のようになります。
　　var 基幹変数名 = ["製品Ａ","製品Ｂ"];
　　var 制約式名 = ["制約１","制約２","制約３"];
　　var 係数表 = [[4,1],[2,2],[1,3]];
　　var 比較子 = ["<","=", ">"];
　　var 定数項 = [72,48,24];
　　var 目的関数 = [3,2];
　　var MinMax = "max";
Trace Return

ケース３

mpLPDual 線形計画法（主問題→双対問題）
　　mpLPDual(主表示場所, 双対表示場所,
　　　　基幹変数名, 制約式名, 係数表, 定数項, 目的関数); 　コード表示

• 線形計画の主問題を双対問題のモデルに変換し、その最適解を求めます。
• 主問題は基準形で、比較子はすべて"<"、定数項は非負。最大化問題とします。
• 双対モデル（入力形式）は別ウインドウに表示されます、
• 主問題のタブローは「主表示場所」に緑色で、双対問題のタブローは「双対表示場所」に青色で表示されます。
• 双対問題の解法には二段階法を用いています。
• 計算誤差の影響や不定解の処理などは一切考慮していません。

ケース１

主問題：次の制約条件
　制約１：　４*製品Ａ + １*製品Ｂ ≦ ７２
　制約２：　２*製品Ａ + ２*製品Ｂ ≦ ４８
　制約３：　１*製品Ａ + ３*製品Ｂ ≦ ４８
の下で、目的関数
　　　　　　３*製品Ａ + ２*製品Ｂ　→　max
のモデルを次のように記述します。

双対問題は、次のようになります。
　変数１：　４*制約１ + ２*制約２ + １*制約３ ≧ ３
　変数２：　１*制約１ + ２*制約２ + ３*制約３ ≧ ２
の下で、
　目的関数：７２*制約１ + ４８*制約２ + ４８*制約３　→　min
　　これをmax にするために、正負反転して
　目的関数：－７２*制約１ － ４８*制約２ －８*制約３　→　max

　双対モデル（実行結果は別ウインドウに表示）
　　var 基幹変数名 = ["制約１", "制約２", "制約３"];　// ←　主制約式名
　　var 制約式名 = ["製品Ａ","製品Ｂ"];　// ←　主基幹変数名
　　var 係数表 = [[4,2,1], [1,2,3]];　// ←　主係数表の転置行列
　　var 定数項 = [3, 2];<　// ←　主目的関数
　　var 目的関数 = [-72, -48, -48];　// ←　主定数項
　　var 比較子 = [">",">"];
　　var MinMax = "max";

ケース２

輸送問題
　　mpTransTrace(表示場所, 費用表, 供給地名, 供給量, 需要地名, 需要量);　コード表示
　　rtn = mpTrans(費用表, 供給地名, 供給量, 需要地名, 需要量);　コード表示

供給地ｉの供給量と需要地ｊの需要量と、ｉ→ｊの単位輸送費用を与えて、総輸送費用を最小化するように、ｉ→ｊの最適輸送量を計算します。
　北西隅の方法により初期解を得て、Ｕ－Ｖ法により解の改善を行い、最適解を求めます。
　すべての入力値は正の整数で、Σ供給量 = Σ需要量 でなければなりません。

ケース１

問題
　　　　　　　 　　　　　ｊ　　　0　　　　 1　　　　 2　　　　 3
　　　　　　　　　　　　　　┌───────────────────┐
　　　　　　　　　　　　　　│需要地Ａ　需要地Ｂ　需要地Ｃ　需要地Ｄ│　需要地名
　　　　　　　　　　　　　　├───────────────────┤
　　　ｉ　供給地名　供給量　│　12　　　　20　　　　16　　　　18　│　需要量
　　　　　┌────┬───┼───────────────────┤
　　　0　│供給地Ｘ│　18　│　 7　　　　　3　　　 　2　　　　 10　│
　　　1　│供給地Ｙ│　22　│　 9　　　　　3　　 　　6　　　　　8　│　費用表（単価）
　　　2　│供給地Ｚ│　26　│　 8　　　　　7　　 　　8　　　　　6　│
　　　　　└────┴───┴───────────────────┘
入力データ
　　var 供給地名 = ["供給地Ｘ", "供給地Ｙ", "供給地Ｚ"];
　　var 供給量 = [18, 22, 26];
　　var 需要地名 = ["需要地Ａ", "需要地Ｂ", "需要地Ｃ", "需要地Ｄ"];
　　var 需要量 = [12, 20, 16, 18];
　　var 費用表 = [ [ 7, 3, 2,10],
　　　　　　　　　 [ 9, 3, 6, 8],
　　　　　　　　　 [ 8, 7, 8, 6] ];
　　var rtn = mpTrans(費用表, 供給地名, 供給量, 需要地名, 需要量);
出力データ
　　rtn["輸送表"]
　　　　　　　0　1　 2　 3
　　　　 ┌─────────┐
　　　0　│　2　 0　16　 0　│
　　　1　│　2　20　 0　 0　│
　　　2　│　8　 0　 0　18　│
　　　　 └─────────┘
　　rtn["総費用"] = 296
　　　　　　　　　 0　　1　　2　　3
　　　　　　　 ┌──────────┐
　　　　　　　│　7　　1　　2　　5　│ rtn["v"]　需要量を１増加したたときの総費用の増加
　　　　┌──┼──────────┤
　　　0 │　0 │　0　　2　　0　　5　│
　　　1 │　2 │　0　　0　　2　　1　│ rtn["評価表"]　輸送量を１増加したたときの総費用の増加
　　　2 │　1 │　0　　5　　5　　0　│
　　　　└──┴──────────┘
　　　　　└ rtn["u"]　供給量を１増加したたときの総費用の増加

ケース２

割当問題 mpAssg

　　　　　　　　　　職務
　 　　　　　　　0　1　2　3　4
　　　　　　 ┌─────────┐
　　　　　0　│　9　5　1　9　7　│
　　　担　1　│　2　8　2　7　5　│
　　　当　2　│　1　3　9　5　9　│
　　　者　3　│　8　7　2　6　4　│
　　　　　4　│　2　3　6　2　8　│
　　　　　　 └─────────┘

割当問題とは、ｎ人の担当者とｎ個の職務があり、それぞれの割当てによる金額表(効果あるいは費用の表）が与えられたとき、総金額が最大あるいは最小の割当を求める手法です。

ここでは、最小化を標準にしています。
最大化をするには、上の表の要素をすべて負数にすればよいのですが、正数にするため、表中の最大要素（金額表[0」[0]~=9）を見つけ、その値をｚとして、全要素からzから引くのが一般的です。
しかしここでは MinMax を "max" とすることで、関数がこの操作を行います。

上例の最小化問題での割付表は、[ [0,2], [1,0], [2,1], [3,4], [4,3] ] になり、
金額は、1 + 2 + 3 + 4 + 2 = 12 になります。

ハンガリー法
　　mpAssgHunTrace(MinMax, 金額表)　コード表示
　　var 割当表 = mpAssgHun(MinMax, 金額表)　コード表示

私の能力により、次の限界があります。
ハンガリー法の特徴は「０要素を網羅する最小個数の線を引く」ことにあります。目視で試行錯誤するのは比較的容易ですが、私にはそのアルゴリズムを作れませんでした。それで「０の個数が最大になる行、あるいは列に線を引く」ことの繰り返せば少ない線数になるだろう」という手段にしていますが、それが最小であるとの保証はありません。不完全な段階で最適と判断する危険性があります。
最適解に到達したとき、「行あるいは列で０の個数が一つのものが最適割当だ」としています。そのため複数の解があるときの判断ができず、最適割当が存在しないとい結論になる危険性があります。

ケース１

入力
　var MinMax = "min";
　var 金額表 = [ [3, 8, 1, 2],
　　　　　　　　　 [3, 2, 4, 5],
　　　　　　　　　 [3, 1, 2, 4],
　　　　　　　　　 [7, 4, 2, 2] ];
　　var 割当表 = mpAssgHun(MinMax, 金額表);
出力
　　割当表 = [[0,2],[2,1],[1,0],[3,3] ];
　　　（担当者０は職務２、担当者２は職務１、… に割当）

ケース２

全ケーススキャン
　　mpAssgScanTrace(表示場所, MinMax, 金額表)　コード表示
　　var 割当表 = mpAssgScan(MinMax, 金額表)　コード表示

担当者、職務の数がｎのとき、ｎ！通りの組合せがあります。それぞれに金額表の値をｔれて計算すれば、最小化・最大化での最適割当が求められます。複数解のすべてを発見できます。
最も確かな解法ですが、ｎが大きくなると極度に計算負荷が増大します。ｎ＜８程度が限度でしょう。

ケース１

入力
　　var MinMax = "min";　　　// 最小化
　　　　　　　　　　　職務
　　　　　　　 　 0　1　2　3　4
　 var 金額表 = [[1, 3, 4, 5, 2],　　// 0
　　　　　　　　 [3, 5, 2, 2, 6], 　 // 1 担
　　　　　　　　 [1, 2, 5, 8, 5],　　// 2 当
　　　　　　　　 [2, 3, 4, 6, 2],　　// 3 者
　　　　　　　　 [2, 5, 1, 3, 4]];　 // 4
　 var 割当表 = mpAssgScan(MinMax, 金額表);
出力
　　割当表 = [[0,2,4,1,3]]
　　　職務0 には 担当者0 、職務1には 担当者2、職務2には 担当者4 … が最適割当になる。
　　　最適解が複数になることもあり。割当表は２次元配列になる。

ケース２

動的計画法による最適資金配分
　　mpSaitekiHaibunTrace(表示場所, 全資金, 利益表)　コード表示
　　rtn = mpSaitekiHaibun(全資金, 利益表)　コード表示

動的計画法により、
　　　制約条件：Ｑ＝x₀ + x₁ + x₂ + ・・・ + x_n ≦ Ｑmax　　0 ≦ x_i ≦ xmax_i
　　の下で
　　　目的関数：R_x = f(x₀) + f(x₁) + f₂(x₂) + ・・・ + f_n(x_n) →最大
を最大化する x_i を求めます。

これは、「ｎ個の投資案件があり、案件ｉに x_i の資金を配分したときの利益が f_i(x_i) であるとしたとする。全投資のための資金の上限がＱmaxであるとき、利益最大にする各投資への資金配分額を求めよ。」という意味です。

ここでは、単純にするために、f(x_i) を　数値 f[x][i] で指定し、前の f[x][i-1] との間を
　　step　 [i] までは　f[x][i-1]で　[i]になったら階段状に f[x][i] になる。
　　line　２点を直線で結ぶ
で指定します。これは f[x] 全体に適用されます。

ケース１

案件０，１，２の案件への資金配分による利益が右図のとおりだとします。
点線の部分は、これ以上配分しても利益は変わらない（無駄な配分）ことを示します。
それを、下の利益表の形式で記述します。
解は、最適解のように２次元表で得られます。
解は与えた全資金だけでなく、資金が０，１．２，…、全資金について得られます。

入力
var 全資金 = 8;
　 // type x0,f0 x1,f1
var 利益表 = [ ["step", 1, 8 ], // 案件０
["line", 1, 5, 3,10 ], // 案件１
["line", 3, 5, 4,15 ] ]; // 案件２
var 最適解 = mpSaitekiHaibun(全資金, 利益表):
出力（最適解）
　　　　　　　　案件0　　　 案件1　　　 案件2
　　　　　 　資金　利益　資金　利益　資金　利益
　q↓i→　　　0　　 1　　 2　　 3　　 4　　　5
　　0　　　　0　　 0　　 0　　 0　　 0　　 0
　　1　　　　1　　 8　　 0　　 0　　 0　　 0
　　2　　　　1　　 8　　 1　　 5　　 0　　 0
　　3　　　　1　　 8　　 2　　 7.5　 0　　 0
　　4　　　　1　　 8　　 3　　 10　　0　　 0
　　5　　　　1　　 8　　 0　　 0　　 4　　 15
　　6　　　　1　　 8　　 1　　 5　　 4　　 15
　　7　　　　1　　 8　　 2　　 7.5　 4　　 15
　　8　　　　1　　 8　　 3　 10　　 4　　 15

ケース２

ナップザック問題
　　mpKnapsackTrace(表示場所, タイプ, 全容量, 体積, 利益[, 個数上限]) 　コード表示
　　var 最適解 = mpKnapsack(タイプ, 全容量, 体積, 利益[, 個数上限]) 　コード表示

ナップザック問題とは、ｎ個の品物について、体積 w[i] とナップザックに入れることの利益 f[i] を与えて、
　　　個数制約：0 ≦ x[i] ≦ 上限個数[i]
　　　容量制約：∑w[i]*x[i] ≦ ナップザック容量
　の制約で
　　　目的関数：∑f[i]*x[i]
を最大化する x[i] を求める問題です。

その代表的解法として最適性の原理による動的計画法があります。
何らかの方法で i-1 までの品物について、容量 q を配分したときの最適配分 p[i-1][q] が求められているとします。
i = 0 のとき、一つしか品物がないので p[0][q] = f[0]*x[0] です。
品物 i を追加したとき、
　　ａ：品物 i を入れなかったとき、その利益は p[i-1][q] のままです。
　　ｂ：x[i] 個入れるときの利益は、次の合計になります。
　　　　　　品物 i での利益は、f[i]*x[i] となり、w[i]*x[i] の容量を使います。
　　　　　　品物 i-1 までの利益は、容量残 = q-w[i]*x[i] なので p[i-1][容量残] になります。
　　aが大ならば、品物ｉを入れないので、以前の品物構成は変わらない
　　bが大ならば、品物ｉを入れる。以前の最適配分は p[i-1][容量残]
これにより、品物 i を追加したときの最適配分 p[i][q] が求められます。
このようにして、全部の品物を追加したときの解が求められます、

タイプ
ナップザックに入れる個々の品物の個数により、次の３タイプがあります。
　　タイプ=1　品物は１個だけ
　　タイプ２　個数は任意
　　タイプ３　個々の品物に上限がある

注意
　　データは全て正整数で与えてください。
　　数値は、なるべく小さい値になるよう単位を調整してください。
　　　全容量は２０以下、体積は１０以下を想定しています。
　　タイプ３以外は個数上限は不要です。

ケース１

入力
　　var タイプ = 3;　 //　３＝上限指定
　　var 全容量 = 8;
　　var 体積 = [2, 4, 1, 3];
　　var 利益 = [3, 7, 1, 8];
　　var 個数上限 = [2, 2, 3, 1];
　　var 表示場所 = "mpKnapsackTest1表示場所";
　　// タイプ１・２のとき
　　最適解 = mpKnapsack(タイプ, 全容量, 体積, 利益);
　　// タイプ３のとき
　　最適解 = mpKnapsack(タイプ, 全容量, 体積, 利益, 個数上限);
出力　最適解 = mpKnapsack(表示場所, 全容量, 体積, 利益, 個数上限)　の戻り値
　　q↓i→　[q][0] [q][1] [q][2] [q][3]
　　 [0]　　　0　　　0　　　0　　　0
　　 [1]　　　0　　　0　　　1　　　0
　　 [2]　　　1　　　0　　　0　　　0
　　 [3]　　　0　　　0　　　0　　　1
　　 [4]　　　0　　　0　　　1　　　1
　　 [5]　　　1　　　0　　　0　　　1
　　 [6]　　　0　　　0　　　3　　　1
　　 [7]　　　0　　　1　　　0　　　1
　　 [8]　　　0　　　1　　　0　　　1

ケース２