オペレーションズ・リサーチ

シラバス

香川大学大学院地域マネジメント研究科2007年度
オペレーションズ・リサーチ (Operations Research)
応用科目; 2単位; 第2学期後半; 水曜日 6-7 校時 (1820-2130); 三原研究室
三原麗珠

「経営科学」あるいは「マネジメント・サイエンス」の中核にあたる「OR (オペレーションズ・リサーチ)」という分野は，ビジネスや政策にかかわる多くの問題を最適化問題としてとらえる．この科目では OR のさまざまな手法のなかでも特に線形計画とネットワーク理論を重点的にあつかう．単純な構造を特徴とする線形計画 (リニア・プログラミング) は生産計画ほか幅広い分野に応用されている．ネットワーク理論は交通・物流・情報・通信などの分野に応用されている．

OR の手法の多くは，最適解を求めるコンピュータソフトウエアに実装されている．したがって多くの実務的問題は，いったん最適化問題として定式化 (モデリング) してしまえば，そのようなソフトウエアで解けてしまう．しかしこの科目は特定ソフトウエアの利用法ではなく，あくまで問題解決の手順であるアルゴリズムの理解を最重視する．その上で，いくつかの具体例を通じて受講者がモデリングのためのヒントを得られるようにしたい．

前提科目・関連科目

厳密な意味での前提科目はない．3 次元座標上の平面のグラフが読める程度の数学の知識は必要である (小暮「線形計画法の定式化と図式解法」が理解できなければ受講はやめた方がいい)．「微分積分と線形代数」などで線形代数を学んでおけば，利用できる参考書の種類が増える．

関連科目を関心対象と方法で分類すると，おおよそ以下のようになる．ゲーム理論や経済学は各主体レベルの最適化を前提として，その帰結を分析・評価する (「ゲーム理論」「経済分析」「費用便益分析」「都市開発論」などの主関心)．あるいは主体レベルの最適化の帰結が社会的に望ましいものになるような制度を設計する (「資源配分の公平」「配分ルールと厚生」の主関心)．そこでは個々の主体レベルでの最適化は主体がどう行動すべきかをしめすものではなく，あくまで分析のための単純化と考えられる．一方，意思決定論は最適化自体に関心を持ち，そのための方法を追求する (「意思決定分析」や「オペレーションズ・リサーチ」)．そこでは主体がどう行動すべきかをしめすことを重視する．なお「意思決定分析」(青井) は不確実性の分析を重視するようである．この科目「オペレーションズ・リサーチ」の方法論は離散数学的であり，関連科目の方法論とは (数学を使うという点を除けば) 一線を画す．

関連分野の位置づけについては，増田靖の「私見：経営における数理モデルの目的」も参考になるだろう．

講義の進め方・成績評価

久保のテキストに沿って講義形式ですすめる．プレゼンテーション用ソフトウエアを利用する予定．受講者全員の積極的な質問やコメントを歓迎する．(互いに発言の自由を尊重してもらう．詳しくは別掲のガイドラインを参照．) 本文の例，主要概念，アルゴリズム，定理の意味の直感的理解を重視する．受講者は授業内容や教材を参考にしながら与えられた練習問題を自習していく．

単位認定は，最終試験・宿題 (いちぶの練習問題など)・授業への貢献度などにもとづく．最終試験のウエイトが高い．最終試験のほとんどの問題は練習問題の類題を予定．[訂正．受講者が 1 名なので，授業への貢献度と宿題と口述試験を重視する．]

必読文献・参考文献

1. 必読文献

小暮仁. 線形計画法の定式化と図式解法 (Web 教材). 講義開始前に読むべき．これがフォローできなければ受講はやめたほうがいい．
久保幹雄. 組合せ最適化とアルゴリズム. 共立出版, 2000 (2400 円). サポートページから正誤表や教材が入手できる．この科目の内容やレベルはその教材で確認できる．

2. リンク集および初歩的な参考文献

