2010年度 数理計画法
期末試験は2月3日に行なわれました．
期末試験の過去問：
2009年 :
2008年 :
2007年 :
2006年 :
2004年 :
2003年 :
2002年
授業の中間と期末に行われる２回の試験の結果，および
演習レポートの提出状況により評価を行う．
出席点は一切考慮しません．
ただし，
-
線形計画に関する4回のレポートを一度も提出していない学生は，
中間試験の受験は不可
-
ネットワーク計画および非線形計画に関するレポートを一度も提出していない学生は，
期末試験の受験は不可
配点：中間試験 ５０点，期末試験５０点，レポート２０点程度．
合計１００点以上は１００点に切捨て。
合格の基準：
中間、期末試験ともに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) 簡単な問題．Ｐは定数なのに変数と勘違いしている解答が多数あり．
(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パスに沿って増加させるフローの量は，可能であれば１より多くても良い．
- 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：証明の流れ自体はＯＫだが，所々不完全な証明が多い．
論理の流れをきちんと書いて欲しい．
なお，「x' を主問題の最適解とする」のように書いてある証明があるが，
系2．2の仮定からは，最適解の存在は保証できないことに注意しよう．
-
問2：例を挙げるだけでなく，その理由も書くと良い．
-
問3： 双対問題を書き忘れている学生が多い．
- 10/14 第2回目 --- 線形計画その2
-
配布資料
- レポートに対するコメント
- 問1：非負条件を忘れている解答が多かった．
また，各変数の意味を説明すること．
- 問2：「最適解を求めよ」という問題ではきちんと最適解を書くこと．
- 問3：一般の不等式標準形のLPに対して，「双対問題の双対問題が元の問題に一致すること」
を証明すること．
手順その１：(1)まず不等式標準形の双対問題を書く．(2)得られた双対問題を不等式標準形に書き換える．(3)得られた不等式標準形に対し，双対問題を書く．(4)得られた問題を不等式標準形に書き換える＝＝＞元のLPが得られる．
手順その２：不等式標準形の双対問題に対し，最適値の上からの見積もり（上界値）を
計算する問題を作る＝＝＞元のLPが得られる．
- 10/07 第1回目 --- 数理計画問題，線形計画その1