Задача о недружных братьях (нелинейная оптимизация)

[2718281828459045]

Недавно попалась следующая задачка: $n$ братьям в наследство достался квадратный участок. Как им разместить свои дома, чтобы наименьшее расстояние между домами было максимальным. Не могу сообразить, как ее формализовать.

[mserg]

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

[paha]

2718281828459045 в сообщении #391154 писал(а):

Не могу сообразить, как ее формализовать.

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

[2718281828459045]

Я примерно так и рассуждал.
$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} $$

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

[ИСН]

В моём понимании она была достаточно формализована уже в исходном сообщении. Сильно лучше не будет. Как не будет и сколько-нибудь интересных аналитических результатов.

[2718281828459045]

Может кто подскажет литературу по решению нелинейных задач?)

[paha]

условие

2718281828459045 в сообщении #391178 писал(а):

.

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

явно лишнее

ИСН в сообщении #391179 писал(а):

Сильно лучше не будет. Как не будет и сколько-нибудь интересных аналитических результатов.

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

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

[mserg]

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

[мат-ламер]

Может попробовать решить исходную задачу без формализации? Допустим, расположить дома по углам квадрата и в центре, и попробовать доказать, что лучше расположить нельзя?

[ИСН]

4 по углам, а остальные 16 в центре?

[paha]

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

[мат-ламер]

ИСН в сообщении #391270 писал(а):

4 по углам, а остальные 16 в центре?

Неверно прочёл условие. Показалось, что братьев 5. Интересно получить решения для малых $n$.

[ИСН]

Когда 5, тогда-то, конечно, всё просто. И 6 просто, и 8.

[paha]

ИСН в сообщении #391299 писал(а):

Когда 5, тогда-то, конечно, всё просто. И 6 просто, и 8.

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

[mserg]

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