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

Проблемы распределения, перераспределения и обмена педробимых ресурсов, определения очередности в процессах их обслуживания являются типовыми для многих экономических, социальных и организационных систем. Центральное место занимают они в управлении транспортными процессами, где решаются задачи планирования грузоперевозок, распределения транспортного состава и заданий на перевозку грузов, определения последовательностей обслуживания транспортных средств. Классическим примером задачи распределительного типа является транспортная задача линейного программирования (ТЗЛП) [51, 168]. Стандартная для данной задачи интерпретация — проблема синтеза плана грузоперевозок (т.е. распределения выпускаемого каждым из производителей продукта по потребителям), но реальная сфера применений ТЗЛП как математической модели принятия решений существенно шире. В частости, рамках транспортном задачи и задачи о назначениях (47, 122| как се частого случая могут быть описаны различные проблемы расстановки, распределения и обмена трапснортпо-технических средств, определения исполнителей заданий. Вопросы синтеза последовательностей обслуживания транспортных средств формулируются в терминах классов задач теории расписаний [164−166], где обслуживанию подлежат заявки, принадлежащие детерминированному входному потоку.

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

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

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

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

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

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

Важно учитывать, какие группы участников обладают определенной самостоятельностью в принятии окончательных решенийконструируемые планы и управления должны удовлетворять соответствующим образом вводимым свойствам теоретико-игровой устойчивости [31, 42, 43, 59, 136].

Сложность создания алгоритмического обеспечения определяется двумя контрарными обстоятельствами. Во-первых, рассматриваемые проблемы достаточно часто оказываются N1'-!рудными (согласно естественно — научной гипотезе Р^ЫР, такие задачи полиномиальных по верхней оценке временной вычислительной сложности решающих алгоритмов не имеют) [56, 71]. Во-вторых, имеются жесткие технологические или регламентные ограничения на продолжительность процесса решения каждой задачи. Разработку точных, приближенных или эвристических алгоритмов следует выполнять с учетом результатов о вычислительной сложности решаемых задач, а также данных о их размерности и ограничениях на время решения.

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

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

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

Методическую и теоретическую базу диссертационной работы составляют подходы и инструментарий системного анализа, исследования операций, теории игр, многокритериальной и комбинаторной оптимизации, теории графов, теории расписаний, а также ряд ранее выполненных работ в областях распределения и перераспределения ресурсов, транспортного планирования и совершенствования эксплуатации водного транспорта. При выполнении исследований автор опирался на теоретические результаты отечественных и зарубежных ученых (Татищев Д.М., Курком П.II., Воробьев H.H., Гсрмсйер IO. I"., Голыитейп lu'., 1лмеличев В.Д., 'Захаров В.М., Кацнельсон М. Ь., Ларичев О. И., Ловецкий С. С., Подиновский В. В., Сигал И. Х., Танаев B.C., Шкурба В. В., Юдин Д. Б., Bellman R., Conway R.W., Cook S.A., Gale D., Garey M., Isermann H., Johnson D., Karp R.M., Lawler E.L., Lenstra J.K., Shapley L. и др.), а также на результаты, полученные для транспортных систем Беленьким A.C., Захаровым В. Н., Игуди-ным Р.В., Савиным В. И. и др.

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

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

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

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

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

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

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

Комплекс алгоритмов и программных средств решения задач недробимого обмена был положен в основу разработанной под научным руководством автора и внедренной в промышленную эксплуатацию автоматизированной системы обмена жилья в г. Горьком (АСОЖ «Волга»).

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

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

7-ом Всесоюзном совещании по проблемам управления (Минск, 1978), 3-ей Всесоюзной школе по математическому обеспечению АСУП (Горький, 1978), 2-ом Всесоюзном семинаре по перераспределению ресурсов (Москва, ИПУ, 1978), 4-ой Всесоюзной конференции по исследованию операций, Горький, 1978), 7-ой Всесоюзной конференции по проблемам теоретической кибернетики (Иркутск, 1985), Всесоюзной конференции по внедрению ЭММ и ЭВМ в планирование и управление производством (1985), Всесоюзной школе-семинаре «Системное моделирование производства» (Воронеж, 1986), 8-ой Всесоюзной конференции по проблемам теоретической кибернетики (Горький, 1988), 11-ом Всесоюзном совещании по проблемам управления (Ташкент, 1989), 9-ой и 10-ой Всесоюзных конференции по проблемам теоретической кибернетики (Волгоград, 1990 и Саратов, 1993), Всероссийском совещании-семинаре «Математическое обеспечение высоких технологий в технике, образовании, медицине» (Воронеж, 1994), Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1995), Всероссийской конференции «Информационные технологии и системы» (Воронеж, 1995), Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1997), Научно-технической конференции по проблемам транспорта (Нижегородский научный центр Академии транспорта РФ, 1999), XII Международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 1999), на научных семинарах Нижегородского госуниверситета по информатике и дискретной математике, на научных конференциях Волжской государственной академии водного транспорта.

