Метод прямого сканирования

ВВЕДЕНИЕ

В математике изучение задач на нахождение максимума и минимума началось очень давно. Но только лишь в эпоху формирования математического анализа были созданы первые методы решения и исследования задач на экстремум.

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

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

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

В математике исследование задач на максимум и минимум началось очень давно – двадцать пять веков назад, Долгое время к задачам на отыскание экстремумов не было сколько – нибудь единых подходов. Но примерно триста лет назад – в эпоху формирования математического анализа – были созданы первые общие методы решения и исследования задач на экстремум.

Накопление методов дифференциального исчисления приняло наиболее явную форму у Ферма. В 1638 году он сообщил в письме Декарту, что решил задачу определения экстремальных значений функции f(x). Ферма составлял уравнение (f(x+h)-f(x))/h=0 и после преобразований в левой части полагал h=0, вопреки мнению позднейших исследователей, которые видели в этой идеи исчисления бесконечно малых. В действительности, Ферма нашел это условие и аналогичное (f(y)-f(x))/(y-x)=0 при y=x ещё алгебраическими путями.

Рассуждения при нахождении экстремума функции f(x) следующие. Пусть для некоторого x функция достигает максимума. Тогда f(x h)<f(x);f(x) Ph Qh2…<f(x). Вычитаем из обеих частей и делим на h, откуда P Qh …<0.Так как h можно выбрать любой малости, член P будет по модулю больше суммы всех остальных членов. Неравенство поэтому возможно лишь при условии P=0, что и дает условие Ферма. В случае минимума рассуждения аналогичные. Ферма знал также, что знак Q определяет характер экстремума.

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

Накопление фактов дифференциального исчисления происходило быстро. В“Дифференциальном исчислении” (1755) Эйлера это исчисление появляется уже в весьма полном виде.

Правила определения экстремумов функции одной переменной y=f(x) были даны Маклореном. Эйлер разработал этот вопрос для функции двух переменных. Лагранж показал (1789), как отличать вид условного экстремума для функции многих переменных.

ПОСТАНОВКА ЗАДАЧИ

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

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

Величина этого интервала – ∆, определяется исходя из требований точности результата решения при постановке задачи (быстродействие, точность и пр.). Таким образом, численное решение задачи поиска экстремума функции сводится к уменьшению интервала неопределенности от исходного до ∆.

Пусть требуется найти экстремум функции одной переменной Q (u) при отсутствии ограничений на диапазон изменения переменной u.

Необходимым условием существования экстремума непрерывной функции Q (u) является равенство нулю первой производной (dQ / du = 0) или ее отсутствие. Графически равенство нулю производной означает, что касательная к кривой Q (u) в этой точке параллельна оси абсцисс (рис. 1.1, а), на рис. 1.1, б изображен случай, когда производные в точках экстремума не существуют.

Названные условия являются лишь необходимыми условиями. Их выполнение не означает еще, что в данных точках функция имеет экстремум (рис. 1.2).

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

Рис.1.1 Различные типы экстремума функции одной переменной:
а — производная в точке экстремума существует
б — производная в точке экстремума не существует

Рисунок 1.2 Функции Q(u), удовлетворяющие необходимым условиям экстремума:

а – производная равна нулю;

б – производная не существует;

в – производная равна бесконечности

1 Сравнение значений функций.

Этот способ сводится к определению значений функции в точках, расположенных слева и справа в достаточной близости от исследуемой точки, т.е. в точках (u 1 – ε), (u 1 +ε), где ε – малая положительная величина. Если Q (u 1) > Q (u 1 – ε) и Q (u 1) > Q (u 1 + ε), то в точке u 1 существует максимум (рис. 1.3). Если Q (u 1) < Q (u 1 – ε) и Q (u 1) < Q (u 1 + ε), то в точке u 1 существует минимум (рис. 1.3, б). Если же Q (u 1) будет занимать промежуточное положение между Q (u 1 – ε) и Q (u 1 + ε), например, Q (u 1) > Q (u 1 – ε) и Q (u 1) < Q (u 1 – ε), то в точке u 1 экстремума не будет (рис. 1.3, в).

