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

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

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

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

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

Содержание

  • Глава 1. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ ЗАДАЧИ ФОРМИРОВАНИЯ ЦЕЛЕВЫХ ГРУПП ИСПОЛНИТЕЛЕЙ
    • 1. 1. Содержательное описание ситуации формирования малых групп
    • 1. 2. Исследование отношений подчиненности в математических моделях формирования целевых групп исполнителей
    • 1. 3. Оценки сложности векторной задачи формирования целевых групп
    • 1. 4. Полиномиально разрешимые случаи. Математическая модель процесса формирования целевых групп на 4-дольных графах
    • 1. 5. Многокритериальная постановка задачи
    • 1. 6. Использование методов надежности для анализа задачи о целевых группах
  • Глава 2. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ КЛАССЫ ВЕКТОРНЫХ ЗАДАЧ ФОРМИРОВАНИЯ ЦЕЛЕВЫХ ГРУПП
    • 2. 1. Общая математическая постановка проблемы дискретной многокритериальной оптимизации
    • 2. 2. Алгоритмические проблемы и оценки сложности
    • 2. 3. Полиномиальные алгоритмы нахождения полного множества альтернатив для 2-критериальных задач Т^ и
  • Глава 3. АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ ЗАДАЧИ ПОКРЫТИЯ ТИПОВЫМИ ГРАФАМИ Н
    • 3. 1. Оценки сложности
    • 3. 2. Методология подхода «алгоритмы с оценками»
    • 3. 3. Вычислительная схема приближенного полиномиального алгоритма А
    • 3. 4. Вероятностный анализ задачи
    • 3. 5. Оптимизация вычислений
  • Глава 4. ИССЛЕДОВАНИЕ РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМА ЛИНЕЙНОЙ СВЕРТКИ ЗАДАЧИ ФОРМИРОВАНИЯ ЦЕЛЕВЫХ ГРУПП ИСПОЛНИТЕЛЕЙ
    • 4. 1. История вопроса и постановка проблемы
    • 4. 2. Описание условий, для которых исследуется разрешимость с помощью алгоритма линейной свертки
    • 4. 3. Исследование разрешимости с помощью алгоритма линейной свертки задачи формирования целевых групп с критериями вида М^вЫМ на 4-цветных графах
    • 4. 4. Исследование разрешимости с помощью алгоритма линейной свертки задачи формирования целевых групп с критериями вида М1ММАХ на 4-цветных графах

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

  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. — С. 593 596.
  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−54 121
  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. 241 247.
  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. 211 219.
  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.
Заполнить форму текущей работой

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