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

• Тебуева, Фариза Биляловна
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Тебуева, Фариза Биляловна

Введение.

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

1Л. Теоретико-графовые модели инженерных и организационных задач.

1.2. К использованию теоретико-графовых моделей в кластерном анализе.

1.3. Задачи индустриально- организационной психологии, сводящиеся к отысканию оптимального покрытия графа звездами.

1.4. О теоретико-графовых задачах землепользования.

1.5. К вопросу о получении численных значений исходных данных для задачи землепользования.

1.5.1. Общие положения.

1.5.2. Зависимость урожайности культуры от предшественников, внос и вынос ими питательных веществ

1.5.3. Влияние органического и минерального удобрения на урожай и плодородие почвы.

1.5.4. Экологическая оценка агромероприятий.

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

1.6. Проблема многокритериальное™ и отсутствие безусловного оптимума в системе земледелия.

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

2.1. Общая постановка проблемы дискретной многокритериальной оптимизации.

2.2. Математическая постановка векторной задачи покрытия графа звездами.

2.3. Обоснование свойства полноты исследуемой задачи.

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

2.5. Основные термины и понятия, необходимые для формулировки задачи покрытия гиперграфа звездами.

2.6. Математическая модель векторной задачи землепользования на гиперграфах.

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

3.1. Исследование условий существования допустимого покрытия графа звездами.

3.2. О методах решения линейных диофантовых уравнений

3.3. Полиномиально разрешимый подкласс 1-критериальных задач.

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

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

4.1. Формулировка интервальной экстремальной задачи

4.2. Сведение интервальной задачи покрытия графа звездами к векторной задаче.

4.3. Методы отыскания паретовских оптимумов с помощью алгоритмов линейной свертки критериев.

4.4. Обоснование неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи покрытия графа звездами с критериями вида MINSUM

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

5.1. Основные положения методологии приближенных алгоритмов.

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

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

5.4. Обоснование асимптотически точного алгоритма.

5.5. Вероятностный анализ применения асимптотически точного алгоритма к конечным множествам взвешенных графов.

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

Актуальность проблемы. Диссертационная работа посвящена математическому моделированию дискретных систем и процессов, дальнейшее развитие которых существенным образом зависит от состояния системы или процесса на предыдущем этапе эволюционирования. Задачи подобного рода возникают в складской логистике, в управленческих задачах организационно-индустриальной психологии и т.д. Возможно, наиболее актуальные проблемы такого рода возникают в процессе моделирования агро-эколого-экономических систем, когда принятие решений на очередном этапе землепользования кардинальным образом отражается на последующих состояниях моделируемой системы. Можно считать общепризнанным тот факт, что экологический кризис конца двадцатого века сделал, как никогда, актуальными вопросы взаимоотношения человека с окружающей средой. Динамическое ухудшение экологической обстановки, истощение природных ресурсов оказывают самое негативное влияние на организацию сельского хозяйства. На пахотных почвах большинства регионов России происходит устойчивая убыль гумуса, а также катастрофически растет площадь земель, подверженных эрозии. Одной из причин этого состояния является «исчерпанность» развития сложившихся современных систем земледелия. Характерными особенностями последних являются: распространение однообразия экологических систем; нарастание специализации, т.е. стремление к монокультуре; упрощение севооборотов, отчуждение с урожаем одних и тех же микроэлементов, т.е. истощение почвы в одностороннем порядке; увеличение засоренности посевов по причине узкой специализации; нарастание токсикологической нагрузки агроэкосистемы.

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

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

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

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

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

Основные задачи исследования

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

2. Вычисление мощности множества допустимых решений задачи покрытия графа звездами.

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

4. Исследование разрешимости в классе алгоритмов линейной свертки критериев (АЛСК) интервальной задачи покрытия графа звездами.

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

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

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

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

На защиту выносятся следующие положения:

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

2. Точная формула вычисления максимальной мощности множества допустимых решений задачи покрытия графа звездами; утверждение о трудно-решаемости этой задачи в случае, когда ее векторная целевая функция содержит хотя бы пару критериев вида МП^ЦМ.

