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

АКАДЕМИЯ НАУК ССОР СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ШВШИКИ

Нз щж&Х pyroses

Ш.ВД5 Эдуард Хайруздиношч

7Щх 519.65

АЛГОРИТМЫ С ОЩШЩ да ЗАДАЧ Щ.-ШЙР01ШШ КРУШСМАСШТШШХ ПРОЕКТОВ

01.01.09 - математическая кабернэжяка

Автореферат

диссертают на соискание учшой сгэшш доктора физико-«атештяческих йауя

Новосибирск - 1988

Рабсза вылойшш в Шштатуяе гаате&- тики СО АН СССР

Щшщивише ошдасвзги: доетор рзнко-матеиакгавекшс наук,

профэссср Шеличев В„А„

чхэи-корресловдент АН СССР, профессор Красногцаков П.С,

доктор ^изико-ыаташгическнх наук, профессор Мазуров Вл Л.

Е^дуает ©ргоЕЕзацаяг Ивоттут кнберлэгики АН УССР.

сосгоызся " "_198 г, в чаео!

на воседашв СЕвцрашзироБанпого совога ДО02.23.01 пра Инсгигу-кз гаг&шака СО АН СССР {630090, Новосибирск, 90, Университет о-ЩКИНШЯ,, 4). "

С доссЕрзздней можно ознакомиться в библиотеке Института каяеаатини СО ЛН СССР«,

АвЕсрефзраг гизоошЕ " " _____________ 188 г.

Ученый секретарь мевдализйрошшого совета J2302.23.0I

докжор ^шко-ыатшагических шук Е.А.Палютин

ОЩЛЯ ШЖГЕРИСТИКА РАБ01Н

Актуальность гемы, Разработка и исследований ряда крупномасштабных проектов, реализуемых в народном хозяЗогвз,» кгевзбс-вали изучения таких магематических моделей пргшяткл оятнмаяктх решенйй как задача календарного планирования з услсшях огразн-чешшх ресурсов к заданных директивных сроков 0 задача размещения предприятий на сетях транспортного кша» задача выбора тгшйга технических средств (мапвт, механизмов) н Осс-'з--> арлугяа™ ность эти проблемы приобретав? при плаккровакш к рглазз;а"лч га- -кос крупномасштабных народнохозяйственных прох^ша; з райеках тк-тенсшшого освоения Сибири п Дальнего Востока гак сгржэяБозгэ ШЛ п дальнейшее хозяйственное освоетша цришсггэдзй к ШМ. соча, развитие Западно-Сибирского нефтегазового' комЕЛС-ксас выбор вша-га оборудования, парка машин и ыэхаишоэ,, параметров есе-оЗ пнет и т.д.

Указанная проблематика интересна с математической ео~кз зрения, поскольку она непосредственно связана о т-зко! бурчо швагощейся ветвью математического ■ програ^сягровзгш: гг/ пая оптимизация«, Более того0 упомянутые вшпе отоизязгчезкге ::о-~ дели, хсак правило, приводят к необходгшостн рзеоко^ШЕЕЯ яакгтх задач дискретной оптимизации,, которые в послсдесь Ертшго

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

записи входных данных. Этот факт два-^ря'десягнлсжя гену язсад связывался с так называема? "проклятие».? ра'змср!:оогнв0 а в ле 70-х годов после сформирования концепций зффзлпляой Сзэлшго-щальной) сводимости переборных задач приобрел соогвегс^.тдазб теоретическое обоснованна благодаря выявлений уак шгнкеушс универсальных (//Р-полных) задач (С„Кук5 РеКарпг, Л „Левин),,

Основными объектами зтой тесркмх'явягаотел: явдпгщдувакгвя задача, массовая задача (в дальнейшем просто ггдача) „ класс всех переборных задач; класс Р переборных еадач„ разрегдаых за полиномиальное время на детерминированной мапрша Тшрянга (очэ-

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

3

— щцяо„ А^сМР) и подкласс класса }1Р упомянутых выше "эталон ншси по слогнос-гн А1Р -полных задач, к которым полиномиально сводится любая другая задача аз НР , Большинством специалистов пршшмаегоя хяпоэааа» что к„ следовательно, нн одна

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

Поскольку трудно надеяться на существование (а„ следова *еяыю„ а шстроадае) эффективных точных алго^лтыов для указан-шх задач |ЩС1фетпой оптимизации* то особую акт}

аяьноегь приобретает, во-шрвах» изучение более уздах классов вадеч^ уча? специфики кэгорш: позволяет разрабатывать эффективны® го-дшз алгоритмы $шешав и, во-вторых, рассмотрение более ттяжяъ гжосапрнблшавашх алгоритмов,

К важнейрш характеристикам качества алгоритмов (как точ-вих, хав и прйблккектд) штасят трудоемкость (количество зяе-тш&рл>£ь сгхарацийУТ ;требуемый объем (число ячеек) пашш 12 в Шо^сдаку для разных конкретных представителе]! из ввделе! пого юшеа дажеодной размерности) указанные параыет]

вдуз? он5Ь различай« яоаас интересуют оценки (сверху) для ха-раккёраезйв качества алгоритма, необходимых для решения любо: конкретней эадача даяиой размерности. Для характераэациа щшбд; глЗЕшлх алгоршшв необходимо еще представление об отклонения ез&№ших соородстзоа првбягшенвого алгоритма решений от оптп шльныхо Говорят, что 1фиближшшй алгоритм Л шее? оценку •гочаоо^щ „ «оли яда всякой конкретной задачи (без огран

чеваа обзщо&щ - ш тШхщ) относительная погрешность £*)/ огиекгшая цоаавой функцаа ъчш алгоритмом не превышает £л , г ш'1?- - соотзвегственно црзближенноа а точное значение цел вой ^гшзди Такие щшблтаакгеш алгоритмы называют также алг тергштжрованныж оценкаш точности. Однако тащв г дачи оогшатс.1 ^грудаорешаемыш е кэтом случае. В то ке время Мно надеяться на построение аффективного алгоритма, гарантнр

кцзго заданную точность,, еслк.пз дяя всякой коккрз™с-й задгш ».осматриваемого класса е то для значительной чг.отл зодач. Шдоб~ юэ распирение класса исследуемых алгоритмов привода? к ввелотж •акой характеристик! качества алгоритмае как одойта 6£ «ого„ щсколько данный алгоритм Л из- яарантяруот. требуемой " vcmeam »тения« Параметр. о, йота сскшать как оценку отшоетеашюй tacrcTu несрабатывания гигорятта Л „ о которой ига случв8воя va-Jope конкретной задачи прпмзненяо к вей одгсрзтка osastsaeswï 5езрезулътатным. Указанные оценка я А caracas айкду сзбой зоотношением - ' "

• n„ Pfí^ííríXf <<£.':

да 2 [*} - вероятность ссотзотстБуюадго соб'гелп. ^

Пояятйо, что оценку щюятяоегя яоорайайозяяя! «яасртз адшо связать яе только с требуемой точность» алгорзйш, ио а о :го оценками трудоештостй и памяти»

