Оптимизационные задачи планиметрии

[eugrita]

"Задача столяра" опубликованная мною здесь недавно принадлежит к классу оптимизационных или экстремальных задач геометрии.
Вот еще перечень таких задач в некот.случаях с ссылкой на источник (Прасолов,МЦНМО)
Многоугольники.Экстремальные свойства
1.Многоугольник вписанный в окружность мах площади и периметра.
Доказать что среди всех n-угольников, вписанных в окружность,$ R$ наибольшую площадь и периметр имеет правильный n-угольник. . (Прасолов В.В,МЦНМО, я)
1.1 Среди всех многоугольников, вписанных в данную окружность, найдите тот, у которого максимальна сумма квадратов длин сторон. (Прасолов В.В,МЦНМО)
2. Многоугольник описанный вокруг окружность мин площади и периметра.
Доказать что среди всех n-угольников, описанных вокруг окружности,$r$ наименьшую площадь,$ S$ и периметр $p$ имеет правильный n-угольник. (Прасолов В.В,МЦНМО, я)
3.Точка сумма расстояний до вершин выпуклого n-угольника=мин. При$N=3$ – точка Торичелли, $N=4$ – т.пересечения диагоналей
3.1. Многоугольник имеет центр симметрии O. Докажите, что сумма расстояний до вершин минимальна для точки O. (Прасолов В.В,МЦНМО)
3.2. Докажите, что сумма расстояний от центра правильного 7-угольника до всех его вершин меньше, чем сумма расстояний до них от любой другой точки. (Прасолов В.В,МЦНМО)
3.3. Докажите, что сумма расстояний от произвольной точки X до вершин правильного n-угольника будет наименьшей, если X — центр n-угольника. (Прасолов В.В,МЦНМО)
4.Точка сумма расстояний которой до сторон выпуклого n-угольника минимальна $\min\sum(d_i)$ (я)
5.Задача о покрытии множества n-точек плоскости кругом мин радиуса (в пространстве – сферой мин радиуса).
----------------------------------------------------------
Интересны следующие вопросы
а)решение задачи 4 при $N>3$
б)решение общей задачи 3)
В принципе задачи кратчайшего пути на графе можно с некоторой натяжкой тоже отнести к экстремальным задачам планиметрии, правда на графе может не выполняться аксиома треугольника

[eugrita]

писать, так писать. Добавлю еще
Задача столяра.(1 или 2 распила наименьшей длины)http://dxdy.ru/topic71588.html
7.Изопериметрические задачи
7.2 Задача Дидоны с границей общая
какой формы должна быть кривая длины , чтобы площадь фигуры, ограниченная этой кривой и заданной линией была наибольшей?
7.2.1 Задача Дидоны частная обл.Г- прямая линия. Решение прямоугольник
7.2.2 Задача Дидоны без границ.
(задача Дидоны для прямоугольников) задача Дидоны для параллелепипедов) задача Дидоны для треугольников з-ча Дидоны для n-угольников.
Найти многоугольник с заданным периметром p охватывающий наибольшую площадь
8.З-ча Евклида Требуется в данный треугольник ABC вписать параллелограмм ADEF наибольшей площади.
6.Задача о минимальном покрытии.http://dxdy.ru/topic70845.html

[ewert]

eugrita в сообщении #721029 писал(а):

1.Многоугольник вписанный в окружность мах площади и периметра.
Доказать что среди всех n-угольников, вписанных в окружность,$ R$ наибольшую площадь и периметр имеет правильный n-угольник.

С площадью тривиально -- ясно, что площадь не максимальна, если хотя бы две стороны не одинаковы. С периметром не приходит в голову ничего более эстетичного, кроме как тупо выписать сумму двух сторон как нечто пропорциональное $\sin(\alpha+\gamma)+\sin(\alpha-\gamma)=2\sin\alpha\cdot\cos\gamma$, где угол $\alpha$ фиксирован, а тогда сумма этих двух сторон максимальна, естественно, при $\gamma=0$, т.е. опять же при равнобедренности.

eugrita в сообщении #721029 писал(а):

1.1 Среди всех многоугольников, вписанных в данную окружность, найдите тот, у которого максимальна сумма квадратов длин сторон.