宋宇. p-OR-tal (オペレーションズ・リサーチポータルサイト). OR 関連情報へのリンク集．「講義資料」の「Webテキスト」では Web で入手できる教材が紹介されている．
小暮仁. オペレーションズ・リサーチ (Web 教材). 文系大学生対象の教材．特に Excel ソルバーによる線形計画法の解法をすすめる．
柏木吉基. Excel で学ぶ意思決定論. オーム社, 2006. 第6章「最適化問題 (線形計画法: Linear Programming)」特に 6-2, 6-3 節．小暮の Web 教材だけでは理解できなかったばあいに参照すればよい．6-2 節で整数制約条件が説明から抜け落ちているミスがあるので注意．希望者に配布する．オーム社のサイトから例題のファイルが入手できる．

3. この科目よりやや高めのレベルの入門

James Orlin. Introduction to Optimization, MIT OpenCourseWare, Sloan School of Management. ビジネススクールで開講されている OR 科目 (ただし学部向け)．
森雅夫, 松井知己. オペレーションズ・リサーチ. 経営システム工学ライブラリー 8. 朝倉書店, 2004. 線形計画ほか多くのトピックをカバー．ただしネットワークはほとんどあつかっていない．
福島雅夫. 数理計画入門. システム制御情報学会編. 朝倉書店, 1996. この科目であつかう内容の大部分をカバー．
藤重悟. グラフ・ネットワーク・組合せ論. 共立出版, 2002. 関連する数学．

4. Ruby プログラミング

今年度は発展的課題として，Ruby によるプログラミングをやってみる．以下は参考になるかもしれない情報:

5. 定番アルゴリズム

時間が余ったので，今年度は代表的なソートアルゴリズム (おまけとして力任せ検索法) を学ぶことにした．

今からでも遅くない！アルゴリズム入門, Part 2, 定番アルゴリズムを徹底理解！ (5, 8, 9 節を除く) ITpro.

授業計画

テキストの各 Part の講義回数目安を括弧内にしめす:

Part 1 グラフ・アルゴリズム・計算量 (2回): グラフの定義と最大安定集合問題，Euler 閉路・Euler の定理・アルゴリズム，ハノイの塔: 無向グラフと有向グラフ，最小木問題，巡回セールスマン問題: P と NP．[Slides: lecture1-new, lecture2-new, lecture3]
Part 2 線形計画 (4回): 線形計画と図式解法，辞書と単体法，双対問題，主問題と双対問題．[lecture4, ex4, lecture5, ex5]
Part 3 ネットワーク理論 (5回): 最短路問題，最大流問題，最小費用流問題．[lecture6, lecture7, lecture8, mcf-ex1]
Part 4 組合せ最適化 (1回以上): 分枝限定法，Lagrange 緩和．[Section4-1, Section4-3]
[予定にはなかった分] 定番アルゴリズム．

講義開始前のおしらせ

2007年 6月

久保テキストのサポートページにあるパワーポイントスライドが見れることをあらかじめ確認しておくこと．Microsoft 製の高価な PowerPoint を買ってしまった人はそれで見てもいいだろう．ほかにも PowerPoint Viewer やオープンソースの OpenOffice.org, NeoOffice などで見れるはず．(NeoOffice で検証したところ，一部数式フォントが正しく表示されない，スライド表示で前に戻ろうとするとひとつ前のページの開始画面に戻るなど，多少の問題はあった．)

スライドの印刷版あるいは pdf 版が必要ならば，各自で準備すること．たとえば Mac の PowerPoint X のばあい，以下の手順で印刷するのがベストだった．どうしても印刷できないときは pdf を渡すので連絡して欲しい．

[ファイル] メニューの [プリント] をクリック．
[印刷部数と印刷ページ] が選択されているポップアップメニューで，[Microsoft PowerPoint] をクリック．
[印刷対象] ポップアップメニューで印刷する要素を指定．「配布資料 (6スライド/ページ)」など．

[三原私的メモ: lecture7.ppt 38 pages, lecture8.ppt 23 pages are unavailable at the moment.]

テキスト・スライドへの注釈

久保テキスト

