12.38 math.simplex - シンプレックスソルバー

Module: math.simplex ¶

線形計画問題をシンプレックス法で解く実装です。

Function: simplex-solve A b goal c ¶

{math.simplex} Aは m x n の数値配列、bは m個の数値のシーケンス、 cはn個の数値のシーケンスで、またgoalは :maximizeか:minimizeです。 この手続きは次の制約を満たす長さnのf64vectorであるxを返します: 制約条件 Ax <= b および x >= 0 のもとで、 内積 c . x が最大値もしくは最小値を取るx。

配列と2つのシーケンスは、全ての要素が数値でさえあればどんな型でも渡せます (配列についてはgauche.array - 配列参照)。内部的には、f64vectorと f64arrayが計算に使われます。 引数に渡した配列とシーケンスは変更されません。

bの要素は負であっても構いません。負の数がある場合、この手続きは 2-phaseシンプレックス法を使います。

制約が「定数項以上」である場合は、両辺の符号を反転して「定数項以下」の制約にしてください。 等しい制約がある場合は、あらかじめその関係を使って変数を減らすか、 「定数項以上」と「定数項以下」の制約を同時に与えることで解けます。

複数の解がある場合はどれか一つが返されます。 解が無い場合は#fが返されます。

;; Maximize x1 + x2 under constraints of
;;     x1 + 0.5*x2 <= 2.0   and
;;   3*x1 +   2*x2 <= 12.0

(simplex-solve '#,(<array> (0 2 0 2) 1 0.5 3 2)
               '#f64(2.0 12.0)
               :maximize '#(1 1))

  ⇒ #f64(0.0 4.0)