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

Введение

1. Принятие решений в нечеткой среде

1.1. Нечеткое описание задач принятия решений

1.2. Использование нечеткого линейного программирования для принятия решений

1.2.1. Симметричные модели

1.2.2. Несимметричные модели

1.2.3. Расширение нечеткого линейного программирования

1.3. Многокритериальное принятие решений в нечеткой среде

1.3.1. ПР нечетких условиях при нескольких целевых функциях

1.3.2. Мультиатрибутное ПР в нечетких условиях

1.4. Выводы

2. Влияние нечеткой информации при принятии решений

2.1. Основные понятия и определения

2.1.1. Понятие принадлежности

2.1.2. Понятие нечеткого подмножества

2.1.3. Нечеткая величина и нечеткий интервал

2.2. Операции над нечеткими числами

2.2.1. Теоретико-множественные операции

2.2.2. Арифметические операции

2.3. Сравнение нечетких чисел

2.3.1. Отношение порядка на множестве нечетких чисел

2.3.2. Индексы ранжирования нечетких чисел

2.3.3. Сравнение средних значений нечетких чисел

2.3.4. Методы сравнения нечетких треугольных чисел

2.4. Операции с лингвистическими переменными

2.4.1. Операции суммирования и вычитания лингвистических переменных

2.4.2. Операции над множествами лингвистических переменных

2.4.3. Сравнение множеств лингвистических переменных

2.5. Выводы

3. Использование нечетких двудольных графов в качестве модели решения задач ЛП с нечеткими данными

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

3.1.1. Понятие степени двудольности графа

3.1.2. Число возможных двудольных частей в нечетком графе

3.1.3. Оценки степени двудольности нечеткого графа

3.1.4. Алгоритмы построения максимальной двудольной части нечеткого графа

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

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

3.2.2. Матричная форма алгоритма

3.2.3. Алгоритм нахождения совершенного паросочетания в нечетком двудольном графе

3.3. Выводы

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

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

4.1.1. Постановка задачи 11 б

4.1.2. Нечеткие данные, представленные в виде нечетких треугольных чисел

4.1.3. Нечеткие данные, представленные в виде нечетких чисел с колоколообразной функцией принадлежности

4.1.4. Нечеткие данные, представленные в виде лингвистических переменных

4.1.5. Задача о назначениях с нечеткими данными

4.2. Многокритериальная транспортная задача с нечеткими данными

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

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

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

4.3.1. Вид процентов

4.3.2. Выбор инвестиций

4.3.3. Нечеткая ситуационная модель

4.4. Оптимизация использования ресурсов при нечетких нормах расхода сырья

4.5. Выводы

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

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

Указанная цель достигается путем решения следующих задач:

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

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

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

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

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

На защиту выносятся следующие результаты:

1. Методы сравнения нечетких данных, основанные на сравнении средних значений нечетких чисел, центров тяжести нечетких треугольных чисел и средних арифметических средних значений интервалов достоверности.

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

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

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

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

Практическую ценность работы представляют:

1) алгоритм и программа выделения нечетких двудольных частей в нечетком графе;

2) алгоритм и программа решения транспортной задачи с нечеткими исходными данными при одном и нескольких критериях оптимизации.

Реализация результатов работы. Результаты диссертации внедрены в Южнороссийском региональном кадастровом центре «Земля» (г. Таганрог), что подтверждается соответствующим актом.

Апробация работы. Основные результаты диссертации представлены на V и VI Европейских конгрессах по нечетким интеллектуальным технологиям и программному обеспечению EUFIT'97 (Aachen, Germany, 1997 г.) и EUFIT'98 (Aachen, Germany, 1998 г.), на всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1997 г.), на межгосударственной научно-практической конференции «Проблемы проектирования и управления экономическими системами» (Ростов, 1998 г.), на XXV Международной конференции «Новые информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Ялта-Гурзуф, Украина, 1998 г.), на Международной конференции

Математика в индустрии» (Таганрог, 1998 г.), на IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 1998 г.).

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

Структура и объем диссертационной работы. Диссертация состоит из введения и четырех глав, заключения, списка литературы из 77 наименований и приложений. Текст диссертации изложен на 178 страницах, включая 41 рисунок, 18 таблиц и 14 страниц приложений.

4.5. Выводы

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

