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

Введение.

Глава 1. Модели комбинаторных задач оптимизации с квадратичным функционалом от линейных функций и их свойства.

1.1. Формулировка конкретных задач, приводящих к комбинаторным задачам оптимизации с квадратичным функционалом от линейных функций.

1.1.1. Задача равноценного распределения ресурсов.

1.1.2. Задача использования неделимого ресурса.

1.1.3. Задача упаковки.

1.1.4. Задача конкурентной борьбы за общие интересы

1.1.5. Модель теории абстрактного вопросника.

1.2. Задача равноценного распределения элементов множеств и ее свойства.

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

1.2.2. Пример поиска наилучших элементов множеств.

1.2.3. Математическая формулировка задачи.

1.2.4.Свойства задач равноценного распределения элементов множеств.

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

Глава 2. Методы решения задач о назначениях с квадратичным функционалом от линейных функций.

2.1. Дискретный метод функциональных уравнений.

2.1.1. Функциональные уравнения задачи о назначени

2.1.1.1. Динамическая постановка задачи о назначениях.

2.1.1.2. Вывод функциональных уравнений задачи о назначениях.

2.1.2. Схема решения задачи о назначениях дискретным методом функциональных уравнений.

2.1.3. Решение тестового примера дискретным методом функциональных уравнений.

2.1.4. Сложность дискретного метода функциональных уравнений.

2.1.5. Блок-схема дискретного метода функциональных уравнений.

2.1.6. Выводы.

2.2. Непрерывный метод функциональных уравнений.

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

2.2.2. Схема решения задачи о назначениях непрерывным методом функциональных уравнений.

2.2.3. Решение тестового примера непрерывным методом функциональных уравнений.

2.2.4. Блок-схема непрерывного метода функциональных уравнений.

2.2.5. Выводы.

2.3. Метод распределения избыточных оценок.

2.3.1. Необходимые условия допустимости решений задачи о назначениях.

2.3.2. Метризация, согласованная с задачей о назначениях.

2.3.3. Оптимальность решений задачи о назначениях.

2.3.4. Алгоритм метода распределения избыточных оценок.

2.3.5. Некоторые оценки сложности метода распределения избыточных оценок.

2.3.6. Решение тестового примера методом распределения избыточных оценок.

2.4. Метод однократных замещений.

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

2.4.2. Алгоритм метода однократных замещений.

2.4.3. Решение тестового примера методом однократных замещений.

Актуальность темы. Задачи дискретной оптимизации представляют прикладной и теоретический интерес и тесно связаны как с потребностями практики (задачи поиска и принятия решений, оптимальное управление), так и с математикой (например, с комбинаторным анализом, дискретной математикой, теоретической кибернетикой). Достаточно подробный перечень таких задач, их моделей и методов решения приведен в обзорах [1-4].

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

Область применения задач дискретной оптимизации достаточно широка и не ограничивается линейными моделями дискретной оптимизации. Функционалы многих конкретных экстремальных комбинаторных задач имеют квадратичную нелинейность от линейных функций [5, с. 13], а переменные этих задач являются либо псевдодискретными, либо дискретными (в частности, целочисленными), что позволяет учесть комбинаторные свойства природы переменных элементов. Такой вид имеет задача равноценного распределения элементов множеств [6-7]. Такого же рода функционал возникает в задаче геометрического метода распознавания образов, когда за меру близости принимается среднее квадратическое расстояние в евклидовой метрике [8, с.133], а также в классе задач распределения порционных ресурсов между потребителями с функцией аддитивного критерия [9, с. 201]. Задачи с такими функционалами другими авторами не исследовались, их свойства не изучены, не построены алгоритмы их решения. Однако в неявной форме задачи такого рода появляются (квадратичная задача о назначениях, об упаковках, о разбиениях, о кучах камней) [2-5;9-12;25;27-29;52-53;62-63;68-72;85;91-92;94;97; 107-110].

Задачи дискретной оптимизации довольно часто, даже в линейном случае, являются сложными для решения. Используются методы динамического программирования Беллмана (метод функциональных уравнений), ветвей и границ [2;5;8-9;13-28;32-33;55;67-72;91-101]. Применяются и "пожирающие" алгоритмы [67]. Не исключено применение метода перебора. Эти же методы переносятся на другие классы функций, причем во многих случаях в алгоритмах приходится максимально использовать специфику задачи. Кроме того, для задач нахождения экстремума нелинейного функционала на множествах комбинаторной природы возникают различные проблемы, связанные с исследованием допустимых комбинаций решений, нахождением правила оптимальности допустимых решений и построением алгоритмов оптимизации функционала.

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

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

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

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

