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

ВВЕДЕНИЕ.

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

1.1 Общая постановка задачи.

1.2 Формулировка задачи о 4-кликах.

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

1.4 Вычисление оценок сложности для задачи о 4-кликах на т-цветных графах.

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

2.1 Формулировка проблемы.

2.2 Необходимые обозначения и определения.

2.3 Исследование разрешимости с помощью АЛС задачи о

4-кликах с критериями вида М1Ы81)1\/1 на 4-цветных графах.

2.4. Исследование разрешимости с помощью АЛС задачи о 4-кликах с критериями вида М1ЫМАХ.

2.5 Исследование разрешимости с помощью АЛС задачи о.

4-кликах с критериями М^БиМ и М1ЫМАХ на 4-цветных графах.

Глава 3. ТОЧНЫЕ АЛГОРИТМЫ ДЛЯ ЭКСТРЕМАЛЬНОЙ ЗАДАЧИ О 4-КЛИКАХ.

3.1 Оценка мощности множества клик, не имеющих общих вершин с данной кликой.

3.2 Описание алгоритма ах нахождения допустимого решения задачи о 4-кликах.

3.2.1. Описание этапов а\ и а] алгоритма ах.

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

3.2.3 Общая схема метода динамического программирования для задачи 0 4-кликах.

3.3 Лексикографический алгоритм а2 нахождения допустимого решения задачи о 4-кликах.

3.3.1 Подготовительный этап.

3.3.2 Этап отсеивания гипервершин.

3.3.3 Формирование множеств входов и выходов икс-клик

3.3.4 Формирование множества пар гипервершин «вход-выход» орклики.

3.3.5 Правило отсеивания гипервершин допустимых подорграфов.

3.3.6 Алгоритм нахождения икс-кпики в тупиковом подорграфе.

Глава 4. АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ ЗАДАЧИ О 4-КЛИКАХ

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

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

4.1.2 Алгоритм линейной свертки для многокритериальной задачи о

4-кликах.

4.1.3 . Вероятностный анализ алгоритма аъ применительно к 1 -взвешенному графу.

4.1.3 . Вероятностный анализ алгоритма аъ применительно к iV-взвешенному графу.

4.2 Малотрудоемкий асимптотически точный алгоритм.

4.2.1 Постановка задачи.

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

4.2.3 Основные утверждения и вероятностные оценки точности алгоритма А

Актуальность проблемы. Настоящая работа посвящена экстремальной задаче о покрытии взвешенного графа 4-вершинными кликами или, кратко, задаче о 4-кликах. Оговоримся заранее, что недостающие определения терминов теории графов и векторных, т.е. многокритериальных задач можно найти в [23],[26].

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

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

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

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

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

Дополнительным результатом, полученным в процессе исследования рассматриваемой проблемы, является численный эксперимент, представленный в виде приложения 2 к данной работе. Здесь осуществлен анализ фазового простанства и использован новый подход, предложенный в [53, 68] к исследованию комбинаторных задач.

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

Цель работы. Основной целью работы является: вывод точных формул вычисления максимальной мощности множества допустимых решений (МДР) задачи о 4-кликах и построение точных алгоритмов для этой задачи; доказательство свойства полноты задачи о 4-кликах на многоцветных графах в случае, когда векторная целевая функция (ВЦФ) включает критерии вида М1Ы81)М и МММАХ; и как следствие, получение заключения о труднорешаемости рассматриваемой задачи; выделение полиномиально разрешимых классов векторных задач и построение статистически эффективного и асимптотически точного алгоритмов для общего случая; исследовние проблемы разрешимости с помощью алгоритма линейной свертки. 7

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

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

Практическая ценность работы.

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

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

Публикации и апробация работы. По теме диссертационной работы опубликовано 11 печатных работ. Основные результаты диссертации докладывались на международной конференции "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики" (Нальчик, 1996), на I Всероссийском симпозиуме «Экономика и право - стратегии 3000» (Кисловодск, 1997), на молодежной научной конференции «XXIII Гагаринские чтения" (Москва, 1997), на второй научно-практической конференция Карачаево-Черкесского технологического института, (Черкесск, 1997), на II Всероссийском симпозиуме «Экономика и право -стратегии 3000» (Кисловодск, 1998), на Международном конгрессе математиков ЮМ'98 (Берлин, 1998), на Всероссийский международной конференции "Компьютерные технологии инженерной и управленческой деятельности" (Таганрог, 1998), на молодежной научной конференции «XXIV Гагаринские чтения" (Москва, 1999), а также на заседаниях научного математического семинара КЧТИ.

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. Доказана неразрешимость исследуемой задачи с помощью алгоритмов линейной сверки для критериев вида М1Ы8им и М1ЫМАХ.

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

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

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

137

1. Абрайтис Л.Б., Шейнаукас Р.И. Жилевичюс В.А. Автоматизация проектирования ЭВМ; Автоматизированное техническое проектирование конструктивных узлов цифровых устройств. - М.: Сов. Радио, 1978.-272 с.

2. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы. М.: Наука, 1975. - 118 с.

