Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения
<
Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Лейкин Максим Валентинович. Многокритериальные задачи ранцевого типа : Математические модели и алгоритмы решения : диссертация ... кандидата физико-математических наук : 05.13.18.- Нижний Новгород, 2004.- 130 с.: ил. РГБ ОД, 61 04-1/1144

Содержание к диссертации

Введение

Глава 1. Постановки, приложения и общие схемы решения многокритериальных ранцевых задач 10

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

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

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

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

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

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

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

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

Глава 2. Адаптация стандартной схемы синтеза эффективных оценок для модифицированных задач ранцевого типа 45

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

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

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

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

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

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

Глава 3. Алгоритмы синтеза представительных совокупностей эффективных оценок 67

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

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

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

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

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

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

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

Глава 4. Схемы ускоренного счета и эвристические алгоритмы в процессах решения мзрт 88

4.1. Метод комбинированной разметки при решении ММЗР 88

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

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

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

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

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

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

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

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

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

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

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

Заключение 111

Литература 112

Приложение

Введение к работе

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

В связи с необходимостью исследования таких задач, разработки эффективных методов их решения в 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-трудности, выделение частных полиномиально разрешимых подклассов. Разработка нескольких приближенных методов решения КЗР, имеющих полиномиальные оценки вычислительной сложности. Применение двойственности для повышения эффективности метода ветвей и границ. О.Г. Алексеев, Л.Г. Ба бат, В.А. Емеличев,Ю.Ю. Финкелыптейн,М. 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, С 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] и др.

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

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

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

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

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

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

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

Апробация результатов. Результаты диссертации докладывались и обсуждались на VII Нижегородской сессии молодых ученых (Саров, 2002г.), XIV Международной школе-семинаре «Синтез и сложность управляющих систем» (Н.Новгород, 2003г.), Нижегородском семинаре по дискретной математике (2003г.), научных семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Публикации. Основные результаты, полученные в ходе выполнения диссертационной работы, опубликованы в [6-9, 28, 35-42].

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

Стандартная постановка многокритериальной многомерной задачи о ранце (ММЗР) имеет следующий вид: Модель (1.19) - (1.21) позволяет учесть важные дополнительные факторы, влияющие на принятие управленческих решений. Например, в задаче объемного планирования, о которой говорилось в разделе 1.1, если предприятие работает не только с российскими, но и с зарубежными заказчиками, выполненные заказы могут оплачиваться в различных денежных единицах (рублях, долларах, евро). В этом случае формируя производственное задание необходимо учитывать получаемый доход отдельно по каждой валюте, что приводит к задаче с несколькими критериями. Таюке часто возникает ситуация, когда часть заказов ху1,...,х.-5 получена от одного и того же крупного и вы годного предприятию заказчика, требования которого желательно удовлетворить как можно полнее. Тогда появляется еще один критерий, в простейшем случае имеющий вид: В задаче формирования инвестиционного портфеля помимо непосредственного дохода Cj -, получаемого от реализации проекта (краткосрочная выгода), инвестор может получать пакет акций реализующего проект предприятия в количестве c2j штук, чем большее суммарное количество акций получит инвестор, тем более выгодным в долгосрочной перспективе является сформированный инвестиционный портфель. Таким образом, возникают два максимизируемых критерия: суммарный доход сі/ху и суммарное количество акций ;=i Все модификации ограничений, описанные в разделе 1.1, естественно могут рассматриваться применительно к ММЗР. Кроме того для некоторых прикладных задач требуется вводить в модель (1.19) - (1.21) нелинейные критерии специального вида. Опишем несколько вариантов таких критериев и задачи, которые привели к их возникновению. Критерий вида (1.24) - максиминный.

