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

ВВЕДЕНИЕ.

Глава 1. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ ЗАДАЧИ

ФОРМИРОВАНИЯ ЦЕЛЕВЫХ ГРУПП ИСПОЛНИТЕЛЕЙ

1.1 Содержательное описание ситуации формирования малых групп.

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

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

1.4 Полиномиально разрешимые случаи. Математическая модель процесса формирования целевых групп на 4-дольных графах.

1.5 Многокритериальная постановка задачи.

1.6 Использование методов надежности для анализа задачи о целевых группах.

Глава 2. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ КЛАССЫ

ВЕКТОРНЫХ ЗАДАЧ ФОРМИРОВАНИЯ ЦЕЛЕВЫХ ГРУПП

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

2.2 Алгоритмические проблемы и оценки сложности.

2.3 Полиномиальные алгоритмы нахождения полного множества альтернатив для 2-критериальных задач Т^ и 72.

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

3.1 Оценки сложности.

3.2 Методология подхода «алгоритмы с оценками».

3.3 Вычислительная схема приближенного полиномиального алгоритма А1.

3.4 Вероятностный анализ задачи

3.5 Оптимизация вычислений.

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

4.1 История вопроса и постановка проблемы.

4.2 Описание условий, для которых исследуется разрешимость с помощью алгоритма линейной свертки.

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

4.4 Исследование разрешимости с помощью алгоритма линейной свертки задачи формирования целевых групп с критериями вида М1ММАХ на 4-цветных графах.

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Основные новые результаты, полученные в диссертации, состоят в следующем:

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

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

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

- для каждого типового графа вычислена мера надежности успешной реализации организационной структуры, соответствующей данному типовому графу;

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

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

115

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

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

3. Вилкас Э.И., Майминас Е.З. Решения: теория, информация, моделирование. М.: Наука, 1982.-256с.

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

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

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

7. Горелик В.А., Ушаков И.А. Исследование операций. М.: Машиностроение , 1986г.-312с.

8. Гущенко К.Ф., Ковалев М.А. Правоохранительные органы. М. : Издательство БЕК, 1985. -237с.

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

10. Данильченко И.А., Мясников В.А., Четверяков В.Н. Автоматизированные системы управления предприятиями. М.: Машиностроение, 1984. -236с.116

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

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

13. Емеличев В.А. К оценке сложности многокритериальных транспортных задач // Докл. АН БССР. 1986. - Т. 30 , - №7. - С. 593596.

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

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

16. Емеличев В.А., Кравцов М.К., Янушкевич O.A. Условия парето -оптимальности в одной дискретной векторной задаче на системе подмножеств//ЖВМ и МФ . 1995. -Т.35, - №11. - С. 1641-1652.

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

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

19. Емеличев В.А., Перепелица В.А. К оценки сложности многокритериальных транспортных задач// Докл. АН БССР.- 1986.- Т. XXX, №7 .- С. 593-596.

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

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

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

23. Карзанов A.B. О максимальных паросочетаниях заданного веса в полных и полных двудольных графах// Кибернетика. 1987. -№1. -С. 7-11.

24. Инвестиционно финансовый портфель (Книга инвестиционного менеджера, книга финансового посредника)/ Отв. ред. Рубин Ю.Б., Солдаткин В.И. - М.: СОМИН - ТЭК, 1993. -478с.

25. Карлин С. Математические методы в теории игр, программировании в экономики .- М.: Наука, 1987. 578с.

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

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

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

29. Кочкаров A.M., Перепелица В.А. Многокритериальная задача покрытия графа цепями большой и малой длины// Вести АН БССР. Сер. физ. мат. наук. - 1985. - №5. -С. 39-44.

30. Кочкаров A.M., Перепелица В.А. Вероятностный анализ одной многокритериальной задачи теории графов// Вести АН БССР. Сер. физ. мат. наук. - 1987. - № 2. - С. 65-66.

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

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

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

34. Лупанов О.Б. О методах получения оценок сложности и вычисления индивидуальных функций// Дискр. анализ. 1974. - Вып. 25. - №1. -С. 7-11.

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

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

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

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

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

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

41. Перепелица В.А., Максишко Н. О многокритериальной задаче покрытия ориентированного графа контурами//Там же. С.97-98.

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

43. Перепелица В.А., Петова Е.Х. Исследование отношений подчиненности в математических моделях формирования целевых групп исполнителей. В сб. «Математическое моделирование и120компьютерные технологии» . Нижний Архыз : РАН CAO, 1999. -С. 1-7.