3. Архейм Рудольф. Новые очерки по психологии искусства. М.: Прометей, 1994.

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

5. Батищев А.Ф., Гришин A.A. Перепелица В.А. Из опыта решения задач по нахождению оптимального севооборота и их внедрения. В сб. Экономико-математические методы и ЭВМ в сельском хозяйстве. -Вильнюс: НИИЭСХЛССР, 1970.-Ч.2 -С.141-145.

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

7. Блатов В.А., Сережкин В.Н. Метод анализа топологии кристаллической решетки с помощью теории графов.// Кристаллография. 1992. - Т. 37, вып. 1. С. 51-62

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

9. Виноградская Т.М., Гафт М.Г. Точная верхняя оценка неподчиненных решений в многокритериальных задачах // Автоматика и телемеханика. 1974. - №9. - С. 111-118.

10. Воробьев H.H. Многокритериальная задача // Математическая энциклопедия. М.: Сов. Энциклопедия, 1982. -Т.З. - С.722-723.

11. Гаврилов Г.П., Сапоженко A.A. Сборник задач по дискретной138математике. М.: Наука, 1977. -256 с.

12. Галиулин Р.В. Кристаллографическая геометрия. М.: Наука, 1984.

13. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы // Изв. АН СССР. Техн. Киберн. 1979. - №6. - С. 9-19.

14. Гермейер Ю.Б. Введение в теорию исследования операций.-М.:Наука, 1971.-324 с.

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

16. Гладкий A.A., Янушкевич О.А.О линейной свертке частных критериев векторной задачи минимизации. Тез. докл. IX Всероссийской конф. « Математическое программирование и приложения.»-Екатеринбунг: УрО РАН, 1995.-С.65.

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

18. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. М.: Наука, 1986. - 296 с.

19. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизации. М.: Наука, 1981. - 344 с.

20. Емеличев В.А., Кравцов М.К. О задачах векторной дискретной оптимизации на системах подмножеств неразрешимых с помощью алгоритмов линейной свертки //ЖВМ и МФ,- 1994,- Т. 34, №7. С. 911.

21. Емеличев В.А., Кравцов М.К. О неразрешимости векторных задач дискретной оптимизаций на системах подмножеств в классе алгоритмов линейной свертки критериев //Докл. РАН.- 1994,- Т. 334, N1. -С.9-11.139

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

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

24. Емеличев В.А., Перепелица В.А. Многокритериальные задачи об остовах графов // Докл. АН СССР. 1988. - Том 298, №3. - С. 544547.

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

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

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

28. Журавлев Ю.И. Дискретное программирование. Матем. Энциклопедия. М.: Сов. Энциклопедия, 1979. - Т.2. - С. 205-206.

29. Зыков A.A. Основы теории графов. М.: Наука, 1987.

30. Казакова М.Ф. Нахождение оптимумов Парето в полиматричной задаче коммивояжера // Мат. методы решения экон. задач. -1974. -№5. С. 55-61.

31. Карапетян A.M. Автоматизация оптимального конструирования ЭВМ. М.: Сов. Радио, 1973. - 152 с.

32. Карзанов A.B. Экономные реализации алгоритма Эдмонса140нахождения парооочетания максимальной мощности и максимального веса. В сб. Исследования по дискретной оптимизации. М.: Наука, 1976.-С. 306-327.

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

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

35. Козина A.B., Козырев В.П. Перечисление кратчайших связывающих сетей с дополнительными ограничениями // Кибернетика. 1974. - №4. - С. 109-115.

36. Козина Г.Л. Исследование векторной задачи коммивояжера на многоцветных графах. В сб. Методы решения анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. - С. 52-60.

37. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969,- с.

38. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1978. - 832 с.

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

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

41. Кочкаров A.M., Перепелица В.А., Сергеева Л.М. Фрактальные графы и их размерность. Карачаево-Черкесский технологический институт, 1996. Деп. в ВИНИТИ, №3284-В96.

42. Кравцов М.К., Янушкевич O.A. О многокритериальных задачах, разрешаемых с помощью алгоритмов линейной свертки критериев || Препринт. Москва: Ин-т техн. кибернетики АН Беларуси,1411995. №16. - 16с.

43. Кристофидес H. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432с.

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

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

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

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

48. Михаличев B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. - 208с.

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

50. Многокритериальные задачи принятия решений. М.: Машиностроение, 1978. - 312 с.

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

52. Окопная В.А.-А., Перепелица В.А., Попова Е.В. Использование методологии нелинейных динамических систем в дискретной многокритериальной оптимизации. Карачаево-Черкесский технологический институт. 1998. Деп. в ВИНИТИ №2619-В98.

53. Ope О. Теория графов М.: Наука, 1968.-352с.

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

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

56. Перепелица В.А. К алгоритмической проблеме для многокритериальных задач проектирования управляющих систем. В сб. Проблемы теоретической кибернетики. Тез. докл.7 Всесоюз.конф. (Иркутск, 18-20 сент. 1985г.) Иркутск: Иркутск.гос.ун-т, 1985,- С. 164165.

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

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

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

