Entscheidungen treffen. Beispiel

Wenn ich das Thema fortsetze, werde ich sagen, dass ich mir die Veröffentlichungen anderer Habr-Autoren zu diesem Thema angesehen habe. Es besteht Interesse an Problemen, aber niemand möchte in die Theorie einsteigen. Benimm dich wie Pionierentdecker. Es wäre großartig, wenn sie neue Ergebnisse und Erfolge erhalten würden, aber niemand strebt danach.



Tatsächlich stellt sich jedoch heraus, dass es schlimmer ist als bereits bekannt, viele Faktoren werden nicht berücksichtigt, die Ergebnisse der Theorie werden dort verwendet, wo dies nicht empfohlen wird, und im Allgemeinen sieht alles nicht sehr ernst aus, obwohl Habr, wie es verstanden werden sollte, dies nicht anstrebt. Leser können und sollten nicht als Filter fungieren.

Die ursprünglichen Alternativen, ihre Messung und Bewertung

Es ist bekannt, dass die Probleme, eine Lösung zu finden, nur in Situationen mit mehreren Alternativen der Wahl auftreten. Um eine Entscheidungssituation zu betrachten, ein spezifisches Entscheidungsproblem (DP) zu formulieren, eine Methode zur Lösung zu wählen, ist es notwendig, erste Informationen über Alternativen zu haben, eine Präferenzbeziehung.



Lassen Sie uns im Unterabschnitt zeigen, welche Methoden es gibt, um es zu erhalten. Alternativen haben viele Eigenschaften (Merkmale), die die Entscheidung beeinflussen. Beispielsweise können Indikatoren für Eigenschaften von Objekten (Gewicht, Volumen, Härte, Temperatur usw.) quantitativ oder qualitativ sein.



Eine Eigenschaft der Menge von Alternativen aus Ω sei durch eine Zahl ausgedrückt, dh es existiert eine Abbildung ψ: Ω → E1, wobei E1 die Menge der reellen Zahlen ist. Dann wird eine solche Eigenschaft durch einen Indikator charakterisiert, und die Zahl z = ψ (x) wird als Wert (Schätzung) der Alternative in Bezug auf den Indikator bezeichnet.



Um Alternativen zu bewerten, müssen die Indikatoren gemessen werden.



Definition. Unter der Messung eines Indikators einer bestimmten Eigenschaft versteht man das Zuweisen von numerischen Werten zu einzelnen Ebenen dieses Indikators in bestimmten Einheiten. In diesem Fall ist die Wahl der Maßeinheit wichtig.



Wenn beispielsweise das Volumen eines bestimmten Teils des Behälters zuerst in Kubikmetern und dann in Litern gemessen wird, ändert sich das Wesen des Indikators nicht. Nur die Anzahl der Einheiten ändert sich. Diese Eigenschaftsmetriken können skaliert, multipliziert oder durch einen konstanten Wert für die Eigenschaftsmetrik geteilt werden.



Andererseits gibt es Eigenschaften, deren Indikatoren eine solche Manipulation ihrer Werte nicht zulassen. Der Erwärmungsgrad von Körpern wird durch die Temperatur charakterisiert und in Grad gemessen. Mit dem Wert dieses Indikators + 10 ° und –15 ° allow kann nicht beurteilt werden, wie oft der Körper mit einer Temperatur von + 10 ° more stärker erwärmt wird als ein Körper mit einer Temperatur von –15 °



Aus diesen Beispielen kann (und ist wichtig) geschlossen werden, dass sich die Indizes Volumen und Temperatur auf verschiedene Arten von Eigenschaften beziehen, über deren Werte von z = ψ (x) bestimmte Transformationen f (z) = f (ψ (x)) zulässig oder unzulässig sind ...



Der Satz zulässiger Transformationen f (z) wird nämlich als Grundlage für die Bestimmung des Typs der Skala verwendet, in der der Indikator eines bestimmten Attributs (einer bestimmten Eigenschaft) gemessen wird. Wenn wir die eine oder andere Messung des Indikators eines vom Forscher hervorgehobenen Merkmals durchführen, kommen wir zu der Aufgabe, die Art der Skala zu bestimmen, in der die Messung durchgeführt werden soll.



Ohne dieses Problem richtig zu lösen, können wir zugeben, dass die Ergebnisse von Beobachtungen (Messungen) bei der Verarbeitung falsch behandelt werden. Dies geschieht, wenn die Werte der Indikatoren Transformationen unterzogen werden, die außerhalb des für einen bestimmten Skalentyp zulässigen Transformationssatzes vorgenommen wurden.



Definition. Eine Messskala ist eine Folge von gleichnamigen Werten verschiedener Größen, die nach Vereinbarung akzeptiert werden.

Lassen Sie uns die wichtigsten Arten von Skalen genauer betrachten.







1. Nominalskalen . Nominalskalen werden verwendet, wenn ein Forscher sich mit Objekten befasst, die durch bestimmte Merkmale beschrieben werden. Abhängig davon, ob ein bestimmtes Objekt einen bestimmten Wert eines Features hat oder nicht, wird das Objekt auf die eine oder andere Klasse verwiesen.



Wenn es sich beispielsweise um Personen handelt, können Sie mit dem Wert des Features (die Skala des Features wird aus zwei Geschlechtswerten gebildet: männlich und weiblich) jede Person eindeutig einer bestimmten Klasse zuordnen. Aus diesem Grund wird die Skala als Bewertungsskala bezeichnet. Ein solches Zeichen als Beruf ermöglicht es, eine Person beispielsweise als Lehrer, Zimmermann oder auf andere Weise gemäß dem Wert des Berufsindikators zu bezeichnen.



