О постановке задачи линейного присваивания

Question

Я смотрю на стандартное определение задачи назначения, как определено здесь

Мой вопрос связан с двумя ограничениями (следует латексная запись):

\sum_{j=1}^n(x_{ij}) = 1 for all i = 1, ... , n
\sum_{i=1}^n(x_{ij}) = 1 for all j = 1, ... , n

В частности, зачем требовалось второе ограничение? Разве первая уже не охватывает все пары x_ {ij}?

Answer 1

Рассмотрим матрицу x_ij с диапазоном i по строкам и j по столбцам.

Первое уравнение говорит, что для каждого i (то есть для каждой строки!) Сумма значений в этой строке равна 1.

Второе уравнение говорит, что для каждого j (то есть для каждого столбца!) Сумма значений в этом столбце равна 1.

Answer 2

Нет.Учитывая, что все записи в X являются 0 или 1, одно ограничение говорит: «в каждом столбце есть ровно один 1», а в другом - «существует ровно один * 1007».* в каждой строке '(я всегда забываю, в какую сторону обычно идут индексы матрицы).Эти утверждения имеют независимые значения истинности.

Answer 3

Это даже не проблема программирования. Но я все равно отвечу.

Первым является сумма по j, для КАЖДОГО значения i. Вторая сумма по i, для КАЖДОГО значения j.

Таким образом, по существу, один из этих наборов ограничений требует, чтобы сумма по строкам матрицы x_ {i, j} матрицы была равна единице. Другое ограничение - это требование, чтобы сумма по столбцам этой матрицы была равна единице.

(правка) Похоже, что мы здесь до сих пор не ясны. Рассмотрим матрицу

[0 1]
[0 1]

Нужно согласиться, что сумма по строкам этой матрицы равна 1 для каждой строки. Однако, когда вы формируете сумму элементов первого столбца, она равна нулю, а сумма элементов во втором столбце мы находим 2.

Теперь рассмотрим другую матрицу.

[0 1]
[1 0]

Обратите внимание, что здесь сумма по строкам или столбцам всегда равна 1.