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

На правах рукописи

А /

00460252* Федорин Андрей Николаевич

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ РАНЦЕВОГО ТИПА: РАЗРАБОТКА И СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ (технические науки)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород 2010

2 О 2010

004602524

Работа выполнена на кафедре информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского

Научный руководитель: доктор технических наук, профессор КОГАН ДМИТРИЙ ИЗРАИЛЕВИЧ.

Официальные оппоненты:

доктор технических наук, профессор ФЕДОСЕНКО ЮРИЙ СЕМЕНОВИЧ, кандидат физико-математических наук, доцент ШАПОШНИКОВ ДМИТРИЙ ЕВГЕНЬЕВИЧ.

Ведущая организация: МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЙ

Защита диссертации состоится «_2010г.

в аудитории ЛИЭ корпуса <€- Нижегородского государственного университета им. Н.И. Лобачевского в часов на заседании

Диссертационного совета Д 212.166.13.

Заверенные отзывы просим направлять по адресу:

бОЗЙЮ, Н. Новгород,

проспект Гагарина, 23, Нижегородский государственный университет им. Н.И. Лобачевского, Диссертационный совет Д 212.166.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета им. Н.И. Лобачевского.

Автореферат разослан «Л-Ь »

2010г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук,

доцент

Савельев Владимир Петрович

Актуальность темы исследования

Классическая задача о ранце (КЗР) относится к числу широко известных

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

Начиная с 60-70-х гг. XX века стали рассматриваться различные модификации КЗР. В частности, была изучена КЗР с дробимыми предметами и КЗР в многомерной постановке. Одновременно исследовались КЗР, где требование булевозначности переменных заменено требованием принадлежности их некоторому множеству неотрицательных целых чисел в ограниченном диапазоне. Встречаются также постановки КЗР с нелинейными критериями, в частности, сепарабельными. Введение обобщений вызвано стремлением моделировать более широкие классы ситуаций, возникающих в практике планирования и оперативного управления.

Наиболее существенным шагом на пути расширения практической применимости ранцевых моделей стало исследование задачи о ранце с несколькими критериями. Последнее десятилетие значительное внимание уделяется именно таким постановкам ранцевых задач. Можно утверждать, что все задачи, реально возникающие в системах управления по сути своей многокритериальны. Это объективно связано с тем, что в каждой экономической, производственной, транспортной системе имеется ряд участников, каждый из которых по-своему оценивает качество принимаемых решений. Кроме того, некоторые участники могут оценивать принимаемые решения по нескольким показателям. Задачам о ранце в многокритериальных постановках посвящен, в частности, ряд работ Д.И. Батищева, В.А. Емеличева, Д.И. Когана, М.В. Лейкина, И.И. Меламеда, И.Х. Сигала, 111. Figueira, М.Н.

Karvvan, K.Klamroth, J. Teghem, L. Thiele, E.L. Ulungu, B. Villarreal, M. Wiecek, E. Zitzler и др.

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

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

Цель работы

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

Методы исследования

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

Научная новизна

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

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

3. На основе анализа разнообразных концепций эволюционно-генетических алгоритмов (ЭГА) решения задач многокритериальной оптимизации и, в частности, многокритериальной задачи о ранце, реализованы собственные модели ЭГА, учитывающие специфику задачи и преодолевающие ряд недостатков существующих подходов.

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

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

6. Путем введения критериев специального вида (не всегда линейных) и ряда дополнительных ограничений построены новые модификации стандартной многокритериальной многомерной задачи о ранце (ММЗР); средствами расширенных ранцевых моделей адекватно описываются более широкие классы задач принятия решений.

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

8. Разработанный в процессе изучения модифицированных ММЗР математический аппарат успешно применен для решения задачи оптимальной загрузки судов, адекватно формулируемой в рамках многокритериальной задачи о ранце с аддитивными и точечными критериями.

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

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

Теоретическая и практическая значимость

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

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

Апробация полученных результатов

По теме диссертационной работы делались сообщения и доклады на юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК (2003г.), VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004г.), XIV Международной конференции по проблемам теоретической кибернетики (Пенза, 2005г.), конференции -«Технологии Microsoft в теории и практике» (Нижний Новгород, 2006г.), 11-ом Международном научно-промышленном форуме «Великие Реки'2009 / ICEF. Проблемы и перспективы развития учебно-научно-инновационных транспортных комплексов» (2009г.), научных семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Реализация результатов работы

Программная система, составляющая прикладную часть диссертационной работы, прошла апробацию во ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова» при решении задач размещения компонентов интегральных схем (ИС), возникающих при проектировании больших интегральных схем на базовых матричных кристаллах с аналоговой частью (БИС АБМК); имеется акт об использовании.

Выполненная в ФГОУ ВПО «Волжская государственная академия водного транспорта» научно-исследовательская работа по теме «Разработка компьютерных средств поддержки оперативного планирования и учета», включающая построенные диссертантом алгоритмы решения задач ранцевого типа, применена в ОАО «АЗИМУТ»

для решения задач оптим&пьнон загрузки транспортных средств; имеется акт о внедрении.

Разработанная в рамках диссертационной работы программная система, решающая многокритериальные и многомерные задачи ранцевого типа, применена в ЗАО «Бизнес Аналитика», г. Москва для решения задач выбора ограниченного числа территориальных участков, исследования в которых достаточно для получения представительной (относительно набора задаваемых показателей) информации по всей совокупности имеющихся в городе предприятий торговли; имеется акт о внедрении.

Результаты, полученные при подготовке диссертационной работы, используются в учебном процессе ФГОУ ВПО «Волжская государственная академия водного транспорта» при выполнении лабораторных и курсовых работ со студентами специализации «Международные информационные и телекоммуникационные системы на транспорте».

