Слайд 2
Оптимизация
Оптимизация – это поиск оптимального (наилучшего) варианта в
заданных условиях.
Оптимальное решение – такое, при котором некоторая заданная
функция (целевая функция) достигает минимума или максимума.
Постановка задачи:
целевая функция
ограничения, которые делают задачу осмысленной
(расходы, потери, ошибки)
(доходы, приобретения)
Задача без ограничений: построить дом
при минимальных затратах.
Решение: не строить дом вообще.
Слайд 3
Оптимизация
локальный минимум
глобальныйминимум
обычно нужно найти глобальный минимум
большинство численных методов
находят только локальный минимум
минимум, который найдет Excel, зависит от
выбора начального приближения («шарик на горке скатится в ближайшую ямку»)
Слайд 4
Поиск минимума функции
1. Строим график функции (диаграмма «Точечная»)
2.
Подготовка данных
начальное приближение
начальное приближение
целевая
ячейка
Слайд 5
Поиск минимума функции
3. Надстройка «Поиск решения»
изменяемые ячейки:
E2
D2:D6
D2:D6; C5:C8
целевая
ячейка
ограничения
A1
= 5
A1 = целое
Слайд 7
Оптимизация
Надстройка «Поиск решения» позволяет:
искать минимум и максимум функции
использовать
несколько изменяемых ячеек и диапазонов
вводить ограничения (=, целое,
двоичное)
Слайд 8
МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 4. ВОССТАНОВЛЕНИЕ
ЗАВИСИМОСТЕЙ
© М.Е. Никитин, 2015-2016
Слайд 9
Восстановление зависимостей
Пары значений (аргумент-функция):
задают некоторую неизвестную функцию
Зачем:
найти
в промежу-точных точках
(интерполяция)
найти вне диапазона
измерений
(экстраполяция,
прогнозирование)
какую?
Слайд 10
Какое решение нам нужно?
Вывод: задача некорректна, поскольку решение
неединственно.
Слайд 11
Восстановление зависимостей
Корректная задача: найти функцию заданного вида,
которая
лучше всего соответствует данным.
Примеры:
линейная
полиномиальная
степенная
экспоненциальная
логарифмическая
Слайд 12
Что значит «лучше всего соответствует»?
заданные пары значений
Метод наименьших
квадратов (МНК):
чтобы складывать положительные значения
решение сводится к системе линейных
уравнений (просто решать!)
Слайд 13
МНК для линейной функции
неизвестно!
a
-b
c
Слайд 14
Сопротивление проводника
a
-b
Закон Ома
R
U
A
I
?
Точки на линии:
?
Слайд 15
Обработка результатов эксперимента
Задача. В файле mnk.txt записаны в
столбик 10 пар чисел (напряжение, ток), полученные в результате
эксперимента с одним резистором. Найти (приближенно) его сопротивление по методу наименьших квадратов.
Этапы решения:
Прочитать данные из файла в массивы U и I.
Вычислить и .
Вычислить R*.
Слайд 16
Работа с файлами: принцип сэндвича
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 переходом на нов.строку }
Слайд 17
Обработка результатов эксперимента
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;
Слайд 18
Обработка результатов эксперимента
var UU: real;
...
UU := 0;
for k:=1
to 10 do begin
UU := UU + U[k]*U[k];
end;
Вычисления:
Слайд 19
Задания
«4»: Используя метод наименьших квадратов, найти приближенное значение
сопротивления по данным файла mnk.txt.
«5»: Сделать то же самое,
предполагая, что в файле неизвестное количество пар значений, но не более 100. Цикл ввода должен выглядеть так:
while not eof(f) do begin
{ читаем U[k] и I[k] }
{ тут еще что-то надо сделать }
end;
not eof(f)
пока не достигнут конец файла (eof = end of file)
Слайд 20
Коэффициент достоверности (Excel)
заданные пары значений
Крайние случаи:
если график проходит
через точки:
если считаем, что y не меняется и
:
– среднее значение
Слайд 21
Восстановление зависимостей
Диаграмма «График»:
ПКМ
Слайд 24
Восстановление зависимостей
Сложные случаи (нестандартная функция):
Алгоритм:
выделить ячейки для хранения
построить
ряд
для тех же
построить на одной диаграмме ряды и
попытаться подобрать так, чтобы
два графика были близки
вычислить в отдельной ячейке
функции: СУММКВРАЗН – сумма квадратов разностей рядов
ДИСПР – дисперсия
Поиск решения:
Слайд 25
МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 5. СТАТИСТИКА
© М.Е. Никитин, 2015-2016
Слайд 26
Ряд данных и его свойства
Ряд данных – это
упорядоченный набор значений
Основные свойства (ряд A1:A20):
количество элементов =СЧЕТ(A1:A20)
количество элементов,
удовлетворяющих некоторому условию:
= СЧЕТЕСЛИ(A1:A20;"<5")
минимальное значение =МИН(A1:A20)
максимальное значение =МАКС(A1:A20)
сумма элементов =СУММ(A1:A20)
среднее значение =СРЗНАЧ(A1:A20)
Слайд 27
Дисперсия
Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ
Дисперсия («разброс»)
– это величина, которая характеризует разброс данных относительно среднего
значения.
Слайд 28
Дисперсия
среднее арифметическое
квадрат отклонения от среднего
средний квадрат отклонения от
среднего значения
Слайд 29
Дисперсия и СКВО
Стандартная функция
=ДИСПР(A1:A20)
Что неудобно:
если измеряется
в метрах,
то – в
м2
Функции – Другие – Статистические
СКВО = среднеквадратическое отклонение
=СТАНДОТКЛОНП(A1:A20)
Слайд 30
Взаимосвязь рядов данных
Два ряда одинаковой длины:
Вопросы:
есть ли связь
между этими рядами (соответствуют ли пары
какой-нибудь зависимости )
насколько сильна эта связь?
Слайд 31
Взаимосвязь рядов данных
Ковариация:
Как понимать это число?
если
если
если
увеличение приводит к увеличению
в
среднем!
увеличение приводит к уменьшению
связь обнаружить не удалось
Что плохо?
единицы измерения: если в метрах, в литрах,
то – в м⋅л
зависит от абсолютных значений и , поэтому ничего не говорит о том, насколько сильна связь
Слайд 32
Взаимосвязь рядов данных
Коэффициент корреляции:
– СКВО рядов
и
безразмерный!
Как понимать это число?
если
: увеличение приводит к увеличению
если : увеличение приводит к уменьшению
если : связь обнаружить не удалось
=КОРРЕЛ(A1:A20;B1:B20)
Слайд 33
Взаимосвязь рядов данных
Как понимать коэффициент корреляции?
: очень
слабая корреляция
: слабая
: средняя
: сильная
: очень сильная
: линейная зависимость
: линейная зависимость
Слайд 34
МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 6. МОДЕЛИРОВАНИЕ
© М.Е. Никитин, 2015-2016
(по мотивам
учебника А.Г. Гейна и др., Информатика и ИКТ,
10
класс, М.: Просвещение, 2008)
Слайд 35
– начальная численность
– после 1 цикла деления
– после
2-х циклов
Особенности модели:
не учитывается смертность
не учитывается влияние внешней среды
не
учитывается влияние других видов
Модель деления
Слайд 36
– коэффициент рождаемости
– коэффициент смертности
Особенности модели:
не учитывается влияние
численности N и внешней среды на K
не учитывается влияние
других видов на K
Коэффициент
прироста
прирост
Модель неограниченного роста (T. Мальтус)
Слайд 37
Модель ограниченного роста (П. Ферхюльст)
L – предельная численность
животных
Идеи:
коэффициент прироста KL зависит от численности N
при N=0
должно быть KL=K (начальное значение)
при N=L должно быть KL=0 (достигнут предел)
Слайд 38
Модель с отловом
Примеры: рыбоводческое хозяйство, разведение пушных зверей
и т.п.
Слайд 39
Модель эпидемии гриппа
L – всего жителей Ni – больных
в i-ый день
Zi – заболевших в i-ый день Vi –
выздоровевших
Wi – всего выздоровевших за i дней
Основное уравнение:
Ограниченный рост:
Выздоровление
(через 7 дней):
Слайд 40
Влияние других видов
Ni – численность белок, Mi –
численность бурундуков
K2, K4 – взаимное влияние
если K2 >K1 или
K4 >K3 – враждующие виды
Слайд 42
Модель системы «хищник-жертва»
Модель – не-система:
Модель – система:
число встреч
пропорционально Ni⋅Zi
«эффект» пропорционален числу встреч
Слайд 43
Модель системы «хищник-жертва»
Хищники вымирают:
Равновесие:
караси
щуки
Слайд 44
Модель системы «хищник-жертва»
Колебания:
Слайд 45
Случайные процессы
Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть
в лотерею
Случайный выбор:
жеребьевка на
соревнованиях
выигравшие номера
в лотерее
Как получить
случайность?
Слайд 46
Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести
результаты
318458191041
564321
209938992481
458191
938992
малый период
(последовательность повторяется через 106 чисел)
Метод середины квадрата
(Дж. фон Нейман)
в квадрате
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.
Слайд 47
Случайные числа на компьютере
Линейный конгруэнтный метод
a, c, m
- целые числа
простое число
230-1
период m
остаток от деления
«Вихрь Мерсенна»: период
219937-1
Слайд 48
Распределение случайных чисел
Модель: снежинки падают на отрезок [a,b]
распределение
равномерное
неравномерное
Слайд 49
Распределение случайных чисел
Особенности:
распределение – это характеристика всей
последовательности, а не одного числа
равномерное распределение одно, компьютерные датчики
(псевдо)случайных чисел дают равномерное распределение
неравномерных – много
любое неравномерное можно получить с помощью равномерного
a
b
a
b
Слайд 50
Вычисление площади (метод Монте-Карло)
Вписываем сложную фигуру в другую
фигуру, для которой легко вычислить площадь (прямоугольник, круг, …).
Равномерно N точек со случайными координатами внутри прямоугольника.
Подсчитываем количество точек, попавших на фигуру: M.
4. Вычисляем площадь:
Всего N точек
На фигуре M точек
Метод приближенный.
Распределение должно быть равномерным.
Чем больше точек, тем точнее.
Точность ограничена датчиком случайных чисел.
!
Слайд 51
Вычисление площади
Когда точка внутри круга?
(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;
Слайд 52
Задания
«4»: Вычислите площади кругов c радиусами
R
= 1, 2, 3, 4, 5.
Используя электронные таблицы,
найдите приближенную формулу для вычисления площади круга.
«5»: Вычислите объем шаров c радиусами
R = 1, 2, 3, 4, 5.
Используя электронные таблицы, найдите приближенную формулу для вычисления объема шара.
Слайд 53
Броуновское движение
Случайный шаг:
Случайное направление (в рад):
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;
Слайд 54
Графика (АЛГО)
Задать цвет линии:
Начальное положение частицы:
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
Слайд 55
Задания
«4»: Постройте траектории движения двух частиц в течение
200 шагов. Частицы должны двигаться одновременно.
«5»: Постройте траектории
движения 10 частиц в течение 200 шагов. Частицы должны двигаться одновременно. Используйте массивы для хранения координат частиц.
Слайд 56
Системы массового обслуживания
Примеры:
звонки на телефонной станции
вызовы «скорой помощи»
обслуживание
клиентов в банке
сколько бригад?
сколько линий?
сколько операторов?
Особенности:
клиенты (запросы на обслуживание)
поступают постоянно, но через случайные интервалы времени
время обслуживание каждого клиента – случайная величина
Слайд 57
Клиенты в банке
Вход клиентов:
за 1 минуту – до
Imax человек
равномерное распределение
Обслуживание:
от Tmin до Tmax минут
равномерное распределение
Слайд 58
Клиенты в банке
Число клиентов в помещении банка:
N :=
N + in - out;
было
пришли
ушли
Количество касс: K
Средняя длина очереди:
Допустимая
длина очереди:
Q – длина очереди
Время ожидания:
Слайд 59
Клиенты в банке
Пришли за очередную минуту:
in := round(inMax*random);
округление
Обслужены
за очередную минуту и выходят:
Случайное время обслуживания:
T := Tmin
+ (Tmax – Tmin)*random;
out := round(K / T);
Слайд 60
Клиенты в банке (программа)
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 минут
![Распределение случайных чиселМодель: снежинки падают на отрезок [a,b]распределениеравномерноенеравномерное](/img/tmb/13/1218224/d1e6825bf55c072f6d4d66f076aaccf7-720x.jpg "Методы вычислений. Оптимизация")