2 Сравнение знаков производной.

При этом способе определяется знак первой производной функции в точках (u 1 – ε) и (u 1 + ε). Если знаки производных различны, то в точке u 1 имеется экстремум функции Q (u), причем, если при переходе от точки (u 1 – ε) к точке (u 1 + ε) знак производной изменяется с "+" на "–", то в точке u 1 – максимум (рис. 1.3 а). Если же знак меняется с "–" на "+", то в точке u 1 – минимум (рис. 1.3, б).

Если же знаки производных в точках (u 1 – ε) и (u 1 + ε) одинаковы, то в точке u 1 экстремума нет (рис. 1.3, в).

3 Исследование знаков высших производных.

Этот способ применяется в тех случаях, когда исследуемая функция имеет производные высших порядков. Если в точке u 1 выполняется необходимое условие экстремума, т.е. и существует вторая производная – , значение которой вычисляется в "подозреваемой" точке u 1, то точка u 1 является точкой максимума, если , и точкой минимума, если .

Рисунок 1.3 Проверка достаточных условий экстремума:

а – максимум; б – минимум; в – экстремума нет

Если , то для дальнейших исследований вычисляются и т.д.

МЕТОДЫ РЕШЕНИЯ

Метод прямого сканирования

Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [ a, b ] с точностью до Δ. При решении этой задачи весь интервал разбивается на участки величиной Δ. В узлах разбиения вычисляются значения функции Q и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения Δ), но главное его преимущество – это определение глобального экстремума.

Рис. 2.1 Локализация экстремума методом сканирования:

а — геометрическая интерпретация

2.2 Метод половинного деления

Естественным и наиболее распространенным на практике методом поиска экстремума функции одной переменной является метод последовательного деления отрезка пополам. Этот метод был известен еще в древней Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке [ a, b ] с точностью Δ. Отрезок [ a, b ] делится пополам и вычисляются значения функции Q (x 1) = F 1 и Q (x 2) = F 2 в точках .

На основе анализа значений F 1 и F 2 вдвое уменьшается интервал неопределенности и процесс повторяется пока b – a > Δ.

Рисунок 2.2 Метод половинного деления: геометрическая интерпретация

2.3 Метод «золотого сечения»

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

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x 1 (см. рис. 2.3, б) по формуле