Структура и объем работы

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

Публикации

Основные результаты, полученные в ходе работы над диссертацией, отражены в 12 публикациях (в том числе 8 статей, 2 из которых опубликованы в научных журналах, рекомендованных ВАК). Список работ приведен в конце автореферата.

Краткое содержание работы

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

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

В разделе 1.1 приводятся математическая постановка КЗР:

¿с,*,--» шах (1.1.1)'

у=1

Ъа]х]<,Ь (1.1.2)

Н __

X/ е {0;1), у =Гй; (1.1.3)

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

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

Дается детальное описание каждого из представленных алгоритмов; отмечаются их основные достоинства и недостатки; приводятся оценки вычислительной сложности. Выполнены вычислительные эксперименты, в которых сравнивались метод ветвей и границ и списковый метод. Полученные результаты показали, что эффективность метода вервей и границ, по отношению к списковому методу, значительно возрастает с увеличением размерности задачи. Так при п = 500 среднее время решения задачи списковым методом составляет 402,5 секунд, в то время как для метода ветвей и границ данный показатель равен 0,1 секунд.

п

Отмечается, что если а] <2Ь, то целесообразнее перейти от решения

М

КЗР к решению обратной задачи о ранце (ОЗР):

п

Ес]у)-> пип (1.1.13)

7 = 1

1 Нумерация формул в автореферате соответствует принятой в диссертации

9

Ъа^^Ъ (1.1.14)

ууе{0; 1}. у = й, (1.1.15)

где Излагаются модификации каждого из описанных ранее

}=1

методов решения КЗР для решения ОЗР.

В разделе 1.2 рассматриваются модификации представленных выше алгоритмов в применении к многомерной задаче о ранце.

В разделе 1.3 вводится обозначаемая 2а многокритериальная многомерная задача о ранце (ММЗР):

N

П

тах

и=1 У=1 )=1

(1.3.7)

£ «:г\', -</>,. / = 1,т (1.3.8)

7=1

х,е{0;1}, у = й (1.3.9)

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

В разделе 1.4 излагаются общая схема адаптации метода ветвей и границ для решения многокритериальных задач дискретной оптимизации; описывается конкретизация данной схемы в применении к многокритериальной задаче о ранце.

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

2 Параметры вычислительной техники: Репйшп IV, 2400 МЬг, [)ГЖ 1 СЬ. 08 \Vindovvs ХР

10

динамического программирования (его списковая реализация) и многокритериальный аналог схемы ветвей и границ. Установлено, что:

- в одномерных бикритериальных задачах (в отличие от однокритериальных) с ростом количества предметов списковый метод оказывается более эффективным по сравнению с методом ветвей и границ (при п = 60 списковый алгоритм в среднем решает задачу за 127,3 секунд, метод ветвей и границ тратит на эту задачу 1093,2 секунд в среднем);