Здесь можно чуть сознательнее. Пусть $\vec r_2$ -- одна из вершин и $\vec r_1$, $\vec r_3$ -- соседние с ней ($|\vec r_1|=|\vec r_2|=|\vec r_3|=1$), тогда сумма квадратов двух сторон есть $|\vec r_2-\vec r_1|^2+|\vec r_3-\vec r_2|^2=4-2\vec r_2\cdot(\vec r_1+\vec r_3)$. И если центр окружности не лежит внутри этого треугольника, то максимум у этой суммы будет тогда, когда средняя вершинка слипнется с одной из крайних. Отсюда ответ: равносторонний треугольник.

eugrita в сообщении #721029 писал(а):

2. Многоугольник описанный вокруг окружность мин площади и периметра.
Доказать что среди всех n-угольников, описанных вокруг окружности,$r$ наименьшую площадь,$ S$ и периметр $p$ имеет правильный n-угольник.

Здесь площадь равносильна периметру, а для соотв. участка периметра отличие от 1-й задачи только в том, что сумма синусов заменится на аналогичную сумму тангенсов, с которой хоть и чуть менее, но тоже всё ясно.

[мат-ламер]

eugrita в сообщении #721029 писал(а):

Интересны следующие вопросы ... б)решение общей задачи 3)

А в каком смысле решение? В общем случае решение - это численный алгоритм. (И без компьютера никак). Имеем задачу негладкой оптимизации (хотя в точке минимума оптимизируемая функция может быть и гладкой). В оптимальной точке выполняется свойство: сумма единичных векторов из данной точки в вершины равна нулю. Можно погуглить - задача Штейнера.

[ewert]

мат-ламер в сообщении #722514 писал(а):

eugrita в сообщении #721029 писал(а):

Интересны следующие вопросы ... б)решение общей задачи 3)

А в каком смысле решение? В общем случае решение - это численный алгоритм.

Общее решение -- это просверлить в вершинках дырочки, протянуть сквозь дырочки верёвочки, привязать к верёвочкам снизу камушки, а сверху связать все верёвочки одним узелком.

Кстати, для треугольника это и наиболее сознательно (правда, потребуется некоторая подводка). Для четырёхугольника тоже вполне можно, но там и без верёвочек всё тривиально. Все же прочие симметричные случаи мгновенно убиваются напрочь соображениями выпуклости и симметрии. Ну а для произвольного расположения надеяться на ответ в замкнутой форме, да, как-то странно.

В дополнение. Задача с кругами и точками -- откровенно переборная, и говорить имеет смысл лишь об оптимизации перебора (самый тупой и напрашивающийся алгоритм требует $O(n^4)$ операций). Задача с расстояниями до сторон -- в принципе, тоже переборная, но там возможен и условно замкнутый ответ: надо сложить все единичные векторы внешней нормали, и тогда их сумма будет указывать на оптимальную вершину. Указывать в том смысле, что эта вершина -- самая далёкая в направлении того суммарного вектора.

[eugrita]

Цитата:

. И если центр окружности не лежит внутри этого треугольника, то максимум у этой суммы будет тогда, когда средняя вершинка слипнется с одной из крайних. Отсюда ответ: равносторонний треугольник.

Имелось в виду что число сторон многоугольника n фиксировано

-- Чт май 16, 2013 20:32:24 --

Цитата:

Все же прочие симметричные случаи мгновенно убиваются напрочь соображениями выпуклости и симметрии. .

2)Нашел еще 1 задачу, на форуме ложащуюся в предложенный цикл -обратные расстояния в треугольнике
http://dxdy.ru/topic62557.html

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

[ИСН]

Несимметричных решений можно ожидать либо в пространстве (но там-то это слишком просто), либо в таких задачах, где по внутренним причинам происходит спонтанное нарушение симметрии. Из последних вспоминается задача о минимальной дорожной сети, но удастся ли её сюда приспособить - не факт.

[eugrita]

Я вижу по-моему еще довольно важную в т.ч на практике оптимизационную задачу геометрии- путь наименьшей длины (геодезическая линия). В частности вариант этой задачи дают в 5 классе на примере развертки куба (Муха и паук) (-проход кратчайшим путем по граням от одной до другой диаметрально-противоположной вершины). Моя формулировка:
Дана плоская односвязная область но с внутренними границами (препятствиями). Требуется пройти кратчайшим путем из т.А в т.B (обходя препятствия). (Любая форма внутр областей, сначала многоугольные не обязательно выпуклые).
Известна ли такая задача? И как профессионально называется в литературе?
Кстати можно ли использовать для таких областей термин "многосвязная"?
Математич.энциклопедия дает такое определение. Но например кольцо многосвязно в смысле этого определения, но связно в смысле, что любые 2 точки кольца можно соединить непрерывной линией, лежащей в кольце.