3. До настоящего времени неизвестные полиномиально разрешимые подклассы 1-критериальных и 2-критериальных задач покрытия графа звездами. Первый из этих подклассов содержит задачи с векторной целевой функцией вида МШ81Ж и второй - критерии вида МШ^ИМ и МГЫМАХ. Строгое обоснование этих подклассов включает исследование диофанто-ва уравнения, для которого построен алгоритм отыскания всех допустимых решений.

4. Исследование крайнего случая неопределенности данных, когда параметры задачи задаются интервалами возможных значений. Обоснование неразрешимости интервальной задачи покрытия графа звездами с помощью алгоритмов линейной свертки для критериев вида МИ\Г8иМ.

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

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Тебуева, Фариза Биляловна

ЗАКЛЮЧЕНИЕ

В настоящей работе получены следующие результаты:

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

2. Выведена точная формула вычисления максимальной мощности множества допустимых решений задачи покрытия графа звездами; доказано утверждение о труднорешаемости этой задачи в случае, когда ее векторная целевая функция содержит хотя бы пару критериев вида МЕМБЦМ.

3. Выявлены 2 подкласса полиномиально разрешимых задач покрытия графа звездами. Первый из этих подклассов содержит задачи с векторной целевой функцией вида МШЧ8иМ и второй критерий - вида МПММАХ. Строгое обоснование этих подклассов включает исследование диофанто-ва уравнения, для которого построен алгоритм отыскания всех допустимых решений.

4. Исследован крайний случай неопределенности в исходных данных рассматриваемых задач, когда веса задаются интервалами. В процессе этого исследования доказана неразрешимость интервальной задачи покрытия графа звездами с помощью алгоритмов линейной свертки для критериев вида МП^ЦМ.

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

Список литературы диссертационного исследования кандидат физико-математических наук Тебуева, Фариза Биляловна, 2002 год

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

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

3. Баккет М. Фермерское производство: организация, управление, анализ.-М.: Агропромиздат, 1989.-464 с.

4. Батищев А.Ф., Перепелица В.А. Об одном алгоритме нахождения оптимального севооборота //Оптимизация планирования.- 1970.- Вып.16.- С. 16-20.

5. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации,- Новосибирск: Наука, 1978.- 333 с.

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

7. Буров Д.И., Чуданов И.А. Некоторые вопросы плодородия черноземных почв в связи с освоением пропашных севооборотов. В сб. Гидрофизика и структура почвы. Вып. 11- Л.: Гидрометеорологическое изд-во, 1965.-С. 196-204.

8. Векленко В.И. Экономическая проблема устойчивости и повышения эффективности земледелия.- Курск: Изд-во Курской сельскохозяйственной академии, 1999.-216 с.

9. Возбуцкая А.Е. Химия почвы.- М.: Высшая школа, 1968,- 427 с.

10. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности.- М.: Наука, 1989,- 356 с.

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

12. Гаджинский A.M. Логистика: Учебник для высших и средних специальных учебных заведений.- М.: Информационно-внедренческий центр1. Маркетинг», 1999.- 228 с.

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

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

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

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

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

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

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

20. Дебрецени Б. Баланс элементов минерального питания в земледелии Венгрии //Междунар. с.-х. журн.- 1988.- № 2.

21. Демченко А.И. Синтез транспортных сетей в условиях неопределенности исходной информации //Труды семинара по интервальной математике. 1990,-С. 10-16.

22. Джуэлл JT. Индустриально организационная психология: Учебник для вузов. - СПб.: Питер, 2001,- 720 с.

23. Егоров A.B. Развитие и эффективность рекомбинированных форм хозяйствования в аграрном секторе: Автореф. дис. канд. экон. наук. Кисловодск: КИЭП, 2001.- 27 с.

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

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

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

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

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

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

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

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

32. Кардаш В.А. Модели управления производственно-экономическими процессами в сельском хозяйстве.- М.: Экономика, 1981.- 184 с.

33. Ким-Гю-Пхир. Оптимальное распределение ресурсов в условиях интервальной неопределенности. М.: Наука, 1992.- 256 с.

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

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

36. Кочкаров A.M., Перепелица В.А. Асимптотическая эффективность локального декомпозиционного алгоритма для одной многокритериальной задачи покрытия, возникающей в САПР//Автоматизация процессов проектирования,- 1984.- Вып.2.- С.78-82.

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

