2
Оптимизация
Оптимизация – это поиск оптимального (наилучшего) варианта в заданных условиях.
Оптимальное решение – такое, при котором некоторая заданная функция (целевая функция) достигает минимума или максимума.
Постановка задачи:
целевая функция
ограничения, которые делают задачу осмысленной
(расходы, потери, ошибки)
(доходы, приобретения)
Задача без ограничений: построить дом
при минимальных затратах. Решение: не строить дом вообще.
3
Оптимизация
локальный минимум
глобальныйминимум
обычно нужно найти глобальный минимум
большинство численных методов находят только локальный минимум
минимум, который найдет Excel, зависит от выбора начального приближения («шарик на горке скатится в ближайшую ямку»)
4
Поиск минимума функции
1. Строим график функции (диаграмма «Точечная»)
2. Подготовка данных
начальное приближение
начальное приближение
целевая
ячейка
5
Поиск минимума функции
3. Надстройка «Поиск решения»
изменяемые ячейки:
E2
D2:D6
D2:D6; C5:C8
целевая
ячейка
ограничения
A1 <= 20
B2:B8 >= 5
A1 = целое
7
Оптимизация
Надстройка «Поиск решения» позволяет:
9
Восстановление зависимостей
Пары значений (аргумент-функция):
задают некоторую неизвестную функцию
Зачем:
какую?
11
Восстановление зависимостей
Корректная задача: найти функцию заданного вида, которая лучше всего соответствует данным.
Примеры:
линейная
полиномиальная
степенная
экспоненциальная
логарифмическая
12
Что значит «лучше всего соответствует»?
заданные пары значений
Метод наименьших квадратов (МНК):
чтобы складывать положительные значения
решение сводится к системе линейных уравнений (просто решать!)
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 не меняется и :
– среднее значение
24
Восстановление зависимостей
Сложные случаи (нестандартная функция):
Алгоритм:
выделить ячейки для хранения
построить ряд для тех же
построить на одной диаграмме ряды и
попытаться подобрать так, чтобы два графика были близки
вычислить в отдельной ячейке
функции: СУММКВРАЗН – сумма квадратов разностей рядов ДИСПР – дисперсия
Поиск решения:
26
Ряд данных и его свойства
Ряд данных – это упорядоченный набор значений
Основные свойства (ряд A1:A20):
количество элементов =СЧЕТ(A1:A20)
количество элементов, удовлетворяющих некоторому условию: = СЧЕТЕСЛИ(A1:A20;"<5")
минимальное значение =МИН(A1:A20)
максимальное значение =МАКС(A1:A20)
сумма элементов =СУММ(A1:A20)
среднее значение =СРЗНАЧ(A1:A20)
27
Дисперсия
Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ
Дисперсия («разброс») – это величина, которая характеризует разброс данных относительно среднего значения.
28
Дисперсия
среднее арифметическое
квадрат отклонения от среднего
средний квадрат отклонения от среднего значения
29
Дисперсия и СКВО
Стандартная функция
=ДИСПР(A1:A20)
Что неудобно:
Функции – Другие – Статистические
СКВО = среднеквадратическое отклонение
=СТАНДОТКЛОНП(A1:A20)
30
Взаимосвязь рядов данных
Два ряда одинаковой длины:
Вопросы:
31
Взаимосвязь рядов данных
Ковариация:
Как понимать это число?
увеличение приводит к увеличению
в среднем!
увеличение приводит к уменьшению
связь обнаружить не удалось
Что плохо?
32
Взаимосвязь рядов данных
Коэффициент корреляции:
– СКВО рядов и
безразмерный!
Как понимать это число?
=КОРРЕЛ(A1:A20;B1:B20)
33
Взаимосвязь рядов данных
Как понимать коэффициент корреляции?
Методы вычислений
Тема 6. Моделирование
34
© М.Е. Никитин, 2015-2016
(по мотивам учебника А.Г. Гейна и др., Информатика и ИКТ, 10 класс, М.: Просвещение, 2008)
35
– начальная численность
– после 1 цикла деления
– после 2-х циклов
Особенности модели:
Модель деления
36
– коэффициент рождаемости
– коэффициент смертности
Особенности модели:
Коэффициентприроста
прирост
Модель неограниченного роста (T. Мальтус)
37
Модель ограниченного роста (П. Ферхюльст)
L – предельная численность животных
Идеи:
39
Модель эпидемии гриппа
L – всего жителей Ni – больных в i-ый день
Zi – заболевших в i-ый день Vi – выздоровевших
Wi – всего выздоровевших за i дней
Основное уравнение:
Ограниченный рост:
Выздоровление (через 7 дней):
40
Влияние других видов
Ni – численность белок, Mi – численность бурундуков
K2, K4 – взаимное влияние
если K2 >K1 или K4 >K3 – враждующие виды
42
Модель системы «хищник-жертва»
Модель – не-система:
Модель – система:
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 минут
Клиенты в банке (исходные данные)
61
inMax := 10; { max число входящих за 1 мин }
Tmin := 1; { min время обслуживания }
Tmax := 5; { max время обслуживания }
L := 1000; { период моделирования в минутах }
M := 10; { допустимое время ожидания }
Задача: найти минимальное K, при котором время ожидания в 90% случаев не больше M минут.
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.