Содержание

Введение

1. Пояснительная записка

1.1 Нелинейное программирование

1.2 Численные методы в задачах без ограничений

1.2.1 Общая схема методов спуска

1.2.2 Градиентные методы

1.2.3 Метод наискорейшего спуска

2. Инструментальные программные средства

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

4. Операционная среда

5. Контрольная задача

Заключение

Литература

Приложение

Введение

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

Численное решение оптимизационных задач на ЭВМ сводится к поиску экстремума функции многих переменных. Таковы задачи оптимального управления и идентификации, задачи супервизорного управления, оптимизационного проектирования и планирования.

Среди различных типов оптимизационных задач особое место занимают задачи оптимизирования невыпуклых детерменированных функций с единственной точкой экстремума.

Эти задачи представляют интерес с различных точек зрения. Прежде всего не выпуклость порождает большие аналитические сложности при разработке методов решения унимодальных задач. Как известно, аналитические методы развиты для значительно простых задач.

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

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

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

1. Пояснительная записка

1.1 Нелинейное программирование

Унимодальные функции. Выделим класс функций, обладающих, с вычислительной точки зрения, важным свойством. А именно: функция f называется унимодальной на отрезке [a,b], если она имеет на этом отрезке единственную точку глобального минимума Xmin и слева от этой точки является строго убывающей, а справа строго возрастающей (см. рис. 1). Другими словами, функция f унимодальная, если точка Xmin существует и единственна, причем для любых двух точек х1, х2 Î [a,b] таких, что х1<x2 из неравенства х1>Xmin всегда следует f(x1)<f(x2), а из неравенства x2<Xmin необходимо вытекает неравенство f(x1)>f(x2).

Самого факта унимодальности недостаточно для получения аналитических результатов или построения эффективных числовых методов. В тоже время «распространенная трактовка выпуклых задач как хорошего модального объекта для задач одноэкстримальных теоретически не состоятельна - сложность классов выпуклых задач несравненно ниже, чем унимодальных.» [1]

Информационная сложность (нижняя граница оценки трудоемкости) задач минимизации непрерывных функций общего вида крайне велика, причем именно унимодальность (а не многоэкстремальность) является причиной такой сложности. В работе [2] отмечено, что информационная сложность класса унимодальных задач «фантастически велика». С точки зрения авторов книги [1], поиск универсальных методов решения унимодальных задач бесперспективен. Поэтому остается один путь – разработка специализированных методов для более узких классов задач.

Задача безусловной минимизации унимодальной функции многих переменных записывается обычно таким образом:

f(x)®min, xÎR (1.1)

Далее будем полагать, что f(x) –достаточное число раз дифференцируемая функция, которая в некотором диапазоне, разумном с точки зрения содержания задачи, имеет один экстремум. Точка X, в которой достигается минимум, называется решением задачи. Известно, что Ñf(x) = 0, где Ñ f(x) – градиент f(x) в точке Х, а гессиан, если он существует в точке Х, является положительно определенной матрицей.

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

F(x) = (Ax,x)/2 + (b,x) + e, (1.2)

здесь А – симметрическая, положительно определенная матрица; b – вектор. Задача минимизации такой функции в принципе может быть решена аналитически, дифференцирование F(x) и приравнивание нулю производных дают систему линейных уравнений. В силу невырожденности матрицы система имеет единственное решение.

Квадратичные одноэкстримальные функции (1.2) принадлежат к более широкому классу строго выпуклых функций. Функция f(x) называется строго выпуклой, если для любых точек х1 и х2 из области ее определения имеет место неравенство:

F(lx1+(1-l)x2)< lf(x1)+(1-l)f(x2), lÎ(0,1).

Строго выпуклые функции унимодальные и обладают достоинством, облегчающим исследование и процесс численной минимизации, - это строгая выпуклость, а следовательно, одноэкстримальность вдоль любого направления. Более широким классом является класс линейно унимодальных функций [3]. Характерное свойство этого множества – унимодальность функций вдоль любой прямой в допустимой области. Функции, унимодальные по любому направлению, если это направление происходит через точку минимум, образуя класс строго унимодальных функций [3].

На рисунке 2 представлены : А – строго выпуклая; Б – линейно-унимодальная; В – строго унимодальная функции.

