Михаил Евгеньевич Никитин

Презентация на тему «Методы вычислений. Оптимизация»

Материал опубликован 26 March 2021

Пояснительная записка к презентации

В процессе проектирования обычно поставлена задача определить лучшие, в некотором смысле, структуру или значения параметров объектов. Такая задача называется оптимизацией. Если оптимизация связана с расчетом оптимальных значений параметров в структуре объекта, это называется параметрической оптимизацией. Задача выбора оптимальной структуры-структурная оптимизация.

Таким образом, была сформулирована стандартная математическая задача оптимизации. Среди элементов χ, образующих множества Χ, найти такой элемент χ*, который доставляет минимальное значение f(χ*) данной функции f (χ). Чтобы правильно поставить задачу оптимизации, необходимо установить:

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

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

Классификация методов оптимизации

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

Методы оптимизации классифицируются в соответствии с задачами оптимизации:

* Локальные методы: приближаются к локальному экстремуму целевой функции. В случае унимодальной целевой функции этот экстремум является единственным и будет глобальным максимумом / минимумом.

* Глобальные методы: дело с многоэкстремальных целевых функций. В глобальном поиске основная задача-определить тенденции глобального поведения целевой функции.

В настоящее время существующие методы поиска можно разделить на три большие группы:

1. детерминированные;

2. случайные (стохастические);

3. смешанный.

Согласно критерию измерения допустимого набора, методы оптимизации подразделяются на методы одномерной оптимизации и методы многомерной оптимизации.

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

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

• В противном случае справиться с задачей нелинейного программирования и применять соответствующие методы. В свою очередь из них есть две частные задачи:

О если и-выпуклые функции, эта задача называется задачей выпуклого программирования;

О если, они имеют дело с задачей целевого (дискретного) программирования.

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

* прямые методы, требующие только расчетов целевой функции в точках масштабирования;

* методы первого порядка: требуется расчет первых частных производных функции;

* методы второго порядка: требуется расчет второго частного производного, т. е.ну. гессиан целевая функция.

Кроме того, методы оптимизации делятся на следующие группы:

* аналитические методы (например. метод мультипликаторов Лагранжа и условия Каруш-Кун-Такер);

* численные методы;

* графические методы.

В зависимости от характера набора х задачи математического программирования классифицируются как:

* задачи дискретного программирования-или комбинаторной оптимизации) - если Х курс или подсчет;

* целые задачи программирования — если Х является подмножеством набора целых чисел;

* нелинейные задачи программирования, если ограничения или целевая функция содержат нелинейные функции, а Х является подмножеством конечного векторного пространства.

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

Кроме того, разделы математического программирования-это параметрическое Программирование, динамическое программирование и стохастическое Программирование.

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

Способ найти крайность полностью определяется классом задачи. Но прежде чем вы получите математическую модель, вам нужно выполнить 4 этапа моделирования:

* Определение границ системы оптимизации

О Мы отвергаем эти ссылки на объект оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, или, точнее, те, без которых решение упрощено

* Выбор управляемых переменных

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

* Определение ограничений для управляемых переменных

о ... (равенство и / или неравенство)

* Выбор цифрового критерия оптимизации (например . показатель эффективности)

о создание целевой функции

Предварительный просмотр презентации

МЕТОДЫ ВЫЧИСЛЕНИЙ ТЕМА 3. ОПТИМИЗАЦИЯ <номер> © М.Е. Никитин, 2015-2016

<номер> Оптимизация Оптимизация – это поиск оптимального (наилучшего) варианта в заданных условиях. Оптимальное решение – такое, при котором некоторая заданная функция (целевая функция) достигает минимума или максимума. Постановка задачи: целевая функция ограничения, которые делают задачу осмысленной (расходы, потери, ошибки) (доходы, приобретения) Задача без ограничений: построить дом при минимальных затратах. Решение: не строить дом вообще.

<номер> Оптимизация локальный минимум глобальныйминимум обычно нужно найти глобальный минимум большинство численных методов находят только локальный минимум минимум, который найдет Excel, зависит от выбора начального приближения («шарик на горке скатится в ближайшую ямку»)

<номер> Поиск минимума функции 1. Строим график функции (диаграмма «Точечная») 2. Подготовка данных начальное приближение Зачем нужен график? ? начальное приближение целевая ячейка Изменение E2 должно влиять на F2! !

<номер> Поиск минимума функции 3. Надстройка «Поиск решения» изменяемые ячейки: E2 D2:D6 D2:D6; C5:C8 целевая ячейка ограничения A1 <= 20 B2:B8 >= 5 A1 = целое

<номер> Параметры оптимизации