44. Перепелица В.А., Петова Е.Х., Магометов А.З. Курс лекций по правовой информатики. Черкесск: КЧТИ, 1997. -45с.

45. Петова Е.Х. Исследование методов надежности для анализа задачи о целевых группах. В сб. Труды 2 научной конференции факультета «Бизнеса и права»,- Черкесск: Карачаево Черкесский Государственный Технологический институт, 1999. - Т.З. -С. 21-22.

46. Петова Е.Х. Математические методы и модели формирования целевых групп исполнителей. Черкесск: Карачаево - Черкесский Государственный технологический институт, 1999. - 31с. -Деп. в ВИНИТИ РАН.

47. Петова Е.Х. Покрытие цепями N-взвешенного графа. «Математическое моделирование и компьютерные технологии». Материалы II международного научного симпозиума «Экономика и право стратегии 3000» 24-26 апреля, Кисловодск 1997. - С.79

48. Петова Е.Х. Статистически эффективный алгоритм для векторной задачи покрытия графа цепями. Тез. докл. второй научной конференции КЧТИ. Черкесск: КЧТИ, 1997. С. 53-54121

49. Петова Е.Х. Вычислительная сложность покрытия N-взвешенного графа цепями. Тез. науч. практ. конф. препод, и аспирантов КЧТИ: - Черкесск: КЧТИ, 1995г. - С.45.

50. Петова Е.Х. Полиномиально разрешимые случаи задачи формирования целевых групп. Тез. докл. Международной конференции «XXIII Гагаринские чтения». М.: МАИ, 1999.

51. Петова Е.Х. Проблема нахождения множества альтернатив для многокритериальной задачи формирования целевых групп. Препринт №133Т,- Нижний Архыз: РАН CAO., 1999. С.1-13

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

53. Полевой Н.С. Правовая информатика и кибернетика. М.: Юрид. Лит., 1993г.- 543с.

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

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

56. Столяренко Л.Д. Основы психологии. Ростов на Дону.- Изд. «Феникс», 1997. - 736с.

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

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

59. Тарьян Р.Э. Сложность комбинаторных алгоритмов// Кибернет. сб. Нов. сер. 1980. - Вып. 17. -С. 61-113.

60. Темирбулатов П.И. Статистически эффективный алгоритм для задачи о трисочетаниях на 3-цветном графе// Тезисы докладов на Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии». Кисловодск.: 1997.-С. 102-104.

61. Хартманис Дж., Хопкрофт Дж. Обзор теории сложности вычислений// Кибернет. сб. Нов. сер. 1974. - Вып. 11. -С. 131 - 176.

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

63. Черкасский Б.В. Новый алгоритм генерации остовных деревьев // Кибернетика. 1987. - №1. - С. 85-89.

64. Шереги В.А., Горшков М.К. Основы прикладной социологии Т.1, Т.2 . М.: Ред. - изд. Фирма «academia», 1995г.

65. Brucker P. Discrete parametr optimization problem and essential efficient points// Operat. Res. (1972). V.16, №5,- P. 189-197.

66. Burkhard R.E., Keiding H., Krarup J,. Prnzan P.M. A relationship between optimality and efficiency in multicriteria 0-1 programming123problems// Computers & Options Research, 1981, V.8, N4.-P. 241247.

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

68. Edmonds J., Fulkerson D.R. Bottleneck extremal//J.Cjmbin. Theory,-1970, 8,№8.-P. 299-306.

69. Chaos Theory in Economics: Methods, Models and Evidnce, Edited by Dechert W.D., Edward Elgar, 1996.

70. Charnes A., Cooper W.W. Management Models and industrial Application of Linear Programming N.Y.; Wijeley, 1961.

71. Emelichev V.A., Perepeliza V.A. Complexite of vector optimization problems on graphs// Optimization, 1991, V. 22, №6. P. 903-918.

72. Hamacher H.W., Rendl F. Color consrained combinatorial optimization problem//Oper. Res. Letters, 1991, V. 10, №4, pp. 211219.

73. Koopmans T.C. Activity analysis of production, N.-Y, Wijey, 1951.

74. Steuer R. Multicriteria optimization. N.-Y, Wijey, 1985.

75. Wald A. Contributions to theory of statistical estimation and testing hypothesis. Ann Math. Statist. (1985) 46,№1. C. 79-86.