Точка x 2 определяется как точка, симметричная точке x 1 на отрезке (a – b). На основе анализа значений F 1 = Q (x 1) и F 2 = Q (x 2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий унимодальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше Δ.

Рисунок 2.3 Метод «золотого сечения»:

а – золотое сечение; б – геометрическое представление

Метод Фебоначчи

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением:

F ₀ = F ₁= 1; F_k = F_k _–1 + F_k _–2; k = 2, 3, …

При большом " k " отношение соседних чисел Фибоначчи близко к отношению "золотого сечения". Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от Δ, число вычислений значений функции Q (u).

По заданному Δ определяется количество вычислений n и соответствующее ему число Фибоначчи F_n, исходя из соотношения:

ПРИМЕР РЕШЕНИЯ

Метод половинного деления

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке [ a, b ] с точностью Δ.

Пусть a, b, Δ известны.

· Отрезок [ a, b ] делится пополам и вычисляются значения функции Q (x 1) = F 1 и Q (x 2) = F 2 в точках .

· Если значение a — b > Δ, проверяем отношение F1<F2. Если оно верно, то . Если отношение F1<F2 неверно, то .

· На основе анализа значений F 1 и F 2 вдвое уменьшается интервал неопределенности и процесс повторяется пока a – b > Δ.

Блок-схема метода половинного деления представлена на рис.3.1

Рис. 3.1 — Блок — схема метода половинного деления

3.2 Метод «золотого сечения»

Пусть требуется определить экстремум унимодальной функции Q(u) на отрезке [ a, b ] с точностью Δ.

Пусть a,b, Δ известны.

1. Рассчитываются начальные точки деления:

;

2. Рассчитываются значения целевой функции в этих точках:

;

· Если , то (для поиска max - );

· Иначе ;

3. Если |b-a| < Δ, то - алгоритм останавливается;

• Иначе возврат к шагу 1;

Блок — схема метода «золотого сечения»представлена на рис. 3.2.

Рис. 3.2 — Блок — схема метода «золотого сечения»

ВЫВОД

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

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

СПИСОК ЛИТЕРАТУРЫ

1. И.К. Волков, Е.А. Загоруйко. «Исследование операций», Издательство МГТУ им Н.Э. Баумана, Москва 2002.

2. А.В. Аттетков и др., «Методы оптимизации», Издательство МГТУ им Н.Э. Баумана, Москва 2003.

3. О.И. Ларичев, «Теория и методы принятия решений», Физматкнига, Москва 2006.

4. Спецнадель В.Н. Теория и практика принятия оптимальных решений. Уч. пособие. – Спб.: Бизнес-пресса, 2002.

ПРИЛОЖЕНИЕ 1

Найти минимум функции методом множителей Лагранжа:

F(x,y)=x²+y²+ax+by+c ―>min

dx+ey+r=0

a	-8
b
c
d
e
r	-3

1. Записать функцию Лагранжа:

min(x²+y²-8x+8y+32)

y-3=0

ƒ(x,y)=x²+y²-8x+8y+32

g₁(x)=0

g₁(x)=y-3

Λ=(x,y,λ₁)=x²+y²-8x+8y+32+λ₁(y-3)

2. Приравнять к нулю градиент функции Лагранжа и найти стационарные точки:

(x*=4, y*=3, λ*=-14)

3.Исследовать второй дифференциал функции Лагранжа для каждой стационарной точки на положительность:

dg₁=dy=0

ПРИЛОЖЕНИЕ 2

Задание 1.

Рассматривается игра двух лиц, интересы которых противоположны. Такие игры называются антагонистическими играмидвух лиц. В этом случае выигрыш одного игрока равен проигрышу второго.

Предполагается, что каждый игрок может выбрать только одно из конечного множества своих действий. Выбор действия называется выбором стратегии игрока. Если каждый из игроков выбрал свою стратегию, то эта пара стратегий называется ситуацией игры. Каждый игрок знает, какую стратегию выбрал его противник. Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

1. Проверяется наличие седловых точек в матрице.

Если седловые точки имеются - выписывается решение игры в чистых стратегиях.

Пусть игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1					-4	-4
A2			-3	-1		-3
A3
A4	-3	-3		-4		-4
A5
b = max(Bi)						―

Находится гарантированный выигрыш, определяемый нижней ценой игры: а=max(a_i)=4, которая указывает на максимальную чистую стратегию А₃.

Верхняя цена игры b=min(b_j)=4.

Седловая точка (3,2) указывает решение на пару альтернатив (А₃, В₂). Цена игры равна 4.

Задание 2.

Игроки	В₁	В₂	В₃	В₄	a = min(Ai)
А1
А2
b = max(Bi)					―

Находится гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 2, которая указывает на максимальную чистую стратегию A₂.
Верхняя цена игры b = min(b_j) = 4.

Это свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 <= y <= 4. Находится решение игры в смешанных стратегиях.

С позиции проигрышей игрока В стратегия B₃ доминирует над стратегией B₂ (все элементы столбца 3 больше элементов столбца 2), следовательно исключается 3-й столбец матрицы. Вероятность q3 = 0.

Решение задачи геометрическим методом который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2(x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1= (p1,p2).

2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.

Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии.

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B2B2 и B3B3, для которых можно записать следующую систему уравнений:

Цена игры .

Минимальная стратегия игрока В находится путем записи соответствующей системы уравнений, исключив стратегию В₁, дающую большой проигрыш игроку В, и следовательно, q₁=0:

;

Решив эту систему, получаем: ;

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

Задание 3.

-3

В каждом столбце матрицы A найдем максимальный элемент. Эти элементы подчеркнуты в матрице A. Их положение соответствует приемлемым ситуациям 1-го игрока, когда второй игрок выбрал стратегию j соответственно.
Затем в каждой строке матрицы B выберем наибольший элемент. Эти элементы подчеркнуты в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал стратегию i соответственно.
Платежная матрица игрока А:

Платежная матрица игрока B:

-3

Таким образом, найдены две равновесные ситуации (2;1), (1;2). Эти ситуации оказались приемлемыми для обоих игроков.
В равновесной ситуации (2,1) игрок 1 выигрывает 5 единиц, а игрок 2 - 8 единицы. В равновесной ситуации (1,2) игрок 1 выигрывает 4 единиц, а игрок 2 - 4 единицы.

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

Итак, чтобы в биматричной игре: А=(a), В = (b) пара (p,q), определяемая равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств:

(p–1)(Cq-α) >= 0, p(Cq-α) >= 0; 0 >= p >= 1

(q-1)(Dp-β) >= 0, q(Dp-β) >= 0; 0 >= q >= 1,

где

C = a11 - a12 - a21 + a22

α = a22- a12

D = b11-b12-b21+b22

β = b22-b21.

Проводя необходимые вычисления:

C = 1 - 4 - 5 + 2 = -6

α = 2 - 4 = -2

D = -3 - 4 - 8 + 2 = -13

β = 2 - 8 = -6

и рассуждения:

(p–1)(-6q+2) >= 0

p(-6q+2) >= 0

(q-1)(-13p+6) >= 0

q(-13p+6) >= 0

получаем, что:

1) p=1,q >= ; p=0, q <= ; 0 <= p <= 1, q= ;

2) q=1,p >= ; q=0, p <= ; 0 <= q <= 1, p= ;