Публикации. Результаты, полученные автором по теме диссертации, опубликованы в работах [2, 10 -25, 54, 78 — 120].

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

В § 1.1 излагаются причины многокритериальное&tradeв задачах синтеза планов перевозок, приводятся примеры многокритериальных транспортных задач, возникающих в воднотранспортных системах, выделяется иерархия классов важных в теоретическом и прикладном отношениях классов многокритериальных транспортных задач. В частности, определяются задачи с несколькими общими критериямизадачи с общим критерием, критериями групп участников и оценками отдельных участников (оценка участника — функция, зависящая от размеров перевозок по всем коммуникациям, относящимся к данному участнику) — задачи с общим критерием и индивидуальными предпочтениями участников.

В § 1.2 в применении к транспортным задачам рассматриваются аддитивная свертка критериев, их лексикографическое упорядочение, излагаются методы последовательных уступок и главного критерия, принцип гарантированного результата и др. 39, 40, 49,137, 144, 145, 175]. В достаточно типичной ситуации, когда выбор конкретной схемы компромисса и ее параметров затруднителен, целесообразным является построение полной или достаточно представительной совокупности эффективных оценок [145] с одновременным обеспечением возможности синтеза для любой из таких оценок Паретооптимального решения, данную оценку порождающего. Приводятся результаты С. Карлина [70] и Ю. Б. Гермейера [49] о возможностях получения эффективных оценок путем применения сверток критериевизлагается принадлежащая Aneja Y. и Nair К. [179], см. также [183,189, 190], методика синтеза полной совокупности эффективных оценок для бикритериальной транспортной задачи линейного программирования (ТЗЛП). Далее проблема синтеза эффективных оценок анализируется для целочисленной бикритериальной ТЗЛПрешается вопрос о построении для этой задачи эффективных оценок, примыкающих к одной из крайних, получаемых путем лексикографического упорядочения критериев, оценок.

В § 1.3 изучаются транспортные задачи с минимизируемыми общим линейным критерием и линейными оценками участников. Вначале рассматривается вопрос существования планов перевозок, для которых значения оценок всех участников не превосходят заданных пороговых величин. Данная проблема в общем случае ИРполна [56]- в ситуации, когда оценки каждого участника дихотомические (т.е. любой из возможных для него партнеров характеризуется числом 0 — «хороший» или 1 — «плохой»), проблема сводится к задаче построения максимального потока [170] в специальным образом построенной сети. Последнее дает возможность при дихотомических оценках участников и заданных пороговых ограничениях эффективным образом решать и проблемы оптимизации значения общего линейного или минимаксного критерия на множествах допустимых планов. Обсуждаются вопросы назначения пороговых значений при решении конкретных задач и реализации метода последовательных уступок как по совокупности критериев (оценок) участников, так и по общему критерию суммарной стоимости перевозокв случае дихотомических оценок этот метод реализуется «сетевым» алгоритмом. Полученные результаты о полиномиальной разрешимости [56] дают возможность для задач с недихотомическими оценками строить достаточно качественные эвристические алгоритмы.

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

Пусть в некоторой транспортной задаче с индивидуальными предпочтениями участников определен план перевозок X, а С — цикл перераспределения поставок, определяемых данным планомдля любого охваченного циклом участника и объем поставки по одной из инцидентных ему коммуникаций уменьшается на величину 8 >0, а по другой на ту же величину увеличивается. Цикл С является не ухудшающим (улучшающим) относительно и, если партнер, для которого поставка по связывающей с и коммуникации увеличивается, для и не менее предпочтителен (более предпочтителен), чем партнер, для которого поставка по связывающей с и коммуникации уменьшается. Цикл С считаем 17-улучшающим (здесь 17 — произвольное множество участников), если он, но меньшей мере для одного участника из 17 является улучшающим, а для остальных входящих в 17 участников — не ухудшающим. План перевозок и — эффективен, если не существует изменяющего этот план 17 — улучшающего цикла.

Множество участников 17 именуем однородным, если оно имеет в своем составе только пункты производства или только пункты потребления. Показывается, что если 17 — однородное множество, то план X транспортной задачи с дихотомическими системами индивидуальных предпочтений участников Uэффективен тогда и только тогда, когда он является решением соответствующим образом составленной однокритериальной ТЗЛГТ. Отсюда получаем, что в случае дихотомических предпочтений участников для однородного множества U проблема оптимизации критерия общих издержек на множестве Uэффективных планов также сводится к решению однокритериальной ТЗЛП. Несложно решается в данном случае и задача минимизации затрат времени.

