На разработке проблемы линейного назначения

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.

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

Answer 2

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

Answer 3

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

Первая - сумма над j, для каждого значения i. Второй - это сумма над i, для каждого значения j.

По сути, один из этих наборов ограничения требует, чтобы сумма по рядам матрицы X_ {I, J} Matrix должна быть единством. Другим ограничением является требование, чтобы сумма по столбцам этой матрицы должна быть единством.

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

[0 1]
[0 1]

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

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

[0 1]
[1 0]

Увидеть это здесь, сумма над рядами или вниз по столбцам всегда 1.