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

РГ6 00

• АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

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

ОГЛИХ Валентина Валериевна

. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ МАРШРУТИЗАЦИИ В УСЛОВИЯХ ДЕФИЦИТА ТРАНСПОРТНЫХ СРЕДСТВ

Специальность: 01.01.09 - математическая кибернетика

V

Автореферат

диссертации на соискание ученой степени Кандидата физико-математических наук

Минск - 1893

Работа выполнена

Украины

в Институте технической механики АН

Научный руководитель -

кандидат физико-математических наук

Официальные оппоненты:

Трофимов Владимир Николаевич доктор физико-математических наук

Сотсков Юрий Назарович

кандидат физико-математических наук

Ведущая организация -

Летан Виктор Васильевич Вычислительный центр АН России

Защита диссертации состоится {2* ьУ&рЦХ 1993г. в.''Л .чесов на заседании специализированного совета К 006.19.01 Института математики АН Беларуси (220072, Минск-72, ул.Сурганова, II)

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

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

1993 г.

Ученый секретарь специализированного совета кандидат физико-математических наук

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

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

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

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

Щ№_5анной_ра^ту_состоит_:.

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

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

"w

¿'каэйькай цель достигается б рзоультато решен® егадуищвх вопросов: -

иэтеыатач&ехгш пэстпюекв задача оггявдалыюг; росолошш .пунктов, располс^ошшх в некоторой области, ш группы, квцдоя кз которых обслугявазтся одшвл движущимся о5ъо1йо.!.': при о той долили быть определены траектория i порядок обхода пунктов и назначены пупкти отправления .раопалоьэшшо и другой оОлсстп;

-математическая постановка k-точочаых задач оптамизаци траектория движущихся объектов ;

- создание практически эффективных алгоритмов рошэпи задачи оптимального разбиения;

- создание точных алгоритмов , пригодных для решена eo.ee :упностн одло'г;яппгх к-точечных задач опттегаацн траектории, отлдчппчлхся лишь граничными условиями позволял^ эффективно отроить п использовать семейств оптпмалышх траекторий;

- обоснование подаода и оценка слоезгости предлагаема алгоритмов.

Нпучнпя__ноп;така__и__основные___Е5§ЗУМотых___вуносш®

- постановка задачи оптимального покрытия специально: орконтированяого графа а цепяш заданной структуру, огрдниченз/шн па длнну цепи и суммарный вэс (специфика rpm¡ G зашатается в том, что Беса дуг заранее неизвестни находятся из решения задач отыскания оптимальных маршруте на динамическом графэ переходов GZ);

- эффективный численный мотод решения вышеуказаннс задачи одтинрльного покрытая;

- алгоритмы построения дпаграмш полукольца матр] опш.кш>вцх затрат, предназначенные для решения зад; ошашзацдн мзрггрутов на взвешенном граф» с аддитивны] ограиичоааямя на дугах, принимающими как положительные, ti а отряцотедыше значения и с измвшшцомися правши част/п (обвдма огракачепшшп), позволящзе решать массовые зада' путоа нэслогзшж алгебраических преобразований "бвзисны: рэшшЗ;

- оценка слошгаста продложэшшх алгоритмов.

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

проектирования и обслуживания сложных технических систем.

Для всех предлоаэнных алгоритмов была осуществлена программная реализация на ЭВМ БЭСМ-6 и EC-IL45.. Проседэншшэ расчета* подтвердили быстродействие и эффективность предложенных алгоритмов.

Стд^кт^ра__и__объем;___работа.Диссертащш' состоит из

введениям четырех1 глав,, закличения* и< списка1 использованию* источников1 и&; 108 наименований!. Объема работы) составляем 151 страниц; в ток«числе' t2'i> машинописного текста,. 2 3 стронпцш рийунков.

