36211

Классы численных методов построения множеств неулучшаемых решений. Основные теоремы для поточечных методов и алгоритма последовательного выбора

Доклад

Математика и математический анализ

Процедуры первой группы осуществляют поочередный поиск отдельных неулучшаемых точек как решений вспомогательных скалярных задач. В них на каждой итерации получается целое множество “неплохих†точек которое на последующих шагах постепенно улучшается. Генератор на каждой итерации порождает набор точек zk а ФВ осуществляет отбор в некотором смысле лучших из них: Генератор множеств точек zk Функция выбора С Для организации выбора необходимо произвести парные сравнения исходных вариантов и отбросить те из...

Русский

2013-09-21

31.5 KB

1 чел.

9  Вопрос

Классы численных методов построения множеств неулучшаемых решений. Основные теоремы для поточечных методов и алгоритма последовательного выбора.

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

Определение 2.1. Будем говорить, что некоторая функция (у), у Q, убывает (не возрастает) по бинарному отношению R, определенному на элементах множества Q, если для любых у, z  Q из отношения (у, z)  R следует          (у) < (z)  ( (у)  (z) ).

Теорема 2.1. (основная для поточечных методов). Если в точке у*  Q достигается минимум некоторой функции (у), убывающей по бинарному отношению R, то  у* СR (Q).

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

Будем рассматривать методы, представляющие собой суперпозицию двух процедур, работающих поочередно: генератора и функции выбора (ФВ). Генератор на каждой итерации порождает набор точек zk, а ФВ осуществляет отбор в некотором смысле лучших из них:

Генератор множеств точек zk                 Функция выбора С()

Для организации выбора необходимо произвести парные сравнения исходных вариантов и отбросить те из них, для которых найдется доминирующий элемент. Если исходное множество велико, то метод попарного сравнения трудоемок, т.к. в общем случае необходимо произвести N(N – 1) / 2 сравнений, где N – число сравниваемых вариантов. Более эффективен следующий алгоритм последовательного выбора, который производит постепенное накопление элементов искомого множества.

Обозначим X = {xi} – исходное множество сравниваемых вариантов.  Для него будем производить отсев плохих точек и получение множества R(Х), содержащее альтернативы, неулучшаемые по заданному бинарному отношению R.

     begin   R(Х) := {х1};

                 for   j := 2   to   N   do

                      R(Х) := CR ({ xj } R(Х) ) ;

     end.

Обычно множество недоминируемых точек содержит значительно меньше элементов, чем исходное, т.е. n = | R(Х) | << |Х| = N. В этом случае нужно провести O(Nn) сравнений, т.е. намного меньше, чем при всевозможных парных сравнениях.

Данный алгоритм корректен, т.е. дает верное решение, если для любых множеств Z, Y X выполняется соотношение:

            CR ( Z Y) = CR ( Z CR(Y) ),                              (2.1)

т.е. выбор можно производить как последовательно – сначала на Y, получив CR(Y), потом на Z  CR(Y), так и сразу на объединении Z  Y.

Теорема 2.2. (основная для алгоритмов последовательного выбора). Соотношение  (2.1)  выполняется, если отношение R является качественным порядком (асимметричным и транзитивным).

Для справок: Отношение R асимметрично, если R R–1= , т.е. пересечение отношения R с обратным отношением пусто.

Эквивалентное определение асимметричности: из двух отношений (x, y) R и (y, x)R одно не выполняется.

Примеры асимметричных отношений:  ">",  "<", "быть начальником".                                                                                           

Отношение R транзитивно, если для любых x, y, zA из того, что (x, y)R и (y, z)R следует (x, z)R.

Примеры транзитивных отношений:  ">",  "<", "=".

Не транзитивным является отношение "". Действительно, пусть x = 2,      y = 3,  z = 2, тогда справедливо x y и y z, но x = z, т.е. (x, z)R.


 

А также другие работы, которые могут Вас заинтересовать

32618. Докладно описати основні пристрої вантажної станції (ВС): -колійний розвиток ВС - сортувальні пристрої; -вимоги до проектування основних пристроїв ВС 69 KB
  Для выполнения работы по приему отправлению и обработке поездов и обслуживанию пунктов погрузки – выгрузки на ГС имеются пути сортировочные устройства грузовой район а в отдельных случаях – устройства для экипировки локомотивов и ремонта вагонов производственнотехнические здания и прочие сооружения. Путевое развитие включает приемоотправочные сортировочные погрузочновыгрузочные выставочные соединительные и ходовые пути. Приемоотправочные пути используются для приема и отправления поездов передач на сортировочную или...
