<<
>>

2.1. Численный метод решения многокритериальной задачи дискретного нелинейного программирования

При совершенствовании ССМП значительное место отводится задачам формирования эффективных управленческих решений с помощью задачи дискретной векторной оптимизации вида:

, (2.1)
, (2.2)
, (2.3)

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

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

В работе [23] приведена значительная библиография работ, посвященных методам решения линейных задач вида (2.1) – (2.3). Как отмечено в работе [25], решение однокритериальных «задач о назначениях» практически значимой размерности традиционными численными методами требует значительных затрат машинного времени.

В работе [26] утверждается, что использование линейной свертки критериев в задачах линейного дискретного программирования приводит к потере 40% точек паретооптимального множества решения таких задач.

В связи с тем, что множество допустимых решений задачи (2.1) – (2.3), которое определяется как:

, (2.4)

является дискретным множеством, то множество достижимости [27] этой задачи также будет дискретным множеством. Для дискретного множества не выполняются условия выпуклости множества, что не позволяет корректным образом применять при решении задачи (2.1) – (2.3) классический метод линейной свертки целевых функций [26], основанный на применении теоремы С.Карлина [28].

Предположим, что множество (2.4) содержит конечное число векторов , сформированных путем полного перебора значений векторов [19], или использования рандомизированных методов генерации таких векторов [21], удовлетворяющих условиям (2.2) – (2.3).

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

,

(2.5)

Как известно [27, 23], оптимизация решений по Парето основывается на выделении во множестве наилучших (паретооптимальных) точек с использованием отношения предпочтения, заданного на множестве возможных решений.

В нашем случае, при решении задачи (2.5) можно утверждать, что -ая точка этого множества является предпочтительнее, чем -ая точка множества , если для этой пары точек при одновременно выполняются все условия вида:
,

(2.6)

причем хотя бы одно неравенство строгое.

Последовательное сравнение возможных решений между собой с исключением из рассмотрения непредпочтительных решений составляет основу метода решения задачи (2.5). Отметим, что множество эффективных (компромиссных) решений (множество Парето) состоит из несравнимых между собой вариантов решений [29].

В работах [23, 29] для выделения оптимальных по Парето точек в континуальном множестве использовалось понятие ортанта, который представляет собой выпуклый острый конус без вершины, порожденный единичными ортантами пространства целевых функций (оценок). При этом утверждается, что рассматриваемая точка является паретооптимальной тогда и только тогда, когда во внутренность ортанта, сдвинутого в эту точку, не попадет ни одна из точек множества .

В связи с дискретностью задачи (6) для выделения в нем эффективных точек будем использовать выпуклый многогранный ортогональный конус, сдвинутый из начала координат в вершину рассматриваемой точки , который формально определим как:

(2.7)

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

10.

Построение приближенного представления множества допустимых решений задачи с использованием условий (2.2) – (2.3).

20. Формирование в пространстве критериев (6) соответствующего приближенного представления множеств достижимости (множества оценок) путем вычисления значений критериев (2.1).

30. Выделение в множестве подмножества паретооптимальных (эффективных, неулучшаемых) решений с использованием понятия ортогонального конуса вида (2.7).

В предлагаемом методе, существенное значение, с точки зрения точности получаемых результатов, имеет объем выполняемых статистических экспериментов. Для получения приемлемых для практики результатов в данном методе предлагается использовать следующее правило останова: «Процесс последовательного выполнения этапов 10 – 30 завершается, если при статистических экспериментах достигается заданная точность сходимости», т.е. полученное решение при статистических экспериментах отличается от решения при -1 статистических экспериментах в пределах заданной точности.

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

Однако, как показала практика, количество паретооптимальных решений может быть настолько большим, что разработчику системы будет сложно выбрать такое решение. В этом случае предлагается использовать принцип «близости к идеальной точке», который заключается в следующем. Из всего множества паретооптимальных решений выбираются следующие значения критериев , и , . Тогда близким к идеальному решению будет решение из паретооптимального множества, координаты которого находятся на минимальном расстоянии от идеальной точки (см. рис.2.1).

Рис. 2.1.

<< | >>
Источник: А.В. Бутузова и др.. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИЗАЦИИ СЛУЖБЫ СКОРОЙ МЕДИЦИНСКОЙ ПОМОЩИ МОНОГРАФИЯ. 2011

Еще по теме 2.1. Численный метод решения многокритериальной задачи дискретного нелинейного программирования:

  1. Решение логических задач
  2. 2.1 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. 2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  4. 3.1. Методы решения образовательных, развивающих и воспитательных задач
  5. 12.2. Аналитический метод решения задач параметрического программирования
  6. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  7. 11.2. Методы решения оптимизационных задач
  8. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  9. Численные методы решения дифференциальных уравнений.
  10. Раздел 1. ЧИСЛЕННЫЕ МЕТОДЫ
  11. 1.6. Численные методы алгебры
  12. 1.8. Численные методы решения обыкновенных дифференциальных уравнений
  13. 10. Практическое занятие №10 "Численные методы решения дифференциальных уравнений"
  14. 2.1. Численный метод решения многокритериальной задачи дискретного нелинейного программирования
  15. 2.5. Задача оптимизации числа диспетчеров и бригад скорой медицинской помощи
  16. СОДЕРЖАНИЕ
  17. 4. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЖЕСТКИХ СИСТЕМ.