Page 21, 下 2行．「定数 C と N が存在して……すべての n > N に対して」と修正．
Page 33. 定理 2 で「最適解が存在し」という条件を外せない例として，たとえば2次元第一象限での最適化がある．
Page 39, line 14. x1+x2+x3=30 でなくて x3=30.
Page 41, 最終行．すべての非基底変数……どの非基底変数．
単体法の説明にあたって，テキスト図 2.3 の矢印の動きと図2.8 で x1=0, x2=0, x3=0, s1=0, s2=0, s3=0 の平面をしめすのは欠かせない．
Page 44. 双対問題の解釈はわかりにくいかも．丼を作って売るよりも仕入れた肉をそのまま売る (ことでゼロの利益を得る) 方が店長にとってはマシな状況を考えよ．そのような状況を考えることで，店長にとっての肉の価値 (市場価格ではない) を導出している．なお，変数 y1は豚肉の量を1単位増やしたときの売上げ (目的関数の最大値) の変化量を表す (y1が 60から61になったときを考えよ) ので，豚肉 1 単位の価値を表す．
Lagrangean 緩和では，変数 x の次元については最大値，それと「直行する」変数 y の次元については最小値となる按点 (馬の鞍，ラクダの背中) をイメージするとよい．
Page 64. 最初の最小化の式で ys, y1, y2, y3, yt の係数の符号については迷うかもしれない．これらを一部逆にすると y が実行可能なポテンシャルでなくなる．すべて逆にすると -y が実行可能なポテンシャルになる．テキストどおりに，入って来る流れをマイナス，出て行く流れをプラスで統一するとき， y は実行可能なポテンシャルになる．
Page 70, line 3. 最適パスは s→2→1→t である．
Page 73, Bellman-Ford 法の 6 行目．if 式の右辺は y_w(k+1) にすべき．でないと複数の点から枝が w に出ているとき，いったん設定された y_w(k+1) が，より大きい値に改訂される可能性がある．
Page 79, トポロジカルソートのアルゴリズム 4 行目． LIST から適当に点 v を選ぶとき，LIST から v を取り除いたと理解する．
Page 92, 図 3.16 は S={s, 3}, {s, 1, 3} (これらは非連結集合) 以外を考えている．

久保スライド

対象は主に 2007 年 3 月 31 日のバージョン．

lecture3 指数時間アルゴリズムの計算時間. 入力サイズ 100 のところがちがっている．
lecture3, page 4. オーダーの定義は絶対値が抜けている．
lecture3, page 13. クラス NP の決定問題の例としては，オイラー閉路の例は (間違いではないが) あまり適切ではないかもしれない．データの記述方法にもよるが，閉路があるかどうかはオイラーの定理ですぐ判定できる．じっさいオイラー閉路問題はクラス P に属する．
lecture5, pages 9 以降．Lagrange 緩和による方法で条件式に y1, y2, y3 が非負とあるのはわかりにくいかもしれない．これはパラメターであり，最大化は x1, x2, x3 についてやっていることに注意．
lecture5, page 24. 双対問題の最適解 yi.
lecture5, page 31以降．s1, s2 の値が正しくない．
lecture6, page 21 ポテンシャルの実行不能，実行可能．ポテンシャル y が実行不能とは，そこの不等式をみたす枝 vw が存在すること．ポテンシャル y が実行可能とはすべての枝 vw にたいして，そこの不等式がみたされること．
lecture6, page 29 双対問題を作ってみよう．目的関数を x についてまとめる．
lecture6, page 33 Bellman 方程式と Bellman-Ford 法---双対問題を眺めてみよう．最後の行の yt が誤っている．
lecture6, page 60 Bellman-Ford 法を適用してみよう．k=3から k=4 にうつるところの矢印がおかしい．
lecture6, pages 61-62 最短路木の作成．点3 にたいする値は 6, 2 が正しい．
lecture6, page 65 通貨の変換．最後の式の log の中身は足し算ではなくて掛け算．
lecture6, page 75 挿入ソート．アルゴリズム5行目は A[i]=key.
lecture6, page 93 トポロジカルソートの疑似コード．4行目で LIST から適当に点 v を選ぶとき，LIST から v を取り除いたと理解する．8行目の右辺は LIST ∪{w}.
lecture6, page 94. 「つまりポテンシャルは1回だけ更新すれば良い」というのはわかりにくい．あとで出て来る言葉をつかえば各点の「走査」は一度でいいということ．
lecture7, page 10 増加可能パス．前ページの続きだとすれば，点 s と点 1 のあいだの枝にたいするラベル1, 4 が逆．そのときは 1 だけ増やせる．
lecture8, page 21 閉路消去法 (疑似コード)．初期設定ですべての辺の流れをゼロと設定するのは不適切．
Section4-3, page 3 Lagrange 緩和のアイディア．最適値は31.
Section4-3, page 9 Lagrange 緩和問題の導出．最小化の式の x_wv は x_vw.

