2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:05 
Недавно попалась следующая задачка: $n$ братьям в наследство достался квадратный участок. Как им разместить свои дома, чтобы наименьшее расстояние между домами было максимальным. Не могу сообразить, как ее формализовать.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:37 
Положение каждого дома задается парой координат (переменных) $x_i,y_i$; без ограничения общности можно считать, что их область определения [0,1]. Еще будет неотрицательная переменная – квадрат минимального расстояния $q$. Для каждой пары домов – ограничение на квадрат расстояния с помощью $q$. Максимизировать нужно $q$.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:46 
Аватара пользователя
2718281828459045 в сообщении #391154 писал(а):
Не могу сообразить, как ее формализовать.

надо максимизировать минимум... это же классический минимакс:))

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:50 
Я примерно так и рассуждал.
$A_1(x_1,y_1), A_2(x_2,y_2), \dots, A_n(x_n,y_n)$- координаты домов.
$r_1=\rho(A_1,A_2),\dots,r_{C_n^2}=\rho(A_{n-1},A_n)$ - всевозможные расстояния между ними.
$q=\min\{r_1,\dots,r_{C_n^2}\}$. Получается такая задачка:
$$q=q(x_1,y_1,\dots,x_n,y_n) -> \max

0 \leq x_1,y_1,\dots,x_n,y_n \leq 1

0<r_1,\dots,r_{C_n^2} \leq \sqrt{2}
$$

А как ее решить не знаю. Да и не уверен, что она корректно составлена. подскажите, пожалуйста как с ней быть.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:51 
Аватара пользователя
В моём понимании она была достаточно формализована уже в исходном сообщении. Сильно лучше не будет. Как не будет и сколько-нибудь интересных аналитических результатов.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:54 
Может кто подскажет литературу по решению нелинейных задач?)

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение24.12.2010, 23:56 
Аватара пользователя
условие
2718281828459045 в сообщении #391178 писал(а):
.
$$0<r_1,\dots,r_{C_n^2} \leq \sqrt{2}$$

явно лишнее

ИСН в сообщении #391179 писал(а):
Сильно лучше не будет. Как не будет и сколько-нибудь интересных аналитических результатов.


так тут не аналитика... интересно, что предложит машина.

это называется в метрической геометрии "разделенное множество"

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 00:57 
В “формате” нелинейного программирования задача выглядит так:
$q \le (x_i-x_j)^2+(y_i-y_j)^2$ , где $1 \le i < j \le n$
$q-->max$
Решить ее можно численно с помощью пакетов глобальной оптимизации.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 12:05 
Аватара пользователя
Может попробовать решить исходную задачу без формализации? Допустим, расположить дома по углам квадрата и в центре, и попробовать доказать, что лучше расположить нельзя?

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 12:21 
Аватара пользователя
4 по углам, а остальные 16 в центре? :D

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 12:39 
Аватара пользователя
Предлагаю салонную интерпретацию:
Даме, которая очень любила крупные бусы (чем крупнее -- тем лучше), подарили красивую коробочку размером $1\times 1$ (в дециметрах). Дама решила заказать себе ожерелье из $n$ бусин. Какого диаметра $d(n)$ ей заказывать бусины, чтобы она могла хранить их в этой красивой коробочке?

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 12:46 
Аватара пользователя
ИСН в сообщении #391270 писал(а):
4 по углам, а остальные 16 в центре? :D
Неверно прочёл условие. Показалось, что братьев 5. Интересно получить решения для малых $n$.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 12:57 
Аватара пользователя
Когда 5, тогда-то, конечно, всё просто. И 6 просто, и 8.

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 12:59 
Аватара пользователя
ИСН в сообщении #391299 писал(а):
Когда 5, тогда-то, конечно, всё просто. И 6 просто, и 8.

и когда бусин $N$ -- тоже просто... до $O(1/\sqrt{N})$

 
 
 
 Re: Задача о недружных братьях (нелинейная оптимизация)
Сообщение25.12.2010, 13:11 
Перевожу на русский язык предыдущие сообщения. Данная задача близкородственна проблеме оптимальной упаковки в формулировке: дано n цилиндров диаметра 1; их нужно поместить в квадратную коробку наименьшей площади. Существует оптимальное покрытие (наиболее плотное) плоскости окружностями – с помощью него можно оценить сверху решение и получить приближенное для больших n.
P.S. Чтобы получить решение для исходной задачи, нужно отрезать от краев коробки полоски размером 0,5.

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group