60. Перепелица В.А., Тамбиева Д.А. Лексикографический алгоритм нахождения допустимого решения задачи о 4-кликах. Препринт №134Т.- Нижний Архыз: САО РАН, 1999. 7 с.

61. Петренко А.И. Основы автоматизации проектирования. -Киев: Техника, 1982. -295 с.

62. Пирсон У. Кристаллохимия и физика металлов и сплавов. Т.1. М.: Мир, 1977.

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

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

65. Поспелов Г.С., Ириков В.А., Курилов А.Е. Процедуры и алгоритмы формирования комплексных программ. М.: Наука, 1985. - 424 с.

66. Попова Е.В. Исследование многокритериальный задач теории расписаний. Дис. . кандидата физ.-мат. наук: 05.13.16.-Черкесск, 1998.- 165 с.

67. Пригожин И., Стингере И. Порядок из хаоса. Новый диалог человека с природой. М.: Прогресс, 1986.

68. Прохоров Ю.В., Розанов Ю.А. Теория вероятностей. М.: Наука, 1973.-495 с.

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

70. Самарский А.А, Галактионов В.А., Курдюмов С.П., Михайлов А.П. Режимы с обострением в задачах для квазилинейных параболических уравнений. М.: Наука, 1987.

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

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

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

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

75. Супруненко Д.А. Отношение порядка на подстановках и144экстремальные задачи // Кибернетика. 1981. - №4. - С. 722-729.

76. Сыроежин И.М. Математика сетевых планов. М.: Экономика, 1967.

77. Тамбиева Д.А. Задача о кликах. В сб.: XXIII Гагаринские чтения. Тез.докл. молодежной научной конференции. -М.:РГТУ-МАТИ, 1997. -С.20-21.

78. Тамбиева Д.А. Исследование задачи о 4-кликах как обобщение задачи о назначениях. В сб.: Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. Тез. докл. международ. Конф. Нальчик: НИИ ПМиА РАН, 1998. -С. 66.

79. Тамбиева Д.А. Малотрудоемкий асимптотически точный алгоритм решения одной задачи покрытия цифровых схем. Карачаево-Черкесский технологический институт, 1998. Деп. в ВИНИТИ,№ 2618-В98.

80. Тамбиева Д.А. Метода динамического программирования для задачи о 4-кликах. В сб.: XXV Гагаринские чтения. Тез.докл. молодежной научной конференции. М.:РГТУ-МАТИ, 1999 -С.20-21.

81. Тамбиева Д.А. Неразрешимость задачи о 4-кликах с помощью АЛС для критериев вида MINSUM и MINMAX. Препринт №132Т145

82. Нижний Архыз: САО РАН, 1999. 9 с.

83. Темирбулатов П.И., Салпагарова A.A., Тамбиева Д.А. Исследование задачи о 4-кпиках. В сб.: Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. Тез. докл. международ. Конф. Нальчик: НИИ ПМиА РАН, 1996. -С. 66.

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

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

86. Форд Д., Фулкерсон Д. Потоки в сетях. Пер с англ. М.: Мир, 1966.

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

88. Хакен Г. Синергетика. М.:1980.

89. Хакен Г. Информация и самоорганизация. М.:1991.

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

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

92. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. Кибернетический сборник, вып. 9. М.: Мир, 1964.-С. 202-218.

93. Холл М. Комбинаторика,- М.: Мир, 1970. -424с.

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

95. Эткинс П. Порядок и беспорядок в природе: Пер. с анг./ Предисл. Ю.Г.Рудого. М.: Мир, 1987.

96. Bellman R., Dynamic programming treatment of the traveling salesman problem//S. Assoc. Comput. Mach., 1962, 9, №1, PP. 61-63.

97. Brucker P. Discrete parameter optimization problem and essentialefficient points // Opérât. Res. (1972) V.16, №5. PP. 189-197.

98. Burkard R.E., Keiding H., Krarup J., Pmzan P.M.A relationship between optimality and efficiency in multicriteria 0 -1 programming problems// Computers & Optuations Research, 1981. V.8, № 4.-PP.241-247.

99. Burkard R.E., Krarup J., Pmzan P.M. Efficiency and optimality in minisum, minimax 0-1 programming problems//J. Oper. Res. Soc. (1982) 33, №2, P. 137-151.

100. Emelichev V.A., Perepeliza V. A. Complexity of vector optimization problems on graphs// Optimization, 1991, V. 22 , №6. PP. 903-918.

101. Mandelbrot B. New Methods in Statistical Economics // Journal of Political Economy (1963), P. 48-56.

102. Tambieva D.A. Research of 4-clique Problem, Abstracts of Short Communications and Poster Sessions, International Congress of Mathematicians, ICM'98, Berlin, August 18-27,1998 .- 351 p.

103. Wells A.F. Three-dimensional nets an polyhedra. -New York : Interscience, 1977.

104. Yu P.L. Cone convexity, cone extreme points, and nondominated solutions in decision problems with rnltiobjectives// JOTA,1974.V.14.-N3.-PP.319-377.

105. Zeleny M. Linear Multiobjective Programming. Springer : Berlin, 1974.