情報工学総合演習 D-I : 近似アルゴリズム GLPK パッケージの利用 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史 1 線形計画問題 目的関数 と minimize x1 + x2 制約条件 x1 + 2 x2 ≦ 10 2 x1 + x2 ≦ 12 4 x2 ≦ 16 0 ≦ x1, 0 ≦ x2 C プログラム (11行目) 最大化/最小化を設定 (12行目) 変数の数を 2 と設定 (13, 14行目) 各変数の係数を設定 (22 ~ 27行目) 各制約の係数を設定 (詳細は、次のページ) (19 ~ 21行目) 各制約の上下限を設定 (15, 16行目) 各変数の範囲を設定 (18行目) 制約条件の数を 3 と設定 2 線形計画問題 と C プログラム 制約条件の各係数を、行列で表す ia[ ], ja[ ], ar[ ] を使って、 0 以外の各係数を順に設定する a a a a a 1, 1, 2, 2, 3, 1 2 1 2 2 は は は は は (続き) 1 2 0 2 1 4 1 2 2 1 4 配列 ar[ ] に格納 配列 ja[ ] に格納 配列 ia[ ] に格納 3 補足 0, 1 整数制約を緩和した制約条件 0 ≦ xi ≦ 1 は、 glp_set_col_bnds( ) で設定することができる 4 実装のヒント C++ で GLPK パッケージを用いるには… C 言語の場合と同様に # include <glpk.h> 関数の利用法も同様 5 6 この教材のご利用について この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を 求めることなく、無償で自由にご利用いただけます。講義、自主学習は もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許 諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著 作者に帰属します。この教材、または翻訳や改変等を加えたもの を公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施 してください。なお、この教材に改変等を加えたものの著作権は、 次ページ以降に示す著作者および改変等を加えた方に帰属しま す。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する 場合には、頒布・再頒布の形態を問わず、このページの利用条件 7 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ このファイルの著作者 堀山 貴史 2009-2011 [email protected] 改変等を加えられた場合は、お名前等を追加してください 図の著作者 各ページ 堀山 貴史 8
© Copyright 2025 ExpyDoc