В ситуации, когда любой пункт производства и любой пункт потребления имеют возможность совместно определить объем перевозки по связывающей их коммуникации, целесообразно принятие концепции устойчивости, соответствующее принципу Гейла-Шепли [185]. Решение X транспортной задачи с взаимными предпочтениями участников назовем устойчивым по ГейлуШепли (Густойчивым), если не существует пункта производства, А и пункта потребления Bj, которым, исходя из имеющихся предпочтений, целесообразно увеличить поставку из Ав Bj на некоторую положительную величину s за счет соответствующего уменьшения поставок из, А в менее предпочтительные для Ai пункты потребления и поставок в Bj из менее предпочтительных ДЛЯ Bj пунктов производства.

Излагается адаптация алгоритма Гейла — Шепли [181, 185], реализующая синтез Г-устойчивых планов для транспортной задачи с индивидуальными предпочтениями участников, изучаются связанные с этой адаптацией вопросы. Исследуются задачи оптимизации общего критерия на множествах Г-устойчивых планов, конструируются алгоритмы синтеза компромиссных решений.

В § 1.5 излагается ряд относящихся к многокритериальным транспортным задачам результатов об NPполноте или NPтрудности[56].

Сложность реализации описания полной совокупности эффективных оценок для бикритериальной ТЗЛП подтверждает тот факт, что проблема определения по исходным данным ТЗЛП с критериями К|(Х), К2(Х) и натуральным константам СЬС2, существует ли в данной задаче план перевозок X такой, что одновременно Кi (X)< С! и К2(Х)< С2, является NP-полной.

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

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

В § 2.1 излагается концепция однокритериальной задачи о назначениях, приводятся оценки вычислительной сложности задач о назначениях с критериями различных типов в частности — классической задачи о назначениях (КЗН), т. е. задачи с аддитивным максимизируемым критерием, и минимаксной задачи о назначениях. Обосновывается необходимость рассмотрения многокритериальных задач о назначениях. Выделяются интересные в теоретическом аспекте и важные в прикладном отношении классы многокритериальных задач, приводя гея примеры многокритериальных задач о назначениях, возникающих в процессах управления на внутреннем водном транспорте.

В § 2.2 рассматривается двухкритериальная задача о назначениях (ДКЗН) с п максимизируемыми аддитивными критериями СМя) — X ат (0 И СМл) =.

1=1 п.

Элементы (пхп)-матриц, А = {а^} и В = {Ьу}, определяющих ДКЗН, принадлежат множеству N и {со}, где N — совокупность целых неотрицательных чисел, а (c) — специальный символ запретаесли в позиции (у) одной матрицы стоит со, то этот знак стоит в позиции (у) и в другой матрице. Изучаются проблема синтеза полных совокупностей эффективных оценок и вопрос о реализации метода последовательных уступок по значению ведущего критерия.

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

Показано, что число различных эффективных оценок в ДКЗН размера пхп с аддитивными критериями может оказаться равным п!, при этом Паретооптимально каждое назначение. Вычислительную сложность рассматриваемой ДКЗН характеризуют и следующие результаты: ЫРполна проблема определения по исходным данным ДКЗН, существует ли в ней назначение, при котором критерии 01(71) и принимают значения не ниже предписанных порогов.

С] и С2 соответственно — проблема определения по исходным данным ДКЗН и назначению к, относится ли оценка (СМтс), СЬ (я)) к числу неэффективных, является ЫР-полнойЫР-грудны проблемы определения по исходным данным ДКЗН, являются ли все ее Парето-оптимальные решения: а) линейно определимыми, б) всршишю-опредслимымиЬП'-трудпа проблема определения, но исходным данным ДКЗН, содержит ли множество ее эффективных оценок больше двух элементов. Две эффективные оценки назовем соседними, если при упорядочении всех эффективных в рассматриваемой задаче оценок по возрастанию значений первого критерия между данными оценками не оказывается промежуточных. Задача определения по исходным данным ДКЗН и двум эффективным в ней оценкам, не являются ли они соседними, ЫР-полна.

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

Пусть (аьЬО и (а2,Ь2) — несовпадающие (а| > а2) эффективные оценки, порождаемые назначениями, оптимальными при двух противоположных лексикографических упорядочениях критериев СЬ и СЪВеличину тш{а! — а2, Ь 2 -Ь]} называем рассогласованием критериев. В ситуации, когда п достаточно большое и рассогласование критериев значительно, метод последовательных уступок для синтеза полной совокупности эффективных оценок оказывается слишком трудоемким, но он применим, если можно ограничиться малым числом итераций. Изложенная технология реализации уступок и знание общей геометрической структуры множеств оценок позволяет отыскивать эффективные компромиссные решения в интерактивном режиме.

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

