つながりと待ちを考える

1点と線で関係を表す

グラフ理論でのグラフは、頂点（ノード）と辺（エッジ）で対象と関係を表すものです。駅を頂点、線路を辺にすれば路線のつながりを調べられます。棒グラフのような統計グラフとは意味が違います。

有向グラフの辺には向きがあり、一方通行A→BからB→Aへ進めるとは限りません。無向グラフは向きを区別しません。辺に時間や費用を付ければ経路の比較にも使えます。

2最短は辺の数だけでは決まらない

例えば、A→Cは8分、A→Bは2分、B→Cは3分とします。AからCへ直接行くと8分。Bを経由すると2＋3＝5分です。辺は2本でも所要時間が短くなります。何を最小にしたいかを先に決めます。

最適化問題は制約の範囲内で、費用を最小又は利益を最大にする解を探す問題です。配達順序、勤務表、原料配分などで使います。安くても到着期限を守らない経路は実行可能な解ではありません。

3処理中にも次の人が来る

待ち行列は、処理する窓口がふさがっている間に次の要求が待つ状態です。客の到着間隔と対応時間のばらつきが待ちを生みます。平均の処理能力が平均到着量を上回っていても待ちは起こり得ます。

架空の窓口が1人3分で対応し、客Aが0分、Bが1分、Cが2分に来ると、開始は0分、3分、6分。待ち時間は0分、2分、4分で平均2分です。

4待ちを減らす手段を選ぶ

処理時間を短くする、混む時間帯に窓口を増やす、予約で到着を分散するなどの改善ができます。稼働率を限界近くまで上げると、ばらつきのある到着では待ちが長くなりやすくなります。

窓口追加には費用がかかります。「人件費の上限を守りつつ待ちを短くする」のように目的と制約をセットにして比較します。この章では高度な待ち行列モデルの公式は用いません。

5制約を満たす候補から最適を選ぶ

最適化では、まず実行できる条件である制約を満たす候補を残し、その中で目的の値が最もよいものを選びます。架空の仕事Aは2時間で利益4万円、仕事Bは3時間で利益5万円で、各仕事を一度まで選べるとします。使える時間は合計3時間です。

Aだけなら2時間・4万円、Bだけなら3時間・5万円、何もしなければ0時間・0万円です。AとBを両方行えば利益は9万円ですが、5時間かかるため制約を満たしません。利益を最大にするなら、実行可能な候補の中で利益が最大のBを選びます。

目的が所要時間の最小化などに変われば判断も変わるため、目的と制約をセットで確認します。