[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

# 74. simplex

[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

## 74.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

·

Categories: Numerical methods ·Optimization ·Share packages ·Package simplex

[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

### 74.1.1 Tests for simplex

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

[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

#### 74.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));

[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

#### 74.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

[ < ] | [ > ] |  | [ << ] | [上] | [ >> ] |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

## 74.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

Option variable: scale_lp

  Default value: `false`

  When `scale_lp` is `true`, `linear_program` scales its input so that the maximum absolute value in each row or column is 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

[ << ] | [ >> ] |  |  |  |  |  | [冒頭] | [目次] | [見出し] | [ ? ]

この文書は市川 雄二によって2014年9月月15日にtexi2html 1.82を用いて生成されました。