УДК 519.86
ПОИСКОВЫЙ АЛГОРИТМ МИНИМИЗАЦИИ СКАЛЯРНОЙ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ ПРИ ИНТЕРВАЛЬНЫХ ОГРАНИЧЕНИЯХ НА ПЕРЕМЕННЫЕ
Ю. Г. БОЯРИНОВ, канд. техн. наук, доцент
Филиал Московского энергетического института (технический университет) Энергетический проезд, д. 1, г. Смоленск, 214013, Россия
Рассмотрен поисковый алгоритм минимизации скалярной функции многих переменных при неявном задании функции и интервальных ограничениях на переменные. Суть алгоритма, в предположении, что наименьшее значение функция принимает в одной из вершин гиперпараллелепипеда - области допустимых значений аргументов, состоит в последовательном обходе вершин из начальной точки в сторону убывания функции. Предложена программная реализация алгоритма в среде МЛТЬЛБ.
Ключевые слова, алгоритм минимизации, скалярная функция многих переменных, интервальные ограничения на переменные, программная реализация алгоритма.
Введение. Задача нахождения наименьшего значения скалярной функции многих аргументов при наличии интервальных ограничений на аргументы является достаточно типовой на практике. Для решения данной задачи разработано множество алгоритмов (см., например, [13]), однако, как правило, подобные алгоритмы хорошо работают только при небольшом числе аргументов. Если же это число велико - десятки и сотни, то многие из известных алгоритмов просто неприменимы. Для подобных ситуаций пригодными оказываются только так называемые алгоритмы большой размерности, реализованные, в частности, в системе компьютерной математики MATLAB [4]. Однако использовать возможности этой и других аналогичных систем не всегда целесообразно ввиду их громоздкости, иногда удобней иметь автономные программы, созданные на каком-либо языке высокого уровня. В статье рассмотрена разновидность алгоритма большой размерности, отличающаяся простотой программной реализации, суть которой, в предположении, что наименьшее значение функция принимает в одной из вершин гиперпараллелепипеда - области допустимых значений аргументов, состоит в последовательном обходе вершин из начальной точки в сторону убывания функции.
Постановка задачи. Предполагается, что задана, в общем случае, неявным образом, скалярная функция f(x) многих вещественных переменных x1, x2,..., xn, или, иначе, векторного аргумента x = [x1, x2,..., xn]T (здесь "T" - символ транспонирования). На переменные наложены интервальные ограничения в форме нестрогих неравенств:
x1 min < x1 < x1 max,
x2 min < x2 < x2 max,
xi m
! £ xi < xi r
(1) = [xi
xn min < xn < xn max,
или, в векторной форме,
x < x < x
min max T
где xmin = [xi min x2 minxn min] , ]T
max, x2 max,., xn max] .
Число переменных может быть значительным, например, до сотни.
Дополнительно предполагается, что функция f(x) - достаточно гладкая в области определения Sx, определяемой соотношением (1), т.е. не имеет экстремумов внутри этой области.
Требуется: найти точку x*e Sx, в которой функция f достигает наименьшего значения, т.е. иными словами, решить оптимизационную задачу
x* = arg f( x*) = arg min [f( x)] . (2)
xeSx
Алгоритм решения. Выдвинутое предположение, что искомая функция не имеет экстремумов внутри допустимой области изменения аргументов, позволяет осуществлять поиск точки наименьшего значения функции среди граничных (угловых) точек области Sx. Данная область, в соответствии с ограничениями (1), представляет собой гиперпараллелепипед в n-мерном пространстве аргументов. Суть алгоритма, как отмечалось - в последовательном переборе вершин гиперпараллелепипеда, так, что осуществляется движение к вершине, где значение функции наименьшее.
Приведем словесное описание алгоритма.
Требуемая входная информация: размерность задачи n (число аргументов функции), подпрограмма вычисления значений функции f(xi, x2,..., xn) при заданном наборе ее аргумен-
тов, границы изменения аргументов - векторы
= [X! ШЩ Х2 ШЩ •
х 1т
. . . , лп шах I •
п] и Хшах = [XI
Х2
Г(х1,х2,...хб)=[0 1 0 0]-
Начало.
1. Ввод исходных данных: числа переменных п, предельного числа итераций К, задание подпрограммы вычисления функции Д(х), начального приближения (начальной точки расчетов) Ы(0) = {и!}, где ! = 1,2,..., п; элемент и! равен 1 или -1, при этом если и = 1, то х! = х! шах, если и = -1, то х! = х! Ш!п (вектор и введен для удобства обхода вершин области определения функции, его элементы - индикаторы значений компонент вектора Х).
Формирование вектора х0 по вектору начального приближения и0.
2. Принятие и(0) (и Х(0)) за базовую точку вычислений; расчет значения функции Д(Х(0)).
3. ! = 1.
4. Переход к ьй соседней с базовой вершине гиперпараллелепипеда Х(!) путем замены значения ьго элементы вектора и, т.е. и!, на противоположный: и = -и!. Соответствующее изменение значения х!.
5. Расчет Дх^).
6. Сравнение Д(Х(0)) и Дх^). Если Д(Х(0)) > Д(Х(!)), то и(0) = и(!) и переход к п. 3 алгоритма.
7. ! = ! + 1.
9. ! > п? Если нет (т.е. обойдены не все п соседних с текущей базовой точки гиперпараллелепипеда), то переход к п. 4 алгоритма.
10. Вывод информации о х* = х№ и Д(Х(0)) = Д(х*) как о достигнутой точке наименьшего значения функции и о значении функции в этой точке.
Конец.
Вариант алгоритма был реализован с помощью "студенческого" языка программирования Турбо Бейсик; без подпрограммы вычисления значения функции основной текст программы имел 40 строк и объем в несколько кБ; компилированный вариант программы, реализующей алгоритм имел объем всего в 27 кБ. Программа достаточно устойчиво работала на многих модельных примерах при числе переменных п < 100. Время счета, естественно, зависело от п и от сложности вычисления значения функции
Д(х).
Пример. Пусть задана функция Д(хь х2, ..., х6) вида (неявного)
0
-(X + Х2)
х, -х3
00
0 -х4
-1 "0"
0
0
1_
(3)
0
1 111 _ при ограничениях: 1.9 < XI < 2.1, 0.9 < х2 < 1.1, 0.9 < ху < 1.1, 2.8 < Х4 < 3.2, 1.9 < Х5 < 2.1, 1.9 < х6 < 2.1.
Требуется в условиях этой задачи найти наименьшее значение функции (и точку, в которой она принимает это значение).
Решение. Здесь п = 6, ограничение и задание функции соответствуют принятой постановке задачи. В предположении, что точкой минимума является одна из угловых точек области определения (гиперпараллелепипеда), найдем данную точку используя разработанный алгоритм при начальном приближении Хо = [2.1 1.1 1.1 3.2 2.1 2.1]т
Полученный результат: х* = [1.9 1.1 1.1 2.8 1.9 1.9]т, Д(х*) = 0.426.
С целью проверки этого результата, минимум рассматриваемой функции производился в среде системы компьютерной математики МЛТЬЛБ с помощью функции Дштооп [4], при начальном приближении х0 = [2 1 1 3 2 2]т. Результаты вычислений приведены ниже.
Д = 0.4262 аш = 1.9000 1.9000 1.9000
1.1000 1.1000
2.8000
Как видно, они совпадают с полученными при помощи предложенного алгоритма, что подтверждает его работоспособность.
Заключение. Разработанный алгоритм и реализующая его программа могут эффективно применяться в составе интегрированного пакета для решения оптимизационных задач для решения задачи поиска минимума скалярной функции большого числа переменных при наличии ограничений на переменные типа нестрогих неравенств. Алгоритм эффективен, если априори известно, что минимизируемая функция не имеет точек экстремума внутри области ограничений и по своему виду близка к линейной. Достоинствами алгоритма являются его простота с вычислительной точки зрения, возможность работать с большим - до сотни и более - числом п аргументов и в высокой скорости поиска точки минимума. Сходимость алгоритма всегда гарантируется ввиду конечности точек поиска (вершин гиперпараллелепипеда) 2п.
х
х
4
х
х
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
1. Аоки М.Введение в методы оптимизации. М.: Наука, 1977.
2. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.
3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Лаборатория Базовых Знаний, 2000.
4. Дьяконов В., Круглов В. Математические пакеты расширения MATLAB. Специальный справочник. СПб.: Питер, 2001.
SCALAR FUNCTION SEARCH ALGORITHM MINIMIZATION OF MANY VARIABLES WITH INTERVAL LIMITATION ON VARIABLES
Y.G. BOJARINOV, Ph.D.
The Smolensk Branch of the Moscow Power Engineering Institute
(Technical University) Energeticheskiy proezd, 1, Smolensk, 214013, Russia
The article deals with the search scalar function algorithm minimization of many variables with implicit function and interval limitation on variables. The main idea of algorithm, that the least value the function takes at one of the hype parallelepiped apexes - the area ofpossible values argument, is in successive bypass of apexes from the initial point to the function decrease. The program algorithm realization is suggested in the MATLAB sphere.
Key words: minimization algorithm, scalar function of many variables, many variables, program algorithm realization.
© Ю. Г. Бояринов, 2009
Материал поступил в редакцию 22.09.2009
УДК 338.984
ПОСТРОЕНИЕ ИТЕРАЦИОННОЙ МОДЕЛИ ОПРЕДЕЛЕНИЯ И КОНТРОЛЯ КЛЮЧЕВЫХ ПОКАЗАТЕЛЕЙ НА ОСНОВЕ МЕТОДОЛОГИИ СИСТЕМЫ СБАЛАНСИРОВАННЫХ ПОКАЗАТЕЛЕЙ
С. В. КОЗЛОВ, аспирант кафедры АСУ А. В. КОЗЛОВ, аспирант кафедры АСУ А. А. МИЦЕЛЬ, д-р техн. наук, профессор кафедры АСУ
Томский государственный университет систем управления и радиоэлектроники пр. Ленина, 40, г. Томск, Томская область, 634040, Россия
В данной статье определены основные недостатки методологии системы сбалансированных показателей. На основании чего предложен подход многослойного (много итерационного) построения системы показателей и связей между ними.
Ключевые слова: система сбалансированных показателей, недостатки ССП, многослойные стратегические карты.
Введение
В последние годы все больше руководителей различных организаций делают ставку на стратегическое развитие компании, а не на достижение краткосрочных целей в ущерб будущих перспектив развития. В связи с этим появляется необходимость в инструменте, который позволил бы руководителям компаний перевести стратегические цели в реальные действия. В
90-х годах 20 века авторами Р.Каплан и Д.Нортон была предложена методология ССП
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.