Задача о лесах на графах и гиперграфах и ее приложение тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Шапошникова, Ольга Ивановна

• Шапошникова, Ольга Ивановна
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Шапошникова, Ольга Ивановна

ВВЕДЕНИЕ.

Глава 1. ТЕОРЕТИКО-ГРАФОВАЯ МОДЕЛЬ ЗАДАЧИ ПРОЕКТИРОВАНИЯ ОРОСИТЕЛЬНЫХ СЕТЕЙ И ОЦЕНКИ ЕЕ СЛОЖНОСТИ

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

1.2. Общая постановка векторной задачи об остовных деревьях.

1.2.1. Топологические критерии оптимизации векторных задач об остовных деревьях.

1.3. Оценка вычислительной сложности задачи об остовных деревьях

Глава 2. АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ ВЕКТОРНОЙ ЗАДАЧИ ОБ ОСТОВНЫХ ДЕРЕВЬЯХ.

2.1. Математическая постановка проблемы.

2.2. Описание алгоритма аъ

2.3. Вероятностный анализ алгоритма аъ.

2.4. Вероятностный анализ применения алгоритма а2 к множеству M(n,R,Ä).

2.5. Статистически эффективный алгоритм а

2.6. Обоснование условий статистической эффективности алгоритма а

Глава 3. ИНТЕРВАЛЬНЫЕ ЗАДАЧИ ОБ ОСТОВНЫХ ДЕРЕВЬЯХ И ИХ НЕРАЗРЕШИМОСТЬ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙНОЙ СВЕРТКИ.

3.1. Отображение неопределенности значений параметров моделей средствами интервальной математики.

3.2. Сведение интервальной задачи к задаче многокритериальной оптимизации

3.3. Неразрешимость интервальных задач с помощью алгоритма линейной свертки.

Глава 4. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЙ КЛАСС ЗАДАЧ ОБ ОСТОВНЫХ ДЕРЕВЬЯХ С ТОПОЛОГИЧЕСКИМ КРИТЕРИЕМ

4.1. Математическая постановка задачи об остовных деревьях.

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

4.3. Полиномиальная разрешимость 2-критериальных задач, в которых один критерий является топологическим.

Глава 5. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ВОДОПОЛЬЗОВАНИЯ НА ГИПЕРГРАФАХ С ИНТЕРВАЛЬНЫМИ ДАННЫМИ

5.1. Основные определения теории гиперграфов.

5.2. Математическая постановка задачи.

5.3. Сведение задачи с интервальными данными к многокритериальной задачи

5.4. Сведение задачи на гиперграфе к задаче на графе.

5.5. Оценки вычислительной сложности исследуемых задач.

5.6. Полиномиально разрешимые постановки.

5.7. Исследование «задачи 3».

5.8. Иллюстративный пример решения конкретной 2-критериальной задачи водопользования.

Введение диссертации (часть автореферата) на тему «Задача о лесах на графах и гиперграфах и ее приложение»

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

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

Частным случаем задачи о лесах является задача об остовных деревьях [23]. Деревья представляют структуры, которые весьма часто используются в процессе математического моделирования дискретных процессов и систем. В качестве предмета исследования такого рода в настоящей работе рассматривается оптимизационная задача, получившая название закрытая оросительная система (ЗОС) [43,46]. ЗОС обеспечивает благоприятный для вызревания сельскохозяйственных культур водно-солевой режим на орошаемой территории с помощью дождевания из оросителей.

На протяжении последнего двадцатилетия в НИИ ПММ Кабардино-Балкарского государственного университета и НИИ прикладной математики и автоматизации Кабардино-Балкарского научного центра РАН создавалась система автоматизированного проектирования (САПР) оросительных систем и систем магистральных водопроводов для сельскохозяйственного водоснабжения [3,33,42,43,46,50,68,69].

