Уважаемые посетители Портала Знаний, если Вы найдете ошибку в тексте, выделите, пожалуйста, ее мышью и нажмите Сtrl+Enter. Мы обязательно исправим текст!


Случайная цитата


Свои способности человек может узнать, только попытавшись приложить их. (Сенека)

Оптимизация. Обзор методов

Оптимизация - важный раздел современной прикладной математики, объединяющий широкий спектр разнообразный методов, позволяющих решать важные  практические задачи.

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

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

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

Имеется несколько важных принципов, которые нужно знать и с пользой применять на практике, например, принцип оптимальности Беллмана или принцип оптимальности Понтрягина и др.

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

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

Начнем с практического вопроса.

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

Естественно рассмотреть наклонный пандус, который позволяет за оптимальное время скатывать предметы с верхних этажей на нижние.

Задача о брахистохроне (линии наибыстрейшего ската).

Термин брахистохрон имеет греческое происхождение и состоит из двух слов хронос – время, брахисто – самый короткий (βραχιστoζ – короткий, χρoνoζ – время).

Формальная постановка задачи такая.

В вертикальной плоскости даны точки A и B. Определить путь, по которому под действием собственной тяжести, тело, начав двигаться из точки A, достигнет точку B за кратчайшее время.

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

Рассматривается идеальный случай, предмет скатывается только под действием силы тяжести.

Прежде всего мы можем предположить, что нам достаточно провести прямую линию, соединяющую точки А и В.

Отрезок прямой будет кратчайшим расстоянием между А и В, однако не факт, что время, затраченное на движение по этому отрезку будет наименьшим.

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

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

Продолжим рассуждения.

Введем декартову систему координат с центром в точке А, пусть точка В располагается, для определенности, в 4-м квадранте, ее координаты x1 > 0, y1 < 0.

Конечно, возможно симметричное расположение точки В относительно оси y, но мы рассмотрим именно этот случай.

Если точка В лежит просто на оси y, то решение очевидно, это отрезок прямой (0, y1).

Проведем какую-то линию, соединяющую точки А и В, обозначим ее y = y(x).

Всякой линии y = y(x), соединяющей точки А и В, сопоставим время спуска T по этой линии.

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

Заметим, что в начальный момент времени t = 0, y(0) = 0 (тело находится в точке А), в момент окончания спуска тело попадает в точку В, следовательно, y(T) = y1.

Итак, формально нам нужно перебрать все линии, соединяющие А и В, и найти оптимальную линию, для которой время Т минимально.

Это и будет линия наискорейшего спуска.

Вопрос: как это сделать?

Воспользуемся символистикой математического анализа.

Формально скорость скатывания тела по дуге определяется выражением

Отсюда:

Время спуска Т по всей линии вычисляется как сумма

=

Интеграл берется по кривой .

Линия задана в явном виде как функция от , поэтому можно считать, что интегрирование ведется от 0 до .

Дифференциал дуги можно вычислить (проделайте это упражнение или обратитесь к стандартной книге по математическому анализу)

Итак, время спуска по кривой задается выражением:

(1)

В этом выражении присутствует скорость тела , ее нужно найти.

Попадая в точку по оси х, тело проходит по оси y расстояние , закон сохранения энергии дает равенство:

В начальный момент времени скорость и высота равны 0, следовательно, поэтому:

(2)

Подставляя формулу (2) в формулу (1), имеем окончательное выражение для времени движения по нашей линии :

(3)

 

Итак, формально нужно найти минимум функционала (3) на кривых удовлетворяющих условию:

Следующие калькуляции потребуют некоторого напряжения, хотя идея простая.

Нам удобно ввести обозначение для подынтегральной функции в (3).

Обозначим:

Принцип Эйлера утверждает, что экстремальное значение функционала

является решением уравнения:

= с (4)

это частная производная по ,

Следовательно, формально имеем:

(5)

Подставим (5) в (4) и проведем алгебраические преобразования.

После возведения в квадрат имеем выражение через :

(6)

Данное дифференциальное уравнение можно решить, формально имеем:

(7)

Проинтегрируем левую и правую часть (7), получим:

(8)

Для сокращения калькуляций обозначим новая константа, сделаем стандартную замену переменных:

После элементарных вычислений (проделайте их!) получим следующие уравнения линии :

