最適化手法

岡本 吉央

資料

• 7/31 期末試験
  • 4問出題する．
  • 出題範囲は，ネットワーク最適化 (1)〜(7)
  • A4用紙の両面に，自筆で書いたメモのみ持ち込み可．
  • 問題と解答例
• (15) 7/26 ネットワーク最適化 (8)：最小費用流問題の応用 (2)
  • スライド | 印刷用スライド | 演習問題はありません
• (14) 7/19 ネットワーク最適化 (7)：最小費用流問題の応用 (1)
  • スライド (7/20修正) | 印刷用スライド (7/20修正) | 演習問題
  • 修正箇所 (7/20)：スライド7ページにて「tを始点」を「tを終点」に． スライド27ページの18〜20枚目にて「pt」を「p_t」に (印刷用スライドでは修正の必要なし)．スライド37ページは全面的に修正 (前回のものを間違えて挿入したため)．
• (13) 7/12 ネットワーク最適化 (6)：最小費用流問題
  • スライド (7/13修正) | 印刷用スライド (7/13修正) | 演習問題 (7/13修正)
  • 修正箇所 (7/13)：スライド62ページに「頂点s, a, b, c, d, tのポテンシャルをそれぞれp_s, p_a, p_b, p_c, p_d, p_tとする (ただし，p_s=0)」を挿入．スライド80ページの下から2行目にて「最大流問題の応用」を「最小費用流問題の応用」に．演習問題前文にて「関すｒう」を「関する」に．
• (12) 7/5 ネットワーク最適化 (5)：最大流問題の応用 (2)
  • スライド | 印刷用スライド | 演習問題
• (11) 6/28 復習テスト2
  • 注意：試験場は「5533教室」
  • 2問出題する．
  • 出題範囲は，5/17の講義「分枝限定法」と5/24の講義「切除平面法」．
  • A4用紙の両面に，自筆で書いたメモのみ持ち込み可．
  • 問題
  • 問題と解答例 (7/8修正)
    • 修正箇所 (7/8)：7ページ目，上から8行目にて「s₁=-5/2」を「s₁=1/2」に．
• (10) 6/21 ネットワーク最適化 (4)：最大流問題の応用 (1)
  • スライド (6/23修正) | 印刷用スライド (6/23修正) | 演習問題 (6/23, 7/4修正)
  • 修正箇所 (6/23)： スライド30ページ，右の図にて，×を付ける箇所は，aを始点としbを終点とする辺とdを始点としgを終点とする辺の2つ． スライド48ページにて「3kmより長く」を「3km以上」に． スライド49ページにて「上側：オアシス，下側：遭難者」を「上側：遭難者，下側：オアシス」に． 演習問題10.3にて「2kmより長く」を「2km以上」に．
  • 修正箇所 (7/4)： 演習問題10.3にて「暑かった」を「扱った」に．
• (9) 6/14 ネットワーク最適化 (3)：最大流問題
  • スライド | 印刷用スライド | 演習問題
• (8) 6/7 ネットワーク最適化 (2)：最短路問題
  • スライド (6/8修正) | 印刷用スライド (6/8修正) | 演習問題 (6/8修正)
  • 修正箇所 (6/8)： スライド9ページ，および，演習問題8.3にて，二俣新町→千葉みなとの「210」を「290」に．二俣新町→蘇我の「290」を「400」に．
• (7) 5/31 ネットワーク最適化 (1)：ネットワークの導入，ネットワークによるモデリング
  • スライド | 印刷用スライド | 演習問題 (5/31修正)
  • 修正箇所 (5/31)： 演習問題7.1(2)にて，2つ目の「{a,g}」を「{b,g}」に． 演習問題7.3にて「任意の2頂点」を「任意の異なる2頂点」に．
• (6) 5/24 整数計画法 (5) ：切除平面法
  • スライド (5/24修正) | 印刷用スライド (5/24修正) | 演習問題 (5/24修正)
  • 修正箇所 (5/24)： スライド49ページにて「=52-s₂+3s₃」を削除． 演習問題6.2にて，「- 2x₁ + 3x₂ ≦ 0」を「2x₁ - 3x₂ ≦ 0」に．
• (5) 5/17 整数計画法 (4) ：分枝限定法
  • スライド (2014/4/24修正) | 印刷用スライド (2014/4/24修正) | 演習問題
  • 修正箇所 (5/17)：スライド11ページにて「P(1,1,x₃,x₄)」を「P(0,1,x₃,x₄)」に． スライド13ページにて 「x₂,x₃,x₄∈{0,1}」を 「x₃,x₄∈{0,1}」に． スライド32ページにて 「P(x₁,1,x₃,1)」を 「P(x₁,0,x₃,1)」に． スライド41ページにて 「x₁,x₃,x₄∈{0,1}」を 「x₃,x₄∈{0,1}」に．
• (4) 5/10 復習テスト1
  • 注意：試験場は「5533教室」
  • 3問出題する．(注：2問ではない．)
  • A4用紙の両面に，自筆で書いたメモのみ持ち込み可．
  • 問題
  • 問題と解答例
• (3) 4/26 整数計画法 (3) ：緩和問題とその威力
  • スライド (2014/4/24修正) | 印刷用スライド (2014/4/24修正) | 演習問題 (4/28修正)
  • 修正箇所 (4/28)：問題3.1にて，条件「23x1」を「23x₁」に．問題3.2の1にて「○○ ≧ 100」の○○の部分は分母を消して，「分子≧100」とする．
• (2) 4/19 整数計画法 (2) ：整数計画法によるモデリング
  • スライド (4/23修正) | 印刷用スライド (4/23修正) | 演習問題
  • 修正箇所 (4/23)：スライド14ページにて 「3+4=7」を「3+2=5」に．
• (1) 4/12 整数計画法 (1) ：線形計画法の復習，整数計画法の導入
  • スライド (4/16修正) | 印刷用スライド (4/16修正) | 演習問題
  • 修正箇所 (4/16)：スライド19ページにて「+-3x₂」を「-3x₂」に．

コメント

