はじめに 組合せ最適化でチーム分けする で紹介されている問題を別のモデルで解いてみます。 この問題は、バラツキを最小化する組合せ最適化問題です。 バラツキ具合の指標としては一般的に分散がよく使われますが、分散は二次関数で表されるため一次関数を最小化する線形計画問題に比べると難しくなってしまいます。そこで元の記事では最大値と最小値の差(範囲)を最小化する線形計画問題として定式化しています。 一方、範囲の代わりに平均偏差を最小化する方法もあります。 そこで本記事では、まず範囲と平均偏差のモデルの違いを比較します。 最後に平均偏差最小化問題の例題をPython+PuLPで解いてみます。 問題設定 前提条件 $n$人のメンバーを$m$個のチームに分ける。 各メンバーが持つコミュニケーション能力の種類は$l$個あり、それぞれ点数が振られている。 目標 チーム内で能力が偏らないようにする。 チーム間の