線形計画法で解決できるかどうかわからない問題があります。基本的に、お互いの好みをリストアップした 2 つのグループがあり、その後マッチングされます。このためのアルゴリズムを書いています。グループ A はグループ B から 4 つまでの選択肢があり、その逆も同様です。
ソリューションを策定するにあたり、現在、各ペアの組み合わせにコストを割り当てています。たとえば、グループ A の人物 1 がグループ B の人物 3 を第 1 の選択肢としてランク付けし、その逆の場合、コストは最小になります (ペア 1-3 のコスト: 0.01)。同様に、他のペアにコストを割り当て、全体のコストを最小化するペアリングを求める目的関数を考案します。
ただし、制約と全体的な目的関数を定義する方法がわからないため、これが実現可能であるとは思いません。オンラインや教科書を読むと、リソース割り当ての問題は、私がやろうとしていることとは異なることがわかります。
進め方についてアドバイスを求めることはできますか？
あなたの問題は「割り当て問題」として定式化できます。標準的なケースとして、割り当て問題は「ジョブ」を「マシン」に割り当てるためのものです。2 つのセットのマッチングにも簡単に使用できます。
式は次のとおりです。A と B の 2 組の人物
決定変数 Xij
i 人 (集合A の i 人目) が集合 B の j 人目に一致する場合はXij1とします。それ以外の場合は0
パラメータ:を人と人Cijのペアリングのコストとするij
目的関数: 最小化 (i の合計) (j の合計)Cij * Xij
制約:
すべての人 i がペアリングされるのは 1 回だけです
Sum over j Xij = 1 (for each i)
すべての Person j が 1 回だけペアになります
Sum over i Xij = 1 (for each j)
Xij はバイナリ変数です
Xij = (0,1)
代入問題の優れた点は、かなりわかりやすい「ハンガリー法」を使用して最適な組み合わせを見つけることができることです。自由に使える LP/IP ソルバーを使用することもできます。
それが役立つことを願っています。