• 7/31 期末試験
  • 採点が終わりました．(8/15)
  • 採点結果について，メールや電話での問合せには応じられません．宜しくお願いします．
  • 期末試験を受けた人数は71で，得点分布は以下の通りでした．
    
  • 採点は1点刻みで行っています．
  • 受験者全体に対して，60点が10人 (14%程度)，55点以上が25人 (35%程度)，50点以上が46人 (64%程度)，45点以上が53人 (75%程度)，40点以上が59人 (83%程度)．
  • 60点，55点，50点のところに際立ったピークがあるのは，5点ごとに部分点を与えるような採点基準を併用しているためです．
  • 試験問題として基礎的な内容を，最短路問題，最大流問題，最小費用流問題から，90分の試験時間で回答できるように出題しました．
  • そして，復習テストを含めた3回の試験の総合得点の分布は以下の通りです．なお，0.5点は切り上げて1点にしています．
    
    期末試験を受けていない人は「未受験」という扱いにし，ここには含めていません．
    全体的にとてもよくできていました．100点を超えている人の成績は100点であるものとして報告をします．そのような人は17名いて，最高得点は109点です．成績分布は，Aが44名，Bが12名，Cが7名，Dが6名，Eが2名です．Eだった人や未受験の人はぜひまた来年度挑戦して下さい．
  • 以下，問題ごとの講評です．
    • 問1．Dijkstra法を実行する問題．ラベルに基づいて確定頂点を決めていくので，ラベルがどのように変更されていくのか明示されていない答案は大幅に減点されています．そのような答案がかなり多くありました．15点満点を獲得した人は21名しかいませんでした．最短路木が明示されていない答案も大幅に減点しています．また，「頂点sから各頂点へ向かう最短路の長さがそれぞれ何であるか，答えよ」と問題文に書いてありますが，「各」という日本語は「多くのもののひとつひとつ」という意味です．そういうことなので，sを始点としてtを終点とする最短路の長さしか答えていないものは減点しています．正しく日本語を理解できるようにして下さい．
    • 問2．(1) 割当問題を最大流問題として定式化し，(2) 最大流を求め，最小カットを使ってその証明をする問題．これはよくできていました．15+15の30点満点を獲得した人は51名です．流れやカットが明示されていない答案は大幅に減点されています．小問(1)の定式化が間違っていても，小問(2)にて，その間違った定式化に対する正しい最大流と最小カットを答えている答案に対して，小問(2)には満点を与えました．
    • 問3．最小費用流問題に対して，与えられた流れが最小費用流であることを補助ネットワークとポテンシャルを用いて証明する問題．これは点数のばらつきが大きな問題でした．15点満点を獲得した人は25名ですが，10点未満の人が25名です．補助ネットワークが正しく描けていれば5点与えています．そこから10個の不等式が導けていれば，さらに5点．逐次最短路法を使って計算している答案もいくつか見られましたが，それで正答に辿りつくことは難しかったようです．(上で挙げた解答例に，逐次最短路法を用いた計算も追加しました．) 最終的に計算されたポテンシャルとして，「bのポテンシャルが-6または-7，tのポテンシャルが-14または-15」と答えている答案もありましたが，この答え方では「bのポテンシャルが-6，tのポテンシャルが-15」という組合せも許されてしまいます．しかし，それは10個の不等式をすべて満たすわけではないので，よくありません．
    • 問4. 以下，皆さんの解答とそれに対するコメントを書きます．
  • 問4の解答とコメントです．順不同です．
  • 半年間という短い間でしたがお世話になりました．講義はとても分かりやすく，生徒の要望にこたえてくれる授業の進行の仕方に感動しました！また機会があったらお世話になります．ありがとうございました！ ---こちらこそありがとうございました．それと，皆さんは「生徒」ではなく「学生」です．生徒と学生はいろいろな意味ではっきりと区別されます．間違えないようにお願いします．
  • 解答見にくくてゴメンなさい！授業楽しかったです． ---ありがとうございます．解答は問題なく読めました．
  • 試験頑張りました．よろしくお願いします． ---お願いされても困ります…．
  • 単位下さい ---お願いされても困ります．
  • 単位をお願いします！！おせわになりました． ---お願いされても困ります．
  • 単位下さい！！ ---お願いされても困ります…
  • 最後の方が難しかった． ---授業が簡単であっては大学に来る意味がないので，ちょっと難しいぐらいがちょうどいいと思ってます．
  • 難しかったです． ---難しいぐらいがちょうどいいです．
  • 難しかった． ---難しいぐらいがちょうどいいです．
  • 難しいです． ---難しいぐらいがちょうどいいです．
  • ありがとうございました．難しかったです． ---難しいぐらいがちょうどいいと思います．
  • ネットワーク問題は難しかった． ---難しいぐらいがちょうどいいと思います．
  • 修正補助ネットワーク頑張ったで． ---はい，正しくポテンシャルも計算できてるので正解です．
  • 主にネットワーク最適化で習った内容をpcで行わせるアルゴリズムを考えてみたいと思いました． ---はい，ぜひそのようにしてみて下さい．
  • たぶんOR第2落としました．今までありがとうございました． ---OR第2は私の担当ではないので，私に言わないでください．ありがとうございました．
  • レジュメが見やすく分かりやすかったです．先生の説明も分かりやすく，理解しやすい授業でした．問題1の解答が見づらくなってしません． ---ありがとうございました．問題1の解答はちゃんと読めたので大丈夫です．
  • 最初の授業はとろうか悩みましたが，とってよかったです．授業はわかりやすかったですが，演習ややこしかったです．答えほしかったです． ---とってよかったと思えてもらえて，うれしいです．
  • 4問出題と聞いていましたが，問題4がこのような問題であり，さらに配点が0点だったので予定がくずれました (笑) ---勝手に予定をされても困ります…．
  • 授業わかりやすかったです． ---ありがとうございました．
  • 分かりやすく教えてくれたので良かったです． ---そう思ってもらえてうれしいです．
  • この期末の範囲は理解するまでかなり苦しんだけれども，講義の分かりやすかったので，なんとか理解できた．前期の間だけでしたがありがとうございました． ---こちらこそありがとうございました．
  • まさか問4がこんな形式だったとは…前期の間ありがとうございました．あと咳が止まりません．つらいです． ---はい，こんな形式でした．ありがとうございました．
  • 半期ありがとうございます！最適化たくさん勉強したので他のところからも出してほしかったです． ---いろんなところから出すと4問になりませんし，90分で解答できなくなりますので，このような形になっています．こちらこそありがとうございました．
  • 思っていたよりも幅広い分野に応用できることに興味をもちました． ---そのように思ってもらえてよかったです．
  • 問題4は配点ありませんか？問題4にも配点がほしいです！！おねがい致します．最後に半年ありがとうございました． ---問題4には0点という配点があります．
  • おつかれさまでした． ---おつかれさまでした．
  • 馬鹿だからでしょうか．全然できませんでした．ごめんなさい．でも単位を下さい．いやお金でも良いです．同情するなら金をくれ！半年ありがとう． ---お金はあげられません．
  • 今期はお世話になりました．とてもわかりやすかったです．また中央大学に来てくださいね☆ ---こちらこそありがとうございました．
  • 4問出すってこういうことですか (笑) やられましたよ （´・ω・｀）あと先生はどういった経緯でこの学校にくることになったのですか？ ---昨年度担当されていた後藤先生が今年度は海外にいってらっしゃるので，代わりに私が講義を担当しました．後藤先生が昨年度担当されていた科目はすべて違う教員が今年度だけ担当します．
  • 問2の(2)の図がきたなくてすいません． ---問題なく読めたので，大丈夫です．
  • ありがとうございました！ ---ありがとうございました．
  • 計算が大変な部分がありましたが，非常に講義がわかりやすかったです． ---ありがとうございました．
  • 楽しかったです！ありがとうございました！！こーゆう勉強したいけど，研究室ではプログラムでやる感じなんですかね？ ---おそらく，研究室ではプログラムでやる感じです．手で解ける問題は小規模なものに限られます．大きな問題を解くときは計算機を使った方がよいです．
  • 先生の講義のスライドや説明，すごく分かりやすかったです． ---ありがとうございます．
  • 図を大きく書くと良いとwebページに書いてあったので，問2で実行した．問3では図をもっと大きく書きたいのにスペースが足りない．問1の幅をもっと狭くして問3のスペースを作って欲しかった．もしくは問4なければスペース足りたと思う． ---問3は逐次最短路法の動きをすべて解答欄に書こうとすればスペースが足りなくなります．必要なものは補助ネットワークとポテンシャル，そして，そのポテンシャルがなぜ本当にポテンシャルであるのかという説明だけなので，逐次最短路法の動きをすべて書く必要はありません．それは計算用紙に書けばよいだけのものなのです．
  • 最小費用流の問題は図を多く書くので別紙がよかったです．4ヶ月間のご講義ありがとうございました． ---上の方と同じ意見だと思いますが，私の回答も上と同じです．ありがとうございました．
  • 点数足りてますように． ---どうでしょう．
  • 面白かったです．ありがとうございました． ---ありがとうございました．
  • 今までOR第1や第2で教わってきた教授よりもはるかに分かりやすかったです．本当にありがとうございました． ---こちらこそありがとうございました．
  • 最適化手法の授業に興味が持てました． ---ありがとうございました．
  • 最適を追求する授業は面白い． ---そう思ってもらえてよかったです．
  • 授業で扱った最大流問題の応用はむずかしくて考えるのがすごく大変でした．最後まで，補助ネットワークがどこまでか分かりませんでした．とても手が疲れました．授業は毎回具体的に数値を出し，例題を扱ってくれたのがとても分かりやすかったです．特に難しい問題に対してはとてもありがたかったです．ありがとうございました． ---具体例を通して理解するように努めたので，その効果があったようでよかったです．
  • ポテンシャルや露天掘りのような難しい問題が出ると思っていました． ---ポテンシャルは出してるつもりなのですが．
  • ポテンシャルを出題してほしかったです．楽しい授業でした．ありがとうございました． ---ポテンシャルは出題したつもりなのですが．
  • わかりやすい講義でした． ---ありがとうございました．
  • テストはもっと難しいと思ってた． ---もっと難しくすると，90分で解答できなくなるので，こんなものです．
  • もう少し複雑な問題がでると予想していたため，少し安心しました． ---もっと難しくすると，90分で解答できなくなるので，こんなものです．
  • あせりました ---どうしてですか？
  • 授業ありがとうございました． ---こちらこそありがとうございました．
  • 今までありがとでした．復習テストが各内容ごとにわかれていたので，どの内容においても，しっかりとテスト勉強ができました (多分)．ちなみに，頭が痛くなってしまうので私は十六茶が嫌いです． ---こちらこそありがとうございました．
  • とても楽しい授業でした．ありがとうございました！！ ---こちらこそありがとうございました．
  • せめて逐次最短路法は出題してほしかった． ---逐次最短路法を出題すると，時間内に解答することが難しくなりそうなので，見送りました．
  • ありがとうございます ---ありがとうございます．
  • テストお疲れ様です〜． ---おつかれさまでした．
  • ありがとうございました． ---ありがとうございました．
  • とっても楽しかったです．前の先生よりもずっと分かりやすかったです． ---ありがとうございました．
  • テスト予想外でした． ---そうでしたか．
  • 4問のうち1問はこれなんですね！そして今回は名前先生にバレてしまうんですね〜ハズカシイ．これ本当に0点なんですか？気持ちで3点くらいくださいな． ---はい，本当に0点です．
  • 高速で計算ができる計算機が普及している今，手計算によって，手間のかかる問題をガツガツ解くのは，貴重な経験であった．また，良いか悪いか分からないが，先生の授業はスライドを見ただけで，かなり理解できた．授業ではさらにユーモアあふれる先生のキャラクターが面白く，全く眠くならなかった．短い間でしたが，ありがとうございました． ---スライドを見ただけで理解できてしまう，という形でスライドは構成されていないはずなので，講義の中のはなしの内容や演習問題を含めて理解するようにして下さい．ありがとうございました．
  • 問題が4問というのにだまされた． ---だましてないです．4問出題されてますから．または，問題3までで，小問を数えれば4問になってますし．
  • 楽しかった． ---ありがとうございました．
  • 大問4つってこういうことだったんですね…．半期ありがとうございました！ ---こちらこそありがとうございました．
  • 以上です．皆さんおつかれさまでした．この講義の内容について，細かいことは忘れてしまったもいいですが，基本的な考え方は忘れてしまっても思い出す必要が出てきたときに，調べて思い出せるようにしておいてください．
• (15) 7/26 ネットワーク最適化 (8)：最小費用流問題の応用 (2)
  • コメントありがとうございました．公序良俗に反するものは掲載しません．
  • 7/5のPDF35/83の真ん中のところの値はどうやって決めているのですか？ ---最大流問題を解いています．
  • 半年間ありがとうございました！！説明がわかりやすくて良かったです． ---こちらこそありがとうございました．
  • 1つ1つの計算を着実に行うことができれば，解を得られると思いました． ---そうだと思います．着実に行って下さい．
  • 質問してめっちゃわかりました！今までありがとうございました！ ---こちらこそありがとうございました．
  • つらいです． ---頑張って下さい．
  • Vielen Dank. ---こちらこそありがとうございました．
  • 定式化しろみたいな問題出ますか？あと基礎的な内容と応用の比率は？ ---講義でやった内容はすべて範囲であると考えて下さい．
  • 解答用紙や計算用紙のスペースが足りなくなってしまったら，もう一枚もらうことは可能ですか？図を書くことが多そうで心配です． ---私は試験に立ち会わないので何ともいえませんが，計算用紙はもう一枚もらおうと試みて下さい．ただし，解答用紙は1枚で留めて下さい．
  • テストが，逐次最短路法など書くことが多過ぎて90分では終わる気がしません．解答用紙は3枚くらいほしいです． ---解答用紙1枚で納まるような問題にする予定です．
  • 最終日晴れましたね！テスト頑張ります！ ---はい，よろしくお願いします．
  • テストがんばるぞー．おー ---是非がんばってください．
  • よいです ---ありがとうございました．
  • 中大に移籍しますか？半期ありがとうございました． ---移籍するという予定はありません．こちらこそありがとうございました．
  • めっちゃ腹減っててめっちゃねむい ---しっかり準備してきて下さい．
  • ネクストテストズヒントを下さい ---すみませんが，ありません．
  • 大人はわかってくれない ---全然勉強してないなんて決めつけられないように，しっかりと準備して試験に臨んで下さい．
• (14) 7/19 ネットワーク最適化 (7)：最小費用流問題の応用 (1)
  • コメントありがとうございました．
  • 演習の(2)は何を言えてれば証明されてることになるんでしょうか？ ---与えられている流れに対応するポテンシャルが存在することを示して下さい．
  • ポテンシャルが出てきたあたりから何をやっているのか良くわからない．ポテンシャルを使う意味が理解できていない． ---1つは，逐次最短路法において最短路の計算をするときに辺の長さが非負になるように調整するために使う用途です．もう1つは，流れが与えられているとき，それが最小費用流なのかそうでないのか判定するために使う用途です．
  • 合格点は60点ですか？ ---はい，その通りです．
  • 点数とれる気がしません (;_;) ---頑張って下さい．
  • 問題を解き進めていくうちに図が複雑になってしまうと思いました ---コツは大きく書くことだと思います．小さく書くと細かくなるので，大きく書けばそれが避けられます．
  • こんな複雑な問題が出るんですか？僕にはできません．あと最大流の応用のところが複雑で困ります ---「出る」というのが「試験に出る」という意味ならば，出る可能性はあります．「実社会で出る」という意味ならば，これよりも複雑なものの方が多いです．むしろこの講義でやっていることは簡単なものです．
  • 中大生になぁ！！こんな問題解けるわきゃねぇだろぉぉぉぉぉ！！！ ---解けます．頑張って下さい．
  • ポテンシャルの問題はテストでもこんな複雑な式がでるのですか？とける気がしないですが ---演習問題をやってみれば，実際にはそれほど複雑でないことが分かると思います．やって下さい．
  • (1) cos x = xをみたすxを求めよ．(2) ブラック＝ショールズの偏微分方程式を証明せよ．(3) 素数の規則を求めよ． ---自分でやって下さい．
  • 先週と同じシャツですね！先生の講義はわかりやすかったです！ ---ありがとうございます．
  • 教室が寒いです ---すみませんが，私に冷暖房を操作する権限はありません．
  • 今日は冷房が強い気がしました．半袖は寒くないですか？ ---特に寒いわけではなかったです．はい．
  • 夏カゼ辛い…先生も冷房の使いすぎには気をつけた方が良いですよ！ ---ありがとうございます．
  • Ich liebe dich♥ ---ありがとうございます．
  • リーチ，一発，ツモ，ドラ5! ---5! = 120なので，それはありえません．
  • おっきいちちとちっちゃいちちどっちがお好きですか？ぼくは幼女が大好きです！！ぐへっ ---警察の厄介にならないようにして下さい．
  • 一番好きなカップヌードルのサイズは？味は？ちなみに私はKINGサイズのチリトマト ---カップヌードルは食べません．
  • 一番好きなかき氷の味は何ですか？私はやっぱりいちごです．KINGのチリトマトも好きです． ---この前，抹茶金時のかき氷を食べました．
  • 難しいです．勉強します．来週はテストについてのことは一切やらないですか？私もKINGのチリトマトです ---表現としては難しいですが，次回行うことは試験範囲には入らない，としか言えません．また，試験対策用の講義を行うことはしません．(なので，そういうことを期待して講義に来るというのは全く無意味なので注意して下さい．)
  • テスト大変そうです…元気ですか？ ---はい，元気です．
  • 海派ですか？山派ですか？ ---おそらく山です．
  • 暑いのと寒いの，どちらが好きですか？ちなみに私は寒い方が好きです． ---寒い時期には大抵体調を崩すので，それよりは暑い時期の方がよいです．
  • ネットワーク問題にファジィ理論を応用することは可能ですか？ ---可能です．実際にそのような研究もあります．
  • スイスはどうでしたか？ ---よいところです．機会があればぜひ行ってみて下さい．
  • ♥ ---♥
  • 座右の銘を教えて下さい ---残念ながらそういうものは持ち合わせていないです．
  • 座右の銘は？ ---残念ながらそういうものは持ち合わせていないです．
  • 最近あった嬉しい事を教えて下さい ---残念ながら思いつくことがないです．
  • 好きなアーティストは？ ---そういう点に関して私は雑食です．なので，特に「好きな…」というのはないです．
  • 私にアドレスを教えて下さい．一緒にいいことしませんか？ (はぁと) ---講義スライドの表紙に私の連絡先は書いてあります．
