情報工学総合演習 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