★Beat Angels

前途は遠かった。でもそれはどうでもいい。道こそが人生だからだ。 - Jack Kerouac

セールスマン勧誘問題とその応用

ある区域でセールスマンが営業活動を開始した。勧誘の結果、成約に至るとその契約した者もセールスマンとして同じように営業を開始する。これを繰り返すことでその区域の加入者数はどんどん増えていく。いわゆるねずみ講の原理である。

   f:id:taamori1229:20200316214008p:plain

 このときの加入者数の推移を数学的に解析する。 

【セールスマン勧誘問題】

(1) ある区域における全体の人口をNとする。

(2) 人口Nに対する加入者の割合、つまり加入率をSとする。
 (Sが100%となった時点が全員加入時つまり営業完了時となる)

(3) 加入者は区域内でランダムに人に接触し、一日に出会う人をm人とする。ランダムなのでm人の中には当然既加入者も含まれる。

(4) 接触した非加入者が成約に至る確率は一定でそれをαとする。

(5) 新規で加入してくれた人にはそのお礼として1泊の温泉ツアーが振る舞われる。

(6) 温泉ツアーは一日最大H人までというホテルの収容制限がある。

 まず、Sについての微分方程式は、

 f:id:taamori1229:20200318065002p:plain

となる。この微分方程式を解くと、

 f:id:taamori1229:20200318065101p:plain

となる。ここでSoはスタート時点(t=0)の契約率である。スタート時点においてセールスマンは全体の人口Nに対して非常にはこれは小さいとして近似式を用いた。

セールス開始直後の期間はさらに、

f:id:taamori1229:20200318065143p:plain

という近似式となる。加入者は指数関数的に増加する。これがねずみ講と呼ばれるゆえんである。

契約率Sが増加してくるに従って元の微分方程式の(1-S)の項の影響が出てきて増加が抑制される。つまり、非加入者が減少してくるためである。こうして時間が経過するに従って下図のようにSは1に限りなく近づいていく。

f:id:taamori1229:20200318065244p:plain

接触者数mそして、成約率αを上げることによって1に近づくまでの時間を短縮することが可能である。

ここで新規加入者に対する温泉ツアーにおけるホテルの収容制限(H人まで)の問題を考える。ホテルの収容能力を考慮すると、接触者数m、成約率αをコントロールして一日あたりの新規加入者数を押さえ込まないといけない

一日の新規加入者の推移はつまりSを微分することでえられる。

 f:id:taamori1229:20200318065322p:plain

さらにこれを微分すると、

 f:id:taamori1229:20200318065402p:plain

となり、これが0となる時が新規加入者数が最大となる時に対応する。そのtを求めると、

 f:id:taamori1229:20200318065446p:plain

が得られる。この時の新規加入率を計算すると、

 f:id:taamori1229:20200318065522p:plain

となる。この時のSを計算するとちょうど0.5となる。つまりこのタイミングで加入者、未加入者の大小関係が入れ替わることになり、この時を境に契約者数の伸びが鈍化するといいうのは直観とも一致する。

以上をグラフにて表すと下記となる。

f:id:taamori1229:20200318065602p:plain


新規加入率の変化に人口Nを掛けたものが、その日一日の新規加入者数になる。これがホテルの収容能力H以下になればいい。

f:id:taamori1229:20200318065634p:plain

これより、接触者数mと成約率αについての条件は、

 f:id:taamori1229:20200318065707p:plain

となる。これを満足するように営業活動を行うことでホテルの収容制限を守ることができる。つまり、一日の接触者数を抑えること、そして接触した場合の制約に至る確率を下げることである。

セールスマンの問題としては以上である。ご推察のとおり、本分析は昨今、世界中を騒がせている最大の関心事の分析を意図してなされたものである。Hとはホテルの部屋数(Hotel)でもあり、病院の病床数(Hospital)でもある。いずれにしても早期に沈静化することを願うばかりである。