• (13) 7/12 ネットワーク最適化 (6)：最小費用流問題
  • コメントありがとうございました．
  • まーじゃんしましょう！ ---いいですよ
  • 先生はスカート派ですか？ホットパンツ派ですか？ ---どちらの派閥にも所属してません．
  • 股間のチャック開いてましたよ．とても素敵なパンツですね♥ ---あとで確認しましたが，開いてませんでした．
  • 何色のパンツはいてますか？僕はノーパンです！ ---すずしそうですね．
  • えらばれたのは綾鷹でした ---私は十六茶を選んでます
  • 風邪をひきました．喉がとても痛いです．ポテンシャルややこしいです．寒いです ---お大事に
  • 口内炎が痛い…貼るタイプのクスリが良いですよ ---今度口内炎になったら試してみます．
  • 口内炎が痛いです．早く治る方法を教えて下さい． ---貼る薬がいいそうです．
  • すごくトロトロします ---冷えピタでも貼って下さい．
  • 暑い！夏です！高校野球の季節です！家でゆっくり野球見てたい (笑) ---夏休みになったら自由にどうぞ．
  • 今回のPDFミスは修正ありますか． ---修正しました．
  • 50/82のスライドでaのポテンシャルが-2 → -3になる理由がよくわかりません． ---ポテンシャルはすべての頂点において更新します．そのため，aでも更新します．修正補助ネットワークで，sからaに至る最短路の長さが1なので，元のポテンシャルである-2から1を引いて，修正後のポテンシャルが-3になります．
  • 「夏」とかけまして，「最適化手法」と解きます．その心は？ ---みなさんから答えを募集しますので，ぜひお寄せください．
  • テストがんばる ---がんばってください．
  • テスト勉強がんばる ---がんばってください．
  • テストにはどの問題が出ますか？具体的にお願いします． ---それは答えられません．
  • 試験に電卓の持ち込みは可能ですか？ ---それは不可能です．
  • 期末テストは，今までのテストと難易度かわらないですか？ ---難易度というのは人によって感じ方が違うものなのでなんとも言いがたいですが，演習問題をしっかりとやってきて下さい．
  • ネットワークはややこしい問題が多いですね．大変です． ---ひとつひとつの手順を確実に踏んでいって下さい
  • やることが複雑すぎて理解できなかった！あととってもいいシャツですね！ ---よく復習をしてください
  • 手順が多くて頭の中がごちゃごちゃします… ---次回の最初にもう一度まとめをします
  • 逐次最短路法の手順を知りたいです． ---次回の最初にもう一度まとめをします
  • 授業完全に置いてかれました．理解できません． ---最大流問題のところから続いているので，まず最大流問題のところの復習からしてみて下さい．
  • 各頂点のポテンシャルは各頂点の何を意味しているのですか？ ---グラフが電気回路を表しているとしたとき，電位に対応するのがポテンシャルです．流れは電流に対応します．
  • 私のポテンシャルは53万です． ---スカウターが壊れそうです．
  • テストのとき解答がゴチャゴチャしそうです． ---整理して書けるようにしてください．
  • 今回扱った内容は計算量が多いと感じました． ---たしかにそうだと思いますが，ひとつひとつの計算は難しくないので丁寧に行って下さい．
  • (x-a)(x-b)…(x-z)=？ ---なんでしょう．
  • アロハシャツかわいい！！テストの採点ごくろう様です！！！ ---ありがとうございます．
  • 今日のシャツはハワイアンでしたね．次の授業のときは先生が持っているシャツで一番お気に入りのものを着て来て下さい！！ ---それは確約できません．
  • 今何歳ですか？ ---オフィシャルな情報がどこかに載ってますので，それを参考にして下さい．
  • どこ出身ですか？ --- 愛知県碧南市です．
• (12) 7/5 ネットワーク最適化 (5)：最大流問題の応用 (2)
  • コメントありがとうございました．
  • 過ぎた試験の話から
  • テストの点数待ってます！ --- もう少しお待ち下さい
  • テスト気になります． --- もう少しお待ち下さい
  • 続いて，来る試験の話
  • 期末のテスト範囲はネットワーク最適化の範囲のみでしょうか？ --- はいそうです．
  • 結局期末の範囲は？ --- ネットワーク最適化に関して出題します．
  • 期末テストはどれくらいの難度ですか --- 難しさというのは個人的な体験なので，答えようがありません． 講義要項には講義の目的や到達目標が書かれています． その目標に到達しているかどうかを評価するために試験を行うので，そのようなものだと思って下さい．
  • 期末テストの出題範囲を教えてもらいたいです．お願いします． ---ネットワーク最適化です．詳しくは講義で再び言います．
  • 続いて講義について
  • 今日のはややこしくて難しかったです ---応用というのはややこしいものなのです．復習をして下さい．
  • 最大最小問題で最適解を求めなさいという問は最適値も求めるんですか？ ---最適値を要求されていないときは，求めなくてもよいです．
  • 難しいです ちゃんと勉強します ---はい，お願いします．
  • むずかしいので復習しなければならない ---はい，復習をして下さい．
  • 露天掘り問題がイマイチ理解できなかった． ---露天掘り問題は最大流問題であると見るよりも，最小カット問題であると見るべきだと思うので，そう思って解釈をして下さい．
  • 露天掘り問題が少し難しかったです． ---同上，です．
  • 意味プーチン大統領．若いのに禿げそうです． ---分からないところをピンポイントに質問してもらえればありがたいです．
  • 実例なので興味深かったですが，途中でついていけなくなって気づいたら寝てました．すいません． ---実例に興味をもってもらえただけでもよかったです．復習をして下さい．
  • 3つ目の応用で頂点間の容量がなぜ1になるのかが分からなかったです． ---これは，そうすればうまくいく，というものなので，あまり理由について深く気にしないで下さい．
  • 密度についてもう一度説明して下さい ---頂点数で辺数を割ったものです．頂点の数が4，辺の数が6ならば，密度は6/4 = 1.5 です．
  • (2,1,0)規則から(3,1,0)規則になった理由は何ですか？ ---伝統的に，サッカーでは勝ちに2点，引き分けに1点という勝ち点を与えていたようですが，イングランドのフットボールリーグが1981年，勝ちに3点，引き分けに1点という勝ち点の与え方に変えたそうです．理由は勝ちに対するインセンティブを高めるためのようです．それが1990年にFIFAワールドカップにも適用されるようになったそうです．参考
  • 最大流は自分で見つけなければならないのですか？どうやって見つけるのですか？ ---増加道法で見つける，というのが1つの方法です．
  • その他，くだけたコメント
  • 今年の夏はあついですね．アロハシャツが似合ってますね．海に行きたいです．女の子と． ---どうぞ行って下さい．
  • 土日は暑くなるそうですね．体調に気をつけて下さい ---ありがとうございます．
  • いいアロハシャツですね． ---ありがとうございます．
  • 夏休みまで一ヶ月！頑張ります ---はい，がんばってください．
  • もうすぐ梅雨明けですね． ---明けましたね．
  • (＾ω＾) ---こんにちは．
  • 先週のあみだくじ，やって下さいましたか？ ---やりました．
  • あみだくじでお茶の種類決めたはずなのになんで十六茶 (´・ω・｀) ---あみだくじをやった上で，従いませんでした．
  • On ne voit bien qu'avec le cœur. ---L'essentiel est invisible pour les yeux.
• (11) 6/28 復習テストと解説
  • 採点が終わりました．(7/11)
  • 自分の得点を知りたい人は，私に直接聞いて下さい．(個人情報なので，メールでの連絡には応じられません．) その際に，本人確認のため，学生証を提示して下さい．
  • テストを受けた人数は71で，得点分布は以下の通り．
    
  • 今回は，採点を1点刻みで行っています．
  • 受験者全体に対して，25点が27人 (38%程度)，20点以上は75%程度，15点以上は96%程度，10点以上は99%程度．全体的によくできています．
  • 今回は，計算ミスと思われるものや用語の間違いに対して比較的甘く採点しています．それよりは，手順がきちんと踏めているかという点を重視して採点しています．
  • 以下，問題ごとの講評です．
    • 問1．分枝限定法の問題．ナップサック問題そのものに貪欲法を適用しても最適解が得られるとは限らないので，「貪欲法の最適解」というような表現をしてはいけません．最適解とただの許容解の違い，最適値と最適解という用語の意味の違い，など，用語の意味を正しく理解して下さい．暫定解が更新された後，その情報を使わずに進めている答案を誤答とはしませんでした．
    • 問2．切除平面法の問題．カットを計算する際に，まず線形計画緩和の最適解を計算する必要があります．これが明示的に行われていない答案は大幅に減点されています．注意して下さい．「スラッグ変数」とか「スラックス変数」と書いてある答案が散見されましたが，そのような用語は存在しません．正しくは「スラック変数」です．「x₁≧0」という式にスラック変数を導入して「x₁+s₃=0」のようにしている答案がありますが，「x₁≧0」という制約式にスラック変数は必要ないです．仮にスラック変数を導入するとしても，スラック変数は非負でなければならないので，「x₁+s₃=0」とするとスラック変数s₃は非正になってしまい，うまくいきません．導入するならば「x₁-s₃=0」としなければなりません．