Он имеет достаточно естественную интерпретацию: желательно не помещать в ранец предметы с низким значением параметра hkj (не принимать к исполнению заказы, приносящие малый доход). Отметим, что бик ритериальная задача о ранце с одним аддитивным и одним максиминным критерием рассматривается в [46], а задача с несколькими минимаксными критериями в [32]. Задачу (1.23) - (1.26) далее будем обозначать символом Zm . ММЗР с аддитивными и диапазонными критериями Предположим, что для каждого предмета П . кроме вектора стоимости и вектора веса задан набор из 8 дополнительных параметров t]j,t2j,...,t$j таких, что влияние этих параметров (исходя из их физического или экономического смысла) на выбор оптимального решения выражается следующими критериями: Для некоторого решения x критерий Тк(х) определяет диапазон между максимальным и минимальным значением z -ro дополнительного параметра для набора предметов, помещенных в ранец, поэтому далее критерии вида (1.27) будем именовать диапазонными. Математическая формулировка многокритериальной задачи о ранце с / аддитивными и 5 диапазонными критериями выглядит следующим образом: n n Смысл дополнительных параметров, входящих в диапазонные критерии, в прикладных задачах может быть различным.

Например, если есть один дополнительный параметр и он интерпретируется как время готовности предмета к помещению в ранец, то при построении решения необходимо учитывать как суммарный вес помещаемых в ранец предметов (максимизируемый критерий), так и время загрузки ранца (минимизируемый критерий). Задачи такого типа часто возникают в логистике, т.к. длительный простой транспортных средств под погрузкой невыгоден и влечет, как правило, большие штрафные санкции. Рассмотрим следующую прикладную задачу. Имеется п грузов ГІ5Г25...,Г„, каждый из которых характеризуется стоимостью Cj, выплачиваемой за его доставку в порт назначения, весом Bj (иногда вес следует характеризовать несколькими показателями) и дополнительным параметром Vj, обозначающим номер порта, в который должен быть доставлен данный груз (порт лежит по маршруту движения судна). Маршрут судна должен обеспечивать максимизацию прибыли от доставки грузов и минимизацию числа заходов в промежуточные порты. Переменная xt в решении х равна 1, если груз Г, принимается к доставке, и 0 в противном случае. Для произвольного решения х введем множество V(x), содержащее номера портов, в которые должны быть доставлены выбранные для перевозки грузы. Соответствующая описанной модели многокритериальная задача может быть записана в виде:

Сформулированную задачу (1.32) - (1.35) будем называть ММЗР с аддитивными и точечными критериями и обозначать Zy. ММЗР с сепарабельными нелинейностями В задаче с ограниченным числом предметов каждого типа возможна ситуация, когда по одному или нескольким критериям доход от выпуска единицы продукции может зависеть от количества выпускаемых единиц (например, при выпуске от 1 до 100 единиц - доход Cij, от 100 до 1000 - Су +S). Тогда можно говорить о том, что вместо одного коэффициента Cj с помощью таблицы значений в точках ОД,...Д.- определена функция C\J(XJ) . Заметим, что в разделе 1.1 аналогичная ситуация была описана для коэффициентов а,. В самом общем случае, ММЗР с сепарабельными нелинейностями имеет вид: Стандартную ММЗР (1.19) - (1.21) и задачи с описанными модификациями ограничений и критериев далее будем называть многокритериальными задачами ранцевого типа (МЗРТ). Исследованию математических моделей МЗРТ и разработке алгоритмов их решения в данной работе уделяется основное внимание. Методы решения стандартной ММЗР вида (1.19) - (1.21) излагаются в разделе 1.4, ММЗР с максиминными, диапазонными и точечными критериями рассматриваются в разделе 2.1, ММЗР с групповой структурой - в разделе 2.2, ММЗР с дробимыми предметами, а также с ограниченным и неограниченным числом предметов каждого типа — в разделе 2.3. Для дальнейшего изложения целесообразно также сформулировать следующую задачу о ранце.

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

В данной главе представлены некоторые схемы ускоренного счета и эвристические алгоритмы, которые могут применяться с целью сокращения объема вычислений при решении многокритериальных ранцевых задач. В разделе 4.1 предлагается схема ускоренного счета, называемая комбинированной разметкой. В разделе 4.2 описано применение декомпозиционного подхода в процессах синтеза совокупностей эффективных оценок для МЗРТ. Основное преимущество данного подхода - возможность распараллеливать вычисления на несколько компьютеров, работающих как единый вычислительный кластер. В разделах 4.3, 4.4. основное внимание уделяется применению эвристических алгоритмов при решении МЗРТ. Эвристическими называют алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального или оптимально-компромиссного решения задачи. Преимуществами эвристических алгоритмов являются простота их реализации, нетребовательность к вычислительным ресурсам и сравнительно небольшое время синтеза решения (по сравнению с точными методами), что особенно важно для прикладных оптимизационных задач большой размерности, имеющих высокую вычислительную сложность, в частности, сводящихся к ММЗР. Основная проблема, связанная с применением эвристических алгоритмов, состоит в том, что получаемые решения чаще всего не являются оптимальными, кроме того невозможно заранее точно оценить отклонение от точного оптимума задачи (погрешность алгоритма). Несмотря на это возможность получать более или менее качественные решения за практически приемлемое время обусловливает значительное внимание к эвристическим алгоритмам, что подтверждается большим количеством работ по данной тематике [20, 67, 76, 84, 87].

