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

Оптимизация – это поиск оптимального (наилучшего) варианта в заданных условиях.

Оптимальное решение – такое, при котором некоторая заданная функция (целевая функция) достигает минимума или максимума.

Постановка задачи:
целевая функция



ограничения, которые делают задачу осмысленной

(расходы, потери, ошибки)

(доходы, приобретения)

Задача без ограничений: построить дом
при минимальных затратах. Решение: не строить дом вообще.

локальный минимум

глобальныйминимум

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

начальное приближение

начальное приближение

целевая
ячейка

изменяемые ячейки:
E2
D2:D6
D2:D6; C5:C8

целевая
ячейка

ограничения
A1 <= 20
B2:B8 >= 5
A1 = целое

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

задают некоторую неизвестную функцию

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

какую?

Вывод: задача некорректна, поскольку решение  неединственно.

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

Примеры:
линейная
полиномиальная

степенная
экспоненциальная

логарифмическая

заданные пары значений

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

неизвестно!

Закон Ома

?

Точки на линии:

?

Задача. В файле 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;

while not eof(f) do begin
{ читаем U[k] и I[k] }
{ тут еще что-то надо сделать }
end;

not eof(f)

пока не достигнут конец файла (eof = end of file)

заданные пары значений

Крайние случаи:
если график проходит через точки:

если считаем, что y не меняется и :

– среднее значение

ПКМ

Сложные случаи (нестандартная функция):

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

Ряд данных – это упорядоченный набор значений

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

Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ

Дисперсия («разброс») – это величина, которая характеризует разброс данных относительно среднего значения.

среднее арифметическое

квадрат отклонения от среднего

средний квадрат отклонения от среднего значения

Что неудобно:
если измеряется в метрах,  то – в м2

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

Как понимать это число?
если
если
если

увеличение приводит к увеличению

в среднем!

увеличение приводит к уменьшению

связь обнаружить не удалось

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

– СКВО рядов и

безразмерный!

Как понимать это число?
если : увеличение приводит к увеличению
если : увеличение приводит к уменьшению
если : связь обнаружить не удалось

Как понимать коэффициент корреляции?
: очень слабая корреляция
: слабая
: средняя
: сильная
: очень сильная
: линейная зависимость
: линейная зависимость

(по мотивам учебника А.Г. Гейна и др., Информатика и ИКТ, 10 класс, М.: Просвещение, 2008)

– начальная численность

– после 1 цикла деления

– после 2-х циклов

Особенности модели:
не учитывается смертность
не учитывается влияние внешней среды
не учитывается влияние других видов

– коэффициент рождаемости

– коэффициент смертности

Особенности модели:
не учитывается влияние численности N и внешней среды на K
не учитывается влияние других видов на K

прирост

L – предельная численность животных

Идеи:
коэффициент прироста KL зависит от численности N
при N=0 должно быть KL=K (начальное значение)
при N=L должно быть KL=0 (достигнут предел)

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

L – всего жителей Ni – больных в i-ый день
Zi – заболевших в i-ый день Vi – выздоровевших
Wi – всего выздоровевших за i дней

Ni – численность белок, Mi – численность бурундуков

K2, K4 – взаимное влияние

если K2 >K1 или K4 >K3 – враждующие виды

Модель – система:
число встреч пропорционально NiZi
«эффект» пропорционален числу встреч

караси

щуки

Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть в лотерею

Случайный выбор:
жеребьевка на соревнованиях
выигравшие номера в лотерее

нужно специальное устройство
нельзя воспроизвести результаты

малый период (последовательность повторяется через 106 чисел)

в квадрате

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

a, c, m - целые числа

простое число

230-1

период m

остаток от деления

«Вихрь Мерсенна»: период 219937-1

Модель: снежинки падают на отрезок [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;

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

Примеры:
звонки на телефонной станции
вызовы «скорой помощи»
обслуживание клиентов в банке

сколько бригад?

сколько линий?

сколько операторов?

Особенности:
клиенты (запросы на обслуживание) поступают постоянно, но через случайные интервалы времени
время обслуживание каждого клиента – случайная величина

Вход клиентов:
за 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 минут

inMax := 10; { max число входящих за 1 мин }
Tmin := 1; { min время обслуживания }
Tmax := 5; { max время обслуживания }
L := 1000; { период моделирования в минутах }
M := 10; { допустимое время ожидания }

Задача: найти минимальное K, при котором время ожидания в 90% случаев не больше M минут.