Die Skala wird in diesem Fall durch die Namen aller Berufe gebildet. Offensichtlich wird auf dieser Skala Null nicht angegeben, obwohl das Fehlen eines Berufs in dem Fach es ihm ermöglicht, genau der Kategorie von Personen ohne Beruf zugeordnet zu werden. Die Namen der Berufe sind in dieser Größenordnung in keiner Weise geordnet, obwohl sie der Einfachheit halber häufig alphabetisch geordnet sind.



Aufgrund dieser Überlegungen wird eine solche Skala als Benennungsskala bezeichnet.

Gültige Transformationen von Werten in dieser Skala sind alle Eins-zu-Eins-Funktionen: f (x) ≠ f (y) <=> x ≠ y.



2. Ordnungsskalen . Wenn sich das untersuchte Merkmal, zum Beispiel die Härte des Materials, in Objekten unterschiedlich manifestiert und Werte aufweist, die nicht spezifisch gemessen werden können, aber man die vergleichende Intensität seiner Manifestation für zwei beliebige Objekte eindeutig beurteilen kann, dann sagen sie, dass der Wert des Merkmals auf einer Ordnungsskala gemessen wird. Ein klassisches Beispiel hierfür ist die Härte von Mineralien. Der Referenzpunkt ist 0 auf der Skala ist nicht definiert.



Der charakteristische Wert ist wie folgt definiert. Das härtere Mineral des fraglichen Paares hinterlässt einen Kratzer auf dem anderen. Alle Mineralien gemäß den Werten dieses Merkmals können wie folgt geordnet werden: Das erste ist am wenigsten hart, das zweite ist härter, es hinterlässt nur beim ersten einen Kratzer, das dritte hinterlässt einen Kratzer bei den ersten beiden usw.



Der Unterschied zwischen der Ordnungsskala und dem Nominalwert besteht darin, dass die Werte des Merkmals aussortiert werden können. während die Werte auf der Nennskala nicht einmal bestellt werden können. Der Nachteil einer Ordnungsskala ist, dass sie nicht proportional ist.



Es ist unmöglich zu beantworten, wie viel oder wie oft ein Mineral härter ist als ein anderes. Die zulässigen Transformationen der Ordnungsskala bestehen aus allen monoton ansteigenden Funktionen mit der Eigenschaft: x ≥ y => f (x) ≥ f (y).



3.Intervallskala (Intervall). unterscheiden sich von den Ordnungsskalen darin, dass für die von ihnen beschriebenen Eigenschaften nicht nur die Äquivalenz- und Ordnungsbeziehungen sinnvoll sind, sondern auch die Summe der Intervalle (Unterschiede) zwischen verschiedenen quantitativen Manifestationen von Eigenschaften. Ein typisches Beispiel ist die Zeitintervallskala.



Zeitintervalle (z. B. Arbeitsperioden, Lernperioden) können addiert und subtrahiert werden, aber das Hinzufügen der Daten von Ereignissen ist bedeutungslos.



Ein weiteres Beispiel ist die Skala der Längen (Abstände) - räumlichen Intervalle, indem die Null des Lineals an einem Punkt ausgerichtet wird und das Lesen an einem anderen Punkt erfolgt. Diese Art von Skala umfasst auch die Temperaturskalen Celsius, Fahrenheit, Reaumur.



In diesen Skalen sind lineare Transformationen zulässig (x - y) / (z - v); x ∓ y; Sie wenden Verfahren an, um die mathematische Erwartung, die Standardabweichung, den Asymmetriekoeffizienten und die verschobenen Momente zu ermitteln.



4. Differenzskala (Punkt) Differenzskalen unterscheiden sich von Ordnungsskalen dadurch, dass die Intervallskala bereits beurteilt werden kann, dass nicht nur die Größe größer als eine andere ist, sondern auch, um wie viel größer dies im Wesentlichen dieselbe absolute Skala ist, sondern dass ihre Werte um verschoben werden ein Wert relativ zu den absoluten Werten (x - y) <(z - v); x ∓ y;



5. Beziehungsskala... Die Skala, für die die Menge der zulässigen Transformationen aus allen Ähnlichkeitstransformationen besteht, wird als Skala der Beziehungen bezeichnet. Der Referenzpunkt ist auf dieser Skala festgelegt und die Messskala kann dafür geändert werden.



Lassen Sie diese Skala die Länge eines Objekts messen. In diesem Fall können Sie von der Messung in Metern zur Messung in Zentimetern wechseln und die Maßeinheit um das 100-fache verringern. In diesem Fall ändert sich offensichtlich das Verhältnis der Längen L (A) und L (B) zweier Objekte A und B, gemessen in denselben Einheiten, nicht, wenn die Einheiten geändert werden.



Die in dieser Skala gemessenen Werte des Indikators des Merkmals ermöglichen es,

die Frage zu beantworten, wie oft sich das Merkmal in einem Objekt intensiver manifestiert als in einem anderen. Zu diesem Zweck ist es notwendig, das Verhältnis der Werte L (A) / L (B) = k zu berücksichtigen.