試験と成績

受講者が 1 名だったので筆記試験は取りやめた．授業への貢献度と宿題と口述試験にもとづいて，「秀」の成績をつけた．

授業記録

11/25/07 Classes 1-2

雑談 (1815-25), シラバスなど授業について (1825-30), Slides (lecture1-new, 1830-2100), ハミルトン閉路の存在しないばあい (lecture2, page 33; 2100-2110), 川渡りと油分け (旧スライド分; 2115-2130), 雑談 (2130-2145).

久保のポワーポイントスライドを 20 インチモニターに表示して講義．学生はノートとテキストをかなり読んでいた．よってペースは早目かもしれない．授業中にできる宿題は，ホワイトボードで解説してもらった．

宿題など

授業中あるいは授業後に済んだ分には "done" と記入する．

lecutre1, 宿題 1, 2, 3, 4 は済み．
lecture2, pages 24-25. ハノイの塔の新ルールでのディスク3枚のときのグラフ [done] と移動回数の漸化式は宿題．次回までにできなかったら，追加のヒントを与える．[12/5 追加のヒントを与えた; 12/12 done]
lecture2, page 26 (ハノイの塔おまけ問題)は省略．
lecture2, page 31. 最適巡回路は宿題．この問題に限らないが，結果だけでなく説明も欲しい．done
lecture2, pages 32-33. ハミルトン閉路問題は済み．これは将来の授業では省略してもよい内容．
lecture2suppl. 油分けパズルは宿題．[12/5 には 10 ステップの答; 12/12 に 9 ステップの答 done] のちに Ruby プログラミングもやってもらう予定．[done; プログラムの穴埋めとした]
lecture3, Ω記号とΘ記号はカットした．
ex3 は省く．

12/5/07 Classes 3-4

前回の宿題の確認とヒント (1815-1840),
lecture4, ex4 (1840-2010),
lecture5 up to page 35, ex5 (2010-2145),
雑談 (2145-2200).

lecture4, pp. 38-53 「番外編 Excel による線形計画」は自習のこと．小暮・柏木も参照するといい．
ex4 (演習 3 は省く) は宿題．演習 1 は Excel でもやること．[12/12 done]
lecture5, pages 14-18 のLagrange 緩和一般論は非表示だったので見落としてしまった．数学の授業でやった内容のはずなので見ておくこと．
ex5 (等式制約のほうは任意) は宿題．導出すること．[12/12 done]

12/12/07 Classes 5-6

雑談 (1810-20), Lagrange 未定乗数法の法線ベクトルによる解釈 (1820-30), lecture5, pages 36-52 (1830-1905), lecture6, pages 1-46 (1905-2100), Part 2 までの宿題の確認 (2100-2150).

この科目は半学期で終わる．半学期でやるほうが一学期かけてやるより勉強しやすいと受講生．その通りだと思う．同じ話題を何週間もかけてやると，わけがわからなくなりがちだ．
lecture5, pages 36-39 の運賃の話を説明してもらった．双対変数は特定区間の潜在価格と解釈できる．
lecture5, page 40 以降の一般論は今回はカバーした．将来はカットしてもいいだろう．
Part 3 のスライドは理論的には軽い．アルゴリズムを理解して実行できるのが目標．
Part 2 までの宿題はプログラミング以外済み．本日は解答をゆっくり確認した．
油分けの演習問題では，受講生がすべての場合を網羅的に調べてきた．思ったほどの量ではなかった．その考えはプログラミングに応用できる．
lecutre6, page 44 の演習問題 1 は宿題 [done]. 演習問題 2 については参考資料を渡す．

