20190075
S.O. Smerchinskaya, N.P. Yashina
Software and Information support and software for engineering education
В: Mrs Smerchinskaya,
Please answer the following question about your report in Inforino conference:
There are a lot of different methods such as AHP, ELECTRE, etc. and huge number of tools, which implement them. What is the advantage of your method and tool compared to existing ones?
Thank you
V. Latypova
О: Dear Mrs Latypova.
Thank you for your attention to our article.
The proposed system allows you to work with all types of incoming information and process a large amount of data, which is due to the small computational complexity of the algorithms.
В: Уважаемые авторы!
В секцию «Software and Information support and software for engineering education» поступил вопрос по докладу «Program System “Decision-making: Procedures on Graphs”»:
1. Поясните особенности работы студентов с разработанной программной системой. Каким образом студенты задают параметры модели и, в частности, E — множество экспертов и P — их индивидуальные предпочтения? Какие метрики M реализованы в системе?
С уважением,
сопредседатель секции №2
Варшавский П.Р.
О: Уважаемый Павел Романович!
Благодарим за интерес, проявленный к нашей работе!
Отвечаем на вопрос:
Запускаем систему. В появившемся окне пользователь (студент) вводит множество альтернатив (А), их имена, а в другом - множество экспертов (Е). Предусматривается добавление удаление альтернатив и экспертов. Для каждого эксперта вводится информация о его предпочтениях: попарное сравнение (ранжирование) (Р). Информация хранится в виде матриц смежности соответствующих графов (М).
Выбирается один из алгоритмов (r) принятия решений для построения агрегированного отношения предпочтения (матрица смежности).
Агрегированное предпочтение должно удовлетворять условию минимального суммарного расстояния до экспертных предпочтений. Расстояние между матрицами смежности определяется как расстояние Хэмминга
Текст доклада № 20190075
Program System “Decision-making: Procedures on Graphs”
Dear colleagues!
Let me introduce myself. My name is Светлана Смерчинская. My colleague and I are working at the Moscow Aviation Institute at the Department of Mathematical Cybernetics. We have developed the DECISION MAKING SYSTEM: PROCEDURES ON GRAPHS, which is used in the teaching of the disciplines Mathematical Theory of Decision Making and Discrete Mathematics.
The developed system allows us to demonstrate the applied value of graph theory procedures. When making decisions, the procedures on the graphs are used to choose the best alternatives from a given set or to order them by preference.
The software system contains both standard and developed by the authors algorithm.
Consider a simple example. The decision maker (father) asked each family member to compare cars in pairs. Having learned the preferences of all relatives, he built an aggregated RELATION from the conditions of a simple majority in preferences. Then he chose the best option for the car. The best options correspond to the NUCLEUS of the graph.
The profile of individual preferences of experts is set by binary relations on a set of alternatives. You need to order alternatives by preference or choose the best ones. First, we need to build an aggregated preference relation.
Each binary relation corresponds to a digraph ??. with vertices the alternatives and the arcs corresponding to the relation ??. We will set the relations with adjacency matrices of graphs.
An aggregated relation can be constructed using the majority rule. It is the majority graph. An arc is drawn in it if there is a positive difference in the preferences of experts. We introduce the concept of distance between preferences, as the Hamming distance between the corresponding adjacency matrices (presented by formula 1). Note that the Majority graph satisfies the condition of minimality of the total distance to expert preferences.
We will define relations by preference matrices: with elements are equivale if a_i is less preffered a_j, one-twelfth - if the alternatives are equivalent, and zero if a_j less preferred a_i or elements are not comparable.
A weighted majority graph is a digraph in which the weight of the arc is defined as the positive difference between the preferences of the experts. The matrix of weights of the majority graph can be determined by the proposed formula (2), using the difference of symmetric elements of the preference matrices.
Contradictory cycles are cycles in which there is an arc from the asymmetric part of the relation rho. Equivalent alternatives belong to the symmetric part of the relation.
We proposed an algorithm for constructing a non-contradiction relation, destroying cycles at ?_?.
We remove from the contradictory cycles all arcs with the least weight, that is, arcs with the minimum expert preference.
Take the transitive closure of the resulting relation.
The algorithm has a polynomial complexity equal to O(n power of third).
To select the best alternatives, it is convenient to use standard procedures for finding internally stable (the so-called independent) subsets of a graph. And externally stable subsets (the so-called dominant) by Magu method.
A subset that is both internally and externally stable forms the NUCLEUS of the graph, and it contains the best alternatives — this is a set of alternatives that are incomparable and dominate over others.
For example. The maximum internally stable set and the minimal externally stable sets. Hence, the nucleos of the graph is the 1st, 3rd, and 4th alternatives
To order the alternatives by preference in the graph without cycles, we use the Demukron algorithm – dividing graphs without cycles on the levels. For example
We have developed an algorithm for dividing a graph with cycles at the preference level. In fact, the problem is reduced to ordering by preference the components of the graph's strong connectivity. Any cycle belongs to the same preference level. For example Ordering the components of a graph's strong connectivity
The mathematical model of a software system contains the following elements
< t, A, E, K, P, M, G, k, r>,
t is the statement of the problem; And there are many alternatives, E there are many experts.
It is envisaged that instead of expert information, one can take verbal information about the preferences of alternatives according to quality criteria. K has many criteria;
P is the profile of individual expert preferences. Information is stored in the form of preference matrices of alternatives M. A set of G digraphs is mapped to preference relations.
The slide shows the logical diagram (дайграм) of the software system.
I’d like to finish by emphasising the main point(s).
We offer a software system DECISION-MAKING: PROCEDURES ON GRAPHS with standard graph procedures developed by the authors. The system is designed to study the disciplines of Mathematical Decision Making Theory and Discrete Mathematics.
Thank you for your attention!