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

Введение.

Глава 1. ИССЛЕДУЕМЫЕ АГРО-ЭКОЛОГО-ЭКОНОМИЧЕСКИЕ ПРОБЛЕМЫ ЗЕМЛЕПОЛЬЗОВАНИЯ

1.1. Предмет исследования.

1.2. Ключевые слова предмета и темы исследования, основные понятия, термины и их содержание

1.3. Исходные данные и условия задачи.

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

2.1. Гиперграфы. Некоторые определения и свойства

2.2. Ориентированные гиперграфы.

2.3. Алгоритм выделения гамильтоновой цепи на гиперграфе

2.4. Оценки сложности для однородных гиперграфов.

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

2.6. Об одной агро-эколого-экономической модели на гиперграфах

2.7. Построение и исследование агро-эколого-экономической модели на ориентированном гиперграфе.

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

3.1. Общая формулировка векторной задачи покрытия графа цепями.

3.2. Задачи с интервальными данными

3.3. Сведение интервальной задачи о цепях к

2-критериальной задаче.

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

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

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

4.2. TVP-трудный подкласс 2-критериальных задач покрытия графа цепями

4.2.1. Критерий количества цепей и проблема поиска решений линейного диофантова уравнения.

4.2.2. Алгоритм решения линейного диофантова уравнения.

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

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

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

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

5.2. Исследование векторной задачи покрытия графа цепями двух типов.

5.2.1. Задача о покрытии графа {h,h+l} цепями.

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

5.2.3. Вероятностный анализ алгоритма, применяемого к

1-взвешенному графу.

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

5.3.1. Формулировка промежуточной задачи и обозначения

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

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

5.3.4. Обоснование теоретико-множественных достаточных условий асимптотической точности алгоритма

5.4. Условия асимптотической точности в случае произвольной структуры искомого покрытия.

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

6.1. Определение понятий и терминов.

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

Актуальность темы. В процессе моделирования дискретных задач оптимального размещения [12,60], маршрутизации [56,89], управления персоналом [28,19], автоматизированного проектирования электронной техники [54,85] и др. возникают задачи о покрытии графов цепями. Аналогичные задачи возникают в землепользовании. Однако, к настоящему времени отсутствуют сколь-нибудь адекватные математические модели, которые отражали бы в системном единстве взаимосвязь и взаимодействие основных факторов, составляющих содержание землепользования. В настоящей работе предпринята попытка восполнить этот пробел. Отталкиваясь от ранее известных математических моделей [7,8], отражающих только один показатель эффективности - экономический, рассматриваются математические модели землепользования, которые одновременно отражают такие аспекты агро-экологических процессов в сельском хозяйстве, как изменение плодородия почвы в зависимости от порядка чередования различных культур на полях, вносимых удобрений, а также ожидаемую урожайность и выход биомассы данной культуры в зависимости от её предшественника [1,17]. Причём, в контексте этих показателей предлагаемые модели являются открытыми для рассмотрения и учёта других критериев, например, химических, биологических и т.д.

Рассматриваемые математические модели базируются на математическом аппарате теории графов и гиперграфов [12,32,38]. Это обусловлено тем, что специфика их теорий в наибольшей степени приспособлена для абстрактного представления циклических процессов чередования. Нельзя не учитывать и то, что задача землепользования формулируется в многокритериальной постановке, которая требует нахождения не одного оптимального решения, а множества альтернатив [35,63,69]. К настоящему времени проблема нахождения множества альтернатив исследована очень слабо, в том числе и для векторной (т.е. многокритериальной) интервальной задачи [5,39] покрытия графов и гиперграфов цепями, которая возникает при математическом моделировании землепользования. Вместе с тем отсутствуют достаточно эффективные (т.е. имеющие полиномиальную трудоёмкость [26]) алгоритмы практически для всех задач на графах и гиперграфах, поэтому актуальной является разработка малотрудоёмких приближённых алгоритмов [20], которые всегда или почти всегда гарантируют нахождение приемлемых решений. Исследованию математических моделей землепользования и построению достаточно эффективных алгоритмов решения векторных интервальных задач покрытия графов и гиперграфов цепями посвящена настоящая диссертационная работа.

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

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

Научная новизна работы заключается в том, что в ней:

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

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

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

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

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

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

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

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

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