• (10) 6/22 ネットワーク最適化 (4)：最大流問題の応用 (1)
  • コメントありがとうございました．
  • [重要] テストに色ペンは持ち込んでOKですか？ 通った道がこんがらがってしまうので． ---OKにします．解答用紙に色ペンで書き込んでもOKです．(ただし，消しゴムで消すことができないので，使用には細心の注意を払って下さい．)
  • 来週テストですね．勉強してきます． ---はい，頑張って下さい．
  • 期末試験の範囲は復習テストのところもはいるの？ ---はいらない予定です．詳細はまた別に連絡します．
  • 期末が大変そうだ ---頑張って下さい．
  • 全体的に少し難しいと感じました．よく復習します． ---はい，よく復習して下さい．
  • 増加道法で，なるべく効率良く少ない手順で最大流をみつけるコツはありますか？ ---あります．辺の数が最小の増加道を見つけるというのがよく知られている手法です．
  • 「3kmより長く歩かせない」っていう表現だと3km歩かせるのは良いと思ってしまいます． ---その通りですね．私が間違っていましたので訂正します．ありがとうございました．
  • 「今でしょ」すきですか？ ---すきでも嫌いでもないです．
  • ノイ皮女いますか？ ---御想像におまかせします．
  • 蛍光ペンにカビが生えるのはなぜだと思いますか？ ---なぜでしょう．カビは湿気の多い場所を好むようなので，湿気が溜まらないように注意しないといけないのでしょうね．
  • 電通大と中央大の生徒の特徴をそれぞれ教えて下さい ---まず，大学生は「生徒」ではなく「学生」です．これは大きな違いなので，間違いないようにして下さい．それで，特徴についてですが，顕著な違いはないと思います．
  • 連結度が実際にどのように使われているか気になりました． ---例えば，連結度を計算すると，ネットワークのどこが弱いのかということが分かるので，ネットワークを守るときにそこを重点的に守ればよいということが分かります．
  • 電気消しちゃうとかおちゃめ (・ω・)☆ ---失礼しました．
  • ひじょうにわかりやすかった ---ありがとうございます．
  • 私，英語全くできないので日本語でおねがいします！ ---ではそうします．
  • 5分ぐらいなら英語の授業聞いてみたいと思いました． ---すみませんが，日本語でやります．
  • 5〜10分のお試しで英語の授業も聞いてみたいです． ---すみませんが，日本語でやります．
  • 今日は台風の影響であいにくの天気ですが，週末は晴れるみたいですね． ---そうですね．晴れ間を大事にしましょう．
  • 先生の辺連結度はいくつですか？私は15くらいです． ---そうだとすると，たぶん私も15くらいです．
  • 腹減った． ---食べて来て下さい．
  • 今日やった2つのちがいがわかりにくい ---例えば次の図のような例では，sからtへの辺連結度は2ですが，頂点連結度は1です．
    
  • 台風だーっ！！ ---気をつけて下さい．
  • しましまかわいいです．難しいけどおもしろい！ ---ありがとうございます．
  • 英語の授業，どうなるのか気になります！最後10分とか，前半だけとかでいいので，やってみてほしいです！ ---すみませんが，日本語でやります．
  • 10分くらいなら英語で授業受けてみたいです． ---すみませんが，日本語でやります．
  • 演習をやって理解したいと思います． ---はい，是非そうしてください．
  • 授業全て英語はキツイので，5分〜10分ぐらいだと，皆やってほしいと思っているかも ---すみませんが，日本語でやります．
  • 授業につかっているスライドのグラフはどうやって描いているんですか？ ---IPEというアプリケーションを使っています．
  • マンボウおっきい． ---八景島シーパラダイスにいるみたいですね．
  • 私は金融工学やデータマイニング，ORなどたくさん知りたいことがあり絞れません．ってか絞った方が良いのでしょうか．今は，広く浅くいろんなことを学んだ方が良いのでしょうか．先生はどうやって専門を決めたのですか．おしえてください． ---絞らなくてもよいと思います．絞ることはいつでもできますが，絞ったところから広げるのはなかなか難しいものだと思います．
  • OR学会入りたいんですがいつ入ればいいんですかね． ---実を言うと，多くの学会では入会するために会員の推薦を必要とすることがあります．なので，周りの先生の誰が会員なのか調べてみて，お願いをしてみて下さい．
  • 来週のお茶の種類は？
    ---十六茶が選択肢にないことに陰謀を感じます (^-^)
• (9) 6/14 ネットワーク最適化 (3)：最大流問題
  • コメントありがとうございました．
  • ジメジメ，ムシムシして辛い ---冷房は入らないのでしょうか？入ってもいいような気がするのですが．
  • やっと梅雨らしい天候ですね．むし暑いのは苦手です． ---私も苦手です．
  • むしむしする ---日本の夏なので仕方ないです．
  • つらい ---耐えて下さい．
  • めんどい ---耐えて下さい．
  • 補助ネットワークをいちいち書くのは嫌だなと思いました． ---面倒くさがらずに書いて下さい．
  • 増加道法が理解できなかった． ---では，次回もう一度説明します．
  • 増加道法と補助ネットワークがちょっとわかりにくいです． ---では，次回もう一度説明します．
  • 問題9.2の説明はどのように書いたらいいですか？ ---「補助ネットワークを作る」，「増加道を見つける」，「増加道に沿って流れを増やし，新しい流れを得る」というステップを順にすべて書いていって下さい．
  • カットをしてから最大流量をしぼっていくことが少し難しいと感じました ---「しぼっていく」というのは最適化において重要な考え方なので，復習して身につけて下さい．
  • テストがんばる ---はい，がんばってください．
  • 今やっている所は期末で出るのですか？小テストでは出ないのですか？ ---復習テストの範囲ではないので，期末試験の範囲になります．
  • 再来週のテストも頑張りまーす．えんしゅーできれば大丈夫です…かね． ---しっかりと演習問題に取り組んで下さい．そして，持ちこめるA4の紙をしっかりと準備してきて下さい．
  • パズル＆ドラゴンみたいで楽しかった ---道を探すところがそのように思えたかもしれないですね．
  • 頂点の数や辺の数が少ないと，最小カットから最大量を逆算できそうだと思った． ---たしかにそうだと思います．
  • 今度英語で授業してみて下さい． ---私は構いません．今度皆さんに聞いてみます．
  • 調布っていいまちですよね． ---最近，駅が新しくなったので，街の雰囲気が変わってきています．
  • あまちゃんが見たいです．じぇじぇじぇじぇじぇ！！ ---そのうちDVDが発売されるでしょう．
  • 「潮騒のメモリー」見てみたい ---たぶん，そういうスピンオフを狙った商売なのだと思います．
  • 夏を意識してますね ---意識したわけではなく，暑かったのでこうなりました．
  • アロハシャツ似合ってます． ---ありがとうございます．
  • 今日のシャツは夏らしくてステキですね． ---ありがとうございます．
  • 夏らしくてステキです． ---ありがとうございます．
  • アロハシャツ似合ってます． ---ありがとうございます．
  • そのアロハシャツどこで買いましたか？ハワイのアラモアナショッピングセンターですか？ ---その通りです．
  • 今日のシャツはどこで買ったんですか？オシャレですね (^ω^) ---ハワイです．
  • ALOHA〜 ---あろはー
  • ひじの色 ---ひじをついて本を読んだりするので，ひじが黒ずんでます．
  • ボク，ミッキーいいえケフィアです．ベリーナイースアロハ〜 ---私はミッキーでもケフィアでもありません．
  • ハローキティーの横顔です． ---私はハローキティーでもありません．
  • 友達が授業に出ません！どうすればいいですか？ ---どうもしなくていいですよ．
• (8) 6/7 ネットワーク最適化 (2)：最短路問題
  • コメントありがとうございました．
  • 髪切りましたね！ ---はい．切りました．
  • かみ切ったね ---はい．切りました．
  • 髪切ってますますさわやかになりましたね！！蛍光ペンにカビが生えました． ---切る前がさわやかだったかどうかには疑問が残ります．
  • かみの毛切りましたね．かわいい．デリシャース ---おいしくはないと思います．
  • 次のテストも前回と同様演習がんばれば良いですか？ ---はい，がんばってください．
  • ヒント下さい ---どう分からないのかということによって，ヒントの出し方は変わるので，どう分からないのか，ということまで書いて下さい．
  • スライドでやり方はわかったけれど，実際に紙で書いてやってみると混乱しそう． ---1つ1つのステップをしっかり踏んでいけば混乱することはないと思いますので，実際にやってみて下さい．
  • 演習8.3は自力で求められますか？ ---はい，できます．
  • 3限テストです．がんばります． ---がんばってください．
  • 今回はよく噛んでましたね ---すいませんでした．
  • 声裏返ってるｗ ---失礼しました．
  • 今日ははじめの方すこし機嫌わるかったですよね？何かあったんですか？ ---もしそのように見えてしまっていたとしたら，申し訳ないです．何もないです．
  • おもしろそうな範囲ですね ---是非楽しんで下さい．
  • 今日もパズルみたいで楽しいです．ORでやったことがあるのですんなり理解できました． ---今後も楽しめるような内容をやる予定ですが，それは私が一方的に思ってることなので，皆さんにもそう思ってもらえるようにしていきます．
  • 丁寧過ぎじゃないですか？ ---そう思ってもらえているなら，たぶん深く理解してもらえているということですので，問題ないと思います．
  • 今日の内容はややむずかしいように思えた． ---しっかりと復習をして下さい．
  • 切符を分割すると安くなるのを知らなかったので知ることができて良かったです． ---はい，活用して下さい．
  • (^^)v ---ありがとうございます．
  • 選び抜かれた乳酸菌から生まれた「○○」 ---カルピス！
  • 分かりやすかった． ---ありがとうございます．
  • 様々なパーカーをお持ちですね ---いえいえ．
  • 天気がびみょうで気分もびみょうです．雨も好きなので降るなら降ってほしい ---確かに天気ははっきりした方がいいですね．
  • 今日は雨の予定でしたけど降りませんでしたね． ---結局降らなかったですね．
  • Twitterが英語なのはどうしてですか？ ---英語の方が書きやすいからです．
  • 手順わかればいけそうです．なんで准教授という職を選んだのですか？ ---准教授というのは職業ではなく職階です．職業は大学教員です．大学教員は教育職でもあり研究職でもあるのですが，教育職でもあり研究職でもあるという職業は他にほとんどありません．私にとってそれが大学教員という職の魅力であり，選んだということになるのか分かりませんが，それを理由として大学教員をしています．それを続けていくということはとても大変なことなのですが，その幸せを日々かみしめているわけです．
  • 出身はどこの国ですか？ ---残念ながら日本です．
  • 京葉線の舞浜という場所はアメリカの「マイアミ・ビーチ」が名前の由来となっているそうです． ---地名の由来にまつわるおもしろい話はいろいろありますね．
  • Ahhhhh ---Ahhhhh
  • 先生お団子似合いますけどどの味のお団子が好きですか？みたらし？あんこ？ ---先日出張で仙台にいったとき，ずんだの団子を食べましたが，それはおいしかったです．
  • 資料アップが早くて助かります！！ ---最近は偶然早いのですが，保証できるのは20時ですので，その点はお願いします．
  • コールオプションとは？ ---勉強して下さい．
  • 電通大学的付近有设有便利佶吗 ---わかりません．
  • あいうえお ---五十音図では，横に並んでいる方を段と呼び，縦に並んでいる方を行と呼びます．一方，行列では，横に並んでいる方を行と呼び，縦に並んでいる方を列と呼びます．呼び方が違うので注意して下さい．