Практически реализованный эвристический алгоритм решения оптимизационной задачи ЗОС доведен до реальных расчетов на конкретных исходных данных колхозов «Волчьи ворота», «Заря», «Родина» Ставропольского края в составе конкретной САПР. Указанная САПР осуществляет проектирование технической части ЗОС, состоящей из сети трубопроводов, служащих для транспорта воды от места водозабора к гидрантам систем, дождевальных установок, подключаемых к гидрантам и предназначенных для полива территории орошения, и насосной станции (НС), осуществляющей забор и нагнетание требуемого расхода воды с необходимым напором через трубопроводную сеть в оросители [67-69].

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

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

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

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

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

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

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

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

В связи с этим задачи исследования состоят в следующем:

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

2. Исследовать оптимизационные и многокритериальные постановки задачи водопользования, как задачи ЗОС.

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

4. Показать, что интервальная задача ЗОС с критерием МШБЦМ и степенью дерева к=3 неразрешима с помощью известного метода линейной свертки критериев.

5. Построить точные полиномиальные алгоритмы нахождения ПМА для 2-критериальной задачи об остовных деревьях с топологическим критерием.

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

Научная новизна работы заключается в следующих аспектах:

1. Предложен многокритериальный подход к разработке математических моделей для проектирования ЗОС и задачи водопользования.

2. При построении медико-эколого-экономико-математических моделей задачи водопользования и задачи ЗОС наряду с методами теории графов впервые использован математический аппарат теории гиперграфов.

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

4. Обоснована неразрешимость с помощью алгоритмов линейной свертки интервальных задач об остовных деревьях с критерием вида МШБЦМ и топологическим критерием степени дерева.

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

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

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

Основные положения, выносимые на защиту:

1. Построены малотрудоемкие приближенные алгоритмы нахождения такого решения задачи ЗОС, которое представляется остовным деревом степени 3.

2. Доказана неразрешимость алгоритмами линейной свертки задачи закрытой оросительной системы, представляемой остовным деревом степени 3, если веса заданы интервалами.

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

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

Апробация работы. Основные результаты работы обсуждались на заседаниях научно-методического семинара кафедры прикладной математики (КЧГТИ, г. Черкесск, 1999-2002г.), на научно-практических конференциях аспирантов и студентов (КЧГТИ, г.Черкесск, 1999-2002гг.), на СевероКавказских научных конференциях аспирантов и молодых ученых «Перспектива - 2001» (КБГУ, г. Нальчик, 2001г.), на III и IV Всероссийском симпозиуме «математическое моделирование и компьютерные технологии» (КИ-ЭП, г. Кисловодск, 1999-2000гг.), на Всероссийской научной конференции «Математическое моделирование в научных исследованиях» (СГУ, г. Ставрополь, 2000г.).

Реализация результатов исследования. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00-01-00652 «Математическое моделирование структуры слабоформализованных систем в условиях неопределенности».

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Шапошникова, Ольга Ивановна

ЗАКЛЮЧЕНИЕ

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

2. Построен асимптотически точный алгоритм для 2-критериальной задачи об остовных деревьях с топологическим критерием степени дерева равной 3. Сформулированы достаточные условия асимптотической точности данного алгоритма, что выполнено впервые для задачи с топологическими критериями.

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

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

5. Представлена математическая модель задачи водопользования на гиперграфах с интервальными данными. Исследована вычислительная сложность данной задачи и приведены полиномиально разрешимые постановки.

Список литературы диссертационного исследования кандидат физико-математических наук Шапошникова, Ольга Ивановна, 2003 год

1. Абрамов H.H. Водоснабжение.- М.: Стройиздат, 1982.-440с.

2. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.-360с.

3. Аттаев А.Х. Задача оптимальной трассировки трубопроводной сети. В сб. науч. трудов САПР и АСПР в мелиорации.- Нальчик, КБГУ, 1983.

4. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгорит-мов.-М.: Мир, 1979.-536с.

5. Брейтон Р.К., Хетчел Г.Д., Санджовани-Витентелли А. Обзор методов оптимального проектирования интегральных схем. ЛГИ-ИЗР. 1981.-Т.69, № 10.-С. 180-215.

6. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов.-М.: Наука, 1986.-544с.

7. Веселов Ю.С., Лавров И.С., Рукобратский Н.И. Водоочистное оборудование: конструирование и использование. -Л., 1985.