12/19/07 Classes 7-8

雑 (1810-20), lecture6 前半の宿題 (1820-30), lecture6, pages 47-120 (1830-2005), lecture7 (2010-2120), 雑談 (2120-45).

lecture6 演習問題 2 は宿題ではなかったのだが，最短路を見つける道具を紐で作って来てくれた．これでダイクストラ法の原理とか点の走査順を小学生にも分からせることができるだろう．
今回は pages 75-76 (longest path problem) をカットした．将来は 3.1.4, 3.1.3 節もカットできるかもしれない．
lecture6, pages 71-75 のソートはひじょうに簡単にあつかった．ソートについては時間があればあとでまとめてやりたい．
lecture6 の宿題は航空機離着陸への Ford法 (高速化版) の適用 [page 105; done]，演習問題 1 [page 118; done].
最大フロー最小カット定理に大いに感動する受講生．自分もこの定理は美しいと思う．
lecture7 の宿題は演習問題 1-2 [pages 36-37; done].

1/09/08 Classes 9-10

油分けプログラミング (考え方; 1815-1935), 最小費用流問題 (lecture8; 1935-2035), 4.1 (Section 4-1; 2040-2100), 4.3 (Section 4-3; 2100-2135), 油分けプログラミング (利用できるコマンドを列挙など; 2135-2200).

Classes 1-2 で油分けパズル (水移し問題) の Ruby プログラミングを宿題にしていた．冬休みは ruby でプログラミングするときの注意などについて，かなりの量のメールを送っていた．受講生は新年に予定外の仕事が入ったりしたこともあり，まだ動く結果は出ていないとのこと．Rubyist Magazine の「だん」による「Ruby ではじめるプログラミング」を読んだあとに，指定していた Chris Pine のチュートリアルを読んだという．それらを読んだときは楽勝だと思ったらしいが，じっさいにコーディングをはじめてみるとさっぱりで，プログラミングの大変さを感じたと．(その後，高橋征義らの『たのしい Ruby』を図書館で入手したらしい．) 授業では，準備した図を用いてアルゴリズムの動きを追った．「こういう結果が出るようにメソッドを定義する」という言い方が多かったかな．図とにらめっこしながらコーディングするといいだろう．「オブジェクト指向プログラミングじゃなくてもいい」と休み中のメールでは言ったけど，今日だいぶヒントをあげたのでそれは撤回する．個々の水移し問題が属するクラスを定義してインスタンスを作るやり方でやってもらう．
本日の範囲，テキストの記述はけっこう高度だが，スライドの方は易しい．スライドに沿ってやった．
宿題は mcf-ex1 の最初の問題 [done] とテキストpage 104 で最悪の初期フローからはじめる問題 [done].
学期末までの宿題として，ダイクストラ法の Ruby プログラミングを課す [done]. オブジェクト指向でやってもらう．各インスタンスは枝に重みのついた有向グラフと始点を持つ (終点は指定する必要なし)．各点への最短距離と最短路を出力するメソッドを作ること．

1/23/08 Classes 11-12

前回分宿題のチェック (1815-25), 油分けプログラミングの経過を報告してもらう (1825-40), 代表的アルゴリズム (1840-1945), 油分けプログラミング (1945-2135).

