Простые алгоритмы численной оптимизации (одномерной)

21.12.14

Разработка - Математика и алгоритмы

В статье приведены реализации на 1С8 двух самых простых алгоритмов численной одномерной оптимизации, а именно: метод парабол и метод золотого сечения.
Статья является продолжением предыдущих:
1. Простые алгоритмы численного интегрирования (http://infostart.ru/public/314372/)
2. Простые алгоритмы численного решения задачи Коши для ОДУ (http://infostart.ru/public/315681/)

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

 

Итак, рассмотрим задачу оптимизации на отрезке [2;7] функции: F(x) = sin(x) + 1/x

Функция Функция_3(х)
	Возврат Окр(sin(х)+(1/х), 10); 
КонецФункции

Вызов расчетных функций:

Процедура ВыполнитьРасчет()

	Х_нач 		= 4;
	Шаг 		= 0.001*Х_нач;
	Точность	= 0.0001*Х_нач;
	Сообщить("Метод парабол	= " + РассчитатьМетодомПарабол(Х_нач, Шаг, Точность));
	
	Х_нач 		= 2;
	Х_кон		= 7;
	Точность	= 0.00001;
	Сообщить("Метод золотого сечения = " + РассчитатьМетодомЗолотогоСечения(Х_нач, Х_кон, Точность));
	
КонецПроцедуры	

Обратите внимание, что в методе парабол точность и шаг сделаны как функции от начального приближения.

Метод парабол:

Функция РассчитатьМетодомПарабол(Х_нач, Шаг, Точность)
	Хц = Х_нач; 
	Флаг = Истина;
	Пока Флаг = Истина Цикл
		Хл = Хц - Шаг; 
		Хп = Хц + Шаг; 
		Хмин = 0.5*((Функция_3(Хл)*(Хп+Хц) - 2*Функция_3(Хц)*(Хп+Хл) + Функция_3(Хп)*(Хц+Хл)))
					/(Функция_3(Хл)-2*Функция_3(Хц)+Функция_3(Хп)); 
					
		Если МодульМ(Хмин-Хц) < Точность Тогда
			Прервать;				
		КонецЕсли;	
		Хц = Хмин;
	КонецЦикла;			
	Возврат Окр(Хмин, 10);
КонецФункции

Метод золотого сечения:

Функция РассчитатьМетодомЗолотогоСечения(a, b, Точность)
	K = 1.618; // 0.5*(1 + Pow(5, 0.5)); 
	Флаг = Истина;
	Пока Флаг = Истина  Цикл
		Хл = b - (b-a)/K;
		Хп = a + (b-a)/K;
	    Если Функция_3(Хл) >= Функция_3(Хп) Тогда
			a = Хл;
		Иначе
			b = Хп;
		КонецЕсли;
		Если МодульМ(b-a) < Точность Тогда
			Прервать;				
		КонецЕсли;
	КонецЦикла;	
	Возврат Окр(0.5*(a+b), 10);
КонецФункции

Вспомогательная функция получения модуля:

Функция МодульМ(Числ)
	Если Числ<0 Тогда
        Возврат (Числ * (-1));
    Иначе     
        Возврат (Числ);
    КонецЕсли;
КонецФункции

Результат вычислений:

Метод парабол	= 4,7566019087
Метод золотого сечения = 4,7566045089

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

оптимизация золотое сечение метод парабол экстремум

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

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

1 стартмани

09.06.2023    7460    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8837    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7803    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Famza 84 22.12.14 09:49 Сейчас в теме
2. Alien_job 190 22.12.14 11:32 Сейчас в теме
такое ощущение что народ собрался написать конфигурации "матлаб". Думаю, такие вещи на 1с не нужны
3. AlX0id 22.12.14 11:40 Сейчас в теме
(2) Alien_job,
Ок. Дорабатывайте формочки на предмет новых реквизитов. Но затем не жалуйтесь на отсутствие работы, так как 1С вылизала типовые конфы до неприличного блеска.
4. Alien_job 190 22.12.14 12:15 Сейчас в теме
(3) AlX0id, Для каждой задачи нужно применять соответствующий инструмент: дорабатывать формы - 1с, решать дифуры - матлаб. Проблемы с отсутствием работы рекомендую решать специализацией а не разного рода экспериментами с микроскопом.
5. Иной 23.12.14 00:03 Сейчас в теме
Не хочу придераться, но в конструкции
    Флаг = Истина;
    Пока Флаг = Истина  Цикл
       ...
        Если Чёто-там Тогда
            Прервать;                
        КонецЕсли;
    КонецЦикла;    
 
Показать

Не лучше ли писать
    Пока Истина  Цикл
        ...
        Если Чёто-там Тогда
            Прервать;                
        КонецЕсли;
    КонецЦикла;    

За красоту и оптимальность боремся же =), лишнее выделение памяти оно же лишнее?
8. Идальго 226 23.12.14 07:16 Сейчас в теме
(5) Иной, ага, я сперва так и написал, но так менее понятно новичкам. Там вообще-то есть более серьёзный недостаток - в методе парабол, из-за которого этот метод немного "допиливают".
19. Поручик 4670 26.12.14 09:00 Сейчас в теме
(5) Не хочу придираться, но "придираться" пишется через И во втором слоге, а ещё учишь, как жить надо.
6. Светлый ум 406 23.12.14 06:33 Сейчас в теме
Пошли лабораторные работы - в массу)
7. Идальго 226 23.12.14 07:13 Сейчас в теме
(6) Светлый ум, 1С это одна сплошная и нескончаемая лабораторная, по моему )).
9. RainyAugust22 265 23.12.14 13:12 Сейчас в теме
классная девка на аватарке статьи
увеличить картинку нельзя оказывается
TreeDogNight; bogdan_sukonnov; BabySG; DrAku1a; Lo1jke; OVladius; spectre1978; so-quest; Persempre; dj_serega; FilatovRA; myoker; Новиков; +13 Ответить
10. Идальго 226 23.12.14 13:30 Сейчас в теме
(9) RainyAugust22, хе-хе это не аватарка, а картинка для анонса. Я для будущих статей специально ещё насобирал ))). А увеличивать их да нельзя, а то слишком уж говорят вызывающие, хотя мне нравятся.
24. DrAku1a 1679 03.01.15 22:23 Сейчас в теме
(9) [ 18+ ] написать в яндекс-поиске-картинок "мисс училка" - и да пребудет с тобой сила )))
11. iov 406 23.12.14 17:19 Сейчас в теме
ну теперь заживем!!!!
А серьезно если , в каких практических задачах использовались эти алгоритмы?
12. Идальго 226 23.12.14 18:22 Сейчас в теме
(11) iov, ну собственно в любой задаче на одномерную оптимизацию. В этой статье такая рассмотрена и решена 3 методами (в т.ч. графически). Если говорить применительно к практическим задачам по 1С, то наверное тоже можно применить. Например к задачам, где надо найти оптимальный уровень чего-либо, а хоть бы и оптимальный уровень запаса, где общие издержки по хранению это функция от времени или от того же наличия запаса. Ну или как-то так. Почитайте литературу, поищите. Очень рекомендую книгу Таха по основам исследования операций.
13. Светлый ум 406 24.12.14 05:57 Сейчас в теме
(12) ценность как раз имеет не теория вроде этих функций, а её практическое применение. Набросай хоть один наглядный пример - подымем твою публикацию не раздумывая. ildarovich - http://infostart.ru/profile/28527/, такие штуки периодически выкладывает.. и сидишь потом смотришь, каким бедным арсеналом сам обладаешь.
14. Идальго 226 24.12.14 07:18 Сейчас в теме
(13) Светлый ум, это не теория в виде функций, а метод решения определенного класса задач. Т.е. теории нет вообще, хоть она и сравнительно проста и интересна. В начале статьи специально про это написано. Пример такой задачи в статье есть. Если вы не видите ценности, то это ваше дело. Проходите мимо да и делов. Как применять подобные методы именно в практике программирования 1С - подумаю над этим.
15. jobkostya1c_ERP 100 24.12.14 20:22 Сейчас в теме
В свое время тоже писали что угодно на делфи ради практики. Даже что-то подобное было более 2000 строк по пересечению кривых для гистерезиса. А все чтоб язык изучить. Знали бы что 1С пригодится на ней бы писали...Правда тут проблема с запуском :) Без платформы то никак :)
16. Mr.Rm 25.12.14 10:47 Сейчас в теме
(Числ * (-1))

