Задача об определении оптим. местоположения с ограничениями

[oleg_d_s]

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

Решение данной задачи без ограничений представлено в справочнике поматематике Бронштейна (1981г, с 290), но как ее модифицировать под ограничения понять пока не могу

[Brukvalub]

oleg_d_s в сообщении #202532 писал(а):

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

Вырежьте из плоскости объединение кругов радиуса Х с центрами во второй группе точек и решайте задачу минимизации на оставшемся множестве.

[мат-ламер]

Нет у меня справочника Бронштейна под рукой. Ваша задача аналитически не разрешима. Если решать её численно, то это задача негладкой оптимизации с ограничениями. Можно попробовать применить метод проекции субградиента, либо путём введения дополнительных переменных свести эту задачу к задаче линейного программирования.

[oleg_d_s]

Как думаете, метод штрафных функций здесь применим?

[мат-ламер]

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

[oleg_d_s]

мат-ламер писал(а):

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

Ну не то чтобы прям очень просто, но по крайней мере этот метод мне немного понятен. Ну вот с написанием программы возможно будут проблеммы((

[мат-ламер]

oleg_d_s. Действительно, с написанием программы могут возникнуть некоторые проблемы. Дело в том, что в исходной постановке задача задана на невыпуклом множестве (плоскость за вычетом кругов). Её можно свести к задаче нелинейного (а не линейного) программирования. Тут я ошибся. Если использовать метод штрафных функций, то трудность будет не в том, что промежуточные задачи недифференцируемые, а в том, что они будут невыпуклые. Поэтому гарантировать глобальную сходимость тут нельзя. Недифференцируемость будет в конечном числе точек, и на неё можно не обращать внимание. Для надёжности надо решать задачу многократно из разных начальных точек и затем сравнить результаты. Для упрощения программирования возьмите MATLAB и промежуточные задачи решайте какой-нибудь стандартной процедурой , типа fminunc.

[mserg]

Так как неизвестных всего две, можно попробовать интервальный анализ. А есть готовые данные для этой задачи?

[oleg_d_s]

mserg писал(а):

Так как неизвестных всего две, можно попробовать интервальный анализ. А есть готовые данные для этой задачи?

данные есть, но смысл задачи состоит не в ее численном решении, а в подборе наиболее оптимального метода решения. Оптимального, имеется ввиду наиболее точного и простого в использовании)) Не слышал ничего насчет интервального анализа, дайте пожалуйста какую-нибудь интересную ссылочку почитать!

[mserg]

Лучший источник, который я знаю:
http://edurss.ru/cgi-bin/db.pl?lang=Ru& ... list=Found
Для использования можно найти библиотеку BIAS/PROFIL.

Из простых методов можно использовать генетический алгоритм/метод отжига, локальную оптимизацию со случайными точками старта (его описал мат-ламер).

Конкретные данные и найденный оптимум могут быть полезны другим пользователям. Когда просите помощи - неплохо что-нибудь сделать для других.