Публикации и' апроббцшк,- Основные результаты',, полученные* fl-i диссертации;. излоеоп№ в* Ю-1 опубликованных* работах с I-IOi, d! такте докладывались йН< республиканской- конференции* *ЙЬтоды< и' проблемы- автока^звированного проектирования хг исследования! систем''' (г^Севастополь,1987г. ), на (isrrpoспубликанской' школе-семинаре* "Дискретная; оптсмизацил" (к>;Алушта,19а9,1991г.г. )>,. на научпо-практической конференция. "Совершенствован!!*- ■ управления предприятиями и* развитие самоуправления^ трудовых коллективов" (г.Ялта,1939г.), па сёШшре "Дискретная- оптимизация: метода- и приЛозкешш?' (г.Тбилиси, 1990г. )■, на семинаре "Теориж графов и приложения* (г.Одесса,J99Ir.),. на семинаре отдела "Математической кибернетики'' института математики АН Беларуси, на сексшаре кафедры- автоматического моделирования. Днепропетровского госуниверситэта,. на Ученом' совете и на ооъедшгешго№ соминар» отделов "Динамики! и> управления", "Дине^ез управлявши й&ганическик систем'*',. "Системных исследованйЭ" института технической механик» АН» Украины.

СОДЕРЖАНИЕ РАБОТУ

Зо введ&йй» обоснована актуальность Еозрангой тог.-л, Шлосеша* цель и исследований,, опгзг-анэ структура

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

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

даокретвой оггпшлзацян.

Суть донной задачи заключается d следущем.

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

Взшевпшй орлэятированнцЛ' граф G'(X°,X,U°,lí) задан

&eí0z9ctdsk2 Пар12ПН х°~{ х°л, 1=1,...к, х={х-л, j=i,...n,

!.aoS&CTD3.V3 дуг u°={ u°,^>={ <Zj,Zj)>, 1=1,...,K, J=I,... ,íí,

IM >={ 'х,,xi)>, 1=1,. ..N, J=I,—N. Каздой вершило

Л Г." i J — * t

z-^-x U X сопоставлен вектор огрвнзчвю® ...,Sjc),

,....I»VK. Граф G необходимо покроть миниизльннм числом

VX—sin цепей QJp, удовлетворяацих слодущш ограничениям;

I) цпчальная поршше с каэдой v - ой цепи всегда

срЕНБДлэхпт множеству Xo, а остальные етохеству X ; 2)

длина 1 попа стремится к максимуму И. 1ч- max, Кы; 3) вес

цэш! SíQ1^) не превосзодат I>L0 ; 4) вес цэпи без первой

дута ütG^-p/íx р>> е& превосходят L ; lí,L, L0-задатка»

числа.

Эта задача решается при условии, что взса дуг зараное шйзвэстш п задавтся взвешенным орграфом (мультнгрофом) CZ-Í ÜZ.CZ,ТЯ где UZ-mhos&ctbo вершин !LÍZ!=n. CZ-шюгзство дуг !CZ¡=т, Tít-мзожаство тагов дуг. Каздой дуге сопоставлен вес s(cz)«Zr Sj^bí uz^ua^ ), Z=0,I,... п вектор ограничен^ vz =( va1.....vz1").

Вас произвольной дута (Xj.Xj) в графе G сущрстЕэвно завясит от того: I) какой _цепи прхгодЕогэт данная дуга , т.е. какие вектора ftp и н] пршпсош поравпам, опроделшщим первую дату,

.....■s3's3t!.....хз); 2) какой по СЧЭТУ

D кгодзг? дуга (Xj^'ízj®) в цепь; 3) какие вектора l/^,»^] щкапсапа продгостоунщоп я последующей г^] вершинам.

Для ояр&дэлэтш веса дуг (x»,xj) в графе G необходимо I) гр&фо GZ (tIZ.CZ,Тй) вшЗрать последовательность дуг

сц(аз. ,...,cz ) (р «эгэт бить » ICZI), обоспочивапдуи

i

и!п з,.«=5г при ограничениях: заддч» А> ' 7ку .=/»6, с&эса х,)' са^сз

