2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Математическое программирование
Сообщение22.09.2014, 19:58 


28/05/12
214
Есть квадрат $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$
Вопрос в том правильно ли я подобрал ограничения и какую выбрать целевую функцию, ведь фактически нам подойдут любые решения удовлетворяющие этим ограничениям.

 Профиль  
                  
 
 Re: Математическое программирование
Сообщение23.09.2014, 21:57 
Супермодератор
Аватара пользователя


20/11/12
5728
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$" Вас ведь не удовлетворит? Почему?

 Профиль  
                  
 
 Re: Математическое программирование
Сообщение24.09.2014, 17:54 


28/05/12
214
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$, но это условие не эквивалентно тому что в каждом парке ровно одно дерево.

 Профиль  
                  
 
 Re: Математическое программирование
Сообщение24.09.2014, 18:59 
Супермодератор
Аватара пользователя


20/11/12
5728
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$. Значит мы можем подобрать их так, чтобы по сумме, аналогичной сумме слева, можно было однозначно определить номер парка.
Также легко всё выразить через дельты Кронекера.

 Профиль  
                  
 
 Re: Математическое программирование
Сообщение24.09.2014, 21:09 


28/05/12
214
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$. Значит мы можем подобрать их так, чтобы по сумме, аналогичной сумме слева, можно было однозначно определить номер парка.
Также легко всё выразить через дельты Кронекера.

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

 Профиль  
                  
 
 Re: Математическое программирование
Сообщение25.09.2014, 09:35 
Супермодератор
Аватара пользователя


20/11/12
5728
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}$

 Профиль  
                  
 
 Re: Математическое программирование
Сообщение29.09.2014, 12:22 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group