Исследование и разработка методов решения многокритериальных задач распределения, обмена, упорядочения в моделях транспортного типа тема диссертации и автореферата по ВАК РФ 05.13.10, доктор технических наук Коган, Дмитрий Израилевич

• Коган, Дмитрий Израилевич
• доктор технических наук
• 1999

Оглавление диссертации доктор технических наук Коган, Дмитрий Израилевич

Введение.

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

Список литературы диссертационного исследования доктор технических наук Коган, Дмитрий Израилевич, 1999 год

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.