Location : Home > Languages > Perl > Package
Title : Math::LP
 		Toolbox Logo

名称

　Math::LP - オブジェクト指向インタフェースの線形計画法

概要

use Math::LP qw(:types);             # 最適化タイプのインポート
use Math::LP::Constraint qw(:types); # 制限式タイプのインポート

# 新たな LP の定義
$lp = new Math::LP;

# LP に対する変数の定義
$x1 = new Math::LP::Variable(name => 'x1');
$x2 = new Math::LP::Variable(name => 'x2');

# 目的関数 to x1 + 2 x2 の最大化
$obj_fn = make Math::LP::LinearCombination($x1,1.0,$x2,2.0);  
$lp->maximize_for($obj_fn);

# 制限式 x1 + x2 <= 2 を追加
$constr = new Math::LP::Constraint(
   lhs  => make Math::LP::LinearCombination($x1,1.0,$x2,1.0),
   rhs  => 2.0,
   type => $LE,
);
$lp->add_constraint($constr);

# LP を解いて出力
$lp->solve() or die "Could not solve the LP";
print "Optimum = ", $obj_fn->{value}, "\n";
print "x1 = ", $x1->{value}, "\n";
print "x2 = ", $x1->{value}, "\n";
print "slack = ", $constr->{slack}, "\n";

説明

　Math::LP パッケージは混合整数線形問題を定義し解くオブジェクト指向のインタフェースを提供する。ソルバとして lp_solve ライブラリを利用している。このことは２つの方法があることに留意して欲しい。LP は Math::LP を用いて定義され、lp_solve データ構造に変換され、lp_solve 関数を用いて解かれる。lp_solve 構造を把握して計算と探査のために Math::LP オブジェクトに変換することは可能ではない。 Perl でそのように処理したいなら替わりに Math::LP::Solve パッケージを使うこと。
　LP を構成する論理的な方法は以下の通り。

  1. Math::LP::Variable オブジェクトを構築する。整数変数があってもよい。
  2. 変数で目的関数と制限式として使い Math::LP::LinearCombination オブジェクトを構築する。
  3. LP を解く。
  4. Math::LP::Variable オブジェクトから変数値を取得し、Math::LP::Constraint オブジェクトからスラック変数値とデュアル値を取得する。Math::LP::LinearCombination から行値（最適値を含む）を取得する。.

データフィールド

solver_status

　最近の solve() 呼び出しの状態を保持。
　$OPTIMAL, $MILP_FAIL, $INFEASIBLE, $UNBOUNDED, $FAILURE, $RUNNING, $FEAS_FOUND, $NO_FEAS_FOUND, $BREAK_BB のいずれか。

variables

　名前でインデクス化されて LP で用いられるA ref to a hash with 全ての Math::LP::Variable オブジェクトのハッシュへの参照。

constraints

　LP で用いられる全ての Math::LP::Constraint オブジェクトの配列への参照。

objective_function

　目的関数を表す Math::LP::LinearCombination オブジェクト。

type

　最適化の型。$MAX または $MIN。

メソッド

new()

　新しい空の LP を返す。

nr_rows()

　行数、すなわち LP の制限式の数を返す。

nr_cols()

　列数、すなわち LP の変数の数を返す。

add_variable($var)

　LP に属する変数を登録する。変数の index フィールドには副作用として設定される。この理由から２つの LP オブジェクトで１つの変数を用いることは許されない。

add_constraint($constr)

　Math::LP::Constraint を LP に追加する。制限式の index フィールドは likewise 設定である。１つ以上の LP に対し単一の制限式を用いることは許されない。制限式に現れる全ての変数は自動的に登録される。

set_objective_function($lincomb,$type)

　LP の目的関数を設定する。以下のパラメータが利用可能である。

  1. $lincomb
    目的関数を形成する Math::LP::LinearCombination
    線形結合に現れる新しい変数は自動的に LP に追加される。
  2. $type
    最適化の型。$MAX または $MIN のいずれか。

maximize_for($lincomb)

　set_objective_function($lincomb,$MAX) へのショートカット

minimize_for($lincomb)

　set_objective_function($lincomb,$MIN) へのショートカット

solve([$lag_solve])

　LP を解き、成功すれば true を返し（すなわち状態値は $OPTIMAL である）、そうでなければ false を返す。ソルバの状態は status フィールドで後でも取得できる。デフォルトではlt is to solve using solve() を用いて使う。しかしながら $lag_solve が指定され true であれば lag_solve() を用いる。

optimum()

　ソルバによって得られた目的関数の値を返す。

参考資料

　Math::LP で利用しているパッケージに関するさらなる情報は Math::LP::Object, Math::LP::Variable 及び Math::LP::LinearCombination にある。
　lp_solve ライブラリへのラッパは Math::LP::Solve でドキュメント化している。それは Michel Berkelaar が書き、Jeroen Dirks が追加した lp_solve ライブラリに基づいている。ocumentation on lp_solve に関するドキュメントはソースコードとともに配布されており、ftp://ftp.ics.ele.tue.nl/pub/lp_solve/ でダウンロードすることができる。

著者

　Wim Verhaegen, <wimv@cpan.org>.

著作権

　Copyright (c) 2000-2001 Wim Verhaegen. All rights reserved.

　本プログラムはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

Toolbox Logo
 Updated : 2007/09/26