/>/>/>/>Содержание
Введение
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] таких, что х1Xmin всегдаследует 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)
Строго выпуклые функции унимодальные и обладают достоинством, облегчающимисследование и процесс численной минимизации, — это строгая выпуклость, аследовательно, одноэкстримальность вдоль любого направления. Более широкимклассом является класс линейно унимодальных функций [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
В этом случае поверхность уровня J(x)=const имеют структуру, сильноотличающуюся от сферической. Такие функции J(x) называются овражными. Степень овражности характеризуетсячислом
/>
S = l1(x) / |min li(x) |, li(x)╪ 0.
Если собственные значения удовлетворяют неравенствам |lm(x)|
В отличие от локальных моделей, описывающих функцию и ее производные вмалой окрестности заданной точки, овражная модель характеризует глобальныесвойства функции.
«Конечно, такое разбиение параметров невозможно для любой функции,которую мог бы задать математик. Однако, для функций, встречающихся впрактической деятельности человека (здесь имеются в виду разумные задачифизики, техники), такое разбиение, по-видимому, имеет место в очень значительномчисле случаев.» [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))
но может привести к слишком большому количеству итераций для достижениятребуемой точности. С другой стороны, выбор большого шага может привести к нарушениюнеравенства 1.4.
На практике нередко в качестве величины шага выбирают некоторое а > 0,одинаковое для всех итераций. При этом если условие 1.4 (при ak=|a|) нарушится, то для текущей итерации величину ауменьшают до тех пор, пока указанное неравенство не станет выполнимым.
Часто величину ak рекомендуют выбирать так, чтобыимело место более жесткое условие убывания, чем 1.4:
f(xk) – f(xk – akÑf(xk))>= eak || Ñf(xk) ||, (1.5)
где 0 0(например, ak = 1), одинаковое для всех итераций, азатем при необходимости уменьшают его до тех пор, пока не будет выполненонеравенство 1.5.
При реализации градиентных методов в качестве критериев окончания счетаиспользуют условие вида || Ñf(xk) || 0 –фиксированная точность вычислений.
Точный смысл сходимости градиентных методов раскрывает следующее утверждение.
Пусть функция f ограничена снизу, непрерывнодифференцируема на R и ее градиент Ñf(x) удовлетворяет условию Липшица:
|| Ñf(x) -Ñf(x’) ||
где L >= 0 – некоторая фиксированнаяконстанта. Кроме того, пусть выбор величины шага akпроизводится на основе условия 1.5. Тогда, какова бы ни была начальная точках0, оба градиентных метода приводят к построению последовательности {xk}, обладающей свойством lim || Ñf(xk) ||= 0. Если, кроме того,функция f дважды непрерывно дифференцируема и существует такие числа М >= m > 0, что
m || y || ²
то для градиентных методов последовательность {xk}будет сходится к точке глобального минимума.
Первая часть утверждения гарантирует сходимость лишь в смысле lim || Ñf(xk) ||= 0, т.е. сходимость по функции либо к точной нижней грани inf f(x), либо кзначению функции f в некоторой стационарной точке х.При этом сама точка х не обязательно является точкой локального минимума; онаможет быть точкой седлового типа. Однако на практике подобная ситуация маловероятнаи применение градиентных методов, как правило, позволяет получить приближенноезначение минимума целевой функции (вообще говоря, локального).
Сравнивая рисунки 5 и 6, можно сделать вывод, что для целевой функции, линииуровня которой близки к окружностям, требуемая точность будет достигнутадовольно быстро, тогда как если линии сильно вытянуты в окресности оптимальнойточки, то градиентные методы приведут к медленному зигзагообразному продвижениюв направлении на оптимальную точку. О функции, поверхность уровня которойсильно вытянуты, говорят, что она имеет «овражный» характер (в случаях двухпеременных график такой функции действительно напоминает овраг)./> /> /> /> /> /> /> /> /> /> /> /> />
Рисунок 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, с помощью которого можнописать макросы.
Среда редактора VisualBasic.
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 WhileRange(«z1»)
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