3. Выделение полиномиально разрешимого подкласса задач покрытия графа цепями.

4. Построение алгоритма с оценками для задач покрытия графа цепями.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

2. Построен алгоритм выделения гамильтоновой цепи на гиперграфах.

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

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

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

1. Агеев В.В. Интенсивное использование пашни. — М.: Россельхозиздат, 1984.-200 с.

2. Агрономическая тетрадь. Возделывание зерновых культур по интенсивным технологиям. М.: Россельхозиздат, 1986. - 234 с.

3. Агропромышленный комплекс России (состояние и проблемы реформи-рования)/Д.М. Хомяков, Р.А. Искандарян; под ред. В.П. Зволинский. М.: Диалог-МГУ, 1997. - 66 с.

4. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов. Основы теории. М.: Наука, 1990.-240 с.

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

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

7. Батищев А.Ф., Перепелица В.А. Об одном алгоритме нахождения оптимального севооборота. Сб. Оптимальное планирование. Новосибирск: ИМ СО АН СССР, 1970.-Вып. 16.-С. 16-20.

8. Батищев А.Ф., Гришин А.А., Перепелица В.А. К задаче нахождения оптимального севооборота. В сб. Математические методы планирования сельского хозяйства. Новосибирск: ИЭОПП СО АН СССР, 1970. -С.103-119.

9. Бенайюн Р., Ларичев О.И., Монтгольфье Ж.Н., Терни Ж. Линейное программирование со многими критериями качества. Метод ограничений//Автоматика и телемеханика. 1971. - №8. - С.48-62.

10. Беннет X. Основы охраны почвы. М.: Изд. иностр. лит-ры, 1958. - 412 с.

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

12. Берж К. Теория графов и ее применения. М.: Изд. иностр. лит-ры, 1962. - 320 с.

13. Бялый A.M. Водный режим почвы в севообороте. Гидрометеоиздат,1971.-232 с.

14. Ван дер Планк Я. Устойчивость растений к болезням. М.: Колос, 1972. -254 с.

15. Вилкас Э.И., Майминас Е.З. Решения : теория, информация, моделирование. М.: Радио и связь, 1981. 328 с.

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

17. Воробьев С.А. Севообороты интенсивного земледелия. М.: Колос, 1979. -368 с.

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

19. Вязин В.А., Федоров В.В. Математические методы автоматизированного проектирования. -М.: Высшая школа, 1989. 184 с.

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

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

22. Глушков В.М. О системной оптимизации//Кибернетика. 1980. №5. -С. 89-90.

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

24. Грызлов Е.В. Почвозащитная система земледелия. Ростовское книжное изд-во, 1975. - 136 с.

25. Гуткин JI.C. Оптимизация радиоэлектронных устройств по совокупности показателей качества. JL: Сов. Радио, 1975. - 368 с.

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

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

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

29. Дресслер Г. Управление персоналом. М.: Бином, 1997. 418 с.

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

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

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

33. Емеличев В.А., Перепелица В.А. К вычислительной сложности дискретных многокритериальных задач//Изв. АН СССР. Техн. киберн. №1. - С. 85-87.

34. Емеличев В.А., Перепелица В.А. Полные задачи многокритериальной дискретной оптимизации//Сообщения АН ГССР. 1988. - Т. 131, №3. - С. 501-504.

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

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

37. Ермолаев Ю.М., Мельник И.М. Экстремальные задачи на графах. Киев: Наук, думка, 1968. - 176 с.

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

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

40. Кахичко А.А. О построении совершенных паросочетаний графа//Методы решения нелинейных задач и обработка данных. Сб. науч. тр. Днепропетровск: ДГУ, 1986. С. 41-44.

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

42. Кини P.JL, Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981. - 420 с.

43. Кляус П.С. Специальный случай задачи о коммивояжере на узкие мес-та//Изв. АН БССР. Серия физ.-мат. наук. 1975. - №1. - С.47-51.

44. Козеноко 3., Рогачев А.Ф., Скитер Н.Н. Оптимизация структуры посевных площадей для крестьянских (фермерских) хозяйств: Препринт. Волгоград: ВГУ, 2001.-40 с.

45. Константинов А.Р. Погода, почва и урожай озимой пшеницы. Ленинград: Гидрометеоиздат, 1978. - 237 с.