Задача о назначениях поставлена как задача дискретного оптимального управления. Выведены функциональные уравнения, позволяющие дать алгоритм дискретного метода функциональных уравнений (ДМФУ) и схему решения задачи о назначениях. Проведено исследование сложности ДМФУ решения задачи о назначениях с квадратичным функционалом от линейных функций.

Задача о назначениях рассматривается как задача непрерывного оптимального управления. Это позволяет непрерывным методом функциональных уравнений (НМФУ) находить псевдооптимальные решения задачи о назначениях с квадратичным функционалом от линейных функций.

Получены условия допустимости и оптимальности решений задачи о назначениях. На этой основе построен алгоритм метода распределения избыточных оценок (МРИО) решения задачи о назначениях с квадратичным функционалом от линейных функций.

Введены однократные замещения элементов, позволяющие через них представлять допустимые решения задачи о назначениях. Получен метод однократных замещений (МОЗ) решения задачи о назначениях.

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

Реализация и внедрение результатов работы. Основные результаты исследований используются в учебном процессе кафедр высшей математики и компьютерных технологий Чувашского государственного университета им. И.Н. Ульянова и в выпускных работах магистров по специальности «Электроснабжение» [78]. Кроме того, кафедры (в том числе высшей математики и компьютерных технологий) Чувашского государственного университета используют алгоритмы решения задачи о назначениях для составления равноценных тестов, экзаменационных билетов и других контролирующих материалов [30-31 ;40].

Апробация работы. Основные результаты диссертационной работы были представлены на VII межвузовской научно-методической конференции по проблемам педагогики и методики высшей школы (Чебоксары, 1983), VII, VIII, IX всесоюзных конференциях «Теоретическая кибернетика» (Иркутск, 1985; Горький, 1988; Волгоград, 1990), итоговой научной конференции Чувашского государственного университета (Чебоксары, 1992), V международной научной конференции «Дифференциальные уравнения и приложения» (Саранск, 2002).

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

Публикации. По результатам исследований опубликовано 10 работ.

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

1. На основе обобщения конкретных прикладньж задач полу чена математическая постановка задачи равноценного распределения элементов множеств, приводящая к задаче поиска наилучших эле ментов.2. На основе полученной математической формулировки про ведено исследование задачи равноценного распределения элементов множеств. Доказаны свойства инвариантности к сдвигу, к сдвигу в одной строке и во всех строках, к преобразованиям оценок эталонных элементов, к растяжению и линейному преобразованию.3. Получены связи значений функционалов различных задач равноценного распределения элементов множеств и их оптимальных значений.4. Общая задача равномерного распределения элементов мно жеств сведена к задаче о назначениях с квадратичным функционалом от линейных функций.5. Получена совокупность теорем, математически строго обосновывающих алгоритмы равноценного распределения элементов множеств.6. Задача о назначениях поставлена и решена как задача дис кретного оптимального уравнения. Разработан алгоритм решения за дачи о назначениях. Проведено исследование сложности дискретного метода функциональных уравнений решения задачи о назначениях с квадратичным функционалом от линейных функций.7. Рассмотрена задача о назначениях как задача непрерывного оптимального уравнения, что позволяет находить псевдооптимальные решения задачи непрерывным методом функциональных уравнений.8. Получены условия допустимости и оптимальности решения задач о назначениях. Построен алгоритм метода распределения из быточных оценок решения задачи о назначениях с квадратичным функционалом от линейных функций.9. Изучен метод однократных замещений исследования задач о назначениях. Введены однократные замещения элементов, и иссле довано представление допустимых приращений через однократные замещения. Доказана теорема, дающая алгоритм метода однократных замещений.

1. Корбут A . A . , Финкельштейн Ю.Ю. Дискретные задачи математического программирования// Итоги науки. Сер. Теория вероятн. Мат. статист. Теоретич. кибернет. 1966.- М.: ВИНИТИ, 1967. - 59-110.

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

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

4. Леонтьев В.К. Дискретные экстремальные задачи// Итоги науки итехники. Сер. Теория вероятн. Мат. статист. Теоретич. кибернет. М.: ВИНИТИ, 1979. - Т.16. - 39-102.

5. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. - М.:Мир, 1985.-509 с.

7. Бычков В.П Оптимальность решений комбинаторной задачи минимизации с квадратичным функционалом от линейных функций// Проблемы теоретической кибернетики: Тез. докл. 8-ой Всесоюзн. конф.: В 2 ч. - Горький: Горьк. госпедин-т, 1988. - Ч . 1 . - 59.

8. Кузин Л.Т. Основы кибернетики: В 2 т. - Т.2. Основы кибернетических моделей. - М.: Энергия, 1979. - 584 с.

