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



..^РОССИЙСКАЯ АКАДЕМИЯ НАУК ^'"ИНСТИТУТ I П'ОШИ'М У1 И'АВЛ!-! 1ИЯ

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

Специальность: 05. 13. 10 - Управление в социальных

и экономических системах

Автореферат диссертации на соискание ученой степени доктора технических наук

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

Коган Дмитрий Израилевич

Москва - 1999

Работа выполнена в Нижегородском государственном университете

Научный консультант:

- доктор технических наук, профессор Батищев Д.И. Официальные оппонен т:

- доктор физико-математических наук, профессор Шкурба В.В.

- доктор технических паук Новиков Д.Л.

- доктор технических паук Чиркова М.М.

Ведущая организация: Санкт-Петербургский экономико-математический институт РАН

Защита состоится ¿3 , 12 1999г. в час.

на заседании Диссертационного Совета Д. 002.68.03 Института проблем управления РАН по адресу: 117806, Москва, ул. Профсоюзная, д.65.

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

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

"/Я" ^

1999 г.

Ученый секретарь Диссертационного совета

к.т.и. Власов С.Л.

ОЫЦЛЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

все 01Ш формализуются в рамках моделей математического программирования транспортного типа.

кпчссмн) получнсмых рСШСИПП, ВОЗМОЖНОСТЬ ИЧ >ффек1ШШ010

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

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

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

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

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

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

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

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

Исследования по теме диссертационной работы выполнялись в соответствии с координационными планами АН СССР по комплексной проблеме "Кибернетика" на 1981-85 и 1986-90 гг., поддержаны грантами Российского фонда фундаментальных исследований (93-013-16253 программы 1993-95гг, 97-01-01095 программы 1997-99гг.). Прикладные разработки осуществлялись в рамках тем бюджетных н договорных ПИР Волжской государственной академии водного транспорта.

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

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

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

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

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

многокритериальной и комбинаторной оптимизации, теории графов, теории расписаний, а также ряд ранее выполненных работ в областях распределения и перераспределения ресурсов, транснортною планирования и совершенствования эксплуатации водного транспорта. При выполнении исследовании автор опирался на теоретические результаты отечественных н зарубежных ученых (Батищев Д.И., Бурков В.П., Воробьев 11.1!., Гермейер Ю.Б., Гольштейн Е.Г., Емеличев В.А., Захаров В.Н., Кацпельсон М.К., Ларичев О.И., Ловецкий C.IÍ., Подиповский U.U.. Сигал И.Х.. Tannen B.C.. Шкурба В.В., Юдин Д.Б., Bellman R., Conway K.W., Cook S.A., Cíale O., Ciurey М., Isermann Н.,Johnson D., Karp R.M., Lawler ii.I... Lcnsira J.К., Shapley L. и Др.).

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

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

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

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

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

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

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

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

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

Полученные научные результаты включены в читаемые на факультете вычислительной математики и кибернетики Нижегородского

б

государственного университета учебные курсы «Системный анализ» и «Распределительные задачи планирования и управления» и внедрены в учебный процесс n;i фпкулмсшх Волжской теударс)пенной академии водного ipaiiciiopia.

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

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

Публикации. По теме диссертации опубликовано 59 работ; основное содержание отражено в [1-30].

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложений (323 страницы текста, включая 16 рисунков, Í схему, 17 таблиц); список цитированной литературы составляет 202 наименования.

СОДЕРЖАНИЕ PABOtbl

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

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

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

U § 1.2 в применении к транспортным задачам рассматриванием различные схемы компромисса (свертки критериев). В достаточно типичной ситуации, когда выбор конкретной схемы затруднителен, целесообразно использование концепций эффективной оценки и Парето-оптимального решения. Излагается принадлежащая Aneja Y. и Nair К. методика синтеза полной совокупности эффективных оценок для бикритериальной транспортной задачи линейною программирования (ТЗЛП). Далее проблема синтеза эффективных оценок анализируется для целочисленной бикритериальной ТЗЛП; решается вопрос о построении эффективных оценок, примыкающих к одной из крайних, получаемых . лексикографическим упорядочением критериев, оценок.

В § 1.3 изучается ТЗЛП с общим критерием и оценками участников

шш I С(Х).СДХ), 1=1,и ,сДх)о=1,»], (1.3.1)

ХеО

гп и „

|дс: С'(Х) Х2!счх1| оГицне транспорт!,ю издержки: С'ДХ) = £ РчХд.-¡-1) 1 /•'

т

оценки плана X пунктами производства А|. ¡=1./н; С] (X) = £ -

ы

оценки плана X пунктами потребления В}, О - совокупность планов. Оценки плана пунктами производства и пунктами потребления задаются парой (тхп)-матрнц Р~{рп( и 0={ЯиЬ Называем их дихотомическими, если матрицы Р и У состоят из нулей и единиц. Дихотомической системой оценок каждый пункт производства,и каждый пункт потребления разбивает совокупность возможных партнеров на два класса: «хорошие» и «плохие». План X для каждого из участников тем лучше, чем большее количество продукта перевозится но коммуникациям, связывающим участника с «хорошими» для него партнерами.

План X называем (а.А)-илаиом (а-(«.|.а?,...,«.,„)), если

¿р,.г, ТЯ (1.3.2)

ч (Р,В)-иланом (р=(р,.р2,...рп)), если

£ чих,*^, у = (1.3.3)

».г

план X именуем (а,(1)-иланом, если (1.3.2) и (1.3.3) выполняются одновременно.

Проблемы существования в (1.3.1) планов, удовлетворяющих условиям (1.3.2) и (или) (1.3.3), решаются в полиномиально зависящем от размерности задачи времени. При дополнительном требовании целочисленности искомых планов эти проблемы становятся полными.

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

существования (а.Р)-плапа для любых векторов а - (о.|,а,.....а1П) и

(|)|,|>2.--Р,,) сиодшся к вопросу отыскания потока максимальной мощности в специально построенной сети с 2(т + п + 1) вершинами.

План Хей назовем (а,Р)-оптималышм, если он минимизирует значение критерия С(Х) при дополнительных ограничениях (1.3.2) и (1.3.3). Синтез (а,р)-оптималыюго плана - задача линейного программирования. Задача же построения целочисленного (а,Р)-оптимального плана ЫР-трудна.

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

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

В § 1.4 рассматриваются транспортные задачи, в которых, кроме общего критерия издержек, следует учитывать индивидуальные предпочтения участников. Пусть С - цикл перераспределения поставок, определяемых планом X; для любого охваченного циклом участника и объем поставки по одной из инцидентных ему коммуникаций уменьшается на е >0, а по другой на ту же величину увеличивается . Цикл С назовем не ухудшающим (улучшающим) (иноспicjh.no и, если партнер, для которого поставка по связывающей с н коммуникации увеличивается, для и не менее предпочппелеп (более предпочтителен), чем партнер, для коюрого поставка по связывающей с и коммуникации уменьшается. Пусть и -произвольное множество участников. Цикл С назовем V- улучшающим, если он по меньшей мере для одного участника из II является улучшающим, а для остальных входящих в и участников - не ухудшающим. План назовем и - устойчивым, если не существует изменяющего этот план и -улучшающего цикла.

Пусть Р = { ру } и () = { я, } - матрицы оценок, соответствующие наборам Ьл и Ьц(более предпочтительным партнерам соответствуют

меньшие оценки). Введем оценки РДХ) ~ £ р^ плана X пунктами

__т

производства Д1, ¡=1,»>, и оценки ОДХ) = £ Яухч того же плана пунктами

1-1

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

Теорема 1.4.1. Для любой транспортной задачи с индивидуальными предпочтениями участников множества I) - устойчивых и и - эффективных планов совпадают.

План перевозок X назовем А-эффектывным, В-эффективным или (АиВ)

-эффективным, если он I/-эффективен при I/. равном (Л|.Л7.....А,,,}.

¡Н|.1$.>.....В„! или ¡Л|. А >.....А,,,. И|, !$_>,...,В,,} соотишстмснн».

Для произвольною множества участников и через иЛ (ив) обозначим множество индексов ! (индексов ¡) таких, что Л.еП (В,еи). Очевидно, что планы перевозок, он гнмальные для ТЗЛП

(1-4.1)

являются П-эффсктиннмми.

Множество и именуем однородным, если оно имеет в своем составе только пункты производства или только пункты потребления.

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

Получаем, что при дихотомических предпочтениях участников проблемы минимизации |р;шсиортпих издержек на множествах А-эффект тип н.1 \ п И- эффективных планов сводятся к однокритернальпым ТЗЛП

( (Хр,; + Си>Х,|1

и

[(Н] + Су)х^]

•е /»I

соответственно, здесь X - достаточно большая константа.

В ситуации, когда любой пункт производства. А1 и любой пункт потребления В, имеют возможность совместно определить объем перевозки X;, по связываю/ней их коммуникации, целесообразно принятие концепции устойчивости, соответствующей принципу Гейла-Шепли. Решение X транспортной задачи с взаимными предпочтениями участников назовем устойчивым по Гсйлу- Шспли (Г- устойчивым), если не сущестпует пункта производства Л, и пункта потребления которым, исходя из имеющихся предпочтений, целесообразно увеличить поставку из Л,- в В,- на некоторую положительную величину е за счет соответствующего уменьшения поставок из А, в менее предпочтительные для А, пункты потребления и поставок в В} из менее предпочтительных для В| пунктов производства.

Излагается адаптация алгоритма Гейла - Шепли, реализующая синтез Г-устойчивых планов для транспортной задачи с индивидуальными

предпочтениями участников. В случае, когда системы предпочтений строго линейны, адаптированный алгоритм в любом из режимов работает однозначно; в противном случае каждая из возможных его реализаций синтезирует Г-усггойчивое решение. Адаптированный алгоритм, функционирующий в режиме «пункты производства делают предложения пунктам потребления», назовем алгоритмом I; тог же алгоритм, работающий в режиме «пункты потребления делают предложения пунктам производства» - алгоритмом 2.

Теорема 1.4.3. Решение Х| транспортной задачи с полными линейными системами взаимных предпочтении, конструируемое алгоритмом I, нвлнстси Г -устойчивым решением, н шшГншмнсМ возможной степени удовлетворяющим предпочтения каждого из пунктов производства, а решение Хг, конструируемое алгоритмом 1, является Г -устойчивым решением, в наибольшей возможной степени удовлетворяющим предпочтения каждого из пунктов потребления.

Теорема 1.4.4. В транспортной задаче с полными строго линейными системами взаимных предпочтений участников каждый Г-устойчивый плап одновременно является (АиВ). эффективным.

Теорема 1.4.5. В транспортной задаче с неполными строго линейными системами взаимных предпочтений участников Г -устойчивое решение существует тогда и только тогда, когда оно строится алгоритмом 1 (утверждение сохраняет справедливость и в отношении алгоритма 2).

Оценки p¡j и q¡¡ реализуемы в плане X, если xv >0. При строго линейных системах предпочтений участников решается задача синтеза Г-усгоичнвого плана, минимизирующего максимальное нт значении реализуемых оценок. Исследуются задачи оптимизации общего критерия на множествах Г-устойчивых планов, конструируются алгоритмы синтеза компромиссных решений.

В § 1.5 излагается ряд относящихся к многокритериальным транспортным задачам результатов об NP- полноте или NP- трудности. Сложность проблемы описания полной совокупности эффективных оценок для ТЗЛП с двумя общим критериями подтверждает

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

Следующая теорема дает оценку трудоемкое™ метода главного критерия в применении к ТЗЛП с линейными оценками одной из групп участников.

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

Идентичный результат относительно ((к,к,..., к),А) - планов также справедлив.

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

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

В § 2.1 излагается концепция задачи о назначениях (311). В каждой