2). Результаты применения венгерского алгоритма для решения ТЗ с нечеткими данными показали адекватность приведенного в данной работе алгоритма, т.к. результаты вычислений совпадают с результатами вычислений, производимых с помощью 88-метода для нечетких данных, описанного в литературе.

3). Решена многокритериальная транспортная задача с нечеткими данными, заданными в различных представлениях.

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

Заключение

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

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

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

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

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

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

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

1. Поспелов Д.А. Ситуационное управление: теория и практика. М.: Наука, 1982 г. - 320 с.

2. Заде JI. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976 г. - 168 с.

3. R.E. Bellman, L.A. Zadeh. Decision-making in a fuzzy environment. // Management Science. 1970. - Vol. 17. - P. 141-164.

4. H.-J. Zimmermann. Application of Fuzzy Set Theory to Mathematical Programming. // Information Sciences. 1985. - Vol. 36. - P. 29-58.

5. H.-J. Zimmermann Fuzzy Sets Theory and its applications. Boston/Dordrecht/London: Kluwer Academic Publishers, 1996. - 435 p.

6. L.A. Zadeh. On fuzzy algorithms. Univ. of California, Berkley, 1972.

7. S.A. Orlovsky. On programming with fuzzy constraint sets. // Kybernetes. 1977. -Vol. 6.-P. 197-201.

8. H. Tanaka, T. Okuda, K. Asai. On fuzzy mathematical programming. // J. Cybern. -1974.-Vol. 3.-P. 37-46.

9. В. Werners. Interaktive Entscheidungsunterstuetzung durch ein flexibles mathematisches Programmierungssystem, Muenchen, 1984.

10. S. Chanas The use of parametric programming in fuzzy linear programming. // Fuzzy sets and Systems. 1983. - Vol. 11. - P. 243-251.

11. H.-J. Zimmermann, P. Zysno, Latent connectives in human decision making. // Fuzzy sets and Systems. 1980. - Vol. 4. - P. 37-51.

12. E.L. Hannan. Linear programming with multiple fuzzy goals. // Fuzzy sets and Systems. 1981. - Vol. 6. - P. 235-248.

13. K. Nakamura. Some extension of fuzzy linear programming. // Fuzzy sets and Systems -1981.-Vol. 15.-P. 132-143.

14. H.-L. Li, C.-S. Yu. Comments on Fuzzy programming with nonlinear membership functions. // Fuzzy sets and Systems 1999. -Vol. 101. - P. 289-292.

15. Yang. Fuzzy programming with nonlinear membership functions. // Fuzzy sets and Systems 1991.-Vol. 41.

16. H. Leberling. On finding compromise solutions in multicriteria problems using the fuzzy min-operator. // Fuzzy sets and Systems 1981. - Vol. 6. - P. 105-118.

17. H. Hamacher. Ueber logische Aggregationen nicht binaer expliziter Entscheidungskriterien. Frankfurt/Main, 1978.

18. U. Thole, H.-J. Zimmermann, P. Zysno. On the suitability of minimum and product operators for the intersection of fuzzy sets. // Fuzzy sets and systems. 1979. - Vol.2. -P. 167-180.

19. H.-J. Zimmermann, P. Zysno. Decisions and evaluations by hierarchical aggregation of information. // Fuzzy sets and Systems 1983. - Vol. 10. - P. 243-266.

20. Giles R. Lukasiewicz logic and fuzzy theory. // Int. J. Man.-Mach. Stud. 1976. - Vol. 8.-P. 313-327.

21. Zadeh L. A. Fuzzy sets. // Inform. Control 1965. - Vol. 8. - P. 338-353.

22. Mizumoto M. Fuzzy sets and their operations. // Inform. Control. 1982. - Vol. 50. -P. 160-174.

23. Dubois D., Prad H. Systems of linear fuzzy constraints. // Fuzzy sets and systems. -1980.-Vol.3.-P. 37-48.

24. Dubois D., Prad H. A class of fuzzy measures based on triangular norms. // Int. J. Gen. Syst.- 1982.-Vol. 8.-P. 43-61.

25. Silvert W. Symmetric summation: A class of operations on fuzzy sets. // IEEE Trans. Sys. Man. Cybernet. 1979. - Vol. 9. - P. 657-659.

26. Yager R.R. On a general class of fuzzy connectives. // Fuzzy sets and systems. -1980. -Vol. 4.-P. 235-242.

27. Yager R.R., Rybalov A. Noncommutative self-identity aggregation. // Fuzzy sets and systems. 1997. - Vol. 85. - P. 73-82.