8. Волконский В.А., Еганян Т.К., Поманский А.Б. О множестве эффективных точек в линейных многокритериальных задачах // Сиб. Матем. Журн. 1983. 24 №2. С. 9-17.

9. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. Изд-во МЭИ, Москва, изд-во Техника, София, 1989.

10. Гимади Э.Х. О некоторых полиномиально разрешимых случаях простейшей задачи размещения. Информационный бюллетень Ассоциации математического программирования. Вып. 5. Екатеринбург: УрО РАН, 1995. - С.66-67.

11. Гимади Э.Х., Глебов И.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики.- М.: Наука, 1975.- Вып.31.- С.35-42.

12. Гимади Э.Х., Перепелица В.А. О статистически эффективном подходе к решению задач комбинаторного типа. Труды II Всесоюзного семинара покомбинаторной математике.- 42.-Науч. Совет «Кибернетика», 1975.-С. 715.

13. Гирлих Э., Ковалев М.М., Кравцов М.К., Янушкевич O.A. Условия разрешимости векторных задач с помощью линейной свертки критериев // Кибернетика и системный анализ. 1999. № 1.-С. 81-95.

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

15. Гнеденко Б.В. Курс теории вероятностей.- М.: Наука, 1969.

16. Глебов Н.И., Перепелица В.А. О верхней и нижней оценке для одной задачи теории расписаний. В сб. Исследования по кибернетике.-М.: Сов. радио, 1970.-С.З-18.

17. Гимади Э.Х., Перепелица В.А. Статистически эффективный алгоритм выделения гамильтонова контура (цикла)// Дискретный анализ.-Вып.22.-Новосибирск : ИМ СО АН СССР, 1073.-С.15-28.

18. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Исследования по теории расписаний // Управляемые системы.-Вып.12.-Новосибирск: ИМ СО АН СССР, 1974.-С.З-12.

19. Гимади Э.Х., Перепелица В.А. О статистически эффективном подходе к нахождению экстремума функции, заданной на множестве перестановок. Материалы I Всесоюзной конференции по исследованию операций.- ИМ АН БССР, 1975.- С. 46-50.

20. Ежов И.И., Скороходов A.B., Ядренко М.И. Элементы комбинаторики.-М.: Наука, 1977.-80с.

21. Емеличев В.А., Кравцов М.К., Янушкевич O.A. Разрешимость векторной траекторной задачи на «узкие места» с помощью алгоритма линейной свертки // Доклады Академии наук Беларуси. 1996. 40 № 4.-С. 29-33.

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

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

24. Емеличев В.А., Перепелица В.А., Шунгаров Х.Д. Асимптотический подход к многокритериальной задаче покрытия графа звездами // ДАН БССР.-1986.-Т.ХХХ1,№5.-С.430-433.

25. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах // Журн. Выч. Математики и мат. физики.-1989.-Т.29, №2.-С.171-183.

26. Емельянов C.B., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985. - 32с.

27. Зарубин Н.Г., Новиков Ю.В. Современные методы очистки и обеззараживания питьевой воды. М., 1976.

28. Захарченко М.П., Кошелев Н.Ф., Ромашов П.Г. Гигиеническая диагностика водной среды СПб., 1996.

29. Зинченко O.A. Об NP-трудном классе векторных задач на гра-фах.Черкесск, 1999. Деп. в ВИНИТИ, № 3103-В 99, с. 1-28.

30. Зинченко O.A., Шурыгина C.B., Шапошникова О.И. Сравнительный анализ эффективности приближенных алгоритмов для задачи об остовных деревьях. Тезисы Международной научной молодежной конференции «XXVI Гагаринские чтения». МАГИ, 2000. Т.1.-С.273.

31. Зыков A.A. Гиперграфы // Успехи математических наук. Т.29. Вып. 6. 1974.-С. 89-154.

32. Казиев В.М. О задаче комплектования графиков гидромодулей. В сб. науч. трудов САПР и АСПР в мелиорации. Нальчик: КБГУ, 1983.

33. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, Сиб. Отд., 19.