однокритериальной ЗН имеются множество исполнителей {1,2.....п'(,

множество работ {Г|,Гз,...,гп} и (пхп)-матрица оценок А-¡а,,}, где а^ - оценка закрепления исполнителя i за работой rj. Каждая оценка является целым неотрицательным числом или специальным символом запрета ь>. Назначение

- взаимно однозначное отображение множества {1,2.....п} в себя; назначение

я исполнителю i предписывает работу г^о , оценка такого закрепления аад. Назначение я допустимо, если для всех i имеет место а, л(0 t го . 11устт. 11 множсспш допустимых назначений. Формулируются задачи:

ailtli), (2.1.1); mJn £ ailt(i), (2.1.2); max min a; „(i), (2.1.3); min tnax ai . (2.1.4)

jtsH i t

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

и

В § 2.2 рассматриваются проблемы синтеза полных или достаточно представительных совокупностей эффективных оценок для ЗН с двумя аддитивными критериями и вопрос о реализации для этой задачи метода последовательных уступок по значению ведущего критерия. Двухкритериальная задача о назначениях (ДКЗМ) записывается и виде: max'{ Q,(k) , <}2(я)} (2.2.1)

яеН

wQ,(it)=¿ amll) hQ2(jí)=¿ bta(1).

i-i »i

С ДКЗП ассоциируется соответствующая ПЛИ с крщсрнями (.Мл) н <^>¿(n). Совокупность эффективных оценок последней в кршернилыюи плоскости представляется выпуклой ломаной L, все вершины которой для исходной ДКЗН также являются эффективными оценками: эти оценки естественно именовать вершинно-определимымн. Кроме того, эффективные для ДКЗН оценки можно получать решением однокритериальных задач, получаемых линейной сверткой критериев Q((л) и Q?(ji) с варьируемыми весами; такие оценки будем именовать линейно-определимыми. Каждая вершинно-определимая оценка является линейно-определимой (обратное неверно). Кроме того, в ДКЗН могут иметься и линейно неопределимые оценки.

'Г е о р е м а 2.2.1. Для любого натурального п существует- ДКЗН (2.2.1), множество эффективных оценок которой имеет в своем составе п! различных элементов.

Вычислительную сложность проблемы синтез:! полной совокупности эффективных оценок Г.(/.) для произвольной ДК'Щ /. .чарамеризуин и следующие результаты.

Теорема 2.2.2. Проблема определения по исходным данным задачи Z, целым числам С| и С2, существует ли в задаче Z назначение л такое, что Qi(ti) > С| и Q2(it) > С2, является NP-полной.

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

Теорема 2.2.3. Проблема определения по исходным данным задачи Z и назначению л , относится ли оценка (Q,(я). Q_>(rt)) к числу неэффективных, является Nl'-полной.

Парето-оптимальные назначения 7t¡ и я2 в задаче У. назовем соседними, если не существует Парсто-оптимальною назначения п шкого, что что Qi(ti) 6[Qi(k,),Q,(w2)] и Q,(n) g rQ2("i).Q2(íti)|.

u

Теорема 2.2.4. ЫР-полна проблема определения по исходным данным задачи Ъ и Парето-оптимальным для нее назначениям 7Г| и ть, не являются ли они соседними.

Теорема 2.2.5. ЫР-трудны проблемы определения по исходным данным задачи Ъ, являются ли все ее Парето-оптимальные решения: а) линейно определимыми; б) вершинно-определимыми.

Теорема 2.2.6. ЫР-трудна проблема определения по исходным данным задачи Ъ, содержит ли множество ее эффективных оценок больше двух элементов.

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

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

Изложенная технология реализации последовательных уступок и знание общей геометрической структуры множеств -»ффекмшнмх в ДКЧ11 (2.2.1) оценок позволяет отыскивать компромиссные решения таких задач в интерактивном режиме. При этом сначала определяются две крайние эффективные оценки Р* = <Ыл*)) и Р** = (О,(л**), 0:(я**))-

Если ЛПР не может в качестве компромиссной выбрать одну из лих, по рассогласование критериев невелико, с целью построения достаточного фрагмента совокупности эффективных оценок можно применить технологию последовательных уступок. В противном случае далее строится ломаная 1. - совокупность эффективных оценок для соответствующей двухкригериалыюй ТЗЛП. Вершины ломаной обозначим I'*, Р|, Р>, .. ., Р„ Р** . ЛПР либо выбирает в качестве компромиссной одну из некрайних вершин ломаной, либо указывает, в каком диапазоне (Р*, Р,), (Р|, Р|+|) где ¡е{1,2,...,с-1}, ( Рс, Р**,), определяющем |раннцы изменения критериев, следует искать компромиссную точку. Показывается, что

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

Далее для решения рассматриваемой проблемы рассмотрены вопросы применения методов динамического программирования и схемы ветвей и границ. Опишем технологию синтеза полной совокупности эффективных оценок с использованием рекуррентных соотношений, основанных на двухкритериальном аналоге принципа динамического программирования. Задачу (2.2.1) условно назовем задачей W. В нолем и рассмотрение частные задачи W(i ,S); и каждой такой задаче между исполни)елями множеиша ¡1. 2, ..., i} следует распределить работы совокупности S,. здесь i t (I, 2,..., nj, а S - произвольное i - элементное подмножество работ; оценки закреплений исполнителей за работами по первому и второму показателям задаются соответствующими элементами определяющих исходную задачу W матриц А и В . Для множества эффективных оценок в задаче W примем обозначение Е, для множеств эффективных оценок в задачах W(i ,S) -обозначение E(i ,S). Как очевидно,

E(l, {rj}) = (aij,b|j), j =1, 2,... ,n .

Для любого множества оценок М через efl' [М] обозначим подмножество недомннируемых (эффективных) оценок в М: (х,у) из М принадлежит eff [М], если в М не найдется отличной от (х,у) оценки (u,v) такой, что u > х и väy. Для произвольного вектора (х,у) имножества оценок М через (х,у) © М обозначим множество оценок, каждая из которых предстанима как сумма вектора(х,у) и некоторой оценки из М.

Тогда

E(i ,S) = eff [|J (К- bjj) ® E(i - 1 ,S\ |.ü))].

Реализуя вычисления по построенным соотношениям, получаем в их итоге совокупность E(n, { г|, т2, ... ,г„ }) , представляющую собой полное множество эффективных оценок для исходной задачи W.

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

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

Пусть (аьЬ|) и (а2,Ь2) - несовпадающие (а|>аг) эффективные оценки, обеспечиваемые найденными назначениями. Тогда верхней оценкой для корня дерева вариантов берем вектор (аьЬг). а в изначально пустое текущее множество векторов-рекордов R включаем (ai,b|) и (аг,Ь2); эта же пара векторов определяется как система нижних оценок для корпя. Из корня исходит п ветвей, i-ая ветвь соответствует закреплению за исполнителем 1 работы r¡. Далее при двух возможных лексикографических упорядочениях критериев решаются соответствующие полученным вершинам частные задачи; найденные оптимальные назначения соотносят с каждой новой вершиной пару векторов. Для объединения множества некшром, входящих и полученные пары, с совокупностью U решается задача иыделения множества недоминируемых оценок; выделенное множество принимается в качестве новой совокупности R. Приписанная каждой полученной вершине пара векторов является системой нижних для нее оценок и, аналогично предыдущему, определяет вектор- верхнюю оценку в этой вершине. Далее в соответствии с общей идеологией схемы вегвей и границ процесс развивается аналогично изложенному. Полученное в завершение множество векторов-рекордов является полной совокупностью эффективных оценок для рассматриваемой задачи. Изложенный метод обладает характерными для схемы ветвей и границ достоинствами. В частности, его легко адаптировать к случаю, когда нужно найти не полную совокупность эффективных оценок, а только те из них, которые удовлет воряют некоторым пороговым ограничениям на значения первой и второй координат.

В § 2.3 рассматривается задача

шах | X 11 с mu . »'i» Ь, „,„} , ( 2..V I)

яеН

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

В § 2.4 рассматривается задача группировки в пары с учетом односторонних предпочтений. Она определяется совокупностью X = < I, R, L>, где I = {1, 2, . . . , п} - множество обьектон первого типа ( исполнителей ); R = {гt, г2,. .., r„ ¡ - множество объектов второго типа (работ); L = { < |, <2, ...,<„} - линейные упорядочения, определяющие предпочтения исполнителей па множестве работ.

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

устойчивым, если не существует коалиции участников 8 . 1, 2.....л),

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

Очевидно, что любое к- устойчивое назначение устойчиво. Вели в Ь все отношения 5 - строгие линейные порядки, то совокупности устойчивых и к- устойчивых назначений совпадают.

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

Задачу группировки 2 назовем днхо|омической. если каждое отношение <(раздсляег множество К па два класса: К (хорошиедля исполнителя 1 работы) и Я ¡" (плохие для исполнителя I работы). В таком случае набор Ь удобно представлять (пхп) - матрицей /,,, = { /у }, в которой: 1ц = 1, если е Я ¡\ и /у = 0, если г> е. К < .

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

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

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

Изучаемая в § 2.5 задача группировки в пары с учетом взаимных предпочтений участников определяется совокупностью Ч'=<А, В, Л ', £ 2>, где А = { а| , а2, . . ., а„ } - множество объектов первого рода, а -участников (например, исполнителей); Я = {Ь| , Ь2 Ь„ } - множество

объектов второго рода, Ь - участников ( например, источников работ); ¿' = { < I, < 2, . . . , < „} - линейные упорядочения, определяющие предпочтения обьсктон первого рода па множестве приемлемых для них объектов второго рода ; /."-{<', 2 2, ...,<"} - линейные упорядочения, определяющие предпочтения объектов второго рода на множестве приемлемых для них объектов первого рода. Система индивидуальных предпочтений участника а; , 1 = 1, 2 ,.. ., п , задается отношением < | , которое упорядочивает множество приемлемых для а, партнеров В (, где В ; с В. Система индивидуальных предпочтений участника Ь, , ] = 1, 2 , . . ., п , задается отношением < 1 , которое упорядочивает множество приемлемых для Ь; партнеров А ], где А ; с А. Системы предпочтений участников полные, если каждое множество Л , совпадает с А и каждое множество В , совпадает с В.

Пару (а;, Ь,) допустима, если а, е В и Ь^ е А у. Совокупность К = { (ап, Ь^), (ац, ^2), . . . , (ац,, Ь^) } именуем решением задачи группировки в

пары, если: в каждом из множеств {а,т, а|2.....«ц | и { Ь,|, Ь,>.....Ь^!

нет одинаковых >леме1пои; все входящие и К нары ивимюкя допустимыми: из '¿цементов множеств А и В , не входящих в пары набора И, нельзя образовать ни одной допустимой пары. Решение Я назовем полным, если им объединяются в пары все элементы множеств А и В.

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

В § 2.6 рассматриваются задачи о назначениях (311), в которых, кроме

общего критерия К^и) = а; или К2(л)-тт а| „(¡), следует учитывать

1=1

индивидуальные предпочтения участников. Сначала изучаемся ЗП с учетом предпочтений исполнителей, определяемая совокупностью = < I, А > , где Е = < I, Н, Ь> - исходные данные задачи I рушшровкн в пары с

учетом односторонних предпочтений исполнителей на множестве работ, а А = {ajj} - матрица оценок. Считается, что исполнители свободны в принятии окончательного варианта распределения работ; возможными являются только устойчивые или к- устойчивые назначения, множества которых обозначаются М(£) и М к(£) соответственно. Изучаются следующие ЗН с учетом односторонних предпочтений (31 ЮН).

Задача 1: Найти max Ki(jt) при условии, что я е М(1);

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

Задача 3: Найти max К|(я) при условии, что л е Mk(I);

Задача 4: Найгн птах К2<тг) при yciiomm, что л • M^i).

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