Wenn das Verhältnis größer als eins ist (k> 1), ist der Wert des Attributindikators für das erste Objekt A k-mal größer als der für B, wenn k <1 ist, ist der Wert des Attributindikators für Objekt B 1 / k-mal größer als der für A. ist Multiplikation mit einer positiven ganzen Zahl und nur das.



6. Absolute Skala . Die einfachste aller Skalen ist eine Skala, die nur eine Transformation f (x) = x erlaubt. Diese Situation entspricht der einzigen Möglichkeit, den Indikator für die Eigenschaft eines Objekts zu messen, nämlich einer einfachen Nachzählung von Objekten.



Diese Skala wird als absolute Skala bezeichnet. Wenn wir das Objekt x registrieren, interessiert uns nichts anderes als dieses Objekt. Die absolute Skala kann als eine bestimmte Implementierung einiger anderer Skalen betrachtet werden.

Entscheidungsaufgabe. Eine Matrix von Beziehungen erhalten

Wir listen die möglichen Einstellungen des ZPR auf, darunter:

• lineare Reihenfolge der Alternativen (die Spitze in der Kette ist die beste);
• Hervorheben der besten Alternative;
• Hervorheben einer (ungeordneten) Teilmenge der besten Alternativen;
• Hervorheben einer geordneten Teilmenge der besten Alternativen;
• teilweise Bestellung von Alternativen;
• geordnete (teilweise geordnete) Aufteilung von Alternativen;
• ungeordnete Aufteilung von Alternativen (Klassifizierung).

Basierend auf der Analyse von Messungen von Indikatoren für Eigenschaften von Alternativen in verschiedenen Maßstäben können die Messergebnisse auf unterschiedliche Weise dargestellt werden [1, 5].



1. Klassifizierungstabelle. Die Tabelle wird erhalten, wenn Messungen in nominalen Skalen durchgeführt werden, und ist eine Tabelle, deren Zeilen lauten: der Name des Objekts und die Spalten die Namen der Klassen$$$X_1, X_2, X_3,$ ... usw. In den Spalten Klasse 1, Klasse 2 usw. wird 1 gesetzt, wenn das Objekt zu dieser Klasse gehört, und 0 - wenn nicht (Tabelle Klassen von Objekten).



In der Klassentabelle Objekte $$$x_1 ,x_2 є X_1, x_3 є X_2, x_4 є X_3.$



2. Matrix des Präferenzverhältnisses. Erhalten durch Messungen in Ordnungsskalen. Präferenzen für die Menge von Objekten Ω aufzuzeigen bedeutet, die Menge aller Objektpaare (x, y) aus dieser Menge anzugeben, für die das Objekt x vorzuziehen ist (z. B. härter) als das Objekt y. Die Präferenzbeziehungsmatrix wird wie folgt erhalten. (siehe hier, Abb. 2.15)



Im Aufbau$$$_{[n×n]}^p$ quadratische Matrix. Seine i-te Linie entspricht dem i-ten Element$$$x_i$ Menge Ω und die j-te Spalte zum Element$$$x_j$ . Am Schnittpunkt der i-ten Zeile und der j-ten Spalte wird 1 platziert, wenn das Objekt$$$x_i$ Objekt vorgezogen$$$x_j$ , Null, wenn das Objekt$$$x_j$ Objekt vorzuziehen$$$x_i$ , 1/2 wenn Objekte$$$x_i$ und$$$x_j$ gleichgültig und es wird nichts gesetzt - wenn die Objekte unvergleichlich sind$$$x_i$ und$$$x_j$ kann nicht verglichen werden.



Ein Beispiel für eine solche Präferenzbeziehung ist in der folgenden Matrix dargestellt.





3. Tabelle der Indikatoren. Erhalten bei der Messung in der Skala der Beziehungen. Die Eigenschaften der zu messenden Indikatoren werden ausgewählt. Die Messung dieser Eigenschaften wird durchgeführt und die Messergebnisse werden in einer Tabelle aufgezeichnet.



In Spalten$$$p_1, p_2, p_3, p_4$ Tabellen Das Präferenzverhältnis enthält die Werte der Eigenschaftsindikatoren, anhand derer Objekte bewertet werden$$$x_1,x_2,x_3,x_4,x_5,x_6$ und$$$x_7$ .



Nachdem wir die Messergebnisse in diesen Darstellungsformen erhalten haben, müssen wir die Ergebnisse in Form von Beziehungen anzeigen, da wir das ZPR lösen werden, wobei wir uns auf den gut entwickelten Apparat der Theorie der binären Beziehungen stützen.



Die Zuordnung der Präferenztabelle zur binären Beziehungsmatrix ist wie folgt:





Aus der Präferenzbeziehungsmatrix $$$_{[4×4]}^p$ für 4 in der Tabelle dargestellte Alternativen. Die Präferenzbeziehung wird die Matrix sein$$$_{[4×4]}^p$ , das so aussieht:





Die Zuordnung der Scorecard zur Präferenzverhältnismatrix ist wie folgt: $$$a_{i,j}=1$ wenn:

1) die Anzahl der Indikatoren, durch die das Objekt$$$x_i$ Objekt vorgezogen$$$x_j$ größer als die Anzahl der Indikatoren, um die sich das Objekt dreht$$$x_j$ Objekt vorzuziehen$$$x_i$ ;



2) für das Objekt$$$x_i$ Keiner der Indikatoren nimmt den kleinstmöglichen Wert an.



3) Bedingung 1 impliziert, dass diejenigen Indikatoren, für die das Objekt$$$x_i$ nicht schlechter als Objekt$$$x_j$ , machen die Mehrheit aller betrachteten Indikatoren aus.