Зачем?! Почему не просто
(-Числ)

17. Идальго 226 25.12.14 12:34 Сейчас в теме
(16) Mr.Rm, мне показалось, что так более читаемо. Так меньше вероятность пропустить минусик спереди.
18. hair 28 25.12.14 16:00 Сейчас в теме
функция для вычисления модуля числа легко заменяется выражением Макс(Число, -Число).
ildarovich; Valerich; eugeniezheludkov; +3 Ответить
20. Makushimo 160 30.12.14 06:49 Сейчас в теме
Вот не понимаю смысла этих статей.
Автор, не спеши посылать меня в даль -)))

Объясню.
Сидит некий просветленный чел, только что выдумал как решить на 1С узкий математический класс задач. Считает себя крутым и вытирает носом потолок.

А дай, думает, выложу, народ по-удивляю. Распирает же ж.
Но писать много букав лень. Он же много ночей не спал, книг... две прочитал. А может уродился весь такой гениальный. Нечего безграмотных обучать, захотят - сами эти же книги прочитают. Может что-то и поймут, хотя и не факт. Зато он по-прежнему будет умнее и круче всех.

Только какой смысл этой и подобных статей? Порисоваться?
Лови плюс в карму, ты красавчег -))) уважуха.

После анонса, где "теории опять нет", читать дальше не стал. Все равно не пойму ни тему ни область ее применения.

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