Специфика каждого из описанных классов может быть использована при построении методов минимизации.

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

В начале 60-х годов И.М. Гельфондом и М.Л. Цетлиным [4] был дескриптивно задан класс невыпуклых функций многих переменных. Элементы класса характеризуются следующей структурой: в любой точке некоторого подмножества области определения функции существует такой базис, что все независимые переменные можно разделить на две группы. Первая группа состоит из тех аргументов, изменение которых приводит к значительному изменению целевой функции (в [4] они названы несущественными переменными). Изменение переменных второй группы (существенных переменных) приводит к незначительному изменению функции. При этом для любой точки подмножества вторая группа содержит лишь небольшое число параметров. Функция, допускающая такое разбиение переменных в некоторой области, называется хорошо организованной (овражной) функцией в этой области, а число существенных переменных определяет размерность оврага [4]. Иными словами, для овражной функции точность линейного приближения

f(x) + Ñf(x) * Ñx в значительной степени зависит от Ñx [5].

В математическом энциклопедическом словаре под редакцией Ю.В. Прохорова дано строгое определение овражной функции.

Пусть «ограниченная снизу функция многих переменных

J * (x) = J(x1, x2, …, xm) Î c²(D), DÌR,

обладает той особенностью, что в исследуемой области собственные значения матрицы Гессе

, i, j = 1, 2, …, m,

упорядоченные в любой точке xÎD, удовлетворяют неравенствам

0 < |min li(x) | << l1(x).

В этом случае поверхность уровня J(x)=const имеют структуру, сильно отличающуюся от сферической. Такие функции J(x) называются овражными. Степень овражности характеризуется числом

S = l1(x) / |min li(x) |, li(x) ╪ 0.

Если собственные значения удовлетворяют неравенствам |lm(x)| <= … <= |lm-r+1(x)| << lm-r(x) << l1(x) , а отношение | lm-r+1(x) | / | lm(x) | невелико, то число r называется размерностью оврага.»

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

«Конечно, такое разбиение параметров невозможно для любой функции, которую мог бы задать математик. Однако, для функций, встречающихся в практической деятельности человека (здесь имеются в виду разумные задачи физики, техники), такое разбиение, по-видимому, имеет место в очень значительном числе случаев.» [4]

Р.П. Федоренко [5] отмечает, что овражные функции совершенно закономерно возникают при конечно-разностной аппроксимации функционалов вариационных задач оптимального управления, и эти задачи требуют не общих, а узкоспециальных методов решения.

Простейшим примером овражной функции является квадратичная функция (1.2), где А – плохо обусловленная матрица. Число обусловленности симметрической матрицы является важной характеристикой ее свойств и определяется через собственные значения: k(A)=max lA / min l4. Если k(A) велико, то А представляет собой плохо обусловленную матрицу, а задача (1.2) называется плохо обусловленной задачей минимизации. В этом случае f(x) определяет многомерную поверхность прямым (неизогнутым) оврагом.

Для неквадратичных функций вводится обобщение этого определения [6]: обусловленностью точки минимум х называется число

