離散数学の応用(待ち行列と最適化)
標準約 16 分2 用語過去問 2 題
この単元の目標
- 待ち行列 のモデルが何を見積もるのかを説明できる
- 利用率 と待ち時間の関係を説明できる
- 最適化問題 を 制約条件 と 目的関数 に分けて組み立て、小さな問題の 最適解 を求められる
用語総表（2 語）
用語
待ち行列 は、サービスを受けるために順番を待つ列を、到着と処理の様子から数量的に扱うモデルである。
到着の間隔も 1 件あたりの処理時間もばらつくので、平均の待ち時間や列の長さを確率と統計で見積もる。基本の形は、窓口が 1 つで、先に着いたものから順に処理される。窓口が処理中である時間の割合を 利用率 といい、平均処理時間を平均到着間隔で割って求める。
たとえ病院の受付で番号札を取り、呼ばれるまで待合室で待つ流れ。混む曜日ほど、待合室の人数も待つ時間も増える。
覚え方待ち行列の理論は、電話交換機の回線がどれだけ混み合うかを調べる研究から始まった。
出題のポイント
- 混同注意利用率が上がると、待ち時間は比例して少しずつ伸びるのではない。利用率が 1 に近づくにつれて、待ち時間は急に長くなる。
- 混同注意待ち行列のモデルは混み具合を見積もるための道具であり、データを入れた順に取り出すデータ構造のキューとは目的が違う。
最適化問題 は、守るべき条件 (制約条件) を満たす解の中から、利益の最大や費用の最小のように良さの尺度 (目的関数) が最も良くなる解 (最適解) を求める問題である。
解の候補が少なければ、すべてを並べて目的関数の値を比べれば最適解が分かる。候補が多いときは、線形計画法 のように条件と目的を式に表して解く手法を使う。作業をどの順番で進めるか、いくつもの地点をどの順番で回るかを決める問題も、最適化問題の例である。
たとえ旅行のかばんに入る量の範囲で、役に立つ持ち物が最も多くなるように詰める物を選ぶこと。
覚え方英語の optimization の元は、ラテン語で「最良の」を意味する optimus。最大と最小のどちらを目指す場合も、まとめて「最良」と呼ぶ。
出題のポイント
- 出題最適化問題では、解が満たすべき制約条件と、最小化または最大化する目的関数を分けて書く。制約条件は問題の前提から導き、前提にない条件を足すと、本来の最適解が候補から外れることがある。
- 出題経由する順番を自由に選べる経路の最短時間は、順番の候補ごとに所要時間の合計を出し、最も小さいものを選べば求まる。通れない区間を含む順番は候補から外す。
- 出題2 台の機械を同じ順に使う作業を、全部が終わるまでの時間が最短になるよう並べるには、最も短い使用時間が前の機械ならその作業を先頭、後の機械なら最後に置き、残りで繰り返す (ジョンソン法)。
この用語の過去問 2 題 最適化問題 →
要点
- 待ち行列 は、到着と処理のばらつきから平均の待ち時間や列の長さを見積もるモデルである。
- 窓口が 1 つの場合、利用率 は平均処理時間を平均到着間隔で割った値で、1 に近づくと待ち時間が急に伸びる。
- 最適化問題 は、制約条件 を満たす解の中で 目的関数 が最も良い 最適解 を探す。
- 候補が少ない最適化問題は、すべての候補の値を計算して比べれば解ける。
この分野の過去問をすべて見る →