<номер> Оптимизация Подбор параметра – это оптимизация? ? Надстройка «Поиск решения» позволяет: искать минимум и максимум функции использовать несколько изменяемых ячеек и диапазонов вводить ограничения (<=, >=, целое, двоичное) Как влияет ограничение «A1-целое» на сложность решения задачи? ?

МЕТОДЫ ВЫЧИСЛЕНИЙ ТЕМА 4. ВОССТАНОВЛЕНИЕ ЗАВИСИМОСТЕЙ <номер> © М.Е. Никитин, 2015-2016

<номер> Восстановление зависимостей Пары значений (аргумент-функция): задают некоторую неизвестную функцию Зачем: найти в промежу-точных точках (интерполяция) найти вне диапазона измерений (экстраполяция, прогнозирование) какую?

<номер> Какое решение нам нужно? Через заданный набор точек проходит бесконечно много разных кривых! ! Вывод: задача некорректна, поскольку решение неединственно.

<номер> Восстановление зависимостей Корректная задача: найти функцию заданного вида, которая лучше всего соответствует данным. Примеры: линейная полиномиальная степенная экспоненциальная логарифмическая График функции не обязательно проходит через заданные точки! ! Как выбрать функцию? ?

<номер> Что значит «лучше всего соответствует»? заданные пары значений Метод наименьших квадратов (МНК): Зачем возведение в квадрат? ? чтобы складывать положительные значения решение сводится к системе линейных уравнений (просто решать!)

<номер> МНК для линейной функции неизвестно! a -b c

<номер> Сопротивление проводника a -b Закон Ома R U A I ? Точки на линии: ?

<номер> Обработка результатов эксперимента Задача. В файле mnk.txt записаны в столбик 10 пар чисел (напряжение, ток), полученные в результате эксперимента с одним резистором. Найти (приближенно) его сопротивление по методу наименьших квадратов. Этапы решения: Прочитать данные из файла в массивы U и I. Вычислить и . Вычислить R*.

<номер> Работа с файлами: принцип сэндвича I этап. открыть файл : связать переменную f с файлом открыть файл (сделать его активным, приготовить к работе) Assign(f, 'mnk.txt'); Reset(f); {для чтения} Rewrite(f); {для записи} II этап: работа с файлом Переменная типа «текстовый файл»: var f: text; III этап: закрыть файл Close(f); Read ( f, n ); { ввести значение n } Write ( f, n ); { записать значение n } Writeln ( f, n );{c переходом на нов.строку }

<номер> Обработка результатов эксперимента var f: text; ... begin Assign(f, 'mnk.txt'); Reset(f); for k:=1 to 10 do begin Read(f, U[k], I[k]); Writeln(U[k]:0:3, ' ', I[k]:0:3); end; Close(f); end. Чтение данных: U, I: array[1..10] of real; k: integer; Какие переменные и массивы надо объявить? ?

<номер> Обработка результатов эксперимента var UU: real; ... UU := 0; for k:=1 to 10 do begin UU := UU + U[k]*U[k]; end; Вычисления: Что вычисляем? ? Как найти ? ? Как найти R*? ?

<номер> Задания «4»: Используя метод наименьших квадратов, найти приближенное значение сопротивления по данным файла mnk.txt. «5»: Сделать то же самое, предполагая, что в файле неизвестное количество пар значений, но не более 100. Цикл ввода должен выглядеть так: while not eof(f) do begin { читаем U[k] и I[k] } { тут еще что-то надо сделать } end; not eof(f) пока не достигнут конец файла (eof = end of file)

<номер> Коэффициент достоверности (Excel) заданные пары значений Крайние случаи: если график проходит через точки: если считаем, что y не меняется и : – среднее значение Фактически – метод наименьших квадратов! !

<номер> Восстановление зависимостей Диаграмма «График»: ПКМ

<номер> Восстановление зависимостей тип функции

<номер> Восстановление зависимостей Насколько хорошо выбрана функция? ? Что такое ? ? В диаграмме «График» для первой точки, для второй и т.д. !

<номер> Восстановление зависимостей Сложные случаи (нестандартная функция): Что делать? ? Алгоритм: выделить ячейки для хранения построить ряд для тех же построить на одной диаграмме ряды и попытаться подобрать так, чтобы два графика были близки вычислить в отдельной ячейке функции: СУММКВРАЗН – сумма квадратов разностей рядов ДИСПР – дисперсия Поиск решения: Это задача оптимизации! !

МЕТОДЫ ВЫЧИСЛЕНИЙ ТЕМА 5. СТАТИСТИКА <номер> © М.Е. Никитин, 2015-2016

