Optimization[LPSolve] - 線形計画問題を解く
使い方
LPSolve(obj, constr, bd, opts)
パラメータ
obj - 代数式;線形目的関数
constr - (オプション) set(relation) または list(relation) ; 1 次制約条件
bd - (オプション) name = range の列; 境界条件
opts - (オプション) option = value の形の等式。ただし、option は assume, binaryvariables, depthlimit, feasibilitytolerance, infinitebound, initialpoint, integertolerance, integervariables, iterationlimit, maximize, nodelimit または output
|
説明
|
|
•
|
LPSolve コマンドは 1 次のもと線形の (または) を計算する (LP) を解きます。
|
•
|
整数計画問題、混合整数計画問題、バイナリ (0-1) 計画問題を解くことができます。整数計画問題は asuume および integervariables または binaryvariables オプションを使い指定をします。詳しくは整数計画問題を参照ください。
|
•
|
第 1 引数 obj は線形代数式の目的関数です。
第 2 引数 constr は線形不等式または等式制約条件の集合またはリストをオプションで指定します。変数はobj および constr にある名前の型を持つ不定元です。
境界条件は varname を変数、varrange を範囲とするとき、 varname = varrange の形で与えます。端点として型 infinity を使うことができます。はじめ、変数が非負変数と仮定していませんが、assume = nonnegative によって指定することができます。
|
•
|
Maple は最小値 (最大値) とそれを満たす点 (極値) のリストを解として返します。 output = solutionmodule オプションを指定すると、モジュールを返します。詳しくは Optimization/Solution を参照ください。
|
•
|
制約条件および境界条件におけるな点だけが必要なとき、 LPSolve の第 1 引数を 0 と指定します。
|
|
|
オプション
|
|
|
引数 opts は次のオプションからいくつか選ぶことができます。これらのオプションは LPSolve コマンドですべての入力の形で使うことができるもので、詳しくは Optimization/Options を参照ください。整数計画問題のオプション には整数計画問題でのみ適応できるオプションがあります。
|
•
|
assume = nonnegative -- すべての変数を非負と仮定します。
|
•
|
feasibilitytolerance = realcons(positive) -- 許容できる誤差の量を指定します。
|
•
|
infinitebound = realcons(positive) -- infinitebound より大きい値を infinity とみなします。
|
•
|
initialpoint = set(equation) または list(equation) -- varname=value の集合またはリストで初期点を指定します。
|
•
|
iterationlimit = posint -- 有効制約法による反復回数を指定します。
|
•
|
maximize または maximize = truefalse -- true のとき最大値を計算し、false のとき最小値を計算します。'maximize' オプションは maximize = true と同じです。はじめは maximize = false が指定されています。
|
|
|
整数計画問題
|
|
•
|
assume = binary, integer または nonnegint -- すべての変数はバイナリ (0-1) または非負の値を値をとるように指定します。
|
•
|
binaryvariables = set(equation) または list(equation) -- 指定した変数が 0 または 1 の値のみをとるように指定します。
|
•
|
depthlimit = posint -- 分岐木の最大の深さを指定します。
|
•
|
integertolerance = realcons(positive) -- 許容できる誤差の量を整数で指定します。
|
•
|
integervariables = list(name) or set(name) -- 指定した変数が整数の値をとるようにします。
|
•
|
nodelimit = nonnegint -- 分岐木の最大探索ノードを指定します。0 を指定したときは、すべてのノードの探索を行います。
|
|
|
注意
|
|
•
|
ネットワーク問題について、LPSolve は Numerical Algorithms Group (NAG) によって組み込まれた反復有効制約法を使います。初期点は initialpoint オプションで指定することができます。指定しないときは、デフォルトの点を使います。
|
•
|
整数計画問題はノード木を使って計算するを使って解きます。各ノードは、有効制約法を使って解くネットワーク LP 部分問題に対応します。
|
•
|
パラメータ constr および bd はオプションで入力しますが、LPSolve は 1 つも制約条件および境界条件または、assume = nonnegative オプションがないときはエラーを返します。
|
•
|
LPSolve は問題がであるときエラーを返します。 問題がとき、LPSolve コマンドは警告を出し、反復計算の最後の結果を出します。この結果は意味がない場合があります。
|
•
|
assume オプションを使うことができますが、一般にOptimizationパッケージではサポートされていません。
|
|
|
例
|
|
4 つの制約条件のもと 2 変数の線形関数の最小値を求めるためには LPSolve を使います。
>
|
LPSolve(-4*x-5*y, {x+2*y<=6, 5*x+4*y<=20, x>=0, y>=0});
|
| (5.1) |
明確な非負制約条件の代わりに assume=nonnegative オプションを使います。
>
|
LPSolve(-x-y, {y<=3*x+1/2, y<=-5*x+2}, assume = nonnegative);
|
| (5.2) |
境界は別々に加えることができます。
>
|
LPSolve(-6*x+4*y+z, {5*x-10*y<=20, 2*z-3*y=6, -x+3*y<=3}, x=1..20,
y=0..infinity);
|
| (5.3) |
目的関数の最大値を求めるために maximize オプションを使います。
>
|
LPSolve(-7*x+2*y, {4*x-12*y<=20, -x+3*y<=3}, x=-5..5, y=0..infinity, maximize);
|
| (5.4) |
整数計画問題を解くために integer オプションを使います。
>
|
LPSolve(-5*x-7*y, {7*x+y<=35, -x+3*y<=6}, assume=integer);
|
| (5.5) |
nonnegint オプションは非負整数値を求めるときに使います。
>
|
LPSolve(2*x+5*y, {3*x-y=1, x-y<=5}, assume={nonnegative, integer});
|
| (5.6) |
|
|