期末の「口述試験」として，代表的アルゴリズム (各種ソート法と力任せ検索法) を説明してもらった．ITpro「今からでも遅くない！アルゴリズム入門」Part 2, 定番アルゴリズムを徹底理解！ (5, 8, 9 節を除く) を材料にした．並べ替えは当初ホワイトボードでやってもらう予定だったが，じっさいは当日百円ショップでボクが買って来たトランプを使って例を説明してもらい，コードが載ってるものについてはコードと対応させながら実行してもらった．受講者は for 文を知らなかったため理解できていなかったプログラムがあったが，ちゃんと「どこでインデックスが増えているのか？」と悩んだようなのでよしとしよう．
これらの並べ替えアルゴリズムは要素数がいくつであっても使える．はじめから要素の範囲が分かっている場合は，その範囲分の場所を用意しておいてそこに突っ込んで行く方法も考えられる．名前を並べるとき，まずはよみがなの最初の文字がア行に来るのかカ行に来るのか……を基準にするなどだ．受講者は仕事で書類のソートを手作業でする機会がよくあり，この方法を採ることが多いそうだ．これはクイックソートの一般化と言えるだろう．
油分けプログラミングについて，ボクの書いた cups2.rb でいえば以下にあたるものを受講生と対話しつつ構築してみた:
- pairs(0...3) とやれば配列 [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]] を返す関数 pairs(range).
- [10,7,3].pour(0,1,[10,0,0]) とやれば配列 [3,7,0] を返す Array メソッド pour(i,j,a).
- [10,7,3].state([10,0,0],[[0,1],[1,2]]) とやれば配列 [3, 4, 3] を返す Array メソッド state(start, actions).
(こうやって改めて眺めると，pour(i,j,start) は state(start,[[i,j]]) だからメソッドをまとめてもよかったかも．) また，油分け問題をインスタントとするクラス Cups の利用例を通して，Cups で定義すべきメソッドの動きを追った．
講義はこれにてほぼ終了となる．外部評価などを気にして下手に講義回数を規定分こなすような愚かなことはしない．受講生の理解が速かったから，標準より早く終わったのだ．また，プログラミングでは，講義を聴くよりも実習の時間を取ることのほうが重要なのは説明するまでもないだろう．といいたいところだが，じっさいは毎週 2.5 講義分くらいの時間をかけたので，6週目の今日で正味15 回分やったといえる．[メールのやりとりによるプログラミング指導にも多大な時間を割いた．] プログラミングは高い評価を得たい受講者のためのエクストラ・タスクと考えられる．
「[高橋征義らの『たのしい Ruby』] を読んだからといって，[この科目の課題のような] プログラムを書けるものじゃないことが分かってきました」と受講生．この科目の課題のような，アルゴリズムを重視するプログラミングについて言えば，単に言語をマスターするだけではむずかしいだろう．(もちろん不可能ではないから課題にしてるんだけどね．) だからプログラマは『アルゴリズムとデータ構造』といった類いの本やら科目で，疑似言語などでアルゴリズムを学ぶわけだ．で，疑似言語で書かれたアルゴリズムとプログラミング言語が分かればすぐプログラムが書けるかというと，特に最初のうちはそうでもないだろう．完璧に理解したつもりのアルゴリズムでも，それを実際のコードで表現するには努力がいる．人に読まれるための疑似コードとコンピュータに読まれるためのプログラミング言語によるコードとには，またギャップがある．だから『C 言語によるアルゴリズムとデータ構造』といった類いの本が売れるわけだ．
課題のプログラミングがビジュアルでないことは特に制限にはならない．グラフを表すテキストデータからグラフを描画するソフトウエアがあるからだ．「最短路問題，グラフ描画，家系図」を参照．

その後 (Classes 13-15 に相当)

プログラミング課題にたいするメールでの指導．細かいやりとりなので，講義よりも文書のやりとりによる指導のほうが有効と考えた．まず，途中経過分をメールで提出してもらった．変数名やメソッド名の分かりにくさ，日本語全角はエラーの原因になるので避けるべきことなどを指摘．むずかしい部分で行き詰まったようなので，油分け問題はプログラムの穴埋め問題とした．その後，2月17日に受け取ったバージョンが両方ともきちんと動作したので，それで完了とした．ダイクストラ法のプログラムがオブジェクト指向でなかったのは多少残念．問題としては，多少冗長な部分や整形が不十分で while ... end の対応が見にくい部分があったていど．

[Up: list of courses]

三原麗珠