46. Корбут А.А., Финкелынтейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.-368 с.

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

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

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

50. Кузнецов А.В., Сакович В.А., Холод Н.И. Математическое программирование. Мн.: Высшэйшая школа, 1994. 286 с.

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

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

53. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998. - 653 с.

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

55. Лыков A.M., Туликов A.M. Практикум по земледелию с основами почвоведения. М.: Агропромиздат, 1985. -207 с.

56. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. -323 с.

57. Марков А.А., Нагорный Н.М. Теория алгоритмов. М.: Наука, 1984. -432 с.

58. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. -М.: Наука, 1982. 287 с.

59. Нефедов В.Н., Осипов В.А. Курс дискретной математики. М.; МАИ, 1992.-264 с.

60. Оре О. Теория графов. -М.: Наука, 1980. 336 с.

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

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

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

64. Перепелица В.А., Гимади Э.Х. К задаче нахождения минимального га-мильтонова контура на графе со взвешенными дугами. Сб. Дискретный анализ. Новосибирск: Ин-т. математики СО АН СССР, 1970. - Вып. 15. -С.49-58.

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

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

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

68. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. — М.: Сов. радио, 1975. 192 с.

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

70. Почвозащитное земледелие/Под ред. А.И. Бараева. М.: Колос, 1975. -304 с.

71. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

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

73. Рюкин А.Н., Папин М.Ю. Интервальное линейное программирова-ние//Международная конф. по интервальным и стохастическим методам в науке и технике (ИНТЕРВАЛ 92): Сб. трудов. - Москва , - 1992. - Т.1. -С. 139-142.

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

75. Сабинин Д.А. Избранные труды по минеральному питанию растений. -М.: Наука, 1971.-512 с.

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

77. Свами М., Тхуласираман К. Графе, сети, алгоритмы. М.: Мир, 1984. — 422 с.

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

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

80. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М.: Наука, 1981. - 312.

81. Солтан П.С., Замбицкий Д.К., Присэкарту К.Ф. Экстремальные задачи на графах и алгоритмы их решения. Кишинев.: Штинца, 1973. - 90 с.

82. Схрейвер А. Теория линейного и целочисленного программирования: -М.: Мир, 1991.-Т.1.-342 с.

83. Татт У. Теория графов. М.: Мир, 1988. - 320 с.

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

85. Тот Л.Ф. Расположение на плоскости, на сфере и в пространстве. М.: Наука, 1958.-430 с.

86. Уилсон Р. Введение в теорию графов. М.: Мир, 1973. - 300 с.

87. Успенский В.А., Семенова А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987. - 288 с.

88. Филлипс Д., Гарсия-Диас А. Методы анализа сетей: М.: Мир, 1984. -496 с.

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

90. Фрущкин М.А. Сложность дискретных задач. М.: 1981. - 59 с. Препринт. АН СССР, ЦЕМИ.

91. Фуллер В. Введение в теорию вероятностей и ее приложение. М.: Мир, 1967.-320 с.

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

93. Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание,1987. - Вып. 1.-32 с.

94. Ху Т. Целочисленное программирование в потоках и сетях. М.: Мир, 1974, - 520 с.

95. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. М.: Наука, 1969, 452 с.

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

97. Claudio D.M., Escadro M.H., Franciosi B.T. An Order-Theoretic Approach to Interval Analysis//Interval Computations. 1992. 3. pp. 38-45.

98. Claudio D.M., Franciosi B.T. Domain Approach to Interval Mathemat-ics//International Conference on Interval and Stochastic Methods in Science and Engineering (INTERVAL 92). - 1992. 2. pp. 13-17.

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

100. Flood M.M. The Travelling-salesman Problem//Operation Research 4, 1. 1956. pp. 61-75.

101. Perepelitsa V.A. and Kozina G.L. Interval Discrete Models and Multiobjec-tivity//Interval computations. 1993. 1. pp, 51-59.

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

103. System Modeling and Optimization, Proceedings of 14 IFIP-Conference, Leipzig, GDR, July 3 7, 1989, pp. 519 - 525.

104. Yakovlev A.G. Classification Approach to Programming of Localiza-tional//Interval omputations. 1992. pp. 61 - 84.