• (7) 5/31 ネットワーク最適化 (1)：ネットワークの導入，ネットワークによるモデリング
  • コメントありがとうございました．
  • 始めなので簡単 ---次回から途端に難しくなるかもしれないので注意して下さい．
  • 今日の内容はパズルみたいで楽しいです．7.3と7.4ができないってのは，なんかひっかけっぽいです． ---ひっかけっぽいかもしれませんが，よく考えると分かるので，考えてみて下さい．
  • 脳が活性化されました！問7.3，7.4のような問題はテストに出ますか？ ---問7.3や7.4のような問題はテストに出ないと思ってもらっていいです．
  • クイズみたいでおもしろかったです． ---楽しんでもらえたようでうれしいです．
  • おもしろかった ---楽しんでもらえたようでうれしいです．
  • 今日はとてもよく理解できました！ ---いままでのところの理解もよろしくお願いします．
  • テスト何が出ますか？前回のやつの成績を知りたいです． ---前回のテストの得点は私に直接尋ねてもらえればお伝えします．学生証を携えて私のところまで来て下さい．
  • 楽しかった． ---どうもありがとうございます．
  • 問題7.2の答えを探すのが難しかったです． ---たしかに難しいですね．それだからこそ，計算機の威力が分かるというものです．
  • 7.2はできた．人生の答えも見つけたい ---私の分も見つけて下さい．
  • 源流に行けば可能 ---情に棹差せば流されますので，注意して下さい．
  • 長さ0でも道なのか．グラフをキレイに図示するテクニックのようなものはあるか． ---長さ0でも道なのかどうか，というのは，実は微妙な問題なのですけども，この講義では長さ0の道もあるということにしました．これをないとする立場もあります．グラフをキレイに図示するテクニックはグラフ描画 (graph drawing)という分野で研究されていて，様々な手法が開発されています．例えば，今回のスライドの25ページの右側にある図の描き方は2010年に発見された手法に基づいていて，日本の中でこれをちゃんと知っているのはたぶん私だけです．グラフ描画については，時間があれば7月にちょっと取り扱う予定です．
  • 迷路みたいでした． ---迷子にならないでください．
  • 考えるのが大変だったができた ---よかったです．
  • 答えが見つけられてうれしかったです． ---できるかできないか，という，ギリギリのラインを狙っていたので，できなかった人には申し訳ないです．
  • 道の問題楽しかったです！合間に休憩があると少しだけ寝れてリフレッシュできます！ ---はい，リフレッシュして下さい．
  • 次のテスト不安です． ---分からないところはどしどし質問して下さい．
  • 今日いつもより声が高かった．十六茶にもどってた… ---別に，アサヒ飲料のまわしものではないのですが，お茶ぐらいは自由に選ばせて下さい．
  • おもしろかったです．赤好きなんですか？ ---今日は偶然こういう服になりました．
  • 原色が輝いていた． ---冬場もだいたいUNIQLOのフリースかパーカーなのですが，原色がおおいです．
  • 今日の洋服オシャレですね．ビタミンカラーですネ．くらやみでもみえますネ．先生は英語はなせるんですか？ ---「英語を話せる」というのはどの辺りからそう言えるのかよく分かりませんが，私自身は英語を勉強する前に日本語を勉強する必要があると思っていて，特に，日本語を話せると思ってる人々が本当に日本語で意思疎通を行えているのかどうかということについて，しっかりと反省するべきだと思うのです．ぼんやりと日本語を使うのではなくて，意識的に論理を気にしながら日本語を使うという訓練が重要だと思っています．そういう意味で，私は日本語を話せるとは思ってないですし，ましてや，英語を話せるとも思ってないです．ただ単に，日本語っぽい音が口から出てるだけだと思ってます．日本語っぽい音を口から出すことができるという意味では，日本語を話せますし，その意味では，英語も話せます．
  • 大学の教授って大変ですか？ ---私は教授ではなく准教授なのですが，それはおいておくとして，おそらく大変ではない仕事は存在しないです．
  • いつもお鼻が赤い．花粉症ですか？ ---鼻の頭を触るのが癖なのです．
  • 今日も笑顔かわいいです． ---ありがとうございます．
  • みそかつ，手羽先，エビフライ．この3つのうちどれが一番好きですか？ ---みそかつです．
  • 好きな食べ物は何ですか？ ---みそかつです．
  • わー ---おー
  • 今日は快晴でよかったです！梅雨は湿気高くて嫌いなので ---そうですね．毎週金曜日は晴れていて欲しいです．
  • 研究している内容はなんですか？オレンジ似合ってます ---離散最適化とか離散アルゴリズムとか離散数学を研究しています．あんまり詳しくないかもしれないですけど， ここら辺とか ここら辺にもう少し詳しい説明があります．
• (6) 5/24 整数計画法 (5) ：切除平面法
  • コメントありがとうございました．だんだん暑くなってきましたね．
  • スーパー灘高生のtehu君に似てますネ ---誰だか知らなかったので調べました．私は裸眼なので，違いますね．
  • 瑞季 (赤) 推しですか？奇遇ですね．ぼくもですよ ---誰だか知らなかったので調べました．すいませんが，あまり興味ないです．
  • 5月病なんですがどうすれば治りますか？ ---睡眠を十分とってますか？余り夜更かしせずに早く寝てみましょう．
  • ピンクのボーダーがとってもかわいいです ---ありがとうございます．
  • パーカー似合ってた．何か分かりそう． ---ありがとうございます．
  • ピンクのボーダーがまぶしい． ---失礼しました．
  • 今日，ちょっとオシャレ ---UNIQLOです．
  • 最近暑いですね ---暑いですね．
  • 贅沢冷茶飲んでくれたんですね！それを見てから授業が楽しくてしかたがなかった(笑) ---おそらく，次回から十六茶に戻ります．
  • おもしろい ---すみませんが，尻尾は生えていません．
  • 実におもしろい ---現象には必ず理由がありますから．
  • 分かりやすかったです． ---ありがとうございます．
  • 分かりやすかった ---ありがとうございます．
  • スライド見やすくて，わかりやすいです．全て手作りですか？ ---はい，全て手作りです．
  • 資料をもっと早くUPしてください．夜だと講義に間に合いません． ---すみませんが，今より早くは私が無理です．
  • ヒントプリーズ ---もう少し具体的にどの部分についてなのか書いてもらえますか？
  • hungry ---朝食をとってきて下さい．
  • 難しかったです ---演習問題を解いて復習をしてください．
  • ちょっと難しかった ---演習問題を解いて復習をしてください．
  • だんだん計算めんどうになってきたー ---演習問題に出した問題は，これでも計算が楽な方なのです．がんばってください．
  • スラックス変数が出ると難い度が上がる ---正しくはスラック変数ですね．難しいかもしれませんが，原理は単純ですので，しっかりと理解して下さい．
  • 演習をやって理解したいと思います． ---はい，是非そうして下さい．
  • 図でかいて考えられたら楽なのに．計算は少し手間ですね…． ---図を描けるのは変数の数が2か3ぐらいまでですが，実際に解きたい問題では変数の数が膨大になるので，図で描けないですね．その場合でも，手計算は大変なので，実際は計算機を使って解くことになりますね．
  • 他の解き方と比べると今回の解き方は少し手順が多くて大変だと思いました ---それだからこそ，計算機の威力が活きてくるのですね．
  • 次回からは今までやってなかったことだと思うので楽しみ ---はい，楽しみにしていてください．今までのことも忘れずにいてください．
  • 今日の内容はそこまで難しくなかったと思いました．講義：演習＝8：2くらいがいいですね． ---ちょっと今日は演習の時間が長くなりすぎたかもしれないです．
  • Twitterフォローしました．これで先生とイチャつけます ---Twitterは連絡用なので，残念ながらイチャつけません．
  • ラストの字を読んでくれてありがとうございます． ---「ラスト」なのか「テスト」なのか，手書き文字が判別できなかったのですが，いずれにせよ，ちょっと心当たるものがないので，なんともいえません．すみません．
  • 早く終わるとゴハンがゆっくり食べれて幸せです． ---今日はもう少しゆっくりと説明してもよかったのかもしれません．
  • 今日の教室は涼しくて授業が受けやすかったです． ---冷房が入ってましたね．
  • TOEICは何点ですか？ ---受けたことがないです．
  • 他のカットの方法はどんなのですか． ---一般的な整数計画問題に使えるカットと，特殊な整数計画問題に使えるカットがあります．一般的に使えるものとしては，例えば離接カットやlift-and-projectカットといったもの，特殊な問題に使えるものは問題によって異なるのですが，例えば，ナップサック問題のような問題に対する被覆不等式，巡回セールスマン問題に対する部分巡回路除去不等式といったものがあります．
  • 線形緩和で最適解が複数出たときはどうしますか？ ---多面体 (多角形) の端点となる最適解が計算によって求まるものだとして下さい．端点最適解が複数ある場合は，その中のどれでもよいので，任意に選んで下さい．
  • 適当な数字をかけたりするより，方程式・不等式を解いたり，辞書つくってやった方が効率的でないですか？ ---はい，そのとおりだと思います．授業では，その説明をすると単体法の説明になってしまうので，それは避けました．実際に実装するときなどは，単体法の知識も合わせて使います．