38. Кузнецов A.B., Сакович В.А., Холод Н.И. Математическое программирование." Минск: Вышейшая школа, 1994.- 351 с.

39. Кук Дж. У. Регулирование плодородия почвы.- М.: Колос, 1970.- 520 с.

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

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

42. Логическое проектирование БИС/В.А. Мищенко, А.И. Аспидов, В.В. Витер и др.- М.: Радио и связь, 1984.- 312 с.

43. Минеев В.Г., Дебрецени Б., Мазур Т. Биологическое земледелие и минеральные удобрения,-М.: Колос, 1993.- 415 с.

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

45. Моисеев H.H. Математические задачи системного анализа.- М.: Наука, 1981.- 488 с.

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

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

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

49. Основы земледелия/Под ред. М.Н. Гуренева 2-е изд., перераб. и доп-М.: Колос, 1981.-495 с.

50. Панников В.Д., Минеев В.Г. Почва, климат, удобрение и урожай.- М.: Агропромиздат, 1987 512 с.

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

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

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

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

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

56. Перепелица В.А., Петова Е.Х. Исследование отношений подчиненности в математических моделях формирования целевых групп исполнителей. В сб. Фракталы в науке, производстве и обществе. Нижний Архыз: КИИ-Центр «SYGNUS», 1999,- С.47-58.

57. Перепелица В.А., Салпагаров С.И., Тебуева Ф.Б. Точные алгоритмы для задач покрытия графов звездами и цепями //Известия вузов. СевероКавказский регион,- 2002,- №1.- С.63-74.

58. Перепелица В.А., Сергеева J1.H. Исследование неразрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач //Кибернетика и системный анализ. 1996.- № 2.- С. 71-77.

59. Перепелица В.А., Сергиенко И.В, Исследование одного класса целочисленных многокритериальных задач //Журнал вычисл. матем. и матем. физики,- 1988,- Т.28, № 3.- С. 400-419.

60. Полевой А.Н. Прикладное моделирование и прогнозирование продуктивности посевов.- Л.: Гидрометеоиздат, 1988,- 319 с.

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

62. Рощин В.А., Семенова Н.В., Сергиенко Н.В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными //Журнал вычисл. матем. и матем. физики.- 1990.-Т.29, № 5.- С. 789-791.

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

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

65. Салпагарова A.A., Темирбулатов П.И. Оценки сложности многокритериальных задач о сочетаниях //Тез. докл. Международной конференции «Математическое программирование и приложения».- Екатеринбург: Институт математики и механики УрО РАН, 1997,- С.78-80.

66. Селютин В.А. Машинное конструирование электронных устройств.- М.: Сов.радио, 1977.- 384 с.

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

68. Столяр A.A. Логическое введение в математику Мн.: Вышэшн. школа, 1971,- 224 с.

69. Теория и методы автоматизации проектирования вычислительных систем.- М.: Мир, 1977.- 283 с.

70. Факторный, дискриминантный и кластерный анализ.- М.: Финансы и статистика, 1989.-215 с.

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

72. Шереги Ф.И., Горшков М.К. Основы прикладной социологии. T.I, Т.2.-М.: Ред.-изд.фирма «Academia», 1935.- 390 с.

73. Экология и экономика природопользования: Учебник для втузов,- М.: ЮНИТИ, 2000.-455 с.

74. Юдин Д.В., Гольштейн Е.Г. Линейное программирование.- М.: Наука, 1963.- 625 с.

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

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

77. 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.

78. Davis, K. Management communication and the grapevine. Harvard Business Revien. (1953) 31,pp. 43-49.

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

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

81. 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).

82. Kochkarov A.M., Perepelitsa V.A. About the algorithms with estimates for multicriterial problems on the graphs, Mathematical methoda in engineering. I, Proceeding of 6th International Conference, Plzen Czechoslovakia (1991),153pp.223-230.

83. Perepelitsa V.A. and Kozina G.L. Interval Discrete Models and Multiobjec-tivity // Interval computations.- 1993.- №1.- P.51-59.

84. Sutton, H., & Porter, L.W. A study of the grapevine in a governmental organization. Personnel Psychology (1968) 21, pp. 223-230.

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