Помощь в написании студенческих работ
Антистрессовый сервис

Математические модели и методы для векторной задачи о кликах

Диссертация: Математические модели и методы для векторной задачи о кликах
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

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

Содержание

  • Глава 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. В качестве дополнительного результата разработана и реализована на персональной электронно-вычислительной машине имитационная модель, которая на базе генератора случайных значений исходных данных воспроизводит и представляет в явном виде критериальное пространство для различных комбинаций критериев, составляющих векторную целевую функциюосуществлен анализ этого пространства методами динамического хаоса.

Показать весь текст

Список литературы

  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. — С. 544 547.
  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. О многокритериальных задачах, разрешаемых с помощью алгоритмов линейной свертки критериев || Препринт. Москва: Ин-т техн. кибернетики АН Беларуси, 1 411 995. № 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, — С. 164 165.
  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 // Operat. 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.
Заполнить форму текущей работой

Сессия? Спокойно!