Понятие векторной операции.

Мы рассмотрели задачу исследования операций, где требовалось так выбрать решение так, чтобы максимизировать (или минимизировать) один-единственный показатель эффективности W.
На практике часто встречается случай, когда эффективность операции приходится оценивать не по одному, а сразу по нескольким показателям: W1,W2,...,Wk; причем одни из этих показателей необходимо сделать больше, другие-меньше.

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

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

Отдельные показатели эффективности будем рассматривать как координаты некоторого вектора W=W(W1,W2,...)
Задачу ИО можно сформулировать следующим образом:
Имеется некоторая операция О, эффективность которой оценивается с помощью векторного критерия эффективности W=W(W1,W2,...) . Необходимо найти такую стратегию Х по управлению операцией О, чтобы она удовлетворяла следующим условиям:

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

    Рассмотрим основные проблемы, с которями приходится сталкиваться при исследовании операции с векторным критерием эффективности.

    Основные проблемы векторной оптимизации.


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

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

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

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

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

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

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

    Подходы к решению проблем векторной оптимизации.

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

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

    Из рис.1 видно, что область совпадает с дугой ВС - частью границы области.

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

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


    Рис.1

    Самой простой разновидностью принципа равномерности является принцип равенства. В этом случае оптимальным компромиссным решением считается такое, которое обеспечивает равенство всех локальных критериев (рис. 2,а).
    Данный принцип является весьма "жестким" и может приводить к решению вне области (рис. 2, б) или совсем не иметь решения
    (рис. 2, в), особенно в случае дискретных задач (рис. 2, г). На основании геометрической иллюстрации легко заметить, какими недостатками обладает данный принцип. Математически этот принцип-оптимальности может быть записан следующим образом:


    Рис.2

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

  • Принцип справедливой абсолютной уступки состоит в том, что справедливым считается такой компромисс, при котором суммарный абсолютный уровень снижения одного или нескольких критериев не превосходит суммарного абсолютного уровня повышения других критериев.
    Для иллюстрации сказанного рассмотрим пример двумерной векторной задачи, т. е. . Пусть требуется сравнить два решения: и принадлежащие области
    (рис.3).

    Рис.3
    Вычислим величину суммарной абсолютной уступки при переходе от к Очевидно, что
    Т.е, улучшение второго критерия меньше, чем ухудшение первого. Следовательно, на основании принципа абсолютной уступки решение лучше чем

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

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

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

    Важным преимуществом рассмотренного принципа является то, что он инвариантен к масштабу измерения критериев.

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

    Важным здесь является решение вопроса о подходе к выбору идеального вектора.
    Рассмотрим некоторые из способов:

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

    2. В качестве идеального вектора может приниматься такой, компонентами которого являются максимумы локальных критериев:

      Недостатком этого способа является то, что он существенно зависит от максимально возможного уровня локальных критериев, определяемых условием задачи.
    При задании приоритета критериев (проблема 4) распространены следующие подходы:
    Компоненты вектора обычно обладают следующими свойствами:
    {1}
    Как вектор так и вектор обычно задаются при постановке задачи и должны учитываться в ходе отыскания оптимального решения.

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

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

    Hosted by uCoz