В разделе 4.3 основное внимание уделено эвристическим процедурам реализации схем компромисса при варьируемых параметрах этих схем. Указанные процедуры используют некоторые эвристические алгоритмы решения однокритериальных задач о ранце. В разделе 4.4 приводятся некоторые эвристические алгоритмы решения многокритериальных ранцевых задач, ориентированные на построение приближенных совокупностей эффективных оценок. В разделе 1.4 в дополнение к алгоритму АТ была описана процедура разметки, позволяющая сокращать количество множеств E(k, р), которые необходимо вычислять в ходе получения совокупности эффективных оценок задачи. Легко видеть, что при выполнении этой процедуры в к -й строке таблицы эффективных оценок количество «размеченных» (т.е. участвующих в построении E(Z)) множеств Е(к, р) не превышает ве личины 2" . Действительно в п-й строке заполняется одна клетка, в (п-1)-й - две клетки, в (и-2)-й - не более четырех, и т.д. Для конкретной задачи количество «размеченных» множеств может быть меньше чем 2" . например, если а„=ап , то (»-2,6 -а„) = Е(п — 2,Ь -ап_{) и в (/7 — 2) -й строке таблицы достаточно построить 3 множества вместо четырех. Обозначим Nk""um количество клеток таблицы эффективных оценок, которые необходимо заполнить в к -й строке с учетом разметки. Общее число столбцов таблицы эффективных оценок - П(6/+1). Следовательно. разметку, в общем случае, целесообразно проводить начиная с к = п н до тех пор пока выполняется условие: Nbk """" U(bi+l) (4.1) i=1 Условие (4.1) имеет важное значение, т.к. ограничивает количество заполняемых клеток в таблице эффективных оценок числом 2", т.е. гарантирует, что табличный алгоритм даже в самом худшем случае не хуже метода полного перебора. Без учета этого условия в случае небольшого количества переменных может оказаться, что выгоднее решать задачу методом полного перебора..

В то же время во многих прикладных задачах условие (4.1) означает, что выполнение разметки имеет смысл только в нижних строках таблицы. Далее количество «размеченных» множеств быстро возрастает, разметку приходится прекращать и заполнять строки таблицы полностью. Разметка для ММЗР (4.2) - (4.5) дает результаты, приведенные в таблице 4.1 (с учетом условия (4.1) в первых двух строках таблицы разметка не проводилась и эти строки должны заполняться полностью). В то же время легко видеть, что строить все множества Е(к,р) в первых строках таблицы нет: помес ТЙТЬ предмет в ранец если это позволяет вес р (обеспечив оценку С]), или не помещать его в противном случае (при этом получится оценка (0,0,...,0)). Ясно, что во всех клетках 1-й строки таблицы соответствующих весу р «j будет записана оценка (0,0,...,0), а начиная с р = а - оценка Q. При заполнении второй строки имеются 4 варианта: Следовательно, во второй строке таблицы необходимо заполнить 3 клетки, соответствующие весам pi = атт, р2 = атгх, Р2=Щ+а2.Ъ клетках таблицы, соответствующих весу р р\ будет записана оценка (0,0,...0); в клетках, соответствующих весу Pi p p2 - оценка тт(Сі,С2), в клетках, соответствующих весу р2 р р3 - оценка тах(С1,С2), в клетках, соответствующих весу р р3- оценка С1+С2. Заметим, что все записанные здесь векторные неравенства следует трактовать как покомпонентные.

Пусть в к-тк строке таблицы эффективных оценок построены множества образом, количество синтезируемых множеств Е(к,р) в каждой строке, в общем случае, удваивается. В то же время для конкретной задачи некоторые из этих множеств могут совпасть так же как при проведении разметки. Изложенный способ заполнения таблицы эффективных оценок будем обозначать А , а количество заполненных клеток в к -й строке в соответствии с алгоритмом А - N p. Выигрыш в количестве заполняе мых клеток при использовании процедуры А в к -й строке таблицы эффективных оценок получается, если выполняется условие: Синтез совокупностей Е(к,р) в ходе реализации алгоритма А выполняется с помощью стандартных рекуррентных соотношений (1.62), (1.63). Однако, вычисления по формуле (1.63) требуют для заполнения клетки (к + 1,р) таблицы эффективных оценок, чтобы предварительно были заполнены клетки (к,р) и (k,p-ak+l). Процедура разметки по построению обеспечивает выполнение данного условия, в то время как ал горитм А этого не гарантирует, т.е. может оказаться, что необходимо найти совокуп ность E(k + \,p), но при этом отсутствуют множества Е{к,р) и Е(к,р-ак+1). Однако легко видеть, что эти множества можно восстановить по следующему правилу: (в одномерном случае формула (4.7) означает, что Е(к,р) = Е(к,р ), где клетка {к,р ) ближайшая слева к {кур ) в к -1 строке таблицы эффективных оценок).

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

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

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

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

Сложность любой задачи естественно характеризовать сложностью простейшего из алгоритмов ее решения. Каждый алгоритм А создается для решения массовой задачи, т.е. совокупности однотипных индивидуальных задач, отличающихся одна от другой только исходными данными. Необходимый объем памяти WА и количество элементарных операций (время счета) Тл являются функциями от объема входной информации V по решаемой индивидуальной задаче: ТА - TA{V) w.WA-WA (V).

Алгоритм называется полиномиальным (имеющим полиномиальную временную сложность), если количество элементарных операций ограничено сверху полиномом от объема входной информации по индивидуальной задаче, т.е. TA(V) p(V) где p{V) некоторый полином относительно V.

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

Алгоритм называется экспоненциальным (имеющим экспоненциальную временную сложность), если количество элементарных операций ограничено сверху экспоненциальной функцией от объема входной информации задачи, т.е. ТА (V) Ch , где h некоторая превосходящая единицу константа.

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

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

Различие в возможностях использования полиномиальных и экспоненциальных по вычислительной сложности алгоритмов значительно. Взятая из [18] таблица 1.4 позволяет сравнивать скорости роста нескольких типичных полиномиальных и экспоненциальных функций. В клетках этой таблицы представлены продолжительности решения задач при определяемых столбцами значениях п и определяемых строками функциях временной сложности; быстродействие ЭВМ полагается равным 10 операций в секунду Различие между алгоритмами полиномиальной и экспоненциальной временной сложности проявляется и при анализе влияния быстродействия ЭВМ на размеры решаемых задач. Так например, для функции TA(V) = 2п увеличение скорости вычислений в 1000 раз приводит к тому, что размер наибольшей решаемой за 1 час задачи возрастает только на 10, в то время как при квадратичной функции временной сложности этот размер увеличивается более чем в 30 раз.

Задача считается труднорешаемой, если для нее не существует полиномиального решающего алгоритма. Остановимся на вопросе установления труднорешаемости.

Будем рассматривать два класса дискретных задач: задачи оптимизации (к ним относятся, в частности, МЗРТ) и задачи распознавания. В каждой задаче распознавания считается определенным некоторый универсум U, в котором выделено подмножество V. По произвольному элементу х из U требуется определить, является ли х элементом подмножества V. Решить задачу распознавания означает ответить «да» или «нет» на поставленный вопрос.

Для ряда задач распознавания полиномиальные по верхней оценке временной вычислительной сложности алгоритмы известны. В качестве примеров можно привести задачи определения по графу, является ли он эйлеровым [34], определения существования полного решения в задаче о назначениях [16], определения реализуемости сетевого графика в заданный период времени [44]. Для многих других, в том числе важных с точки зрения приложений, таких алгоритмов построить не удалось. Будем говорить, что задача распознавания принадлежит классу NP, если для этой задачи можно построить решающую ее недетерминированную машину Тьюринга, функционирующую в полиномиально зависящем от объема входной информации времени (концепция недетерминированной машины Тьюринга см. в [18]). Задача распознавания «а є Г?» — полиномиально сводима к задаче «ft &W?», если существует вычислимая в полиномиальном времени функция (р такая, что а є V тогда и только тогда, когда р(а) eQ. Задачи распознавания «а є VI» и «/? є W1» считаются полиномиально эквивалентными, если задача «a eV?» полиномиально сводима к « ft є W?», а задача «j3 eW?» полиномиально сводима к«аєК?». Если задача «а є Г?» полиномиально сводима к задаче «ftsW?» и задача « /? є W » имеет полиномиальную временную сложность, то временная сложность задачи «а є VI» также полиномиальна. Задача распознавания именуется NP -полной, если: 1. она принадлежит классу NP; 2. к ней полиномиально сводима любая принадлежащая классу NP задача. Все NP -полные задачи полиномиально эквивалентны. Наличие полиномиального по верхней оценке временной вычислительной сложности решающего алгоритма для какой-либо одной NP -полной задачи автоматически влекло бы за собой полиномиальную разрешимость всех принадлежащих классу NP задач, включая NP -полные. Накопленный опыт решения дискретных задач, с учетом факта полиномиальной эквивалентности ЯР-полных задач, позволяет принять следующую гипотезу: Для NP -полных задач полиномиальных по верхней оценке временной вычислительной сложности алгоритмов решения не существует. Сформулированная гипотеза часто записывается в виде Р Ф NP. Задача называется NP -трудной, если к ней полиномиально сводится любая принадлежащая классу NP задача. Для доказательства NP -трудности задачи достаточно показать, что к ней за полиномиально зависящее от объема входной информации время сводится некоторая NP -полная задача. В доказательствах NP -полноты и NP -трудности важную роль играют выделенные в [18] 6 основных NP -полных задач. Далее будут использоваться следующие две из них.

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

Каждый заказ в этом случае представляется в виде группы Га, состоящей из к заказов (где к - количество периодов планирования) и для этой группы вводится либо ограничение (1.8), если заказ обязательно необходимо выполнить в один из периодов планирования, либо (1.7), если выполнение заказа не обязательно. Другое приложение данной математической модели возникает, если имеется несколько вариантов выполнения одного и того же заказа. Так, если некоторый заказ П , допускает 3 варианта выполнения, то соответствующую этому заказу переменную ху-следует представить в модели как группу из трех переменных Гу- = {xj , х , Xj }, каждая из которых характеризуется собственными параметрами (Cj ,cj ,Cj ,a,- ,а ,а, ) , определяющими соответственно прибыль и трудоемкость при изготовлении заказа по каждому варианту. На группу переменных Г,- необходимо наложить условие (1.7), т.к. можно принять только один из вариантов изготовления заказа Пу-. У ММЗР с групповой структурой могут быть также и другие приложения, так например, в [98] рассматривается возможность применения этой задачи при построении отказоустойчивых технических систем. КЗР с групповой структурой и методы ее решения, рассмотрены например, в [4, 26,43,92]. Задача о ранце с условием дробимости для части предметов Рассмотрим ситуацию, когда для некоторых предметов существует возможность помещать в ранец не весь предмет, а лишь некоторую его часть (такие предметы называют «дробимыми»), В этом случае, вместо ограничения (1.3) накладывается ограничение (1.9), называемое «условием дробимости для части предметов» К задаче о ранце с условием (1.9) сводится, например, задача объемного или объемно-календарного планирования на машиностроительном предприятии, имеющем собственное металлургическое производство. Действительно, заказы машиностроительного профиля могут выполняться только целиком («недробимые» предметы), а заказы, связанные с металлообработкой допускают частичное выполнение («дробимые предметы»). Если дробимыми являются все предметы, то ограничение (1.9) принимает вид: Фактически задача о ранце при этом трансформируется в задачу линейного программирования.

В одномерном случае для ее решения может быть применено хорошо известное правило Данцига [19], предусматривающее помещение предметов в ранец в порядке убывания отношения —.. Задача о ранце с ограниченным числом предметов каждого типа (bounded knapsack problem) Вместо ограничения (1.3) накладывается ограничение: которое означает, что имеется kj единиц предметов типа х . (предметы одного типа имеют одинаковую стоимость и одинаковый вес). В качестве примера приложения задачи о ранце с ограниченным числом предметов каждого типа можно привести известную «задачу размена денег»: кассиру необходимо разменять некоторую сумму денег используя минимально возможное число монет, при этом в наличии имеется фиксированное число монет каждого достоинства (в этом случае ограничение (1.11) превращается в равенство). КЗР с условием (1.11) моделирует задачу объемного планирования производства, в которой имеются заказы на изготовление к: единиц продукции типа х и существует возможность принять заказ к исполнению полностью или частично. Следует заметить также, что затраты (например, временные) на выпуск продукции вида Xj могут расти непропорционально количеству выпускаемых единиц. Эту ситуацию легко представить, если предположить что для выпуска одной единицы требуется занимающая значительное время переналадка оборудования.

Далее для выпуска последующих единиц продукции этого же вида переналадка уже не нужна. Фактически это означает, что вместо одного коэффициента я,- с помощью таблицы значений в точках 0,1,...,&у определена функция а:(хА. Ресурсное ограничение принимает вид: ;=i При таких условиях выпуск одной или даже двух единиц продукции может оказаться экономически нецелесообразным, т.е. имеет смысл либо вовсе не принимать заказ к исполнению, либо исполнять его полностью. Задача о ранце с неограниченным числом предметов (unbounded knapsack problem) Вместо ограничения (1.3) накладывается ограничение: Разумеется, в прикладных задачах всегда можно ввести ограничение на число предметов исходя из ресурсных ограничений. Однако КЗР с неограниченным числом предметов удобно использовать как модель в теоретических исследованиях для установления некоторых важных свойств семейств ранцевых задач (например, свойства периодичности, см. [63, 65]). Задача о нескольких ранцах (multiple knapsack problem) Задача формулируется следующим образом. Имеется п предметов хІ5...,х„ и т ранцев кі,...,кт, ранец kt имеет вместимость bt. Требуется разместить предметы по ранцам таким образом, чтобы максимизировать суммарный доход и не нарушить огра ничения по максимальному весу ни для одного ранца. Математическая формулировка задачи о т ранцах выглядит следующим образом: В данном случае X = xtj — матрица, элемент xtj = 1 означает, что предмет с но мером j должен быть помещен в z -й ранец, ограничение (1.16) означает, что каждый предмет может быть помещен не более чем в один ранец. С точки зрения приложений данная задача может рассматриваться как обобщение рассмотренной выше задачи загрузки уникального оборудования для случая наличия нескольких одинаковых единиц уникального оборудования. Методы решения КЗР условно можно разделить на три класса: точные, приближенные и эвристические. Точные методы в основном представлены различными реализациями схемы динамического программирования [1, 13, 14, 31, 89, 90, 91, 93] и метода ветвей и границ [1, 30, 59, 85, 93, 97]. Схема динамического программирования [13, 14] - метод оптимизации, основная идея которого заключается в замене одновременного выбора большого количества параметров последовательным их выбором.

Таким образом, синтез решения трактуется как многошаговый процесс. В основу метода положен принцип оптимальности, сформулированный Р.Беллманом [13]. Этот принцип устанавливает, что часть оптимальной траектории от любого ее состояния х до конца траектории, сама является оптимальной траекторией с началом в состоянии х. Практически схема динамического программирования как правило реализуется с помощью некоторой системы рекуррентных соотношений. Метод ветвей и границ предусматривает построение дерева- перебираемых вариантов. Для работы этого метода требуется задать процедуры вычисления верхних и нижних оценок попадающих в рассмотрение вариантов, ветвления и отсева неперспективных вариантов. Подробно применение метода ветвей и границ к решению задач дискретной оптимизации, в частности, задачи о ранце описано, например, в [60]. Преимуществом метода ветвей и границ является наличие в любой момент в процессе решения текущего рекорда, который в случае досрочной остановки вычислительного процесса, например, из-за нехватки ресурсов, может быть принят в качестве решения задачи. В свою очередь, преимущество схемы динамического программирования в том, что можно заранее установить сколько значений функции Беллмана [15] потребуется вычислить для построения полной совокупности эффективных оценок.

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