<<
>>

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

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

F [302,300,176,177], иногда с безразмерным значением функционалов. На рис. 4.23 представлен граф поиска для данного алгоритма, использующего оптимизацию по Парето.

Граф поиска и сам алгоритм поиска во многом аналогичен варианту задачи формирования межцеховых расписаний для нескольких ГПК и СОУ с одинаковым составом функционала и ограничений (см. п.п. 4.4.3.1), но имеется следующее отличие.

На каждой аддитивной вершине поиска определяется текущее значение каждого конкретного функционала из (4.70). Первый проход по графу

от вершины S^ до вершины стока / позволяет получить первое допустимое решение задачи, если оно существует на имеющемся составе ограничений, в виде вектора текущих значений функционалов из (4.69)

F1^,^,...,^}, (4.71),

который используется в качестве нижней границы.

241

Пример использования

СОУ различными

заявками

* F4F1 Fl Fl

\ Г 2'"' /

Рис. 4.23. Граф поиска в многокритериальной задаче

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

Flфункционалов из данного множества, т.е. ищутся неухудшаемые векторы

F1 на текущей ветви графа. Если вектор не ухудшается, то данная аддитивная вершина включается в расписание, если нет (найдено неулучшае-

242

мое частное решение), то дальнейшие вычисления на данной ветви графа не производятся.

Поиск оптимума возможен на двух видах Парето-множествах - строгом и нестрогом.

В первом случае (рис.4.24.а) область строгого Парето-

множества Fp* составляют те векторные функционалы, для которых, по мере их отыскания, не ухудшается ни один из критериев из предыдущего вектора, т.е.

а) б)

Рис.4.24. Парето-оптимальные множества

VF'eF^IMl,//) V/, F^F1.-1

(4.72)

^1

Данное множество Fri в ряде случаев, обычно - при небольшой

размерности задачи, достаточно ограничено и поэтому возможно исполь-

Р9 зование нестрогих Парето-множеств FrL таких (рис.4.24.б), для векторов

которых справедливо выражение

