合コンの席の最適化

広告

スレに「[合コン「席決め」]奈良の学生ベンチャーがシステム開発」というのがあったので、考察してみます。

これはたぶんLP(線形計画法)ですね

違うかも知れないけど、以前に大学でゼミの割り振りを科学的にやってくれという話があったので使った話を思い出しつつ書きます。

まずポイントを割り振ります。第一志望の満足度を仮に10とします。第二志望は7、第三志望は4、それ以下だと0とでもしておきます。実はこのポイントの割り振り(パラメータの決定)が一番のキモで、それが決まってしまえばこの程度のシステムは1時間もかからずに作ることはできます。頭が錆びていなければね。LPのソルバーもフリーで十分実用になるのが転がっていますし、Excelでもよいでしょう。

もちろん、インターフェースとか本質的でない部分は多少手間はかかるかも知れませんね。

パラメータを決めたら

n番目の人の満足度S(n)を求めます。理想的にはS(1)=S(2)=・・・・S(n)=10ですが、なかなかそうも行きません。膨大な組み合わせの中から最適解を探すには、S(1・・n)の合計が最大になるという条件で線形計画問題を解けばOKです。

制約条件は

これはバイナリ計画問題です。席の場所にも番号を振って、nさんがその席に座っていれば1、座っていなければ0とでもします。同じ席に二人座れないという制約は「足して1」であることでよいでしょう。

他にもなんかあったかも。でもそう複雑ではありません。その条件の下で満足度を最大にする組み合わせを見つければいいのです。

システムはできても検証できないのが喪

男女5人ずつが横一列に向かい合って座る場合、約100万通りの席順があるが、98%以上の確率で第1〜3希望の異性が自分の正面に座る席順をはじき出せる。男女15人ずつまでならこの確率を維持できるという。好みが1人に集中するような場合は、希望に添えないこともある。

100万通りとかいう解説は実は無意味です。実際にLP解いてみればわかるけど、最近のコンピュータならほぼ一瞬で解けるはずです。数理計画を勉強したことのある人なら、これを100万通り全部試すと考えません。最適解があるのは、実行可能領域と呼ばれる凸多面体の頂点だけと偉い人が保証して下さっていますので、そこだけ探せばいいのです。

問題は、ですね、システムができても合コンを開けないし、開けるリア充の友達がいないため、システムの有効性が検証できないところにあります。

もう一つはですね「男女15人ずつまでならこの確率を維持できる」と言うけど、これはもっと多くても数理的には可能です。が、人間の場合は美形に人気が集中するため、人数を増やしすぎると1人に100人の希望者が殺到して破綻します。人間は数理的には動かないのです。

広告