114



  1. Задачи векторной оптимизации.

    1. Основные понятия и определения.

Напомним, что классической задачей оптимизации или задачей математического программирования является следующая:

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

( 11.1.0 )

- векторная функция с компонентами

- обычно называется целевой функцией,

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


Множество называется допустимым , то есть допустимое множество – это части пространства , где выполнены ограничения : .


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

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


Работы по скалярной оптимизации имеют два основных направления:

  • выявление условий единственности решения задачи ( 11.1 .0 ) , либо условий отсутствия решений;

  • разработка численных методов решения задачи ( 11.1 .0 ).


Эти два направления тесно связаны, так как разработка численных методов обычно предполагает выполненными определенные условия ,следующие из 1-го направления.

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


Напомним, что основными численными методами решения задачи ( 11.1 .0 ) являются:

  • методы штрафных функций ;

  • прямые методы, использующие только значения функций;

  • градиентные методы ;

  • метод случайного поиска.


И, наконец, в заключение напоминания о задаче скалярной оптимизации, заметим, что в настоящее время существуют самые разнообразные пакеты прикладных программ, решающих задачу ( 11.1 .0 ) . Это пакеты на самых распространенных языках / FORTRAN, BASIC, PASCAL, C/ и для различных вычислительных машин /ЕС, СМ, ПЭВМ/.


Задача, решению которой посвящена данная работа, состоит в нахождении минимума векторной функции

при некоторых ограничениях и может быть записана так :

( 11.1.0 )

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

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



Итак, мы будем заниматься задачей ( 11.1 .0 ), которая в разных источниках может называться как :

  • задача векторной оптимизации;

  • многокритериальная задача оптимизации;

  • задача многоцелевой оптимизации.


Дело в том, что реальные задачи , а особенно задачи , связанные с созданием АСУ, САПР, задачи системного анализа, теории больших систем и так далее, в основном многокритериальные, поэтому сама жизнь требует умения их решать, что подчеркивает актуальность проблемы.

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

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

С математической точки зрения, задача ( 11.1 .0 ) может иметь решение только в том случае, если оно совпадает со всеми решениями скалярных задач:

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

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

  1. , ;

  2. , .


По-видимому, в данном случае, решения несравнимы.


В дальнейшем будем использовать следующие понятия и определения.

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

предыдущий критерий важнее всех последующих , то есть - самый важный, следующий за ним и так далее.


Определение 1.

Из двух точек точка называется доминирующей по отношению к (), если для всех выполняется и, кроме того , по крайней мере для одного :