34. Ким-Гю-Пхир. Оптимальное распределение ресурса в условиях интервальной неопределенности // Международная конференция по интервальным и стохастическим методам в науке и технике (ИНТЕРВАЛ 92): Сборник трудов. Москва. 1992. Т.1. - С.60-63.

35. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер // Успехи матем. наук. 1985. Т.40, №1(241).

36. Коршунов А.Д. Об одном алгоритме нахождения паросочетаний в конечных графах // Кибернетика. 1975. № 1. С. 1-8.

37. Кравцов М.К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев // Дискретная математика. 1996. 8 №2.-С. 89-96.

38. Кульский Л.А. Основы химии и технологии воды. Киев, 1991.

39. Кульский Л.А., Строкач П.П. Технология очистки природных вод. Киев, 1986.

40. Кузнецов A.B., Сакович В.А., Холод Н.И. Математическое программирование. М.: Наука, 1994.

41. Кудаев В.Ч., Нахушева М.М. 2-оптимальное решение задачи синтеза сетей методом динамической декомпозиции / Доклады АМАН, 1999. Т.4, №1 С .15-20.

42. Кудаев В.Ч., Луценко Е.В., Алдошин В.И. Об одном подходе к автоматизированному проектированнию оросительных насосных станций. В кн.: САПР и АСПР в мелиорации. Сборник научных трудов (межведомственный). Нальчик, 1983.

43. Ларичев О.И. Наука и искусство принятия решения. М.:Наука, 1979. -200с.

44. Левин А.Г. О построении минимальных реализаций гиперграфов // Дискретная математика. Т.2. Вып.З. 1990. С.50-61.

45. Луценко E.B. Задачи оптимального проектирования ЗОС. В сб. науч. трудов САПР и АСПР в мелиорации. Нальчик: КБГУ, 1983.

46. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования: модели, методы, алгоритмы. -М.: наука, 1986.-264с.

47. Многокритериальные задачи теории графов. Алгоритмический подход (учебное пособие). Киев.: УМК ВО, 1989. - 45с.

48. Морозов К.К., Одиноков В.Г., Курейчук В.М. Автоматизированное проектирование конструкций радиоэлектронной и вычислительной аппаратуры. Учебное пособие для ВУЗов.-М. Радио и связь, 1983, 280с.

49. Нахушева М.М. Метод динамической декомпозиции решения задач синтеза сетей и его приложения: Автореферат дис. .к.ф.-м.н., Нальчик.-2000.

50. Норенков И.П., Маничев В.Б. Система автоматизированного проектирования электронной и вычислительной аппаратуры. Учебное пособие для ВУЗов.-М.: Высшая школа, 1983.

51. Ope О. Графы и их применение. М.: Мир, 1965. - 173с.

52. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Наука, 1981. - 208с.

53. Перепелица В.А. Асимптотический подход к решению некоторых экстремальных задач на графах // Проблемы кибернетики.- М.: Наука, 1973.-Вып.26.С.291-314.

54. Перепелица В.А., Сергиенко И.В. Исследование одного класса целочисленных многокритериальных задач // Кибернетика,-1987.-№5, С.45-51.

55. Перепелица В.А., Севастьянов C.B. Об одной задаче теории расписаний на сети // Управляемые системы.-Вып. 15.-Новосибирск: ИМ СО АН СССР, Наука, 1976.-С.128-150.

56. Перепелица В.А., Мамедов A.A. Исследование сложности и разрешимости векторных задач на графах: Уч. пособие.Черкесск, 1995. 68с.

57. Перепелица В.А. Об одном классе многокритериальных задач на графах и гиперграфах // Кибернетика.- 1984.-№4.-С.62-67.

58. Перепелица В.А., Шапошникова О.И. Математическая модель водопользования на гиперграфах с интервальными данными // Человек и Вселен-ная.-2002.-№ 8(18).-С.67-79.

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

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

61. Попова Е.В., Шапошникова О.И. О неразрешимости алгоритмами линейной свертки некоторых интервальных задач на графах // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2002. - № 3. - С. 29-33.

62. Прикладные нечеткие системы. Под редакцией Т.Тэрано, К. Асан, М.Сугэно. М.: Мир, 1993. - 367с.