[eugrita]

[eugrita]

мат-ламер в сообщении #722514 писал(а):

eugrita в сообщении #721029 писал(а):

Интересны следующие вопросы ... б)решение общей задачи 3)

А в каком смысле решение? В общем случае решение - это численный алгоритм. (И без компьютера никак). Имеем задачу негладкой оптимизации (хотя в точке минимума оптимизируемая функция может быть и гладкой). В оптимальной точке выполняется свойство: сумма единичных векторов из данной точки в вершины равна нулю. Можно погуглить - задача Штейнера.

Поясните, что вы имеете ввиду под термином "негладкая оптимизация".
Я видел рабочую программу дисциплины "Экстремальные задачи в геометрии и анализе." Так вот там включен раздел "Анализ в функциональных пространствах. Производные Фреше и Гато."
Можете ли объяснить как изучение этого раздела конкретно может помочь решению хоть одной из представленных здесь задач?
Кроме того туда включен раздел "Геометрические задачи.Задача о быстродействии". Полагаю реально там и рассказывается о задачах преследования возможно с применением методов оптимального управления

[ewert]

eugrita в сообщении #725302 писал(а):

Поясните, что вы имеете ввиду под термином "негладкая оптимизация".

Целевая функция не является гладкой.

[eugrita]

Да. задал вопрос этот сдуру и получил соответств ответ.
Но тогда и в задаче мин покрытия целевая функция хотя и оч сложная тоже не является гладкой, хотя бы потому что число кругов(узлов решетки) сумма числа узлов внутри круга и числа узлов в близкой за-граничной обл - тоже сумма 2 разных функций. А методы развитые Демьяновым В.Ф СПБГУ (негладкий анализ)
хоть как-то применимы? очень хорошо написана его статья. в Соровском ж-ле
А его наглядный пример с МНК - образец как надо преподавать этот раздел в эконометрике. А то всем дают догму "метод наименьших квадратов" без всякой альтернативы!

[ewert]

eugrita в сообщении #725324 писал(а):

А его наглядный пример с МНК - образец как надо преподавать этот раздел в эконометрике.

Возможно, в эконометрике действительно так и надо (я в эконометристах не разбираюсь). Однако для всех остальных это наглядный пример того, как не нужно преподавать:

Цитата:

Так, если $|ax_i+b-y_i|$ есть штраф за нарушение графика, то, как следует из изложенного выше, выгоднее удовлетворить точки $x_0,\ x_1,\ x_2,\ x_3$ и игнорировать точку $x_4$ (и выбрать функцию $F_2$).

Уж не говоря о путанице в обозначениях и прочих стилистических прелестях -- тут двойной мухлёж. Во-первых, из изложенного выше вовсе не следует, что последняя точка именно "игнорируется". Во-вторых, если сдвинуть последнюю точку на единичку вправо, то визуально картинка практически не изменится, однако оптимальной окажется уже совершенно другая прямая -- проходящая через точки $(x_1,y_1)$ и $(x_4,y_4)$. Т.е. Демьянов тут тщательно пудрит мозги.

[eugrita]

1)хорошо, может и так.
А как бы вы решали задачу подбора параметров сглаживающей прямой по экспериментальным данным по критерию минимума мах отклонения? $\min \max|ax_i+b-y_i|$
Для использования компьютера вижу один только алгоритм -"грубой силы"
разбить области изменения a и b на маленькие куски и перебором находить оптимум. Возможно в этом то и была причина, что в свое время основатели эконометрики и методов прогноза тоже увидели отсутствие конструктивного метода и пошли по пути мин суммы квадратов, где функционал - дифференцируемая функция...А сейчас все преподаватели, а за ними студенты хором повторяют...

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

[ewert]

eugrita в сообщении #726438 писал(а):

А как бы вы решали задачу подбора параметров сглаживающей прямой по экспериментальным данным по критерию минимума мах отклонения? $\min \max|ax_i+b-y_i|$

Она решается стандартно -- перебираются средние линии всех треугольников и среди них ищется оптимальная. Перебор можно несколько ускорить, ища только "альтернансы" (простейший случай дискретного варианта теоремы Чебышёва). Можно, наверное, ещё олее ускорить, но это уже в раздел программирования.