ここで定義されている割り当て問題の標準定義を見ています
私の質問は、2 つの制約を処理することです (ラテックス表記が続きます)。
\sum_{j=1}^n(x_{ij}) = 1 for all i = 1, ... , n
\sum_{i=1}^n(x_{ij}) = 1 for all j = 1, ... , n
具体的には、なぜ 2 番目の制約が必要なのですか? 最初のものはすでに x_{ij} のすべてのペアをカバーしていませんか?
3 に答える
4
行にまたがり、列にまたがる行列x_ijを考えてみましょう。ij
最初の式は、各行i(つまり、各行) の値の合計が 1 になることを示しています。
2 番目の方程式はj、各列 (つまり、各列) の値の合計が 1 になることを示しています。
于 2010-02-03T12:23:10.380 に答える
1
Xいいえ。すべてのエントリが0orであることを考えると1、一方の制約は「1各列1に正確に 1 つある」と言い、もう 1 つの制約は「各行に正確に 1つある」と言っています (行列の添字が慣習的にどのように移動するかを常に忘れています)。これらのステートメントには、独立した真理値があります。
于 2010-02-03T12:24:11.640 に答える
0
これは、リモートでさえプログラミングの問題ではありません。とにかく答えます。
1つ目は、iの各値に対するjの合計です。2つ目は、jの各値に対するiの合計です。
したがって、基本的に、これらの制約セットの1つでは、行列x_ {i、j}行列の行全体の合計が1である必要があります。もう1つの制約は、その行列の列の合計が1でなければならないという要件です。
（編集）ここではまだはっきりしていないようです。行列を考えてみましょう
[0 1]
[0 1]
この行列の行全体の合計が各行に対して1であることに同意する必要があります。ただし、最初の列の要素の合計を作成すると、それはゼロになり、2番目の列の要素の合計を作成すると2が見つかります。
ここで、別のマトリックスについて考えてみましょう。
[0 1]
[1 0]
ここで、行または列の合計は常に1であることがわかります。
于 2010-02-03T12:29:48.460 に答える