21. AlexWhite 194 30.12.14 08:48 Сейчас в теме
В картинках к публикации есть изображение

Ага, увидел аватарку, показалось, что это наша университетская преподавательница :-) Как сейчас, помню, вернулись с картошки, сидим в аудитории, ждем ботана-препода, который только что отчитал нам лекцию по матану на своем птичьем языке ("о чем поет страшнАя птица?") Но, вдруг, заходит длинноногая стройная блондинка - оказалось, что лекции читает один, практику другой преподаватель. Слышно было, как у парней бряцнули об стол отпавшие челюсти и в мыслях раздался шорох от массового скидывания с нее этого тесного красного платьишка с коротенькой юбочкой, кто-то сглотнул слюну, подумав: "Ну все, подкачуууу и стану великим математиком" (...закатились мечтательно глазки). А она с порога:
"Меня зовут Имя Отчество, мне 26 лет, у меня серьезный муж. Кто подумал, что сможет подкатить и сдать, забудьте! Я, в прошлом, студентка, знаю, кто, где, прячет шпоры - даже не думайте!" что-то типа того, в общем. Тот случай, когда понимаешь, что в человеке может быть все прекрасно, и тело, и ноги, и платье, и аналитический склад ума, и тончайшее притягательнейшее чувство юмора :-)
Курсовую по математике считал под ее руководством. Тема "решение дифференциальных уравнений методом Рунге-Кутта". Детали расчета давно забыл, но итерационный подход к решению много раз пригодился на практике. В армии - "перелет, недолет, точное попадание!" и в управлении распределенными программными проектами http://infostart.ru/public/318707/ :-)
22. hillsnake 35 30.12.14 12:00 Сейчас в теме
зачем это в 1С?

я знаю человека который написал в ALtera Учетную систему. Скажу честно выглядело убого.
но круто, hardware 1с такой.

23. Идальго 226 30.12.14 13:46 Сейчас в теме
зачем это в 1С?

А пусть будет. Оно никому не мешает )))
user596475_a.lutkov; +1 Ответить
25. Поручик 4670 11.01.15 19:41 Сейчас в теме
В общем-то, после прочтения учебника математики для 9-10 класса и вспоминания пройденного в школе материала, вопрос к автору только один - почему на аватаре публикации девушка выглядит как порядочная проститутка, а не добропорядочная учительница, сеющая разумное, доброе, вечное?
Оставьте свое сообщение