Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Численные методы оптимизации



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

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

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

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



.

Для заданного расхода воды перепад давления можно выразить через диаметр трубы

.

Потребляемая энергия будет равна

.

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

.

Затраты, обусловленные потерями тепла в трубах, примерно пропорциональны величине этих потерь, которые равны

,

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

.

Будем считать, что стоимость трубы пропорциональна ее диаметру .

Стоимость теплоизоляции приближенно пропорциональна ее толщине .

Таким образом, общие затраты можно выразить в следующей форме:

.

Для минимизации этой функции затрат можно регулировать два параметра: D и х. Задача состоит в нахождении значений D и х, при которых затраты минимальны. Допустим, что постоянные имеют сле­дующие значения:

.

Тогда затраты можно выразить так: .

Чтобы использовать этот метод, необходимо найти начальную точку. В данном случае . Теперь, сохраняя значение постоянным, изменяем до тех пор, пока не будет найдено оптимальное значение. Если мы используем шаг 0,2, этим значением оказывается D=1,8. (На данном этапе не имеет смысла выполнять вычисления с большей точностью.) Теперь при D=1,8 параметр х изменяется до тех пор, пока не будет достигнуто новое оптимальное значение x1=1,25, и т. д. Результаты этих расчетов, выполненных на вычислительной машине, показали, что окончательным результатом является D=1,85 и x=1,37. Таким образом, выберем трубу с внутренним диаметром около 1,85 см и задать толщину тепловой изоляции около 1,37 см.



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

Рис. 5

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

и .

В обоих случаях коэффициент пропорциональности один и тот же. На рис. 5 показано направление движения, но не показано, насколько нужно продвигаться. Коэффициент пропорциональности в этих двух уравнениях еще не определен. Желательно двигаться в этом новом направлении до тех пор, пока функция U не обратится в нуль или не уменьшится. (В этой точке производится поиск нового направления наискорейшего спуска, и процесс повторяется.) Пусть коэффициент пропорциональности равен у.

После перемещения на расстояние, соответствующее у, значения параметров становятся приближенно равными

,

и целевой функцией будет .

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

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

Вывод

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

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!