28. Ralescu A.L., Ralescu D.A. Extensions of fuzzy aggregation. // Fuzzy sets and systems. 1997. - Vol. 86. - P. 321-330.

29. Kuhn H.W., Tucker A.W. Nonlinear programming. // Proc. 2nd Berkeley Symp. Math. Stat. Prob. 1951. - P. 481-492.

30. Кини P., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981 г. - 560 с.

31. Chames A., Cooper W.W. Management Models and Industrial Applications of Linear Programming. New York, 1961.

32. Dyer J.S. Interactive goal programming. // Management Science. 1973. - Vol. 19. -P. 62-70.

33. Negota C.V., Minoiu S., Stan E. On considering imprecision in dynamic LP. // ECECSR. 1976. - Vol. 3. - P.83-95.

34. Kacprzyk J., Orlowsky S.A. Optimization Models Using Fuzzy Sets and Possibility Theory. Dodrecht, Boston, 1987.

35. Wang H.-F., Wang M.-L. A fuzzy multiobjective linear programming. // Fuzzy Sets and Systems. 1997. - Vol. 86. - P. 61-72.

36. Tanaka H., Asai K. Fuzzy linear programming problems with fuzzy numbers. // Fuzzy Sets and Systems. 1984. - Vol. 13. - P. 1-10.

37. Ramik J., Rimanek J. Inequality relation between fuzzy numbers and its use in fuzzy optimization. // Fuzzy Sets and Systems. 1985. - Vol. 16. - P. 123-138.

38. Guu S.-M., Wu Y.-K. Weighted coefficients in two-phase approach for solving the multiple objective programming problems. // Fuzzy Sets and Systems. 1997. - Vol. 85.-P. 45-48.

39. H.-J. Zimmermann. Fuzzy programming and linear programming with several objective functions. // Fuzzy sets and systems. 1978. - Vol.1. - P. 45-55.

40. Sakawa M., Yano H. An interactive satisficing method for multi-objective nonlinear programming problems with fuzzy parameters. // In Kacprzyk J. and Orlowsky S.A. -1987.-P. 258-271.

41. Sakawa M., Kato K. Interactive decision making for large-scale multiobjective linear programs with fuzzy numbers. // Fuzzy sets and systems. 1997. - Vol. 88. - P. 161-172.

42. Tanaka H., Ishihashi H., Asai К. A value of information in FLP problems via sensitivity analysis. // Fuzzy Sets and Systems. 1986. - Vol. 18. - P. 119-129.

43. Hulsurkar S., Biswal M.P., Sinha S.B. Fuzzy programming approach to multi-objective stochastic linear programming problems. // Fuzzy sets and systems. 1997. -Vol. 88.-P. 173-181.

44. Buckley J.J. Possibility and necessity in optimization. // Fuzzy Sets and Systems. -1988.-Vol. 25.-P. 1-13.

45. Buckley J.J. Possibilistic linear programming with triangular fuzzy numbers. // Fuzzy Sets and Systems. 1988. - Vol. 26. - P. 135-138.

46. Yager R.R. Fuzzy decision making including unequal objectives. // Fuzzy Sets and Systems. 1978. - Vol. 1. - P. 87-95.

47. Baas M.S., Kwakernaak H. Rating and ranking of multiple-aspect alternatives using fuzzy sets. // Automatica. 1977. - Vol.13. - P. 47-58.

48. Saaty Th.L. Exploring the interface between hierarchies, multiple objectives and fuzzy sets. // Fuzzy Sets and Systems. 1978. - Vol. 1. - P. 57-68.

49. Gogus O., Boucher Т.О. A consistency test for rational weights in multi-criterion decision analysis with fuzzy pairwise comparisons. // Fuzzy Sets and Systems. 1997. -Vol. 86.-P. 129-138.

50. C. Chen, C.M. Klein. An efficient approach to solving fuzzy MADM problems. // Fuzzy Sets and Systems. 1997. - Vol. 88. - P. 51-67.

51. Кофман А., Хил Алуха X. Введение теории нечетких множеств в управление предприятиями: пер. с испанского. Минск: Выш. шк., 1992 г.

52. Кофман А. Введение в теорию нечетких множеств. / Пер. с франц. В.Б. Кузьмина; Под ред. С.И. Травкина. М.: Радио и связь, 1982 г. - 432 с.

