gifts2017

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

Опубликовал Михаил Гусев (Идальго) в раздел Программирование - Практика программирования

В статье приведены реализации на 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. В картинках к публикации есть изображение графика рассмотренной функции (синяя сплошная линия), а также графика её производной (пунктирная зеленоватая линия). Видно, что на рассматриваемом участке наша функция достигает локального экстремума как раз примерно в той точке, значения которой были вычислены.  

См. также

Подписаться Добавить вознаграждение

Комментарии

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

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

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

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

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

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

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

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

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

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

21. Александр Белов (AlexWhite) 30.12.14 08:48
В картинках к публикации есть изображение

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

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

23. Михаил Гусев (Идальго) 30.12.14 13:46
зачем это в 1С?

А пусть будет. Оно никому не мешает )))
user596475_a.lutkov; +1 Ответить
24. Андрей Акулов (DrAku1a) 03.01.15 22:23
(9) [ 18+ ] написать в яндекс-поиске-картинок "мисс училка" - и да пребудет с тобой сила )))
25. Сергей Ожерельев (Поручик) 11.01.15 19:41
В общем-то, после прочтения учебника математики для 9-10 класса и вспоминания пройденного в школе материала, вопрос к автору только один - почему на аватаре публикации девушка выглядит как порядочная проститутка, а не добропорядочная учительница, сеющая разумное, доброе, вечное?
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа