テレビでみるOR!

2004/04/01

東海大学理学部情報数理学科 松井泰子

私の専門は,オペレーションズ・リサーチです。略してO R( オーアール)とよばれます。
ORは,限られた資源を効率良く使うことによって無駄を無くし,必要コストを削減する, すなわち利益を最大とすることを目的に研究されている技術を指します。 テーマは,数理計画,確率・統計,待ち行列,経営分析,ゲーム理論,金融工学,都市計画等, 多岐に渡ります。

具体的には,ORを用いて,

  • パイロットの勤務スケジュール作成
  • ゴミ集配車の巡回経路決定
  • 電力の需要予測
  • 在庫管理
  • 役所の窓口の混雑解消
  • リスクの少ない金融商品の提案
  • 企業間の駆け引き

といった問題を効率良く解くことができます。

ORの研究は地味ではありますが,テレビで取り上げられることもあるので,ここで 紹介しましょう。

特に,国内の番組で取り上げれた問題は,私達の身近にあるものです。皆さんも学生生活の中で問題を見つけてORを使って解いてみませんか? きっとスリリングな気分が味わえますよ。

Monty Hall -3つの扉-

Monty Hall 問題

あなたの目の前に三つの箱があります。箱の一つには賞金が入っていて,残りは 空です。 あなたからは,箱の中身は見えません。賞金の入っている箱を当てれば,賞金 を獲得できます。

Step 1  あなたは,箱を一つを選びます。
Step 2  司会者は,残りの二つの箱のうち,空のものの扉を一つ開 けます。
Step 3  司会者はあなたに,「箱の選択を替えることができますが ,どうしますか?」と聞きます。

さて,ここで箱の選択を替えるべきでしょうか?

ケース分けをして,確率を考えてみましょう。
今,箱にA,B,Cと名前を付けると,以下の三つのケースがあります。あなたは最初に いつも箱Aを選ぶとします。

箱A 箱B 箱C
ケース1  空  空  賞金
ケース2  空  賞金  空
ケース3  賞金  空  空

★Step 3で箱を替えない 場合
司会者は,ケース1では箱Bの扉を開け,ケース2では箱Cの扉を開けます 。ケース3では箱BかCの扉を開けますが,あなたは箱を替えないので,賞金を獲得す る確率は 1/3 です。

★Step 3で箱を替える 場合
司会者は,ケース1では箱Bの扉を開けるので,Step 3 であなたは箱Cを 選びます。同様に,ケース2では,司会者は箱Cの扉を開けるので,あなたは箱Bに替 えます。ケース3では,司会者は箱BかCの扉を開けるので,あなたは箱B・Cのうち扉 を開けられなかった箱に替えます。すると,賞金は,3ケースのうち2ケースで獲得で きるので,確率は 2/3 となります。

よって答えはYESです。箱の選択を替えた方が,賞 金を 獲得する確率が高くなります。Step 1で箱を選んだとき,箱の中に賞金が入っている確 率は 1/3 ですが,Step 3で箱を替えることにより, 確率が 2/3 にあがるのです。

以上の確率は,ベイズの定理を使って示すことができますが,ここでは直感的な説明 にとどめます。

Monty Hall 問題では,箱の数が10個あり,Step 2で八つの空箱の扉を開ける場合も ,上と同様にStep 3で箱を替えた方が有利です。 箱を替えた時に,賞金が獲得できる確率がどの位になるかは,簡単に考えられますね。

トリビアの泉-最長しりとり-

最長しりとり問題

最長のしりとりを作成しなさい。ただし,しりとりは以下の条件をすべて満たすもの とします。

  • 広辞苑に載っている15万語余りの名詞のみを使用する。
  • 母音で次の言葉へ繋ぐ。「コーヒー(こぉひぃ)」→「イルカ」
  • 「じ」と「ぢ」,「ず」と「づ」は同じ音として扱う。
  • 同じ音の名詞(「橋」と「箸」等)は同じものとして扱い,使用は1度の みとする。
  • 1度使用した言葉は再び使用しない。
  • 「しりとり」から始まり,言葉の語尾に「ん」が付いたら終了する。

さて,上の条件を満たす最長しりとりは,何語からなるでしょう。またパソコンで, どの程度の時間で求められるでしょうか。

答えは,約7万語を用いた最長しりとりを作成でき,性能の良い パソコンを用いて,たった11秒で解けるのです。

東京農工大の研究者達は,「最長しりとり問題」を,「頂点と矢印からなる有向グラフ上で,最長の一筆書きを求める問題」としてとらえ,この問題を線形計画問題に定式化して解きました。

更に詳細な解説を知りたい方は,番組で問題を解いた,東京農工大・品野勇治氏による 解説をご覧く ださい。

トリビアの泉はHPはこちら

NHK BShi 列島縦断鉄道12000キロの旅 -最長片道切符でゆく42日-

最長片道切符問題

国内のJR鉄道網を利用した最長片道切符を求めなさい。ただし,以下の条件を満たすものとします。

  • 同じ駅には2度と立ち寄らない。
  • JR鉄道網を一筆書きで乗りつぶしていく。

上の条件を満たす,最長片道切符で旅行できる経路の長さは,どの程度なのでしょうか。

答えは,JR全路線の約6割を走破する,全長約12000キロのもの経路で,パソコンを用いて100秒程度で求めています。
この最長片道切符問題は,葛西隆也氏が東大大学院生時代に,友人の宮代隆平氏と協力して解きました。 彼らは「最長片道切符の旅を求める問題」を,「頂点と線からなる無向グラフ上で,最長パスを求める問題」としてとらえ,整数計画問題 に定式化して解いたのです。

葛西氏は,自分で求めた最長片道切符を購入し,実際に42日間かけて旅行されました。 更に詳細な解説を知りたい方は,葛西隆也氏による 解説をご覧ください。

NHK BShi 列島縦断鉄道12000キロの旅 - 最長片道切符でゆく42日-のHPはこち ら