Введение к работе
Актуальность темы. Проблемы распределения, перераспределения и обмена недробимых ресурсов, определения очередности в процессах их обслуживания являются типовымн для многих экономических, социальных и оргапнзациоттых систем. Центральное место занимают они в управлении транспортными процессами, гдЬ решаются задачи планирования 1рузоперевозок, распределения транспортного состава и заданий на перевозку грузов, определения последовательностей обслуживания транспортных средств. Классическим примером задачи распределительного пін;) япляется |рапсіїоріиая задача линейного программироваиия (ТЗЛП). С1андар1ная для данной задачи интерпретация - проблема сИнтеза плана грузоперевозок (т.е. распределения выпускаемого каждым из производителен продукта по потребителям) но реальная сфера применений математической модели принятия решений существенно шире. В частности, в рамках транспортной задачи и задачи о назначениях как ее частного случая могут быть описаны различные проблемы расстановки, распределения и обмена транспортно- технических средств определения исполнигелей заданий. Вопросы синтеза последовательностей обслуживания транспортных средств формулируются в терминах классов задач теории расписаний где обслуживанию подлежат заявки принадлежащие детерминированному входному потоку.
Задачи распределительного типа, формулируемые в. рамках модификаций транспортной задачи и задачи о назначениях, существенны в процессах управления научными исследованиями и опытно-консфукюрскими разрабогками, где позникаюг проблемы формпронання временных творческих коллективов, распределения заданий, определения организаций для эксплуатации опытных образцов продукции'.
В социальной сфере возникают задачи размещения объектов бытового и торгового обслуживания в районах массовой застройки, задачи обмена жилья, нпдивидуальных гаражей, мест в детских дошкольных учреждениях;
все они формализую1ся в рамках моделей математического программирования транспортного тина.
ІСіічссіі») нолучаемых решении, возможность ич эффекмншот практического использования определяется не только точностью и быстродействием применяемых алгоритмов, но, прежде всего, степенью адекпагности мтсматических моделей (огр1ниченнй и критериев) реально имеющимся условиям.
Прииципиально важно, что возникающие на практике проблемы синтеза решении задач распределения, обмена, упорядочения достаточно часто оказываются многокритериальными; в частности, для зранспортных систем это обусловлено как множественностью показателей, но которым решения оцениваются в целом, так и наличием в процессе перевозок ряда участников, причем каждый участник или группа участников по-своему оценивает возможные планы и управленческие решения. В связи с этим целесообразно введение критериев, характеризующих планы перевозок, работы или обслуживания транспортных средств не только в целом (общие критерии), но и с точки зрения некоторых групп учпстникоп (групповые критерии) или о1дслып,1х участнмко» перевозочного процесса (крнтерии учасчннков, индивидуальные предпочтения). Наличие критериев, характеризующих качество управленческих решений как в целом, так и для подсистем различных уровней, является характерным для большинства экономических, социальных и организационных систем.
Весьма существенной для рассматриваемых задач является проблема обоснованного выбора приемлемой схемы скаляризации критериев; в достаточно часто встречающейся ситуации отсутствия оснований для назначения конкретной схемы, естественно строить в пространстве критериев полную или достаточно представительную совокупность эффективных оценок с одновременным обеспечением возможности синтеза для любой выбранной ЛПР (лицом, принимающим решения) оценки Парето-оптимального плана, данную оценку порождающего.
Нередко проблема заключается не в составлении нового решения, а в коррскшронкс уже имеющегося, причем возможную коррск!провку можно чракговагь как обмен заданиями или ресурсами между участниками; при этом общие критерии следует оптимизировать на множестве решений, которые не ухудшают имеющихся значений групповых или индивидуальных критериев (оценок).
Важно учитывать, какие группы участников обладают определенной самосгоятельностью в принятии окончательных решений; конструируемые
планы и управления должны удовлетворять соответствующим образом вводимым свойствам теоретико-игровой устойчивости.
Сложность создания алгоритмического обеспечения определяется двумя контрарными обстоятельствами. Во-первых, рассматриваемые проблемы достаточно часто оказываются NP-трудными (согласно естественно -научной гипотезе P*NP, такие задачи полиномиальных но верхней оценке временной вычислительной сложности решающих алгоритмов не имеют). Во-вторых, имеются жесткие технологические или регламентные ограничения на продолжительность процесса решения каждой задачи. Разработку точных, приближенных или эвристических,алгоритмов, следует uыполнять с учетом pезультатов о вычислиісльной слпжіфс1и решаемых задач, а также данных о их размерности и ограничениях на время решения.
Вопросы построения н 'исследования многокритериальных математических моделей, создания, программной реализации и внедрения эффективных алгоритмов синтеза решений для задач распределения и обмена недробимых ресурсов, упорядочения в процессах их обслуживания с учетом несовпадающих интересов сторон-участников важны и актуальны.
Исследования по теме диссертационной работы выполнялись в соответствии с координационными планами АН СССР по комплексной проблеме "Кибернетика" на 1981-85 и 1986-90 гг., поддержаны грантами Российского фонда фундаментальных исследований (93-013-16253 программы 1993-95гг, 97-01-01095 программы 1997-99гг.). Прикладные разработки осуществлялись в рамках тем бюджетных и договорных ПИР Волжской государственной академии водного транспорта.
Целью нсслсдования япляегся создание меіодолоііін н номой
информационной технологии для решения днскрсшых
многокритериальных задач распределения, обмена недробимых ресурсов (в том числе с учетом индивидуальных предпочтений учасзников) н упорядочения в процессах их обслуживания, формулируемыx и рамках соответствующих модификаций моделей транспортного типа. Под моделями транспортного типа для распределительных задач понимаются ТЗЛП и ее
конкретизации для задач упорядочения модели теории расписаний в
рамках которых описываются проблемы синтеза последовательностей обслуживания транспортных средств Специфика вводимых моделей заключается в наличии иерархических систем критериев а также возможности принятия некоторых отсутствуют..* и сгандартных постановках ограничений что наряду с выбором сооiвciеп'уюшнхсхем компромисса обеспечивает высокую степей. адск.пшоап формулируемых
}
задач реальным проблемам принятия решений. Разрабатываемые алгоритмы должны обеспечить возможность получения качественных решений в реально приемлемом времени.
Достижение цели исследования предусматривает выделение важных в
теоретическом и прикладном аспектах классов многокригериальных задач
распределения, перераспределения, обмена и упорядочения, которые
описываются в рамках соответствующих модификаций стандартных
моделей транспортного типа, построение и классифнкацию
модифицированных моделей, определение целссообразпых схем
компромисса между критериями или коНцСпций тсоретико-игровой
устойчивости, изучение вопросов временной вычиСЛИІСЛМІой сложное!и
получаемых экстремальных задач выделение для тр'уднорешаемых задач
полиномиально разрешимых чнетных подклассов синтсч и программную
реализацию эффективных решающих алгоритмов., '
Методы исследования. Методическую и теоретическую базу
диссертационной работы составляют подходы и инсгрументарий
системного анализа, исследования операций, теории игр,
многокритериальной и комбинаторной оптимизации, теории |рафов, теории расписаний, а также ряд ранее выполненных работ в областях распределения и перераспределения ресурсов, трапспортною планирования и совершенствования эксплуатации водного транспорта. При вынолнеини исследований автор опирался на теоретические результаты отечественных н зарубежных ученых (Батищев Д.И., Бурков В.П., Воробьев 11.11., Гермейер Ю.Б., Гольштейн Е.Г., Емеличев В.А., Захаров B.Н., Кацпельсон М.Ь„ Ларичев О.И., Ловецкий С:., Подинонскпй В.В.. Сигал И.Х.. Типпеи B.C.. Шкурба В.В., Юдин Д.Ь., Bellman R„ Conway R.W., Couk S.A., (iale (>., Сішеу M., Isermann H.,Johnson D., Каф R.M., Lawler E.l... Lcnsira J.K., Shaplcy L. и Др.).
Научная новизна работы. Реализован новый подход к постановкам и решению широкого класса задач распределения, перераспределения и обмена недробимых ресурсов, упорядочения в процессах их обслуживания. В постановках задач выполнен систематический учег мпогокригериальности решаемых проблем, что обеспечивает качественность получаемых решеший. При этом построен ряд новых математических моделей (в гом числе с учетом общих критериев, групповых критериев и индивидуальныx предпочтений участников), которые с достаточнон сгененью адекватности отображают специфику реальных проблем принятия решении.
Для построенных моделей с учетом возможностей отдельных участников или групп участников в той либо иной степени влиять на формируемые решения, определять фрагменты этих решений, дан анализ возможных схем компромисса и теоретико-игровых концепций устойчивости, получены оценки временной вычислительной сложности экстремальных задач, возникающих в результате принятия конкретных схем, разработаны алгоритмы синтеза оптимальных решений.
В связи с наличием жестких регламентных ограничений на продолжительности циклов решения большинства задач и получением для общих посгановок многих из этих задач резульгагоп о грудпорешлемостн
(NI1- ПОЛНОГО ИЛИ N1'- чруДІІОСІИ), нучем ВВедеіІІІЯ ДОСІ1ІІочІІО L'CICCIIICIIIIMX
дополнительных ограничений на классы рассматриваемых моделей или допустимых в моделях управлений выделены практически значимые полиномиально разрешимые частные подклассы, построены эффективные но быстродействию алгоритмы синтеза оптимальных решений. Для задач, которые в рамках полиномиально разрешимых подклассов не формулируются, построены эвристические алгоритмы и интерактивные процедуры синтеза решений.
Обоснованность и достоверность результатов. Научные положeния диссертационной работы обоснованы математически с использованием методов исследования операций, теории игр, многокритериальной и комбинаторной оптимизации, теории алгоритмов, теории графов, теории расписаний. Корректность и обоснованность научных положепнй, выводов и рекомендаций подтверждены строго математическими построениями и доказательствами, экспериментальными исследонаииями nа 'ШМ, л закже практическим использованием при решении црикладных задач распределительного типа и при синтезе расписаиий обслуживания транспортных средств.
Практическая значимость диссертационной рабогы определяется созданным моделыю-алгоритмическим обеспечением для решения широкого класса многокритериальных задач распределения, обмена и упорядочения, возникающих в процессах планирования и управления в экономических, социальных и оргапизацнонных системах. Бла1одаря иерархичности систем критериев и многовариантности схем компромисса. построепные математические модели с высокой степенью адский і носі и отображают реальную специфику проблем, что обеспечивает качественпое их решение. Будучи в своей основе инвариантным к комкрсшым видам систем, созданное мазематическое обеспечение можс ! нспользоваться при
разработке объектно-ориентированных программных средств, пнедренче которых позволит повысить эффективность функционирования систем различных типов, в которых возникают задачи распределения, обмена и упорядочения в процессах обслуживания.
Становление тематики диссертационной работы связано, прежде всего, с выполнявшимися автором в течение ряда лет разработками и внедрением программных средств и информационных технологий для различных объектов внутреннего водного транспорта. Вместе с тем, разработанные модели и методы имеют существенно более широкую сферу приложений. 5 частности, постановки и процедуры решения мііоіокри1српальньїх трансноргных задач и задач о пазничепиях с нндивидуильными предпочтениями участников находят приложения в процессах управления научно-техническими и опытно-конструкторскими разрабогками, при определении мест расположения объектов соцкультбыга, алгоритмы решения задач обмена - в системах перераспределения ресурсов (а том числе жилья) методы синтеза расписаннн обслуживания - в сислемах управления производственными объектами с единичным и мелкосерийным характером выпуска продукции.
Внедрение. Изложенные в диссертации результагы выполненныx теоретических и прикладных исследований внедрены при решении важных прикладных задач. Математические модели, алгоритмы и программные средства решения многокритериальных трапснортных задач, сннгеча расписаний работы транспортных и транспортно-іехпологических средств применены во внедренных в Казанском речном нopiу - Камском грузовом районе и Уфимском речном пор iy Mнкрокомпиокрпыч CIісісмах организационного управления добычей и поставкой нерудных строительных материалов. Процедуры решения многокригериальных модификаций задачи о назначениях и задач группировки используюгся в практике работы Нижегородского филиала НИИ спецтехники и связи МИД РФ при формировании рабочих групп (коллективов исполннгелей) и при распределении спецтехиики между оператевпыми подразделениями осуществляющими опытную эксплуатацию.
Комплекс алгоритмов и программных средств решения задач недробимого обмена был положен в основу разработанной под научным руководством автора и внедренной в промышленную эксплуатацию автоматизированной системы обмена жилья в г. [Ърьком (АСОЖ «Волга»).
Полученные научные результаты включены в чттаемыс на фaкультете вычислительной математики и кибернетики Иижегородского
б
государственного университета учебные курсы «Системный анализ» и «Распрелелнтельные задачи планирования и управления» и внедрены в учебный процесс на факулыеглх Полжской госудмрсіпсиной академии водного ipaiicMopia.
Апробация результатов работы. Основные положения и результаты диссертационной работы дoклaдывалиcь на следующих научных совещаниях, конференциях и семинарах:
7-ом Всесоюзном совещании но проблемам управления (Минск, 1978), 3-ей Всесоюзной школе но математическому обеспечению АСУП (Горький, 1978), 2-ом Всесоюзном семинаре по перераспределению ресурсов (Москва, ИПУ, 1978), 4-ой Всесоюзной конференции по исследованию операций, Горький, 1978), 7-ой Всесоюзной конференции по проблемам теоретической кибсрнетнки (Иркутск, 1985), Всесоюзной конференции по внедрению ЭММ и ЭВМ в планирование и управление производством (1985), Всесоюзной школе-семинаре "Системное моделирование производ-ства"(Воронеж, 1986),8-ой Всесоюзной конференции по проблемам теоре-шчсской киберне1П<и (Горький, 1988), 11-ом Всесоюзном cовещании по проблемам упраплсния (Ташкент, 1989), 9-ой и 10-ой Всесоюзных конференции п> проблемам теоретической кибернетики (Волгоград, 1990 и Сарагов. 1993), Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, образовании, медицине" (Воронеж, 1994), Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург,1995), Всероссийской конференции "Ипформационные технологии и системы" (Воронеж, 1995), Всероссийской конференции "Математическое программирование и приложения" (Ккатерннбург,1997), Научно-технической конференции по проблемам транспорта (Нижегородский научный центр Академии транспорта РФ, 1999), XII Международной конференции "Проблемы 1еоретнчсской кибернетики" (Нижний Новгород, 1999), на научных семинарах Нижегородского госуниверситета по информатике и дискретной математике, на паучпых конференциях Волжской государственной академии модної o i раненой i a
Публикации. По теме диссертации опубликовано 59 работ; основное содержание отражено в [1-30].
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложений (323 страницы текста, включая 16 рисунков, I схему, 17 таблиц); список цитированной литературы составляет 202 наименования.