В § 2.3 для ДКЗН вида шах { 2 aj, min bj я (0} ы ' тгеН изложена основанная на методе последовательных уступок технология синтеза полной совокупности эффективных оценок. Каждая следующая уступка связана с решением определенным образом построенной КЗН. Общее число уступок не более п2 — п.

В § 2.4 рассматривается задача группировки в пары с учетом односторонних предпочтений. Она определяется как совокупность? = < 1, R, L>, где 1 = {1, 2,., п} - множество объектов первого типа (исполнителей или участников) — R= {ri, г2, .. ., гп } - множество объектов второго типа (работ) — L = { < ь < 2, • • •, ^ п} - квазилинейные упорядочения, определяющие предпочтения исполнителей на множестве работ.

Каждое назначение определяет систему пар «исполнитель-работа». Назначение 71 называем устойчивым, если не существует группы (коалиции) участников S, Sc{ 1, 2,., п}, члены которой могут обменяться между собой полученными в результате реализации этого назначения работами так, что каждый член коалиции i, i е S, получит работу, с точки зрения его предпочтений лучшую, чем работа, предписываемая ему данным назначением. Назначение л называем к — усгоичивым, если не существуеткоалиции участников S, Sc{ 1, 2,. .. , п}, члены которой могут обменяться между собой полученными при реализации этого назначения работами так, что по меньшей мере один участник, обозначим его j, j е S, получит работу, с точки зрения его предпочтений лучшую, чем работа, предписываемая ему данным назначением, а каждый из остальных членов коалиции — работу, не худшую, чем получаемая в соответствии с данным назначением.

Очевидно, что любое кустойчивое назначение устойчиво. Если в L все отношения < j — линейные порядки, то совокупности устойчивых и кустойчивых назначений совпадают.

Через л- (S) обозначим совокупность работ, получаемых участниками множества S, Sc{l, 2,., п}, при реализации назначения тс. Показывается, что назначение л устойчиво тогда и только тогда, когда в любом подмножестве участников S найдется такой, которому этим назначением предписана лучшая (с точки зрения его предпочтений) работа из множества п (S).

Задачу группировки S назовем дихотомической, если каждое отношение < - разделяет множество R на два класса: R ?+ (хорошие для исполнителя i работы) и R ?" (плохие для исполнителя i работы). В таком случае набор L удобно представлять (пхп) — матрицей L л = { /?, }, в которой: 1V} = 1, еслиг^ е Rj+, и 1ц = 0, если ij е •.

Показано, что для кустойчивости назначения в дихотомической задаче группировки? необходима и достаточна его оптимальность в КЗН, определяемой матрицей ¿-д. Таким образом, кустойчивыми являются те и только те назначения, в которых максимальное число исполнителей получает работы, оцениваемые как хорошие.

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

Изучаемая в § 2.5 задача группировки в пары с учетом взаимных предпочтений участников определяется совокупностью W=, где, А = { а|, а2, .. ., а&bdquo- } - множество объектов первого рода, а — участников (например, исполнителей) — В = {bi, b2,., bn} - множество объектов второго рода, b — участников (например, источников работ) — L1 = { < ь < 2, • • •, ^ п} - линейные порядки, определяющие предпочтения объектов первого рода на множестве приемлемых для них объектов второго рода — L2 = { < < 2,. ., <" } - линейные порядки, определяющие предпочтения объектов второго рода на множестве приемлемых для них объектов первого рода. Система индивидуальных предпочтений участника а{, = 1, 2 ,.. ., п, задается отношением <, которое упорядочивает множество приемлемых для а-, партнеров В, где В, с В. Система индивидуальных предпочтений участника Ь- ,?=1,2,., п, задается отношением < 1, которое упорядочивает множество приемлемых для партнеров, А, где А] с А. Системы предпочтений участников полные, если каждое множество, А совпадает с, А и каждое множество В — совпадает с В.

Пару (аь Ь|) допустима, если а, е В иЬ]еА]. Совокупность Я = { (ац, Ьр), (а,-2, Ц2), • • •, (а-к, Ьд) } именуем решением задачи группировки в пары, если: в каждом из множеств {ап, а)2,. .. , ^ } и { Ь,-ь • • •, Ь^} нет одинаковых элементоввсе входящие в Я пары являются допустимымииз элементов множеств, А и В, не входящих в пары набора II, нельзя образовать ни одной допустимой пары. Решение Я назовем полным, если им объединяются в пары все элементы множеств, А и В.

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

В § 2.6 рассматриваются задачи о назначениях (ЗН), в которых, кроме общего п критерия К 1(71) = X а1 или к2(я)=тт а> следует учитывать индивиду-'=1 альные предпочтения участников. Сначала изучается ЗН с учетом предпочтений исполнителей, определяемая совокупностью III = < ?, А >, где Е = < I, Я, Ь> - исходные данные задачи группировки в пары с учетом односторонних предпочтений исполнителей на множестве работ, а, А = {а^} - матрица оценок. Считается, что исполнители свободны в принятии окончательного варианта распределения работвозможными являются только устойчивые или к-устойчивые назначения, множества которых обозначаются М (Х) и Мк (£) соответственно. Изучаются следующие ЗН с учетом односторонних предпочтений (ЗНОП).