- с увеличением числа ограничений т > 2 применение метода ветвей и границ оказывается более эффективным, независимо от количества предметов (например, для серии задач с п = 30 и т = 2 временные характеристики спискового алгоритма составляют (ср = 46,4, метода ветвей и границ - ;ср = 1,1; при я = 40 и яг = 2 время решения списковым алгоритмом составило 1ср = 1548,2, методом ветвей и границ - 1ср = 17,7).

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

При проектировании БИС АБМК возникает задача размещения компонентов ИС. Посадочные места цифровых компонентов разбиты на столбцы. Столбцы характеризуются «вместимостью» - числом посадочных мест. Цифровые компоненты могут иметь разную протяженность и должны занимать несколько подряд идущих посадочных мест в столбце - «вес» компонента.

Множество цифровых компонентов могут иметь связи (общие цепи) определенного типа - данный показатель выражает «полезность» компонента. Все столбцы для цифровых компонентов (в зависимости от его типа связи) можно упорядочить по целесообразности включения в них этих компонентов -это «важность» столбца.

Таким образом, надо размещать в максимально «важные» столбцы максимально «полезные» компоненты с учетом «весов» компонентов и «вместимости» столбцов.

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

Программная система, решающая бикритериальные задачи о ранце, прошла апробацию во ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова» при решении задачи размещения компонентов ИС, возникающей при проектировании БИС АБМК.

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

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

Характерными примерами консервативных операторов являются оператор выбора подмножеств крайних и квазикрайних оценок, а также операторы выбора подмножеств оценок, оптимальных для линейных сверток критериев (коэффициенты сверток варьируются в задаваемых ЛПР

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

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

Разделы 2.2 - 2.4 посвящены вопросам синтеза представительных совокупностей эффективных оценок для ММЗР многокритериальными реализациями метода ветвей и границ. Особое внимание уделяется построению представительных совокупностей эффективных оценок в случаях, когда это невозможно применением принципа многокритериального динамического программирования (оператор выбора неконсервативен).

В разделе 2.2 изучаются вопросы синтеза совокупностей эффективных

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

описывается технология синтеза /-разреженных совокупностей эффективных

оценок. Раздел 2.4 посвящен построению совокупностей эффективных оценок,

удовлетворяющих некоторым типовым схемам компромисса при варьируемых

параметрах этих схем (метод последовательных уступок, аддитивная свертка

критериев, метод главного критерия, метод идеальной точки). Результаты

вычислительных экспериментов по синтезу представительных совокупностей

эффективных оценок методом ветвей и границ изложены в разделе 2.5. В

экспериментах установлено, в частности, что количество всех эффективных

оценок, получаемых линейными свертками критериев, составляет в среднем

около трети от полной совокупности, при этом коэффициент ускорения равен

1,5 (также в среднем). Метод последовательных уступок дает, естественно,

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

10-процентной уступки позволило получить около 20 процентов эффективных

оценок при 68-кратном ускорении времени решения в среднем). При удачном

13

назначении порогового вектора (выбор порогов сам по себе является нетривиальной задачей) можно также значительно сократить время вычислений.

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

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

Множество оценок 0е(2'1) назовем е -приближением полной совокупности эффективных оценок Е{2(1), если: для каждой оценки из Е(2и) в С£{1(1) найдется оценка (у^г,...,^/) такая, что

———<е, 1 = 1,с1; для каждой оценки (у^у-,,...^) из в Е(1'1) найдется

IV/

оценка (м^,^,...,^) такая, что ——— <с, / = 1,с/; считается, что координаты

Щ

любой эффективной в оценки являются ненулевыми. Оценки,

принадлежащие совокупности Ое(2'1) именуем е -эффективными. Если значение е умножить на 100, то мы получим гарантированное отклонение в процентах.

Описана адаптация вычислительных процедур метода ветвей и границ для синтеза множества оценок 0,Л21') задачи 7''. Проведено программное тестирование представленного алгоритма. Переход к синтезу С1е{1с') при £ = 0,03 для серии задач с п = 40 и »¡ = 15 позволил в сравнении с синтезом множества Е(21>) достичь ускорения 1,35; для серии задач с и = 60 и т = 1 ускорение составило 12,3. При этом было получено более 40 процентов

14

эффективных оценок (от их полной совокупности), оставшиеся оценки Gl:(Zd) удовлетворяли заданному отклонению.

Раздел 3.2 посвящен применению ЭГА для получения эвристических решений. Выполнен обзор ряда основных технологий и подходов. Предложены собственные реализации ЭГА, учитывающие специфику задачи и преодолевающие недостатки существующих подходов. Результаты вычислительных экспериментов, представленные в завершении раздела, подтверждают эффективность применения разработанных ЭГА. На примере серии задач с и = 60 и т = 1 оказалось, что в наихудшем случае любая эффективная оценка представлена с отклонением в не более чем 3 процента, в наилучшем - в I процент (в первом указанном случае коэффициент ускорения равен 370, во втором - 17 по сравнению с методом ветвей и границ).

Раздел 3.3 содержит описание комбинированных алгоритмов решения задач о ранце. Основная идея данного подхода заключается в комбинировании ЭГА и МВГ. При этом ЭГА служат для достаточно быстрой генерации «предварительных» (эвристических) решений; полученные таким образом решения используются в процессе работы МВГ для сокращения счета процедур поиска точных решений. Дана экспериментальная верхняя оценка ускорения от применения описанного подхода, она составила 1,6. При этом ускорение от использования конкретного комбинированного алгоритма (представленного в данном разделе) для синтеза полной совокупности эффективных оценок составило 1,56.

В разделе 3.4 рассматриваются вопросы эффективности программной реализации сложных вычислительных алгоритмов на ЭВМ. Основной целью данного раздела является применение некоторых подходов к повышению быстродействия программ, реализующих ресурсоемкие вычислительные алгоритмы, за счет оптимизации программного кода и адаптации процедур алгоритма для более эффективной работы на ЭВМ. В качестве модельного алгоритма для оптимизации выбран многокритериальный аналог метода ветвей и границ. Исследование программы проводилось с использованием инструмента анализа производительности программ Intel VTune Performance

Analyzer, что позволяет выявлять критичные с точки зрения быстродействия участки кода (так называемые "узкие места")- В процессе оптимизации удалось достичь 164-кратного ускорения работы модельного алгоритма на ЭВМ по сравнению с его первоначальной реализацией.

В четвертой главе рассматриваются две модификации задачи о ранце -задача, где кроме стандартного линейного критерия присутствует «точечный» критерий, и задача с несколькими ранцами. В рамках моделей с несколькими ранцами естественно и адекватно формулируется ряд задач объемно-календарного планирования, в рамках постановки задачи о ранце с аддитивным и точечным критериями - задача оптимальной загрузки речных судов.

В разделе 4.1 рассматривается следующая прикладная задача. Судно грузоподъемности b по маршруту следования должно последовательно, по возрастанию номеров, пройти множество пунктов N = [1,2.3,...,к}. Считается известным множество заявок на перевозку грузов Т = {t],t2} по маршруту движения судна. Каждая заявка tj, j = i,n, характеризуется вектором (Cj,Wj,Sj,fj), где су - прибыль от перевозки у-го груза, wj - вес J-го груза, Sj и fj - пункты отправления и назначения у-го груза соответственно. Все параметры, определяющие заявку, считаются целыми положительными числами, причем < fj, s} е Л' \ к, fj е N, /= \.п. Решение задачи фиксируется вектором х = (xi,x2,...,xn) с булевозначными координатами; заявка tj принимается к обслуживанию тогда и только тогда, когда х} = 1. Для

произвольного решения х введем множество £(.*) = JJ (sj и fj),

j=U\x,= 1

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

бикрнтериальная многомерная задача о ранце с аддитивным и точечным критериями:

п

Ес^-япах (4.1.5)

У=>

¡ЭД|->ш[п (4.1.6)

I «,гх/ <6, / = Ы (4.1.7)

7 = 1

ху е {0,1}, у= и, (4.1.8)

При записи в рамках (4.1.5) - (4.1.8) задачи оптимальной загрузки судна каждый предмет (заявка на перевозку) П / характеризуется стоимостью с,- и т-

мерным весовым вектором а], т = к-1, координаты которого определяются

согласно правилу:

>1',, если 5, <; < /, — —

; ^ ; , ¡ = \,т, у = 1,«

0, в противном случае

Вес ранца ограничен ш-мерным вектором Е = (Ь,Ь,...,Ь). Излагаются решающие процедуры поиска точных решений задачи (4.1.5)

- (4.1.8), основанные на многокритериальных аналогах принципа динамического программирования и схемы ветвей и границ. В качестве эвристического алгоритма описывается конкретная реализация ЭГА.

В процессе проведения вычислительных экспериментов выяснилось, что продолжительности решения задач точным алгоритмом, в частности составляют: для 16 пунктов и 20 заявок - 76 секунд; для 11 пунктов и 25 заявок

- 542 секунды. Отметим, что указанные характеристики являются приемлемыми для решения конкретных задач перевозки грузов по маршруту Н.Новгород-Астрахань. В случае перехода в другую предметную область с большей размерностью задач или при необходимости более оперативного принятия решений целесообразно применение ЭГА. Для сравнения, описанные задачи (обеих размерностей) применением ЭГА были решены в среднем за 0,2 секунды, при этом было получено порядка 60 процентов эффективных оценок, остальные находились в 5-процентной их окрестности.

Разработанные алгоритмы решения ЗОЗС и реализованная на их основе

программная система используются в ОАО «АЗИМУТ» для решения задач

17

планирования транспортно-технологических процессов на внутреннем водном транспорте.

Раздел 4.2 посвящен задачам о нескольких ранцах, также имеющим важное прикладное значение. Изучаются две постановки - задача о к ранцах с критерием суммарной стоимости:

к п

шах £ (4.2.1)

х ./=l'=i '

<br j = U (4.2.2)

1

к _

IXj Sl, i=ln (4.2.3)

j=1

XiJ6{0,1}, i = u, y = u (4.2.4) и максиминная задача о к ранцах:

( " )

max min 2>,rt, (4.2.6)

х 0=i,i,=i 1 J J

при ограничениях (4.2.2) - (4.2.4).

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

Показывается, что введенные модели задач о нескольких ранцах могут трактоваться как достаточно естественные обобщения задач о назначениях. Примером важной прикладной проблемы, записываемой в рамках модели (4.2.1) - (4.2.4), служит также задача оптимального размещения баз снабжения.

В конце раздела рассматриваются основанные на ЭГА эвристические процедуры решения поставленных задач.

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

исходной совокупности. Излагаются два подхода к решению задачи - поиск точного решения и применение эвристик.

В разделе 5.1 приводится математическая постановка задачи, дан способ построения ее оптимального решения. В задаче имеется генеральная совокупность объектов Л/, [Л/j = N, состоящая из попарно непересекающихся

il — " подмножеств Л/,, Л/2,..., М„, где \МЛ=МГ j = i,n, На элементах

j=1

генеральной совокупности хеМ задан набор функций fa(х), а = \,р, каждая из которых принимает значения на множестве {i,2,...,ka}. Через KJap, ß = ),ka, обозначим число элементов xeMj, для которых fa(x) = ß. Число элементов х е А/, для которых выполняется fa (х) = ß, обозначим Кар. Таким образом,

Г1

К aß = S К l». Выборкой назовем произвольное подмножество Я с {\,2,...,п}.

j=1

Реализуя выборку И мы образуем множество M (Я) = U Л/,. Каждое

JtU

множество Л/(Я) характеризуем долей входящих в него элементов

ÏhNj ?HK"ß d(II) = —-— и долями принятия значений функций dun(ll) = —--,

or = l,p, ß = \,ka . Считается заданной константа i//е(0,1). Требуется найти выборку Я, которая минимизирует взвешенное суммарное отклонение введенных числовых характеристик от константы i//. Возникающая задача записывается в виде:

Р К,

min {y\d{H)-W\ + Y. I.yaß\daß(H)-V\), (5.1.1)

где у и уар - весовые множители, принимающие значение на интервале (0,l). Задачу (5.1.1) обозначим Zv, а ее критерий К,., (Я).

Приведем следующую интерпретацию. Имеется генеральная совокупность торговых точек (TT) города и информация о делении города на участки. На каждом участке могут располагаться TT разных типов (например:

магазины, павильоны, киоски, арендные отделы, АЗС, рестораны, кафе, бары, столовые и т.д.). Требуется провести выбор участков города таким образом, чтобы создать выборку ТТ заданной мощности, при этом структура выборки должна быть подобна структуре генеральной совокупности.

Излагается адаптация ранее представленного спискового метода решения КЗР для поиска точного решения задачи 7У.

Раздел 5.2 посвящен рассмотрению эвристических алгоритмов, реализующих второй подход к решению задачи I4'. Предложенные алгоритмы основаны на сведении задачи 1¥ к специальным образом построенной многомерной задаче о ранце и ее решении ранее описанными методами. В качестве альтернативы излагается ЭГА поиска решений.

Каждый из представленных алгоритмов программно реализован и прошел тестирование на реальных задачах выбора ограниченного числа территориальных участков. Для начального тестирования использовалась задача, в которой город состоит из 8 административных районов разделенных на 79 участков с 8 видами ТТ. По совокупности характеристик наилучшие результаты показал ЭГА (в среднем, примерно за 6,5 секунд удалось сформировать выборку достаточно «близкую» искомой). Точным алгоритмом решить данную задачу за приемлемое время не представилось возможным. При уменьшении размерности задачи (5 районов, 20 участков и 8 видов ТТ) и генерации серии задач, аналогичных начальной, удалось применить точный алгоритм и оценить примерное отклонение значения критерия (5.1.1) на получаемых ЭГА решениях, оно составило 1,66 процента в среднем.

Результаты проведенных исследований нашли применение в ЗАО "Бизнес Аналитика", г. Москва.

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

Основные результаты

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

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

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

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

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

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

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

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

Публикации по теме диссертации

Публикации в научных журналах, рекомендованных ВАК:

1. Федорин А.Н. Задача выбора ограниченного представительного подмножества объектов. Вестник ННГУ им. Н.И. Лобачевского. Серия Математическое моделирование и оптимальное управление. Вып.3(32). Нижний Новгород: Изд-во ННГУ, 2006, с. 138-141.

2. Федорин А.Н. Об одной задаче выбора ограниченного представительного подмножества объектов // Системы управления и информационные технологии, 2008, №1.3(31), с. 416-420.

Остальные публикации по теме диссертационной работы:

1. Коган Д.И., Лейкин М.В., Федорин А.Н. О некоторых подходах к оптимизации программ, реализующих сложные вычислительные алгоритмы. Технологии Microsoft в теории и практике. Материалы конференции. Н.Новгород: изд-во Нижегородского госуниверситета, 2006, с. 193-195.

2. Коган Д.И., Федорин А.Н. Решение бикритериальной задачи о ранце методом ветвей и границ // Моделирование и оптимизация сложных систем: Межвузовский сб. научных тр. Н. Новгород: ВГАВТ. 2004. Вып.9, С. 108 -117.

3. Коган Д. И. Федорин А. Н. Задачи о двух ранцах. Проблемы теоретической

кибернетики. Тезисы докладов XIV международной конференции (Пенза, 2328 мая 2005г.). Под редакцией О.Б. Лупанова - М.: Изд-во механико-математического факультета МГУ, 2005, с. 63.

4. Коган Д.И., Федорин А.Н. Задачи о нескольких ранцах: постановки и алгоритмы синтеза решений // Информационные технологии моделирования и управления, 2008, №7(50), с. 780-789.

5. Резников А.Е„ Федорин А.Н. Математические модели и алгоритмы решения задач оптимальной загрузки транспортных средств. В сб. тр. 11-го Международного научно-промышленного форума «Великие Реки'2009 / ICEF. Проблемы и перспективы развития учебно-научно-инновацнонных. транспортных комплексов». Н. Новгород, 2009.

6. Федорин А.Н. Решение бикритериальной задачи о ранце методом последовательных уступок. Математика и кибернетика 2003: Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород, 2003, с. 266-268

7. Федорин А.Н. К вопросу синтеза эффективных оценок для бикритериальной задачи о ранце // Моделирование и оптимизация сложных систем: Межвузовский сб. научных тр. Н. Новгород: ВГАВТ. 2004. Вып. 14, С. 112-121.

8. Федорин А. Н. Сравнительное тестирование процедур решения многокритериальной многомерной задачи о ранце // Моделирование и оптимизация сложных систем: Межвузовский сб. научных тр. Н. Новгород: ВГАВТ. 2007.

9. Федорин А.Н. Эволюционно-генетические алгоритмы решения задач о ранце // Информационные технологии моделирования и управления, 2007, №9(43), с. 1054-1062.

10. Fedorin А. N. Branch and bound approaches to solve bicriterion discrete optimization problems. VI International Congress on Mathematical Modeling/ Book of Abstracts/ September 20-26, 2004, Nizhniy Novgorod, University of Nizhniy Novgorod, p. 79

Подписано в печать 15.04.2010. Формат 60x84 1/16. Печать оперативная. Бумага офсетная. Усл. печ. л. 1. Тираж 100 экз. Заказ 442.

Типография Стимул-СТ, 603155, Н.Новгород, ул. Трудовая, 6. Тел. 436-86-40

ВВЕДЕНИЕ.

ГЛАВА 1. КЛАССИЧЕСКАЯ ЗАДАЧА О РАНЦЕ В ОДНОКРИТЕРИАЛЬ-НОЙ И МНОГОКРИТЕРИАЛЬНОЙ ПОСТАНОВКАХ. АЛГОРИТМЫ РЕШЕНИЯ.

1.1. Классическая задача о ранце и алгоритмы поиска точного решения.

1.2. Многомерная задача о ранце.

1.3. Алгоритмы синтеза Парето-оптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования.

1.4. Синтез полной совокупности эффективных оценок многокритериальной задачи о ранце методом ветвей и границ.

ГЛАВА 2. СИНТЕЗ ПРЕДСТАВИТЕЛЬНЫХ СОВОКУПНОСТЕЙ ЭФФЕКТИВНЫХ ОЦЕНОК ДЛЯ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РАНЦЕ

2.1. Концепция оператора, строящего представительную совокупность. Понятие консервативного оператора.

2.2. Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям.'.

2.3. Синтез ^-разреженных совокупностей эффективных оценок.

2.4. Алгоритмы построения совокупностей эффективных оценок получаемых применениями типовых схем компромисса при варьируемых параметрах этих схем.

2.4.1. Метод последовательных уступок.

2.4.2. Линейная свертка критериев.

2.4.3. Метод главного критерия.

2.4.4. Метод идеальной точки.

2.5. Результаты вычислительных экспериментов.

ГЛАВА 3. ПОДХОДЫ К УСКОРЕНИЮ СЧЕТА ПРИ ПОИСКЕ РЕШЕНИЙ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РАНЦЕ.

3.1. б- эффективные оценки. Синтез совокупностей б- эффективных оценок методом ветвей и границ.

3.2. Применение эволюционно-генетических алгоритмов для получения эвристических решений.

3.3. Комбинированные алгоритмы решения задач о ранце.

3.4. Некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов.

ГЛАВА 4. НЕКОТОРЫЕ МОДИФИКАЦИИ ЗАДАЧИ О РАНЦЕ И МЕТОДЫ ИХ РЕШЕНИЯ.

4.1. Задача о ранце с аддитивным и точечным критериями.

4.1.1. Математическая постановка задачи и алгоритмы ее точного решения.

4.1.2. Эволюционно-генетический алгоритм решения задачи.

4.2. Задачи с несколькими ранцами.

4.2.1. Математические постановки задач с несколькими ранцами и алгоритмы их точного решения.

4.3.2. Эволюционно-генетические алгоритмы решения задач.

ГЛАВА 5. ОБ ОДНОЙ ЗАДАЧЕ ВЫБОРА ОГРАНИЧЕННОГО ПРЕДСТАВИТЕЛЬНОГО ПОДМНОЖЕСТВА ОБЪЕКТОВ.

5.1. Математическая модель задачи и ее интерпретация. Алгоритм поиска точного решения.

5.2. Эвристические алгоритмы поиска решения.

Классическая задача о ранце (КЗР) относится к числу широко известных задач дискретной оптимизации. Данная задача впервые была сформулирована Д. Данцигом в работе [120] и с тех пор активно исследуется. Популярность КЗР вызвана большим количеством ее приложений, поскольку многие из реально возникающих задач описываются в рамках данной модели. Основные сферы применения находятся в областях планирования и управления производственными и транспортными системами. В частности, отметим формулируемые в рамках КЗР задачи объемного планирования.

Историческую хронологию этапов изучения КЗР и наиболее важные результаты данных исследований можно представить следующим образом.

1950 гг. - Постановка КЗР; алгоритм решения, использующий принцип динамического программирования (R. Bellman, G. Dantzig- [16, 17,25, 120]).

1960 гг. — Первый алгоритм решения КЗР, основанный на методе ветвей и границ; совершенствование алгоритмов использующих принцип динамического программирования (G. Dantzig, А.Н. Land и A.G. Doig, P. Gilmore, R. Gomory, P.J. Kolesar- [25, 120, 141]).

1970 гг. — Исследование вычислительной сложности КЗР, доказательство ее NP-трудности, выделение частных полиномиально разрешимых подклассов. Разработка нескольких приближенных методов решения КЗР, имеющих полиномиальные оценки вычислительной сложности. Применение двойственности для повышения эффективности метода ветвей и границ. Изложенные результаты описаны в работах О.Г. Алексеева, В.А. Емеличева, Ю.Ю. Финкельштейна, М. Garey и D. Johnson, O.Ibarra и С. Kim, С. Ра-padimitriou и К. Steiglitz, S. Sahni - [1,24,29,46,47,67, 92-95, 135, 154].

1980 гг. - Выделение новых полиномиально разрешимых подклассов КЗР; доказательство ряда важных свойств; введение понятий «ядро» и «расширяющееся ядро» и построение приближенных схем решения, основанных на этих понятиях. Разработка комбинированных подходов к решению КЗР, сочетающих применение комбинаторных методов (динамическое программирование или метод ветвей и границ) с приближенными и эвристическими алгоритмами. Полученные результаты отражены в публикациях В.А. Емеличева, И.В. Сергиенко, И.Х. Сигала, Е. Balas, T.Hu, S. Martello, D. Pisinger, P. Toth, E. Zemel - [79, 80,98, 108, 147].

1990 гг. - Применение эвристических алгоритмов, нейронных сетей, параллельных алгоритмов, эволюционно-генетического подхода к решению ранцевых задач. Достигнутые результаты изложены А.А. Корбут, И. X. Сигалом, S. Khuri, W. Loots, Z. Michaleviwicz, M. Ohlsson, С. Peterson, D. Pisinger, T.H.C. Smith - [27, 82, 137, 138, 146, 148,150-153].

2000 гг. - Новые оценки трудоемкости метода ветвей и границ; параллельные реализации методов ветвей и границ и динамического программирования; комбинированный параллельный алгоритм решения КЗР. Описанные результаты получены P.M. Колпаковым, М.А. Посыпкиным, И.Х Сигалом [35-38, 74-76].

Начиная с 60-70-х гг. XX века стали рассматриваться различные модификации КЗР. В частности, была изучена КЗР с дробимыми предметами (решающий алгоритм разработан Д. Данцигом [25, 120]) и КЗР в многомерной постановке (см., например [47]). Последняя математическая модель, в отличие от КЗР, позволяет учитывать для каждого из предметов несколько ограничивающих его факторов. Присутствие такой возможности позволяет описать в рамках многомерной КЗР множество прикладных задач, которые было невозможно адекватно выразить в рамках математической постановки КЗР. К примеру, в задачах объемного планирования, когда трудоемкость производственных задач оценивается по видам или группам работ. Таким образом, оценивая трудоемкость вектором, получаем многомерную КЗР. Фонд рабочего времени и ресурсов также представлен вектором.

Одновременно с этим, исследуется КЗР, где требование булевозначности переменных заменено требованием принадлежности их некоторому множеству неотрицательных целых чисел в ограниченном.диапазоне. Вообще говоря, некоторые авторы (см. например [98, 102]) под КЗР понимают задачу с неотрицательными целочисленными переменными. Также встречаются постановки КЗР с нелинейными критериями, в частности Д.И. Батищев и Д.И. Коган в своей работе [7] рассматривают задачу о ранце с се-парабельным критерием.

Последнее десятилетие значительное внимание уделяется ранцевым задачам в многокритериальных постановках. Данное обстоятельство вызвано стремлением более адекватно описать возникающие на практике ситуации. Зачастую многие реальные задачи оценивают принимаемое решение по нескольким показателям, а критерии, по которым оценивается решение, не всегда выражаются аддитивными функциями. Можно утверждать, что все задачи, реально возникающие в экономических системах по сути своей многокритериальны. Это объективно связано с тем, что в каждой экономической системе имеется ряд участников, каждый из которых по-своему оценивает качество принимаемых решений. Кроме того, некоторые участники могут оценивать принимаемые решения по нескольким показателям. Задачей о ранце в многокритериальной постановке занимаются Д.И. Батищев, В.А. Емеличев, А.П. Иванова, Д.И. Коган, М.В. Лейкин, И.И. Меламед, И.Х. Сигал, J.R. Figueira, М.Н. Karwan, K.Klamroth, J. Teghem, L. Thiele, E.L. Ulungu, B. Villarreal, M. Wiecek, E. Zitzler и др. Основные результаты, полученные данными учеными, представлены в работах [6, 8-12, 14, 15, 30-32, 40, 41, 43, 5159,64,65, 83, 84, 125,139, 160-162,166-168].

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

Известны два регулярных метода решения задач о ранце (в том числе многомерных многокритериальных) - принцип динамического программирования [5, 10, 16, 17, 40, 59, 139, 161] и схема ветвей и границ [43, 47, 82, 141, 160, 162]. Каждый из них допускает несколько реализаций и обладает своими достоинствами и недостатками; вместе с тем, оба они достаточно гибки и универсальны.

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

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

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

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

В жизни, при предъявлении полной совокупности эффективных оценок, ЛПР, как правило, выбирает некоторую его часть, используя собственные дополнительные соображения. Аналогичная идея используется в динамическом программировании при синтезе представительных совокупностей эффективных оценок. Реализована данная идея через концепцию оператора выбора; результативность данного оператора возможна только при условии его консервативности (см. например, [10,40]).

Альтернативный подход решения задач дискретной многокритериальной оптимизации основывается на использовании приближенных алгоритмов решения задачи, основным критерием эффективности которых, служит точность и полнота полученных решений. В настоящее время все большую популярность приобретают эволюционно-генетические алгоритмы (ЭГА) - алгоритмы случайного поиска, имитирующие в своей работе процесс эволюции популяции особей [13,23, 127, 129]. Также, в данный момент, вызывают большой интерес алгоритмы муравьиных колоний [2, 104, 122, 123].

Широкими возможностями по ускорению поиска точного решения задач дискретной оптимизации обладает комбинированный подход. Основная идея данного подхода заключается в комбинировании эвристических и точных алгоритмов решения — эвристические алгоритмы служат для достаточно быстрой генерации предварительных (приближенно-оптимальных) решений; полученные таким образом решения используются для ускорения счета процедур поиска точного решения. Наиболее удачной видится комбинирование эвристических алгоритмов с методом ветвей и границ.

Отдельное направление исследований формируют вопросы эффективной реализации вычислительных алгоритмов на ЭВМ. Конечной стадией разработки любого алгоритма является его программная реализация с целью применения в автоматизированных системах принятия решений. Вычислительная среда (аппаратная архитектура, операционная система, компилятор и т.д.) обладает своими особенностями, что не может не повлиять на работу алгоритма. Так же сюда можно отнести современные технологии параллельной реализации вычислительных алгоритмов на многопроцессорных системах (см., например [19]).

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

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

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

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

В разделе 1.1 приводятся математическая постановка классической задачи о ранце и алгоритмы ее решения, основанные на принципе динамического программирования и на схеме ветвей и границ. В раздел 1.2 излагаются модификации описанных выше алгоритмов в применении к многомерной задаче о ранце. В разделе 1.3 вводится многокритериальная задача о ранце; дан обзор основных подходов к решению задач дискретной многокритериальной оптимизации; приводится описание схем решения многокритериальной задачи о ранце, основанных на многокритериальном аналоге принципа динамического программирования. В разделе 1.4 излагаются общая схема адаптации метода ветвей и границ для решения многокритериальных задач дискретной оптимизации и конкретизация данной схемы в применении к многокритериальной задаче о ранце. Вопросы вычислительной сложности рассматриваются по мере описания алгоритмов. 7

Программная система, решающая бикритериальные задачи о ранце, прошла апробацию во ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова» при решении задач размещения компонентов интегральных схем, возникающих при проектировании больших интегральных схем на базовых матричных кристаллах с аналоговой частью (имеется акт об использовании).

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

В разделе 2.1 рассматриваются особенности построения представительных подмножеств эффективных оценок методами, реализующими принцип многокритериального динамического программирования. Вводится понятие оператора, строящего представительную совокупность, а также концепция консервативного оператора. Излагается ряд полученных ранее результатов о консервативности и не консервативности некоторых конкретных операторов выбора. Разделы 2.2 - 2.4 посвящены изложению методов синтеза представительных совокупностей эффективных оценок для многокритериальной многомерной задачи о ранце; указанные методы являются модификациями рассмотренного в разделе 1.4 алгоритма ветвей и границ. Уделяется внимание построению представительных совокупностей эффективных оценок в случае, когда это невозможно применением принципа многокритериального динамического программирования (оператор выбора является неконсервативным). Данный факт является несомненным преимуществом схемы ветвей и границ перед принципом динамического программирования.

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

В разделе 3.1 излагаются процедуры адаптации метода ветвей и границ для синтеза приближенных решений многокритериальной задачи о ранце с заданной точностью. Раздел 3.2 посвящен применению эволюционно-генетических алгоритмов для получения эвристических решений. Произведен обзор имеющихся технологий и подходов. Предложены собственные реализации эволюционно-генетических алгоритмов учитывающие специфику задачи и преодолевающие недостатки существующих подходов. Раздел 3.3 содержит описание комбинированных алгоритмов решения задач о ранце. Рассмотрены варианты комбинирования метода ветвей и границ и эволюционно-генетических алгоритмов для ускорения поиска точного решения задач о ранце; дана экспериментальная оценка ускорения от применения данного подхода. В разделе 3.4 рассматриваются некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов на ЭВМ.

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

В разделе 4.1 вводится математическая постановка задачи о ранце с аддитивным и точечным критериями. Излагаются решающие процедуры поиска точных решений, основанные как на принципе динамического программирования, так и на схеме ветвей и границ. В качестве эвристического алгоритма описывается конкретная реализация ЭГА. Рассматривается прикладная задача оптимальной загрузки судов, адекватно формализуемая в рамках построенной модели. Разработанные алгоритмы и реализованная на их основе программная система используются в ОАО «АЗИМУТ» для решения задач планирования транспортно-технологических процессов на внутреннем водном транспорте (имеется акт о внедрении).

Раздел 4.2 посвящен двум постановкам задачи с несколькими ранцами. Приводятся алгоритмы поиска точных решений. Предлагаемые решающие процедуры основаны на принципе многокритериального динамического программирования (его списковой реализации). Описывается возможность дополнительного использования верхних и нижних оценок для сокращения объема выполняемых вычислений. Рассматриваются основанные на ЭГА эвристические процедуры решения поставленных задач.

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

В разделе 5.1 приводится математическая постановка задачи и одна из ее интерпретация. Излагается адаптация ранее представленного алгоритма решения КЗР для поиска точного решения описанной задачи. Раздел 5.2 посвящен рассмотрению эвристических алгоритмов, реализующих второй подход к решению поставленной задачи. Предложенные алгоритмы основаны на сведении исходной задачи к специальным образом построенной многомерной задаче о ранце и ее решении ранее описанными методами. В качестве альтернативы излагается эволюционно-генетический алгоритм поиска решений. Каждый из представленных алгоритмов программно реализован и прошел тестирование на реальных задачах. В частности, результаты проведенных исследований нашли применение в ЗАО "Бизнес Аналитика", г. Москва. На данном основании имеется акт о внедрении научно-технической разработки.

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

Основные результаты, полученные в ходе работы над диссертацией, изложены в одиннадцати публикациях [42-45, 78, 86-91, 124], в том числе восемь из них в центральной печати [43, 45, 86-91], четыре в материалах и тезисах докладов на международных [44,78, 124] и российских конференциях [42].

Основные результаты анализа кода и реализованные методы устранения "узких мест" приводятся в таблице 3.4.2.

ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты диссертационной работы:

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

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

3. На основе анализа разнообразных концепций эволюционно-генетических алгоритмов (ЭГА) решения задач многокритериальной оптимизации и, в частности, многокритериальной задачи о ранце, реализованы собственные модели ЭГА, учитывающие специфику задачи и преодолевающие ряд недостатков существующих подходов.

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

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

6. Путем введения критериев специального вида (не всегда линейных) и ряда дополнительных ограничений построены новые модификации стандартной многокритериальной многомерной задачи о ранце (ММЗР); средствами расширенных ранцевых моделей адекватно описываются более широкие классы задач принятия решений.

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

8. Разработанный в процессе изучения модифицированных ММЗР математический аппарат успешно применен для решения задачи оптимальной загрузки судов, адекватно формулируемой в рамках многокритериальной задачи о ранце с аддитивными и точечными критериями.

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

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

1. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987.

2. Антамошкин А.Н., Кагиров P.P. Алгоритмы муравьиных колоний для многомерной задачи о рюкзаке // Системы управления и информационные технологии, 2007, №1.2(27), с. 214-218.

3. Архангельский А.Я. Программирование в C++Builder 4. 2-е изд., перераб. и до-полн. -М.: ЗАО «Издательство БИНОМ», 2000 г. - 1088 е.: ил.

4. Бабат Л.Г. Приближенное вычисление линейной функции на вершинах единичного п-мерного куба // в сб. «Исследования по дискретной оптимизации». М.: Наука, 1976, с. 156-169.

5. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

6. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Н.Новгород: Издательство Нижегородского университета, 1994.

7. Батищев Д.И., Коган Д.И. Многокритериальный выбор элементнотехнической базы для покрытия схем // в межвуз. сб. «Автоматизированное проектирование в электронике и приборостроении». Санкт-Петербург: изд-во СПбГЭТУ, 1994, с.26 - 32.

8. Батищев Д. И., Коган Д. И. Метод решения одного класса многокритериальных целочисленных задач сепарабельного программирования. Ассоциация математического программирования. Информационный бюллетень № 5, Екатеринбург, 1995, с. 36.

9. Батищев Д.И., Коган Д.И., Лейкин М.В. Многокритериальные задачи о ранце: эффективные оценки. // в межвуз. сб. «Высокие технологии в технике, медицине, образовании», изд-во Воронежского технического госуниверситета, 2001, с.4 -11.

10. Батищев Д.И., Коган Д.И., Лейкин М.В. Многокритериальные задачи о ранце: метод линейной свертки. // в межвуз. сб. «Прикладные задачи моделирования и оптимизации», изд-во Воронежского технического госуниверситета, 2001, с. 13-22.

11. Батищев Д.И., Коган Д.И., Лейкин М.В. Вопросы синтеза совокупностей эффективных оценок в многокритериальной задаче о ранце Н Математическое моделирование и оптимальное управление: Вестник Нижегородского университета, вып. 1 (25), 2002, с.211-223.

12. Батищев Д.И., Коган Д.И., Лейкин М.В. Алгоритмы синтеза решений для многокритериальной многомерной задачи о ранце // Информационные технологии, №1, 2004, с.18-27.

13. Батищев Д.И., Коган Д.И., Шеянов А.В. Модифицированная многокритериальная задача о ранце и алгоритм ее решения // в межвуз. сб. «Моделирование и оптимизация сложных систем» Волжская Гос.академия водного транспорта, вып. 273 (часть 2), 1998, с. 125-132.

14. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации: Учебное пособие.-Нижний Нов1415,16