2010年度 数理計画法
期末試験は2月3日に行なわれました.
期末試験の過去問:
2009年 :
2008年 :
2007年 :
2006年 :
2004年 :
2003年 :
2002年
授業の中間と期末に行われる2回の試験の結果,および
演習レポートの提出状況により評価を行う.
出席点は一切考慮しません.
ただし,
-
線形計画に関する4回のレポートを一度も提出していない学生は,
中間試験の受験は不可
-
ネットワーク計画および非線形計画に関するレポートを一度も提出していない学生は,
期末試験の受験は不可
配点:中間試験 50点,期末試験50点,レポート20点程度.
合計100点以上は100点に切捨て。
合格の基準:
中間、期末試験ともに25点以上で合格(24点以下は不合格).
ただし,レポートの提出状況がきわめて悪い場合には,
中間、期末試験ともに30点以上で合格(29点以下は不合格).
- 02/03 第13回目--- 期末試験
- 今年の問題 (問1(c)を修正しました)
- 受験者数 64人 合格 56人 不合格 8人
- 平均点 35.34点 (問1: 14.4/16 , 問2: 6.3/9 , 問3: 6.9/13, 問4: 7.8/12)
- コメント
- 問1:
-
(a) [3点] 簡単な問題.
-
(b) [3点] 「カットの容量」の定義を誤解している学生がいます.
1月6日の授業で説明したやり方で証明できます.
-
(c) [3点]
大変申し訳ありません.
出題者の意図した問題と異なり,解の存在しない問題となっていました.
「解なし」という答えはフェアではないので,
全員正解とします.
-
(d) [5点]
終了条件をきちんと書くこと.
一つの反復にて2つ以上のパスに沿ってフローを変化させた場合,パス増加法ではありません..
-
(e) [2点] 最終的に得られた残余ネットワークにおいて,供給点から到達可能な頂点をすべて
求めればよい.
- 問2:
-
(a) [5点] 終了条件をきちんと書くこと.
-
(b) [4点] 各枝の容量と費用,需要点と供給点の場所,および需要供給量を
どのように設定するかを説明すること.
- 問3:
-
(a) [4点] 授業で説明したとおり.簡単.
-
(b) [2点] 基本的な概念の定義を問う問題.簡単.
-
(c) [2点] 解の最適性条件に関する問題.簡単.
-
(d) [5点] (c) の条件を使って,極小解であるか否かを示すこと.
極小解である/ない理由が書かれていないと減点.
- 問4:
-
(a) [2点] 簡単な問題.
-
(b) [3点] 合計で4つくらい長短所をあげると良い.
-
(c) [4点] 直線探索を厳密に行うこと.
-
(d) [3点] ニュートン方向の定義を覚えていれば簡単.
- 01/27 第12回目--- 非線形計画その3
- 01/20 第11回目--- 非線形計画その2
- 01/13 第10回目--- 非線形計画その1
- 2011/01/06 第9回目--- ネットワーク最適化その3
- 12/16 休講
- 12/9 第8回目--- ネットワーク最適化その2
- 12/2 第7回目 --- 中間試験
- 今年の問題
- コメント
- 問1:
(a) 簡単な問題.Pは定数なのに変数と勘違いしている解答が多数あり.
(b) 授業でやったとおり.結構間違えが見受けられる.
(c) 理由がきちんと書けていない解答が多い.目的関数が無限に小さく(大きく)なるような
許容解があることを示す必要有り.
- 問2:
(a) (a-1), (a-2)ともに[P]と[D]の制約を使えば簡単に証明できる.
x_iの非負性を使っていない場合は減点.へんな間違った証明が多数有り.
(b) 実質的には第3回目のレポート問題と同じなので,レポートをきちんとやった学生は
出来ているはず.
- 問3:
(a), (b) はサービス問題.出来て当然.
(c) は第4回目のレポート問題と同じ.ウェブのコメントをきちんと見ていれば
避けられる間違いをしている学生が多数有り.
- 問4:
(a)は普通の単体法により1回の反復で解ける問題.最適解有り.
(b)も普通の単体法により1回の反復で解ける問題.非有界.
(c)は2段階単体法により3回の反復で解ける問題.許容解なし.
ちょっと計算の手間が多すぎたかと思いきや,意外と出来ている学生が多かった.
-
中間試験の過去問:
2009年:
2008年:
2007年:
2006年:
2004年:
2003年:
2002年:
- 11/25 第6回目--- ネットワーク最適化その1
-
配布資料
- レポートに対するコメント
- フロー増加法の各反復において利用するs-tパスをきちんと明記すること.
- s-tパスに沿って増加させるフローの量は,可能であれば1より多くても良い.
- 11/18 第5回目 --- 線形計画その5
-
配布資料
- レポートに対するコメント
-
問1: 最適解が存在し,最適値は -3 となる.
最小添字規則を理解していない学生が数名いた.
-
問2: 補助問題の最適値は 1/3 となる.
補助問題の最適値が正であることが何を意味しているかは,授業の資料を見て
確認して欲しい.
なお,
補助問題の最適値が正であるにも関わらず,
人工変数 x_a の入れ替えを行なっている解答が見受けられるが,これは意味がない.
-
問3:
問題は非有界であるが,そのように判断した理由をきちんと書くこと.
- 11/11 休講
- 11/04 第4回目 --- 線形計画その4
-
配布資料
- レポートに対するコメント
-
問1,問2: 得られた解が許容解であることを忘れずに確認すること.
「弱双対定理」を使って,双対定理の解を得ようとしている学生がわずかにいたが,これは
間違い.
-
問3: 最適値は -13 になる.詳細は
こちらのファイルを参照のこと.
なお,単体法の途中での計算間違いを防ぐ方法としては,
(i)各反復で得られた基底解が
本当に許容解であるかどうかをチェックする,
(ii)最終的に得られた解が最適解であることを,
相補性定理などを利用してチェックする,
というやり方があります.
- 10/28 休講
- 10/21 第3回目 --- 線形計画その3
-
配布資料
- レポートに対するコメント
-
問1:証明の流れ自体はOKだが,所々不完全な証明が多い.
論理の流れをきちんと書いて欲しい.
なお,「x' を主問題の最適解とする」のように書いてある証明があるが,
系2.2の仮定からは,最適解の存在は保証できないことに注意しよう.
-
問2:例を挙げるだけでなく,その理由も書くと良い.
-
問3: 双対問題を書き忘れている学生が多い.
- 10/14 第2回目 --- 線形計画その2
-
配布資料
- レポートに対するコメント
- 問1:非負条件を忘れている解答が多かった.
また,各変数の意味を説明すること.
- 問2:「最適解を求めよ」という問題ではきちんと最適解を書くこと.
- 問3:一般の不等式標準形のLPに対して,「双対問題の双対問題が元の問題に一致すること」
を証明すること.
手順その1:(1)まず不等式標準形の双対問題を書く.(2)得られた双対問題を不等式標準形に書き換える.(3)得られた不等式標準形に対し,双対問題を書く.(4)得られた問題を不等式標準形に書き換える==>元のLPが得られる.
手順その2:不等式標準形の双対問題に対し,最適値の上からの見積もり(上界値)を
計算する問題を作る==>元のLPが得られる.
- 10/07 第1回目 --- 数理計画問題,線形計画その1