単体法
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
添え字や転置が見難いときは『編集』からソースを見て、~
適当に置換してTeXに直し、コンパイルしてから見てください。
- 線形計画問題
-- 主問題：~
min &mimetex(c^{T}x);~
s.t. &mimetex(Ax = b \wedge x \geq 0);~
-- 双対問題：~
max &mimetex(b^{T}y);
s.t. &mimetex(c-A^{T}y \geq 0);
-- ただし、Aの各行は１次独立で、許容領域は有界であること...
- 単体法
-- Aの列を選んで、正則な部分行列&mimetex(A_B);を作る。~
それ以外の部分を&mimetex(A_N);とする。~
一般性を失わずに、&mimetex(A = (A_B,A_N));とできる。~
等式制約条件、&mimetex(Ax=b);は、&mimetex((A_B,A_N)(x_B,x...
この条件の任意の解は、&mimetex(x_N);をパラメタとして、~
&mimetex(x_B = A_{B}^{-1}b - A_{B}^{-1}A_{N}x_N);と置いて...
&mimetex((x_B,x_N));と書ける。
&mimetex(x_N = 0);と取ったものは基底解、許容解になってい...
最適解は許容基底解のいずれかとなる。
単体法は、許容基底解を次々と辿って最適解となっている許容...
-- 非退化仮定~
任意の主問題の許容基底解が、0を要素に持たないことを仮定す...
-- 非退化仮定から、許容基底解から&mimetex(x_N);を微小に動...
現在の許容基底解を&mimetex(\hat{x} = (\hat{x}_B,0) = A_{B...
そこから微小に移動した場所を、&mimetex(x = (x_B,x_N) = \h...
単体法では、&mimetex(x_N);の要素のどれか一つだけを変化さ...
-- &mimetex(x_N);の変化によって、目的関数&mimetex(c_{T}x)...
&mimetex(c^{T}x - c^{T}\hat{x} = (c_N - A_{N}^{T}(A_{B}^{...
--- もし、&mimetex(c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B);の...
現在の許容基底解が最適解。
--- &mimetex(c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B);の要素に...
&mimetex(\hat{i});番目の要素が最も小さいとして、その方向...
その方向の単位ベクトルを&mimetex(e_{i});、&mimetex(x_N = ...
&mimetex(x = (x_B,x_N) = \hat{x} + (-A_{B}^{-1}A_{N}e_{i}...
許容性を保ったまま&mimetex(t>0);をギリギリまで増やす。~
&mimetex(\hat{x}_B - A_{B}^{-1}A_{N}e_{i}t \geq 0);となる...
&mimetex(x(\hat{t}) = \hat{x} + (-A_{B}^{-1}A_{N}e_{i},e_...
このとき、目的関数は&mimetex(\hat{x});での値よりも減少し...
(許容領域の有界性の仮定から、tには最大値が存在し、非退化...
この&mimetex(x(\hat{t}));を新たな初期値として反復すれば、...
許容基底解は有限個しかないので、反復は有限解で終わる。
-- 一番最初の許容基底解を見つけるのは難しい。~
変数を一つ追加して、許容基底解を作る手法がとられる。
終了行:
添え字や転置が見難いときは『編集』からソースを見て、~
適当に置換してTeXに直し、コンパイルしてから見てください。
- 線形計画問題
-- 主問題：~
min &mimetex(c^{T}x);~
s.t. &mimetex(Ax = b \wedge x \geq 0);~
-- 双対問題：~
max &mimetex(b^{T}y);
s.t. &mimetex(c-A^{T}y \geq 0);
-- ただし、Aの各行は１次独立で、許容領域は有界であること...
- 単体法
-- Aの列を選んで、正則な部分行列&mimetex(A_B);を作る。~
それ以外の部分を&mimetex(A_N);とする。~
一般性を失わずに、&mimetex(A = (A_B,A_N));とできる。~
等式制約条件、&mimetex(Ax=b);は、&mimetex((A_B,A_N)(x_B,x...
この条件の任意の解は、&mimetex(x_N);をパラメタとして、~
&mimetex(x_B = A_{B}^{-1}b - A_{B}^{-1}A_{N}x_N);と置いて...
&mimetex((x_B,x_N));と書ける。
&mimetex(x_N = 0);と取ったものは基底解、許容解になってい...
最適解は許容基底解のいずれかとなる。
単体法は、許容基底解を次々と辿って最適解となっている許容...
-- 非退化仮定~
任意の主問題の許容基底解が、0を要素に持たないことを仮定す...
-- 非退化仮定から、許容基底解から&mimetex(x_N);を微小に動...
現在の許容基底解を&mimetex(\hat{x} = (\hat{x}_B,0) = A_{B...
そこから微小に移動した場所を、&mimetex(x = (x_B,x_N) = \h...
単体法では、&mimetex(x_N);の要素のどれか一つだけを変化さ...
-- &mimetex(x_N);の変化によって、目的関数&mimetex(c_{T}x)...
&mimetex(c^{T}x - c^{T}\hat{x} = (c_N - A_{N}^{T}(A_{B}^{...
--- もし、&mimetex(c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B);の...
現在の許容基底解が最適解。
--- &mimetex(c_N - A_{N}^{T}(A_{B}^{N})^{-1}c_B);の要素に...
&mimetex(\hat{i});番目の要素が最も小さいとして、その方向...
その方向の単位ベクトルを&mimetex(e_{i});、&mimetex(x_N = ...
&mimetex(x = (x_B,x_N) = \hat{x} + (-A_{B}^{-1}A_{N}e_{i}...
許容性を保ったまま&mimetex(t>0);をギリギリまで増やす。~
&mimetex(\hat{x}_B - A_{B}^{-1}A_{N}e_{i}t \geq 0);となる...
&mimetex(x(\hat{t}) = \hat{x} + (-A_{B}^{-1}A_{N}e_{i},e_...
このとき、目的関数は&mimetex(\hat{x});での値よりも減少し...
(許容領域の有界性の仮定から、tには最大値が存在し、非退化...
この&mimetex(x(\hat{t}));を新たな初期値として反復すれば、...
許容基底解は有限個しかないので、反復は有限解で終わる。
-- 一番最初の許容基底解を見つけるのは難しい。~
変数を一つ追加して、許容基底解を作る手法がとられる。
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