Wenn diese Bedingung jedoch erfüllt ist, kann sich herausstellen, dass entsprechend den Indikatoren, für die das Objekt$$$x_i$ schlimmer als Objekt$$$x_j$ ist der Unterschied signifikant; Um die Anzahl solcher Fälle zu verringern, wenn x bevorzugt wird, wird Bedingung 2 eingeführt.

Methoden zur Lösung des Entscheidungsproblems

Lassen Sie uns nach Erhalt der Anfangsdaten die Beziehung R auf der Menge der Alternativen haben $$$Ω= {(x_1, ...,x_n)}$... Und die Aufgabe ist es, eine Entscheidung zu treffen. Die Hauptmethode ist die lineare Reihenfolge (Rangfolge) von Alternativen, dh das Erstellen von Alternativen in einer Kette in absteigender Reihenfolge ihres Werts, ihrer Eignung, Wichtigkeit und dergleichen vom „Besten“ zum „Schlechtesten“.



Das Verhältnis R kann sein:

1. vollständige nicht-transitive Haltung;
2. eine partielle Ordnungsbeziehung;
3. lineare Ordnung.

Nur bei Linearität der Beziehung R erfüllt die Präferenzstruktur die Aufgabe. In diesem Fall wird die Rangfolge der Alternativen aus der Menge Ω direkt durch Erstellen eines Liniendiagramms der geordneten Menge erhalten. Im Diagramm die Alternative$$$x_i$wird streng höher sein als die Alternative $$$x_j$falls bevorzugt.



Die Lösung des Problems für vollständige und transitive Beziehungen wird unter Verwendung von Methoden (Algorithmus) zum Einordnen von Alternativen und für Teilordnungen unter Verwendung eines linearen Neuordnungsalgorithmus durchgeführt. Diese Algorithmen werden in den folgenden Abschnitten erläutert.



Rangfolge der Alternativen . Die Beziehung [Ω, R] sei vollständig und nicht transitiv. Die Vollständigkeitseigenschaft bedeutet, dass alle Alternativen$$$Ω = {(x_1, ...,x_n)}$aus dem Set sind miteinander vergleichbar. Das Vorhandensein von Nichttransitivität ist nur möglich, wenn der Präferenzgraph G [Ω, R] Konturen enthält.



Es ist notwendig, die Struktur des Beziehungsgraphen so zu transformieren, dass logische Widersprüche in Form von Konturen beseitigt werden. Wenn wir annehmen, dass es eine Kontur in Bezug auf R gibt$$$x_1, x_2, …,x_k, x_1,$ dann beim Ranking von Alternativen $$$x_1$ sollte höher liegen $$$x_2, x_3, …,x_k, x_1,$was zu einem Widerspruch führt.

Lassen Sie uns die folgende Aussage einführen [1,5].



Sei B 'und B "zwei beliebige Konturen eines Graphen der Form G [Ω, R], dann wenn irgendein Element$$$x_i$ є B 'dominiert das Element $$$x_j$ є B '', dann ein beliebiges Element $$$x_1$є B 'jedes Element dominiert $$$x_k$є B ''.



Dieser Vorschlag ermöglicht es, die Menge R in m Teilmengen zu unterteilen$$$B_1, B_2, …,B_m$so dass $$$B_i ∩ B_j=∅, ∀i,j є [1, m]; UB_i =Ω.$

Das Problem der Rangfolge der Alternativen der Menge fällt also in zwei Stufen:

1) die Auswahl der Konturen des Graphen, d.h. Aufteilung der Menge Ω in Teilmengen$$$B_1, B_2, …,B_m$und die Gruppenreihenfolge dieser Teilmengen;

2) Rangfolge der in der ersten Stufe ausgewählten Konturelemente.



Algorithmus zum Identifizieren von Diagrammkonturen



Es gibt einen einfachen Algorithmus zum Ermitteln der Konturen eines Diagramms [1]. Lassen$$$_{[n×n]}$ Ist die Adjazenzmatrix des Graphen G [Ω, R] und $$$_{[n×n]}$–Einheitsmatrix. Wir formen$$$_{[n×n]}+ _{[n×n]}$, $$$(_{[n×n]}+ _{[n×n]})^2$, $$$(_{[n×n]}+ _{[n×n]})^3$,… Eine Folge von Matrizengraden, deren Elemente die Anzahl der Längenpfade höchstens 1, 2, 3 ausdrücken… Für einen Wert m ≤ n erhalten wir die folgende Gleichheit (eine stetige Matrix):

$$$(_{[n×n]}+ _{[n×n]})^m=(_{[n×n]}+_{[n×n]})^{m+1}$...



Aus der Graphentheorie [10] ist bekannt, dass jedem System aller identischen Zeilen einer "stetigen" Matrix eine Teilmenge der Eckpunkte des Graphen entspricht, die in einer Kontur liegen. Wenn wir die entsprechenden Eckpunkte in Klassen gruppieren, erhalten wir eine Partition der ursprünglichen Menge Ω in Teilmengen$$$B_1, B_2, …,B_m$...



Es ist offensichtlich, dass man unter diesen Teilmengen eine solche Teilmenge finden kann$$$B_im$dass die Elemente dieser Teilmenge nicht von Elementen aus anderen Teilmengen dominiert werden. Diese Teilmenge wird als die beste angesehen und nimmt in absteigender Reihenfolge der Präferenzen den ersten Platz in der Rangliste ein.