63. Руководство по гигиене водоснабжения / Под ред. С.Н. Черкинского. -М, 1975.

64. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973. - 304с.

65. Сакович В.А. Исследование операций: Справочное пособие. Минск, 1985.-256с.

66. САПР-СКГВХ (первая очередь). Автоматизированные технологические линии проектирования, разработанные в НИИ ПМА КБГУ, г. Нальчик. -1982.

67. САПР-СКГВХ (вторая очередь). Подсистемы, разрабатываемые в НИИ ПМА КБГУ, г. Нальчик. 1985.

68. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.- Киев: Наук. Думка, 1988.- 472с.

69. Соломащенко Н.И. Факторы окружающей среды и здоровье населения Карачаево-Черкесской республики: Автореферат дис. . к.м.н., Казань-2003.

70. Справочник по очистке природных и сточных вод // Пасль JI.JI., Кару Я.Я., Мельдер Х.А., Репин Б.Н. М., 1994.

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

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

73. Хармут X. Теория секвентного анализа. Основы и применения / Пер. с англ. Л.М.Сороко. М.:Мир, 1980. - 574с.

74. Шапошникова О.И. Алгоритмы с оценками для векторной задачи об ос-товных деревьях. Деп. рукопись в ВИНИТИ, per. № 3618-1398 от 09.12.98.

75. Шапошникова О.И., Тебуева Ф.Б. Вероятностный анализ градиентных алгоритмов для задачи о лесах. Сб. науч. трудов III Всероссийского симпозиума «Математическое моделирование компьютерных технологий». Кисловодск: КИЭП, 1999. Т.З.-С.25-27.

76. Шапошникова О.И. Алгоритмы с оценками для векторной задачи об ос-товном дереве ограниченной степени. Тезисы Международной научной молодежной конференции «XXV Гагаринские чтения». МАГИ, 1999. Т.1.-С.181.

77. Шапошникова О.И. Полиномиальная разрешимость 2-критериальных задач на графах с топологическим критерием. Сборник тезисов III научно-практической конференции. Черкесск: КЧГТИ, 2001. С. 96-98.

78. Юдин Д.В., Голынтейн Е.Г. Линейное программирование. М., 1963.

79. Brucker P. Discrete Parameter optimization problem and essential afficient points. // Operat. Res. 1972 16. №5. P. 189-197.

80. Claudio D.M., Escadro M.H., Franciosi B.T. An Order-Theoretic Approach to Interval Analysis // Interval computations. 1992. 3. P. 38-45.

81. Claudio D.M., Franciosi B.T. Domain Approach to Interval Mathematics. // International conference on Interval and Stochastic Methods in Science and Engineering (Interval-92). 1992 2. P. 13-17.

82. Emelichev V.A., Perepelitsa V.A. Multiobgective Problem on the Spanning Trees of a Grafh, Soviet Math. Dokl. Vol.37(1988).-No.l,p.l 14-117.

83. Emelichev V.A., Perepelitsa V.A. Complexity of Vector Optimization Problems on Graphs, Optimization 22(1991),p.903-918.

84. Emelichev V.A., Perepelitsa V.A. On cardinality of the set of alternatives in discrete manycriterion problems, Discrete Math.Appl., Vol.2, № 5, pp.461-471(1992).

85. Kozina G.L., Perepelitsa V.A. Interval Spanning Trees Problem: Solvability and Computational Complexity // Interval Computations. 1994. №1., pp.42-50.

86. Perepelitsa V.A. On finding sets of alternatives for the discrete multiobjective problems, Lecture Note in Control and Information Sciences, IFIP 143, System

87. Modeling and Optimization, Proceedings of the 14th IFIP-Conference, Leipzig, GDR, Juli 3-7,1989, p.519-525.

88. Perepelitsa V.A. and Kozina G.L. Interval Discrete Models and Multiobjectiv-ity // Interval computations. 1993. l.pp. 51-59.

89. Yakovlev A.G. Classification Approach to Programming of Localizational. // Interval computations. 1992. 1. P. 61-84.