単体法のバックアップ(No.2) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ] [ リンク元 ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
単体法へ行く。
- 1 (2007-11-14 (水) 10:47:53)
- 2 (2007-11-14 (水) 11:26:40)

添え字や転置が見難いときは『編集』からソースを見て、
適当に置換してTeXに直し、コンパイルしてから見てください。

線形計画問題
- 主問題：
  min $c^{T}x$
  s.t. $Ax = b \wedge x \geq 0$
- 双対問題：
  max $b^{T}y$ s.t. $c-A^{T}y \geq 0$
- ただし、Aの各行は１次独立で、許容領域は有界であることを仮定する。

単体法
- Aの列を選んで、正則な部分行列 $A_B$ を作る。
  それ以外の部分を $A_N$ とする。
  一般性を失わずに、 $A = (A_B,A_N)$ とできる。
  等式制約条件、 $Ax=b$ は、 $(A_B,A_N)(x_B,x_N) = b$ と書ける、
  この条件の任意の解は、 $x_N$ をパラメタとして、
  $x_B = A_{B}^{-1}b - A_{B}^{-1}A_{N}x_N$ と置いて、
  $(x_B,x_N)$ と書ける。 $x_N = 0$ と取ったものは基底解、許容解になっている基底解を許容基底解と呼ぶ。
  最適解は許容基底解のいずれかとなる。単体法は、許容基底解を次々と辿って最適解となっている許容基底解を探す方法。
- 非退化仮定
  任意の主問題の許容基底解が、0を要素に持たないことを仮定する。
- 非退化仮定から、許容基底解から $x_N$ を微小に動かしても許容解となる。
  現在の許容基底解を $\hat{x} = (\hat{x}_B,0) = A_{B}^{-1}b$ 。
  そこから微小に移動した場所を、 $x = (x_B,x_N) = \hat{x} + (-A_{B}^{-1}A_{N},I)x_N$
  単体法では、 $x_N$ の要素のどれか一つだけを変化させる。
- $x_N$ の変化によって、目的関数 $c_{T}x$ は、
  $c^{T}x - c^{T}\hat{x} = (c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B)x_N$ と変化する。
  - もし、 $c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B$ の成分が全て正なら、
    現在の許容基底解が最適解。
  - $c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B$ の要素に負のものがあるとき、
    $\hat{i}$ 番目の要素が最も小さいとして、その方向に移動する。
    その方向の単位ベクトルを $e_{i}$ 、 $x_N = te_{i}$ とすれば、
    $x = (x_B,x_N) = \hat{x} + (-A_{B}^{-1}A_{N}e_{i},e_{i})t$
    許容性を保ったまま $t>0$ をギリギリまで増やす。
    $\hat{x}_B - A_{B}^{-1}A_{N}e_{i}t \geq 0$ となる最大の $t$ を $\hat{t}$ とすると、
    $x(\hat{t}) = \hat{x} + (-A_{B}^{-1}A_{N}e_{i},e_{i})\hat{t}$ は許容基底解になっていて、
    このとき、目的関数は $\hat{x}$ での値よりも減少している。
    (許容領域の有界性の仮定から、tには最大値が存在し、非退化仮定から、目的関数の減少が示せる。)
    この $x(\hat{t})$ を新たな初期値として反復すれば、最適解が見つかる。
    許容基底解は有限個しかないので、反復は有限解で終わる。