Рассмотрим задачи 1 и 2 . Пусть U* - произвольная подмодель модели Ui , получаемая из нее изъятием некоторого множества исполнителей и такого же по мощности множества работ. Имеющиеся в подмодели V* множества исполнителей и работ обозначим 1* и R* соответственно. Оптимальные значения критериев К^тс) и K2(it) в задачах I и 2 дня подмодели И* обозначим K((U* ) и K^IJ* ) соотнесшем по. В силу принятых обозначений K|(Ui) и K2(U|) - искомые оптимальные значения критериев задач 1 и 2 соответственно. Через U* [ i, г, | обозначим модель, получаемую из U* изъятием имеющихся в ней исполнителя i и рабои.1 г,.

Теорем а 2.6.1. Имеют место следующие cooiношения:

K|(U*)-max | max |a(i i K,(ll*| i, г, | )| !; tJ.(.l) i e I* je R*(i)

K2(U* ) = max { max min |a,j , K2(ll*| i. | )| J; (2.6.2) i e 1* je R*(i)

здесь R*(i) обозначает множество номеров лучших для исполнителя i (с точки зрения его предпочтений) работ из совокупное in R*.

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

Теорема 2.6.2. Экстремальные задачи 1,2, 3, и 4 N1'-трудны.

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

Теорема 2.6.3. Для моделей с дихотомическими предпочтениями исполнителей задачи 3 и 4 сводятся к решению КЗН и разрешимы в полиномиально зависящем от п времени.

Теорема 2.6.4. Для моделей с дихотомическими предпочтениями исполнителей задачи 1 и 2 являются NP-трудными.

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

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

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

. . ,В(ш) , где (J B(j) с N (N ={1, 2, . . . ,n¡ множество всех

исполнителей), B(i) n B(j) = 0 для всех i - im. j -I,ш. Переназначение оцснппаскя как по общему критерию К(л). ык н но частым кртернмм К Дл), j=l,m. Общий и все частные критерии сначала считаем адекватными -если критерий К(я) выражает, например, суммарную производительность всех исполнителей в переназначении п, то критерии к /я) показывают суммарные производительности отдельных бригад.

Полагаем К(я) = £ a¡ *(¡, . Тогда к ¡(л) ^ £ a¡ „(i| , ¡=¡7T".

a in а

Рассматриваемые критерии считаем максимизируемыми. 11ерепазпачение п допустимо, если для каждой из бригад оно не хуже исходного назначения (kjWsk^o), j=ÜI).

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

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

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

Существенно более простой оказывается задача о переназначениях с максимизируемым общим критерием Q(jt) = min a¡ n|¡) и критериями бригад

q j(?t) = min a¡ „(¡) , j=I,»>. Она сводится к задаче о назначениях с

léHíiа ;

запрошенными элементами и общим максимизируемым кршернем вила min b¡ „jj, . Столь же проста задача с общим критерием К(к) - £ a, m¡) н

' i-I

максимизируемыми критериями бригад q,(7i) = mm t)| , J I, ш.

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

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

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

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

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

Исходные данные ПЗО можно представлять конечным ориентированным графом О = (V,А); вершины графа соответствуют участникам задачи (V = J 1, 2, . . . , п }), а пара (íj) является дутой ((i.j) е Л), ннда и только тогда, когда принадлежащий участнику j предмет p(j) для участника i желанный.

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

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

Показывается, что »опрос об отыскании 2-рсн1сипи с максимальным числом обменивающихся участников сводится к задаче построения в специальным образом построенном неориентированном графе С* наибольшего паросочетания и решается в кубично зависящем от п времени . Проблемы же определения в ПЗО I -решения, I* - решения или I ** - решения с максимальным числом обменивающихся участников являются - трудными в сильном смысле при любом фиксированном значении 1^3.

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

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

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

Рассмотрим ситуацию, когда в множестве участником ПЗО выделены непересекающиеся подмножества I г , 1 2 , . . • , I р и каждое решение Я характеризуется векторным критерием (у(К, 1 |) , у(К, I > ). . . . ■ у(Я, I,,)), где у( К., I ,) - число участников, входящих в подмножество I ^ и обменивающихся при реализации решения К. $ !.р. Показано, что

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

R*,lj) > I при всех j = i,p, NP-полна.

В § 3.3 изучается задача простого платного обмена (ЗППО). Участники ЗППО связывают получение приемлемых предметов с платежами различных знаков. Если участник i для получения предмета p(j) взамен предмета p(i) согласен на положительный платеж w(i j), то величину этого платежа будем называть доплатой участника i за предмет p(j); если же платеж w (i,j) отрицателен, то это размер компенсации, которую требует участник i при получении им предмета p(j) »замен p{i). Исходные данные 3IIIIO можно нредскшляи. нтнсшспным орнамнронанпмм фафом (i' (V,A), вершины которого соответствуют участникам задачи (V - J 1,2,.. . , п }), пара (¡j) является дугой ( (¡j) е А), тогда и только тогда, когда принадлежащий участнику j предмет p(j) для участника i желанный; vv(i,j) -вес дуги (ij).

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

Сумму весов составляющих допустимое решение R цепочек обмена называем суммарным доходом от реализации решения R. Задача синтеза допустимого решения, максимизирующею величину суммарного дохода, сводится к 1C3I1. В то же время, задача сшиеза ,иш)стимою решения с максимальным числом обменивающихся учасшнкои окаn.maeioi NT-трудной.

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

