計画数学第2レポート第2回
締め切り 1月21日(火) 15:00
提出先: uno@nii.jp


1. 次の数理計画を等価な線形計画に変形しなさい。変形できないものはそう解答しなさい。  (1問3点：3問まで)
最小化  | x1 + x2 | + | x2+ x3 | 
制約　ax ≧ b
      x ≧ 0

最小化   | x1 - x2 |
制約　| x1 + x2 | ≧ | x1 + x3 |

最小化 max { | x1 - x2 |, | x2 - x3 | }
制約　| x1 + x2 | ≧ | x1 + x3 |

最大化 max { x2 , | x2 - x3 | }
制約　x2 ≧ | x1 + x3 |

最大化 max { x2 , y }
制約　x2 ≧ y
      2x2  ≦ 3y

最大化 log x + log y
制約　x5 ≧ 1/ y3
      2x2y4  ≦ log 3 + log 5


2. 次の問題を解きなさい(1問5点：2問まで)
・　新入社員が n 人入ってきた会社があります。仕事場は k 箇所あり、社員 i が仕事場 j に行くと aij 分の働きをするとします。さて、会社の利益を最大にするような赴任先の決め方を求める問題を定式化しなさい。
・ 上記の問題設定では、「どうしても自宅から通える範囲にしなければならない」人が遠くに飛ばされる可能性があります。こういうことが起きないようにするためには、どのようなコスト付けをすればいいでしょうか
・　この会社では、方針を転換して、「だれでもそれなりに働いている」という方針で人を赴任させることにしました。さて、「最も働きが悪い人」の働きがなるべく良くなるように赴任させるためには、割り当て問題の目的関数をどのように変更すればいいでしょうか


3. n 個の数（a1,…,an）がある。これらの数のk個の組合せで、合計がちょうど b になるようなものは、いくつあるか？

と言う問題を解く動的計画法のプログラムを作りなさい。言語は問いません。
ソースと実行結果を添付すること。(15点)