Математическая постановка оптимизационной задачи

Быстрая сортировка

Эффективность алгоритма УлПир

Реализация алгоритма УлПир

Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте "Просеивание", поэтому здесь ограничимся только реализацией основного шага 1:

for i:= N downto 2 do

begin x:= a[1];

a[1]:= a[i];

a[i]:= x;

j:= 1;

while j<=((i-1)div 2) do

begin k:= 2*j;

if (k+1<=i-1) and (a[k]<a[k+1])

then k:= k+1;

if a[k]>a[j]

then begin x:= a[j];

a[j]:= a[k];

a[k]:= x;

j:= k

end

else break

end

end;

Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12,11,8,7,10,6,5,4,2,9,3,1]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт - элементы, исключенные из дальнейшей обработки:

1) Меняем местами a[1] и a[12]: [1,11,8,7,10,6,5,4,2,9,3,12];

2) Просеиваем элемент a[1], получаем: [11,10,8,7,9,6,5,4,2,1,3,12];

3) Меняем местами a[1] и a[11]: [3,10,8,7,9,6,5,4,2,1,11,12];

4) Просеиваем a[1], получаем: [10,9,8,7,3,6,5,4,2,1,11,12];

5) Меняем местами a[1] и a[10]: [1,9,8,7,3,6,5,4,2,10,11,12];

6) Просеиваем элемент a[1]: [9,7,8,4,3,6,5,1,2,10,11,12];

7) Меняем местами a[1] и a[9]: [2,7,8,4,3,6,5,1,9,10,11,12];

8) Просеиваем элемент a[1]: [8,7,6,4,3,2,5,1,9,10,11,12];

9) Меняем местами a[1] и a[8]: [1,7,6,4,3,2,5,8,9,10,11,12];

10) Просеиваем элемент a[1]: [7,4,6,1,3,2,5,8,9,10,11,12];

11) Меняем местами a[1] и a[7]: [5,4,6,1,3,2,7,8,9,10,11,12];

12) Просеиваем элемент a[1]: [6,4,5,1,3,2,7,8,9,10,11,12];

13) Меняем местами a[1] и a[6]: [2,4,5,1,3,6,7,8,9,10,11,12];

14) Просеиваем элемент a[1]: [5,4,2,1,3,6,7,8,9,10,11,12];

15) Меняем местами a[1] и a[5]: [3,4,2,1,5,6,7,8,9,10,11,12];

16) Просеиваем элемент a[1]: [4,3,2,1,5,6,7,8,9,10,11,12];

17) Меняем местами a[1] и a[4]: [1,3,2,4,5,6,7,8,9,10,11,12];

18) Просеиваем элемент a[1]: [3,1,2,4,5,6,7,8,9,10,11,12];

19) Меняем местами a[1] и a[3]: [2,1,3,4,5,6,7,8,9,10,11,12];

20) Просеивать уже ничего не нужно;

21) Меняем местами a[1] и a[2]: [1,2,3,4,5,6,7,8,9,10,11,12];

22) Просеивать ничего не нужно, сортировка закончена.

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.

В среднем этот алгоритм имеет сложность, пропорциональную N*log N.

Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка. Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).

1. Дать словесную формулировку задачи.

2. Ввести обозначения для критериев, варьируемых при переменных задачи.

3. Выбрать критерий и определить его зависимость от варьируемых переменных.

4. Определить множество «D», т.е. составить все математические соотношения между варьируемыми переменными, определяющие возможность их выбора.

Оптимизационная задача классифицируется:

Задачи определения max функции одной переменной

Постановка задачи: Для функции нужно определить max при условии

(1)

Множество «D», заданное (1) всегда выпуклое.

Определение: функция называется выпуклой на множестве «D», если она имеет на нем единственный max .

Для решения оптимизационных задач применяются методы, которые условно делятся на две группы:

1) аналитические, которые используют необходимое или достаточное условие максимума

2) численные методы

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

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

Необходимое и достаточное условие максимума функции одной переменной

- необходимое условие

- достаточное условие

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

; помножим на

;

На каждом шаге расчета внутри интервала неопределенности определяют положение двух точек (№3 и №4), которое должно удовлетворять условиям (*). Вычисляют значение функции в этих точках, сравнивают их между собой и сокращают интервал неопределенности «L» до значения «», так , чтобы внутри «» сохранялась точка с наибольшим значением функции. Внутри сокращенного интервала неопределенности оставшаяся точка располагается в соответствии с соотношением (*). Поэтому на каждом шаге расчета, кроме первого, требуется вычислять значение целевой функции только один раз.

и

- погрешность (допустимая ошибка)

Расчет продолжается до тех пор, пока интервал неопределенности (L) не будет меньше погрешности .

Необходимое и достаточное условие max функции многих переменных (безусловного)

необходимое достаточное

Определение условного максимума

функции многих переменных

(задача нелинейного программирования)

Определить максимум функции функции для .

(1)

Где

Метод неопределенных множителей Лагранжа

Рассматривается подзадача определения max, заданная только условиями (2) и (3)

D: (5)

Составляем новую функцию.

L-функция Лагранжа

L

-неопределенный множитель Лагранжа

При выполнении уравнения связи (5) функция Лагранжа совпадает с функцией (1).

Если вычислить max функции Лагранжа при произвольной , то (6)

Из (6) следует, что: максимум функции Лагранжа по «» при произвольной «» максимуму той же функции по «» при оптимальном «», т.е.в точке решения [,] функция Лагранжа достигает max по «» и min по «». Это седловая точка функции Лагранжа.

Условия оптимальности:

L(,)= (7)

Теорема Куна-Такера – дает условие оптимальности для решения задачи условного максимума (1) ¸(4).

Функция Лагранжа общего вида:

L( (8)

Если - решение задачи (1) ¸(4), то найдутся такие , и такие одновременно не равные нулю, что при функция (8) достигает максимума по , минимума по , а также все а .

Условия оптимальности:

L(=

При условии

1) если , то д.б.

2) если , то д.б.