VF/eFP2(/ = (1//) 3J\J = {j>l}v#J(4.73)

J J

V/ F\>Fl.

J J J

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

243 После окончания поиска и перебора всех вершин графа на последнем //-м шаге получается решение оптимальное относительно первоначального базиса для текущей ветви:

F»\F?,F%,...,F»

(4.74)

Рис.4.25. Парето-оптимальные множества для разных ветвей графа

Далее множество Парето дополняется теми решениями, которые были получены для других ветвей графа, поскольку для каждой ветви возможно свое непересекающееся множество решений в силу того, что первоначальное допустимое решение зависит от конкретной последовательности ветви поиска. На рис.4.25 показан случай, когда для разных ветвей возможны свои неулучшаемые решения (помечены итерациями «2»). В результате поиска по всему графу мы получаем полное множество неулуч-шаемых решений, на котором можно либо выбрать наилучший вариант с лучшими значениями всех частных критериев, либо, в случае отсутствия такого варианта, провести дальнейшую фильтрацию. Фильтрация решений на Парето-множествах предполагает различные методы выбора оптимального решения среди имеющихся равноценных с точки зрения сложности их однозначного выбора.

Рассмотрим варианты.

244 Например, критерий вида

Lift

Р=Ш)~ S F.//|)-»min (4.75)

М J j=i J

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

Интегральный критерий общего вида

F = \yf JLQF* -FjP'l/lFJ -FJOP* |)2 ->min (4.76)

где F. и F. - наилучшие и наихудшие значения для функционала

F1-, позволяет находить решения с равномерным ухудшением, по правилу

Лапласа [116], частных критериев, представленных в виде безразмерных величин.

В результате выбора оптимума решения на множестве Парето мы

имеем множество частных расписаний в ,0 ,...,0^ для всех g ГПК и СОУ. Представленный способ не дает полной оптимальности решения этой комплексной многокритериальной задачи, но характерной чертой яв-ляется отсутствие искажения расписания, что присуще многим многокритериальным задачам с использованием ранжирования критериев и использованием весовых коэффициентов, поскольку при разнородности отдельных функционалов в (4.69) - использование в одной модели критериев стоимостного и временного характера и т.д., достаточно трудно осуществить равноправное ранжирование. Нахождение оптимума для данного случая, даже локального, возможно при наличии хотя бы одного допустимого решения на графе поиска. Наилучший эффект данный метод может дать на задачах с большой размерностью и чем больше размерность задачи, тем больше разница между первым базисом F, и неким окончательным решением Fц.

245

Оптимизация по Парето может быть использована также при использовании векторного критерия для случая формирования расписаний для локальных систем - ГПК, цехов и участков, модели которых представлены в п.п. 4.2, 4.3,4.4.

<< | >>
Источник: Загидуллин Равиль Рустэм-бекович. Система оперативно-календарного планирования автоматизированного механообрабатывающего мелкосерийного производства на основе комплексных моделей [Электронный ресурс] : диссертация... д-ра техн. наук : 05.13.06. - Москва: РГБ,2007. - (Из фондов Российской Государственной Библиотеки).. 2007

Еще по теме 4.5.3.2.1. Особенности алгоритма построения оптимального расписания для многокритериальной задачиОптимизация с помощью оптимума Парето:

  1. Алгоритм поэтапного построения оптимального расписания для многокритериальной задачи (остаточный метод)
  2. 4.2.Э.1. Процедура прямого хода в алгоритме формирования оптимального расписания
  3. 4.5.3.2.2. Решение задач многокритериальной оптимизации при построении расписаний с использованием неопределенных весовых коэффициентов
  4. 4.2.Э. Алгоритм формирования расписания работ в ГПК
  5. 6.3. Поиск оптимальных параметров расписаний на модели СМО
  6. 7.4.2. Результаты построения расписаний и их моделирования
  7. 6.2. Оценка расписаний с помощью моделей СМО
  8. 6. Улучшения по Парето, эффективность по Парето и теоремы благосостояния
  9. 5.4. Особенности алгоритма формирования работ в ГПС с учетом дифференциации операций
  10. 4.5.3.2. Математическая модель формирования межцеховых расписаний для нескольких ГПК и СОУ с различным составом функционала и ограничений
  11.     ШПАРГАЛКА ДЛЯ РАЗБОРА     Об алгоритме морфемного, анализа
  12. 4.5.3.1. Математическая модель формирования межцеховых расписаний для нескольких ГПК и СОУ с одинаковым составом функционала и ограничений
  13. 4.4 Выбор оптимальных параметров для производства утеплительных плит из соломы зерновых культур
  14. 2.2. ОПРЕДЕЛЕНИЕ ХАРАКТЕРИСТИК МАСС ГОТОВЫХ ДОЗ НА ВЫХОДЕ ИЗ ДОЗАТОРА ДЛЯ РАЗЛИЧНЫХ АЛГОРИТМОВ РАБОТЫ МГД
  15. Особенности построения публицистических текстов
  16. РАЗДЕЛ 2. Оптимум потребителя
  17. Иссерс О.С., Кузьмина Н.А.. Интенсивный курс русского языка: Пособие для подготовки к тестированию и сочинению в правилах, алгоритмах и шпаргалках. - Москва, Центр тестирования - 164 с., 2002
  18. Некоторые особенности построения индексов промышленной продукции в других капиталистических странах и в международных организациях
  19. Т. Д. Гордон, М. Д. Раффенспергер ПОСТРОЕНИЕ ДЕРЕВА ЦЕЛЕЙ ДЛЯ ПЛАНИРОВАНИЯ ТЕОРЕТИЧЕСКИХ НАУЧНЫХ ИССЛЕДОВАНИЙ