• (5) 5/17 整数計画法 (4) ：分枝限定法
  • コメントありがとうございました．だんだんコメント提出数が減ってますが，これが私の生きがいですので，どしどしお寄せ下さい．
  • 線形計画緩和の最適解で0, 1以外の値が割り当てられた変数をナップサック問題では分割に使うと良い理由は何ですか？ ---講義の中で出てきた例を使って説明します．はじめにP(x₁, x₂, x₃, x₄)の線形計画緩和を解いて，その最適解が(x₁, x₂, x₃, x₄)=(1,2/3,0,0)と計算されます．いま，x₁を分割に使うことにして，P(1, x₂, x₃, x₄)とP(0, x₂, x₃, x₄)という問題を作ります．では，P(1, x₂, x₃, x₄)を解くことを考えて，その線形計画問題を解きます．しかし，その最適解は(x₁, x₂, x₃, x₄)=(1,2/3,0,0)であり，はじめに解いたP(x₁, x₂, x₃, x₄)の線形計画緩和の最適解と同じになります．これはよく考えると当然のことで，P(1, x₂, x₃, x₄)の線形計画緩和はP(x₁, x₂, x₃, x₄)の線形計画緩和にx₁=1と代入してできた問題であり，P(x₁, x₂, x₃, x₄)の線形計画緩和の最適解であった(x₁, x₂, x₃, x₄)=(1,2/3,0,0)はP(1, x₂, x₃, x₄)の線形計画緩和の許容解なので，2つの線形計画緩和の最適解は変化しないのです．こうなると，折角新しい問題を解こうと思って線形計画緩和を解いたのに，何も新しい情報が得られない，という困ったことが起きるわけです．しかし，このような困ったことは，分割に使う変数として，線形計画緩和の最適解において割り当てられる値が0でも1でもないものを選べば，起こりえません．これが理由です．
  • もっと簡単に最適値と最適解を求める良い方法はありませんか？ ---人によって何を簡単だと思うのか，という基準が異なるので，答え方が難しいですが，限定操作を行わない分枝限定法は，(それを分枝限定法と呼んでよいのかどうかという疑問を横においておけば) 理解しやすい手法です．しかし，効率がよくないという難点があるので，限定操作について講義では紹介しました．効率がよく，なおかつ，理解しやすい手法，というのは今のところなく，そういう手法を開発することは整数計画法という分野のみならず，アルゴリズム設計における大きな未解決問題であり，そういう手法は存在しないのではないかと考える研究者が多くいます (むしろ，そういう手法が存在しないと考える研究者の方が大多数です)．これは計算複雑性とか計算量理論というものと関係しているのですが，それはこの講義の範囲を超えますので，興味があったら，そのようなキーワードでいろいろと調べてみて下さい．
  • 分枝をどこで停止するのかの判断はむずかしいと思いました． それから，どこまで省略して解答すればいいのか分かんないです！ ---判断は難しいですが，覚える必要はないので，例を通して理解して下さい．解答についてですが，それは読み手が読んで理解できると思える範囲での省略はよいですが，そうでない省略は止して下さい．現在，復習テストの採点をしていますが，他人が読むことを全く考えていないような書き方をしている答案が見受けられます．テストの答案やレポートもそうなのですが，一般に，文章というのは想定する読者がいるわけですから，その人が読んで理解できるように，そして，読みやすいように書くのが当然のことです．これは大学生が身につけるべき技術ですので，心がけて下さい．
  • 分かりやすかったです． ---ありがとうございます．
  • わかりやすかったです． ---ありがとうございます．
  • わかりやすかった． ---ありがとうございます．
  • わかりやすかった ---ありがとうございます．
  • ちゃんと聞いてました ---ありがとうございます．
  • 大丈夫 ---ありがとうございます．
  • 新しい解き方を毎回学べて楽しいと感じます． ---次回も新しい解き方がでてきますので，御期待下さい．
  • なんとなく分かった ---「なんとなく」が「本当に」になるように，よく復習して下さい．
  • 分枝限定法すごい大変！電卓が使えないとキツイかも です… ---電卓ないとキツイかもしれませんが，一旦，効率を計算して大きい順に並べれば，線形計画緩和の最適解を計算するのはそれほどつらくないと思います．頑張って下さい．
  • 大変だぁ〜〜 ---頑張って下さい．
  • やる作業が多くて大変だったが理解できた． ---作業量は多いですが，一度はやってもらいたい内容なのでやってもらいました．
  • 疲れたけど，何とか分かったような気がする． ---世間では「20代は疲れをしらない」といわれてるようなので，(20代，またはそれ以下ならば) 頑張って下さい．30代以上であっても，頑張って下さい．
  • 今回の課題みたいに，解説はのせなくても，答えが何であるのか，ぐらいの情報はほしいです．勉強しようと思ってもできてるのかわからず，はかどりません． ---では，講義の中でそれぐらいの情報は口頭でお伝えします．演習問題の紙にはじめから書いておくようなことはしないことにします．
  • 演習のヒント下さい． ---今回については，講義でやった通りに分枝限定法を実行して下さい，としかいいようがないですね．すいません．まず，線形計画緩和の最適解を計算して下さい．
  • もう少しはやく資料のアップをお願いします！その日の一限も講義があって印刷する時間がないです． ---「もう少しはやく」を今のところ私は行っているつもりで，昨日は19時前に掲載しました．あと1時間見直しができれば，もっと誤植を減らすことができたかもしれないのが心残りですが．とりあえず，私としては現在できる限り早い段階で掲載をしているので，前日帰る前にとりあえず掲載されてるかどうか確認してみて下さい．
  • バイトいってきます． ---いってらっしゃいませ．
  • タイプの顔です♡ ---ありがとうございます．
  • たのしかった！先生かわいい． ---ありがとうございます．
  • 今日は若干早口な感じがしました．休憩は良かったです！ ---早口な感じは私自身もそう思っていたのに，途中で直せなかったのはよくなかったです．反省します．
  • 休憩で一気に目が覚めた☺！！ ---休憩した甲斐がありました．
  • 5分キュウケイより10分の方がいい ---10分だと長すぎてだれてしまうので，純粋な休憩の場合は最長5分にします．途中に演習を入れる場合にはそれを10分にするかもしれません．
  • 途中休憩よかったです． ---休憩は好評なので，続けていく可能性が高いです．
  • 途中の休憩時間が良いリフレッシュとなったので良かったです． ---教卓から見ていると，休憩になって眠りから覚めた人，休憩になって眠りについた人，が半々ぐらいで，リフレッシュの方法も様々なのだな，と思いました．
  • 休憩あったの良かったです． ---ありがとうございます．
  • 真実はいつも１つ！！ ---休憩になった瞬間，多くの人が眠りについたのはあなたのせいでしょうか？
  • ちょっとやせました？ ---たぶんそんなことはないので，おそらく，いままで着太りしていたのでしょう．
  • フリースじゃなくなっていて涼しげ！！はやく半袖がみたいです．いつも十六茶ですね．贅沢冷茶オススメですよ． ---では (忘れていなければ) 今度は贅沢冷茶を飲んでみます．
  • 十六茶 ---十六茶を愛飲している理由は，量が多くてお得な気分になるからです．
  • テストの結果が悪そうなので，次の中間は頑張ります！ ---実際によいか悪いかはわかりませんが，いずれにせよ，頑張って下さい．
  • おすすめのアニメを教えて下さい！ ---アニメを見ないのでわかりません，とかいうと，あんまりなのですが，サマーウォーズはよい作品だと思いました．
  • よかった． ---ありがとうございます．
  • わふー ---今日は中華料理を昼に食べました．
  • マイクがなくても声届いてますよー ---ありがとうございます．でもマイクは使おうと思います．
  • 他にイラスト2件 ---ありがとうございました．
• (4) 5/10 復習テストと解説
  • 採点が終わりました．(5/19)
  • 自分の得点を知りたい人は，私に直接聞いて下さい．(個人情報なので，メールでの連絡には応じられません．) その際に，本人確認のため，学生証を提示して下さい．
  • テストを受けた人数は78で，得点分布は以下の通り．
    
  • 都合上，採点は0.5点刻みで行っています．
  • 受験者全体に対して，20点以上は45%程度，15点以上は74%程度，10点以上は92%程度．
  • 得点が10点以上であまり点数が伸びていない人は，些細な計算ミスが多く見られました．時間は十分あったと思うので，計算は注意深く行って下さい．そうすれば，期末試験まで受けて，最終的にちゃんと合格できると思います．
  • 得点が10点に到達していない人は，基本的な理解が欠けているように思います．試験に対してしっかりと準備をするようにして下さい．
  • 以下，問題ごとの講評です．
    • 問1．図を描くことによって整数計画問題と混合整数計画問題を解く問題．案外と，計算間違いなどによって，正しく図を描けていない人が多かったです．x₁軸やx₂軸にも許容領域に含まれる点があるので，そこも描く必要があります．
    • 問2．ナップサック問題に対する基礎的な問題．問2.1は効率を計算して，貪欲法を適用する問題．貪欲法では，詰めない商品が一旦見つかっても，そこでアルゴリズムは停止せず，その後に控える商品も詰めるかどうか判定しますので，そこには注意して下さい．貪欲法で見つかった解は最適解であるとは限らないので，それにも注意して下さい．問2.2は線形計画緩和を書き下す問題．よくできていました．問2.3は線形計画緩和を解く問題．些細な計算間違いを少なからず見ましたが，総じてよくできていました．(問2.1が間違っていても，問2.3が合っている，という解答も割とありました．)
    • 問3．整数計画モデルを作成する問題．遭難者の動く距離が間違っている解答は (それが整数計画モデルを作成するという意味においてそれほど本質的ではないため) 1点減点に留めました．遭難者の動く距離自体を変数としている解答がいくつかありましたが，どのオアシスに行くのか決めれば動く距離は自動的に決まるので，重要なのは動く距離を決定することではなく，どのオアシスに行くのか，ということであることを見抜くことが重要です．これは講義でやったタクシーの配車問題に似ているのですが，講義では，1つの要請に1つのタクシーしか応じられないので，「○○≦1」という制約を設けたのですが，この問題では，どの遭難者もどちらかのオアシスに行かなくてはならないので「○○＝1」という制約でなくてはなりません．各オアシスで2人までしか救護できない，という制約は「2人まで」なので「○○≦2」とするのが自然なのですが，この問題においてはオアシスが2つ，遭難者が4人なので「○○＝2」とした解答も正解にしました．私の解答例とは全く違う方法で，6通りの割り当て方それぞれを1つの変数で表し，その中のちょうど1つが選ばれるとしたモデルも正解としました．整数計画モデルを作成せず，ただ解いているだけの解答にも少し点を与えました．
• (3) 4/26 整数計画法 (3) ：緩和問題とその威力
  • コメントありがとうございました．
  • コメントの前に，今回の演習問題について多かった質問を．
  • 演習問題3.1の3番「上問の線形計画緩和に対する最適解を1つ発見せよ．この線形計画問題の最適値は何か？」において，「上問の線形計画緩和」と上問の線形計画緩和」は同じもので，それは2番で何かと問われた線形計画緩和のことです．線形計画緩和は線形計画問題なのでそのような書き方をしましたが，紛らわしかったようです．誤解のないようにお願いします．
  • 間に演習がある方が，眠くなってしまっても一度目が覚ませるのでいいです． ---なるほど，そういう効果があるのですね．
  • 途中に演習があると目が覚めて良かったです． ---上の人と同じ意見ですね．
  • 合間に演習があるほうがやりやすかったです ---理由は不明ですが，同じ意見ですね．
  • 最後に演習をやるよりも今日みたいに途中一回と最後の方がいいと感じました． ---他の人の意見も下に続きます．
  • 演習は最後にまとめてやる方が良い． ---今までのやり方がよいという意見ですね．
  • 演習は最後にまとめた方が良い ---同じですね．
  • 演習でつまっていたのが，未説明部分だったので，やっぱり最後に演習の方が効率が良い． ---途中の演習時間で取り組んで欲しい問題を言っていたのですけど，時間が余ったときに，その後の問題に取り組もうと思うと，それは難しくなりますね．
  • 相談で会話してからの授業集中は時間がかかるので，間にいれるのは良くないと思うが，逆に息抜きにもなるので，どちらがいいとは言えない ---よいという意見とよくないという意見が混在するので，いろいろと入れ替えて，ときには途中で演習を入れる，ときには最後にまとめて演習の時間をとる，という方法にしたいと思います．
  • もっと演習の時間をとって欲しい ---演習の時間は20分としているのですが，それより増やすと講義の時間が減ってしまうので，すみませんが演習の時間を増やすのは難しいです．自習の時間をしっかりとって下さい．
  • 演習をはさむのはいいが，解答がほしい． ---模範解答はありません．
  • テスト前だけでも演習の答えを出してほしいです ---模範解答はありません．
  • 問題の答えがほしい (切望！) ---模範解答はありません．
  • 演習の解答はやっぱり必要です．それか，せめてWebにアップして下さい． ---模範解答はありません．
  • 解答がないのに単位はとれますか？ ---「解答がないのに単位がとれる」でなければ意味がないので，そのつもりで勉強をして下さい．
  • 単位は何をしていけばとれますか？ ---演習問題のような問題がテストでは出題される，と思って下さい．基本的な事項が理解できているか確認する問題を出題します．
  • テストが不安です． ---しっかりと準備してきて下さい．
  • 単位とれますか．いつとればいいんですか ---いまとってください．
  • 演習の答えはなくてもいいので，答案の考え方などを次回授業の始めに軽く教えてほしい．また確認したい． ---直接聞いて下さい．多く質問を受けたことについては，このページで広報します．
  • 4/19の2-3がうまくできません． ---前回に書いたヒントは参考になりましたか？とりあえずそれを見て考えてみて下さい．
  • 問題2.3がわからないです； ---上の質問と同じです．
  • 資料をもっと早くアップしてもらえると助かります． ---たぶん今回は17時ぐらいに掲載してたと思います．20時前には掲載しますが，その前に掲載できていることもありますので確認して下さい．
  • 授業の資料がもう少し早く出してもらえたら嬉しいです． ---できる限り頑張ります．
  • スライドもう少し早くUPしてください．演習の考え方とかヒントとかものせてください． ---演習のヒントなどは，具体的に質問があった場合にのみこちらに書きます．
  • 資料をもっと早くアップして下さい．(家に印刷機ないんで学校でコピーしたいです．) ---大学で印刷できる時間帯を私は把握していないのですが，早く来て印刷してもらえるとありがたいです．また，最近はメモリスティックやメモリカードをもっていくとコンビニで印刷もできるので，そういうのも活用してみて下さい．
  • 今回のいいと思います．ただ，スライドはもう少し早めにほしいです．あと解答ほしいです． ---ここまでのコメントと回答と同じです．よろしくお願いします．
  • 今日の内容は少し分かった気がした．施設配置は難しかった． ---施設配置問題のところの説明は少し急いだと自覚しています．すみません．
  • 最後に説明した施設配置問題が若干難しかった． ---実際，最適化が使われる現場ではあれぐらいモデル化を使っています．場合によってはもっと難しいです．そういうものに慣れる第一歩だと思って，復習をして下さい．
  • 結局最適値は求められないんですか (01の) ---最適値の求め方は次回以降説明します．御期待下さい．
  • 演習のとき，もっと見回ってほしいです．遠くにいて質問できません． ---すいません．まんべんなくまわってるつもりなのですが，そういう場合もあるかもしれませんでした．授業後にもいますのでそのときにも質問して下さい．
  • 理解するのと解ける (定式化できる) のは違いますね… ---はい，そのための演習だと思ってしっかりと取り組んで下さい．
  • 演習問題の記述ミスはカンベンしてほしいです． ---すみません．気をつけます．
  • 新しく線形計画緩和のやり方が出てきたので，よく復習したいと思います． ---毎回新しいことがでてきますので，復習をして下さい．
  • 今日の内容は難しかったけど，なんとなくわかった．2週間しっかり復習する． ---はい，しっかり復習して下さい．
  • テストがんばります！！ ---はい，頑張って下さい．
  • 非常にわかりやすかったです．青色が似合ってました． ---ありがとうございます．
  • 分かりやすい．2度いってくれるのがすごくよい． ---大事なことは繰り返します．
  • マイクを使わなくていい気がします． ---使わないとおそらく喉が大変なことになるので，使わせて下さい．
  • 分かりやすかったです ---ありがとうございます．
  • 他人の力を利用しよう！ ---普段勉強をするときはそうして下さい．試験においてカンニングはもちろん許されないので，注意して下さい．
  • わー ---おー
  • 100万47って何か意味のある数字なんですか？ ---意味はないです．
  • おもしろかった ---すみませんが，尻尾は生えていません．
  • いつまでフリースきているのですか？あつくないですか？ ---暑かったです．
  • 自己紹介みました！すごいですね！ ---すごいですか．ありがとうございます．
  • ユニクロですか？ ---ユニクロときどきg.u.です．
  • 岡本♡ ---こちらこそ．
  • 今日，夢にでてきました！ ---悪夢でなかったことをお祈りしています．
  • テストがんばります．スイスでの話をして下さい． ---時間があったらします．
  • 今日はいけた ---それはよかったです．その調子で気を抜かずにいきましょう．