m = lim(sup||x-x’||²(inf||x-x’||²), xÎL, L = {x:f(x)=f(x’)+d}.

Если m велико, функция имеет овражный характер.

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

Известно, что минимизация овражных функций связана с большими вычислительными трудностями. Поэтому Р.П. Федоренко [5] предлагает при разработке первичной постановки задачи избегать тех способов формализации, которые приводят к появлению овражных функций.

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

1.2 Численные методы в задачах без ограничений

1.2.1 Общая схема методов спуска

Будем рассматривать задачу безусловной минимизации, т.е. задачу минимизации целевой функции f на всем пространстве R. Сущность всех методов приближенного решения этой задачи состоит в построении последовательности точек х1, х2, х3, …, хk, …, монотонно уменьшающих значение целевой функции:

f(x0) >= f(x1) >= f(x3) >= … >= f(xk) >= … (1.3)

Такие методы (алгоритмы) называют методами спуска. При использовании этих методов применяют следующую схему.

Пусть на k-й итерации имеется точка хk. Тогда выбирают направление спуска pk Î R и длину шага вдоль этого направления ak > 0. Следующую точку последовательности вычисляют по формуле:

xk+1 = xk + ak*pk, k = 0, 1, 2, …

Согласно этой формуле, величина продвижения из точки xk в xk+1 зависит от как ak, так и от pk. Однако ak традиционно называют длиной шага.

Формально различают методы спуска отличные друг от друга способом выбора числа ak и вектора pk. Если для определения ak и pk требуется вычислять только значения целевой функции, соответствующий метод называют методом нулевого порядка или методами поиска. Методы первого порядка требуют, кроме того, вычисления первых производных целевой функции. Если же метод предполагает использование и вторых производных, то его называют методом второго порядка и т.д.

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

Важнейшей характеристикой любых методов спуска является их сходимость. Сходимость здесь понимается в том смысле, что последовательность {xk} должна сходиться к точке глобального (локального) минимума. Однако точки минимума могут составлять целое множество и многие алгоритмы позволяют построить последовательность {xk}, которая сама не является сходящейся, но любая ее сходящаяся последовательность имеет в качестве предельной некоторую точку минимум (см. рис. 3).

В этом случае говорят, что каждая предельная точка последовательности {xk} является точкой минимума. С помощью подобных алгоритмов можно строить последовательности точек, сколь угодно близко приближающихся ко множеству точек минимума.

Возможен случай, когда ничего определенного сказать и о сходимости последовательностей нельзя, однако известно, что соответствующая последовательность значений при {f(xk)} сходится к точке минимального значения (локальный или глобальный минимум). Тогда говорят, что последовательность {xk} сходится к минимуму по функции (см. рис. 4). Кроме того, существуют еще более слабые типы сходимости, когда, например, последовательность {xk} (каждая ее последовательность) имеет в качестве предельной стационарную точку (т.е. точку, в которой градиент равен нулевому вектору), являющуюся лишь «подозрительной» на оптимальную.

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

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

1.2.2 Градиентные методы

Ненулевой антиградиент - Ñf(x0) указывает направление, небольшое перемещение вдоль которого из х0 приводит к значению функции f меньшему, чем f(x0). Это замечательное свойство лежит в основе градиентных методов, согласно которых на k-й итерации полагают pk = - Ñf(xk), т.е.

xk+1 = xk - akÑf(xk), ak > 0, k = 0, 1, 2, … .

Эти методы отличаются друг от друга способом выбора величины шага ak. Достаточно малый шаг ak обеспечивает убывание целевой функции

f(xk+1) = f(xk – ak Ñf(xk)) < f(xk), (1.4)

но может привести к слишком большому количеству итераций для достижения требуемой точности. С другой стороны, выбор большого шага может привести к нарушению неравенства 1.4.

На практике нередко в качестве величины шага выбирают некоторое а > 0, одинаковое для всех итераций. При этом если условие 1.4 (при ak =|a|) нарушится, то для текущей итерации величину а уменьшают до тех пор, пока указанное неравенство не станет выполнимым.

Часто величину ak рекомендуют выбирать так, чтобы имело место более жесткое условие убывания, чем 1.4:

f(xk) – f(xk – akÑf(xk)) >= eak || Ñf(xk) ||, (1.5)

где 0 < e <1 – некоторая фиксируемая константа. Здесь также сначала фиксируют некоторое ak = a > 0 (например, ak = 1), одинаковое для всех итераций, а затем при необходимости уменьшают его до тех пор, пока не будет выполнено неравенство 1.5.

При реализации градиентных методов в качестве критериев окончания счета используют условие вида || Ñf(xk) || <= e, где е > 0 –фиксированная точность вычислений.

Точный смысл сходимости градиентных методов раскрывает следующее утверждение.

Пусть функция f ограничена снизу, непрерывно дифференцируема на R и ее градиент Ñf(x) удовлетворяет условию Липшица:

|| Ñf(x) -Ñf(x’) || <= L || x – x’ || для всех x,x’ Î R,

где L >= 0 – некоторая фиксированная константа. Кроме того, пусть выбор величины шага ak производится на основе условия 1.5. Тогда, какова бы ни была начальная точка х0, оба градиентных метода приводят к построению последовательности {xk}, обладающей свойством lim || Ñf(xk) ||= 0. Если, кроме того, функция f дважды непрерывно дифференцируема и существует такие числа М >= m > 0 , что

m || y || ² <= (Ѳf(x)y,y) <= M || y || ² для всех x,y,

то для градиентных методов последовательность {xk} будет сходится к точке глобального минимума.

Первая часть утверждения гарантирует сходимость лишь в смысле lim || Ñf(xk) || = 0, т.е. сходимость по функции либо к точной нижней грани inf f(x), либо к значению функции f в некоторой стационарной точке х. При этом сама точка х не обязательно является точкой локального минимума; она может быть точкой седлового типа. Однако на практике подобная ситуация маловероятна и применение градиентных методов, как правило, позволяет получить приближенное значение минимума целевой функции (вообще говоря, локального).

Сравнивая рисунки 5 и 6, можно сделать вывод, что для целевой функции, линии уровня которой близки к окружностям, требуемая точность будет достигнута довольно быстро, тогда как если линии сильно вытянуты в окресности оптимальной точки, то градиентные методы приведут к медленному зигзагообразному продвижению в направлении на оптимальную точку. О функции, поверхность уровня которой сильно вытянуты , говорят, что она имеет «овражный» характер (в случаях двух переменных график такой функции действительно напоминает овраг).

О степени «овражности» функции f можно получить представление, зная минимальное (m) и максимальное (M) собственные числа матрицы Гессе Ѳf, вычисленной в оптимальной точке: чем меньше отношение m/M, тем больше “овражность” данной функции. Применение градиентных методов к таким функциям приводит к спуску на «дно оврага», после чего, поскольку направление спуска почти перпендикулярно «линии дна», точки последовательности {xk} будут поочередно находится то на одном «склоне оврага», то на другом и продвижение к оптимальной точке сильно замедляется.

1.2.3 Метод наискорейшего спуска

Поиск минимума функции R(x) выполняют по шагам начиная с начальной точки. На первом шаге вычисляют значение функции, градиент поля функции, путем вычисления частной производной по каждой переменной, модуль градиента, значения переменных в шаге и величину шага по каждой переменной.

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

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

2. Инструментальные программные средства

Перед началом работы над курсовым проектом передо мной встал вопрос: в какой системе программирования или с помощью какого приложения я буду писать программу по данной мне теме. Мой выбор остановился на приложении Microsoft Excel. В настоящее время данный программный продукт можно найти практически на любом персональном компьютере, на котором установлена операционная система Windows 9x, 2000, NT 4.0, XP. Microsoft Excel обладает требуемым для расчетов модели математическим аппаратом. Кроме того, в данный программный продукт встроен редактор Visual Basic, с помощью которого можно писать макросы.

Среда редактора Visual Basic.

Visual Basic предоставляет единую законченную среду редактирования, схожую со средой автономной версии Visual Basic 5.0. Каждая книга Microsoft Excel имеет связанный с ней проект. Среда редактирования Visual Basic включает улучшенный редактор кода, иерархическое средство просмотра объектов, многооконный отладчик, окно отображения свойств и средство просмотра проектов для управления кодом и объектами проекта. Для облегчения создания синтаксически правильного кода среда редактирования Visual Basic имеет группу команд в меню Правка, включающую команды Список свойств/методов, Список констант и Параметры.

Использование объектов ActiveX в формах.

Visual Basic обеспечивает согласованные и расширяемые элементы управления и интерфейс диалоговых окон для всех программ Microsoft Office. Элементы ActiveX (ранее называвшиеся элементами управления OLE) могут быть внедрены непосредственно на листы, что позволяет пользователю создавать свои собственные формы.

События

Богатейшие возможности обработки событий предоставляют гибкие средства определения реакции на действия пользователя.

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

Ввод данных осуществляется с помощью диалогового окно «Ввод данных» (см. рис. 7).

Рисунок 7 Вид формы для ввода данных

Вывод промежуточных и выходных данных осуществляется в таблицу (см. табл. 1)

Таблица 1

Результаты решения

X1	X2	dR/dX1	dR/dX2	|grad|	R(x)

4. Операционная среда

Минимальные требования предъявляемы к аппаратной части:

Процессор – 486 DX/2 80Mz

ОЗУ – 12Мб

Видеоадаптер – VGA 640-480

Монитор

Клавиатура

Мышь

В качестве операционной среды на персональном компьютере должна быть установлена одна из версий Windows (9x, 2000, NT 4.0, XP, Me), а также программный пакет Microsoft Office (97, 2000) или, хотя бы, Microsoft Excel.

Для того, чтобы начать работу с моделью нужно скопировать файл «Метод наискорейшего спуска» в папку «Мои документы» и с помощью программного приложения Microsoft Excel открыть файл.

5. Контрольная задача

Задача. Найти минимум функции

R(x)=a*x1^3+b*x2^2-c*x1-d*x2, где a = 1, b = 2, c = 3, d = 4.

Начальные точки: х1 = -0,5; х2 = -1. Пробный шаг g = 0,01. Коэффициент пробного шага h = 0,1. Погрешность е = 0,01.

Решение. В начальных точках х1=-0,5, х2=-1 вычислим по методу градиента значение функции, градиент поля функции, значение переменных в шаге и величину шага. Полученные данные занесем в таблицу и поставим номер шага. Затем по формуле xi+1 = xi – h*(dR/dxi) найдем новые значения переменных х1 и х2 и вычислим значение функции. Последние операции будем повторять до тех пор, пока значение функции не начнет возрастать. Когда это случится, предыдущее значение функции будем считать локальным минимумом. Вычислим значения градиента поля, модуль градиента, занесем результаты в таблицу и укажем следующий номер шага.

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

Таблица 2

Результаты решения контрольной задачи

Х1	X2	dR/dx1	DR/dx1	|R|	R(X)	№Шага
-0,5	-1	-2,2499	-8	8,310358	7,375	1
-0,27501	-0,2				1,684231
-0,05002	0,6				-1,53007
0,17497	1,4				-2,19955
0,17497	1,4	-2,90806	1,6	3,319155	-2,19955	2
0,465776	1,24				-3,18108
0,756581	1,08				-3,82387
1,047387	0,92				-3,98036
1,047387	0,92	0,291158	-0,32	0,432635	-3,98036	3
1,018271	0,952				-3,99438
0,989155	0,984				-3,99914
0,989155	0,984	-0,06462	-0,064	0,090946	-3,99914	4
0,995617	0,9904				-3,99976
1,002078	0,9968				-3,99997

1,002078	0,9968	0,012583	-0,0128	0,017949	-3,99997	5
1,00082	0,99808				-3,99999
0,999562	0,99936				-4
0,999562	0,99936	-0,00253	-0,00256	0,003599	-4	6

Проанализировав результаты в таблице 2, мы видим, что если не учитывать промежуточные значения, минимум функции R(x) найден на 6-ом шаге. Если сравнить результаты, полученные при поиске минимума методом градиента и методом наискорейшего спуска, мы заметим, что метод наискорейшего спуска оправдывает свое название, т.к. минимум функции найден на 6-ом шаге, а метод градиента найдет этом минимум только на 15-ом. Отсюда вывод, метод наискорейшего спуска также эффективен, но работает гораздо быстрее.

Заключение

Универсального метода (алгоритма), с помощью которого можно было бы успешно решать разнообразные задачи оптимизации, не существует. Поэтому для решения каждого конкретного класса задач используют (и, как правило, не один) «свой» численный метод. Следует помнить, что эффективность численного решения зависит от того, насколько полно и точно отражается в применяемом методе специфика данной задачи, ее «индивидуальные» особенности. Данную программную модель рекомендуется использовать для поиска глобального минимума нелинейных «овражных» функции двух переменных.

Конечно, на этом можно было бы и остановиться. Метод успешно работает, довольно быстро находит минимум функции, но этот поиск можно было бы еще ускорить. Следует разработать способ выбора овражного шага, т.е. величина шага должна меняться от этапа к этапу в зависимости от расположении локального минимума функции. Эффективность рассмотренного метода возросла бы еще больше, т.к. метод зависит от величин овражных шагов h1, h2. Но здесь есть свои трудности, если овражный шаг слишком велик, то можно довольно далеко отойти от линии «дна оврага»; если же этот шаг мал, то продвижение будет незначительным. Величину шага нужно подбирать эмпирически, учитывая известные свойства минимизируемой функции.

Литература

1. Юдин Д.Б., Юдин А.Д. «Число и мысль» М.: Знание, 2005. С.190

2. Немировский А.С., Юдин Д.Б. «Информационная сложность математического моделирования» Изв. АНСССР. Тех. Кибернетика. 2003 №1 С.88-117

3. Уайнд Д. «Методы поиска экстремума». М.: Наука, 2007. С.267

4. Гельфонд И.М., Цетлин М.Л. «О некоторых способах управления сложными системами». УМН, 2002. Т.27. С.3-26

5. Федоренко Р.П. «Об одном алгоритме решения задач математического программирования». Журнал вычислительная математика, 2006. Т.22 №6 С.1331-1343

6. Поляк Б.Т. «Введение в оптимизацию» М.: Наука, 2003. С.384

7. Ногин В.Д. «Основы теории оптимизации» М.: Знание, 2007. С99-122

8. Ларичев О.И., Горвиц Г.Г. «Методы поиска локальных экстремумов овражных функций» М.: Наука, 2003. С.5-12

Приложение

Код модуля

Option Explicit

Dim i, s, j, h1, h2

Sub Кнопка2_Щелкнуть()

Form1.Show 'Ввод исходных данных

End Sub

Sub Кнопка3_Щелкнуть()

j = 1

i = 2 'Номер шага(этапа)

Do 'Цикл нахождения минимума функции

h1 = Range("aa3") 'Присвоение переменным

h2 = Range("aa4") 'h1,h2 значения шага

Do

Range("z1").Select 'Сохранение предыдущего

s = ActiveCell 'значения функции

'Вычисление новых начальных точек

Range("v1").Select

ActiveCell = Range("x1")

Range("v2").Select

ActiveCell = Range("x2")

Range("x1").Select

ActiveCell = ActiveCell - h1

Range("x2").Select

ActiveCell = ActiveCell - h2

'Вывод в таблицу новых начальных

'точек и значение функции в этих точках

Range("a3", "f23").Select

ActiveCell(j, "a") = Range("x1")

ActiveCell(j, "b") = Range("x2")

ActiveCell(j, "f") = Range("z1")

j = j + 1

'Cравнение нового значения функции с предыдущим

Loop While Range("z1") < s

j = j - 1

Range("x1").Select

ActiveCell = Range("v1")

Range("x2").Select

ActiveCell = Range("v2")

'Вывод в таблицу новых начальных точек,

'градиент поля функции, модуль градиента

'и значение функции в новых начальных точках

Range("a3", "g23").Select

ActiveCell(j, "a") = Range("x1")

ActiveCell(j, "b") = Range("x2")

ActiveCell(j, "c") = Range("w1")

ActiveCell(j, "d") = Range("w2")

ActiveCell(j, "e") = Range("w3")

ActiveCell(j, "f") = Range("z1")

'Вывод номера шага(этапа) вычисления минимума функции

ActiveCell(j, "g") = i

j = j + 1

i = i + 1

Range("w3").Select

'Сравнение значения модуля градиента и погрешности

Loop While ActiveCell > Range("y3")

End Sub

Sub Кнопка4_Щелкнуть()

'Очистка диапазона ячеек

Range("a2", "g40").Clear

Range("x1", "x2").Clear

Range("y1", "y3").Clear

Range("v1", "v2").Clear

Range("z1").Clear

End Sub

Код формы “Метод наискорейшего спуска”

Private Sub CB1_Click()

End

End Sub

Private Sub CB2_Click()

Range("Z1").Select

Lbl1.Caption = ActiveCell

Range("c2").Select

ActiveCell = Range("w1")

Range("d2").Select

ActiveCell = Range("w2")

Range("e2").Select

ActiveCell = Range("w3")

'Вывод номера шага нахождения минимума функции

Range("g2").Select

ActiveCell = 1

End Sub

Private Sub TB1_Change()

Range("X1").Select

ActiveCell = TB1.Text

Range("a2").Select

ActiveCell = Range("x1")

End Sub

Private Sub TB2_Change()

Range("X2").Select

ActiveCell = TB2.Text

Range("b2").Select

ActiveCell = Range("x2")

End Sub

Private Sub TB3_Change()

Range("Y1").Select

ActiveCell = TB3.Text

End Sub

Private Sub TB5_Change()

Range("Y3").Select

ActiveCell = TB5.Text

End Sub

Private Sub TB4_Change()

Range("Y2").Select

ActiveCell = TB4.Text

End Sub

Private Sub TB6_Change()

Range("Z1").Select

ActiveCell = TB6.Text

Range("f2").Select

ActiveCell = Range("z1")

End Sub