Dann finden wir die beste Teilmenge unter den verbleibenden Teilmengen nach demselben Prinzip und setzen sie an zweiter Stelle. Wir werden dieses Verfahren fortsetzen,

bis alle Teilmengen ihren Platz in der Rangliste einnehmen.



Die Präferenzrelation R sei auf der Menge Ω durch die Matrix gegeben$$$_{[6×6]}$...





Der Beziehungsgraph R ist in Fig. 4 gezeigt. G.





Zahl: D. Graph der nichttransitiven Beziehung R



Um die erste Stufe der Rangfolge der Elemente der Menge zu implementieren, müssen die Konturen des Graphen G [Ω, R] ausgewählt werden. Dies erfolgt durch Erhöhen der Adjazenzmatrix des Graphen auf aufeinanderfolgende Potenzen, bis die Matrizen übereinstimmen.



Wir bekommen$$$(_{[6×6]}+ _{[6×6]})$, $$$(_{[6×6]}+ _{[6×6]})^2$, $$$(_{[6×6]}+ _{[6×6]})^3$...

Als nächstes berechnen wir nacheinander die zunehmenden Potenzen der Matrix und summieren sie mit der Einheitsmatrix der entsprechenden Dimension, bis sich die Matrix nicht mehr ändert:





Als $$$(_{[6×6]}+ _{[6×6]})^2 =(_{[6×6]}+ _{[6×6]})^3$, können wir schließen, dass $$$(_{[6×6]}+ _{[6×6]})^2 = (_{[6×6]}+ _{[6×6]})^k$, für k ≥ 2. Aus der Analyse der Matrix $$$(_{[6×6]}+ _{[6×6]})^2$ Daraus folgt, dass die Linien den Elementen entsprechen $$$x_1,x_4,x_6$Dies zeigt an, dass diese Elemente zur gleichen Kontur des Graphen G [Ω, R] gehören.



Die Elemente$$$x_1,x_4,x_6$ bilden eine Menge $$$B_1 =(x_1,x_4,x_6)$... Eine weitere Kontur besteht aus Elementen$$$x_2,x_3,x_5$die im Set enthalten sind $$$B_2 =(x_2,x_3,x_5)$...



Daher haben wir die Menge in m = 2 Klassen unterteilt$$$B_1, B_2$... Lassen Sie uns eine Gruppenreihenfolge dieser Teilmengen durchführen. Dazu müssen Sie ein Element finden$$$x_i є B_1$welches Element dominiert $$$x_j є B_2$...



Dies bedeutet die Überlegenheit der Teilmenge$$$B_1$ Über $$$B_2$... In unserem Beispiel$$$x_1 є B_1$ dominiert $$$x_2 є B_2$... Daher die Teilmenge$$$B_1$ dominiert $$$B_2$... Eine grafische Darstellung der Dominanz in der Partition Ω ist in Abb. 1 dargestellt. QC.





Zahl: QC. Rangfolge der in der ersten Stufe ausgewählten Konturen



Algorithmus zur Rangfolge der Elemente der Konturen . Ist es möglich, die Elemente einer Beziehung in derselben Kontur anzuordnen, sind sie einander äquivalent oder gibt es ausreichend subtile Unterschiede zwischen ihnen, um sie zu unterscheiden? Es stellt sich heraus, dass eine solche Möglichkeit in der Regel besteht [1].



Bezeichnen wir mit$$$B_{h_{[n×n]}}$die Adjazenzmatrix der h-ten Kontur. Lassen Sie uns das Konzept vorstellen$$$p^i(k)$ist die Kraft der Ordnung k des Elements i, dessen Wert als die Summe der Elemente der i-ten Zeile in der Matrix berechnet wird $$$B_{h_{[n×n]}}^k$(1).



Lassen$$$b_{h_{[i,j]}}^k$Ist das Element in der i-ten Zeile und j-ten Spalte der Matrix, dann





Die relative Stärke der k-ten Ordnung des Elements i wird als Bruch verstanden



Wenn k unbegrenzt zunimmt (k → ∞), wird die Zahl $$$π_i(k)$tendiert zu einer bestimmten Grenze π, die wir weiter die Stärke des Elements i nennen werden. Vektor$$$_{[n]} = (π_1,...,π_n)$wird der Grenzvektor genannt.



Aufgrund des Perron-Frobenius-Theorems [1] existiert die Grenze immer. Der normalisierte Eigenvektor der Kontur-Adjazenzmatrix fällt mit seinem Grenzvektor zusammen. Daher der Vektor$$$_{[n]} = (π_1,...,π_n)$(2)



kann ohne Berechnung der integrierten Kräfte gefunden werden$$$p^i(k)$durch Lösen des linearen Gleichungssystems

$$$B_{h_{[n×n]}} · _{[n]} = λ_{[n]}$, (3)

wobei λ die größte nicht negative reelle Wurzel der charakteristischen Gleichung ist

$$$det(λ_{[n×n]}- B_{h_{[n×n]}}) = 0$(4)

Es ist zu beachten, dass sich der normalisierte Eigenvektor einer nichtnegativen nicht zusammensetzbaren Matrix nicht ändert, wenn die Matrix mit einer Zahl s> 0 multipliziert wird und wenn sie mit einer Matrix der Form sE summiert wird.



