Многокритериальные задачи ранцевого типа: Математические модели и алгоритмы решения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лейкин, Максим Валентинович

• Лейкин, Максим Валентинович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Лейкин, Максим Валентинович

ВВЕДЕНИЕ.

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

1.1. Классическая задача о ранце, ее приложения и модификации.

1.2. Многокритериальные задачи ранцевого типа: математические модели, приложения и модификации.

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

1.4. Схемы синтеза полных совокупностей эффективных оценок в ММЗР.

1.4.1 Табличный алгоритм.

1.4.2 «Графовый» алгоритм.

1.4.3 Алгоритм последовательной генерации списков.

1.5. Вычислительная сложность МЗРТ и алгоритмов их решения.

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

2.1. ММЗР с различными типами критериев.

2.1.1. ММЗР с аддитивными и максиминными критериями.

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

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

2.2. ММЗР с групповой структурой.

2.3. ММЗР с дробимыми и недробимыми предметами.:.

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

3.1. Операторы, строящие представительные совокупности. Понятие консервативного оператора.

3.2 Алгоритм синтеза совокупностей, удовлетворяющих пороговым ограничениям

3.3. Адаптация технологии синтеза эффективных оценок для применения типовых схем компромисса при решений ММЗР.

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

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

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

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

ГЛАВА 4. СХЕМЫ УСКОРЕННОГО СЧЕТА И ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ В ПРОЦЕССАХ РЕШЕНИЯ МЗРТ.

4.1. Метод комбинированной разметки при решении ММЗР. 4.2. Метод декомпозиции в процессе синтеза совокупностей эффективных оценок в ММЗР.

4.3. Применение эвристических алгоритмов в ходе реализации типовых схем компромисса при решении МЗРТ.

4.3.1. Жадные алгоритмы.

4.3.2. Процедуры округления в процессах решения МЗРТ.

4.3.3. Эвристические процедуры, связанные с понятием ядра.

4.4. Эвристические процедуры решения ММЗР.

4.4.1. Эвристические алгоритмы, приближающие полную совокупность эффективных оценок.

4.4.1.1. Двухэтапный эвристический алгоритм.

4.4.1.2. Эвристический алгоритм, основанный на «укрупнении» предметов.

4.4.1.3. Декомпозиционно-пороговый эвристический алгоритм.

4.4.2. Эвристический алгоритм, приближающий фрагмент полной совокупности эффективных оценок.

Введение диссертации (часть автореферата) на тему «Многокритериальные задачи ранцевого типа: Математические модели и алгоритмы решения»

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

В связи с необходимостью исследования таких задач, разработки эффективных методов их решения в 50-х годах XX века возникло новое направление в математике, которое получило название «дискретная оптимизация». Первым в отечественной и, по-видимому, в мировой литературе сводным изложением основ дискретной оптимизации явилась монография [31]. С середины XX века и по настоящее время теория дискретной оптимизации непрерывно совершенствуется, а ее методы интенсивно развиваются.

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

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

Уже с 70-х гг. наряду с классической задачей о ранце стали рассматриваться различные ее модификации: многомерная задача о ранце, задача о ранце с групповой структурой и т.п. Введение модификаций было вызвано стремлением адекватно моделировать ситуации, возникающие в практике принятия управленческих решений. Наиболее существенным шагом на пути расширения практической применимости ранцевых моделей является рассмотрение задач с несколькими критериями. В частности, задачей о ранце в многокритериальных постановках занимаются В.А. Емеличев, И.Х. Сигал, Д.И. Батищев, Д.И. Коган, K.Klamroth, M.Wiecek, J.R. Figueira, E.L. Ulungu, J. Teghem, B. Villarreal, M.H. Karwan.

Таблица 1. Основные результаты исследования КЗР

Период Основные результаты Ученые, в работах которых получены данные результаты

50-е гг. Постановка КЗР; верхняя оценка оптимального значения критерия; алгоритм решения, использующий принцип динамического программирования. G. Dantzig, R. Bellman

60-е гг. Первый алгоритм решения КЗР, основанный на методе ветвей и границ; совершенствование алгоритмов, использующих принцип динамического программирования. A.G. Doig, P. Gilmore, R. Gomory, A.H. Land, P J. Kolesar,

70-е гг. Исследование вычислительной сложности КЗР, доказательство ее NP-трудности, выделение частных полиномиально разрешимых подклассов. Разработка нескольких приближенных методов решения КЗР, имеющих полиномиальные оценки вычислительной сложности. Применение двойственности для повышения эффективности метода ветвей и границ. О.Г. Алексеев, JI.Г. Ба-бат, В.А. Емеличев, Ю.Ю. Финкельштейн, М. Garey, O.Ibarra, D. Johnson, С. Kim, С. Papadimitriou, S. Sahni, K. Steiglitz

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

90-е гг. Применение эвристических алгоритмов, нейронных сетей, параллельных алгоритмов, эволюци-онно-генетического подхода к решению ранцевых задач. D. Pisinger, W. Loots, T.H.C. Smith, M. Ohlsson, C. Peterson

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

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

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

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

В процессах синтеза совокупностей эффективных оценок для задач дискретной многокритериальной оптимизации, в частности, многокритериальной задачи о ранце, можно использовать два регулярных метода: многокритериальный аналог метода ветвей и границ [29, 100, 102] и многокритериальный аналог принципа динамического программирования [4, 83, 101].

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

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

В соответствии с поставленной целью, предметом рассмотрения в диссертационной работе являлись следующие задачи:

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

• построение схем синтеза эффективных оценок для многокритериальных задач ранцевого типа;

• исследование вычислительной сложности построенных моделей;

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

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

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

Методическую и теоретическую базу диссертационной работы составляют подходы и инструментарий системного анализа, исследования операций, дискретной и многокритериальной оптимизации, а также ряд ранее выполненных работ, связанных с изучением задач ранцевого типа. При выполнении исследования автор опирался на теоретические результаты отечественных и зарубежных ученых. Здесь, прежде всего, следует отметить работы О. Г. Алексеева [1], Л.Г. Бабата [2], В.А. Емеличева [22-25], АА. Кор-бута [30-31], В.Д. Ногина [54], В.В. Подиновского [50-54], И.В. Сергиенко [56-57], И.Х. Сигала [58-60], Ю.Ю. Финкельштейна [61], R. Bellman [13-14], G. Dantzig [19, 77], М. Garey [18], Т. Ни [63], D. Johnson [18], С. Papadimitriou [48], К. Steiglitz [48] и др.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лейкин, Максим Валентинович

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

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

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

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

Исследована вычислительная сложность всех рассматриваемых в работе задач, для большинства задач доказана NP-трудность в несильном смысле, выделены частные полиномиально разрешимые подклассы.

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

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

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат физико-математических наук Лейкин, Максим Валентинович, 2004 год

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

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

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

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

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

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

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

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

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

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

11. Батищев Д.И., Шапошников Д.Е. Многокритериальный выбор с учетом индивидуальных предпочтений. Н.Новгород, Изд-во ИПФ РАН, 1994.

12. Батищев Д.И., Шапошников Д.Е. Решение многокритериальных задач методом идеальной точки // в сб. «Модели и алгоритмы оптимизации в автоматизированных системах», Воронеж, ВПИ, 1989, с.48-53.

13. Беллман Р. Динамическое программирование. М.: ИЛ, 1960,

14. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. -М.: Наука, 1965.

15. Габасов Р., Кириллова Ф.М. Основы динамического программирования. Минск: Изд-во БГУ, 1975.

16. Гейл Д. Теория линейных экономических моделей. М.: Мир, 1969.17.