9. Рубинштейн М.И., Плитман А.Д. Комбинаторные методы группировки в задачах планирования и организации // Итоги науки и техНИКИ. Сер. Техн. кибернет. - М.: ВИНИТИ, 1986. - Т. 19. - 190 288.

10. Вайнштейн А.Д. Задачи об упаковки прямоугольников в полосу// Дискретные задачи оптимизации (управляемые системы). Новосибирск: Ин-т математики СО АН СССР, 1984. - Вып. 25. - 17-37.

11. Ушаков И.А. Задача о выборе предпочтительного объекта// Изв.АН СССР. Техн. кибернет. - 1971. - №4. - 3-8.

12. Рыбников К.А. Введение в комбинаторный анализ. - М.: Изд-воМоск. ун-та, 1985.-308 с.

13. Беллман Р. Динамическое программирование. - М.: ИЛ, 1960.400 с.

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

15. Современное состояние теории исследования операций/ Подобщ. ред. Н.Н. Моисеева, - М.: Наука, 1979. - 464 с.

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

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

18. Dantzig G.B. , Fulkerson D.R., Johnson S. Solution of a large scaletraveling salesman problem. - Opérât. Res. - 1954. - V.2, №3. - P. 393 -410 .

19. Dantzig G.B. Discrete variable exstremum problems. - Operat. Res.- 1957. - V.5, №2. - P. 266-277.

20. Gomory R.E . Outline of an algorithm for integer solution to linearprograms. - Bul l . Amer. Math. Soc. - 1958. - V.64, №5. - P. 275-278.

24. Кузин Л.Т. Основы кибернетики: В 2 т. - T. 1. Математическиеосновы кибернетики. - М . : Энергия, 1973. - 504 с.

25. Бурков В.Н., Рубинштейн М.И. Комбинаторное программирование. - М.: Знание, 1977. - 64 с.

26. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. - М.: Наука, 1981.-208 с.

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

28. Баранов В,И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. - М.: Наука, 1989.

29. Захаров В.Н., Поспелов Д.А., Хазацкий В.Е. Системы управления: Задания, проектирование, реализация. - М.: Энергия, 1972. 344 с.

30. Бычков В.П. Экстремальные комбинаторные задачи и некоторыеметоды их решения // Высшая школа - народному хозяйству Чувашии. Естественные науки: Тез. докл.- Чебоксары: Изд-во Чуваш, ун-та, 1 9 9 3 . - С . 23.

31. Бычков В.П. Метризация, согласованная с функционалом комбинаторной задачи минимизации// Математические модели и их приложении: Сб.науч. тр. - Чебоксары: Изд-во Чуваш.ун-та, 1999. - 35-40.

32. Бычков В.П. Один метод решения комбинаторной задачи оптимизации с квадратичным функционалом от линейных функций // Там же. - Вып. 2. - Чебоксары: Изд-во Чуваш, ун-та, 2000. - 24 35.

33. Бычков В.П. Метод однократного замещения в задаче равноценного распределения дискретного множества объектов// Там же. Вьш.З. - Чебоксары: Изд-во Чуваш, ун-та, 2001. - 35-40.

34. Бычков В.П. Свойства задач равноценного распределения элементов множеств// Там же. - Вып.4. - Чебоксары: Изд-во Чуваш, ун-та, 2002. - 70-79.

35. Бычков В.П., Желтов В.П. Применение алгоритмов равноценного распределения элементов множеств при составлении контролирующих материалов// Там же. - Вып.4. - Чебоксары: Изд-во Чуваш, ун-та, 2002. - 64-70.

36. Бычков В.П. Модель абстрактного вопросника в задаче равноценного распределения элементов множеств// Автоматизация и производство.- Москва: Изд-во Овен, 2002. - 71-76.

37. Бычков В.П., Желтов В.П., Шестакова H . A . Оптимизационнаязадача о назначениях// Математические модели и их приложения: Сб. науч. тр. - Вып.4. - Чебоксары: Изд-во Чуваш, ун-та, 2002. 80-83.

38. Белкин А.Р. Желательные свойства оптимальных линейныхупорядочений// Изв. АН СССР. Техн. кибернет. - 1987. - №2. 321.

39. Белкин А.Р. Модели упорядочения объектов: свойства, характеристика, сравнительный анализ. - Препринт/ НСК АН СССР. - М.: 1988.-57 с.

40. Кофман А. Введение в прикладную комбинаторику. - М.: Наука,1975.-480 с.

41. Пфанцагль И. Теория измерений. - М.: Мир, 1976. -248 с.