Идеи построения алгоритмов о оценкам» походка нз рйаз \.ЭЛекнона по синтезу- переключательных cxe&r я'С*В«Я&1®зсе£?о г,о злгоратиическш трудностям саптеза 'кянвваяБШес яс-тгстагдг е:сегЧ Тришенителыго к задача?.' дискретной ошадааяаз гаябггзэ ртяет результаты по разработке л обоскозздав алгоретшз ■ о вдедазга Зшш получены а Институте ттакзткйн S0 Ж <Й0? 190^5 В*А.Перехгаища й диссертант, ХГ'33)е -Easyc-o гаюз» ct&ss es-горитмов с оценками занимает асгаотстпческя ^огяа» f.Tor-nwj, . [им которых £л~> о.'р. § О с ростом paratpaosss ' куетз„ Ifeío-тателен сам оо себе факт» что в случаэ акоттсткагсйя тсчгого алгоритма с упеягчеялем рагмзрнооти задает m г.утт ггезтлз гс-зге рассчитывать на получение бсэ более точного ggsaftes я s : -sïp?« смысле наш враг - богатая раз^орность (гфушялзештабаогга) ча - выступает а рола нашего невольного совзшп®*

Целью настоящей работы является исодейовёЕ©9 дайо^зшоежегк алгоритмов для решения, указанных етпе груддарекегл/Е декретной оптимизации аа осяове учета специфики указанных гадет н статистически эффективного подхода» связашого с цгшешзгпгй со-строения эффективных алгоритмов о одеякш® йх качества'« .

: Васильев ю.д.. Глаголев В.В.. Коробков В.к"» msspreecisná исследования в_дискретнс.. анализе // йроолемы ¿моерйэ'таш „ - Чв 1973. - Вып. 27. - с. 63-75; Яблонский C.B. Об аятжтмгческах трудностях синтеза данимаяышх контактный "схем // Яроблеьте кибернетики, -.M.,f 195^. - Вал. 2. - С. 75~I2Î0

' Науикяг; мтазна, В диссертации идеология построения алго-ptiiMos с одегегая использована для исследования характеристик качосхоа (грудойшоаги,, пайятй, точности „ вероятности несрабатн-s&zs) ¿;йлсгр7дг)£»кйз: алгоритмов для решения известных трудноре-imei'ux дискреяшх одтшнзащонных задач: задачи кошивоянера, веда® калйадпрюто планирования в условиях ограниченных ресур-еов„ гадачл упаковки в контейнеры и в полосу, задачи размещения ш-сагк еравспоргнсго tsna н задачи стандартизации.

Вндаяены классы задач 0 для которых'удается построить эффек-■швши вочныа гиггсритьш: для одномерной задачи упаковки в кон-sejiuspi; в слу^аг специального класса детерминированных. сгаюкоь грздгзехоз, дея еадач размещения на ациклических сетях и циклических се*2ях с центрально-связными областями обслуживания, для задача размещения на отрезке (задача ближайшего соседа) с супермодулярной функцией затрат о для задачи стандартизации (в случае свойств свкзносзн£ квазивыпуклости, обобщенной квазивштуклости) н да» ' . _ •. - '

Оиооновшщ эффективные приближенные алгоритмы с оценками 8j , (б том "¡коле я условия- асимптотической точности) для задачи Еовглпюяаера на минимум н на максимум,- задачи календарного планирования Се случае складируемых и нескладируешх ограниченных ресурсов), задача ушковш! в контейнеры и в полосу со случайней сяаокака, задачи стандартизации.

Птзактичеакая ценность „ Разработанные алгоритмы используются дрз яострозшш ¡.lassbiai-inecKoro обеспечения в задачах планирования 1фулног,асштабяых проектов» Статистически эффективный подход е ксследованшо трудаорешаемых задач дискретной оптимизации мокет быть иедслЬаоваг: для построения новых эффективных алгоритмов . с сцепками. •

¿¡ШйййЗЗй* Основные полоаения диссертационной работы частично ели в цслоу докладывались на Всесоюзных конференциях • по цроблслау тосрсзкчзокой кибернетики (г.Новосибирск)„ УП рабочей ксЕфэренцип HIP но моделированию,-и оптимизации елейных систем (Нозоснбзройа IS70), П конференции IP3P по оптимизации (Варшава, 1880)р П Всесоюзном семинаре но комбинаторной математике (Москва/1976) t Всесоюзных конференциях по проблемам БАМ (Еяаго-.вещзкек, 19?-? в 1988? Улан-Удэ« 1981), Всесоюзном семинаре по

и те;.ш$нк& {Г.Кйшнев, 1983), на научно-исследовательских оешварах в Институте математики СО All СССР, Институте

G -

кибернетики' математики Уральского научного

центра. Вычислительных центров АН СССР и СО АН СССР (Höböch-бирск), на рабочей встреча по дискретной оптишеадки {Алушта, 1986), на 17 Всесоюзной школе-семинаре по дискретной рпгнкзэЕЦйа (г.Таштагол, 1987), йа Международной конференция по сяаяяосяи вычислений (Казань, IS37) 0 на УП1 Всесоюзной конфэреншн яо язо-ретической кибернетике (Горький, 1988).

Публикация. Результаты диссертации опубликованы в [1-35] „ Структура и объем работы. Диссертация сосгсат hs ввэдегаш, четырех глав, заключения й списка литературы (118 найкайовашй) п излокена на 224 страницах.

СОДЕРЕАГ7ИВ ДИССЕРТА1Щ

Во введении обосновывается актуальность *ема дасезртзцЕЯ, обсудцаются вопроси, связанные с построением зф|31дазиых вжго-ритмов решения задач дискретной огошкзацши В сгз:?$ с «гао поставленные на рассмотрение задачи принадлежав й числу трудно-решаемых ( WP-трудных), обосновывается необхсдазгозев с'ожзз пристального изучения специфики задач и перехода к шводьзовакгаз Золее широкого класса приближенных алгоритмов с ми9 vc&bi* во-тертвовав в определенной степени понятием точноота 8ягоратвзз8 то пытаться сделать ею малотрудоемким (эффекташыа). Шюкзлькзг алгоритмы о гарантированным*! оцешшки точности чато се позеоле-от построить эффективные алгоритмы, приходится «ешзмвагвся ?ак-

и от гарантии, чтобы алгоритм всегда обеспечктгол аадвЯЕуо точность. Это приводит ж пояяхт приближенных алгсртноз о сцеп» ¡tarn ¿А я ¿>4 ГШ,

Подробному описанию основных понятий», с®жданыг о посгрсе-шем и обоснованием алгоритмов о. оценками, псоаячеаа первая глава. 1» этой главе введенные понятия идяюстрирушся ка пршиврэ пя-роко известной математической постановки s задача кшиявсяизра, шиющейся своеобразным оселком» на котором иршеняготся'Е отга-шваются различные алгоритмические идеи оцтишэа&аа» В частно-:ти, именно к этой задаче был впервые применен утверсальшй точный метод ветвей и границ, широко используемый з настоящее зремя для решения декретных экстремальных задач, и позволяющий гайке организовать приближенную схему вычислений с апостериорной

оцэвхоВ »«возя» зсяу^аеыого реветля. Одшш из ранних примеров шаяроенка эс&ваязшого алгоритма с оценкаш ' является

ш-эдщк /.¿.Вороькова яш решения задач класса Жп , получаемых 2 рааулшяз • сдгкШного выбора Н точек в ограниченной односвяз-цо2 Г -горного евклидова аросграистьа, Г» 2. , галавдей

досеаго'-®? гладкуэ зраннцу. В случае разиивероятного выбора п згочзк в сйгатезш квадрате данный алгоритм имеет следующие оцен-качсстаа, егоей работы; Ыс<ъп Г1~ п £ -О '¡8

п (/ 1 * и* г 1

Ор О П-ТО& ь

Шркк розулшагда з направлении выделения нетривиальных клйссоэ веда* дйсгсргзгяой ©штшацЕн» дош которых представляется воашаанн лоМ'гювкяе стагноточески эффективного алгоритма для рзпжшз аздачЕ яошивоякэра, является обоснование условий асшп-еозячоской есщюсгп врайлиавнного алгоритма "Яда в блиаайшй I з-Еройкс:ип$ город" <Х8вЭ г.« автор совместно с Ь.А.Перепелицей £2о"Л). Обсггачгс: его через Л\ ,

Теоозш 1.4«, Пусть элементы П*П. -штрицы \С-;) принимают 80£*вшя кззашсшо друг от друга нб множества { 1В} согласно дмяршквд распределению {(ри... рк % о, к-л,...

, Тогда алгоритм Л является асымпто-

кзязакг т<таз9 есда В

гт ' -

В «-'Г.

•Л д'

¿1 4-'-О(П),

'К

Стаггл

Слалотачо.'В случав равновероятного распределешя услоше акзлвгозягаэошЗ эсчаооот пршшлает вид

Ь.п - о (п/Спп).

Б рабоаз ГII] (1574 г,, совместно с ВД.Переаелвдей) этот результат бкл обобщен на случай непрерывного распределения.Пусть Ж1Ь класс задач кошгвоввера,. каздая конкретная задача в которой получается случайна« н независимым выборои любого элемента и* и -катили (Сгу) из отрезка [<1а, 61Ь] , Яа> О, в соответствии с одхшаковой функцией распределения ?Г(х) ~-Р(£<х}

С1п £ X и .-Пусть Зукяцзи рящтязша

рованной случайной -велггошы | « ( к - ае«)/ { $ ~ аг ) р

Теореш 1,1. Алторякт на класса «л.-- (Л/г,

а-

гогяашшэрз являйся ¿оижготгчгсга тж*, «ягл

а,, [»иг* {пХ1Ь;Зп}) тав - корень урэкгеют * ~ / -¿тгг »

^ _ . -"-у

Теорема 1.2. В случае вжйкязгг гэрсзгспсёя р{§) Еагоой случайной велздаян § -( ас - / ( — ее5,. ззо-ду болгпзй нуяаг ра * р0 - погсклгаг

О < рс< 1 . „ аягсретм за кг?,ооэ ' аог^гчхстп-гсс^п града, 3052

- /бгп). 4 >Г

В ходе доказательозга окекгл 6а,0,1г о^ягггда з жгжя е:-да. Нащшгф» з случае рашсвгернсто распрел^сггл » л

О ^ Д 1) оцет« глд

г„=£ . <*/•

■ я ял л

Т%<$ 11 7> 1 ,

В § 1,2 аойкагстачзсяц яочшй йсдход г.-

кошивоягара на кшяшуи, щяхбрсЕгкй позу^.гттйсс".; з время благодаря работал В.И,75з*еова н ОЛаггсягг

черпз = «юсотюльау» погрззйзс^?- пхсучзггззк?

средсгвом алгоригка решения„ н - х^&згеззш з'

точное значение целевой функция оадачя й&йЛЕэдаэра та

алгоритм "Ида в самый удалешшЗ яояроЙденгкЗ город% Жг. " класс задач кошавояаера на иакспиуи с эясяеетгма /г.х/1 -явгря*» цн (С;-) о выбираемыми случайно и взэаак&шэ друг ог друхв о одинаковой функцией распределения £ ), 4 ~(Сс-а,.) » Г < ^ 1 [24]. .

3

Тюоеаса I.S3 Алгоритм <А*асимптотически точен на классе

Ж ~

Jk = с(п) j eint jh

ж

Ч -Г tX3

/ - im

«Я® J*> ~JfZ Р($)

Б случае равномерного распределения ( О i) алгоритм классе вадач коммивояжера

Ба тксшуа асвжготическя точен.

Паяучвзш гакжэ условия асвдптотаческой точности алгоритма оГв случае распределения вида F(%)zk ^ i Jn = о(п) в вэде * f, С5 § i .' . Jn.

§ X.4 саавэдв ведаче отискащш гавдльтовова контура (цикла) ш вероятностном (либо неполном) п -вершинном ориентированной (Ееоркеютродпнкои) графе. В случае вероятностного xpagja ду~ т (ребро) каадой парой вершин rpatja появляется случайно и Еезашнш) о1? других пар с заданной вероятностью рп 0<рп< 1. Прн ©том щюйлештично само существование гашлътонова контура (цшоа) в случайно и графе» Наиболее точное пороговое значение Ма указанно® взроятности (или числа (ребер), начиная с которого в случайной веораекщрованном графе дочти всегда существе® гшилъкщоз дакла было получено А,Д,Коршуновым34/. В.А.Пере-йадкцеЗ сначала бил построен елгориты, который за время С(ч ) кочти Bosses гшждзт ззашльтонов контур (цикл) в случайном ipa-фо црз -t 0(1)) а затем автору совместно с

БФЛ«йзраз1здзщгй |*8] удалось достроить описываемый в.диссертации елгорати, таор^й за врама 0{пубгп) почта всегда находит га-юлкоыог iiCHtyp (цикл) при ph % (i + c<i\)( .Д'А-^. В настоящее щяш сто® алгоритм имеет .скорее иллюстративное значение, поскольку позже радом аарубеаных авторов dam построены алгоритма с улучшении?,да оценками качества (L&kxi, 1976; eh. thuiiuui and LAVä&ant , тъгЖ.Жахр, ievs). 0

Центральное место в данной диссертации занимают главы 2 и 3.

А.Д.Коршунов. Решение проблемы Эрдеша и Реньи о гамиль-тоновнх дадах в неориентированных графах // Методы дискретного анализа. - Новосибирск, 197?. - Вцд.31. - С. 17-5$,

Вторая глава посвящена та*одам psircins гзвзсгг-к г^ТДзр?« га&шх задач георяп расписаний; задача сегс-вого юшгдадкязз: s услошях охраничеших ресурсов к задана®* дорзг.ггг ^х opoion собыгяа,, одномерной задачг упаковки прокатов в я

двумерной задачи уцаковпп пржоутольпзкоз a üz-;ot>7*

Есть несколько sopóztz сбзороз я кояогрйСзй чю n*jv

нисзкяй (в чясж> огачестаягзых айюрог/*'} с -зз сц-г»,

что сЗфэктош»? хсчнке алгсрп'лтц удается ясстрсгет> в

nix-to очень частных случаях этих задач я dostr.-» «actiO ;гп гоева дало с /VP-трудшан «гюксая, Fssyvrsra^: гтеа: ocrr:*r¿' па рзбо-хах [lt- 13, 14,' 150 1Э, 23„ 24s 30, S-Sj. .

В §§ 2.2-2 „5 ясследуетея зэддча ссгспога в

условиях охраютзгашх ресурсов п гздакшх дярзю&гхгх созга?,

Пуоть задана сзтевая то &~(X,U} - бг^оэт^'И®^ гз оззагшшй граб (мульзяхраф), itis /V - кзсгеотво scp^í-cc^r^l« U - ияоаество jQTvpaíos. Ввдолгна пояжоззо?:» л

рекганных ссбгияй, для каадого яз нзх укаггш д^йгшшпй гте™-

и Хд11(3 (всп работа» гходтаа в звдэ&шши» собигнэ ЯГ должна бить заверяет? на асзякзэ ксколга

Чсраз Ж обозначал мпсззсгео огов pscypcc2e сззайЙл»* гашшх а пргаетэг - кновеагэд csrc® crssnrcjtrts rí-a'T.cor-, Л1ссЖ\ , ' .

Для кггдоЗ работа íigU ваджгзаг йэлн í/ei. • aminoro з концевого ообнтай ояой-работ«» сз »

a TOKES COr-rtyiX'iOCTB /7^ ЯрСйЯЛСЙ-5ГГЗр £?tJT'*í.-í

еоДаваеша: в ацдв

гдз ¿T - тип потребляемого-рзсурсз,, 5

т° сдшг начала дзйссетя Ж одокзз&ззд йсзз»

та начала внполнэншх работа а;

длительность нрофяля-зшзра'зг 5 • ±)(0< ± < . - функщпг йягейсявгггота яяргбявпя ресурсов профиля Ж в интервале [OrT¿PJ „что

•Л ~1 ...........'

Мпхалевяч В4С.„ Кукса AJÍ. Мзтодо посл^доштольаоЗ - ое--тишзацип в дискретных сетзвпх задачах оптзп.1ального'T;asin>;jfe®j-нкя ресурсов. — Я.: Наука» 1983, - 208 е.; Тятей В»С„Д úkvp-ба В.В. Введение в теорию расписаний. - М.: toyica¡, 2'}э с,

^(ij-O iva тф [О,T^] ).

Для кадйото ресурса i € Jll° считается заданным количество ¿35 ресурсове выделяемое в каздый год t " t.. ,Т; , где

ГТ7 ' "С t

/; - .уителькоогь интервала шшщрования с ограничением на ресурсы i -ю '/¿та» При Ь>Т- рзсуро i -го типа считаем неогра-шгегхша.

ПзройкйШЕК ватниками в задаче являются моменты iu начал рабе;- ite[r„ Совокупность 7 ~ f (и<£ С?) на-SiiESKCv'» допуетшу решением (расписанием), если выполняются. уЗДйВЗШ; . ^

с) Ссйдздг.с^ся мхиологая вщкищашя работ?

для любой пари работ U,V е U такой, что ;

6} Не нарушены директивные сроки

для. хобоь paöoiu и ¿U у которой уи=> ос, х е .

з) Имеющаяся в иалдачэа в каздый ыоыент' t , 7} ог-

разачшае ресурсов ьеМ° хватает для всех работ, выполняешь б данный ыомгнт,

Офорауларуеа освовнуго задачу сетевого планирования в усло-v-^ ограшчешшх ресурсов а заданных директивных сроков (задачу 2.1): ереда додустЕшх расписаний най-2» рйошэазаэ шдаашюй продолжительности:

Li'l) « Mix (tu *ти) min . .

'uel/- iq}

l^ZiB 2.J.* S0® ограниченные ресурсы складируемы, то для

зада® 2 Л ыаязэг бить пострсоно асимптотически точное расписание еа чглоло деЕсявай, зажеящее от числа работ п как функция С п Ссд^ 1г , гдо С не зависит с? П.

Цра этом оценка точности отыскания длины расписания ведет сабя как фуйодш €(п~1} ,

?а5с}.;аг;ситегся такае задача 2.1 с дополнительным критериев цшщт оушарной навязки меаду выд&яенкыш ресурсами (Ь1) (t - *, ♦*■* 5 7} , ¿<= и ресурсами, потребляемыми

при данном расписании.

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

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

При наличии ограничений ка рзеурен гата

для задачи 2Д построен алгоритм грудоемкосия V(>t Cft't, il) ft апостериорной оценкой tosHocsn о шшодаавашод s каж&до од*« ночного такого рссекля, которое получено а зкда-

дзруемости всех ограниченных ресурсов.

В § 2.6 изучаемся задача одномерной уттт; a ^Jtraetepa, которая закатается з размезегшя прздеэтез из списка Си ~ « (аЛ(1 в кивашаиов часто йоаггйкэроз sksssuhq-

стю В , Bb<Zt Задача 2Д шштзэяеетка задало

упаковка в контейнеры в случав поотояааой даягальяэста в пега*' шсицссти рабог сетевой мотеля» величина otpaisnssabw peejpea» равной в каждой год интерзала плапгр©вайия»я (»сугогвзга ограничений на дарйкташшэ сроют. Пря ого?.* шеншзацнк ургяет -вшой-шгоя совокупности работ сетевой модеяя 'рагаосшшза гзшшкаэдя* числа задействованних контейнеров» Несмотря т зтчтшздааоа fn-.рощение посгааовкк задачи» ш остался-в кяассо /VP «епудшег са-дачо Большая часть работ по утаясвйэ.а контейнеру огг.сстггоя . к разработка калотрудоклких щифшаенных штцш»?оз с хзракЕкрз-вагашия оценками точности. Наилучшим даш алгертецо» га оег-пд™ нетпй день является алторию FFD ц^згедага с

дочвняем по неБозрастшйш") с -ашягготгсдеоЗ сцзасгЛ ошуок-тельной ттгрешностя <5^= 2/9 (<* 22 %),

В диссертаций изучается одномерная задача ivss&sm в тейнерн (ЗУК) в случав В -асп.йтатрзчяюс ш B-vSTyxss&JZ prists— ределешй весов предметов е 2 I = i*-• >. ft' « Eyosa %qi(f) - число предметов веса Г в ¡списка 01 , гВ « функцшв ft* назовем В.-асиш^го^^сй СЗ-с:"?-

кетрзчной)'9'еоля f(r)4f(B-r) i f (г) у(Ъ-?') ) язя ляСго r-i,.. .,[B/z J и при , ^-згцга J-

будем называть В -регулярно» <при t> не лоз нэсграха-

тельное число), если она представит в виде 2К -езмиэгричнаг , функций f(Ki,

. ' . Q

¿m(r) > Г*1'-'-'8-

Ч,-й> Нзьоэрастазкцая .¿ункцдя ^(с), (при

В --) »"шляется В-регулярной.

П;10Е0;.К'Х£ я шиз алгоритма из работы Г19} автора ы ВЗ.йзлзйбогакох*^. ¿лгоршни ишет ¿швейную (прн В 5 С -ков-<шнта) гру'Доешюсгь»

Л'эашп 3 случае де?е$шшироваьных В -регулярных (В-ыдовгезргтаиг) еаасков 01 алгоритм находит точное решение ВЖ со гзнйчеккеи целевой функция В

если схшоок В -регулярен:;'

В

г. ^ И + • Й^Ж08 5 ^

Дж-з исследуется ЗУК со случайными описками 01 предметов, в которых гвоа нрздкетоа - независимые случайные величины с сггтаноэЕой дискретной рушащей распределения; • :

; • В

Г-Х

£032КЕСС2Г 6С20СТБЗННЫЙ ВОПРОС О ВОЗМОЖНОСТИ ПОСТрОЗШЯ Ш-

елгоритиов решения- ЗУК в случае функций распреде-декш, с&здаадх свойсгззаш» аналогична® тем, которые для де-сшоков позволили построить аффективный точный . Отвоз не трзшигав; поскольку соответствующее свс&из распределения Г- -I,-- <■> &) для хара-

фуйаща конкретной рза-

ДЕюадю! описка» вообще говоря» на сохраняется. В

д/юсэр-;;дйш рдосиатрив&етса класс Ж* ЗЖ со следующим ыехакиз-коа формования случайного сшска; в'ходе П последовательных' Еезашшш шштайиЙ очередной предает а£ попадает в один из весовых классов »1,,.., В в соответствии о функцией распрада^эьш (рг){ г = 1,. - <,В) „ Для решения задач из класса строится ■ кодн^цврованный щшЗлякенный алгоритм Л, , псподьеужцяй решение, полученное с помощью алгоритма Лх для н«-которого декршнировашого оценочного сшска 01 , .мажорирующего исходный список.

Теорема 2.4» Алгоритм яа классе ЕУК е В скхызг-ргавой функцией распределения (д.) ( г - ±,..,, Д!

В * о(п/бпп)

асимптотически точен с оценкгш?

6/г * Г1/{пп)г

Ч

Из теорем« следует справедливость утверждения да чть&ш случаев В -асимметричного распределения? В -ешцеертпгого, неубывающего,равномерного.

Л

Обозначим сСр - £ грг .

Теопет 2Т5. Алгоритм па класса задач 37К о 5 -регулярной функцией распределения (рг) (г~±г...,В)

Р>/Щр ~0(П /Спп) асимптотически точен с сцеякагя

Замечание. В случае ограничена* «аксшзлЕгэта ркзгзр.^ предмета величиной к < В » условия асимптотической «гз:сетя £дгэ~ ратма Л} на классе ВУК закештотся на «гпез »гаиив, Дкя В -асимметричных случайных списков асшгптотнчеакея гочгаогь алгоритма имеет место при

а для В -регулярных сгоскоа при В/Мг1 =» 0(Т1),

Я/оС(р) = 0(п/{ап),

¿' д

Г'*

О&о^Еогдавухщв оценки точности при отом имеют порядок ве-

**** а \nHfi п/*пп ) ]'

В гараграфз 2.7 изучается класс упаковки двумерных врздмзяоэ (прямоугольников} в полосу со следующей моделью фор-кзроЕанхй е^шДкого списка: на казной шаге в серии 11 незаш-содзх сспнгазсй очередной предаст й- „ щшшшает

звон разшрн - г.зе и длительность Т- в соответствии с да-зкреьнай ¿уиадмй распределения

Ргг~'Р{Г1 =Г>Г< жГ1 ' В,

. в т >

ЁХ рп-1-

' г"тс1 ■ ■ 7

Для репши: оодач из класса Лп описывается алгоритм Лг , осоэ-еядай в последовательном применении алгоритма Л1 к под спи-<йшы 017 , . .,Т. , лде. '£ЖГ состоит из предметов

даша т ; '(?£г <2 01 , т-^,.., Т.

Говори чго матрица обладает некоторым свойством, если ем обладает каздпй и-холбец матрицы. Обозначай

В Т

«Г-5т^гтргг. г-х т»*

ЙЗЁ.^Ягй'- Еола матрица(¡р^) , ¿-регулярна,- то при ВТ/зер - о(п/£ап)

и г?ау■:<•„:■■. прнзэдпт к асимптотически точному решению задачи

-ИЗ » ПОЛ 85; С"

^о(ШШ)'

В случае В -асимметричной матрицы ЭРр заменяется на ве-яэчаду /Т - отношение математического ожидания длительности - предав „'а к максимальной длине предмета.

При задании частичного порядка Ч на множестве двумерных предметов списка ОС рассматривается кл^с случайных

списков и строится алгоритм , для которого условия асимптотической точности имеют вид» аналогичный условиям .теоремы 2*6 .(с заменой произведения ВТшВТЛ, где Л- число классов эквивалентности, задаваемых частичпни порядком -< )0

Леша 2Л0. Задача из класса Ж* упаковки двумерных предметов в полосу является оценочной сверху для задачи календарного планирования 2.1 в случае постоянного по времена однотипного нескладируемого ограниченного ресурса, работ-прямоуголышков ' и отсутствия директивных событий (задачи 2Л').

Теорема 2.10. В случае В-регулярных случайных списков из класса ЗС* алгоритм Л* при

ВТА /зе <*о(п/'€пп) .

приводит к асимптотически точному решена» задачи. 2.1

Третья глава диссертации посвящена разработке методов решения задач размещения и выбора типаяа' оборудования (задачи стандартизации). Рассмотрение этих задач в рамках одной глава вызвано их единством в постановочном плане: в своей основе они содержат математическую модель так называемой простейшей задача размещения - ПЗР (или базовой задачи стацдартнзацЕШ - ЗС}8 одна .из компактных формулировок которой алеет вид;

Е ,<-}{ +Е т1%, ^ '

СеМ 1-еШ о-1 Ж'е Ж

хде ......

Эта задача в общем случае МР -трудна в сильном смысле ' и исследования ко ней в основном направлены на отыскание полиномиально и пс евдополиноииально разрешимых частных случаев, построение малотрудоемких приближенных алгоритмов с апостериорными оценками качества решения и развитие техники алгоритм в неявного перебора. Наибольший вклад в эти исследования принадлежит отечественным авторам (ВД.Вересаев, диссертант, В.Т.Дементьев, В.С.Михалевич, В.А.Трубин, Н.З.Шор, А Д.Агеев, М.М.Беркович.» Н.Й.Глебов, В.П.Гршцухин» Б.МД'ольденгоркн, Ю.В.Чуев» В.]1.Чере-ейн, В.Р.Хачатуров и др.). Достижения зарубе~ннх авторов по ПЗР освещены в большом обзоре3^, в хутором приведены результаты

Кгагир Т., Ргигап Р.М. №е в±тр1в 1оса1;1оо ргоЪ-

1ет - шгуеу ап<3 вуп-ЬЬ^в // Еигор, J* Орвз?. Нее. - 1993» -V. 12, - Г 1. - Р. 36-81,

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

Результаты,принадлежащие автору диссертации, содержатся в работах ¡V?» 10, 14» 15, 17, 18 , 20-22 , 24 , 26-29 , 31-35], Перейдем к ш мадожерзр.

8 щредрафе 3.2 приводятся результаты по задаче размещения Точек на 0?резке (цепи), представамой в виде задачи о ближайшем со<Щ0 (ЗШ)! м

- О".т0-< хт - п. ;

■I «' т с N ,

г *

Дед этой задачи применима стандартная схема динамического проградаированвд, »В случае,, когда для функции / соблюдается

тек дазыщямое условие Глебова (аналог супермодулярности):

,^ ) - , «<>

для .любых 1* удается доказать спра-

ЕШЖВйэд шярро реда свойств оптимальных решений ЗБС, позволивших (оувдеотвеяко улучшить оценки качества точных алгоритмов

редевда.щ;,,

Р даратрафе 3,3 рассматривается задача размещения ад адак-яичесвда <оети С - (21,£), Ж - {!,•"■>- множество вершин (пунктов ¡ссроса)0 £ = £ек/кк< - множество ребер Задано такае щожеощвоЩ ~ {!,.. возмогших пунктов производства однородного продукта. Исходными данными являются вектор (д?)(1 £ Щ.) затрат на размещение щ>едщшятия в пунктах с еШ* «шриа 1 б Ш, I е Л) затрат на доставку - единили щрадгнуа из пункта производства с в пункт спроса у , с е Ш и вектор (</?•) (/ с объемов спроса; ^г? е Сц 0 у?« - неотрицательны,, Полагая - р- Су , мы имеем вадачу в ище ДЗР„ В.А.Трубинш да случая задачи размещения на ациклической «еети при Ш~Ж построен алгоритм трудоемкостью 0(п3) в я^редполокешш;, что ^¿у попарно различны для любых ^ и равны сумме длин ребер сети, входящих в цепь, соединяющую вершины с и у ( ^) .В диссертации описывается

алгоритм, имеющий трудоемкость 0{¡un) (или 0(пг) при дК^Ж ) при более общих предположениях на матрицу (CjL¡) . Для описания' алгоритма вводится специальная (сегментная) йумерация Езршин сети» реализуемая за 0(ii) действий. Решение исходной задачи осуществляется сведением ее к некоторой оценочной задаче, для которой построена рекуррентные соотношения, используемые з ходе работы алгоритма» Доказано существование оптимального решения т совокупностью связ1шх. областей обслуживания на ациклических сетях, в которых для любой пари,пунктов размещения УЗЬ найдется такое разбнекяз {'Ли>, nu>¡ вершн сети & „ что

денные множествами вершин 71<к) - связные.

В следующем параграфе рассматривается простейшая задача размещения на сети = ('Л, £) 0 вообще говоря3 не являющейся ациклической а случае Ш сг Ж „ Предполагаются заданными неотрицательные длины рэбер сети, с помощью которых могут быть определены кратчайшие цени меяду вершками сети. Вводится iwiacc Ц -ьатрйц (</,у) „ для которых нз CJ¡¿ < gK¿ при к Jé Щ. , je Ж следует Д®1 любой веришш Jsfil » принад-

лежащей кратчайшей цепи из i з i . Показано, что для задача размещения на сети G- с ¿(-матрицей существует оп^шаль-

ноэ решение с совокупностью центрально-связних областей обслуживания а когда каздый размещаемый пункт оказывается принадлена-К5ш своей области обслуживания. Назовем основой сета С некоторый максимальный связный подграф Pe Q, , ш одно ребро которого на принадлежит никакому циклу сети G- <> D -квазиблоко?! сета назовем максииалышй циклический подграф сети 6- „ точки сочленения которого не принадлежат основа D этой сета» Одна зз вершин основы Р берется в качестве корневой,.Квазнблок сети называем псеадодревеснш» если подграф породденнчй шаяеством вершин квазиблока (за вычетом бляжаШяей к корневой),, является ациклическим.

Теорема 3.12. В случае сети содержащей только псевдодревесные кваэиблокн, ПНР с Ц-матрицей монет-быть решена с помощью алгоригма, имеющего трудоемкость 0(шгп + п) действий t гае p = ¡E¡-

Кваздблок назовем логарифмически ограниченным» если количество содержащиеся в нем возможных пунктов производства не превышает W .

Теорема 3.13, В случае сети G , содержащей только логаршЪ-шчески ограшчэщи® кзааабдакв» точное решшга ПЗР о Ц -матрицей (дф тжоъ бы»ь аодучэво sa Oivui1) действий,

В § 3.5 рассматриваема математическая постановка базовой кодела с«аадарздазадан (SG)a которая, как было сказано, мойет быть сфорзужкрощна в одном из видов ПЗР;

Z jï +L $и >

ЫМ Je31 сёШ 04 Ш*с.т

1яе ffît** {i,..->inj - множество„ соотввтствуадее перечив типов Ездедшй$ v

71 ~ {s ,п} - щоааотво, соотЕетстауадее совокушостз видов спроса;

Çy- - затраты« связанные с обслуживанием спроса j -го ш-да с помета» изделий I -го згвпа ( I 6 Щ, /е Ж) . . $ Ш" ~ набор нзделнй» вводшйс в действие, В общем случае (д-)<= гик сфораулиро-

ШЕНой задачи будем «cœœasoBatï»'обозначение S0js а при допол-вдгелшом ограничении

Im'i < /V

нсшдьзуеи обозначена® SCj-2 { ограничение сверху на количество ïhhob взодаых s действие изделий),

30. с кзотрщателдаш исхадныш дашзшн обозначаем через

Dfrfr

OU Q

Легко показывается, чго SCj сводится к решению BSj, чего -нельзя сказать о SCT-,g„ В § 3.6 рассматриваются так называемые • связные SC (СЗЗ)» Uàïpnuy {вф называем связной, если для дабой нары строк i,K (1 il <■ Kim) матрицы разность Çji■ -mesîes знак при монотонном измшоккй индекса ¿,..ft на боке® одного раза.

Теорема 3,14. Найдется оптимальное pt 1еше СЗС с совокупностью связных областей обслуя, зания.

Приводятся рекуррентные соотношения, позволяющие подучить «точное решение CXj^fT <9(М,»я/г) „ a CBCj рететсЛа^т«) алго: :тмом5 описанным для задачи размещения на ациклической сеет о ■

Сведением C3Cj-k некоторой СЗС| получаем алгоритм решения C3Gj той se трудоемкости. Для СЗС|_2 такса сведение осуществить не удается а приходится обосновывать специальный алгоритм решения C3Cj_2,

Пусть N) - совокупность связних областей

использования изделий; Mi = (jK_i, jK] f /<=!,».0-* j0 i i i3 ^ • - • £ П » Решение K77l,^{in)(K-iy..,M)i N$N0 « назовем согласовании« с совокупностью {'Л/ I ..<■>№) • связных

областей обслуживания (шш0 корбче, согласовашо-связшш), если ¿^ < ... < ¿w - „

Теорема 3,15. Существует согласованно-связное оптимальное решение C3Cj_2„

Утверждение позволяет подучить рекуррентный соотношения и построить алгоритм решения CàCj^»

Теорема 3.17. CSG^ MCœe- бить решена за число действий <~ m/i ( N0 f icat m) „ либо за ~ п +г) 0 если Û-, -целы а, о 4 ie Я). ' ■

В §§ 3;7„ 3.8 исследуется SC с квазивдауюшш^ патрицами ■ (КЗС) » Матрицу я SC называют квазивыпуклой (квазавогнутой),,есла соответствующее свойство иуеез,. место для каждого столбца матрицы: для всяких L11 , ij из 7TL ,f i t, ^/jit^OT» справедливо:

fo < ' СА;} ( Ьг] > Ш>г (р.) >рл)}) •

В.Л.Береснев, используя представление КЗС* в виде задачи минимизации так называемого правильного полинома от булевых переменных, осуществил сведение последней й СЗС*. Это позволяет построить алгоритмы решения-КШ| я KSCj^ р оценками ^ m (л+т) а ~ иг (п+ Ntm) соответственно. В дассертащя используется более перспективная для КЗС сводимость к ЗБС (см. § 3.2)„ в в которой выполнено условие Глебова.

Теорема 3.20. Решбнпе КЗС можно получить за вреш *>т(п+т) в случае SSGj и за время ^ m ( п + т + Мд m) в случае

В § 3.9 рассматриваются более широка» класса S3, полиномиально разрешимые путем сводимости их к последезательности KSC.

Пусть ( с[) ( L - i%... •, ni) - упорядоченная по неубыванию по, следовательность элементов j -го сголбца матрицы I £ /е il) ; I a.- ? с} - лебегово множество точек целочисленного сегмента [ t, ы ], в которых элемента j -го столбца матрица (^ф

• <т

не меньше С.„ где С е с / = !■,■•■ >'ъ • Кс&шо-'

пенту связности лебегова шязодва. {ffijZ ¡¡(--¿у,171 *

назовем внутренней» если она,- нз содержит его крайние точка »Матрицу {fj¡j ) s назовем квазивупуклой справа (слева) с если ыакспмальная (минимальная)? хочха дабой внутренней коипонеъты связности <EKG > 0 принадлежащей- некоторому лебегову множеству { g¿- z C¡\ t совладает с каксяаашюй

.(шнкмальной") точкой егого щояес.теа. ' v

Теорема 3„2I, 80 с кваздшсукяой справа матрицей [Cj^J сво-дасся. к решении последовательности nt КЗО о матрицам ■ ш* \ (¿»i,-> п) с к- „ где fij-inílllfij ; ¿У).

Отсада сдедуек0 что ододвк времени репелия 30 о кзазпш-щрэдвзд справа (ияв слева,} ¡гздргщйа утзеаготваятся в'т. раз по сравнении, с КЗС„

Частный случаен ятзшсржоЗ справа Силе слева) ' являются вдазквагнутад учет спедпйкки зтой»зздачд позвэ-jssss- шкуч^гь. бола© экокоишз оцешя. •

■ У^ореьа 3.22» Ксознвогнутей 33 ибада* быть рзшзна за время ~ K№(Kt*my йсдрас: Sjj ж й за зфвыя ~ tn(n + tnN$) в

случае . . . '

изярдщ- е 53: щз,овам ос!о^щ2нпо-квазлвшчгккоа0 если лэбоо лаб.егоао. тштъ о ¿-¿,..'.,«1 . j*>j}...,n. t со-

ctoes s© более чем из двух компоя$кг связности.

Теорема 3,23а Обой&ешо-хсшзившукяая 35 сводится к рзшз-шш последовательности КЗС с матрицаж (%{/')(* j е el) , т „ где - №П 'fc?^; ^ ; .

При этом од&жк рреазет решзшш увеличиваются на бокее чей в гпг по сравнению о К53» Оценки требуемой памяти остаются тгсг ss0 чгс е для K2Gtt

Класс обобщеннс^ЕШЗиадцукдых SC ,йшнает в себя классы КВ00 квгзивппуклцх справа (слева) 30'и квазивогнутых 20.

В § ЗДО ошснбшотсе приближенный подход к решению ЗСт с апосхериоргой оценкой еочноотй к применение ~хечы неявного перебора. е использованием кэгдай оц-нкк к величине целевой функции ЗС„ представленной в щдэ задачи целочисленного, программирования» В качестве нишей оценки используется двойственная задача к входной при условии снятия ограничения на целочислек-ноеть переменных;

п.

2 1». *пах ; У" '

Г*

Решение (назовем тупиковым, если дай всякого столбца ¿€ТС матрицы найдется такой элемент ^^ , что для

е -ой строки выполнено ^Г(гу- «.

Тупиковое решение обладает определенным преимуществом перед решениями вида 1} = <?(/ » где ^¿эО „ ,

^ ^ 1 , поскольку последние на могут дать лучшую оценку, чем Тупиковое решение. Понятие тупикового решения позволяет построить алгоритм с апостериорной оценкой точности» Трудоемкость алгоритма С(тгп) „ Кроме того, метод построения тупикового решения является основой вычисления нижних' и верхних оценок на множествах продолжений частичных решений э методе ветвей и границ как в точном так а приближенном вариантах его реализации» В случае предварительного упорядочения элементов кагдого столбца матрицы по неубывании, верхние оценки вычисляются за время ~ пг (п-г т) »

§ 3.11 посвящен вероятностному анализу малотрудоемкого, алгоритма решения задач класса ЗС| (определяемых случайным выбором элементов вектора и матрицы (<]ф(7=/,... ,/п.,уп) соответственно из числовых интервалов [А* > 8°] и К,ДЛ , При атом элементы матрицы » независимые одинаково распределенные лучайныа величины с функцией распределения Р величины | ~С1,Ь)/ У(6,~С1Л)>■" удовлетворяющей условии Р(%)* | , , Дня решения 30| построен приближенный алгоритм X* шешдай емкость 0(иг), V = мах {т;а / ^ д

Теорема 3.34. Алгоритм Ж решения зада*"* ЗС^ (й^ёл^Ф*

О, асимптотически точен, е~ли (Ъг «п.)= В°/а11*о(п/-1сд1п).

На подклассе ЭС1С 30| о равномерным распределением случайных величин £ - ал)/\0(,Ц

и с параметрами т. = 0(11*), А°? % Ьи^п/гь „где 1 -константа, X * I , ^ О(ч) , £йп У* = <*=> » алгоритм Т с

вероятностью, стршлязейся к -I при я-*-^ „ даот ресзкие с оценками Ьг- , $? , асимптотически рашнки 1/1 и О при соп „

В ■четвертой главо обсукдаются некоторые прикладные аспекты и обобщения задач» Более подробно затрагиваются вопросы, связанные с задачей сетевого планирования крупномасштабного проекта в условиях задания сяраютешгй на ресурсы и директивные сроки, В § 4.2 приводится общее описание'программного комплекса под обида названием "СИБИРЬ"«. В § 4.3 предлагается компактная к уикфццирог вашая форма задания информации о фактических работах сетевой модели. Возникавшая ЩЩ ода? задача выбора так называемого базового множества, нормализованных фунгащй, описывавших динамику1потребления ресурсови сказалась связанной с задачей стандартизации о дополнительным условие« лилейного вида. В § 4.4 обсуздаетсл шохшодуташй щттщп ооотрооаш сотовой модели» пр:; котором процесс развития комплекса рабог, входящих в цроокт, требует использования, некоторого набора стандарт сх типовых графиков Ого-дулой). Этот принцип сочетается с блочным строенном сетевой модели 8 где под блоками в случае задач хозяйственного освоения зоны ШI и развития ЗСНГК понимается »рррцторгакьпо-цроаналещца комплексы (промдалсшшэ узлы) либо их совокупности (зот.,.

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

сформулированы выгоды, обещающие результаты' диссертационной работа. .

Автор выразает искреннюю признательность коллективу отдела теорет- юской кибернетики Ш СО АН СССР {а особенно коллегам по лаборатории дискретных экстремальных задач) за постоянное внимание к поддержку при выполнении данной работы.

Список научных трудов по тепе днесертащш:

I. Алексеев АЛ.. Гилади ЭД„, Перепелица В,.., Математические модели календарного плаякронакая и управления долгосрочны-?,ш ярсектаьш (на примере БАМ) // Проблемы строительства магистрали и развития строительной база для хозяйственного осваекая зоны ЕШ. - Новосибирск,, 1977. - (Материалы П Всей. конф. по проблемам хозяйственного освоения зоны ВАМ. ~ Благовещенск» 1177). - С, 113-126,

Берескев В Д.. Гишдз ЭЛ., Дементьев ВЛ. Экстремальные задачи стандартизации., *» Новосибирск; Наука5 2978» - 333 с.

3. Кшздутдинов 3.1, 0 свойствах решений одной задача оптимального размещения точек на отрезке // Управляемые систе;га,-Новосибкрск, 1369. - Вып. 2„ ~ С. 77-91 „

4. Гимадн ЭЛ. (Вшадутднков). Выбор оптимальных шкал в одно!,} классе задач топа размещения, упифшщия и стандартизация .// Управляемые системы, ~ Новосибирск., 1370, - Вцп, 6.-С.57-70.

5. Гимадн Э..Х., Глебов,.Н.11а Об одном класса задач ■ таза стандартизации. унификация я размещения // Тезисы докладов П-сЗ Всес. конф. по проблемам теоретической кибернетика. - Новосибирск, 1971. - С. 23-30.

6. Гимади 3 Л», Дементьев Б.Т£ О методах решения некоторых

. задач оптимизации параметрических рядов // Стандарты а качество. - 1971. - » 12. - С. 10^12." .

Т^.тздзгЭД.^ Дементьев В,Т. Некоторые задачи выбора оптимальных параметрическая' рядов и ыетодц жх решения (задача стандартизации) // Проблемхышбернеотш. - 1973» - Вып. 27. -С. 19-32,

8. Гжлади. ЭД,.,. Перепелица В.А. Статистически эффективный алгоритм выделения гашльтонова контура (Цикла) // Дискретный анализ. - Новосибирск* 1973» - Вшт» 22« - С» 15-28.

• Гишди ЭЛ., Глебов НЛ!,.«. .Варедедша; ВД. Исследования по теорий расписаний //, Управляемые системы. ~ Новосибирск, 1974. - Вып. 12. - С. 3-10.

ю. Гго.тадя Э Д.... Глебов Н.И,,, Дементьев ВЛ. Об одном методе построения нижней оденет и приближенного решения о апостериорной оценкой точности для задачи стандартизации // Уярзвля-

емые системы. - Новосибирск, 1974. - Вцп. 13. - С. 26-31.

Il» Гимадл ЭЛ.. Перепелица В.А. Асимптотически точный подход к решеют задачи коммивояжера — Управляемые систем«. - Новосибирск» Ш4» - Был, 12. - С. 3&-45.

Х2ч ГКиади 3 Д. » Глебов И.И,. Перепедида В.А. Алгоритмы .с опешат для задач дискретной oirnaa задан // Проблемы кибернетики, - 1975. - Вып. 31. - С» 35-42,

13. Ги?лади Сетзвах В.ВМ Сокольская Î.H. Программа построения календарного гошна-графика строительства БАМ-// Пробле-101 строительства магистрали н развитая строительной базы.для хозяйственного освоения зоны БАМ. - Новосибирск, 1977. - (Матери-ада 2-й' Бсес. конф. до проблемам хозяйственного освоения зоны БАМ. - Благовещенск, 1977). - С, 127-133.

14, Римади "ЭЛ.. Пузшжна Н.МГ, Севастьянов С.В» 0 некоторых экстремальных задачах реализации круяйых проектов типа БАМ // Экономика Ж математические методы» - 1979. - Вып. 5„ - С. ïûI7~ÎQ2£>e

Î5/» фздд.ЗА* Н.И. Экстремальные задачи принятия

решений. ~ Новосибирск-, Новосибарсетй ун-т,, 1982«, - 80 с,

16„ Ттш1,,Пузынина Н.1Л. Бг-ача календарного планирования крушдаасЕаабного проекта в услошях ограниченных ресурсов; mm яэедроещя математического обеспечения // Экстремальные задача аоакедошшя операций (Управляемые системы). -HosoeaâgpOKo - 23. -'С.24-32в

I?» I^jgjg^SjX в Эффективный алгоритм реиенкя задачи размещения о областями ®бслузшвавдя5 связны® относительно адапточе-ской сети задачи исследования операций (Управ-

ляеше системы)» «. Новосибирск» 1983. - Вып. 23. - С. 12-230

18« Задача размещения на сети с центрально-

связными областяда еващщт&т // Ди кретные экстремальные за-,дачй (Управляемые ояотемы), - Новосибирск» 1984» - Вып. 25. -С. 32-47.

19, Ги?.ади Э.Х», Залюбовский В.В. Асимптотически «очный подход к решению одномерной задач" упаковки в контейнеры' // Дискретные экстремальные задачи (Управляемые систолы). - Новоси-

,бирск, 1984,Sua. « С, 48-57. .

20. ГшадиЭД. Обоснование априорных оценок качества приближьнного решения задачи стандартизации // Методы целочисленной оптимизации (Управляемые системы), - Новосибирск, 1986.-

Виц. 27. - С, 12-27»

21. Гнмади ЭЛ.. Кисельников A.A., НаГщанов A.B., Яши-лов Ц.-Д.Я, Оптимизация развитая п. размещения баз »материально-технического снабжения а зоне БАМ // Сборник научнчх трудов: Комплексное развитие зонн ВАМ» - Новосибирск,» Институт экономика и Оргшшзацшт промышленного производства СО All СССР, 1985„■ -С. I4I-I53. .

22. Гимади ЭЛ.. Дондопов 3,Б.„.Киселъников A.A.. Майданов А.В» Моделирование -развития транспортной сети и баз материально-технического снабжения в районе нового освоения // Совершенствование разработки планов развития отраслевых комплексов«-Новосибирск: Наука». 1987. - С* 170-194«,

23в Гиыадй ЭЛ.„ Гончаров E.H., Залгобовский В.В. Алгоритм решения задачи в условиях ограниченных ресурсов а директивных сроков // В raus Перспективное плшшроватате Западно-Сибирского нефтегазового комплекса. - Новосибирск: НаукаD 1987, -ОЛ72-180.

24• Гетлэди ЭЛ. 0 некоторых математических моделях и методах планирования крушомасптабдых проектов // Модели и методы оптимизации. - Новосибирск: Наука, 1988. - (Тр./АН СССР." .Скб„ отд-mie. Нн-т математики; T« 10)» - С. 89-115»

25. Перепелица В.А., Тимадй 3.Х< К Задаче нахождения минимального гамнльтонова контура на графе со извещенными дуга;,и Ц - Дискретный анализ о - Новосибирск, 1969» - Вып. 15, - С„ 57-65.

26. Разработка типовой метотаки оптимизации параметрического (типорззмерного) ряда,» Кглга 2. Обоснование методов оптимизации // Отчет ЗШЖтандартпЭацщг Госстандарта СССР и Ин-та математики СО АН СССР. (В„В,Ткаченкое С.Л.Соболев,, В.Т.Дементьев, ЭЛ.Гиыада, Д.У.Комаров), - М„;-БШИС Госстандарта, 1972» -89 с.

27. Рекомендатош по оптимизации многомерных napg етрпчес-ких рядов // М.: ВШШСтандартизацвд Гостандарта й Ин-в математики СО АН СССР, 1973в - 81 C«

28. Типовая методика, .опттгазацт! шогомер'ных параметрзчес-. ких рядов // U.: Госстандарт, 1975. - 43 с.

29. Типовая методика оптимизации одномерного параметрического <типоразм8Рного^ тшца // М» ; Госстандарт, 1975» - 64 с»

30. Разработка математического я программного обеспечения ffliH задачи планирования Западно-Сибирского нейтегазового комп-

'яокса, I и П // Отчет Ин-та математики СО АН СССР (научный ру-

ковбдитаяь Э.Х.Гимада). - Новосибирск, 1985. - 90 о.

31., Еимадгишнов ЗД. Об одном классе вадач нелинейного програшзроваяия; // Управляемые системы» - Новосибирск, 1969. -

Выл» з„ - шь-нз.

32„ Дйиадю Задача стандартизации о дакяымя произвольного знака- вг свйаннм£к квазывыпуклыми и почти квазивывуг-иги иагрицаш; //Методы; целочисленной оптимизации {Управляемые скс-- Новосибирск,, 198?о - Вып. 2?, - С. 3-11.

' Б&аашвзг Oimsfiy Sen gsaeyAiay Же Зшэ Eoñele of Se« Шш® оа^йшШ. (BrofeioE© // Шой&1Ищ esí O^tiEisaUoa ©£ Cosplox

S<®« С&аяйй ВЛШуч.'gleliwr f >g<> Sos® proSüeao

of ahelee. o£ ©gSinaü essdsa ü&S ttea E®teodo ot thsi:?

colefcica // Х1-ш$ Sp^osiea ca oS «o

StuoáiasfSiesStete- « ©asacad «S?2o - .

$S» glacd& Botau Ой-аэа» c3tlislcaS¿oa юроЗйеаз of larg рго^оейз tsüüS сff fi&stpas^s. 1Ш* CosfejíeEse са optld* ciUoa Secbíügüeso. «? Эагтшвго ШЯо > .