где ад® .4. «'Г- '>т>- Дяя

гес-зроопзш дога требуется рвиопне зздот:! при огрошлэпхтх: задача В> £__ргшно посл&допптольш

ж 4. С2«С2 ^ д.

(А1,.....¿ГЬ.....(А1 ,...,А; задача С) тшбуэтся

1 ' к 1 +

дзсглпь «'.пкснлальноо число (&,... ,А" такзх, что

при условиях: I) !<!*, М заданное целсо ч^схо;

саеез ^

2) 55Ь+ХЯ; 3> БТ -а-Б^'Ь» где 1 з 10 зэдзптп;э ч::слл; задача О) для требуется достичь каждого го

(А ,...»А 1=1....к с определонкем послрдопзтолытоетя Де>С*И28тИ.

Величины А® тогут быте» значительно больй» велзггоЕЭ Щт.» рэвкой суггх- ограшгчепнй всея дуг грсфа

Сформулированная задач г покрытая сп&щтэлыгого ориентированного графа цепями заданной структура о ограничениям* на сухарный вое и длину доп"л рззбтааетея кэ две комбинаторные подзадач!?. Вовроса, поставл-лто;-} и стп: подзадачах, а такнэ структура графов и число г-с-рс-хя существенно различные, поэтому трг-бовашм, иродьязля&г.г» к алгоритмам их решения таюке отличны друг с*' друга. Вследствие этого разрабатываемые» методы по срзгшэшгэ с известнгаш должны позволять:

-получать близкое к оптимальночу р&гляло водэчг? покрытая спо цельного орнентаровшшого графз Я дэшгди звданной структура с ограничениями на длину ц&пя п суг'-тзрп-:! вес; специфика графа и заключается в том, что еэсэ дуг находятсяа аз решения задач отыскания ггарЕ^утов гэ динамическом графе переходов;

-получать решение любых конкретных етдквздуалыих задач А,В,С,В для всевозможных значений сектора врагкл частей ограниченна путем кослоют/х прос 'разово'пй "безоки" решений, получаемых из решения конечной совокупности индивидуальных задач для зкаче;сй1 огрзклчмгай, по превосходящих некоторых наперед заданию: конечных вэлипп, определяемых только графом СЛ.

Во второй главе для решения задач А, В,С,Б пр:т:эгэп теоретико-групповой подход, осуществлено его далыгэйноо развитие. Решение оптимизационных задач но ззповэнпои

сржстгаровайдо:.: грз'|а с аддЕГпганши огрзнпчешяш ва дугах, прашмащака кек полсйзткишэ так и отрицатзяигыз заачошя» сш/"">ш к . гюстроетш и анализу полукольца матриц опчтаяльпнг Ептрат со специально подобранном ошэрацшзш. Излохэшз рззработашша алгоритму. Приведены оценки слошости алгоритмов. Работа олгорптшв проиллюстрирована на коЕкрэтшк ггпл-иорпх.

В п.2Л раесштрон алгебраический подход, рспользуоша в работа}: В.В.Гсрбунцова для роионня задач оптсшнзоцдп шргрутоп бзз ограничений, . с использованием полугруппы ) матриц оптимальных затрат п-го порядка с полугрупновоК операцией &3 : С=АЕЗВ »

гдв С-А&В (а11с(^)ьк;}); р®8=р+в. рф8-т1п(р,0),

е- йг.х^ь^);'" а,б.се б. 1,3.к ^

Так как для ро^егия задачи оптимизации маршрутов с

учотом ограничений данной конструкции недостаточно, в п. 2.2 предлагается рзсшрлть полугруппу до полукольцо (К. ® , ЕЗ) квадратных ыотрнц п-го порядка добавив операция: С-АВЗВ -Афв-в* - С-С'-а; ь13=ш1п(а1.-]'ь13)»

2-®1л(с'., А,В,СвК.

.3

Приведем утверждение из которого следует конечность

полукольца (Р., ,Ш). Есла воличшш разброса катрид-

образуицвх по строкам гстр=, 1:Еа1 ' г^^ ^-г^^! и по

*-1,к-п

столбцам гстолб=, ^^¿/^Г^й: ограш-еш. то

Еолпчлна разброса элементов любого элемента полукольца I

тогев ограничено г- шах г.,.,- ш!л г.,., г„,п1гЛ.

1£1,Л£П 13 151,¡¿П 13 СТР СТОЛО Для роаення поставленной задачи нот необходимости

серость есо полукольцо котр-щ (К.^.ЕЗЭ ). Достаточнс

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

шэурпц оппхиолъшх затрат, которая строится в пространстве

ограютошгЗ 41. Кромэ того, рэзмэр этой часта не зависит о-

кошфэтЕЫХ значений ограниченна А^, оа не превосходи-

пекотори. косочпих кэлзгпш, задавземих графом СЪ.

В п. 2.3 рассмотрены алгоритму построения натри

оОразупззх я дазгрзкки полукольца матриц оптшальних затрат

а угшаэ дапэ обоснованна слошостп приведенных алгоритмов

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

зтппятся в соотвотств1то цвлочислвшшй вектор, я р п к т о р ттз '/гдкй прирвщешю гранячпых условий. Вводом зрострапстоо ограничений ,... ,72,.), где У2 мнохвство

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

полукольца,определенного операциями С2>ЕП), каздая такая матрица характеризует минимальные затраты на перемещение из начала координат в точку V.

Для построения диагрвммн применяется последовательная процедура уточнения матриц -элементов по формуле:

М1Г Ш(а!1<-а1.....Ч-а^^'4 .....

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

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

Структура диаграммы полукольца для случая дпух ограничений имеет следу щий вид. Плоскость ограничений (У21 ,ЧЪ0) разбита базисными вектором ограничений на конечное число конусов, в каждом из которых можно выделить четыре части: некоторую индивидуальную часть и три части, имепцде повторяющуюся структуру. В случае, когда уа^О, ,..эти вектора соответствуют базисным векторам задачи цолочислоипого программирования, ■

Алгоритм I предназначен для построения кптряц-обрвзунцих из матриц затрат и ограничений, задащях граф ЪЪ. ;

Алгоритмы 2,4-8 предназначены для построения диаграмм . '; полукольца матриц оптимальных затрат для ограниченна, !

принимающих как положительные так и отрицательные значения, I

и кшщях размерность вектора 1=1,2. ! ,

Алгоритм 3 строит полугруппу расширенной матрицы затра*? ■ 'Г (Б', ЕЗ) для решения задачи нахождения всех кратчайших путей |

на взвешенном графе с одним аддитивным полоннтельиш ,!

огрзшчовнеы на дугах. Сложность алгоритма 11 д

0{ (п+ г У2«<-п) ), где п-число вершин исходного графа»

щ-число дуг исходного графа, значение ограшивнкя на

дуги (1.3).

Алгоритм 2 основан на построении давграгаа полукольца (й, (§) , 52) матриц оптимальных затрат, предназначенное дая решения маршрутных задач но изшшзнном графе с однкя аддитивным ограничением на дугах, имеет сложность 0(п5:с>, гдэ С- конс?атгга определяемая графом ЪЪ.

¿лгорнжа 4,5 построения диаграммы полукольцо {Я0.ВЗ) матриц отгкальзеа затрат, предназначены для решения ыарсрутиых задач, пэ взв&эешюа графе с одним .аддитивным ограничением на датах, принимающим как полоазггельные так и отрзда-гольяие значения. Сложность алгоритма 4 имеет порядок СКп'^С). Слогзость алгоритма 5 - 0(п^(р/а)а), где а-число итераций.

Алгоритм 6 построения Д2агра&&«н полукольца (И,® ,ЕВ) кзтриц оптимальных затрат, предназначенной для решения кзрпрутяш: задач ва взвезенном графе о двумя еддитивншяа зслоеешш>еумз ограничениями имеет сложность порядке 0{п7г2С).

Алгоритмы 7,8 построения диаграммы полукольца (И,1*^,ЕВ) матриц оптимальных затрат предназначены для решения мархрутных задач па графах с двумя аддитивными ограничениями, пришгмапцими как положительные, так и отрлцат&льниэ значения. Сложность алгоритма 7- 0(пэА).

В главе 3 разработаны точные алгоритмы решения гюстсвг&ШЕлг в главе I задач оптимизации маршрутов с процзгугочнцлзз гровзчними условиями А,В,С,Б на графах с вддаипззл'лп ограЕичеизякз на дугах. Алгоритмы рассчитаны на роаэяЕО совакупзэота одзотшних задач, отличаицихся значениями прехза частей ограничений. Приведены примера.

В П.-3.1 рассматриваются влгорито построения матриц сосгоянс2 а прожиточных вершин.

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

еашшчоЕии 3-еП гласу предлагается алгоритм, позволявший

свооти определение оптшальвой траектория на графэ GZ прп ;

усяотая ДОСТШГ.Э1ЕШ СОВОКУПНО С Ï1I ЕЗДБШШХ o6cçc ограничена!,,

дяи случая шшшотного порядка сяэдрвсв^л Cïj

т.. о, рэаешго обобщенной задачи шямявоягора па ' грпфз

GS1=(A,GZ), к ропгошта зпдачп комт-гооя'кэро на грофэ GS боз

ограничений. В обобщенной зодочо коммяпояжорз изогэсгоо

зэршпн Л-а то ограничения, которое необходимо достичь, о

GZ=(TîZ,CZ)- граф с двумя пдцитсгангми ограничениями па дугах, ]

опродвлкщкй конкретную траектория двже&нил мзяду любимл

ворпшнпш-

Работа алгоритмов проиллюстрирована на конкротгалс примерах.

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

В предлояэннога эвристическом алгорите построение цепей осуществляется последовательно и начинается с вэриглп га^Х, йклшеш» которых в какую лноо цепь наиболее проблематично, К таким вершинам били отнесен-i вершит". имеющие шгог.глльпое количество допустимых связей и такие, что ребро мипимэльшгэ noca шщидентное им тлеет максимальный вое. Как прошито, такими вершинами являются вершин?}, расположенные по граница'» области. Для указанной вершины а впбираетоя вершила

начальная вершина цвпя. В зависимости от внбора вершка et и (3 выбирается вершина ? - вторая вершина цопи. Для уипзашшх вершин а, р , 7 габлра&тся кгоггество взрппга. которг'9 -hm9dt возможность войти в ц&пь, еэ которой рпиезтоя !

задача С.

Включение оставшихся вершин осущэстпляэтся с использованием алгоритма градиентного тест. Прп о том пэо | • !

дуг определяется с помощь» диаграмма полукольца матриц Г. • . { оптимальных затрат. Построение цепи закапчивается d случае .когда 1-й, либо добавление произвольной верппшы влэчот ' • i

провшониз ограничила. Работа алгоритма закапчпппвтея, воли ; ('

гокртз все вершины графа G.

Работа алгоритма проиллюстрирована примером!

Эффективность предложенного алгоритма обусловлена его бйст^ ^действием; небольшим объемом потребной' памяти1 и» усто&швостыэ решения при изменений' пйракетров. Это означает, что при' увеличении параметров L и L0 (ограничений' на вес цепа) чиЬло цепей1, необходимых для покрытий1 rpaj&v уменьшается' и1 сфемй^ся' к теоретическому" минимуму N/M.

ЗАКЛШЕНИЕ

Основные результату диссертационной1 работы могут бы№ кратко ЕЗЛ020НЫ' следущий* образом:

1. Представлена МйТематическвя модель оптимального1 обслуживания пунктов' в условиях дефицита транспортный? средств и при налЛнН' ограничений в промежуточных точках.

2. Проведено исследование двух экстремальных задач на-взвешенных оривнтиройаниых графах, связанных с покрытиями1 цепями и опта&НЪаци&й' маршрутов с ограничениями.

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

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

5. Введено понятие и разработаны алгоритмы построений1 днагракбаг полукольца матриц оптимальных затрат, строящейся в* пространстве ограничений. Это позволило существенно yüäHbEHVb обЪ&ы вычислений. Выявлена структура диаграммы 0 Ш париодаческие свойства.

6. Показано, что предложи иные алгоритмы, исиользущие ЙагЬвраическиа подход, наиболее аффективны в том случае,-ЧогМ' Требуется решать большую совокупность однотипных задач ог^й&йзацаЗ с ограничениями, отличащихся только правша

ограничена».

luafeptftte',? диссертации опубликованы в следующих работах.

Г. Jbisojsav H.A., Оглях В. В. Об одной методике

Евт-омэтизиропвшюго выбора проектных параметров слоззшк техшгаоокях скотом // Методллоги^вскт пробджш аптоматтопровзнлого прооктпроваппя п исследования систем.Тез.докл.ро сп.копф•-Сова стополь,1987.

2. Горбунцов D.B..Ог.лтс Б.В. Адгобрэическгш свойства дпскротшх стационарных процессов с ограпгачипсгазгет условия?!!! И ИХ ИСПОЛЬЗОВаГШЭ для создания ЗффОКТЯШИХ олгорит\юв оптимизации управления// Г'етоипо прикладных задач матемотпчоской физики и дискретной матомлттсп. -Днепропетровск : ДГУ,1Р87.

3. Горбунцов В.В.,Оглих В.В. Алгебрзнчоскай метод оптимизации программного годпульспого управления двизусргаася объектами // Вопросы прикладной математики и матоггатического моделирования.-Днепропетровск : ДГУ,1983.

4. Горбунцов В.В.,Оглих В.В. Алгебраический подход к решению задач оптимизации триокторин с прскекуточ1'»№1 граничшиш условиями // Вопроси прикладной матоматптга к математического моделирования.—Днепропетровск : ДГУДВ8Л.

5. Лихолат H.A., Оглих В.В. Об одной алгоритма покрытия графа лесом // Методы решения задач математической физики и обработки данных.-Днепропетровск : ДГУ, 1990.-С.77-81.

6 Оглих В.В. ^Алгебраический алгоритм решения задачи о ранце // Метода решения задач математической физики п обработки данных.-Днепропетровск : ДГУ, 1990.-G.II6-118.

7. Лихолат H.A., Оглих В.З. Алгебраический подход к рошетга задач механики дискретноупрявляемнх объектов // Математическое программирование и приложения. ?оз. до'кЛ., Свердловск, 1991.-С.II0-III.

8. Лихолат H.A., Оглих В.В. Об одной комбинаторной задаче оптимального управления // Вопросы прикладной математики и математического моделирования. -Днепропетровск : ДГУ, 1990.-С.77-81.

9. Лихолат H.A., Макарова A.C., Отитах В.В. Программное обеспечение задачи управления производство нно-эконоинчеслгтл! структурами с применение дорогостоящих изделий в условиях ограниченности времени // Новые организационные структуру в экономике. Тез. докл. Всесоюзной нвучно практической конференции., Днепропетровск-Ялта, 1991.

10. Likholat N.. Ogllkh V. Algorithms of graph cover with forest of special type, Proceedings of tho eusaer

oobool on the Ka thereat ioal modelling and Boientifio ocaci>utationa, Albtina, 1990. Bulgaria. ClfiCI. Reg. N HO II Q14147.

Ho^iscsko k neiara 05.0I.I993r. E3> I6508 ®opaaT 60x84/16 E^iar o$coiHnn ycJt.nsH.jracT. 1,0 Y«I.H3,H.JIHCT 1,0 ?cpaa___IQ0____3aic§3_39._______B&cnjinTHo__________________

OH UHSSNU