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

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

Лейкин Максим Валентинович

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

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

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

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

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

Научный руководитель: доктор технических наук, доцент КОГАН Д.И. Официальные оппоненты:

доктор физико-математических наук, доцент АЛЕКСЕЕВ В.Е. кандидат физико-математических наук, доцент ШАПОШНИКОВ Д.Е.

Ведущая организация: Вычислительный центр РАН (Москва)

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

в аудитории ЛЗ-З корпуса ^ Нижегородского государственного университета им. Н.И. Лобачевского в (^ часов на заседании Диссертационного совета Д 212.166.13.

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

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

Автореферат разослан

Ученый секретарь диссертационного совета, /^Ь

кандидат физико-математических наук, доцент Савельев В.П.

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

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

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

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

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

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

Задача о ранце в многокритериальных постановках явилась предметом работ Д.И. Батищева, ВА. Емеличева, Д.И. Когана, И.Х. Сигала, В.Н. Шевченко, J.R. Figueiгa, M.H. Kaгwan , K.Klamгoth, J. Teghem, E.L. Ulungu, B. УШаггеа1, М. Wiecek и других авторов.

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

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

Цель работы

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

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

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

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

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

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

3. Выполнено исследование некоторых важных с практической точки зрения операторов на предмет обладания ими свойством консервативности.

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

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

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

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

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

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

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

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

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

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

Публикации

Основные полученные в диссертации результаты отражены в 13 публикациях (в т.ч. 6 статьях), список которых приведен в конце автореферата.

в

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

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

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

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

(1.24)

(1.27)

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

Hl = шах min hu, к = \,q

(максиминные критерии); 7i(i) = ^ max tjcj- min ->min, k = \,ö

(диапазонные критерии);

(точечные критерии; здесь предполагается; что каждому предмету сопоставлен его тип Vj, У(х) -

число типов предметов, задействованных в решении

Среди дополнительно вводимых ограничений: - блочные (групповые) ограничения

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

7

(1.33)

51 - из группы предметов Га в ранец может быть.

П,еГ„

(1.7)

помещено не более одного предмета;

Хлг,- = 1 - из группы Га в ранец должен быть помещен П ,еГа

(1.8)

ровно один предмет (здесь предполагается, что все предметы разбиты на группы Г^Гт,..., Г\): условие дробимости для части предметов

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

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

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

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

X} €[0;1], у = \,к; х} е {0,1}, j = k + \,n.

(1.9)

Пусть Ъ - исходная ММЗР (1.19) - (1.21); Е(Т.) - искомая полная совокупность эффективных в 7. оценок; 2{к, р) • совокупность порождаемых задачей Z частных задач, здесь к 6 {1,2,...,и}, реР; Р —множество всех целочисленных векторов {.Р\*Р2*—>Рт} с координатами, удовлетворяющими условиям О<Р1<Ь/, 1 — 1,т. Полную совокупность эффективных оценок в задаче 2(к,р)^ обозначим-Е(к,р). Как очевидно, Е(2)=Е(п„Ь): С учетом введенных обозначений, рекуррентные соотношения для построения E(Z) имеют вид:

^ {(сп)с21,...,сп) приа,\ < р, для всех / = 1,ш ' ) Е(к + 1,р)= е#(Е(к,р)и{Ск+1 ФЕ(к,р-ак+1)}) (1.63)

В ходе реализации вычислений на основании (1.62) - (1.63) по строкам сверху вниз заполняется таблица 1.1. В крайнюю справа клетку последней строки вносится множество

Таблица 1.1. Таблица эффективных оценок