• (2) 4/19 整数計画法 (2) ：整数計画法によるモデリング
  • コメントありがとうございました．
  • ナップサック問題の3つのモデル化の話で1つ目より2つ目と3つ目の方がよいことは何となく分かりましたが，2つ目より3つ目の方がなぜ良いのかが分からなかったです． ---これは実際に実験などをしたわけではないので経験からの類推ですが，2つ目のモデル化は対称性が高いため，(次回以降扱う) 分枝限定法が不得意とする問題になっていて，それを理由として3つ目よりも悪いと思っています．ただ，最近のソルバーの進歩によって，対称性の高い問題を効率良く解く手法も開発されてきているので，実際に実験をするとそれほど差がなかったり，場合によっては2つ目よりもはやくとけるかもしれません．
  • ナップサック問題のモデル(3)の処理が一番速いと言っていたのですが，モデル(1)，(2)より速いのはなぜですか． ---上の回答を参考にして下さい．
  • 何を変数にするか簡単に分かる方法はありますか？ ---これは難しい質問で，短く答えると「ありません」になります．何を変数にするか，ということはモデル化を行う人の経験と慣れが強く現れる部分で，そこに対して一般的な方法論を与えられていない，というのがオペレーションズ・リサーチという分野の現状だと思って下さい．研究をする人の視点に立つと，それがまだ解決されていない問題だということなので，取り組むべき研究課題の1つになりえます．
  • 問題2.3が難しかったです．頭の中である程度分かっていても，実際にモデル化することは難しいと思いました． ---そうですね．そのために，演習問題をやって，実際にモデル化するということが重要です．
  • 話は分かったが演習はできなかった．がんばる． ---演習問題の時間を授業の中でとってるのは，そういうことを想定しているからです．演習について，はじめはできなくて当然なのですが，だんだんとできるようになっていくはずです．がんばりましょう．
  • 授業内容は簡単に理解できるけど，演習を解く力はないみたいです; ---力は鍛えるものなので，鍛えていきましょう．
  • 解説はわかりやすいけど解説のときに扱う問題と演習のときの問題の差が大きい気がする．あと，おにぎりくんっぽい． ---「おにぎりくん」っていうのが何なのか分からなかったのですが，授業のあとに宮城県へ出張にいって，そこに「むすび丸」っていうのがいました．これのことでしょうか？
  • もう少し早く授業資料をwebにおいてほしい． ---これはすみません．今の時間で精いっぱいなので，早く行うことは難しいです．出来る限りがんばります．
  • もう半日ぐらい早く資料アップロードしてくれませんか ---上の回答と同様です．
  • 演習時間を小分けにしてほしいです． ---では，これを次回は試してみます．試してみて，皆さんから意見をいただくことにします．
  • モデル化っていうのは式だせばいいんですよね？ ---はい，そうだと思っていてもらってよいです．
  • 難しい ---もっと的を絞って，どの点が難しかったかというご意見をもらえると，改善の仕方を考えられるので，そのような御意見をお待ちしてます．
  • むずかしい ---上の回答と同様です．
  • 割当問題が難しい ---割当問題では，割当の選択を整数変数 (01変数) で表現しています．顧客にタクシーを割り当てるのではなくて，会社の重役に秘書を1人ずつ割り当てたり，など，比喩として割当問題が使えような場面も考えてみて下さい．後半の「ネットワーク最適化」のところでも割当問題が出てくるのでそこで再度考えて下さい．
  • 演習をもう少し簡単に．あと解説をして下さい． ---たぶん簡単にはならないです．今回だと2.1は一人でできてほしい問題，2.2は悩んだ末にできてほしい問題．2.3はできなくても悲観する必要のない問題です．
  • 演習2.2が難しいと思った ---慣れないことに慣れるのも勉強なので，慣れない間は難しいと思います．そのために勉強するわけなので，がんばりましょう．
  • 問2.2の解説，次回して下さい！ ---解説ではないですが，以下2.2のヒントです．○の場所に警官を置くかどうかという選択をそれぞれの○に対して変数を用意して表現することをまず考えてみましょう．その後で，最適化すべき目的関数を書き下して，そして，制約を書いて下さい．制約は「どの道路も監視されなくてはならない」ということなので，道路1つに対して制約が1つあると考えて下さい．それぞれの道路に対して，それが監視されなくてはならない，ということを線形不等式を使って表現して下さい．
  • 問題2.2が分かりません．もちろん2.3も． ---2.2については上のヒントを参考にして下さい．2.3は次のヒントを参考にして下さい．
  • 2.3が分かりません ---2.3のヒントです．これは「三角形を選択する」問題だと思って下さい．問題の図には6つの点があるので，その中の3つの点を使ってできる三角形の数は20個あります．その20個の三角形のそれぞれが選択されるのかされないのか，ということを01変数によって表現してみて下さい．
  • 問題2.3がわからないので，解説してください． ---ヒントは上のコメントを参考にして下さい．
  • 2番から先のヒントを下さい． ---上のコメントを参考にして下さい．
  • 問2.3のヒント下さい． ---上のコメントを参考にして下さい．
  • ヒントになるくらいの解説は欲しい． ---直接聞いて下さい．
  • 解説がほしい． ---直接聞いて下さい．
  • 演習の答え合わせをしてほしい ---答え合わせはないです．直接聞いてもらえればよいか悪いかは回答します．
  • 答えいらないのでヒントor簡単な解説がほしいです ---直接聞いて下さい．
  • 問題の解答方針が知りたい ---直接聞いて下さい．
  • 演習の解説を毎週してほしいです． ---直接聞いて下さい．
  • 答えが必要 ---模範解答はありませんので，周りの人と相談してやって下さい．
  • 周りもできてないと答えがいつまで経っても分からない ---できたところまでで，まず質問して下さい．その方針がよければ，そこからどう考えればよいか，その方針が良くない場合はどう方針をかえるとよいか，というヒントを出します．ぱっと素早くできるということはないかもしれないので，時間をかけてやって下さい．
  • わかりやすいです．演習の答え．．．泣．がんばります！ ---はい，頑張って下さい．
  • 鼻詰まってますか？私は詰まってますよ． ---はい詰まってます．応援(?)ありがとうございます．
  • 本日初めて受けましたが，分かりやすく良かったです． ---ありがとうございます．だんだん難しくなっていくと思うので，気を抜かずにお願いします．
  • コメントに丁寧に答えていて良い．上からものを言ってなくて良い． ---どうもありがとうございます．これが皆さんからもらえる大切なフィードバックなので，いろいろと活かしていきます．
  • 大変楽しいです ---授業が楽しめるという感覚がいいですね．今後も楽しんで下さい．
  • おもしろい ---すみませんが，尻尾ははえていません．
  • 来週もよろしくお願いします ---はい，よろしくお願いします．
  • 去年のORの問題でやっていたので，理解しやすかった ---今後，いままでやってきたものではない内容も出てくるので，期待して下さい．
  • 寝てしまった．．． ---他の人に迷惑かけなければ寝ててもいいです．
  • 先週よりわかりやすく感じました．だけれど，眠かったです．寝てしまいました．ごめんなさい． ---同上です．できれば，前もってしっかり寝て来てもらえるとうれしいです．
  • 先生の授業があると，朝は雨で天気も良くなかったです． ---天気ばかりは私の力で何ともできませんが，次回はよい天気だと期待しましょう．
  • 良い講義でした． ---ありがとうございます．
  • 今日の授業はとてもていねいでした． ---一応そういうつもりでやりましたので，そう思ってもらえてよかったです．
  • とても分かりやすかったです！！ ---今後も分かりやすいままできるようにしていきたいです．
  • 説明のスピードは良かったです． ---分かりました．ありがとうございます．
  • 授業の速度を上げてください！ ---うーん．ちょうどいいという意見と，遅いという意見と，難しいという意見と，混在していて，どこに合わせるのがよいのか難しいですが，これぐらいのペースよりも遅くすることはないと思います．話すスピードは変えないようにしますが，内容はだんだん難しくなっていくので，遅いと感じることはだんだんなくなっていくと思います．
  • 今日もかわいいですね．授業の速度が遅くて眠くなる． ---このペースをとりあえずはキープしていこうと思うので，十分寝てから来て下さい．
  • かわいい ---なにがかわいいのかいまだに不明ですが，とりあえずありがとうございます．
  • 楽しかった ---次回以降もよろしくお願いします．
  • OR苦手だけどガンバリマス ---はい，頑張って下さい．
  • 何歳ですか？ ---オフィシャルな情報がどこかに載ってますので，それを参考にして下さい．
  • 緑がにあいますね！ ---次回はたぶん違う色になります．