(9)

 

(10)

Константу нужно подобрать так, чтобы кривая проходила через конечную точку В с координатами .

Как пользоваться этими уравнениями?

Достаточно просто, это время, представьте, вы выбрали константу например, положив далее берем последовательные значения = 0, 0.1 и тд.

На рисунке ниже показана одна такая кривая:

Рис. 1

С помощью уравнений (9), (10) мы можем определить положение тела, двигающегося под действием силы тяжести по линии наискорейшего спуска, в любой момент времени.

Уравнения (9), (10) позволяют определить пару констант t1, c1 и тем самым определить отрезок кривой кратчайшего спуска между точками А и В.

Эта замечательная кривая называется циклоидой!

Эта кривая относится к классу трансцендентных кривых, уравнение которых не может быть записано в виде многочленов от x, y, однако параметрические уравнений (9), (10) позволяют исследовать эту кривую и вывести ее замечательные свойства.

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

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

Заметьте, важен принцип рассуждения, вначале мы поняли, что решение может быть отличным от прямой линии, затем формализовали задачи и использовали математическую символику, позволяющую записать решение в виде уравнений (9), (10).

Конечно, это задача имеет много вариаций, можно рассматривать движение частицы в поле действия определенных сил, движение луча в неоднородной среде и тд.

Обсуждение задачи.

Мы свели задачу о линии кратчайшего времени спуска к нахождению экстремума некоторого функционала

Термина функционал не нужно бояться, это то же самое что функция, только немного сложнее, его значение зависит от самой линии и ее производной

Возникает вопрос, как находить экстремумы функционалов, например, минимальные или максимальные значения.

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

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

Это естественное обобщение достигается с помощью принципа Эйлера.

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

является решением уравнения:

= с

Имеется множество численных методов поиска экстремума функций, очевидно, эти методы можно распространить и на поиск экстремумов функционалов.

Приведем несколько задач на брахистохрону:

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

Объясните, почему выпуклая вверх циклоида, симметричная относительно прямой АВ, не является брахистохроной.

Ограничим возможные кривые только ломаными линиями, рассмотрим различные ломанные линии, соединяющие точки А и В. Как нужно расположить N точек А, , N > 1 чтобы ломаная линия была линией наикратчайшего спуска. Какой принцип оптимальности здесь можно применить? Заметьте, что в точках излома отсутствуют производные.

Дальнейшие задачи для самостоятельных размышлений:

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

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

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

Для этого, прежде всего, введите декартову систему координат и запишите функционал, экстремум которого нужно найти.

Далее примените принцип Эйлера для нахождения экстремума и проведите математические выкладки.

Визуализация брахистохроны

Изобразим графически задачу наискорейшего спуска, чтобы наглядно убедиться в том, что материальная точка быстрее спустится именно по брахистохроне, а не по прямой. Для этого напишем небольшой макрос в Microsoft Excel во встроенной среде разработки Visual basic for Application (VBA).

Для начала сделаем некоторую предварительную подготовку: построим графики брахистохроны и прямой в Microsoft Excel. Согласно теории, уравнение брахистохроны в декартовых координатах имеет вид:

Введем в первый столбец рабочего листа цифры от 0 до 2 с шагом 0.1.

Рис. 2

Во второй столбец введем следующую формулу и растянем ее на 22 строки:

Рис. 3

В итоге получим следующие данные:

Рис. 4

Теперь займемся построением прямой, с которой будем сравнивать брахистохрону. Мы знаем, что данная прямая должна проходить через точки (0;0) и (2; 3.14). Воспользуемся уравнением прямой по двум точкам:

Решаем уравнение:

Получаем уравнение прямой: y = 1.57x

Теперь вбиваем в третий столбец следующую формулу, и растягиваем ее на 22 строки:

Рис. 5

Получаем в итоге:

Рис. 6

Построим точечный график по имеющимся столбцам. Для этого выделим прямоугольную область A1:С22, затем выберем пункт меню Вставить -> Диаграмма -> Точечная.

Рис. 7

В результате у нас должен получиться следующий график:

Рис. 8

Теперь займемся созданием шариков, которые будут скатываться по нашим кривым. Начальное положение шариков уже известно, это точка (2; 3.14). Чтобы шарики красиво, реалистично скатывались, сделаем координату по Oy немного побольше, чтобы шарики не были «нанизаны» на кривые, а находились на их поверхности.