32619. Дати докладну характеристику розв’язок перехрещень в вузлах 900 KB
  Основное требование ко всем пересечениям маршрутов в одном уровне заключается в том что эти пересечения не должны снижать пропускную способность ниже необходимой в период интенсивного движения и создавать угрозу безопасности движения. Пересечения в одном уровне устраиваются при благоприятных топографических условиях относительно небольших размерах движения. Безопасность движения поездов обеспечивается с помощью устройств автоматики и сигнализации предохранительных тупиков. Развязки в одном уровне осуществляются чаще всего с...
32620. Розрахунок конструктивної висоти сортувальної гірки на сортувальній станції 571.5 KB
  Профільна висота головної дільниці h1 встановлюється з урахуванням найбільшого використання допустимої швидкості входу Vвх розрахункового бігуна вагою 85 т ωо=05 Н кн. в уповільнювачах 1 ГП при сприятливих умовах скочування: де Vo – найбільша швидкість розпуску приймається 25 м с; g′ох – розрахунковий параметр для ОХ бігуна м с2; де g – прискорення вільного падіння 981 м с2; n – кількість осей бігуна ОХ 4; q – вага бігуна ОХ 85 т; hωо1 hск1 – питома робота сил опору основного і від стрілок та кривих в межах головного дільниці l1...
32621. Докладно описати питання щодо пасажирської технічної станції (ПТС): 1) призначення і класифікація; 2) основні пристрої; 3) основні операції, що виконують на станції; 4) умови застосування; 5) переваги та недоліки окремих ПТС 116.5 KB
  1 ПТС призначаються для переформування ремонту очищення і екіпірування пасажирських составів. Станції бувають крупні 1520 составів за добу і середні 815.20 составів. На технічних парках менше ніж 68 составів.
32622. Аналіз схем двосторонніх станцій с послідовним розташуванням основних парків. Описати системи гіркової автоматики 216.5 KB
  Для комплексної механізації і автоматизації процесу сортування вагонів сортувальні гірки обладнуються локальними системами автоматики ГАЦ ГПЗУ АРС АЗСР ТГЛ пристроями зв’язку телебачення сигналізації. Під час роботи в маршрутному режимі оператор натисканням кнопки яка відповідає номеру підгіркової колії встановлює маршрут для кожного відчепу перед розпуском його з гірки. Система АСУ РСГ дозволяє регулювати швидкість насуву і розпуску составів швидкість руху відчепів з гірки керувати маршрутами руху відчепів з контролем...
32623. Докладно описати такі питання: визначення спеціальної вантажної станції, спеціалізація спеціальних вантажних станцій,основні операції,які виконують на спеціалізованих вантажних станціях 677.5 KB
  Докладно описати такі питання: визначення спеціальної вантажної станції спеціалізація спеціальних вантажних станційосновні операціїякі виконують на спеціалізованих вантажних станціях. Спеціалізовані вантажні станції це вантажні станції що будуються в пунктах масової переробки однорідних вантажів і забезпечують ритмічність і потоковість обробки масових вантажів і прискорену обробку рухомого складу на станції ефективне використання вантажнорозвантажувальних механізмів і скорочення обсягу роботи сортувальних станцій за рахунок формування...
32624. Дати технічну характеристику колієпроводів 992.5 KB
  Минимальная длина путепроводной развязки в плане определяется в зависимости от радиуса кривой и угла пересечения. Рис 1 – К расчету путепроводной развязки в плане. Длина путепроводной развязки в плане должна быть не менее длины развязки в профиле Lnл Lпp Длина путепроводной развязки в профиле зависит от характера подходов. Минимальная длина развязки в профиле: Lпр=lпод0.
32625. Особливості проектування вузлових дільничних станцій (ВДС). Принципи розташування основних пристроїв на дільничних станціях 98 KB
  Докладно описати такі питання: особливості проектування вузлових дільничних станцій ВДС; принципи розташування основних пристроїв на дільничних станціях; розрахунок числа приймальновідправних колій на ВДС При проектировании УУС следует выполнять такие требования: 1 на подходах к станции должны предусматриваться развязки маршрутов в одном или в разных уровнях; 2 расположение главных путей на подходах к станции конструкции горловин должны обеспечивать одновременный прием и отправление поездов со...
32626. Описати принципи і особливості проектування залізничних вузлів великих і столичних міст 559.5 KB
  В генеральной схеме развития узла особенно тщательно должна быть проработана охрана окружающей среды бережного отношения к природным ресурсам минимального использования земель и угодий ценных для других отраслей хозяйства отдыха населения и дальнейшего развития жилищного строительства. При проектировании железнодорожных узлов необходимо руководствоваться следующими принципами: общая эффективность комплексная оптимизация концентрация децентрализация специализация сохранение равновесия и пропорциональности развития отдельных...