Р\ Р2 Рз ... Рв-1 р,{=Ь

1 Е(\,Р\) Е(1,р2) Е(1,р3) ... Е(\,рв~\)

2 Е{2,рх) Е(2,р2) Е(2,р3) Е(2,рв_х) Е(2.Ь)

... ... ... ... ... ...

п Е(п,р,) Е(п,р2) Е(п,рг) Е(п,рв_,) Е(п.Ь)

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

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

Теорема 1.1. Проблема определения по исходным данным бикритериальной одномерной задаче о ранце, в которой веса всех предметов равны 1, и константам С{,С2, имеет ли данная задача решение Зс; такое что Q(i)>C|, Q2(x)2C2, NP-полна.

Болеет высокую вычислительную сложность. ММЗР по сравнению с классической задачей о ранце характеризует также следующий факт.

Теорема 1.2. Для любого четного п существует двухкритериальная

одномерная задача о ранце с n предметами, в которой имеется:не менее различных эффективных оценок.

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

R

положительными коэффициентами через

критериальную, массовую задачу о ранце, в которой все

коэффициенты критериев и все правые части q е {1,...,ш}) не превышают R{ri), здесь п- число переменных.

Теорема 1.3. Проблема синтеза полной совокупности эффективных оценок в задаче K^\l,m,p,q\ полиномиально разрешима, если l + m- p-q£\..

Если условие (1.90) не выполняется, проблема синтеза полной совокупности эффективных оценок в задаче

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

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

Теорема 1.5. Однокритериальная задача о ранце с групповой структурой № -трудна в сильном смысле.

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

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

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

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

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

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

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

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

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

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

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

(3.3)

(3.4),

Возникает вопрос о возможности построения подмножества 11{Е(Х))' без предварительного отыскания совокупности.' £(Z), путем систематического применения оператора I/ в ходе реализации табличного алгоритма, т.е. выполнением счета по рекуррентным соотношениям:

„„,, _ч Г(0Д...,0), если3/: 0 < р{ <ап ;

Я(иХр) = \ _

[ц приа\йр\

Я(и,к,р) ес.7«Э/:0<р] < ;

Я{УЛ +1 ,р) = - £/(е#(/?(£/Д,р)и {С*+| в Я(иХр-аш)))] приам<р,

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

Оператор будем называть консервативным, если для произвольных множеств /-мерных векторов-оценок и произвольного вектора

той же размерности выполняются равенства:

1. щмх и мг)={/({/(Л/, )и^/(Л/2))

Теорема 3.1. Если оператор V консервативен, то при любых к,р имеет

Щи,к,р) = и(Е(к,р)).

Для консервативного оператора V синтез совокупности ЩЕ(И)) можно выполнять применением рекуррентных соотношений (3.3) - (3.4).

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

оператор квазикрайних по каждому из критериев оценок,

консервативен. Оператор выделяющий множество оценок, не входящих

13

в число к квазикрайних, консервативным не является (дополнительно полагается, что в случае {/^(А/) = Л/ имеет также место (/^(Л/) = Л/). Определяемый в работе оператор строящий по возможности равномерно

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

применением рекуррентных соотношений (3.3) - (3.4) строятся множества, не совпадающие с соответствующими совокупностями Ц(Е(Е)).

В разделе 3.2 рассматривается ситуация, когда ЛПР имеет информацию, позволяющую назначить нижние пороговые значения критериев задачи Z. Здесь, при известном пороговом векторе Н =(Л|,./»2 ,.•«/»/), где А, -минимально допустимое значение критерия возникает задача

построения множества состоящего из принадлежащих

совокупности Е оценок »—>0/), удовлетворяющих

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

(3.15)

Излагается использующий процедуру оценивания алгоритм синтеза

совокупности Е{2,И^,И2.....А/).

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

Оценку если она является

оптимальным решением задачи

при некотором наборе лежащих в интервале (0,1) коэффициентов Л{,Л.2,...,Л/.

Огметим, что множество « -оценок из Е(2) - это совокупность оценок всех

14

2: А,; 1 = И

решений, оптимальных в однокритериальных задачах, получаемых из линейной сверткой критериев.» Пусть {/$ И 1/<;(Л\Л~) - операторы, выделяющие из множества оценок М соответственно совокупность всех 5-оценок и совокупность получаемых при значениях весовых

коэффициентов в диапазонах Я} ¿Л, ¿Л^; 1 = \,1.

Теорема 3.4. Оператор и$ консервативен.

Теорема 3.5. Оператор {/^(Я'.Л2) консервативен.

Теоремы 3.4 и 3.5 дают возможность применять операторы Ц*; и

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

также примерно в 3 раза.

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

При реализации метода главного критерия после того, как лицом, принимающим решения, определены» главный . критерий Q^(x),k = \,f н пороговый вектор Н = (/ц Л/), осуществляется синтез совокупности

оценок £(2,А|,А2,—>А/).

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

наименее удаленную от идеальной точки.

Предлагаемая адаптация схемы синтеза эффективных оценок (считается, что расстояние г{х,у) между произвольными точками 0? = (ЛГ|, ..,.*/) и у = (_У], У2->"">У1) пространства критериев определяется по формуле для реализации данного метода предусматривает

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

расстояние Д = ),1). Оптимальное решен о л ж н о порождать

оценку, находящуюся от точки отсюда получаем:

0а(х*)>/„- Д, а = У. (3.65)

Таким образом, искомое Парето-оптимальное решение х* характеризуется оценкой, принадлежащей совокупности

На втором этапе строится совокупность оценок в ней

находится оценка, Л, наименее удаленная от точки 1 I, по оценке Л синтезируется порождающее ее решение

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

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

соответствуют удаленности границ подобласти расположения идеальной точки от центра / ).

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

К схемам ускоренного счета относится, в частности, комбинированная разметка, предлагаемая в разделе 4.1.

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

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

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

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

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

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

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

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

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

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

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

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

Предложены использующие комбинированную разметку и

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

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

18

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

1. Лейкин М.В. Модифицированная многокритериальная задача о ранце и ее использование в процессах планирования и управления // Вычислительная математика и кибернетика 2000: Тез. Докл. конф., посвященной 80-летию Ю.И. Неймарка. - Н.Новгород, ННГУ, 2000. С. 51.

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

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

4. Коган Д.И., Лейкин М.В. Ранцевые модели в процессах выбора вариантов реализации схемных решений задачи группового обмена // Интеллектуальные информационные системы: Труды всероссийской конференции. - Воронеж. 2001.С.13-14.

5. Лейкин М.В. К проблеме синтеза эффективных алгоритмов для многокритериальной многомерной задачи о ранце // Интелектуальные информационные системы: Труды всероссийской конференции. - Воронеж, 2001.С.35-36.

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

7. Лейкин М.В. К вопросу о вычислительной сложности многокритериальных задач о ранце // Тезисы докладов VII Нижегородской сессии молодых ученых (математические науки). - Саров, 2002. С. 55-56.

8. Лейкин М.В. Об одной эвристической процед>ре решения многокритериальной многомерной задачи о ранце // Математика и кибернетика 2002: Материалы конференции. - Н.Новгород, 2002. С. 62-64.

19

9. Лейкин М.В. Алгоритм решения многокритериальной задачи о ранце с аддитивными и диапазонными критериями // Синтез и сложность управляющих систем: Материалы XIV международной школы-семинара. -Н.Новгород, 2003. С.52-53.

10. Лейкин М.В. Синтез представительных совокупностей эффективных оценок в многокритериальной задаче о ранце // Ломоносов 2003: Материалы международной конференции студентов и аспирантов по фундаментальным наукам. - М.: Изд-во МГУ, 2003. С. 10-11.

11. Лейкин М.В. К вопросу о вычислительной сложности многокритериальных задач о ранце // Математика и кибернетика 20031 Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК, Н.Новгород, 2003, С. 203 - 205.

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

13. Лейкин М.В. Многокритериальная задача о ранце с дополнительными диапазонными и точечными критериями // Вестник ВГАВТ. Межвузовская серия «Моделирование и оптимизация сложных систем», выпуск 9,2004, С. 4352.

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

Типография Нижегородского госуниверситета. Лицензия №18-0099. 603000, П. Новгород, ул. Б. Покровская, 37.

ВВЕДЕНИЕ.

ГЛАВА 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-трудность в несильном смысле, выделены частные полиномиально разрешимые подклассы.

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

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

ЗАКЛЮЧЕНИЕ

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

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.