53. Дюбуа Д., Прад А. Теория возможностей. / Перевод с франц. М.: Радио и связь, 1990.-328 с.

54. Мелихов А.Н., Берштейн JI.C., Коровин С .Я. Ситуационные советующие системы с нечеткой логикой. М.: Наука, 1990 г. - 271 с.

55. Калмыков С.А., Шокин Ю.И. Методы интервального анализа. Новосибирск: Наука, 1986 г.-234 с.

56. Борисов А. Н., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей. Примеры использования. Рига: Зинатне, 1990 г. - 184 с.

57. Борисов А.Н., Алексеев А.В. и др. Обработка нечеткой информации в системах принятия решений. М.: Радио и связь, 1989 г. - 304 с.

58. Baldwin J.F., Guild N. Comparison of Fuzzy Sets on the same Decision Space. // Fuzzy Sets and Systems. 1979. - Vol. 2. - P. 213 - 231.

59. Yager R.R. A Procedure for Ordering Fuzzy Subset of the Unit Interval. // Inform. Science. -1981.-Vol. 24.-P. 143-161.

60. Модели принятия решений на основе лингвистической переменной. / А.Н. Борисов, А.В. Алексеев, О.А. Крумберг и др. Рига: Зинатне, 1982. - 256 с.

61. Попов В.А. Аналитическое выполнение арифметических операций над нечеткими числами. / Тезисы докладов Всесоюз. науч. семинара «Модели выбора альтернатив в нечеткой среде». Рига: Риж. политехи, ин-т, 1980. - с. 14-15.

62. Dubois D., Prad Н. Ranking Fuzzy Numbers in the Setting of Possibility Theory. // Inform. Science. 1983. - Vol. 30, N3. - p. 183 - 224.

63. Tong R.M., Bonissone P.P. Linguistic Approach to Decision-Making with Fuzzy Sets. / IEEE Trans. On Systems, Management and Cybernetics. 1981. - Vol. 10, N1. - P. 716- 723.

64. Wang X., Kerre E.E. On Robustness and Sensitivity of an Ordering Index. // Proceedings ofEUFIT'97, Aachen, Germany. 1997. - Vol. 1. - P. 20-23.

65. Берштейн JI.C., Дзюба T.A. Определение совершенного паросочетания в нечетком двудольном графе Математика в индустрии. // Труды Международной конференции. Таганрог: ТГПИ, 1998 г. - с. 51-53.

66. H.-J. Zimmermann. Fuzzy Sets Theory and its applications. Boston/Dordrecht/London: Kluwer Academic Publishers, 1991. 399 p.

67. Ope О. Теория графов. M.: Наука, 1980 г. - 356 с.

68. Берштейн JI.C., Дзюба Т.А. Выделение оптимальной двудольной части в нечетком графе. // Сборник трудов XXV международной конференции IT&SE'98. Ялта-Гурзуф, 1998. с. 55-62.

69. Кристофидес Н. Теория графов. М.: Мир, 1978 г. - 432 с.

70. Bershtein L.S., Dzuba Т.А. Construction of a spanning subgraph with ordered degrees in the fuzzy bipartite graph. / Proceedings of EUFIT'98, Aachen, Germany. p. 47-51.

71. Линейное и нелинейное программирование. / Под ред. И.Н. Ляшенко. Киев: Вища школа, 1975 г.

72. Дзюба Т. Решение транспортной задачи с исходными данными, представленными в виде лингвистических переменных. // Сборник тезисов докладов IV Всероссийской научной конференции студентов и аспирантов. -Таганрог: ТРТУ, 1998 г. с. 275-276.

73. Дзюба Т.А. Многокритериальное принятие решений в задаче о назначениях. // Сборник тезисов докладов первой всероссийской конференции молодых ученых и аспирантов. Таганрог: ТРТУ, 1998 г.

74. Dzuba Т. Optimization of a choice of the object of the investments with the help of fuzzy situational model. // Proceedings of EUFIT'97, Aachen, Germany. 1997. -Vol. 3.-P. 2449-2452.

75. Дзюба Т. Выбор и ранжирование эталонных ситуаций для нечеткой модели принятия решений в задаче о капиталовложениях. // Работы Всероссийской научно-технической конференции. ТРТУ, 1997. с. 34-36.

76. Орлова И.В., Горчаков А.А. Компьютерные экономико-математические модели. М.: Компьютер, ЮНИТИ, 1995 г. - 136 с.