Цена игры: H_a(; ) = 3, H_b(; ) =

Ответ: P* = (; ); Q* = (; ).

Выигрыш игроков в равновесной ситуации: f(P*,Q*) = (3; ).

ПРИЛОЖЕНИЕ 3

1. Найти наикратчайший путь из узла (1) в узел (16).

2. Найти остов графа.

1. Пусть дан граф G{M,N}, где M – множество вершин, N – множество дуг, и дана таблица длин пути (Таблица 1).

Таблица 1:

	(1, 2)
	(2, 3)
	(3, 4)
	(1, 5)
	(2, 6)
	(3, 7)
	(4, 8)
	(5, 6)
	(6, 7)
	(7, 8)
	(5, 9)
	(6,10)
	(7,11)
	(8,12)
	(9, 10)
	(10, 11)
	(11, 12)
	(9, 13)
	(10,14)
	(11,15)
	(12,16)
	(13,14)
	(14,15)
	(15,16)

Для поиска наикратчайшего пути воспользуемся алгоритмом Дейкстры:

1. Пусть (1) — начальный узел. Присваиваем всем вершинам метки (таблица 2).

• Метка начального узла — 0;

• Каждой вершине, связанной с (1) присваиваются временные метки, разные длине пути;

• Остальным вершинам присваивается временная метка - ∞;

Таблица 2:

46*

∞*

16*

∞*

2. Среди всех временных выбирается та, которая имеет наименьшее временное значение и переводится в постоянное V_i (Таблица 3);

Таблица 3:

46*

∞*

3. Во всех вершинах j, связанных с i (Таблица 4), происходит пересчет метки:

V_i^*=min (V_j^*; V_i+C_ij),

где C_{ij —} расстояние между i и j,

V_i, V_j – значения метки i и j;

Таблица 4:

46*

∞*

16 i

∞* j

∞*

∞* j

∞*

V₆^*=min (∞*; 16+25)=min (∞*; 41)=41;

V₉^*=min (∞*; 16+10)=min (∞*; 26)=26;

4. Пункт 2 повторяется до тех пор, пока существуют временные метки.

5. Используя алгоритм «обратного хода», находятся наикратчайшие пути.

Решение.

46*

∞*