Задача 1: Найти шах К 1(71) при условии, что п е М (1);

Задача 2: Найти шах К2(я) при условии, что л е М (£);

Задача 3: Найти шах К| (л) при условии, что п е Мк (Е);

Задача 4: Найти max К2(я) при условии, что л е М к (Е).

Показывается, что все эти задачи NPтрудны. Приведенные в § 2.4 критерии и способы синтеза устойчивых (кустойчивых) назначений позволяют применять для их решения метод ветвей и границ, а для задач 1 и 2, кроме того, метод динамического программирования.

Устанавливается, что для моделей с дихотомическими предпочтениями исполнителей задачи 3 и 4 сводятся к решению КЗН и разрешимы в полиномиально зависящем от п времени, а задачи 1 и 2 остаются NPтрудными.

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

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

Кроме обычной для КЗН совокупности исходных данных, полагаем определенным начальное назначение я 0 и состав бригад: В (1), В (2),. .. , В (т), где т.

J B (j) cN (N ={1,2,., п} -множество всех исполнителей), B (i) n B (j) = 0 1 для всех i^j, i = 1, m, j =1, m. Переназначение оценивается как по общему критерию К (7г), так и по частным кри териям к ¡-(тс), у~, т. Общий и все частные критерии сначала считаем адекватными — если критерий К (тс) выражает, например, суммарную производительность всех исполнителей в переназначении %, то критерии kj (7t) показывают суммарные производительности отдельных бригад.

Полагаем К (те) =? a-, n (i). Тогда к ¡-(те) =¦ щ n (i), j=l, т. РассматриваеМe?(7) мые критерии считаем максимизируемыми. Переназначение 7t допустимо, если для каждой из бригад оно не хуже исходного назначения (k ?(7t) > к Дл0), j=l, т).

Доказывается NPтрудность проблемы максимизации K (7t) на множестве допустимых переназначений в случаях, когда выделена только одна бригада, и когда каждая из выделенных бригад имеет в своем составе только двух исполнителей.

Изучаются возможности решения задачи максимизации K (7t) на множестве допустимых переназначений методом динамического программирования и применением схемы ветвей и границ.

Существенно более простой оказывается задача о переназначениях с максимизируемым общим критерием Q (7t) = min и критериями бригад q ,(л) = min аn) и максимизируемыми крите1 риями бригад цДя) = min b^,), j=l, т.

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

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

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

В § 3.1 вводится понятие задачи обмена, выделяются важные в прикладном отношении классы задач обмена, отмечается обширность сферы приложений задач обмена (см., например, [76]), формулируются некоторые прикладные задачи.

В § 3.2 рассматривается простейшая задача обмена (ПЗО), т. е. задача простого обмена, в которой каждый участник указывает только множество предметов, любой из которых — желанный.

Исходные данные ПЗО можно представлять конечным ориентированным графом в = (У, А) — вершины графа соответствуют участникам задачи (V = { 1, 2,.. ., п }), а пара (1,]) является дугой ((у) е А), тогда и только тогда, когда принадлежащий участнику ] предмет р (]) для участника I желанный. Циклам графа соответствуют возможные в ПЗО цепочки обмена. Решая соответствующим образом построенную КЗН, мы конструируем решение ПЗО с наибольшим числом обменивающихся участниковв графе О при этом отыскивается система попарно непересекающихся по вершинам циклов (цепочек обмена), покрывающая максимально возможное число вершин.

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

Показывается, что вопрос об отыскании 2-решения с максимальным числом обменивающихся участников сводится к задаче построения в специальным образом построенном неориентированном графе в* наибольшего паросо-четания и решается в кубично зависящем от п времени [122]. Проблемы же определения в ПЗО к-решения, к* - решения или к ** - решения с максимальным числом обменивающихся являются ЫР — трудными в сильном смысле [56] при любом фиксированном значении к > 3.

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

Через у (к)(Я) обозначаем число участников, которые в данном решении обмениваются в циклах, длина каждого из которых не превышает константы к. С учетом важности для реальных задач критериев у (К), у (2)(И), при различных схемах компромисса рассматривается соответствующая двухкритериаль-ная задача.

Через Б (К) обозначим количество цепочек обмена, составляющих решение К. Наряду со стремлением максимизировать общее число обменивающихся участников, часто целесообразно искать решение, реализация которого предполагает выполнение обменов в максимально большом числе циклов. Оказывается, что для ПЗО проблема максимизации значения критерия О (Я) также ЫР-трудна.

Рассмотрим ситуацию, когда в множестве участников ПЗО выделены непересекающиеся подмножества 11, 12,. .. , I р и каждое решение Я характеризуется векторным критерием (у (Я, I 0, у (11, I 2),. .. , у (11, I р)), где у (II, I}) — число участников, входящих в подмножество I з и обменивающихся при реализации решения К,) ~ 1, р. Показано, что проблема существования решения Я* этой задачи такого, что у (11*, 1^ > 1 при всех] = 1, р, полна.

В § 3.2 изучается задача простого платного обмена (ЗППО). Участники ЗППО связывают получение приемлемых предметов с платежами различных знаков. Если участник I для получения предмета р (|) взамен предмета р (0 согласен на положительный платеж то величину этого платежа будем называть доплатой участника I за предмет рфесли же платеж (у) отрицателен, то это размер компенсации, которую требует участник 1 при получении им предмета рО) взамен р (1). Исходные данные ЗППО можно представлять взвешенным ориентированным графом в' = (У, А), вершины которого соответствуют участникам задачи (V = { 1, 2,., п }), пара (1,]) является дугой ((у) е А), тогда и только тогда, когда принадлежащий участнику ] предмет р (]) для участника I желанный- №(¡-, 1) вес дуги (у).

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

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

Проблему распределения получаемого суммарного дохода в задаче обмеа с платежами участников можно описывать как кооперативную игру п лиц. При этом для произвольной коалиции участников Б, Э с {1, 2,. , п}, выигрыш уобм (8) определяем как максимальное значение суммы платежей в частной задаче обмена, получаемой из исходной изъятием всех не входящих в Б участников. Функция у0бм (8) супераддитивна и определяет кооперативную игру п лицпоказано, что каковы бы ни были исходные данные задачи платного обмена, эта игра обязательно обладает ядром.

В § 3.3 изучается задача простого обмена с индивидуальными предпочтениями участников (ЗПО с ИПУ), определяемая совокупностью О = { I — Р — I'-, ¡-е!}, где I {1,2,., п} - множество участниковР ~ {р (1), р (2),., р (п)} -множество предметов (по начальным данным участнику 1 принадлежит предмет р (1), I е I) — Р- - множество предметов, более предпочтительных для участника I в сравнении с р (0, Pi с Р, р (1) ёР|, 1 е I — < ! — квазилинейное упорядочение множества Р-* = Ри {р (0}, выражающее предпочтения участника I, I € I .

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

Пусть К — произвольное подмножество участников, Кс I. Через р (К) обозначаем множество предметов, по начальным данным принадлежащих участникам подмножества К.

Решение % ЗПО с ИПУ назовем некомпрометируемым (кнекомпрометируемым), если не существует (не более чем кэлементной) коалиции К участников, способных перераспределить между собой совокупность предметов р (К) так, что каждый член коалиции получит в результате лучший для себя предмет в сравнении с предметом, получаемым при реализации решения к.

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

Некомпрометируемые и, одновременно, стабильные решения ЗПО с ИПУ называем устойчивыми. Решение называем кустойчивым, если оно к-стабильно и кнекомпрометируемо одновременно.

Устанавливается, что каждая ЗПО с ИПУ О обладает устойчивыми решениями, излагается процедура, А синтеза устойчивого решения. Данная процедура, вообще говоря, неоднозначна, но любая ее реализация строит устойчивое решение. Отметим, что применениями процедуры, А может быть построено, вообще говоря, пе любое устойчивое решение задачи О — это утверждение верно и для частного класса задач, в котором каждый участник строго линейно упорядочивает подходящие ему предметы (здесь процедура, А работает однозначно). Далее вводится новая, ограниченная концепция Аустойчивости, которой удовлетворяют только решения, конструируемые процедурой А.

Показывается, что множество Аустойчивых решений задачи О совпадает с совокупностью решений, являющихся неблокируемыми [72,75].

Решение 71 ЗПО с ИПУ называем строго некомпрометируемым, если не существует коалиции участников К, члены которой могут перераспределить между собой множество изначально принадлежащих им предметов так, что каждый входящий в К участник получит предмет, с точки зрения его предпочтений не худший, а по меньшей мере один из таких участников — предмет, лучший чем в результате реализации решения 7 Т.

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

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

Решения и п2 ЗПО с ИПУ для участника I равноценны, если он одинаково оценивает предметы р^О)) и р (7с2(0). Эти решения эквивалентны, если они равноценны для каждого из участников. Показано, что если щ и к2 -два строго устойчивых решения ЗПО с ИПУ, то они эквивалентны между собой.

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

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

Как очевидно, концепция внутренней устойчивости представляет собой существенное ослабление общей концепции устойчивости.

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

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

В реальных задачах обмена большой размерности каждого участника, как правило, можно отнести к некоторому тину, причем число типов является ограниченным. В связи с этим вводится понятие стандартного класса задач обмена групповой структуры. Для того, чтобы в стандартном классе с п группами однотипных участников определить конкретную ЗПО с ИПУ, необходимо указать п-мерный вектор состава W = (wbw2,., w п), где w? — количество участников в группе g i, i = 1, п .

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

В § 3.4 изучается простейшая модель обмена-распределения, в которой имеются: множество обменивающихся участников (каждый из них обладает некоторым предметом, но желает обменять его на более приемлемый) — множество участников, каждый из которых, не обладая никаким предметом, желает получить некоторый подходящий — множество предметов, принадлежащих обменивающимся участникаммножество предметов, не имеющих обладателей. Вводятся критерии, выражающие число обменивающися участников и число участников, впервые получающих некоторый предмет. Получаемая двухкрите-риальная задача решается «потоковыми» методами.

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

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

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

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

В § 4.1 рассматривается каноническая задача обслуживания, состоящая. в следующем. Однопроцессорная система должна обслужить поток заявок Z = {1, 2, ., п}. Каждая заявка i характеризуется целочисленными параметрами: t (i) — момент поступления (0 = t (l) < t (2) <. .. < t (n)) — t (i) — требуемая продолжительность обслуживанияa (i) — коэффициент функции штрафа, i =1,й. Если обслуживание заявки i завершается в момент t*(i), то величина штрафа по ней равна a (i) [t*(i) — t (i)]. Процессор готов к обслуживанию заявок потока начиная от t = 0. Обслуживание каждой заявки реализуется без прерываний, одновременное обслуживание процессором нескольких (более одной) заявок невозможно. Требуется найти расписание (перестановку номеров заявок), минимизирующее значение суммарного штрафа.

Данная задача NPтрудна в сильном смысле. Отнесем ее к классу К1 (р), если среди величин t (i), i =1, 2,., n, имеется не более р различных, и к классу Кц (q), если среди величин ji (i) = a (i) / x (i), i ~, n, имеется не более q различных.

Для задач класса К1 (1) известен простой алгоритм синтеза оптимального расписания (см., например, [166]): вычислив величины jj.(i) = a (i) / x (i), i=l, u, упорядочить заявки по убыванию значений jx (i) .

Задачи класса Кц (1) возникают в достаточно типичной ситуации, когда штраф за единицу времени простоя прямо пропорционален грузоподъемности транспортного средства, а, следовательно, и времени погрузки (разгрузки). Устанавливается, что для задач класса Кц (1) перестановка р° = (1,2, ., п) является оптимальным расписанием обслуживания.

Таким образом, вычислительная сложность задач классов К1 (1) и Кц (1) имеет порядок n III и (совпадает со сложностью сортировки пэлементного числового массива).

Доказывается, что задачи классов К1 (2) и (2) являются NPтрудными.

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

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

ЧМ 1. Заявки аи[5 называем однотипными, если т (а) = т (Р) и а (а) = а (Р). Вводится ограничение сверху на число типов заявок в потоке Z.

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

ЧМ 3. Заявка р обгоняет заявку а, если, а < Р, но заявка Р обслуживается раньше заявки а. Разность Р — а именуем длиной обгона. Расписание р называем dрасписанием, если при его реализации длины обгонов не превышают константы d. Допустимыми в рамках модели считаются только dрасписания.

ЧМ 4. Расписание р называем {q} - расписанием, если при его реализации любую заявку обгоняют в обслуживании не более q других заявок. Расписание допустимо, если оно является {q}- расписанием.

ЧМ 5. Через r)(t) обозначим последнюю из поступивших на момент времени t заявок. Пусть M (t, S, d) = {j |у (S) + d < j < rj (t) }. Расписание p назовем (d, q) -расписанием, если при его реализации в любой момент времени t в множестве M (t, S, d) оказывается не более чем q завершенных обслуживанием заявокздесь q — целочисленная константа, принадлежащая отрезку [0, п — 1] .Таким образом, в реализации (d, q) — расписания любая заявка i может быть обогнана в обслуживании: а) заявками из совокупности {1 + + 2, ., I + ё}- б) не более чем я другими заявками. Значение критерия суммарного штрафа минимизируется на множестве (с!, я) — расписаний.

ЧМ 6. Специфика модели заключается в двух условиях:

1) каждая заявка входного потока может находиться в системе обслуживания не более Т единиц времени (Т — априорно заданная константа);

2) в течение любого отрезка времени длины Т в систему поступает не более к заявок — множество заявок, имеющихся в очереди на обслуживание по состоянию на момент времени 0, тоже не более чем к — элементно.

Для каждой из перечисленных ЧМ строятся полиномиальные алгоритмы синтеза оптимальных расписаний.

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

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

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