<номер> Ряд данных и его свойства Ряд данных – это упорядоченный набор значений Основные свойства (ряд A1:A20): количество элементов =СЧЕТ(A1:A20) количество элементов, удовлетворяющих некоторому условию: = СЧЕТЕСЛИ(A1:A20;"<5") минимальное значение =МИН(A1:A20) максимальное значение =МАКС(A1:A20) сумма элементов =СУММ(A1:A20) среднее значение =СРЗНАЧ(A1:A20)

<номер> Дисперсия Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ В чем различие? ? Дисперсия («разброс») – это величина, которая характеризует разброс данных относительно среднего значения.

<номер> Дисперсия среднее арифметическое квадрат отклонения от среднего средний квадрат отклонения от среднего значения

<номер> Дисперсия и СКВО Стандартная функция =ДИСПР(A1:A20) Что неудобно: если измеряется в метрах, то – в м2 Функции – Другие – Статистические СКВО = среднеквадратическое отклонение =СТАНДОТКЛОНП(A1:A20) В каких единицах измеряется? ?

<номер> Взаимосвязь рядов данных Два ряда одинаковой длины: Вопросы: есть ли связь между этими рядами (соответствуют ли пары какой-нибудь зависимости ) насколько сильна эта связь?

<номер> Взаимосвязь рядов данных Ковариация: Если и – один и тот же ряд? ? Как понимать это число? если если если увеличение приводит к увеличению в среднем! увеличение приводит к уменьшению связь обнаружить не удалось Что плохо? единицы измерения: если в метрах, в литрах, то – в мл зависит от абсолютных значений и , поэтому ничего не говорит о том, насколько сильна связь

<номер> Взаимосвязь рядов данных Коэффициент корреляции: – СКВО рядов и Какова размерность? ? безразмерный! Как понимать это число? если : увеличение приводит к увеличению если : увеличение приводит к уменьшению если : связь обнаружить не удалось =КОРРЕЛ(A1:A20;B1:B20)

<номер> Взаимосвязь рядов данных Как понимать коэффициент корреляции? : очень слабая корреляция : слабая : средняя : сильная : очень сильная : линейная зависимость : линейная зависимость Если , то связи нет? ? Метод для определения линейной зависимости! !

МЕТОДЫ ВЫЧИСЛЕНИЙ ТЕМА 6. МОДЕЛИРОВАНИЕ <номер> © М.Е. Никитин, 2015-2016 (по мотивам учебника А.Г. Гейна и др., Информатика и ИКТ, 10 класс, М.: Просвещение, 2008)

<номер> – начальная численность – после 1 цикла деления – после 2-х циклов Особенности модели: не учитывается смертность не учитывается влияние внешней среды не учитывается влияние других видов Модель деления

<номер> – коэффициент рождаемости – коэффициент смертности Особенности модели: не учитывается влияние численности N и внешней среды на K не учитывается влияние других видов на K Коэффициент прироста прирост Модель неограниченного роста (T. Мальтус)

<номер> Модель ограниченного роста (П. Ферхюльст) L – предельная численность животных Идеи: коэффициент прироста KL зависит от численности N при N=0 должно быть KL=K (начальное значение) при N=L должно быть KL=0 (достигнут предел) Модель адекватна, если ошибка < 10%! !

<номер> Модель с отловом Примеры: рыбоводческое хозяйство, разведение пушных зверей и т.п. отлов Какая будет численность? ? , прирост = отлову Сколько можно отловить? ?

<номер> Модель эпидемии гриппа L – всего жителей Ni – больных в i-ый день Zi – заболевших в i-ый день Vi – выздоровевших Wi – всего выздоровевших за i дней Основное уравнение: Ограниченный рост: болели и выздоровели Выздоровление (через 7 дней):

<номер> Влияние других видов Ni – численность белок, Mi – численность бурундуков K2, K4 – взаимное влияние если K2 >K1 или K4 >K3 – враждующие виды Откуда видно влияние? ?

<номер> Моделирование двух популяций Как скопировать формулы «вниз»? ?

<номер> Модель системы «хищник-жертва» Модель – не-система: караси щуки вымирают без еды Модель – система: число встреч пропорционально NiZi «эффект» пропорционален числу встреч численность уменьшается численность увеличивается

<номер> Модель системы «хищник-жертва» Хищники вымирают: Равновесие: караси щуки

<номер> Модель системы «хищник-жертва» Колебания:

<номер> Случайные процессы Случайно… встретить друга на улице разбить тарелку найти 10 рублей выиграть в лотерею Случайный выбор: жеребьевка на соревнованиях выигравшие номера в лотерее Как получить случайность?