16*

∞*

46*

∞*

46*

∞*

16 i

∞* j

∞*

∞* j

∞*

46*

∞*

41*

∞*

26*

∞*

46*

∞*

41*

∞*

46*

∞*

41*

∞*

26 i

∞*j

∞*

∞*j

∞*

V₁₀^*=min (∞*; 26+20)=min (∞*; 46)=46;

V₁₃^*=min (∞*; 26+11)=min (∞*; 37)=37;

46*

∞*

41*

∞*

46*

∞*

37*

∞*

46*

∞*

41*

∞*

46*

∞*

46*

∞*

41*

∞*

46*

∞*

37j

∞*j

∞*

V₁₄^*=min (∞*; 37+50)=min (∞*; 87)=87;

46*

∞*

41*

∞*

46*

∞*

87*

∞*

46*

∞*

46*

∞*

87*

∞*

46*

∞*

41i

∞*j

∞*

46*j

∞*

87*

∞*

V₇^*=min (∞*; 41+31)=min (∞*; 72)=72;

V₁₀^*=min (46*; 41+45)=min (46*; 86)=46;

46*

∞*

72*

∞*

46*

∞*

87*

∞*

72*

∞*

46*

∞*

87*

∞*

46 i

∞*j

∞*

72*

∞*

46*

∞*

87*

∞*

V₃^*=min (∞*; 46+40)=min (∞*; 86)=86;

86*

∞*

72*

∞*

46*

∞*

87*

∞*

86*

∞*

72*

∞*

87*

∞*

86*

∞*

72*

∞*

46 i

∞*j

∞*

87*j

∞*

V₁₁^*=min (∞*; 46+34)=min (∞*; 80)=80;

V₁₄^*=min (87*; 46+16)=min (87*; 62)=62;

86*

∞*

72*

∞*

80*

∞*

62*

∞*

86*

∞*

72*

∞*

80*

∞*

86*

∞*

72*

∞*

80*

∞*

62 i

∞*j

∞*

V₁₅^*=min (∞*; 62+41)=min (∞*; 103)=103;

86*

∞*

72 *

∞*

80*

∞*

103*

∞*

86*

∞*

80*

∞*

103*

∞*

86 *

∞*

72 i

∞*j

80*j

∞*

103*

∞*

V₈^*=min (∞*; 72+19)=min (∞*; 91)=91;

V₁₁^*=min (80*; 72+50)=min (80*; 122)=80;

86 *

∞*

91*

80*

∞*

103*

∞*

86 *

∞*

91*

∞*

103*

∞*

86 *

∞*

91*

80 i

∞*j

103*j

∞*

V₁₂^*=min (108*; 80+28)=min (108*; 108)=108;

V₁₅^*=min (103*; 80+28)=min (103*; 108)=103;

86*

∞*

91*

108*

103*

∞*

91*

108*

103*

∞*

86i

∞*j

91*

108*

103*

∞*

V₄^*=min (∞*; 86+7)=min (∞*; 93)=93;

93*

91*

108*

103*

∞*

93*

108*

103*

∞*

93*

91 i

108*j

103*

∞*

V₁₂^*=min (108*; 91+47)=min (108*; 138)=108;

93*

108*

103*

∞*

108*

103*

∞*

93 i

108*

103*

∞*

108*

103*

∞*

108*

∞*

108*

∞*j

V₁₆^*=min (∞*; 103+39)=min (∞*; 142)=142;

108*

142*

108 i

142*j

V₁₆^*=min (142*; 108+1)=min (142*; 109)=109;

109*

Кратчайший путь в графе — (1)→(5)→(9)→(10)→(11)→(12)→(16)

2. Остов графа — R', которое связывает все вершины и имеет минимальную длину: .

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

∞

―

Минимальная длина:

(1.2)	(2.6)	(6.5)	(5.9)	(6.7)	(7.8)	(8.4)	(4.3)	(9.10)	(9.13)	(10.11)	(10.14)	(11.15)	(15.16)	(12.16)

;

Остов графа: