2017年度 数理手法III（数理最適化）
授業はすべて終了しました．
教科書（参考書）：それぞれの本を参考にして講義を進めます
中間試験と期末試験の結果により評価を行う．
たまに出席を取るかもしれませんが，出席点は一切考慮しません．
配点：中間試験 50点，期末試験 50点
合格の基準：
中間，期末試験ともに21点以上，
かつ合計点が51点以上で合格．
東北大学で同様の授業を行っていたときの試験問題です．
参考にしてください．
以下の予定は変更される可能性があります
- 2018/01/17 第14回目 --- 期末試験
-
試験問題
- コメント
- 問1：
[1], [2]: 講義で説明したとおり．良くできている．
[3]: 残余ネットワークの作り方に基づいて説明すれば良い．
[4]: 「任意のフローの総流量≦カット(S,T)の容量C(S,T)＝フローxの総流量」を示せば良い．
[5]: 講義で注意したように，初期フローが０でない場合，および
ある反復で複数の増加路を用いている場合は間違い．
[6]: 「最小カット」と「最小カットの容量」は違うものを意味します．
- 問2：
[1]: 条件(a)を残余ネットワークの言葉で書き直すと見通しが良くなる．
[2]: 「各枝ごとにみて，フローのコストが最小になっていること」，
「c'_ij に関して最小費用であることとc_ijに関して最小費用であることが等価であること」
を示せば良い．
[3] 負閉路消去を2回で最小費用フローを求めることが可能．
ある反復で複数の負閉路を用いている場合は間違い．
[4] 残余ネットワークで最短路を計算することにより求めることが可能．
- 問3：
[1], [2]: 講義資料に書いてある定義を参照のこと．
[3]: f は微分可能とは限らないことに注意．なので，
勾配ベクトルを使った証明は間違い．
[4]: g が凸関数であること，凸関数の和が凸関数になることを示せばよい．
- 問4：
[1]: 講義で証明を省略した方の主張を証明する問題．
なので，講義で示した証明をそのまま書くと間違い．
講義で説明した証明のポイントを理解していれば容易に解ける．
なお，ノルムの記号と絶対値の記号の間違いが多い．
[4]-[7]: 定義にしたがって計算すれば良い．
- 2018/01/10 第13回目 --- 非線形計画その３
-
講義資料
-
今回は資料の内容に加え，以前省略した
「大リーグの優勝可能性の判定問題」について説明します．
- 12/20 第12回目 --- 非線形計画その２
- 12/13 --- 休講
- 12/06 第11回目 --- 非線形計画その１
- 11/29 第10回目 --- ネットワーク最適化その３
- 11/22 第9回目 --- ネットワーク最適化その２
- 11/15 第8回目 --- ネットワーク最適化その１
- 11/08 第7回目 --- 中間試験
-
試験問題
- コメント
- 問1から問4の解答は別々の用紙に書いてください
- 問1： [15点]
-
[1] 各制約，目的関数の説明が抜けていると減点．
最後に「整数」と書いてあるのに，見落としている解答が幾つかあり．
-
[2] [2-1] では緩和問題を解けと書いてあるのに，なぜか元の問題を解いている解答が幾つかあり．
- [2-2] 分枝操作，限定操作をなぜ行うのか，理由が説明できていないと減点．
- 問2： [14点] 単体法の動きの理解を確認するための問題
- [1]
単体法の途中で実行可能でない基底解がでてくる解答や，
目的関数の係数が負であるのに単体法を終了している解答がありましたが，
単体法の基本的な動きを理解していない証拠です．
最小添字規則を使っていない解答や，違う線形計画問題を解いている解答が幾つかあり．
- [2]
[1]で間違った答えを導出していても，この問題で間違いに気がつけるように用意した
親切な問題のはずが，気がついていない学生も何人かいました．
実行可能領域は凸多角形になるはずなのに，分かっていない学生数名いました．
- [3] 授業で注意したにも関わらず，
相補性条件を勘違いして覚えている学生が何人かいました．
- [4] 双対問題の最適解は無限にあります．実行可能性もチェックすること．
- 問3： [10点] 2段階単体法の1段階目の動きを理解しているか，確認するための問題
- [2] 初期辞書から許容辞書を得るためのピボット演算のやり方を間違えている
解答が多い．
- 問4： [11点]
- [1] 授業で説明したように，最適解の存在を仮定してはだめ．
主問題の解 x の最適性の証明は不要なのに，なぜか書いてある解答多数．
- [2] 「双対問題が非有界」になるには，
「主問題が実行不可能」
であることが必要条件であるが，十分条件ではない．
- [3], {4] 演習でやった問題．これは簡単だったようです．
- 11/01 第6回目 --- 組合せ最適化
- 10/25 第5回目 --- 線形計画問題その４
- 10/18 第4回目 --- 線形計画問題その３
- 10/11 第3回目 --- 線形計画問題その２
- 10/04 第2回目 --- 線形計画問題その１
- 9/27 第1回目 --- 数理最適化モデル