42. Берж К. Теория графов и ее применения. - М.: ИЛ, 1962. - 319 с.

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

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

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

46. Моисеев H . H . Численные методы в теории оптимальных систем.- М . : Наука, 1971.-424 с.

47. Нропой А.И. Элементы теории оптимальных дискретных процессов. - М.: Наука, 1973. -256 с.

48. Моисеев H . H . Элементы теории оптимальных систем. - М.:Наука, 1975.-526 с.

49. Табак Д., Куо Б. Оптимальное управление и математическоепрограммирование. - М.: Наука, 1975. - 280 с.

50. Аоки М. Введение в методы оптимизации. М.: Наука, 1977.344 с.

51. Кротов В.Ф., Гурман В.И. Методы и задачи оптимальногоуправления. - М.: Наука, 1977. - 448 с.

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

53. Райфа Г. Анализ решений. - М.: Наука, 1977. - 408 с.

54. Марченков С., Матросов В.Л. Сложность алгоритмов и вычислений// Итоги науки и техники. Сер. Теория вероят. Мат. статист. Теоретич. кибернет. 1979. - М.: ВИНИТИ, 1980. - Т.16. - 103-149.

55. Немировский A . C . , Юдин Д.Б. Сложность задач и эффективность методов оптимизации. - М.: Наука, 1979. - 384 с.

56. Гудмен С , Хидетниями Введение в разработку и анализ алгоритмов. - М.: Мир, 1981. - 368 с.

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

58. Носов В.А., Сачков В.Н., Тараканов В.Е. Комбинаторный анализ: Неотрицательные матрицы, алгоритмические проблемы// Итоги науки и техники. Сер. Теория вероят. Мат. статист. Теоретич. кибернет. - М.: ВИНИТИ, 1983. - Т.21. - 120 - 178.

59. Кнут Д. Искусство программирования для ЭВМ: В 7 т. - Т. 1. Основные алгоритмы. - М . : Мир, 1976. - 735 с.

60. Кнут Д. Искусство программирования для ЭВМ: В 7 т. - Т.2.Полученные алгоритмы. - М.: Мир, 1977. - 724с.

61. Кнут Д. Искусство программирования для ЭВМ: В 7 т. - Т.З.Сортировка и поиск. - М.: Мир, 1978. - 844 с.

62. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения// Кибернетический сборник. - Вып.2. - М.: Мир, 1961. - 95107.

63. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.275 с.

64. Тарьян Р.Э. Сложность комбинаторных алгоритмов// Кибернетический сборник. - Вып. 17. - М . : Мир, 1980. - 60-113.

65. Вагнер Г. Основы исследования операций: В 3 т. - Т.1. - М.:Мир. 1972.-335 с.

66. Вагнер Г. Основы исследования операций: В 3 т. - Т.2. - М.:Мир. 1973.-407 с.

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

68. Леонтьев В.К. Комбинаторика: ретроспектива и перспектива//Компьютер и задачи выбора. - М.: Наука, 1989. - 49-88.

69. Белкин А.Р., Левин М.Ш. Принятие решений: комбинаторныемодели аппроксимации информации. - М.: Наука, 1990. -160 с.

70. Хачиян Л.Г. Проблемы оптимальных алгоритмов в выпукломпрограммировании, декомпозиции и сортировке// Компьютер и задачи выбора. - М.: Наука, 1989. - 161-205.

71. Гордеев Э.Н. Задачи выбора и их решение// Компьютер и задачивыбора. - М . : Наука, 1989. - 5-48.

72. Проблемы принятия решений: Сб. статей. - М.: Наука, 1976.319 с.

73. Теория прогнозирования и принятие решений. - М.: Высш.школа, 1977. - 350 с.

74. Евланов Л.Г. Основы теории принятия решений. - М.: Акад.нар. хоз-ва, 1979.-212 с.

75. Курсовые работы по высшей математике: Задания и методические указания/ Сост. В.Г. Агаков, В.П. Бычков и др. - Чебоксары: Чуваш, ун-т, 2002. - 52 с.

76. Мальцев А.И. Основы линейной алгебры. - М.: Наука, 1970.423 с.

77. Понтрягин Л.С. Эрмитовы операторы в пространстве с индефинитной метрикой// Изв. АН СССР. Сер. Мат. - 1944. - Т.8. - С . 243280.

78. Бурбаки Н. Топологические векторные пространства. - М.: ИЛ,1959.

79. Рудин У. Функциональный анализ. - М. : Мир, 1975.

80. Гантмахер Ф.Р. Теория матриц. - М.: Наука, 1967. - 576 с.

