next up previous
Next: [注意事項] Up: 実験 Previous: 実験課題

実験方法

ディレクトリ~hanba/info-eng/に, ビッグM法, ショートステップパス追跡法 および ロングステップパス追跡法 の完成したプログラムが置かれている。 ファイル名はそれぞれ bigM.sce, spf.sce, lpf.sceである。 これらは$ n$次元立方体 $ 1 \leq x_i \leq 2$ $ (1 \leq i \leq n) $ の内部(境界を含む)で目的関数 $ \vec{1}^T\vec{x}$を解くための プログラムである。 最適解は $ x_1=1,\ldots,x_n=1$である。 いずれも, プログラムの2行目のn=1; という部分で次元が指定されている(最初は値が$ 1$に設定されている)。 計算が終了すると, 変数timeに計算にかかった時間が格納される。 この値は計算終了後にScilabのウィンドウ内で

$\displaystyle \verb?time?$ (88)

と入力することで参照できる。 問題の解はsolという変数に格納される。 計算が正常に終了すれば, これらは全要素がすべて1のベクトルになる (若干の数値誤差を含む可能性はあるが)。 値を確認するには, Scilabのウィンドウ内で

$\displaystyle \verb?sol?$ (89)

と入力する。 なお, シンプレックス法では, 人為変数の値を含んだ 解がasolという変数に格納される。

これらを利用して, ショートステップパス追跡法 およびロングステップパス追跡法の それぞれについて, $ n$の値を1から20まで増加させて計算時間を測る。 ただし, $ n$の刻みは$ 1$ではなく, $ 2 \sim 3$程度に取って構わない。





Shigeru HANBA
平成16年3月19日