79. simplex

79.1 Introduction to simplex

simplexはシンプレックスアルゴリズムを使った線形最適化のパッケージです。

例:

(%i1) load("simplex")$
(%i2) minimize_lp(x+y, [3*x+2*y>2, x+4*y>3]);
                  9        7       1
(%o2)            [--, [y = --, x = -]]
                  10       10      5

79.1.1 Tests for simplex

ディレクトリ share/simplex/Testsにいくつかテストがあります。

79.1.1.1 klee_minty

関数 klee_mintyは linear_programのための入力を生成します。 入力に関してスケーリングなしには解くためには指数時間が要求されます。

例:

load(klee_minty)$
apply(linear_program, klee_minty(6));

よりよいアプローチ:

epsilon_sx : 0$
scale_sx : true$
apply(linear_program, klee_minty(10));

79.1.1.2 NETLIB

netlib (http://www.netlib.org/lp/data/) テストスイートからいくつかのより小さい問題が Maximaが可読なフォーマットに変換されます。 問題は adlittle, afiro, kb2, sc50aです。 それぞれの問題は、行列 A とベクトル bと cのため、CSVフォーマットの3つの入力ファイルを持ちます。

例:

A : read_matrix("adlittle_A.csv", 'csv)$
b : read_list("adlittle_b.csv", 'csv)$
c : read_list("adlittle_c.csv", 'csv)$
linear_program(A, b, c)$
%[2]
=> 225494.963126615

結果:

PROBLEM        MINIMUM                SCALING
adlittle       225494.963126615       no
afiro          - 464.7531428571429    no
kb2            - 1749.900129055996    yes
sc50a          - 64.5750770585645     no

79.2 Functions and Variables for simplex

オプション変数: epsilon_lp

デフォルト値: 10^-8

linear_programの数値計算で使われるイプシロン。

以下も参照してください: linear_program

Categories:  Package simplex

関数: linear_program (A, b, c)

linear_programはシンプレックスアルゴリズムの実装です。 linear_program(A, b, c)は、 A.x = bかつ x >= 0を満たすベクトルの中で c.xが可能な最小となるベクトル xを計算します。 引数 Aは行列で、引数 bと cはリストです。

linear_programは、最小化ベクトル xと最小値 c.xを含むリストを返します。 もし問題が有界でないなら、 "Problem not bounded!"を返し、 もし問題が実現可能でないなら、 "Problem not feasible!"を返します。

この関数を使うためには、最初に load(simplex);で simplexパッケージをロードしてください。

例:

(%i2) A: matrix([1,1,-1,0], [2,-3,0,-1], [4,-5,0,0])$ (%i3) b: [1,1,6]$ (%i4) c: [1,-2,0,0]$ (%i5) linear_program(A, b, c); 13 19 3 (%o5) [[--, 4, --, 0], - -] 2 2 2

以下も参照してください: minimize_lp, scale_lp, epsilon_lp

Categories:  Package simplex · Numerical methods

関数: maximize_lp (obj, cond, [pos])

いくつかの線形制約 condに従う線形目標関数 objを最大化します。 引数と戻り値の詳細な記述に関しては、 minimize_lpを参照してください。

以下も参照してください: minimize_lp.

Categories:  Package simplex · Numerical methods

関数: minimize_lp (obj, cond, [pos])

いくつかの線形制約 condに従う線形目標関数 objを最小化します。 condは線形等式や不等式のリストです。 厳密な不等式では、 >は >=に、 <は <=に置き換えられます。 オプションの引数 posは正と仮定される決定変数のリストです。

もし最小が存在するなら、 minimize_lpは目標関数の最小値と最小が得られる決定変数値のリストを含むリストです。 もし問題が有界でないなら、 minimize_lpは "Problem not bounded!"を返し、 もし問題が実現可能でないなら、 "Ploblem not feasible!"を返します。

決定変数はデフォルトでは非負とは仮定されません。 もし決定変数すべてが正なら、 nonegative_lpを trueに設定してください。 もし決定変数のいくつかだけが正なら、オプション引数 posの中でそれらをリストしてください。 (これは制約を足すより効率的だということに注意してください。)

minimize_lpは Maximaの linear_program関数で実装されたシンプレックスアルゴリズムを使います。

この関数を使うためには、最初に load(simplex);で simplexパッケージをロードしてください。

例:

(%i1) minimize_lp(x+y, [3*x+y=0, x+2*y>2]); 4 6 2 (%o1) [-, [y = -, x = - -]] 5 5 5 (%i2) minimize_lp(x+y, [3*x+y>0, x+2*y>2]), nonegative_lp=true; (%o2) [1, [y = 1, x = 0]] (%i3) minimize_lp(x+y, [3*x+y=0, x+2*y>2]), nonegative_lp=true; (%o3) Problem not feasible! (%i4) minimize_lp(x+y, [3*x+y>0]); (%o4) Problem not bounded!

いかも参照してください: maximize_lp, nonegative_lp, epsilon_lp。

Categories:  Package simplex · Numerical methods

オプション変数: nonegative_lp

デフォルト値: false

もし nonegative_lpが trueなら、 minimize_lpと maximize_lpの決定変数すべては正と仮定されます。

以下も参照してください: minimize_lp。

Categories:  Package simplex

オプション変数: scale_lp

デフォルト値: false

scale_lpが trueの時、 linear_programは行や列それぞれの最大絶対値が1になるように入力をスケールします。

Categories:  Package simplex

変数: pivot_count_sx

linear_programが戻った後、 pivot_count_sxは最後の計算のピボットの数です。

Categories:  Package simplex

変数: pivot_max_sx

pivot_max_sxは linear_programが許すピボットの最大数です。

Categories:  Package simplex

This document was generated by 市川雄二 on June, 21 2016 using texi2html 1.76.