81. Колмогоров А.Н., Фомин С В . Элементы теории функций ифункционального анализа. - М.: Наука, 1976. - 544 с.

82. Шепелев И.Г. Математические методы и модели управления встроительстве. - М . : Высш. школа, 1980. -213 с.

83. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. - М.:Наука, 1984.-320 с.

84. Беллман Р. Введение в теорию матриц. - М.: Мир, 1969.

85. Воеводин В.В. Линейная алгебра. - М . : Наука, 1980. -400 с.

86. Ланкастер П. Теория матриц. - М.: Наука, 1978. -308 с.

87. Стренг Г. Линейная алгебра и ее применение. - М.: Мир, 1980.412 с.

88. Габасов Р.Ф., Кириллова Ф.М. Основы динамического программирования. - Минск: Изд-во БГУ, 1975. - 264 с.

89. Ковалев М.М. Дискретная оптимизация. - Минск: Изд-во БГУ,1977.-191 с.

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

91. Мухначева Э.А., Рубинштейн Г.Ш. Математическое программирование. - Новосибирск: Наука, 1977. - 320 с.

92. Полак Э. Численные методы оптимизации. Единый подход.М. :Мир, 1974.-376 с.

93. Поляк Б.Т. Введение в оптимизацию.-М. : Наука, 1983.384 с.

94. Рихтер К. Динамические задачи дискретной оптимизации. - М.:Радио и связь, 1985. - 136 с.

95. Романовский И.В. Алгоритмы решения экстремальных задач.М.: Наука, 1977.-352 с.

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

97. Сачков В.Н. Введение в комбинаторные методы дискретной математики. - М.: Наука, 1982. - 384 с.

98. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. - Киев: Наукова думка, 1980.-274 с.

99. Трауб Дж., Вотьняковский X . Общая теория оптимальных алгоритмов. - М.: Мир, 1983.-384 с.

100. Харди Г.Г., Литтльвуд Дж. Е., Полна Г. Неравенства. - М.: ИЛ,1948.-456 с.

101. Черников С П . Линейные неравенства. - М.: Наука, 1968.488 с.

102. Ефимов Н.В,, Розендорн Э.Р. Линейная алгебра и многомернаягеометрия. - М.: Наука, 1970 . - 528 с.

103. Юдин Д.Б., Юдин А.Д. Математики измеряют сложность// Число и мысль. - Вып. 8. - М.: Знание, 1985, - 192 с.

104. Егоров Е.Е. О минимальной укладке дерева с закрепленнымивершинами// Дискретная математика. - №7. - 1997. - Т.9. - Вып.1. - С . 147-153.

105. Болотов A . A . О метрической кластеризации// Дискретная математика. Т.8. - Вып. 4. - М.: 1996. - 62-78.

106. Емеличев В.А., Кравцов М.К. О комбинаторных задачах векторной оптимизации// Дискретная математика. - 1995. - Т.7.- Вып. 1. 3-18. ПО. Супрунёнко Д.А. К задаче о назначениях// Изв. АН СССР. Сер. физ-мат. наук. - 1974. - №4. - 5-10.

107. Эллиот д . , Эрдеш П. Некоторые теоремы о пересечениях// Теория графов: покрытия, укладки, турниры. - М.: Мир, 1974. - 711.

108. Коган Д.И., Лиогонький М.И. Задача о назначениях с учетоминдивидуальных предпочтений// Кибернетика. - 1983. - №6. 80-84.

109. Ларин В.Я. Задачи распределения ресурсов в смешанных шкалах//Изв. Ан СССР. Техн. кибернет. - 1981. - №2. - 31-39.

110. Левин М.Ш. Применение оптимизационных комбинаторныхмоделей в автоматизированных системах// Обзорная инф. Сер. С

111. Автоматизированные системы проектирования и управления.М.: ВНИИТЭМР, 1986. - Вып. 1. - 64 с.

112. Левин М.Ш., Фуремс Е.М. Задача формирования портфеля заказов с учетом предпочтений ЛПР// Тез. докл. II Всес. конф. по статистическому и дискретному анализу нечисловой информации и экспертным оценкам. - М.: Таллин: ИПУ. ВНИИСИ, 1984. - 224-225.

113. Клейтман Д. Число скрещивании графа Кз^п // Теория графов:покрытия, укладки, турниры. - М.: Мир, 1974. - 151-159.

114. Раушенбах Г.В. Меры близости и сходства// Анализ нечисловойинформации в социологических исследованиях. - М.: ВНИИСИ, 1 9 8 5 . - С . 169-203.

115. Кемени Дж., Снелл Дж. Кибернетическое моделирование. - М.:Сов. радио, 1972.- 192 с.