Идея простейшей версии первого эвристического алгоритма {(р, ц) — алгоритма, здесь р и ц — небольшие натуральные числа, п > р > ц) заключается в сле-дующем.На первом этапе расписание Я инициализируется пустым расписанием, а множество С необслуженных заявок — совокупностью {1,2, ., п}. Далее из С выбираются р первых заявок, строится оптимальное расписание их обслуживания. Начальный сегмент полученного расписания, включающий ц заявок, переносится в синтезируемое расписание Я, остальные выбранные заявки возвращаются в С. Процедура циклически повторяется вплоть до исчерпания совокупности С.

Верхняя оценка числа элементарных операции для изложенной версии (р,<.|)-алгоригма С п, где С определяется только значениями р и ц. Если оптимальные решения задач с р заявками синтезируются методом динамического программирования, то С линейно зависит от дроби (р22р)/ц. Чем больше р и меньше ц, тем выше ожидаемое качество решения и трудоемкость его синтеза. Концепция (р, я) — алгоритма играет существенную роль для периодов с относительно большим горизонтом планирования, когда точной является информация о моментах поступления только нескольких первых заявок.

Принцип построения второго эвристического алгоритма {алгоритма вставки) заключается в следующем. Пусть имеется расписание Я к обслуживания первых к заявок (к < п). Выполняется вставка заявки к + 1 на первое, второе,., (к+1) -ое место в расписании Я к — для каждого из получаемых расписаний вычисляется суммарный штраф, лучшее из расписаний фиксируется как И ^ +1. Процесс начинается от расписания II) и продолжается вплоть до построения Яп. Оценка временной вычислительной сложности алгоритма Сп 2.

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

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

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

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

В § 5.2 рассматривается и решается задача синтеза оптимальною расписания обслуживания конечного детерминированного потока заявок одним mobil-процессором (перемещаемым процессором). Известен поток заявок Z = {zbz2,., zn}, проходящих транзитом рабочую зону mobilпроцессора. Зона представляет собой отрезок AB длины L. В пределах зоны процессор может перемещаться как в автономном режиме, с зависящей только от направления движения скоростью, так и в паре с обслуживаемой заявкой с ее скоростью. Обслуживание любой заявки — однофазноеоно может выполняться: а) в стационарном режиме при совместном нахождении процессора и обслуживаемой им заявки в одной точке зоныб) в режиме совместного движения заявки и процессора (движение осуществляется со скоростью заявки) — в) в смешанном режиме, чередующем два вышеуказанных. Процессор не может обслуживать более одной заявки одновременно, переналадки отсутствуют, прерывания запрещены. Поток Z состоит из подпотоков: Z1 — заявок, следующих в направлении ЛВ, и Z2 — заявок, следующих в направлении ВА. Отрезок AB удобно считать разбитым на ш+1 элементарных участков равной длины, последовательно пронумерованных числами от нуля до т. Обязательным является обслуживание только специально выделенных привилегированных заявок.

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

В § 5.3 рассматривается задача синтеза оптимальной последовательности обработки заявок в однопроцессорной системе с накопителем ограниченной емкости. Данная задача возникла при создании компьютерных средств поддержки оперативного планирования и регулирования процессов грузовой обработки танкерного флота в условиях короткой навигации нижней Оби. Математическая постановка задачи отличается от канонической следующими дополнительными компонентами. Каждая заявка Ъ потока Ъ имеет объемную характеристику V) и принадлежит одному из двух подпотоков, 1) (заявок с горючим, которое должно быть слито в накопительную емкость) и 7} (заявок, требующих горючее из емкости). Накопительная емкость Ь имеет объем V и начальное (на момент времени 1=0) заполнение У0. В результате обслуживания заявки ъ из подпотока.

I «).

Z ^) заполнение емкости Ь увеличивается (уменьшается) на величину V-.

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

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

В заключении сформулированы основные научные и практические результаты работы.

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

На защиту выносятся:

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

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

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

4. Результаты о полиномиальной разрешимости ряда выделенных, имеющих существенное прикладное значение, частных классов введенных труднорешаемых (ИР-полных или трудных) задач принятия решений.

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

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

§ 5.4. ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО ГЛАВЕ 5.

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

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

9. На основе разработанных моделей и алгоритмов созданы программные средства информационно-аналитической поддержки процедур принятия плановых и управленческих решений в системах внутреннего водного транспорта (Камский грузовой район, Уфимский речной порт). Внедрение указанных средств позволяет на качественно новом, существенно более высоком уровне решать задачи оперативного планирования и диспетчеризации. Установлена практическая применимость разработанных процедур решения многокритериальных модификаций задачи о назначениях и задач группировки в процессах управления науч-но-иссседовательскими и опытно-конструкторскими работами (Нижегородский филиал НИИ спецтехники МВД РФ). Социально-экономический эффект внедренных разработок определяется обеспеченным качеством и обоснованностью принимаемых решений. Математические модели, принципы и алгоритмы решения задач обмена послужили основой созданной и внедренной в эксплуатацию автоматизированной системы обмена жилья АСОЖ «Волга».

.