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

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

ご利用にあたって

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

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

採録関数

線形計画法（シンプレックス法)
　　mpLPTrace(表示場所, モデル, 変数名, 制約名)　コード表示
　　rtn = mpLP(モデル, 変数名, 制約名)　コード表示

ごく基本的なＬＰ（線形計画法）問題をシンプレクス法により解を求めます。
・変数および制約式の個数は、それぞれ１０個以下を想定しています。
　計算誤差の影響は一切考慮していません。
・制約式≦定数項、０＜定数項　でなければなりません。

単に基底解を求めるだけでなく、シャドウプライスやレンジも求めます。

ケース１

右図のモデルを対象にします。
それを下の入力例の形式で入力すると、出力例が得られます。

入力例
　　　　　　　　　　　　　　製品
　　　　　　　　　定数項 　Ａ  Ｂ
    var モデル = [ [  0,   3,  2 ],　  // 目的関数：定数項＝０、製品の価格
                   [ 72,   4,  1 ],    // 原料制約：4*製品Ａ + 1*製品Ｂ ≦ 72
                   [ 48,   2,  2 ],    // 労力制約：2*製品Ａ + 2*製品Ｂ ≦ 48
                   [ 48,   1,  3 ] ];  // 電力制約：1*製品Ａ + 3*製品Ｂ ≦ 48
    var 変数名 = ["製品Ａ", "製品Ｂ"];
    var 制約名 = ["max", "原料","労力","電力"];

出力例  var rtn = mpLP(モデル, 変数名. 制約名) の結果
    rtn["解Ａ"][k][j]  最終タブロー
       k  [k][0]  [k][1]  [k][2]  [k][3]  [k][4]  [k][5]  [k][6]
       0   基底   定数項  製品Ａ  製品Ｂ   原料    労力    電力
       1   min      64      0       0     0.333    0.833     0
       2   製品Ａ   16      1       0     0.333   -0.167     0
       3   製品Ｂ    8      0       1    -0.333    0.667     0
       4   電力      8      0       0     0.667   -1.833     1
    rtn["解Ｂ"][j][*]　感度分析
       j  [j][0]  [j][1]  [j][2]  [j][3]    [j][4]  [j][5]
       0  変数名   価格   解の値  シャドウ  レンジ レンジ
                  定数項          プライス   下限   上限
       1  製品Ａ     3      16      0         2      8
       2  製品Ｂ     2       8      0         0.75   3
       3  原料      72       0      0.333    60     96
       4  労力      48       0      0.833    36     52.364
       5  電力      48       8      0        -0.5    0.455

ケース２

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

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

ケース１

問題
               需要地番号ｊ    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 = mpTLP(費用表, 供給地名, 供給量, 需要地名, 需要量)

出力データ
    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"]  供給量を１増加したたときの総費用の増加 

ケース２

割当問題
　　mpALP(表示場所, 金額表)　コード表示
　　rtn = mpALP(金額表)　コード表示

    rtn["最大金額"]
    rtn["最大割当"]
    rtn["最小金額"]
    rtn["最小割当"]

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

割当問題の解法としてハンガリー法が有名です。参考（Ｗｅｂテキスト）割当問題
しかし、「０要素を網羅する最小個数の線を引く」ことをプログラムで実装することが私にはできないままです。

それでｎ！の組合せの中から最大／最小のものを探索するという、あまりにも姑息な手段を採用した。これでもｎ＜８程度なら、計算時間を意識せずに解が求まります。

ケース１

入力
//                     職務
//                 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 rtn = mpALP(金額表);
出力
    rtn["最大金額"]= 25,　rtn["最大割当"][k][j]= [[3,4,0,2,1],]
    rtn["最小金額"]= 8,　rtn["最小割当"][k][j]= [[0,2,4,1,3],]

ケース２

動的計画法による最適資金配分
　　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であるとき、利益最大にする各投資への資金配分額を求めよ。」という意味です。

ケース１

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

入力
    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(表示場所, タイプ, 全容量, 体積, 利益[, 個数上限]) 　コード表示
　　最適解 = 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] が求められます。
このようにして、全部の品物を追加したときの解が求められます、

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

ケース１

入力
    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

ケース２