Главная страница

Решение многокритериальной оптимизационной задачи распределения ресурсов


НазваниеРешение многокритериальной оптимизационной задачи распределения ресурсов
Дата10.02.2016
Размер69.3 Kb.
ТипРешение

С.Н. Боранбаев


Решение многокритериальной оптимизационной задачи распределения ресурсов


(Евразийский национальный университет имени Л.Н.Гумилева, г.Астана)
Статья посвящена разработке математического и программного обеспечения решения многокритериальных оптимизационных задач распределения ресурсов сети. Предложен подход к решению рассматриваемых задач.

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

Решению задач многокритериальной оптимизации посвящено много статей и книг, в частности можно отметить работы [3-12] и обзоры [13,14].

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

а ее качество оценивается вектор-функцией

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

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

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

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

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

Рассмотрим следующую многокритериальную оптимизационную задачу.


Предполагаем, что область не пустая, ограниченная. Функции - выпуклы, непрерывно дифференцируемы.

Поиск решения в рассматриваемой задаче многокритериальной оптимизации проводится в два этапа.

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

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

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

Определим . Пусть , в противном случае можно перейти к шагу и проводить новое назначение критериев.

Рассмотрим последовательность , которая является точками безусловного минимума последовательности функций.
, (1)

где , , вычисляются следующим образом:
(2)

Примем

Рассмотрим
,
с границей . Очевидно, что . Положительные величины использованы с целью выполнения

. Учитывая специфику функции , в качестве начальных точек для последовательной минимизации можно использовать .
Теорема 1. Пусть функции - выпуклы, непрерывно дифференцируемы. Существует , что

.

Доказательство. Как видно, компактно. Из непрерывности функции следует, что функция непрерывна внутри области , а при и функция стремится к . Следовательно, функция достигает минимума в .
Теорема 2. Пусть – выпуклые функции и произвольный положительный вектор, тогда .

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

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

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

Следствие. Если , то ,

Таким образом, если , то имеется возможность, по крайней мере, в достаточно малой окрестности улучшить значения критериев. Однако в реальных практических задачах в качестве решения может быть принято то решение, которое удовлетворяет определенным критериальным ограничениям. То есть можно принять его в качестве оптимального решения, хотя оно и улучшаемое. Часто такие решения принимаются в системах реального времени, когда на принятие решения отпускается ограниченное время.
ЛИТЕРАТУРА


  1. Boranbayev S.N. Mathematical Model for the Development and Performance of Sustainable Economic Programs // International Journal of Ecology and Development, Vol. 6, No. W07, 2007, р.15-20.

  2. Boranbayev S.N. Optimality condition in optimization network tasks // Program 989 American Methematical Society Meeting. University of Colorado. Boulder. USA. 2003.

  3. Моцкус Й.Б. Многоэкстремальные задачи в проектировании. –М.: Наука, 1976.

  4. Бабий А.Н. Алгоритм нахождения значения глобального экстремума функции нескольких переменных с заданной точностью // Кибернетика, 1978, №5.

  5. Батищев Д.И., Любомиров А.М. Применение методов классификации образов к отысканию глобального минимума функции нескольких переменных // Вопросы кибернетики, 1985, т.122.

  6. Букатова И.Л. Глобальный поиск в эволюционном моделировании// Вопросы кибернетики, 1985, т.122.

  7. Васильев Ф.П. Численные методы решения экстремальных задач. –М.: Наука, 1980.

  8. Евтушенко Ю.Г. Методы решения экстремальных задач и их применения в системах оптимизации. –М.: Наука, 1982.

  9. Жилинскас А.Г. Глобальная оптимизация. Вильнюс, 1986.

  10. Моисеев Н.Н. Элементы теории оптимальных систем. –М.: Наука, 1975.

  11. Стронгин Р.Г. Численные методы многоэкстремальной оптимизации. –М.: Наука, 1978.

  12. Чичинадзе В.К. Решение невыпуклых, нелинейных задач оптимизации. –М.: Наука, 1983.


Боранбаев С.Н.

Желілердің құнарларын үлестіру көпкритериялы оптимизациялық есепті шешу

Мақала желілердің құнарларын үлестіру көпкритериялы оптимизациялық есептердің математикалық және программалық қамтамасыздығына арналған. Қарастырылған есептердің шешілу әдістері ұсынылған.
Boranbayev S.N.

The decision is a lot of criteria of optimizing tasks of distribution of resources

Article is devoted to development mathematical and the software of the decision of criteria of optimizing tasks of distribution of resources of a network having many. The approach to the decision of examined tasks is offered.