Сделаем следующую табличку для координат шариков на брахистохроне (шарик БР) и на прямой (шарик ПР).

Рис. 9

Кликнем правой кнопкой мыши на графике, выберем пункт «Выбрать данные».

Рис. 10

Затем нажмем «Добавить ряд», в названии укажем «Шарик БР», в поле «Значения Х» укажем ячейку F2, в поле «Значения Y» укажем ячейку G2.

Рис. 11

 

Рис. 12

Аналогичным образом добавим шарик на прямой (ячейки будут соответственно H2 и I2).

Чтобы кривые были более красивыми и цельными, изменим тип диаграмм. Кликнем правой кнопкой мыши на кривой брахистохроны и прямой, выберем пункт «Изменить тип диаграммы для ряда…»:

Рис. 13

И в том же меню Диаграмма -> Точечная, выберем третий по счету вид (Точечная с гладкими кривыми):

Рис. 14

Получим такой график:

Рис. 15

На следующем этапе сделаем наши шарики более круглыми и объемными. Нажмем на один из них правой кнопкой мыши, выберем «Формат ряда данных».

Рис. 16

В следующем меню сделаем настройки:

Рис. 17

 

Рис. 18

Аналогичным образом сделаем синий объемный шарик на брахистохроне. Получим такой вид:

Рис. 19

Теперь напишем макрос на VBA, который будет управлять нашими шариками. Нажмем Alt+F11, и перейдем в среду разработки VBA. В приложении приведен подробный листинг макроса с комментариями.

А вот и результат нашей работы:

Рис. 20

Приложение

Sub Лист3_Кнопка1_Щелчок()

Dim BrahY(22), BrahX(22) As Double

Dim i As Double

Cells(2, 6) = 2 'начальное положение шариков

Cells(2, 7) = 3.3

Cells(2, 8) = 2

Cells(2, 9) = 3.3

BrahX(1) = 1.9 'координаты Х брахистохроны

BrahX(2) = 1.8

BrahX(3) = 1.7

BrahX(4) = 1.6

BrahX(5) = 1.5

BrahX(6) = 1.4

BrahX(7) = 1.3

BrahX(8) = 1.2

BrahX(9) = 1.1

BrahX(10) = 1

BrahX(11) = 0.8

BrahX(12) = 0.7

BrahX(13) = 0.6

BrahX(14) = 0.5

BrahX(15) = 0.3

BrahX(16) = 0.18

BrahX(17) = 0.12

BrahX(18) = 0.08

BrahX(19) = 0.04

BrahX(20) = 0.015

BrahX(21) = 0

BrahX(22) = 0

BrahY(1) = 3.141592654 ' координаты Y брахистохроны

BrahY(2) = 2.254675947

BrahY(3) = 1.898091545

BrahY(4) = 1.632050981

BrahY(5) = 1.414297436

BrahY(6) = 1.28369699

BrahY(7) = 1.05798034

BrahY(8) = 0.921549779

BrahY(9) = 0.79235835

BrahY(10) = 0.675976311

BrahY(11) = 0.570796327

BrahY(12) = 0.475641469

BrahY(13) = 0.389642509

BrahY(14) = 0.312164471

BrahY(15) = 0.242764342

BrahY(16) = 0.181172147

BrahY(17) = 0.127295218

BrahY(18) = 0.081255987

BrahY(19) = 0.043501109

BrahY(20) = 0.015136917

BrahY(21) = 0

BrahY(22) = 0

Application.Wait (Now + TimeValue("0:00:1"))

For i = 0 To 2.2 Step 0.1 ' в цикле меняем координаты шариков

Cells(2, 6) = BrahX(i * 10 + 1)

Cells(2, 7) = BrahY(i * 10 + 1)

Cells(2, 8) = 2.2 - i

Cells(2, 9) = 1.57 * (2.2 - i) + 0.22 'немножко поднимаем шарик над прямой

Application.Wait (1000)

Next i

Application.Wait (Now + TimeValue("0:00:2"))

Cells(2, 6) = 2

Cells(2, 7) = 3.3

Cells(2, 8) = 2

Cells(2, 9) = 3.3

End Sub


В начало

Содержание портала