線形計画問題とは

最適化問題のひとつで、目的関数と制約条件がすべて線形関数で表せる問題を線形計画問題といいます。

問1　製品A,Bを生産するためには原料a,b,cが必要です。売却利益はAが3、Bが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売却利益を最大にするためにはA,Bをどのように生産すればよいでしょうか？

A B 在庫

a 3 1 10.5
b 2 2 9
c 1 2 8

解説　この問題を定式化すると、以下のようになります。Aの生産単位をx、Bの生産単位をyとします。

目的関数
z = 3x + 2y
を、制約条件
3x + y <= 10.5
2x + 2y <= 9

x + 2y <= 8

の下で最大にするx,yとそのときのzの値を求めなさい。

今回のように変数が2つだけであれば、図を描いて交点を求めれば解を得ることが出来ます。

＃図を挿入

しかし、製品の数が3つ以上になると図を描くのはほぼ不可能になります。授業ではそのような線形計画問題を解くための方法(線形計画法)を学びます。具体的なアルゴリズムは書きませんが、それを用いることで多変数の場合でも効率よく解を求めることが出来ます。

問2　製品A,B,C,Dを生産するためには原料a,b,c,d,eが必要です。売却利益はAが3、Bが2、Cが1、Dが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売却利益を最大にするためにはA,B,C,Dをどのように生産すればよいでしょうか？

A B C D 在庫

a 3 1 1 2 10.5
b 2 2 0 2 9
c 1 2 1 0 8
d 3 1 2 1 10
e 1 1 2 1 7.5

解説　これでは図を書くことが出来ませんね。どう解くのかは授業でのお楽しみに！
離散数学の学習効果

授業では、コンピュータを使って解く数学的問題とそれに対する今日までに考えられてきた解法が多数紹介され、まず離散的な問題の類型と有名な手法を学ぶことが出来ます。学んだ解法はいざ自分がアルゴリズムを設計する時に利用できることがあり、またアルゴリズムの効率を評価するための基礎知識が身につきます。
授業の進行について(今井先生の場合)

先生の説明を聞きながら板書を書き取っていく形です。先生曰く、板書はスライドよりほどよく遅いので、その場で考えて理解していくとよいとのことです。内容は今井先生が本質的なところから犀利な論理を用いて語って下さいます。受講生の自習のためとして「証明は略証明を与える。各自完成させよ。」のような指示がよく出ます。ですから少し厳しめな印象をもつこともあると思いますが、努力してついていけば必ず力はつきます。
試験について

大問４〜６題程度で大体が授業で扱う問題だと思います。後半の授業で、試験問題の出題範囲を先生が詳しく教えてくださいます。例年ほぼ試験のみで成績が決まるようです。
次のステップへ

次の学期(つまり３年冬学期)の全く同じ時間帯に今井先生による「計算量理論」の講義があります。困難さの尺度を導入することで離散数学的問題を分類し、計算の時間空間効率の解析に特化した議論をします。
注釈

1 巡回セールスマン問題(Traveling Salesman Problem, TSP)
　　本来は一度訪れた場所に二度訪問してはいけないというルールがある。