<номер> Случайные числа на компьютере Электронный генератор нужно специальное устройство нельзя воспроизвести результаты 318458191041 564321 209938992481 458191 938992 малый период (последовательность повторяется через 106 чисел) Метод середины квадрата (Дж. фон Нейман) в квадрате Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

<номер> Случайные числа на компьютере Линейный конгруэнтный метод a, c, m - целые числа простое число 230-1 период m Какой период? ? остаток от деления «Вихрь Мерсенна»: период 219937-1

<номер> Распределение случайных чисел Модель: снежинки падают на отрезок [a,b] a b a b распределение равномерное неравномерное Сколько может быть разных распределений? ?

<номер> Распределение случайных чисел Особенности: распределение – это характеристика всей последовательности, а не одного числа равномерное распределение одно, компьютерные датчики (псевдо)случайных чисел дают равномерное распределение неравномерных – много любое неравномерное можно получить с помощью равномерного a b a b равномерное распределение

<номер> Вычисление площади (метод Монте-Карло) Вписываем сложную фигуру в другую фигуру, для которой легко вычислить площадь (прямоугольник, круг, …). Равномерно N точек со случайными координатами внутри прямоугольника. Подсчитываем количество точек, попавших на фигуру: M. 4. Вычисляем площадь: Всего N точек На фигуре M точек Метод приближенный. Распределение должно быть равномерным. Чем больше точек, тем точнее. Точность ограничена датчиком случайных чисел. !

<номер> Вычисление площади Когда точка внутри круга? (x,y) Случайные координаты: x := R*random; y := R*random; Программа: for i:=1 to N do begin { найти случайные координаты } if x*x + y*y <= R*R then M := M+1; end; S := 4*R*R*M / N; Как найти число ? ?

<номер> Задания «4»: Вычислите площади кругов c радиусами R = 1, 2, 3, 4, 5. Используя электронные таблицы, найдите приближенную формулу для вычисления площади круга. «5»: Вычислите объем шаров c радиусами R = 1, 2, 3, 4, 5. Используя электронные таблицы, найдите приближенную формулу для вычисления объема шара.

<номер> Броуновское движение Случайный шаг: Случайное направление (в рад): alpha := 2*pi*random; h := hMax*random; Программа: for i:=1 to N do begin { найти случайное направление и шаг } x := x + h*cos(alpha); y := y + h*sin(alpha); end;

<номер> Графика (АЛГО) Задать цвет линии: Начальное положение частицы: x:= 200; y:= 250; MoveTo(round(x), round(y)); Pen(1, 0, 255, 0); Движение частицы: for i:=1 to N do begin { определить новые координаты } LineTo(round(x), round(y)); end; толщина линии R(red) 0..255 G(green) 0..255 B(blue) 0..255

Задания <номер> «4»: Постройте траектории движения двух частиц в течение 200 шагов. Частицы должны двигаться одновременно. «5»: Постройте траектории движения 10 частиц в течение 200 шагов. Частицы должны двигаться одновременно. Используйте массивы для хранения координат частиц.

<номер> Системы массового обслуживания Примеры: звонки на телефонной станции вызовы «скорой помощи» обслуживание клиентов в банке сколько бригад? сколько линий? сколько операторов? Особенности: клиенты (запросы на обслуживание) поступают постоянно, но через случайные интервалы времени время обслуживание каждого клиента – случайная величина Нужно знать характеристики (распределения) «случайностей»! !

<номер> Клиенты в банке Вход клиентов: за 1 минуту – до Imax человек равномерное распределение Обслуживание: от Tmin до Tmax минут равномерное распределение Сколько нужно касс, чтобы клиенты стояли в очереди не более М минут? ?

<номер> Клиенты в банке Число клиентов в помещении банка: N := N + in - out; было пришли ушли Допущение: клиенты распределены по кассам равномерно! ! Количество касс: K Средняя длина очереди: Допустимая длина очереди: Q – длина очереди Время ожидания:

<номер> Клиенты в банке Пришли за очередную минуту: in := round(inMax*random); округление Обслужены за очередную минуту и выходят: Случайное время обслуживания: T := Tmin + (Tmax – Tmin)*random; Каждый оператор за эту минуту обслужит клиентов! ! out := round(K / T);

<номер> Клиенты в банке (программа) count := 0; { счетчик «плохих» минут } for i:=1 to L do begin in := { случайное число входящих } out := { случайное число обслуженных } N := N + in – out; if N/K > Qmax then count := count + 1; end; writeln(count/L:10:2); Что выводится? ? период моделирования L минут

Скачать оригинальную презентацию

в формате MS Powerpoint (.ppt / .pptx)

Теги публикации