Математическое программирование

[Slow]

Есть квадрат $n \times n$ клеток разделенный на связные области(парки). В каждом парке должно быть высажено ровно одно дерево. Два дерева не могут располагаться на одной горизонтали или вертикали. Также два дерева не могут находиться на соседних по горизонтали, вертикали и диагонали клетках. На вход подается матрица $A_{ij}$ размера $n\times n$, $a_{ij} \in \{1,...,n\}$ - номер парка в котором лежит клетка$(i,j)$. Нужно поставить задачу оптимизации для нахождения допустимой расстановки деревьев.
Мои мысли по поводу решения: В качестве неизвестных возьмем матрицу $n \times n$ $ X_{ij}$ и следующие ограничения:
$\sum_{i=1}^n x_{ij}\leqslant 1$
$\sum_{j=1}^n x_{ij}\leqslant 1$
$\sum_{(i,j)} x_{ij}=1$ $(i,j)\in O_k$, где $O_k$ k-ая область.
$x_{i,j}+x_{i+1,j+1}\leqslant 1$
$x_{i,j}+x_{i-1,j+1}\leqslant 1$
$x_{i,j}+x_{i-1,j-1}\leqslant 1$
$x_{i,j}+x_{i+1,j-1}\leqslant 1$
Вопрос в том правильно ли я подобрал ограничения и какую выбрать целевую функцию, ведь фактически нам подойдут любые решения удовлетворяющие этим ограничениям.

[Deggial]

Slow в сообщении #910635 писал(а):

$x_{i,j}+x_{i+1,j+1}\leqslant 1$
$x_{i,j}+x_{i-1,j+1}\leqslant 1$
$x_{i,j}+x_{i-1,j-1}\leqslant 1$
$x_{i,j}+x_{i+1,j-1}\leqslant 1$

потеряли ещё 4 ограничения из условия

Slow в сообщении #910635 писал(а):

Также два дерева не могут находиться на соседних по горизонтали, вертикали и диагонали клетках.

остальное нормально

Slow в сообщении #910635 писал(а):

и какую выбрать целевую функцию

Очевидно какую Решение "все $x_{ij}=0$" Вас ведь не удовлетворит? Почему?

[Slow]

Deggial в сообщении #911145 писал(а):

Slow в сообщении #910635 писал(а):

$x_{i,j}+x_{i+1,j+1}\leqslant 1$
$x_{i,j}+x_{i-1,j+1}\leqslant 1$
$x_{i,j}+x_{i-1,j-1}\leqslant 1$
$x_{i,j}+x_{i+1,j-1}\leqslant 1$

потеряли ещё 4 ограничения из условия

Slow в сообщении #910635 писал(а):

Также два дерева не могут находиться на соседних по горизонтали, вертикали и диагонали клетках.

остальное нормально

Так если на вертикали и горизонтали не лежит два дерева следовательно и на соседних по вертикали и горизонтали тоже не могут лежать два дерева.

Добавилось условие что парков должно быть ровно $n$ штук, тогда $\sum_{i=1}^n x_{ij}\leqslant1$ можно заменить на $\sum_{i=1}^n x_{ij}=1$ и второе условие тоже.
Еще возникла такая проблема: чтобы записать условие того что каждый парк содержит ровно одно дерево нужно сначала в матрице $A$ искать одинаковые индексы соответствующие одному парку, а хотелось бы записать это условие в более удобном виде, например я пробовал $\sum_{j=1}^n\sum_{i=1}^n a_{ij}x_{ij}=\sum_{i=1}^n i$ тут мы использовали только значения матрицы $A$, но это условие не эквивалентно тому что в каждом парке ровно одно дерево.

[Deggial]

Slow в сообщении #911504 писал(а):

Так если на вертикали и горизонтали не лежит два дерева следовательно и на соседних по вертикали и горизонтали тоже не могут лежать два дерева.

Да, действительно (это потому, что я читал снизу вверх).

Slow в сообщении #911504 писал(а):

чтобы записать условие того что каждый парк содержит ровно одно дерево нужно сначала в матрице $A$ искать одинаковые индексы соответствующие одному парку, а хотелось бы записать это условие в более удобном виде

Что понимается под "удобным видом" - аналитически удобно или в плане вычислений?

Slow в сообщении #911504 писал(а):

например я пробовал $\sum_{j=1}^n\sum_{i=1}^n a_{ij}x_{ij}=\sum_{i=1}^n i$ тут мы использовали только значения матрицы $A$, но это условие не эквивалентно тому что в каждом парке ровно одно дерево.

Как Вы сами понимаете, нумерация парков числами $1,2,...,n$ совершенно произвольна. На самом деле, нумеровать парки мы можем какими попало числами - $c_1,\dots ,c_n$. Значит мы можем подобрать их так, чтобы по сумме, аналогичной сумме слева, можно было однозначно определить номер парка.
Также легко всё выразить через дельты Кронекера.

[Slow]

Deggial в сообщении #911532 писал(а):

Slow в сообщении #911504 писал(а):

Так если на вертикали и горизонтали не лежит два дерева следовательно и на соседних по вертикали и горизонтали тоже не могут лежать два дерева.

Да, действительно (это потому, что я читал снизу вверх).

Slow в сообщении #911504 писал(а):

чтобы записать условие того что каждый парк содержит ровно одно дерево нужно сначала в матрице $A$ искать одинаковые индексы соответствующие одному парку, а хотелось бы записать это условие в более удобном виде

Что понимается под "удобным видом" - аналитически удобно или в плане вычислений?

Slow в сообщении #911504 писал(а):

например я пробовал $\sum_{j=1}^n\sum_{i=1}^n a_{ij}x_{ij}=\sum_{i=1}^n i$ тут мы использовали только значения матрицы $A$, но это условие не эквивалентно тому что в каждом парке ровно одно дерево.

Как Вы сами понимаете, нумерация парков числами $1,2,...,n$ совершенно произвольна. На самом деле, нумеровать парки мы можем какими попало числами - $c_1,\dots ,c_n$. Значит мы можем подобрать их так, чтобы по сумме, аналогичной сумме слева, можно было однозначно определить номер парка.
Также легко всё выразить через дельты Кронекера.

Вы имеете ввиду перенумеровать значения элементов матрицы? Но тогда опять же придется искать в матрице элементы с одинаковыми номерами. Под "удобно" я имею ввиду в плане вычислений.

[Deggial]

Slow в сообщении #911602 писал(а):

Вы имеете ввиду перенумеровать значения элементов матрицы?

Да, но не перестановку.

Slow в сообщении #911602 писал(а):

Но тогда опять же придется искать в матрице элементы с одинаковыми номерами.

В общем случае - нет.
Ассоциация: $a_02^0+a_12^1+a_22^2=7, a_0,a_1,a_2\in\{0,1\} \Leftrightarrow a_0=a_1=a_2=1$

Slow в сообщении #911602 писал(а):

Под "удобно" я имею ввиду в плане вычислений.

Тогда проще исходная запись с суммой $\sum\limits_{(i,j)\in O_k}$

[Slow]

Большое спасибо, я во всем разобрался. Тему можно считать закрытой.