Dann werden die Konturelemente geordnet, indem die Werte der entsprechenden Vektorkomponenten verringert werden$$$_{[n]}$d.h. Element i dominiert Element j wenn$$$π_i >π_j$...



Wir werden die Elemente des Sets ordnen$$$B_1 =(x_1,x_4,x_6)$... Lassen Sie uns eine Präferenzmatrix für diese Menge erstellen





Der Vektor der integrierten Kräfte 1. Ordnung für die Elemente $$$(x_1, x_4, x_6)$sieht aus wie (1,1,2), der Vektor der relativen Kräfte P (k) = (1 / 4,1 / 4,2 / 4).

Artikel-Ranking$$$(x_1, x_4, x_6)$Die Stärke 1. Ordnung ist in Abb. 1 dargestellt. R.





Zahl: R. Rangfolge der Elemente



Lassen Sie uns Vektoren finden, die die Kräfte der 2., 3., 4. und 5. Ordnung charakterisieren.





Eine grafische Darstellung der Rangfolge ist in Abb. 1 dargestellt. P.







Abb. C - Kette



Wenn wir die Rangfolge der Elemente der Menge B2 auf ähnliche Weise durchführen, erhalten wir die in Abb. 1 gezeigten Ergebnisse. Recht.



Als Ergebnis der Kombination der Rangfolge der Elemente der Menge 1 und 2 gelangen wir zur endgültigen Reihenfolge der Elemente der Menge Ω (Abb. C).

Lineare Neuordnung strenger Teilbestellungen

Die Beziehung R (Abb. A unten im Text), die sich aus der Aggregation einzelner Urteile von Experten ergibt, sei eine partielle Ordnungsrelation auf der Menge Ω. In diesem Fall ist Ω eine geordnete Menge. Die Konstruktion einer linearen Reihenfolge von Alternativen besteht darin, globale Bewertungen ihrer "Fähigkeiten" in einer Ordnungsskala zu erhalten.



Aus irgendeinem Grund können einige Experten bestimmte Paare von Alternativen hinsichtlich ihrer Präferenz nicht vergleichen. In diesem Fall ist die aggregierte Beziehung R auf der Menge Ω keine lineare Ordnung. Dies führt offensichtlich zu dem Problem der linearen Neuordnung von Alternativen von Ω. Diese Neuordnung ist oft auf viele Arten möglich.



Das Vorhandensein mehrerer linearer Ordnungen für eine Teilordnung zeigt an, dass die "intrinsische Ordnung" in der Struktur für eine einzelne lineare Ordnung nicht ausreicht. Somit wird es notwendig, das Problem der linearen Neuordnung von Teilordnungen zu lösen. Sei R eine Teilordnung.



Satz (Spielrein [5, 10]). Jede Reihenfolge R in einem Satz kann auf eine lineare Reihenfolge in diesem Satz erweitert werden.



Eine Folge von Spielreins Theorem: jede lineare Neuordnung einer Teilmenge$$$Ω_i ⊆ Ω$kann auf eine lineare Neuordnung des gesamten geordneten Satzes Ω erweitert werden.



Wenn X eine Teilmenge in Ω ist, die aus unvergleichlichen Alternativen besteht, kann jede lineare Ordnung von X auf eine lineare Ordnung der gesamten Menge Ω erweitert werden. In diesem Fall wird die Ordnung von R als lineare Ordnungen ausgedrückt$$$R_i$...



Nach dem Satz von Spielrein existiert auf der Menge Ω eine Nummerierung$$$x_1, x_2,...,x_n$Elemente dieses Satzes. Die Nummerierung einer geordneten Menge Ω mit n Elementen mit einer gegebenen Ordnungsrelation R ist eine Eins-zu-Eins-Abbildung der Menge Ω in sich selbst, d.h. in {1, 2, ..., n}, wobei das "größere" Element in Bezug auf die Reihenfolge der größeren Zahl entspricht [5]. Im Folgenden meinen wir mit der Rangfolge der Elemente jede lineare Neuordnung dieser Reihenfolge. Beachten Sie, dass die Nummerierung eines geordneten Satzes dessen Dimension darstellt.



Im allgemeinen Fall wird das Problem des Findens linearer zusätzlicher Ordnungen auf das Finden aller zulässigen Nummerierungen der ursprünglichen teilweise geordneten Menge reduziert. Sie können alle Permutationen von Elementen aus Ω aufschreiben, von denen es n geben wird! und überprüfen Sie für jedes die Bedingung, dass das "größere" Element der größeren Zahl entspricht. Diese Methode zum Auffinden aller zusätzlichen Bestellungen ist jedoch sehr mühsam und ineffizient.



Für eine geordnete Menge Ω mit einer gegebenen Ordnung R wird ein Element x 'der Menge Ω als maximal bezeichnet, wenn es kein streng größeres Element x gibt, d.h. wenn x> x 'gilt nicht für x є Ω. Ein Element x '' wird das größte Element der geordneten Menge [Ω, R] genannt, wenn es größer als jedes andere Element x ist, d.h. für jedes x є Ω ist x ''> x [5].



Wenn eine geordnete Menge ein größtes Element enthält, ist dies das maximale Element. Wenn eine geordnete Menge ein einzelnes maximales Element hat, ist es das größte Element. In einem teilweise geordneten Satz sind mehrere maximale Elemente zulässig.