В § 3.4 изучается задача простого обмена с индивидуальными предпочтениями участников (ЗПО с И11У), определяемая совокупностью Q = { 1 ; Р ; Р[, < ¡, iel}, где 1 = { 1,2,...,п| - множество участников; 1' -{р(1),р(2),...,р(п)| - множество предметов ( но начальным данным

участнику 1 принадлежит предмет р(1), 1 е I ); Р| - множество предметов, более предпочтительных для участника 1 в сравнении с рО), Р, с Р, р(0 ёР^ 1 е I ; < ] - линейное упорядочение множества Pi * = Р( и {р(0}, выражающее предпочтения участника I, I е I .

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

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

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

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

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

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

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

концепция Л- устойчивости, которой удовлетворяют только решения, конструируемые процедурой А .

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

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

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

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

Решения тг( и щ ЗПО с ИПУ для учаепшка ! равноценны, если он одинаково оценивает предмет р(л,(0) и р(1с_>(0). ')ш решении эквивалентны, если они равноценны для каждого из участников. Показано, что если 71) и Я2 - два строго устойчивых решения ЗПО с ИПУ, то они эквивалентны между собой.

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

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

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

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

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

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

В реальных задачах обмена большой размерности каждого участника , как правило, можно отнести к некоторому типу, причем число типов является ограниченным. В связи с этим вводится понятие стандартного класса задач обмена групповой структуры. Для того, чтобы в стандартном классе с п. группами однотипных участников определить конкретную 31Ю с ИПУ , необходимо указать п- мерный вектор состава W - (w|,\v>,...,\v „), где w , -количество участников в tpynne g ,, i = l,n .

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

В § 3.5 изучается простейшая задача обмена-распределения, определяемая совокупностью Е = { I1Р1, Р2, М }, где 1|'= {1, 2,'.!., тп) ' - множество обменивающихся участников (каждый из них обладает некоторым предметом, но желает обменять ею на более приемлемый); 12 = { m + 1, ш + 2,...,т +п ) - множество участников, каждый из которых, не

обладая никаким предметом, желает получить некоторый подходящим ;

{p(I),p(2),...,p(m)J - множество предметов, принадлежащих обменивающимся участникам ; по начальным данным участнику i принадлежит предмет p(i) , i =!,ш; Р1 = {p(m + 1), р(т + 2), ... , р(т + г>|)} - множество предметов, не имеющих обладателей; М = {m(i,j)} -целочисленная матрица оценок, имеющая размерность (ш + п) х (ш + п,), здесь m(ij) - оценка участником i предмета p(j). Для i =1,«/, i.e. для обмениваю!цихся участников, считаем, что m(ij) = 0, если предмет p(j) для участника i неприемлем; m(ij)=l. если ¡-.¡(!- оценка изначально принадлежащего участнику предмет); m(i.j) 2, сели предмет p(j) для участника i является желанным, т.е. более предпоч пчельным и сравнении с предметом p(i). Для i =/я + 1,ш + я, т.е. для участников, пе обладающих предметами, m(ij) = 0, если предмет p(j) для участника i неприемлем, и m(ij) = 2, если предмет p(j) для участника i является желанным.

Решение R задачи Е определяем как взаимно однозначное отображение множества It 12' , здесь 12' с 12, в подмножество номеров объектов из Р, удовлетворяющее условию допустимосгн (Vi е !, и 12')[ m(i, R(i))>0 ]. Реализация решения R делает участника i из 1/ u J2' обладателем предмета p(R(i)). В решении R участник i , i б lj , обменивающийся, если R(i) * i ; участник i , i е l2, становится обладателем некоторого подходящего для него предмета, если i е 12' . Получаемый обменивающимся участником предмет можс1 принадлежать как множеству I'1 , так и множеству Рг.

Решении R называем конссриаишиым, если для imiimiо j in I, ... , nv), в множестве 1| и 12' найдется i такое, что R(i) = j ; в консервативном решении предметы, которые по начальным условиям задачи, имеют обладателей, не могут оказаться никому пе принадлежащими.

Каждое решение R оцениваем критериями Qi(R) - число обменивающихся участников и Q2(R) - число участников множества 12 , которые в результате реализации решения становятся обладателями предметов из Р. Рассматривается также общий критерий Q(R) = Q.(R) + Q2(R).

Показывается, что проблема построения для задачи обмена -распределения с критериями Qi(R) и Q>(R) соответствующего множества эффективных оценок, как с наложением доиолшпелыюго требования консервативности конструируемых решений, так и без указанного

ограничения, сводится к последовательному решению не более чем min (п, П|) однотипных задач поиска в сети максимального потока, имеющего минимальную суммарную стоимость. Задача синтеза решения, максимизирующего значение Q(R), сводится к однократному решению указанного вида сетевой задачи.

В § 3.6 рассматриваются задачи сложного обмена, т.е. задачи, в которых каждый участник обладает и желает обладать, вообще говоря, неодпоэлементным набором недробимых предметов. Задачу сложною ( мпогопредметного) обмена определяем совокупностью X : S ; S ¡. М ¡. i с_-

I; '/■> , где I - ¡1,2.....п) - множество участников; S {.s|,s........ |

множество принадлежащих участникам предметов ( N ^ и ); S - множество

предметов, которыми обладает участник i, S , £ 0, (JSj = S, S; n S j =

i-i

0 для всех tej; M i - совокупность непустых подмножеств из S, каждый входящий в М j элемент - это множество предметов, более приемлемых для участника i в сравнении с совокупностью S ¡, i = I

Решением задачи обмена I называем упорядоченную совокупность непустых попарно непересекающихся множеств предметов II = {Hi.fb,..., II „ }при условии выполнения следующих требований:![, либо совпадаете S,,

либо является элементом совокупности М j , i = 1,«; (J II = S. При

i-1

реализации решения Н каждый участник i становится обладателем совокупности предметов 11„ которая либо совпадает с S „ либо представляет собой множество предметов, для данною участника более приемлемое. Участник i в решении 11 обменивается, если 11, J- S j.

Если все множества S \ одноэлементны (при этом | S I - 111 ),то каждое из множеств II; обязательно также одноэлементно, задача X превращается в простейшую задачу обмена. Будем говорить, что задача многопредметного обмена принадлежит классу £р, если каждый ее участник обладает и может обладать не более чем р- элементным множеством предметов. Задачу многопредметного обмена отнесем к классу Е \ если каждое множество предметов, более приемлемых для любого участника i в сравнении с совокупностью принадлежащих ему предметов S ¡, i - I //, совпадает с совокупностью предметов, принадлежащих некоторому другому участнику. Как очевидно, Для задач класса 2 , сохраняется справедливость всех результатов, относящихся к простейшим задачам обмена.

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

Пусть Н - произвольное решение задачи сложного обмена. Оно определяет разбиение совокупности участников на коалиции обмена; каждая коалиция - минимальное подмножество участников, в данном решении обменивающихся только между собой. В коалициях обмена каждому ее участнику следующим образом присвоим нскоюрмй ранг. IIa нервом -пане ранг I присваивается участнику с минимальным номером в каждой из коалиций; на втором этапе ранг 2 приписывается каждому участнику, который по решению Н получает по меньшей мере один предмет от участника ранга I; на произвольном k-ом этапе ранг к присваивается каждому из участников, получающих предмет от участника ранга k -1 и до этого этапа ранга не имеющему. Задаче обмена приписываем степень р, если для любого ее решения в любой из коалиций обмена число участников любого фиксированного ранга не превосходит константы р. Через! i' обозначим подкласс задач обмена из £р, которые имеют степень не выше к .

Теорема 3.6.1. Проблема определения по исходным данным задачи подкласса £ 2 \ обладает ли она решением, в ко юром множество обменивающихся участников непусто, NP- полна.

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

Пусть I j./ обозначает некоторого р-го участника, обладающего j предметами и желающего получить взамен k-мредмешый набор из определенного для этого участника списка.

Схема S | = [1 мр, 1 |.2Ч, 1 2-1П предполагает обмен между собой двух участников, первый обладает двумя предметами и желает получить вместо них один (в терминах обмена квартир это съезжающийся участник), второй участник (разъезжающийся) обладает одним предметом и желает получить вместо него два. Анализ исходных данных задачи сложного обмена позволяет выделить все возможные нары учао никои. которые Moiyr обменяться по схеме S ¡; проблема синтеза решения, максимизирующего

ли

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

Схема в 2 = [12.,р<,), 1 ,.2Ч(,), I г-,1"2', ... , I 1-2"""', I г-!1*" 1 предполагает обмен любого четного числа участников. При этом каждый участник, занимающий позицию нечетного номера, обладает двумя предметами, обмениваемыми на один предмет, принадлежащий участнику, занимающему позицию со следующим порядковым номером; каждый участник, занимающий в схеме позицию четного номера, обладает одним предметом; взамен имеющегося предмета такой участник получает от участника, занимающем» позицию со следующим номером, желательную для пего пару предметов.

Схема в 3 = [I мр(", I .-I40', I ия(2), - , I м4'"", I ь/'2', I м1"" ] включает некоторых участников 12-|Р<1> и I и141', обменивающих соответственно два предмета на один и один предмет на два; каждый из остальных обменивающихся в рамках схемы участников обладает и может обладать только одним предметом. Предполагается, что участник 1 2-1Р,1> получает нужный ему предмет от участника [ мч(|); каждый участник I м40',!' =1,»/ -1, получает желанный предмет от участника I ы4^"1, учаепшк I м4'"0 получает желанный предмет от участника 1 |.2р(2>, который, в свою очередь, получает желанную пару предметов от участника 12.|Р<1)-

Теперь очевидным оказывается содержание схем Я 4 = [ 1 |.->р<", 1 г-'4'"-'

2Ч,2\ ... , ! 2-2ФП\ I 2-.Р(21, 1 1-2Р<" ] и Б 5 = [ I 2.2Ч(П, I 2./2».....I 2.,Ч,т1, ы чП>1"

Схема

I 1.|ч"), I |.1Ч(г).....I

I 1(1) I Г(») . 1(1)

11-1 ,11-1 ,..., 11-1 >

предполагает, что участник 1 |.2Р"> получает подходящую для него пару предметов от участников I |.|Ч<" и I мг("; далее каждый вписанный в верхнюю (нижнюю) линию участник получает желанный предмет от участника, записанного в той же линии правым соседом, участники I ю40"' и I м1*0 получают по одному желанному предмету от I 21; участник I 2_|Р12>, отдающий два предмета, получает нужный для нею предмет от участника I |.2Р<".

Схема 87 =

т ч0> I 4(21 I Ч(п" 4-1 .1 1-1 1-1 ,

П Р(1) 1 Р(21 , 1(1) 1 «'> I Ич , р!1) .

11 1-2 , I 2-1 . ' 1-1 . 1 1-1 , ••• . I 1-1 .1 |-> |

является прямым усложнением предыдущей, от она отличается тем, что между соседними в Б 6 участниками I 2-|Г<г) и 1 появляются

промежуточные I м4", 1 ы"21, ... , I м11 v> , каждый из который обменивает собственный предмет на предмет, принадлежащий ближайшему соседу справа.

Схему обмена назовем ограниченной, если се реализация связана с привлечением фиксированного числа участников. Показывается, что вопросы существования обменов в рамках ограниченной схемы 8 , и априорно неограниченных схем 82 - 8 <„ полиномиально разрешимы. Вопрос "о сложности проблем 1,1 существования решении, описываемых схемой 8 7, открыт' . Задача синтеза решении, максимизирующею число обменивающихся по схеме Б 2 участников, очевидным образом сводится к решению КЗН. Отметим^ что для любого фиксированного стандартного класса задач сложного обмена групповой структуры при определенном наборе возможных ограниченных схем обмена проблема синтеза решения с максимальным числом обменивающихся участников сводится к решению многомерной задачи о ранце (размерность задачи совпадает с числом классов).

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

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

В § 4.1 рассматривается каноническая задача обслуживания, состоящая в следующем. Однопроцессорная система должна обслужить поток заявок '/. = (1, 2, . . . , п}. Каждая заявка 1 характеризуется целочисленными параметрами: 1(0- момент поступления (0 = 1(1)< 1(2)< ...< 1(п)); т(0 - требуемая продолжительность обслуживания процессором; а(0 -коэффициент функции штрафа, 1 =Т,и. Кслп обслуживание заявки )' завершается в момент 1*(0, то величина штрафа по ней равна а(0 |1*(0 -ЦО) . Процессор готов к обслуживанию заявок потока начиная от 1 0. Обслуживание каждой заявки реализуется без прерываний, одновременное обслуживание процессором нескольких (более одной) заявок псво ¡можно.

Расписание отождествляем с перестановкой р - (¡|, 'ь , ..., ¡„) элементов множества {1, 2,. . . , п}; заявка I ^ в расписании р обслуживается к-ой по

очереди, пусть t*(p , i к) - момент завершения обслуживания З&ЯВКИ 1 ^ ПрИ реализации расписания р , к = 1 Суммарный штраф fio всем заявкам

есть W(p) = a(i) (t*(p,i) - t(i)]. Проблема состоит в нахождении

'•i

minW(p) . (4.1.1)

Р

Известно, что задача (4.1.1) NP-трудна в сильном смысле. Задачу (4.1.1) отнесем к классу К1 ( р), если среди величин t(i), i =1, 2, . . . , n , имеется не более р различных. Задачу (4.1.1) отнесем к классу Км ( q), если срсди величин p(¡) =a(i)/t(i), ¡ =1,н , имеется не более q различных.

Для задач класса К1 (1) известен простой алгоритм синтеза оптимальног о расписания: вычислии величины p(i) -a(¡)/t(¡), i l.n , упорядочить заявки по убыванию значений p(i) . Полученная перестановка является расписанием обслуживания, минимизирующим суммарный штраф.

Для задач класса К" (1) выполняется условие

а(1)/т(1) = а(2)/т(2) = ... = а(п)/т(п) . (4.1.2)

Соотношение (4.1.2) может иметь интерпретацию: штраф за единицу времени простоя транспортного средства прямо пропорционален его грузоподъемности, а, следовательно, и времени погрузки (или разгрузки).

Теорема 4.1.1 . Для задач класса Км (1) перестановка р° = (1, 2,.. . , п) является оптимальным расписанием обслуживания.

Таким образом, порядок вычислительной сложности задач классов К1 (1) и Км (1) совпадает со сложностью сортировки п- элементного массива натуральных чисел, т.е. C¡ n In п, где С| - не зависящая от п константа.

Г е о рема 4.1.2 . Задача (4.1.1) для класса 1С' (2) иилнегеи N1'-трудной.

Т е о р е м а 4.1.3 . Задача (4.1.1) для класса К'1 (2) является NP-трудной.

Легко видеть, что наложение на задачу (4.1.1) в ее обшей постановке дополнительного условия t(n) < С , где С - некоторая константа, обеспечивает полиномиальную разрешимость получаемого подкласса задач. Возникающие на практике задачи удовлетворяют существенно более слабому условию t(n) < (1 + с*)п , где с* - положительная константа. Подкласс задач вида (4.1.1), удовлетворяющих этому условию, обозначим К[с*].

зз

Теорема 4.1.4. Задачи подкласса К[с*] , где с* - произвольная положительная константа, NP- трудны в сильном смысле.

Рассмотрим процедуру динамического программирования для решения задачи ( 4.1.1). Очевидно, что управленческие решения принимаются для моментов времени, когда процессор свободен; каждое решение состоит в определении очередной обслуживаемой заявки. При этом текущая ситуация вполне характеризуется парой ( t, S), где t - момент принятия решения, a S — множество заявок, на данный момент ожидающих обслуживания.

Пусть £ (t,S) - минимальная величина суммарного штрафа за период ог момента t до завершения процесса обслуживания всех заявок потока для определяемой парой ( t , S) ситуации; здесь I - произвольный момент нрннмшя решения. Через 0(1, S, (t) ооошлчнм ирифмсшчсскн вычисляемую величину суммарного штрафа, выплачиваемого за период от момента t до момента 1 + ц по заявкам множества S и заявкам, пополняющим это множество во временном интервале (1,1 + р); считается, что за этот период ни одна из заявок не покидает систему обслуживания. Через D(t, ц) обозначим совокупность заявок, прибывающих в систему обслуживания на временном отрезке [t + I, t + р|.

В паре (t,S) множество S считаем непустым, что обеспечивается обязательным включением в него фиктивной заявки 0 с параметрами а(0) = О , t(0) = t и т(0) = min {0 I D(t, t + О ) }. Обслуживание фиктивной заявки означает простой процессора от момента I то момента прибытия в систему какой- либо новой заявки потока Z.

В принятых обозначениях рекуррентное соопюшепне динамическою программирования записывается в виде il(t.S) - min { <¡(1,.S,t(í» i i t(i),(S\i)wP(i, c(i|) ¡. (1.1 Л)

Вычислительная сложность основанного на (4.1.J) алгоршма экспоненциальна, что определяется числом рассматриваемых подмножеств S.

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

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

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

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

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

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

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

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

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

Для каждой из перечисленных 4M строятся полиномиальные алгоритмы синтеза оптимальных расписаний,

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

и

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

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

Для каждого из перечисленных обобщений записываются соотношения динамического программирования. Показывается, что введение дополнительных ограничений, определяемых введенными в §4.2 ЧМ1 -ЧМ6, для рассматриваемых обобщений дает, как правило, возможность строить основанные на соотношениях динамического программирования полиномиальные по верхней оценке временной вычислительной сложности решающие алгоритмы.

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

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

зь

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

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

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

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

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

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

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

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

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

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

В § 5.2 рассматривается задача синтеза оптимальною расписания обслуживания конечного детерминированного потока заявок одним mobil-процессором (перемещаемым процессором). Известен поток заявок Z =

{zi,z2.....z„}, проходящих транзитом рабочую зону mobil- процессора. Зона

представляет собой отрезок AB длины L. В пределах зоны процессор может перемещаться как в автономном режиме, с зависящей только от направления движения скоростью, так и в паре с обслуживаемой заявкой с се скорост ью. Обслуживание любой заявки однофазное и может выполнии.еи: а) и стационарном режиме прн совместном плчожчешш процессора н обслуживаемой им заявки в одной точке зоны; б) в режиме совместного движения заявки и процессора (движение осуществляется со скоростью заявки); в) в смешанном режиме, чередующем два вышеуказанных. Процессор не может обслуживать более одной заявки одновременно, переналадки отсутствуют, прерывания запрещены. Поток Z состоит из подпотоков: Z1 - заявок, следующих в направлении AB, и Z2 - заявок, следующих в направлении ВА. Отрезок AB удобно считать разбитым на ш+1 элементарных участков равной длины, последовательно пронумерованных числами от нуля до т. Обязательным является обслуживание только специально выделенных привила ированпых заявок.

Каждая заявка характеризуется целочисленными параметрами: помер подпотока, в который она входит; момент гюауплепия в зону (точку А для

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

Сформулированная задача, рассматриваемая в дискретном времени, решается методом динамического программирования. Записываемое рекуррентное соотношение определяет способ вычисления значений функции \У(1,р,[8],), выражающей максимально возможную суммарную оплату по обслуженным заявкам в ситуации: а) процесс обслуживания начинается от момента 1; б) по состоянию на момент I процессор находится на элементарном участке р; в) [в], - множество поступивших необелуженных заявок, любая из которых в момент I может быть начата обслуживанием (оплата окажется не ниже пороговой); г) каждая заявка из [8], считается находящейся на наиболее приемлемом элементарном участке из числа достижимых к моменту I. При подсче1е каждого значения функции \У(1,р,|Х||) определяется номер принимаемой и дикими мимом к обслуживанию заявки и отрезок зоны, на котором обслуживание будет осуществляться.

Качество решения задачи зависит от шага дискретности как по пространственной, так и по временной координате. Временная вычислительная сложность решающего алгоритма пропорциональна произведению количеств дискретов по одной и другой координате и экспоненциально зависит от общего числа заявок н потоке. Далее трудоемкость алгоритма оценивается для достаточно типичного частного случая задачи, [а, р]-сегментом потока заявок У. (а и р принадлежат множеству {1,2,...,п), а < (3) назовем множество заявок этого потока, номера которых лежат в отрезке [а, р]. Введем в рассмотрение подкласс К'1 задач таких, что в любой момент дискретного времени I, в силу имеющихся

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

Решен ряд конкретных прикладных примеров.

В § 5.3 рассматривается задача синтеза оптимальной последовательное-!и обработки заявок в однопроцессорной системе с накопителем ограниченной емкости. Данная задача возникла при создании компьютерных средств поддержки оперативного планирования и регулирования процессов грузовой обработки танкерного флота в условиях короткой навигации ппжпеН Оби. Математическая постановки задачи ошичаася от канонической следующими дополнительными компонентами. Каждая заявка Zj потока Z имеет объемную характеристику v, и принадлежит одному из двух подпотоков, Z1 (заявок с горючим, которое должно быть слито в накопительную емкость) и Z2 (заявок, требующих горючее из емкости). Накопительная емкость L имеет объем V* и начальное ( на момент времени t=0) заполнение Vo. В результате обслуживания заявки г, из подпотока Z1 (Z2) заполнение емкости L увеличивается (уменьшается) на величину v,.

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

Обозначим через V' и V2 суммы объемных характеристик заявок подпотоков Z1 и Z1 соответственно и будем считать верным условие

2vî<V\H,2.....п. (5.3.1)

И предположении (5.2.1 ) необходимым и достаточным условием нснустош множества допустимых в рассматриваемой задаче расписаний является выполнение соотношения

0< Vo + V' -V2< V*. (5.3.2)

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

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

Расписание обслуживания назовем [d|,d2]-pacniieaiiiicM, если в его реализации длины обгонов, совершаемых заявками ноднотков /.' и Z" не

и>

превышают <1| и с12 соответственно. При фиксированных значениях с1| и синтез оптимального [(1Ь(12]-расписа>шя методом динамического программирования реализуется в квадратично зависящем отп времени.

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

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

ОСНОВНЫЙ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМП ДИССЕРТА1 (ИИ

1. Коган Д.И., Лиогонький М.И. Задачи распределения работ с учетом взаимных предпочтений. Межвуз. сб-к "Анализ и моделирование экономических процессов", ИНГУ, 1981, е.29-34.

2. Коган Д.И. Сравнительный анализ концепций устойчивости в задачах распределения работ. Межвуз. сб-к "Анализ и моделирование

: экономических процессов", ННГУ, 1982, с. 29-34.

3. Батищев Д.И., Коган Д.И., Шахриев К. Транспортная задача с дихотомическими предпочтениями. "Вопросы кибернетики",вып. 122,изд.АН УзССР, 1983, с. 17-27.

4. Коган Д.И. , Лиогонький М.И. Задача о назначениях с учетом индивидуальных предпочтений. "Кибернет ика", 1983. № 4,

с.80 - 85.

5. Коган Д.И.,Макарычен 11.11.,1'енел В.Ф.. Шепелев Ü.M. Автоматизированная система обмена жилья в i. Горьком, журнал "Жйлищное и коммунальное хозяйство", 1983, № 2, с. 19.

6. Еатищев Д.И., Коган Д.И., Шахриев К. Многокритериальные транспортные задачи, изд. Горьковского госун-та, 1984, 64 с.

7. Коган Д.И.,' Шахриев К. Пакет прикладных программ для решения многокритериальных транспортных задач. "Пакеты прикладных программ. Функциональное наполнение", нзд-во "Наука", Новосибирск, 1985, с. 107-114.

8. Батищев Д.И., Коган Д!И., Шахриев К. Решение многокритериальных транспортных задач в интерактивном режиме. 30 Inlern. Wiss. Koll. "Mathematische Optimierung -Theorie und Anwendungen", llmenay, DDR, 1985, pp.7-10.

9. Коган Д.И., Лиогонький М.И. Многокритериальные задачи о назначениях// Межвуз. сборник «Принятие оптимальных решений в экономических системах». - Горький: птд-во Горькоиекот унниеренкча, 1985, с. 27-33.

Ю.Коган Д.И. О вычислительной сложности фапепортны.х задач с нелинейным критерием // Межвуз. сборник «Принятие оптимальных решений в экономических системах»,- Горький: Изд. Горьковского университета, 1986, с. 28 - 33. ...

11. Коган Д.И., Шепелев В.В. Планирование и оперативное управление работой водителей ATI1 МГ1. Тезисы Всесоюзной школы-семинара "Системное моделирование процессов интенсификации общественного производства", Горький, 1987, с.152-153.

12. Батищев Д.И., Коган Д.И. Транспортные задачи с линейными оценками участников. Известия АН СССР. Техническая кибернетика, 1988, № 1, с.45-51.

13. Горячев В.И., Коган Д.И., Мухамеджанов В. Многокритериальные задачи распределения транспортных средств. Тезисы докладов 11-го Всесоюзн. совещания по проблемам управления, Ташкент, 1989, с. 186187.

14. Коган Д.И. Задачи обмена, определяемые двухцветным графом, Тезисы докладов 11-ой Всесоюзной конференции по проблемам теоретической кибернетики, часть1(3), Волгоград, 1990,с. 25.

15. Коган Д.И. Дискретные многокритериальные задачи распределительного типа, изд-во Нижегородского университета, 1991, 82 с.

16. Коган Д.И. Многокритериальные задачи о назначениях и обменах// Межвуз. сборник «Методы н системы технической диа| ноепнш». Вып. 19. - Саратов: изд-во Саратовского университета. 1993. С. 83 - 85.

17. Коган Д.И. Обобщенные задачи о назначениях, оценки сложности и алгоритмы решения. Межвуз.сб-к " Математическое моделирование в образовании (программные средства), ННГУ, 1994, с.158-164.

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

19. Коган Д.И. Двухкритериальные задачи о назначениях: оценки сложности и алгоритмы решения. Известия РАН. Теория к системы управления, 1996, №3, с. 80-85.

20. Коган Д.И., Федосенко Ю.С. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы. Дискрет ная математика, 1996,1.8, № 3, с.135-147.

21. Коган Д.И. Концепции коалиционной устойчивое!и и задачах проемио обмена. Межвуз. cG-к "Математическое моделирование и оптимальное управление", изд-во ННГУ, 1996, с.119-125.

22. Коган Д.И., Федосенко Ю.С. Алгоритм решения общей задачи однопроцессорного обслуживания потока заявок. Вестник Нижегородского ун-та. Математическое моделирование и оптимальное управление, 1997, с.123-130.

23. Коган Д.И., Шеянов A.B. Полиномиальная реализуемость метода ветвей и границ для частных классов задач диспетчеризации, там же, с.131-137.

24. Коган Д.И., Федосенко Ю.С., Шеянов A.B. Моделирование и оптимизация управления потоком объектов в однопроцессорной системе обслуживания с изодромпым элементом. Межвуз. сб-к "Моделирование и оптимизация сложных систем", Волжская госакадемия водного транспорта, 1997, вып. 273 (часть 1), с.44-54.

•и

25. Батищев Д.И., Коган Д.И., Шеянов A.B. Модифицированная многокритериальная задача о ранце и алгоритм ее решения. Межвуз.сб-к "Моделирование и оптимизация сложных систем" Волжская госакадемия водного транспорта^ 998, вып. 273 (часть 2), сгр.125-132.

26. Коган Д.И., Федосенко Ю.С. Управление дискретными ресурсами в однопроцессорной системе. Оптимизация обслуживания заявок в пакетах переменной структуры. "Автоматизация решения транспортных задач" , сб-к научных трудов, изд-во Санкт-Петербургского госунпверспгета водных коммуникаций, 1998, с.102-108.

27. Коган Д.И. Планирование перевозок однородного продукт с учеюм взаимных предпочтений. «Автоматизация решения транспортных задач»,, сб-к научных трудов, изд-во Санкт-Петербургского госуниверситета водных коммуникаций, 1998 с.109 -114.

28. Коган Д.И., Федосенко Ю.С., Шеянов A.B. Проблема синтеза оптимального расписания обслуживания бинарного потока объектов mobil-процессором. Труды III Международной конференции "Дискретные модели втеории управляющих систем", Москва, МГУ,1998, с. 43-46.

29. Коган Д.И. Оптимизация выбора и упорядочения заявок в односсорных моделях платного обслуживания. Вестник Нижегородского ун-та. Математическое моделирование и оптимальное управление. 1998, вып. 26, с. 193-203.

30. Коган Д.И. Многокритериальные задачи планирования и управления в системах транспортного типа. Тезисы докладов XII Международной конференции «Проблемы теоретической кпберпешки». Нижний Новгород, I9'W.t. I.c.W.

Личный вклад диссертанта в работы, опубликованные в соавторстве, состоит в следующем:

в [1, 3, 4, 6 - 9, 12] (см. список основных работ диссертанта, приведенный в автореферате) - построение многокритериальных моделей распределительных задач транспортного типа, исследование вычислительной сложности, синтез решающих ал! ори шов, выделение полиномиально разрешимых подклассов; в [5] - общая идеология созданной автоматизированной системы обмена жилья, принципы решения задач по подбору вариантов обмена; в (11 , 13| - применение моделей многокритериальных задач о назначениях н алгоритмов их решения в процессах оперативного управления автотранспортным предприятием междугородних перевозок; в [18] - реализация многокритериального аналога принципа динамического программирования для синтеза

совокупностей эффективных оценок и Парето- оптимальных решений; в [20, 22] - исследование вычислительной сложности канонической задачи однопроцессорного обслуживания и ее конкретизаций, выделение полиномиально разрешимых подклассов, синтез основанных на принципе динамического программирования решающих алгоритмов (в том числе полиномиальной сложности); в [23] - синтез для полиномиально разрешимых подклассов однопроцессорных задач полиномиально реализуемых модификаций схемы ветвей и границ; в [24, 26, 28] -математическое исследование задач, выделение обладающих меньшей вычислительной сложностью частных подклассов, нос Iроение решающих алгоритмов; в [25[ - построение общей модели н рекуррешимх соотношений, реализующих многокритериальный аналог принципа динамического программирования.

Введение.

Глава 1. МНОГОКРИТЕРИАЛЬНЫЕ ТРАНСПОРТНЫЕ ЗАДАЧИ,

ИХ МОДИФИКАЦИИ И ПРИЛОЖЕНИЯ.

§1.1. ПРИРОДА МНОГОКРИТЕРИАЛЬНОСТИ В ТРАНСПОРТНЫХ

ЗАДАЧАХ. ЧАСТНЫЕ КЛАССЫ И ПРИЛОЖЕНИЯ МКТЗ.

§ 1.2. ОСНОВНЫЕ СХЕМЫ КОМПРОМИССА И МЕТОДЫ РЕШЕНИЯ

МК ТЗЛП С ОБЩИМИ КРИТЕРИЯМИ.

§ 1.3. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ С УЧЕТОМ ЛИНЕЙНЫХ ОЦЕНОК УЧАСТНИКОВ.

§ 1.4. ТРАНСПОРТНЫЕ ЗАДАЧИ С УЧЕТОМ ПРЕДПОЧТЕНИЙ

УЧАСТНИКОВ.

§ 1.5. РЕЗУЛЬТАТЫ О ТРУДНОРЕШАЕМОСТИ ДЛЯ ТРАНСПОРТНЫХ ЗАДАЧ.

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

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

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

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

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

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

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

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

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

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

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

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

Методическую и теоретическую базу диссертационной работы составляют подходы и инструментарий системного анализа, исследования операций, теории игр, многокритериальной и комбинаторной оптимизации, теории графов, теории расписаний, а также ряд ранее выполненных работ в областях распределения и перераспределения ресурсов, транспортного планирования и совершенствования эксплуатации водного транспорта. При выполнении исследований автор опирался на теоретические результаты отечественных и зарубежных ученых (Татищев Д.М., Курком П.II., Воробьев H.H., Гсрмсйер IO.I»., Голыитейп lü'., 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., Захаровым В.Н., Игуди-ным Р.В., Савиным В.И. и др.

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

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

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

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

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

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

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

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

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

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

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 излагаются причины многокритериальное™ в задачах синтеза планов перевозок, приводятся примеры многокритериальных транспортных задач, возникающих в воднотранспортных системах, выделяется иерархия классов важных в теоретическом и прикладном отношениях классов многокритериальных транспортных задач. В частности, определяются задачи с несколькими общими критериями; задачи с общим критерием, критериями групп участников и оценками отдельных участников (оценка участника - функция, зависящая от размеров перевозок по всем коммуникациям, относящимся к данному участнику); задачи с общим критерием и индивидуальными предпочтениями участников.

В § 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 - совокупность целых неотрицательных чисел, а © - специальный символ запрета; если в позиции ( у ) одной матрицы стоит со, то этот знак стоит в позиции ( у ) и в другой матрице. Изучаются проблема синтеза полных совокупностей эффективных оценок и вопрос о реализации метода последовательных уступок по значению ведущего критерия.

С рассматриваемой ДКЗН ассоциируется соответствующая ТЗЛ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=<A, В, L L 2>, где А = { а| , а2 , . . . , а„ } - множество объектов первого рода, а - участников (например, исполнителей); В = {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<jj , j~1,т. Она сводится к задаче о назначениях с запрещенными элементами и общим максимизируемым критерием вида min fy . Столь же проп ста задача с общим критерием К(тс) = ai *(>) и максимизируемыми крите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(í) - требуемая продолжительность обслуживания; 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.(í) = 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. На основе разработанных моделей и алгоритмов созданы программные средства информационно-аналитической поддержки процедур принятия плановых и управленческих решений в системах внутреннего водного транспорта (Камский грузовой район, Уфимский речной порт). Внедрение указанных средств позволяет на качественно новом, существенно более высоком уровне решать задачи оперативного планирования и диспетчеризации. Установлена практическая применимость разработанных процедур решения многокритериальных модификаций задачи о назначениях и задач группировки в процессах управления науч-но-иссседовательскими и опытно-конструкторскими работами (Нижегородский филиал НИИ спецтехники МВД РФ) . Социально-экономический эффект внедренных разработок определяется обеспеченным качеством и обоснованностью принимаемых решений. Математические модели, принципы и алгоритмы решения задач обмена послужили основой созданной и внедренной в эксплуатацию автоматизированной системы обмена жилья АСОЖ «Волга».

1. Лисп О.И., Ловецкий C.Ii., Моисеспко l'.li. Оптимизация iрапсиортпых потоков. М.: Наука, 1985. - 316 с.

2. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы. М.: Наука,1975. -119 с.

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

4. Алексеев Д.О. Транспортная задача по критерию времени при ограниченном количестве транспортных средств//Математические методы оптимизации и управления в сложных системах. Калинин: КГУ,1984, с.60 65.

5. Арлазаров В.Л., Усков A.B., Фараджев И.А. Алгоритм нахождения всех простых циклов в ориентированном графе . в кн.: Исследования по дискретной математике. - М.: Наука, 1973, с. 178 - 183.

6. Аронович А.Б. О выборе оптимальных комбинаций локальных правил календарного планирования// Экономика и мат. методы. 1970, т.6, N4, с.548 557.

7. Багатурова О.С., Кацнельсон М.Б., Красицкая Л.М., Мамиконов А.Г. Управление перераспределением ресурсов путем натурального обмена.Препринт. -М.: ИПУ, 1978.

8. Батищев Д.И. Задачи и методы векторной оптимизации. Горький : Изд. ГГУ, 1979. 90 с.

9. Батищев Д.И., Коган Д.И. Распределительные задачи планирования и управления НПО// Межвуз. сборник «Анализ и моделирование экономических процессов»,- Горький: изд. Горьковского университета, 1980, с. 35 41.

10. Батшцев Д.И., Коган Д.И., Шахриев К. Транспортная задача с дихотомическими предпочтениями. "Вопросы кибернетики",вып.122,изд.АН УзССР, 1983 г., с. 17-27.

11. Батищев Д.И., Коган Д.И., Шахриев К. Многокритериальные транспортные задачи, изд. Горьковского госун-та, 1984 г., 64 с.

12. Батищев Д.И., Коган Д.И., Шахриев К. Решение многокритериальных транспортных задач в интерактивном режиме. 30 Intern.Wiss.Koll."Mathematische Optimierung -Theorie und Anwendungen", Ilmenay, DDR, 1985, p.7-10.

13. Батищев Д.И., Горячев В.И., Коган Д.И. Экономико-математические модели и методы в управлении автотранспортным предприятием. Тезисы Всесоюзной школы-семинара «Системное моделирование производства», Воронеж, 1986.

14. Батищев Д.И., Коган Д.И., Клочков Д.П. Многокритериальные задачи планирования и управления грузоперевозками // Межвуз. сборник «Математическое и программное обеспечение САШ'» Воронеж, 1987, с. 136 141.

15. Батищев Д.И., Коган Д.И. Транспортные задачи с линейными оценками участников. Известия АН СССР. Техническая кибернетика, 1988г., N 1, с.45-51.

16. Батищев Д.И., Коган Д.И., Клочков Д.П. Метод уступок в многокритериальных задачах размещения элементов РЭА // Межвуз. сборник «Математическое моделирование и оптимизация» .- Горький: Издательство Горьковсого университета, 1990, с. 15- 28.

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

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

19. Батищев Д.И., Коган Д.И., Чернышова H.H. Задачи многоцелевого управления с булевыми переменными. Тезисы докладов Всероссийского совещания-семинара «Математическое обеспечение высоких технологий в технике, образовании, медицине», Воронеж, 1994, с. 148.

20. Батищев Д.И., Коган Д.И., Шеянов A.B. Задача объемного планирования с альтернативными вариантами исполнения. Материалы Международной научно-практической конференции «Управление большими системами», Москва, 1997. с. 248.

21. Батищев Д.И., Коган Д.И., Шеянов A.B. Многокритериальная задача о ранце и ее модификации. Тезисы докладов Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, 1997.

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

23. Бедина A.A., Коган Д.И., Шепелев В.В. Автоматизированная система обмена жилья АСОЖ «Волга». Тезисы докладов II Всесоюзного семинара по перераспределению ресурсов. Москва: ИПУ, 1978.

24. Беленький A.C. Исследование операций в транспортных системах: идеи и схемы методов оптимизации планирования. М.: Мир, 1992. - 582 с.

25. Беленький A.C., Левнер Е.В. Применение моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте// Автоматика и телемеханика, 1989. N 2, с. 3 77.

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

27. Бланк IM.II., Мигаишвили A.A., Легостасв В.А. Экономика внутреннего водного транспорт а. М.: Транспорт, 1983. - 464 с.

28. Бондарева О.Н. Некоторые применения методов линейного программирования к теории кооперативных игр. «Проблемы кибернетики», вып. 10, М.: Наука, 1963, с. 119- 139.

29. Бондарева О.Н. О теоретико-игровых моделях в экономике. Ленинград: Изд-во Ленинградского ун-та, 1974. - 39 с.

30. Бородкип С.М. О минимаксной задаче назначения // Автоматика и телемеха-пика, 1974,№ 10, е. 105 115.

31. Браверман Э.М. Математические модели планирования и управления в экономических системах. М.: Наука, 1976, 366 с.

32. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных комбинаторных задач (обзор) // Изв. АН СССР. Техническая кибернетика, 1968, N 4,с. 82 -93.

33. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных задач комбинаторного типа (обзор) // Автоматика и телемеханика, 1968, N11, с. 68 93.

34. Бурков В.Н., Рубинштейн М.И. Комбинаторное программирование. -М.: Знание, 1977, 72 с.

35. Ваганов Г.И., Захаров В.Н., Никифоров B.C., Троегубов В.Н. Управление эксплуатационной деятельностью речных транспортных организаций. Горький: 1'ИИВТ, 1989.- 259 с.

36. Васильева Е.М., Игудин Р.В., Лившиц В.Н. Оптимизация планирования и управления транспортными системами. М. : Транспорт, 1987. - 208 с.

37. Вентцель Е.С. Исследование операций: задачи, принципы, методология. -М.: Наука, 1980. 552 с.

38. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. М.: Радио и связь, 1981.-328 с.

39. Воробьев H.H. Современное состояние теории игр.// УМН, 1970,т. 25, вып.2 (152), с. 81 140.

40. Воробьев H.H. Теория игр. Лекции для экономистов-кибернетиков.- Ленинград: Изд-во Ленинградского университета. 1974. 160 с.

41. Втюрин А.В. Оперативное регулирование использования плавучих кранов на обработке судов //Моделирование и решение задач использования флота и портов. Труды ГНИ В Та, вып. 176. Горький: ГИИВТ.1980, с. 33 28.

42. Втюрин Л.В., Саламатон Д.Д., Сидорок Г.С. Регулирование использования плавучих кранов в пароходстве// Совершенствование эксплуатации плавучих кранов и технологии перегрузочных работ . Сборник научных трудов, вып. 215. Горький: ГИИВТ, 1985, с. 3 - 14.

43. Гайцгори В.Г., Первозванский А.А. О приближенной оптимальности скользящего планирования// Автоматика и телемеханика, 1977, N10, с. 93 99.

44. Гейл Д. Теория линейных экономических моделей. М.: ИЛ, 1963. - 418 с.

45. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы (обзор) //Изв. АН СССР. Техническая кибернетика, 1979. № 6, с. 9 20.441 ермсиер Ю.Ь. Введение в теорию исследования операций. М.: Наука, 1971.- 383 с.

46. Головников В.И. и др. Основы организации работы флота и портов. М.: Транспорт, 1976 . -390 с.

47. Голыитейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 382 с.

48. Гордон А.Я. Один алгоритм решения минимаксной задачи о назначении// Исследования по дискретной оптимизации. М.: Наука, 1976, с.327 - 332.

49. Гордон В.С. Минимизация стоимости, связанной с переменными директивными сроками, в задаче теории расписаний с одним прибором // Автоматика и телемеханика. 1992, № 2, с. 105 112.

50. Горячев В.И;, Коган Д.И., Мухамеджанов В. Многокритериальные задачи распределения транспортных средств. Тезисы докладов 11-го Всесоюзн. совещания по проблемам управления, Ташкент, 1989, с. 186-187.

51. Грибов А.Б. Рекурсивное решение транспортных задач линейного программирования// Вестник ЛГУ, 1978, вып.4, N19, с. 11-19.

52. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.-416 с.

53. Диниц Е.А. Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой // ДАН СССР, 1970, т. 194, N4, с. 754 -757.

54. Диниц Е.А. О решении двух задач о назначении// Исследования по дискретной оптимизации. M.: 11аука, 1976, с.333 - 347.

55. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр. М.: Наука, 1981.- 336 с.

56. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. - 384 с.

57. Емеличев В.А., Перепелица В.А. К вычислительной сложностидискретных многокритериальных задач// Изв. АН СССР. Техническая кибернетика, 1988, № 1, с. 78 85.

58. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика, 1994, т.6, N 1, с. 3 33.

59. Емеличев В.А., Гирлих Э., Янушевич O.A. Лексикографический оптимум многокритериальной задачи//Дискретный анализ и исследование операций, сер. 1, 1997, 4, №2. с.З 14.

60. Захаров В.Н., Асеев C.B. Основы диспетчерского руководства и коммерческой работы.- Горький: изд. ГИИВТ, 1979, 93 с.

61. Захаров В.Н., Федюшин В.М. Оперативное управление работой грузовых судов речного флота на базе АСУ «Пароходство».- Горький: изд. ГИИВТ, 1987, 78 с.

62. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. -М.: Наука, 1967.-460 с.

63. Игудин Р.В.Задачи теории расписаний на транспорте и алгоритмы их решения// Экономика и математические методы. 1975, № 3 с. 491 499.

64. Йспсеп П., Барпес Д. Потоковое программирование. М.: Радио и связь, 1984.- 391 с.

65. Карзанов A.B. Нахождение максимального потока в сети методом предпото-ков // ДАН СССР, 1974, т.215, N1, с. 49 53.

66. Карлин С. Математические методы в теории игр, программировании и экономике. -М.: Мир, 1964. 838 с.

67. Карп Р. Сводимость комбинаторных проблем. Кибернетический сборник (новая серия). - М.: Мир, 1975, вып.12 , с. 16-38.

68. Кацнсльсон М.Б., Красицкая JT.M., Мамикопов Д.Г. Задачи управления перераспределением обменного ресурса// Автоматика и телемеханика, 1974, N 10, с. 140- 147.

69. Кацнельсон М.Б. Задача подбора вариантов обмена жилыми площадями с учетом индивидуальных предпочтений клиентов,- в кн. Построение автоматизированных систем обработки данных. Сборник трудов, вып. 16.- М.: ИПУ, 1978, с.43 54.

70. Кацнельсон М.Б., Мамиконов А.Г. Модели интеграции систем обеспечения населения жилой площадью// Автоматика и телемеханика, 1978, N 6, с. 99 -104.

71. Кацнельсон М.Б., Темкин В.М. О вычислительной сложности задачи поиска множества вариантов обмена неделимыми ресурсами// Автоматика и телемеханика, 1982, N 8, с. 120 125.

72. Кацнельсон М.Б. Перераспределение ресурсов. М.: Паука, 1985. - 248 с.

73. Ковалев М.Я., Струсевич В.А., Танаев B.C., Тузиков A.B., Шафранский Я.М. Приближенные алгоритмы в теории расписаний. В кн. Методы решения экстремальных задач.- Минск, 1989 г.

74. Коган Д.И., Шепелев В.В. О решениях задачи обмена квартир в автоматизированных системах перераспределения жилплощади. YII Всесоюзное совещание по проблемам управления. Тезисы докладов, книга 2. Минск, 1978 г.

75. Коган Д.И., Лиогонький М.И., Шепелев В.В. Оптимальные назначения в системах с индивидуальными предпочтениями. Тезисы докладов Ш-ей Всесоюзной школы-семинара по математическому обеспечению АСУП, Горький, 1978 г.

76. Коган Д.И., Лиогонький М.И. Две экстремальные задачи построения устойчивых перераспределений. Тезисы докладов II Всесоюзного семинара по перераспределению ресурсов. Москва: ИПУ, 1979, с. 14-15.

77. Коган Д.И., Лиогонький М.И. Проблемы распределения заданий в системах обработки экономической информации // Межвуз. сборник «Анализ и моделирование экономических процессов». Горький: Изд. Горьковского университета. 1979, с. 30 - 35.

78. Koran Д.И., Шепелев В.В. О коалиционно-устойчивых решениях задач обмена-распределения. Тезисы докладов 1Y Всесоюзной конференции но исследованию операций. Горький, 1979.

79. Коган Д.И., Шепелев В.В. Проблема существования устойчивых решений в задаче обмена квартир// Межвуз. сборник «Динамика систем». Горький: Изд. Горьковского университета. 1979, с. 30 - 35.

80. Коган Д.И., Алексеев А.Е. О сложности отыскания оптимального распределения лиц по работам // Межвуз. сборник «Комбинаторно-алгебраические методы принятия решений» . Горький: Изд. Горьковского университета. 1980, с.З- 11.

81. Коган Д.И., Лиогонький М.И. Задачи распределения работ с учетом взаимных предпочтений. Межвуз. сб-к "Анализ и моделирование экономических процессов". 1IIII У, 1981 г. с.29-34.

82. Коган Д.И. Сравнительный анализ концепций устойчивости в задачах распределения работ// Межвуз. сб-к "Анализ и моделирование экономических процессов", ИНГУ, 1982 г., с. 29-34.

83. Коган Д.И. , Лиогонький М.И. Задача о назначениях с учетом индивидуальных предпочтений. "Кибернетика", 1983 г., N 4, с.80 85.

84. Коган Д.И., Макарычев П.П. ,Ренев В.Ф., Шепелев В.В. Автоматизированная система обмена жилья в г. Горьком, журнал "Жилищное и коммунальное хозяйство", 1983 г., N2, с. 19.

85. Коган Д.И. Оценки вычислительной сложности многокритериальных транспортных задач. Тезисы докладов YII Всесоюзной конференции по проблемам теоретической кибернетики, Иркутск, 1985.

86. Коган Д.И., Лиогонький М.И. Многокритериальные задачи о назначениях// Межвуз. сборник «Принятие оптимальных решений в экономических системах». Горький: изд-во Горьковского университета, 1985, с. 27 -33.

87. Коган Д.И., Шахриев К. Пакет прикладных программ для решения многокритериальных транспортных задач. "Пакеты прикладных программ. Функциональное наполнение", изд-во "Наука", Новосибирск, 1985 г., с.107-114.

88. Коган Д.И., Клочков Д.П., Шахрн л» К. Диалоговый подход к решению многокритериальных транспортных задач. Тезисы докладов Всесоюзной конференции по внедрению ЭММ и ЭВМ в планирование и управление производством, Москва, 1985 г., ч.2, с.257 259.

89. Коган Д.И. О вычислительной сложности транспортных задач с нелинейным критерием // Межвуз. сборник «Принятие оптимальных решений в экономических системах».- Горький: Изд. Горьковского университета, 1986, с. 28 33.

90. Коган Д.И., Шепелев В.В. Планирование и оперативное управление работой водителей АТП МП. Тезисы Всесоюзной школы-семинара "Системное моделирование процессов интенсификации общественного производства", Горький, 1987 г. с. 152-153.

91. Коган Д.И. Многокритериальная задача распределения работ. Тезисы Всесоюзной школы-семинара "Системное моделирование процессов интенсификации общественного производства", Горький, 1987 г. сЛ54-155.

92. Коган Д.И., Шахрисв К., Ахмеджанов И. Минимаксная транспортная задача// Межвуз. сборник «Вычислительные алгоритмы прикладной математики». Самарканд: Изд-во Самаркандского ун-та, 1987, с. 67- 75.

93. Коган Д.И. О вычислительной сложности задач простого обмена. Тезисы докладов УШ Всесоюзной конференции «Проблемы теоретической кибернетики», Горький, 1988 г., ч.1, с. 158-159.

94. Коган Д.И. Задачи обмена, определяемые двухцветным графом, Тезисы докладов 11-ой Всесоюзной конференции по проблемам теоретической кибернетики, часть 1(3), стр. 25, Волгоград, 1990.

95. Коган Д.И. Дискретные многокритериальные задачи распределительного типа. Н. Новгород: изд-во Нижегородского госун-та, 1991 г., 82 с.

96. Коган Д.И. Многокритериальные задачи о назначениях и обменах// Межвуз. сборник «Методы и системы технической диагност ики». Вып. 19. Саратов: изд-во Саратовского университета. 1993. С. 83 - 85.

97. Коган Д.И. Обобщенные задачи о назначениях, оценки сложности и алгоритмы решения. Межвуз.сб-к "Математическое моделирование в образовании (программные средства), ННГУ, 1994 г., с.158-164.

98. Коган Д.И., Федосенко Ю.С. Задача о назначениях с группой привилегированных однородных ресурсов// Труды Волжской государственной академии водного транспорта, вып. 271,- Нижний Новгород, 1995, с.25 32.

99. Коган Д.И. Анализ концепций устойчивости в задаче о переназначениях. Тезисы докладов Всероссийской конференции «Математическое обеспечение высоких технологий в технике, образовании и медицине», Воронеж, 1995, с. 134.

100. Коган Д.И., Федосенко Ю.С. Об алгоритмах синтеза субоптимальных расписаний в однопроцессорных задачах обслуживания. Тезисы докладов Всероссийской конференции «Информационные технологии и системы», Воронеж, 1995, с.77.

101. Коган Д.И., Федосенко Ю.С. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы. Дискретная математика, 1996 г.,т.8, N 3, с.135-147.

102. Коган Д.И. Двухкритсриальпые задачи о назначениях: оценки сложно сги и алгоритмы решения. Известия РАН. Теория и системы управления, 1996 г., N3, с. 80-85.

103. Коган Д.И. Концепции коалиционной устойчивости в задачах простого обмена. Межвуз. сб-к "Математическое моделирование и оптимальное управление", изд-во ННГУ, 1996,с. 119-125.

104. Коган Д.И., Федосенко Ю.С. Однопроцессорные задачи обслуживания потока заявок, объединяемых в группы. Межвуз. сб-к "Математическое моделирование и оптимальное управление", изд-во ННГУ, 1996,с.112 118.

105. Коган Д.И., Федосенко Ю.С. Алгоритм решения общей задачи однопроцессорного обслуживания потока заявок. Вестник Нижегородского ун-та. Математическое моделирование и оптимальное управление, 1997 г., с. 123-130.

106. Коган ДИ., Шеянов A.B. Полиномиальная реализуемость метода ветвей и границ для частных классов задач диспетчеризации. Вестник Нижегородского ун-та. Математическое моделирование и оптимальное управление, 1997 г., с.131-137.

107. Ш.Коган Д.И., Федосенко Ю.С. Две модели обслуживания конечного детерминированного потока заявок. Материалы Международной научнопрактической конференции «Управление большими системами», Москва, 1997. с. 254.

108. Коган Д.И., Федосенко Ю.С., Шеянов A.B. Синтез оптимальных расписаний обслуживания мультипотока объектов. Межвуз. сб-к "Моделирование и оптимизация сложных систем" Волжская Гос.академия водного транспорта, 1997, вып. 273 (часть 1),стр. 55- 62.

109. Коган Д.И. Планирование перевозок однородного продукта с учетом взаимных предпочтений. «Автоматизация решения транспортных задач», , сб-к научных трудов, изд-во Санкт-Петербургского госуниверситета водных коммуникаций, 1998 г.,с. 109 114.

110. Коган Д.И. Оптимизация выбора и упорядочения заявок в однопроцессорных моделях платного обслуживания. Вестник Нижегородского ун-та. Математическое моделирование и оптимальное управление. 1998 г., вып. 26, с. 193-203.

111. Коган Д.И. Многокритериальные задачи планирования и управления в системах транспортного типа. Тезисы докладов XII Международной конференции «Проблемы теоретической кибернетики». Нижний Новгород, 1999, т. 1, с. 99.

112. Коган Д.И., Федосенко IO.C. Бикритериальная задача однофазного обслуживания конечного детерминированного потока объектов. Тезисы докладов XII Международной конференции «Проблемы теоретической кибернетики», Нижний Новгород, 1999, т. 1, с. 100.

113. Кожухаров А.Н., Ларичев О.И. Многокритериальные задачи о назначениях // Автоматика и телемеханика, 1977, N 7, с.71 87.

114. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.-368 с.

115. Корбут A.A., Сигал И.Х., Финкельштейн Ю.Ю. Гибридные методы в дискретной оптимизации// Изв. АН СССР. Техническая кибернетика, 1988, № 1, с. 65 77.

116. Кристофидес И. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432 с.

117. Ларичев О.И., Стернин М.Ю. Многокритериальные задачи о назначениях

118. Автоматика и телемеханика, 1988, N 7, с. 135 156.

119. Леонтьев В.К. Дискретные экстремальные задачи // Итоги науки и техники. Теория вероятностей, математическая статистика, теоретическая кибернетика. Т.16. М.: ВИНИТИ, 1979, с. 39 - 101.

120. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. -323 с.

121. Малышкин А.Г. Организация и планирование работы речного флота. М.: Транспорт, 1985 .-216 с.

122. Мамиконов А.Г., Кацнельсон М.Б., Темкин В.М. Оценки неделимых ресурсов в системах натурального обмена. Препринт. М.: ИПУ, 1984, 38 с.

123. Меламед И.И., Сигал И.Х. Исследование линейной свертки критериев в многокритериальном дискретном программировании// Ж.вычислит. математики и математич. физики. 1995, t.35,N8, с. 1260 - 1270.

124. Меламед И.И., Сигал И.Х. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. Препринт. М.: ВЦ РАН, 1996, 51 с.

125. Меламед И.П., Сигал И.Х. Вычислительное исследование трех критериальных задач о деревьях и назначениях // Ж. вычисли!, математики и математич. физики. 1998, 1.38, N10, с. 1780 - 1787.

126. Меламед И.И. Линейная свертка критериев в многокритериальной оптимизации// Автоматика и телемеханика, 1997.№ 9, стр.119-125.

127. Михалевич B.C., Бакаев A.A., Петухов B.C. и др. Экономике математическое моделирование деятельности флота и портов. - М.: Транспорт, 1986.287 с.

128. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.-487 с.

129. Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение.-М.: Наука, 1970,- 708 с.

130. Озерной В.М., Гафт М.Г. Методология решения дискретных многокритериальных задач. В кн. «Многокритериальные задачи принятия решений».- М.: Машиностроение, 1978, с. 14 - 47.

131. Оре О. Теория графов. М.: Наука,1980. - 336 с.

132. Оуэн Г. Теория игр. М.: Мир, 1971. - 230 с.

133. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 510 с.

134. Первозванский A.A. Декомпозиция и агрегирование в задачах оперативного управления дискретным производством // Изв. АН СССР. Техническая кибернетика. 1990, N 6, с. 116 - 124.

135. Персианов В.А. и др. Моделирование транспортных систем . М.: Транспорт, 1972 .-208 с.

136. Плитман А.Д., Рубинштейн М.И. Эвристические методы в календарном планировании // Итоги науки и техники. Сер. Техническая кибернетика. М.: ВИНИТИ, 1990, т. 29, с. 79 - 127.

137. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Советское радио, 1975.

138. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 258 с.

139. Подчасова Т.П., Португал В.М., Татаров В.Д., ТПкурба В.В. Эвристические методы календарного планирования. Киев : Тех ni ка, 1980,- 126 с.

140. Полищук Л.И. Анализ многокритериальных экономико-математических моделей . М.: Наука, 1989.

141. Пьяных С.М. Экономико-математические методы оптимального планирования работы речного транспорта.-М.: Транспорт, 1988. 253 с.

142. Резер С.М., Ловецкий С.Е., Меламед И.И. Математические методы оптимального планирования в транспортных системах// Итоги науки и техники. Сер. Организация управления транспортом. Т.9. М.: ВИНИТИ, 1990. -172с.

143. Розен В.В. Цель оптимальность - решение. - М.: Радио и связь, 1982. - 169 с.

144. Розепмюллер И. Кооперативные игры и рынки. М.: Мир,1974. - 159 с.

145. Рубинштейн М.И. Об шп орит мах решения задачи о назначении // Автоматика и телемеханика. 1981. N 7 с. 145 154.

146. Рубинштейн М.И. Алгоритм решения минимаксной задачи о назначении со слабо заполненной прямоугольной исходной матрицей // Автоматика и телемеханика. 1986 , № 1, с.81 89.

147. Рубинштейн М.И. Оптимальная группировка взаимосвязанных объектов. -М.: Наука, 1989,- 167 с.

148. Рубинштейн М.И., Плитман А.Д. Комбинаторные методы группировки в задачах планирования и организации // Итоги науки и техники. Сер. Техническая кибернетика. М.: ВИНИТИ, 1986, т. 19, с. 190 - 228.

149. Савин В.И. Математические методы оптимального планирования работы флота и портов . М.: Транспорт, 1969 . -168 с.

150. Савин В.И., Неволим В.В., Захаров В.Н., Булов A.A. Автоматизированная система управления водным транспортом. М.: Транспорт, 1985.- 238 с.

151. Свами М., Тхуласираман К. Графы, сети и алгоритмы,- М.: Мир, 1984,- 454

152. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка. 1980. - 273 с.

153. Сергиспко И.В. Математические модели п методы решения задач дискретной оптимизации. Киев: 11аукова думка, 1985.

154. Современное состояние теории исследования операций (серия «Оптимизация и исследование операций», под редакцией Моисеева H.H.).- М.: Наука, 1979.-464 с.

155. Справочник диспетчера речного флота. М.: ЦБНТИ МРФ РСФСР, 1990. -167 с.

156. Стернин М.Ю. Система поддержки решений задачи о назначениях. Системы и методы поддержки решений. Сб. трудов. М.: ВНИСИ, 1986, с. 74 - 86.

157. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы . М.: Наука, 1984. - 382 с.

158. Танаев B.C., (дисков К).П., Сгрусевич В.А. Теория расписаний. Многостадийные системы. M.: 11аука, 1989. - 328 с.

159. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.-256 с.

160. Taxa X. Введение в исследование операций. Т.1.-М.: Мир, 1985. 364 с.

161. Триус Е.Б. Задачи математического программирования транспортного типа. М.: Сов. Радио, 1967. - 208 с.

162. Финкелыдтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

163. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966. - 276 с.

164. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

165. Ху Т. 1 елочисленное программирование и потоки в сетях. М.: Мир, 1974. -519 с.

166. Черкасский Б.В. Быстрый алгоритм построения максимального потока в сети. В кн.: Комбинаторные методы в потоковых задачах. - М.: ВНИИ-СИ,1979.

167. Шкурба В.В., Подчасова Т.П., Пшичук А.Н., Тур Л.П. Задачи календарного планирования и методы их решения. Киев: Наукова думка, 1966. - 155 с.

168. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1992. - 504 с.

169. Якубовская Л.П. Задача поиска варианта обмена для заданного владельца при перераспределении ресурсов общего вида,- в кн. Построение автоматизированных систем обработки данных. Сборник трудов, вып. 16.- М.: ИПУ, 1978, с.64 73.

170. Abdul-Razaq Т., Potts С., Van Wassenhove L. A survey of algorithms for the single machine total weighted tardiness scheduling problem // Discrete Appl. Math., v.26, 1990, N 2/3, pp.235-253.

171. Aggarwal V., Tikekar V., Lie-Fern Hsu.Bottleneck assignment problems under categorization // Comput. & Oper. Res., v. 13, 1986, № 1, pp. 11 26.

172. Ancja Y.P., Nair K. Bicrilerial transportation problem//Manag. Sci., 1979, v. 25,N1 , pp. 73 -79.

173. Blanco Т., Hillery C. A sea story; Implementing The Navy's Personnel Assignment System// Oper. Res., 1994, v.42, N5, 814 822.

174. Brissenden T.H.F. Some derivation from the marriage bureau problem// The Math. Gaz., 1974, N 406,pp.250 257.

175. Chiwei C., Hirofumi M., Guochum T. Worst-case analysis of local search heuristics for the one- machine total tardiness problem.// Naval Res. Logist.Quart., v. 37, 1990, N 1, pp. 111-121.

176. Diaz J. Finding a complete description of all efficient solutions to a multiple-objective transportation problem// Ekonomico- Math. Obzor, 1979, v. 15, N 1, pp. 62-73.

177. Francis N., Fleming D. Optimum allocation of places to students in a national university system// BIT (Dan), 1985,v.25,N2, 307 317.

178. Gale D., Shapley L. College Admissions and Stability of Marriage// Amer. Math. Monthly, 1962, v.69, pp.9-15.

179. Gardenfors P. Assignment Problem Based on Ordinal Preferences // Mgmt Sci, 1973, v.20, pp. 166 173.

180. Gavich B., Schwa I/.er P., Sheiber E. The zero-pi vol phenomenon in transportation and assignment problems and its computational complications// Math. Program. 1977, v. 12, pp.226-240.

181. Hultberg T., Cardoso D. The teacher assignment problem: A special case of the fixed charge transportation problem // Eur. J. Oper. Res., 101, 1997, № 3, pp. 463 -473.

182. Isermann H. The enumeration of the set of all efficient solutions for a linear multple objective program // Operational Res. Quarterly, v.28, 1977, N3, pp. 711725.

183. Isermann H. The enumeration of all efficient solutions for a linear multiple-objective transportation problem// Naval Research Logistics Quarterly, 1979, v.26, N I, pp. 123 -139.

184. Kuhn II., Baumol W. An approximate algorithm for the fixed-charges transportation problem // Nav. Res. Log. Quart., 1962,v. 9, N 1.

185. Lee H., Pulat P. Bicriteria network flow problems: continuos case// Eur. Jour. Oper. Res., 1991 ,v.51 ,№ 1 ,pp. 119-126.

186. McVitie D., Wilson L. The application of the stable marriage assignment to university admissions// Opl. Res. Q., 1970,v.21, pp.425 433.

187. Ramanan P., Deogun J., Liu C. A personnel assignment problem// J. Algorithms. 1984,№5, pp.132 144.

188. Ross G., Soland R. A branch and bound algorithm for the generalized assignment problem// Math. Program. 1975 v.8, pp. 91 103.

189. Roth A. Conflict and coincidence of interest in job matching: some new results and open questions// Mathematics of operations research, 1985, v. 10, N3, pp.379389.

190. Roth A. On the allocation of residents to rural hospitals: a general property of two-sided matching markets// Econometrica. 1986,v.54, N 2, pp. 425- 427.

191. Ruhe G. Complexity results for multieriterial and parametric network flows using a pathological graph of Zadeh//Zeit.Oper.Res.l988. v.32, № 1, pp. 9 27.

192. Seslinn C.R. Some generalizations of (he lime minimizing assignment problem// J. Oper. Res. Soc., v.32, 1981, pp. 489-494.

193. Shaplley L. On balanced sets and cores. Naval Res. Logist.Quart., v. 14, 1967, N 4, pp. 453-460.

194. Ullman J.D. NP- complete sceduling problems // J. Comput. System Sci.,v. 10, 1975, pp. 384-393.

195. Zanakis S. A staff to job assignment (partitioning) problem with multiple objectives// Comput. And Operat. Res. 1983, v. 10 , № 4, pp.357 -363.