• (1) 4/12 整数計画法 (1) ：線形計画法の復習，整数計画法の導入
  • コメントありがとうございました．
  • ORを落としているので，この講義も不安がある ---講義要項にも書いてありますが，この講義はOR第1，OR第2，OR演習の単位取得と内容理解を前提としてますので，注意して下さい．
  • OR第2をやってないので，そこを詳しくやってほしい． ---講義要項にも書いてありますが，この講義はOR第1，OR第2，OR演習の単位取得と内容理解を前提としてますので，OR第2の内容をやる予定はないです．OR第2を履修して下さい．
  • 去年までの授業の復習が必要だと思った． ---講義要項にも書いてありますが，この講義はOR第1，OR第2，OR演習の単位取得と内容理解を前提としてますので，しっかり復習をお願いします．
  • 内容をだいぶ忘れてしまっていた．ちゃんと復習する． ---はい，しっかり復習をお願いします．
  • 昨年のORの線形計画法の内容を少し忘れていたので，よい復習になりました． ---はい，線形計画法は重要ですので，しっかり復習して下さい．
  • 復習できてしかももっと理解できた ---理想的ですね．
  • 双対問題があまりわかっていなかったがわかるようになってきた． ---双対性は線形計画法の中でもっとも重要な概念の一つであるにも関わらず，なかなか難しいものなので，時間をかけて理解していきましょう．
  • 主問題と双対問題の一般の対応式をのせてほしかったです． ---これは線形計画法の復習になるのですが，「一般の対応式」や「一般の場合の解法」については資料にはのせないつもりでいます．なかなかややこしいものなので．それらについては参考図書を講義要項に挙げてあるので，そちらを見て下さい．
  • 少し早口だった気がしました． 講義前日の夜20時までじゃなくてずっと資料置いておいてほしいです． ---スライドでの説明がわかりにくかったので，再度説明します． 資料はずっと置いておかれますが，各回の講義の資料が準備されるのがその前日の夜20時であるということです． よろしくお願いします． 早口だということについては他の方も指摘してるので気をつけます．
  • おちついて！ ---早口なようなので落ち着いてしゃべるように努力します．
  • しゃべるのが速くて理解できない ---そのようなので落ち着いてしゃべるように努力します．
  • 少し授業がはやかった． ---そのようなのですが，今回の分量は多かった気もしますので，分量を調整します．
  • 説明をもう少しかみくだいてくれるとうれしいです．あとゆっくり話して下さい． ---わからなかった部分については質問してもらえるとうれしいです．
  • ちょっと細かくて全体像が見えづらかった ---今回の前半は復習のつもりだったので，あまり全体像を気にしていませんでした．すいません．
  • 分かりやすかったです．説明はもう少し遅くお願いします． ---落ち着いてしゃべるように努力します．
  • 久しぶりでけっこうしんどかったです．最初のうちは少しゆっくりおねがいします． ---最初のうちとは限りませんが，落ち着いてやるように努力します．
  • 証明とか定義をとばしてくれるのはありがたい． ---本当はとばしてはいけないのですけど，この講義ではとばしていくことにします．ちゃんとした証明や定義については講義要項に挙げた参考文献を見て下さい．
  • 答えがほしいです． ---模範解答はありません．
  • 答え！ ---模範解答はありません．
  • 演習問題の解答が欲しいと思いました．解説も少しでもあればうれしいです． ---模範解答はありません．自分で解いてみてよく分からないときは質問を下さい．
  • 答え下さい（ヒントだけでも） ---模範解答はありません．ヒントはどしどし出しますので，分からないところを質問して下さい．
  • 解法がわからなかった ---「わからない」というときは質問して下さい．わからないときに質問する相手がいる，というのが大学のよいところなので．
  • 難しい問題はヒントがあるといいです． ---はい，ヒントが必要なときは尋ねて下さい．
  • 最後にまとめて演習より，説明して，演習するように，小まめに演習したい． ---これは一理ありますが悩みますね．一旦演習のモードになってしまうと，再び講義のスタイルに戻るのが難しくなると思っています．とりあえずは今回のスタイルを保持しようと思います．
  • ORが苦手な人はこの授業に来ていないと思うので，基礎の復習はもっとさらっとやっていいのではないかと思います．もう少し楽しく感じられる授業だとうれしいです．あと，演習の解説はなくても，解答はありますよね？ ---頂いたコメントによるとORが苦手な人が来ていない，ということもないようです．復習は今回だけなので，次回からは違う感じになります．演習の模範解答はありません．
  • 問1.1は円ですか？ ---円は線形の不等式で表せないので，ダメですね．
  • 問題1.1は円ですか？ ---同上．
  • 問1.1の解説をしてほしいです． ---授業中にも出したヒントを繰り返しますが，「重要な性質2」(スライド21ページ) から，許容領域が端点を持ってしまうと，自動的に問1.1の答えになりえないことがわかります．なので，許容領域が端点を持たないようにしなくてはなりません．2次元なので，2つ以上の不等式があると許容領域に (特別な場合を除いて必ず) 端点ができます．別の言い方をすると，許容領域が端点を持たないようにするためには，不等式の数が極端に少ない方がよさそうです．以上がヒントです．
  • 眠かった ---ちょっと部屋が暑かったかもしれないので，窓を開けたりとか，適当な室温管理が必要そうですね．
  • お腹すきました ---朝食をとってきて下さい．
  • 春休みボケが激しかったです． ---春休みボケは4月までしか許されないのですが，5月に「ゴールデンウィークボケ」とかいうのは止めて下さいね ;-)
  • テンポよい授業でよいと感じました． ---話し方がおちついてないという意見もありますので，おちついて話しながらテンポを維持するということは，なんか無理そうですけど，努力します．
  • ORは得意ではないので難しそうだなと思いました． ---がんばりましょう．楽な科目ではないと思いますが，得られるものは大きいと私は確信してます．
  • 久しぶりに最適化手法をやったので難しかった ---ある程度難しいことをやらないと大学ではないと思うので，そういうものだと思って下さい．「慣れ」も重要なので，復習をしてしっかり慣れて下さい．
  • 難しい ---同上．
  • 難しいです．今日は晴れですね！ ---晴れましたね．次回も晴れますように．
  • 今日ははれです． ---はれですね．雨はいやです．
  • かわいい． ---何がですか？ ;-)
  • 例題をとり入れて授業するとわかりやすくていい！ ---今後も例を重視していきます．
  • わかりやすくて良かったです． ---ありがとうございます．
  • よかったです． ---ありがとうございます．
  • 非常にわかりやすい講義でした． ---ありがとうございます．
  • わかりやすかったです． ---ありがとうございます．
  • わかりやすかった． ---ありがとうございます．
  • わかりやすくてよかったです ---ありがとうございます．
  • 次回の講義も楽しみにしています． ---ありがとうございます．こういうコメントを書いてる方々は講義のレベルがあってるのだと思うことにします．
  • どのような分野でORなどが利用されているのかを交えて話をしてほしい． ---これは1年の『OR第1』で紹介されていると思いますが，私の視点からいいますと，利用されていない分野はないといっていいです．最適化というのは考え方です．世の中にはいろいろな現象や構築物があるのですが，それらをどのような視点から見るのかによって，違った見え方をもたらします．最適化という視点で現象を見ると，世の中にあるすべてのものが最適化をするという原理に基づいて動いているように見えてきます．ものを作るという観点からも同様です．この講義でも「視点」としての最適化に注意していくことにします．

スケジュール

• (1) 4/12 整数計画法 (1) ：線形計画法の復習，整数計画法の導入
• (2) 4/19 整数計画法 (2) ：整数計画法によるモデリング
• (3) 4/26 整数計画法 (3) ：緩和問題とその威力
• (4) 5/10 復習テスト１と解説
• (5) 5/17 整数計画法 (4) ：分枝限定法
• (6) 5/24 整数計画法 (5) ：切除平面法
• (7) 5/31 ネットワーク最適化（1）： ネットワークの導入，ネットワークによるモデリング
• (8) 6/7 ネットワーク最適化（2）： 最短路問題 (幅優先探索，ダイクストラ法)
• (9) 6/14 ネットワーク最適化（3）： 最大流問題 (線形計画法，補助ネットワーク，増加道法，最大流最小カット定理，整数流定理)
• (10) 6/21 ネットワーク最適化 (4) ： 最大流問題の応用 (割当問題，連結性)
• (11) 6/28 復習テスト２と解説
• (12) 7/5 ネットワーク最適化 (5) ： 最大流問題の応用 (優勝可能性判定，露天掘り問題，最密部分グラフ問題)
• (13) 7/12 ネットワーク最適化 (6) ： 最小費用流問題（線形計画法，補助ネットワーク，逐次最短路法，修正補助ネットワーク，整数流定理)
• (14) 7/19 ネットワーク最適化 (7) ： 最小費用流問題の応用 (最小費用流問題の変種，輸送問題，割当問題)
• (15) 7/26 ネットワーク最適化 (8) ： 最小費用流問題の応用 (生産計画問題，連結度増大問題)
• 7/31 (6限) 期末試験

オンライン文献

• OR事典Wiki
• 整数計画法メモ (東京農工大学 宮代先生)
• Shortest Path Online (藤澤研究室)
• RIOT -- Major League Baseball Playoff Races: リーグ戦における優勝可能性判定

参考にした書籍，文献など

• 今野浩，鈴木久敏 (編)，『整数計画法と組合せ最適化』，日科技連，1982年．
• W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, "Combinatorial Optimization", John Wiley & Sons, Inc., 1998.
• 藤重悟，『グラフ・ネットワーク・組合せ論』，共立出版，2002年．
• 久保幹雄，田村明久，松井知己 (編)，『応用数理計画ハンドブック』，朝倉書店，2002年．
• 森雅夫，松井知己，『オペレーションズ・リサーチ』，朝倉書店，2004年．
• 山下信雄，福島雅夫，『数理計画法』，コロナ社，2008年．
• 加藤直樹，『数理計画法』，コロナ社，2008年．
• R. Burkard, M. Dell'Amico, S. Martello, "Assignment Problems", SIAM, 2009.
• 繁野麻衣子，『ネットワーク最適化とアルゴリズム』，朝倉書店，2010年．
• F. S. Hiller, G. J. Lieberman, "Introduction to Operations Research, Ninth Edition", McGraw-Hill, 2010.
• 福島雅夫，『新版 数理計画入門』，朝倉書店，2011年．
• 茨木俊秀，『最適化の数学』，共立出版，2011年．
• 久野誉人，繁野麻衣子，後藤順哉，『IT Text 数理最適化』，オーム社，2012年．
• B. コルテ，J. フィーゲン (著)，浅野孝夫，平田富夫，小野孝男，浅野泰仁 (訳)，『組合せ最適化 理論とアルゴリズム 第2版』，丸善出版，2012年．
• 室田一雄，塩浦昭義，『離散凸解析と最適化アルゴリズム』，朝倉書店，2013年．
• H. P. Williams, "Model Building in Mathematical Programming, Fifth Edition", John Wiley & Sons, Inc., 2013.
• David Avis先生 (京都大学) の講義資料
• 塩浦昭義先生 (東北大学) の講義資料
• 根本俊男先生 (文教大学) の講義資料
• オペレーションズ・リサーチ学会機関誌，2012年4月号，特集『はじめよう整数計画』