Für jede Nummerierung des n-Element-Satzes Ω wird dem maximalen Element die Nummer N zugewiesen. Alle Nummerierungen der Menge Ω können erhalten werden, wenn alle Nummerierungen aller aus Ω erhaltenen Teilmengen bekannt sind, indem eines dieser maximalen Elemente gelöscht wird. Die gleiche Technik wird auf jede Teilmenge angewendet [7]. Betrachten Sie einen Algorithmus zum Konstruieren aller Nummerierungen der geordneten Menge [Ω, R].



1. Es wird ein Hilfsgraph [β, γR] der geordneten Menge [Ω, R] konstruiert, dessen Eckpunkte die folgenden Bedingungen erfüllen:



a) sind Teilmengen von Ω;



b) für zwei beliebige Teilmengen X, Y є β ist es wahr: (X, Y є γR), wenn die

Teilmenge Y aus der Teilmenge X erhalten werden kann, indem eines ihrer maximalen Elemente entfernt wird (Fig. A und AA).





2. Schreiben Sie für jede Ein-Element-Teilmenge der Menge γR ihre eindeutige Nummerierung auf. Um alle Nummerierungen der Teilmenge X zu erhalten, müssen alle benachbarten Teilmengen aufgelistet werden, und für jede dieser Teilmengen müssen alle ihre Nummerierungen fortgesetzt werden. Als Ergebnis werden alle Nummerierungen des Satzes Ω erhalten, d.h. alle linearen Erweiterungen der Ordnung R.



Das Problem besteht darin, alle linearen zusätzlichen Ordnungen einer Teilordnung zu finden, deren Diagramm in Fig. 1 gezeigt ist. A. Es gibt diesbezüglich beispielsweise keine Informationen darüber, ob die Alternative dominiert$$$x_1$Alternative $$$_2$ oder umgekehrt und auch ähnlich für Paare $$$(_3, _6);(_4, _5)$... Dies bedeutet, dass A eine Teilbestellung ist. Es gibt viele (22) Optionen, um eine lineare Reihenfolge zu vervollständigen, die es wünschenswert ist, zu einer einzigen zu bringen. Dies ist möglich, indem zusätzliche Informationen zu den Alternativen einbezogen werden, die aus einer detaillierten Untersuchung der Situation hervorgehen.



1. Wir konstruieren einen Hilfsgraphen [β, γR], beginnend mit der Menge$$$(x_1, x_2, x_3,x_4, x_5, x_6)$und darunter. Die Zahl in der Nähe des Diagrammbogens gibt an, durch Löschen des maximalen Elements die Teilmenge erhalten wurde, auf die dieser Pfeil gerichtet ist (Abb. AA).



2. Wir bilden die Tabelle. AAA, um alle Nummerierungen von Teilmengen zu finden, die Eckpunkte des Graphen sind [β, γR]. Das Füllen der Tabelle erfolgt zeilenweise von oben nach unten. Jede Zeile ist die Nummerierung der Teilmenge, die in der linken Spalte der Tabelle (Tabelle AAA) aufgezeichnet ist.



3. Beim Kompilieren der Nummerierung der Teilmenge X, die aus k Elementen besteht, müssen alle zuvor geschriebenen (für die vorherige Teilmenge) Nummerierung der Teilmengen Y є γR (x) neu geschrieben und dem Element, das Y zu X ergänzt, eine Nummer zugewiesen werden.





Der letzte (untere) Block (Tabelle AAA) enthält alle Nummerierungen der linearen Neuordnung der Menge Ω. Eine grafische Darstellung dieser Nachbestellungen ist in Abb. 1 dargestellt. AAA.





Zahl: AAA. Grafische Darstellung von Vorbestellungen



Es ist zu beachten, dass ein Satz von 6 Elementen 6 lineare Ordnungen enthält! oder 720 und lineare Neuordnung der Menge Ω mit der Beziehung, die durch das in Fig. 1 gezeigte Diagramm gegeben ist. AA, insgesamt 22. Dies reicht auch aus, um eine Entscheidung zu treffen.

Gibt es Möglichkeiten, die Anzahl solcher Optionen zu reduzieren? Ja, das gibt es.

Um die Anzahl der linearen Nachbestellungen zu verringern, müssen Sie zusätzliche Informationen verwenden.

Weitere Informationen

Sei [Ω, R] die Anfangsrelation, dann kann die zusätzliche Information als Relation δ auf der Menge Ω dargestellt werden, wobei die Bedingung (x, y) є δ, d. H. (x> y) wird als Nachricht interpretiert, dass das Objekt x das Objekt y dominiert;

Das Verhältnis δ kann dann als eine Menge ähnlicher Informationsnachrichten über die Dominanz betrachtet werden, die in Form eines binären Verhältnisses δ gegeben sind. Bei Verwendung zusätzlicher Informationen gibt es zwei mögliche Fälle:

1. der Beziehungsgraph R∪δ enthält Konturen;
2. Der Graph der Beziehung R∪δ enthält keine Konturen.

Im ersten Fall wird die lineare Ordnung der Menge Ω mit einem gegebenen Verhältnis R∪δ darauf unter Verwendung des

zuvor betrachteten Rangfolgenalgorithmus durchgeführt .



Im zweiten Fall wird die lineare Ordnung der Menge Ω mit dem darauf angegebenen Verhältnis R∪δ unter Verwendung des oben betrachteten linearen Neuordnungsalgorithmus durchgeführt

. Es ist zu beachten, dass die Beziehung R∪δ, die keine Konturen enthält, nicht transitiv und daher keine Teilordnung sein kann.



Für einen erfolgreichen Ausweg aus dieser Situation ist es notwendig, dass die zusätzlichen Informationen & dgr; und das Anfangsverhältnis R in Form von Hasse-Diagrammen angegeben werden, d. H. ohne ausdrückliche Angabe von transitiven Verbindungen. Der Wert zusätzlicher Informationen wird dadurch bestimmt, wie oft die Anzahl linearer Zusatzbestellungen abnimmt, wenn sie verwendet werden.



Zum Beispiel, wenn Informationen empfangen werden, die $$$x_2$ dominiert $$$x_4$d.h. $$$x_2>x_4$Dann verringert sich die Anzahl der linearen Nachbestellungen von 22 auf 19, und wenn Informationen eintreffen: $$$x_1>x_2$dann halbiert sich die Anzahl der linearen Vorbestellungen. Somit stellt sich die Frage: Welche Informationen sind am wertvollsten, oder wenn Sie welches Verhältnis δ hinzufügen, verringert sich die Anzahl der zusätzlichen Bestellungen am meisten?



Um dieses Problem für alle Elementpaare zu lösen$$$(x_i, x_j)$die Mengen Ω, die nicht in der Beziehung R enthalten sind, im unteren Block der Tabelle. AAA müssen Sie berechnen$$$n_{ij}$ - wie oft die Artikelnummer $$$x_i$ mehr Artikelnummer $$$x_j$d.h. Element$$$x_i$ steht über dem Element $$$x_j$ und $$$n_{ji}$ - wie oft ein Artikel $$$x_j$ steht über dem Element $$$x_i$...

Der Wert zusätzlicher Informationen über die Beziehung in diesem Paar ist umso höher, je geringer die Differenz ist$$$|n_{ij} - n_{ji}|$... Größere Zahlen$$$n_{ij}, n_{ji}$ist gleich der Anzahl der Nachbestellungen der Menge [Ω, R∩δ]. Für das betrachtete Beispiel erhalten wir eine Zusammenfassung der Eigenschaften der grafischen Darstellung der Nachbestellungen





Aus der Analyse der Tabelle folgt, dass die nützlichsten

Informationen Informationen über die Beziehung in Paaren sind$$$(x_1, x_2)$ und $$$(x_4, x_5)$... Das Erhalten zusätzlicher Informationen über die Beziehung in einem dieser Paare führt zu einer Halbierung der Anzahl linearer zusätzlicher Bestellungen.

Fazit

Die Formulierung und Lösung des DP ist nur in einer Situation mit vielen Alternativen und der Wahl der besten möglich. Wenn Sie keine andere Wahl haben, folgen Sie dem Pfad, auf dem Sie sich befinden.

Entscheidungen eines Entscheidungsträgers basieren auf seiner Präferenz, die durch eine Präferenzbeziehung beschrieben wird. Das Vorhandensein der Beziehung ermöglicht es Ihnen, ein mathematisches Modell für die Forschung zu erstellen. Unsicherheiten in den Präferenzen werden durch die Verwendung zusätzlicher Informationen beseitigt, die keine Experten sind.



Es wird auf die Berücksichtigung von Messungen und Schätzungen der Werte von Indikatoren für Eigenschaften von Objekten geachtet. Es werden Beispiele für verschiedene Skalen angegeben, die häufig ignoriert werden.

Mögliche Formulierungen von ZPR und die für ihre Lösung erforderlichen Informationen sind aufgeführt.



Anhand eines spezifischen numerischen Beispiels wird die Anwendung algebraischer Methoden zur Lösung von ZPR ohne Verwendung statistischer Stichproben und empirischer Verarbeitungsmethoden gezeigt.

Die Methode basiert auf dem Ergebnis des Satzes über die Möglichkeit, eine Teilordnung auf eine lineare (perfekte) zu erweitern.

Liste der verwendeten Literatur

1. Berge K. Graphentheorie und ihre Anwendung. - M.: IL, 1962 - 320 p.

2. Vaulin AE Diskrete Mathematik bei Computersicherheitsproblemen. Teil I. SPb .: VKA benannt nach A. F. Mozhaisky, 2015 .-- 219 p.

3. Vaulin AE Diskrete Mathematik bei Computersicherheitsproblemen. II. SPb .: VKA benannt nach A. F. Mozhaisky, 2017 .-- 151 p.

4. Vaulin AE Methoden zur Erforschung von Informationsrechnersystemen. Problem 2. - L .: VIKI sie. A. F. Mozhaisky, 1984 - 129 p.

5. Vaulin AE-Methodik und Methoden zur Analyse von Informationscomputersystemen. Ausgabe 1.– L .: VIKI im. A. F. Mozhaisky, 1981 - 117 p.

6. Vaulin AE Methoden der digitalen Datenverarbeitung: diskrete orthogonale Transformationen. - SPb .: VIKKI sie. A. F. Mozhaisky, 1993 - 106 p.

7. Kuzmin VB Konstruktion von Gruppenlösungen in Räumen klarer und unscharfer binärer Beziehungen. - M.: Nauka, 1982. - 168 p.

8. Makarov IM et al. Die Theorie der Wahl und Entscheidungsfindung. - Moskau: Fizmatlit, 1982. –328 S. 52.

9. Rosen V.V. Zweck - Optimalität - Lösung. - M .: Radio und Kommunikation, 1982. - 169 p.

10. Szpilraijn E Sur Textension de l'ordre partiel. - Fundam. math., 1930, Bd. 16, S. 386-389.