3.1.4. Îïèñàíèå ìàøèííîãî àëãîðèòìà Ôîðäà
   Ïîñêîëüêó çàäà÷à ìîæåò èìåòü íåñêîëüêî âàðèàíòîâ ðåøåíèÿ, òî âîç-
ìîæíûé àëãîðèòì ìîæåò âêëþ÷àòü ñëåäóþùèå îñíîâíûå øàãè.
   1. Ââîä ìàòðèöû äëèí äóã ãðàôà (L) è åå ðàçìåðà (n).
   2. Óñòàíîâêà íà÷àëüíûõ çíà÷åíèé: 1) âåêòîðà ìåòîê: Ì0=0; i=1(1)n–1,
Ìi=max; ãäå max – ìàêñèìàëüíî äîïóñòèìîå ÷èñëî äàííîãî òèïà; 2)
îáíóëåíèå âñïîìîãàòåëüíîãî âåêòîðà âåðøèí, âõîäÿùèõ â êðèòè÷åñêèå
ïóòè, V è ìàòðèöû êðàò÷àéøèõ ïóòåé Ê.
   Ïðÿìîé õîä
   (Ðåàëèçàöèÿ ïðàâèë 3 è 4 àëãîðèòìà Ôîðäà – öèêëû ïîèñêà ñìåæíûõ
âåðøèí ãðàôà ïî ñòðîêàì i è ñòîëáöàì j è îáíîâëåíèå ìåòîê âåðøèí):
   3. Öèêë i=0(1)n–1                               (ïî ñòðîêàì ìàòðèöû L)
   4. Öèêë j=0(1)n–1                             (ïî ñòîëáöàì ìàòðèöû L)
           åñëè (Lij>0 è Ìj – Ìi>Lij)                         (åñòü ìåòêà,
                                                òðåáóþùàÿ èçìåíåíèÿ, òî)
              { MN=Mi + Lij ; (âû÷èñëåíèå íîâîé ìåòêè (MN) âåðøèíû j)
                åñëè (MN < Mj)            (íîâàÿ ìåòêà ìåíüøå ñòàðîé, òî)
                 Ìj=MN;                      (èçìåíåíèå ìåòêè âåðøèíû j)
              }
   Îáðàòíûé õîä
   (Ðåàëèçàöèÿ ïðàâèëà 5 àëãîðèòìà Ôîðäà – ïîèñê âåðøèí êðàò÷àé-
øèõ ïóòåé):
   5. Vn-1=1;                      (êîíå÷íàÿ âåðøèíà êðàò÷àéøåãî ïóòè)
   6. Öèêë j=n–1(–1)0                        (îáðàòíûé öèêë ïî âåðøèíàì,
                                                      íà÷èíàÿ ñ ïîñëåäíåé)
        åñëè (Vj=1)              (âåðøèíà âõîäèò â êðàò÷àéøèé ïóòü, òî)
   7.      Öèêë i=0(1)n–1               (ïîèñê ïðåäøåñòâóþùèõ âåðøèí i,
                                                    ñìåæíûõ ñ âåðøèíîé j)
              {åñëè (Lij>0 è Ìj – Ìi=Lij)         (ðàçíîñòü ìåòîê ñìåæíûõ
                               âåðøèí ðàâíà äëèíå äóãè ìåæäó íèìè, òî)
                   { Kij= Lij ; (çàïîëíåíèå ìàòðèöû êðàò÷àéøèõ ïóòåé)
                     Vi=1;             (âêëþ÷åíèå âåðøèíû i â âåêòîð V)
                    }
              }                                         (êîíåö öèêëîâ i è j)
   8. Âûâîä ìàòðèöû ñìåæíîñòè Ê ( ïîäãðàôà êðàò÷àéøèõ ïóòåé) è
âåêòîðà ìåòîê âåðøèí M (äëèí êðàò÷àéøèõ ïóòåé îò âåðøèíû V0).
   Ïî ìàòðèöå Ê íåîáõîäèìî ïîñòðîèòü äëÿ èñõîäíîãî ãðàôà ïîäãðàô
êðàò÷àéøèõ ïóòåé îò âåðøèíû v0 ê vn.
                                                                         51


 à) M:
           Âåðøèíû 0            1   2       3   4 5 6
            Ìåòêè  0            7   8       9   11 13 19
á)                                              â) K:
                                                                0   1
                                                                    E   2   3   4   5   6
         v [7]     4           v" [11]                     0   0   7   0   9   0   0   0
                                                            1   0   0   0   0   4   0   0
                                            8               2   0   0   0   0   0   0   0
     7                  2
             9              4           6                   3   0   0   0   0   2   4   0
                                                            4   0   0   0   0   0   0   8
v [0]            v! [9]        v# [13]         v$ [19]
                                                            5   0   0   0   0   0   0   6
                                                            6   0   0   0   0   0   0   0
 Ðèñ. 3.4. Ðåçóëüòàòû ïîèñêà ìèíèìàëüíûõ ïóòåé â ãðàôå: à – âåêòîð ìåòîê
 M (äëèí êðàò÷àéøèõ ïóòåé îò âåðøèíû v0 äî îñòàëüíûõ); á – ïîäãðàô êðàò-
   ÷àéøèõ ïóòåé îò âåðøèíû v0 äî v6; ⠖ ìàòðèöà äëèí ïóòåé (Ê) ïîäãðàôà



   Íà ðèñ. 3.4 ïðåäñòàâëåíû ðåçóëüòàòû îáðàáîòêè ìàòðèöû äëèí äóã L
(ðèñ. 3.3) èñõîäíîãî ãðàôà íà ðèñ. 3.2 â ñîîòâåòñòâèè ñ àëãîðèòìîì Ôîðäà.


          3.2. Ïîèñê ìàêñèìàëüíîãî ïóòè â ãðàôå áåç êîíòóðîâ
    Àëãîðèòì Ôîðäà ìîæåò áûòü èñïîëüçîâàí äëÿ îòûñêàíèÿ ìàêñèìàëü-
íîãî ïóòè (èëè êðèòè÷åñêîãî ïóòè â çàäà÷å ñåòåâîãî ïëàíèðîâàíèÿ è óï-
ðàâëåíèÿ) â àöèêëè÷åñêîì ãðàôå. Äîñòàòî÷íî ïîëîæèòü íà÷àëüíûå ìåòêè
âåðøèí λi=0, i=0, 1, 2, … , n, à çàòåì çàìåíÿòü λj íà λ'j=λi+L(vi, vj), åñëè
λ'j>λj, äî òåõ ïîð, ïîêà âîçìîæíî óâåëè÷èâàòü λj.




52


          4. ÇÀÄÀ×À ÂÛÁÎÐÀ ÏÐÅÄÏÎ×ÒÈÒÅËÜÍÛÕ
           ÂÀÐÈÀÍÒÎÂ ÈÑÑËÅÄÓÅÌÎÉ ÑÈÑÒÅÌÛ


                   4.1. Îáùàÿ ïîñòàíîâêà çàäà÷è
    Ïðè ïðîåêòèðîâàíèè ñëîæíîé ñèñòåìû, êàê ïðàâèëî, èññëåäóåòñÿ
íåñêîëüêî âàðèàíòîâ ñèñòåìû, ïðè ýòîì âîçíèêàþò ïðîáëåìû êàê ïðè
îöåíêå ýôôåêòèâíîñòè ñèñòåìû, òàê è ïðè âûáîðå íàèáîëåå ýôôåêòèâ-
íîãî, à çíà÷èò, è ïðåäïî÷òèòåëüíîãî âàðèàíòà. Ïîä ýôôåêòèâíîñòüþ ñè-
ñòåìû ïîíèìàåòñÿ ìåðà ñîîòâåòñòâèÿ ñèñòåìû ñâîåìó íàçíà÷åíèþ,
ò. å. ñòåïåíü ïðèñïîñîáëåííîñòè åå äëÿ ðåøåíèÿ ïîñòàâëåííûõ ïåðåä
íåé çàäà÷, êîòîðàÿ îöåíèâàåòñÿ çàäàííîé öåëåâîé ôóíêöèåé f (ôóíêöèåé
êðèòåðèÿ ýôôåêòèâíîñòè).
    Òðóäíîñòü ñîñòîèò â òîì, ÷òî ýôôåêòèâíîñòü ñëîæíîé ñèñòåìû íå
ìîæåò áûòü îöåíåíà îäíèì ïîêàçàòåëåì, äàæå óíèâåðñàëüíûì, ïîñêîëü-
êó îíà ÿâëÿåòñÿ ôóíêöèåé áîëüøîãî êîëè÷åñòâà ôàêòîðîâ è êðèòåðèåâ
ýôôåêòèâíîñòè âñåõ ïîäñèñòåì, âõîäÿùèõ â ðàññìàòðèâàåìóþ ñèñòåìó.
Ýôôåêòèâíîñòü ñëîæíîé ñèñòåìû íåîáõîäèìî îöåíèâàòü ñ ðàçëè÷íûõ
òî÷åê çðåíèÿ ñ ïîìîùüþ ÷àñòíûõ ïîêàçàòåëåé êà÷åñòâà åå ôóíêöèîíè-
ðîâàíèÿ, â îáùåì ñëó÷àå ïðîòèâîðå÷èâûõ, íàïðèìåð ãàáàðèòû, âåñ, ïðî-
ïóñêíàÿ ñïîñîáíîñòü, íàäåæíîñòü, ñëîæíîñòü àëãîðèòìîâ ôóíêöèîíè-
ðîâàíèÿ, ñòîèìîñòü ïðîèçâîäñòâà è ýêñïëóàòàöèè è ò. ï. Òàêèì îáðà-
çîì, êðèòåðèé ýôôåêòèâíîñòè ñëîæíîé ñèñòåìû ÿâëÿåòñÿ âåêòîðíûì

                           .={fn}, n = 1, N ,
ãäå fn – ÷àñòíûå ïîêàçàòåëè êà÷åñòâà (êðèòåðèè ýôôåêòèâíîñòè) ôóíê-
öèîíèðîâàíèÿ ñëîæíîé ñèñòåìû.
   Ïîäîáíàÿ ïðîáëåìà âîçíèêàåò è ïðè ýêñïåðòíîì àíàëèçå âûáèðàå-
ìûõ îáúåêòîâ, êîãäà îáúåêòû, íàïðèìåð êâàðòèðà, îöåíèâàåòñÿ íåñêîëü-
êèìè ñïåöèàëèñòàìè (ýêñïåðòàìè) ïî íåñêîëüêèì ïîêàçàòåëÿì (ìåòðàæ,
óäîáñòâà, ñòîèìîñòü, óäàëåííîñòü îò òðàíñïîðòà èëè öåíòðà ãîðîäà è äð.).
Ïðè ýòîì îöåíêè ýêñïåðòîâ ìîãóò îòëè÷àòüñÿ âåñüìà ñóùåñòâåííî.

                                                                     53


   Âîçíèêàåò îáùàÿ ïðîáëåìà îöåíêè Ì âàðèàíòîâ èññëåäóåìîé ñè-
ñòåìû (îáúåêòîâ) ïî N êðèòåðèÿì è âûáîðà íàèáîëåå ïðåäïî÷òèòåëü-
íûõ èç íèõ (æåëàòåëüíî âûáðàòü îäèí âàðèàíò), ñ òî÷êè çðåíèÿ âñåõ
êðèòåðèåâ. Òàêèì îáðàçîì, ýòó ïðîáëåìó âûáîðà ìîæíî ðàçáèòü íà
äâà ýòàïà.
   Íà ïåðâîì ýòàïå âàðèàíòû ñèñòåìû èññëåäóþòñÿ ïî ìíîæåñòâó
êðèòåðèåâ .={fn}, n = 1, N . Ðåçóëüòàòû èññëåäîâàíèÿ (îöåíèâàíèÿ)
âñåõ Ì âàðèàíòîâ ñâîäÿòñÿ â ìàòðèöó îöåíîê ||Ð||M×N, îòîáðàæàþùóþ
ñòàòè÷åñêè óñòîé÷èâûå èëè äåòåðìèíèðîâàííûå îöåíêè ïîêàçàòå-
ëåé êà÷åñòâà Ì âàðèàíòîâ ïî N êðèòåðèÿì.  íàøåì ïîñëåäóþùåì
ðàññìîòðåíèè çàäà÷è ìû áóäåì ñ÷èòàòü ýòè äàííûå (M, N, P) êàê èñ-
õîäíûå.
   Âòîðîé ýòàï çàêëþ÷àåòñÿ â ïîñëåäîâàòåëüíîé îáðàáîòêå ìàòðèöû
îöåíîê Ð. Íåîáõîäèìî èç ñîâîêóïíîñòè èíäèâèäóàëüíûõ îöåíîê âàðè-
àíòîâ ïî çàäàííîìó íàáîðó êðèòåðèåâ âûðàáîòàòü ãðóïïîâîå ðåøåíèå
î ïîðÿäêå ïðåäïî÷òåíèÿ àëüòåðíàòèâíûõ âàðèàíòîâ, ò. å. äîëæíà áûòü
ðåøåíà ïðîáëåìà ãðóïïîâîãî âûáîðà. Ôîðìàëèçàöèÿ è ðåøåíèå ýòîé
çàäà÷è ïîêàçàíû äàëåå.

                  4.2. Ïîëó÷åíèå ñðàâíèìûõ îöåíîê
   Ïóñòü ðmn – îöåíêà m-ãî âàðèàíòà ïî êðèòåðèþ fn. Îöåíêè ðmn, m = 1, M ,
ÿâëÿþòñÿ àáñîëþòíûìè, îíè ïîëó÷åíû ⠓åñòåñòâåííîé” äëÿ êàæäîãî
êðèòåðèÿ øêàëå è ðàñïîëîæåíû â íåêîòîðîì äèàïàçîíå [pmin(n), pmax(n)].
Ïðè ýòîì äëÿ îäíèõ êðèòåðèåâ pmax ÿâëÿåòñÿ íàèëó÷øåé èç ïîëó÷åííûõ
îöåíîê, äëÿ äðóãèõ íàèõóäøåé, ò. å. òàêèå îöåíêè ïî ðàçíûì êðèòåðèÿì
ÿâëÿþòñÿ íåñðàâíèìûìè.
   Ïåðâûé øàã îáðàáîòêè ìàòðèöû îöåíîê Ð çàêëþ÷àåòñÿ â ïðåîáðàçî-
âàíèè ýëåìåíòîâ ìàòðèöû ñ öåëüþ ïîëó÷åíèÿ ñðàâíèìûõ îöåíîê ïóòåì
ïðèâåäåíèÿ èõ ê åäèíîìó ìàñøòàáó è íà÷àëó îòñ÷åòà. Ýòà çàäà÷à ìîæåò
áûòü ðåøåíà ðàçëè÷íûìè ìåòîäàìè, íàïðèìåð ðàíæèðîâàíèåì îöåíîê.
Ðàíæèðîâàíèå ïðåäñòàâëÿåòñÿ ïðîöåäóðîé âû÷èñëåíèÿ îöåíîê â ðàíãî-
âîé øêàëå, êîòîðóþ ìîæíî îïèñàòü ñëåäóþùèì îáðàçîì.
   Îáîçíà÷èì pl (n), px (n) – ñîîòâåòñòâåííî ëó÷øóþ è õóäøóþ îöåíêè
ïî êðèòåðèþ fn∈., n = 1, N . Îöåíêè ïî êðèòåðèþ fn äëÿ âñåõ âàðèàíòîâ
íàõîäÿòñÿ â äèàïàçîíå
                      px (n) ≤ ðmn ≤ pl(n), m = 1, M .
54


    Ïîñòðîåíèå øêàëû îöåíîê Sn çàêëþ÷àåòñÿ â çàäàíèè ÷èñëà ãðàäàöèé
D (ðàíãîâ, äåëåíèé) øêàëû è îïðåäåëåíèè öåíû äåëåíèÿ øêàëû
                             dn= ( pl (n)– px (n)) / D.
    Áëèçêèå îöåíêè (ñ òî÷íîñòüþ äî öåíû äåëåíèÿ) ìîãóò ïîïàñòü â îäèí
ðàíã øêàëû Sn, ò. å. ýòè îöåíêè ýêâèâàëåíòíû â äàííîé øêàëå Sn, çíà-
÷èò, D îïðåäåëÿåò êîëè÷åñòâî êëàññîâ ýêâèâàëåíòíîñòåé â ìàòðèöå îöå-
íîê.
    Èç èñõîäíîé ìàòðèöû îöåíîê Ð àáñîëþòíûå îöåíêè pmn ïðåîáðàçó-
þòñÿ â ðàíæèðîâàííûå îöåíêè rmn ñëåäóþùèì îáðàçîì:
    äëÿ pl (n) ïîëàãàåì rmn = D,
    äëÿ îñòàëüíûõ âû÷èñëÿåì ïî ôîðìóëå rmn = [( ðmn– px(n)) / dn +1], ãäå
[x] – áëèæàéøåå öåëîå ÷èñëî, ìåíüøåå èëè ðàâíîå õ, ò. å. öåëàÿ ÷àñòü õ.
Îöåíêè rmn ñîîòâåòñòâóþò ðàíãó, ò. å. áîëåå ïðåäïî÷òèòåëüíîìó îáúåê-
òó ñîîòâåòñòâóåò áîëåå âûñîêèé ðàíã.
    Ïðåîáðàçîâàííàÿ òàêèì îáðàçîì ìàòðèöà ðàíæèðîâàííûõ îöåíîê
||R||M×N ñîäåðæèò ñðàâíèìûå ïî ðàçëè÷íûì êðèòåðèÿì îöåíêè, ïîñêîëü-
êó ðàíæèðîâàííûå îöåíêè òåðÿþò “àáñîëþòíûé” âåñ è çíàê, ñïåöèôè÷-
íîñòü, îïðåäåëÿåìóþ öåíîé äåëåíèÿ øêàëû äàííîãî êðèòåðèÿ, ñîõðàíÿÿ
îòíîñèòåëüíûé âåñ, ò. å. ïîëîæåíèå â ðàíãîâîé øêàëå.

                  4.3. Ïîëó÷åíèå ãðóïïîâûõ îöåíîê
   Âòîðîé øàã îáðàáîòêè ìàòðèöû îöåíîê Ð ñîñòîèò â âûðàáîòêå ãðóï-
ïîâîãî ïðåäïî÷òåíèÿ âàðèàíòîâ íà îñíîâå èíäèâèäóàëüíûõ ðàíæèðî-
âàííûõ îöåíîê ìàòðèöû R, ïîëó÷åííîé â ðåçóëüòàòå ñîãëàñîâàíèÿ îá-
ùåé øêàëû îöåíîê.
   Ïðîñòåéøèé ñïîñîá ïîëó÷åíèÿ ãðóïïîâîé îöåíêè ñîñòîèò â òîì, ÷òî
êàæäîìó êðèòåðèþ fn ñòàâèòñÿ â ñîîòâåòñòâèå ÷èñëî ln, íàçûâàåìîå “âå-
ñîì” êðèòåðèÿ fn. Ñîâîêóïíîñòü { ln}, n = 1, N , óïîðÿäî÷èâàåò ìíîæå-
ñòâî .={fn} ïî ñòåïåíè “âàæíîñòè” êðèòåðèåâ. Ãðóïïîâàÿ îöåíêà îïðå-
äåëÿåòñÿ êàê âåêòîð G = RM×N ×L, ãäå L={ln }, n = 1, N , à ýëåìåíòû
âåêòîðà G îïðåäåëÿþòñÿ âûðàæåíèåì
                                    N
                             gm =   ∑ rmnln ,
                                    n =1

îòñþäà ìîæíî ïîëó÷èòü óñðåäíåííûå çíà÷åíèÿ
                                                                      55


                                N
              gm = gm / N = (   ∑ rmnln ) / N   , m = 1, M ,
                                n =1

ãäå M – êîëè÷åñòâî âàðèàíòîâ.
   Âàðèàíòû îáúåêòîâ ñðàâíåíèÿ óïîðÿäî÷èâàþòñÿ â ñîîòâåòñòâèè ñî
çíà÷åíèåì âåëè÷èí gm èëè g m , ïðè ýòîì âàðèàíò ñ ìàêñèìàëüíûì çíà-
÷åíèåì gm ( g m ) ÿâëÿåòñÿ íàèáîëåå ïðåäïî÷òèòåëüíûì. Åñëè îáðàçóåòñÿ
ìíîæåñòâî íåðàçëè÷èìûõ ïî gm âàðèàíòîâ, òî äàëüíåéøåå óïîðÿäî÷å-
íèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ëåêñèãðàôè÷åñêîãî ïîðÿäêà. Ïðèíèìà-
åòñÿ, ÷òî âàðèàíò v1 ïðåäïî÷òèòåëüíåå âàðèàíòà v2, åñëè îöåíêà v1 ïî
ñàìîìó âàæíîìó ïîêàçàòåëþ âûøå, ÷åì îöåíêà v2, ïðè ðàâåíñòâå ýòèõ
îöåíîê âàðèàíòû ñðàâíèâàþòñÿ ïî ïîêàçàòåëþ, ñëåäóþùåìó ïî âàæíî-
ñòè è ò. ä.
                                 Ïðèìåð
   Ðàññìîòðèì øàãè îáðàáîòêè ìàòðèöû îöåíîê ÐM×N äëÿ ñëåäóþùèõ
èñõîäíûõ äàííûõ: êîëè÷åñòâî îáúåêòîâ ñðàâíåíèÿ (âàðèàíòîâ) Ì=4, êî-
ëè÷åñòâî êðèòåðèåâ (ôóíêöèé ïðåäïî÷òåíèÿ) N=6, ìàòðèöà îöåíîê Ð4×6:

                        1   2           3    4   5    6
                   1   2,5 102         0,1   2 –3,5   4
                   2   –3 57           0,9    1  0    0
                   3   5,7 32          0,4   10 –5    2
                   4   17 52           1,1   0   5    3

   Ïåðâûé øàã îáðàáîòêè Ð – ïîëó÷åíèå îòíîñèòåëüíûõ îöåíîê. Äèà-
ïàçîíû îöåíîê ïî êðèòåðèÿì fn→[px(n), pl(n)] è öåíû äåëåíèé øêàë Sn
ïðè ÷èñëå ðàíãîâ D=10:
                       f1→[–3, 17], d1 = 2,
                         f2→[102, 32], d2 = –7,
                         f3→[0,1; 1,1], d3 = 0,1,
                         f4→[10, 0], d4 = –1,
                         f5→[–5, 5], d5 = 1,
                         f6→[0, 4], d6 = 0,4.

56


  Ðàíæèðîâàííàÿ ìàòðèöà îöåíîê R4×6:
                           1   2     3   4         5       6
                     1     3    1    1   9        20       10
                     2     1   7    9    10        6        1
                     3     5   10   4     1        1       6
                     4    10   7    10   10       10       8
  Âòîðîé øà㠖 ïîëó÷åíèå ãðóïïîâûõ îöåíîê.
                     fn    1   2    3    4    5        6
  Âåñà êðèòåðèåâ:
                     ln    3   2    2    3    1        1
  Ãðóïïîâûå îöåíêè âàðèàíòîâ:
  g1 = 3⋅3+2⋅1+2⋅1+3⋅9+1⋅2+1⋅10 = 52, g1 =8,7,
  g2 = 3⋅1+2⋅7+2⋅9+3⋅10+1⋅6+1⋅1 = 72, g2 = 12,
  g3 = 3⋅5+2⋅10+2⋅4+3⋅1+1⋅1+1⋅6 = 53, g3 = 8,7,
  g4 = 3⋅10+2⋅7+2⋅10+3⋅10+1⋅10+1⋅8 = 112, g4 = 18,67.
   Èñõîäÿ èç óñðåäíåííûõ ãðóïïîâûõ îöåíîê âàðèàíò 4 ìîæíî ñ÷èòàòü
ïðåäïî÷òèòåëüíûì èç ðàññìàòðèâàåìûõ âàðèàíòîâ ñðàâíåíèÿ. Îäíàêî
ïî ïîâîäó óñðåäíåííûõ ãðóïïîâûõ îöåíîê ìîæíî ñêàçàòü òî æå, ÷òî è î
ñðåäíåé òåìïåðàòóðå áîëüíûõ â áîëüíèöå èëè îòíîñèòåëüíî ñðåäíèõ
îöåíîê ýêñïåðòîâ. Ýòè îöåíêè íèâåëèðóþò ðàçëè÷èÿ â ôóíêöèÿõ ïðåä-
ïî÷òåíèÿ, îíè îòðàæàþò òî îáùåå, ÷òî åñòü â èíäèâèäóàëüíûõ îöåíêàõ,
è ñãëàæèâàþò áîëåå òîíêèå îòíîøåíèÿ ìåæäó ðàçëè÷íûìè êðèòåðèÿìè.
   Çàäà÷ó âûáîðà ïðåäïî÷òèòåëüíûõ âàðèàíòîâ ìîæíî ðåøèòü äðóãèì
ñïîñîáîì – ïðîèçâîäÿ àíàëèç ïðåäïî÷òåíèé ñðåäè àëüòåðíàòèâíûõ âà-
ðèàíòîâ ïóòåì èõ ïîïàðíîãî ñðàâíåíèÿ. Ñôîðìóëèðóåì ýòó çàäà÷ó âû-
áîðà êàê çàäà÷ó òåîðèè ãðàôîâ.

                4.4. Ôîðìàëèçàöèÿ çàäà÷è âûáîðà
                   ïðåäïî÷òèòåëüíûõ îáúåêòîâ
   Ïóñòü V – ìíîæåñòâî îáúåêòîâ (âàðèàíòîâ) ñðàâíåíèÿ, ïðè÷åì
V =Ì (êîëè÷åñòâî îáúåêòîâ), à . – ìíîæåñòâî êðèòåðèåâ (ôóíêöèé
ïðåäïî÷òåíèÿ), ïî êîòîðûì ìîæíî îöåíèâàòü ýòè îáúåêòû, è .=N
(êîëè÷åñòâî ôóíêöèé). Âåëè÷èíû pn, íàçûâàåìûå îöåíêàìè, îòðàæà-
þò ðàçëè÷èå ìåæäó ýëåìåíòàìè V ïî êðèòåðèþ fn∈., n = 1, N , ò. å.
ïðåäñòàâëÿþò ñîáîé îòîáðàæåíèå pn :
                                                                 57


    V→fn, êîòîðîå ïîçâîëÿåò âûïîëíèòü ñðàâíåíèå ïî êðèòåðèþ fn.
Îáîçíà÷èì ÷åðåç .n ìíîæåñòâî îöåíîê, êîòîðûå ìîæíî ïîëó÷èòü,
èññëåäóÿ ýëåìåíòû V ñ òî÷êè çðåíèÿ êðèòåðèÿ fn. Ïðè àíàëèçå ïî
âñåì êðèòåðèÿì êàæäîìó ýëåìåíòó v∈V ñòàâèòñÿ â ñîîòâåòñòâèå
ïîñëåäîâàòåëüíîñòü èç N îöåíîê, âçÿòûõ èç ìíîæåñòâ .1, … , .N, ò. å.
ñ êàæäûì ýëåìåíòîì ìíîæåñòâà V ñîïîñòàâëÿåòñÿ ýëåìåíò äåêàðòîâà
ïðîèçâåäåíèÿ . '= .1× .2×…× .N..
    Ñòàâèòñÿ çàäà÷à âûïîëíèòü ñðàâíåíèå îáúåêòîâ ìíîæåñòâà V ñ ïî-
ìîùüþ ìíîãîìåðíîãî ñîñòîÿíèÿ .' = .1× .2×…× .N. ñ öåëüþ âûáîðà
îäíîãî èëè íåñêîëüêèõ îáúåêòîâ, ÿâëÿþùèõñÿ íàèëó÷øèìè ñ òî÷êè çðå-
íèÿ ìíîæåñòâà êðèòåðèåâ .. Ïðåäñòàâèì ðåøåíèå çàäà÷è ïîïàðíîãî ñðàâ-
íåíèÿ îáúåêòîâ íà ÿçûêå òåîðèè ãðàôîâ.
    Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð v, v'∈V îáîçíà÷àåòñÿ V×V. Ïîä-
ìíîæåñòâî B⊆V×V íàçûâàåòñÿ áèíàðíûì îòíîøåíèåì, ò. å. (v,v') ∈B.
Âûøå ìû ðàññìîòðåëè ñîîòâåòñòâèå ìåæäó áèíàðíûì îòíîøåíèåì è
îðãðàôîì, ïðè ýòîì âåðøèíû ãðàôà ñîîòâåòñòâóþò îáúåêòàì ñðàâíåíèÿ
vi∈V, à äóãè îòðàæàþò áèíàðíîå îòíîøåíèå ìåæäó îáúåêòàìè.
    Íàïîìíèì, ÷òî åñëè (v,v') ∈B, òî â ãðàôå ïðîâîäèòñÿ äóãà èç v â v',
ïðè ýòîì v – íà÷àëî, à v' – êîíåö äóãè, ò. å. äóãà îïðåäåëÿåòñÿ ïàðîé
(v,v'). Ïîñëåäîâàòåëüíîñòü äóã (vi, vi+1), i=1,2, … , k–1, íàçûâàåòñÿ ïó-
òåì. Êîíå÷íûé ïóòü, ó êîòîðîãî v1=vk, îáðàçóåò êîíòóð. Äóãà (v, v) íà-
çûâàåòñÿ ïåòëåé.
    Êàê èçâåñòíî, áèíàðíîå îòíîøåíèå íàçûâàåòñÿ ðåôëåêñèâíûì, åñëè
(v,v) ∈B (ò. å. ãðàô ñ ïåòëÿìè); àíòèðåôëåêñèâíûì, åñëè (v,v) ∉B (ò. å.
ãðàô áåç ïåòåëü); ñèììåòðè÷íûì, åñëè (v,v') ∈B ↔ (v',v) ∈B (ò. å. äëÿ
êàæäîé ïàðû ñìåæíûõ âåðøèí åñòü âñòðå÷íûå äóãè); àíòèñèììåò-
ðè÷íûì, åñëè (v,v') ∈B è (v',v) ∈B → v=v' (ò. å. âåðøèíû ñî âñòðå÷íû-
ìè äóãàìè ðàññìàòðèâàþòñÿ êàê îäíà âåðøèíà); àñèììåòðè÷íûì, åñëè
(v,v') ∈B → (v',v) ∉B (ò. å. ãðàô áåç âñòðå÷íûõ äóã ìåæäó ïàðàìè âåð-
øèí); òðàíçèòèâíûì, åñëè (v,v') ∈B è (v',v'') ∈B → (v,v'') ∈B (ò. å. åñëè
ëþáûå òðè ïîñëåäîâàòåëüíûå âåðøèíû ñâÿçàíû äâóìÿ ïîñëåäîâàòåëü-
íûìè äóãàìè, òî ñóùåñòâóåò äóãà ìåæäó ïåðâîé è òðåòüåé âåðøèíàìè);
ëèíåéíûì, åñëè (v,v') ∈B èëè (v',v) ∈B (ò. å. ëþáûå äâå âåðøèíû ñâÿçà-
íû õîòÿ áû îäíîé äóãîé).
    Ðàññìîòðèì òåïåðü ìíîæåñòâî êðèòåðèåâ .. Êàæäûé ÷àñòíûé êðèòå-
ðèé fn∈. çàäàåò íàïðàâëåíèå âîçðàñòàíèÿ ïðåäïî÷òåíèÿ îáúåêòîâ, â ñî-
îòâåòñòâèè ñ óâåëè÷åíèåì èõ îöåíîê, îïðåäåëÿåìûõ â êîëè÷åñòâåííîé
èëè ðàíãîâîé øêàëå, ò. å. ìîæíî çàäàòü áèíàðíîå îòíîøåíèå ïðåäïî÷-
58


òåíèÿ (ïðåâîñõîäñòâà) Pf , êîòîðîå ñâÿçûâàåò ïàðó îáúåêòîâ ìíîæåñòâà
V: (v,v') ∈ Pf , åñëè îöåíêà p(v) ≤ p(v').
    Äëÿ êàæäîãî ÷àñòíîãî êðèòåðèÿ fn ìîæíî ïîñòðîèòü ãðàô Gn=(V,Un)
(çäåñü Un – ìíîæåñòâî âñåõ äóã ãðàôà Gn), â êîòîðîì ïðîâîäèòñÿ äóãà
(v,v')∈Un, åñëè îöåíêà pn(v)<pn(v'), ò. å. ñòðåëêà äóãè ïîêàçûâàåò íà ïðåä-
ïî÷òèòåëüíûé îáúåêò è ïðîâîäÿòñÿ âñòðå÷íûå äóãè (v,v'), (v',v) ∈ Un,
åñëè pn(v)=pn(v'). Ãðàô Gn =(V,Un) áóäåò òðàíçèòèâíûì è ðåôëåêñèâ-
íûì, íî íå áóäåò àñèììåòðè÷íûì, òàê êàê ìåæäó äâóìÿ âåðøèíàìè ìî-
ãóò áûòü âñòðå÷íûå äóãè.
    Òðàíçèòèâíîå è ðåôëåêñèâíîå îòíîøåíèå Pf íàçûâàåòñÿ êâàçèïîðÿä-
êîì, à ïðè óñëîâèè, ÷òî ëþáûå äâà îáúåêòà ñðàâíèìû ïî Pf : (v,v') ∈ Pf èëè
(v',v) ∈ Pf , îíî íàçûâàåòñÿ ëèíåéíûì, èëè ïîëíûì êâàçèïîðÿäêîì.
    Ââåäåì îòíîøåíèå íåðàçëè÷èìîñòè Nf äëÿ îáúåêòîâ ñ p(v)=p(v'):
(v,v') ∈Nf. Ýòî òðàíçèòèâíîå, ðåôëåêñèâíîå è ñèììåòðè÷íîå îòíîøå-
íèå, íàçûâàåìîå ýêâèâàëåíòíîñòüþ, îòðàæàåòñÿ íà ãðàôå Gn êîíòó-
ðàìè è ïîðîæäàåò êëàññû (ïîäìíîæåñòâà) ýêâèâàëåíòíûõ îáúåêòîâ
K i⊆V. Ìåæäó êëàññàìè ýêâèâàëåíòíîñòåé ñóùåñòâóåò îòíîøåíèå
ñòðîãîãî ïðåäïî÷òåíèÿ: (v(K),v(K')) ⊆ P, åñëè p(v(K)) < p(v(K')). Ýòè
îòíîøåíèÿ, íàçûâàåìûå êâàçèñåðèÿìè, ðåôëåêñèâíû è òðàíçèòèâ-
íû. Êâàçèñåðèþ P, äëÿ êîòîðîé Nf ÿâëÿåòñÿ îòíîøåíèåì ðàâåíñòâà, ò.
å. (v,v')∈Nf →v=v' íàçûâàþò ñåðèåé. Ñåðèè ñîîòâåòñòâóþò ñòðîãîìó
óïîðÿäî÷åíèþ îáúåêòîâ.
    Ïîëíûé êâàçèïîðÿäîê ÿâëÿåòñÿ ïîëíûì ïîðÿäêîì, èëè ñåðèåé, òîãäà
è òîëüêî òîãäà, êîãäà îí àíòèñèììåòðè÷åí, ò. å. êîãäà êëàññû ýêâèâàëåí-
òíîñòåé ñâåäåíû ê îäíîìó îáúåêòó:
                          (v,v')∈Nf è (v',v)∈Nf → v=v'.
    Òàêèì îáðàçîì, ãðàô Gn âîñïðîèçâîäèò îòíîøåíèå ïîëíîãî êâàçè-
ïîðÿäêà íà ìíîæåñòâå îáúåêòîâ V íà îñíîâàíèè êðèòåðèÿ fn.
    Óêàçàâ ðÿäîì ñ âåðøèíàìè ãðàôà çíà÷åíèÿ îöåíîê îáúåêòîâ, ïîëó-
÷åííûõ â êîëè÷åñòâåííîé èëè ðàíãîâîé øêàëå, ìîæíî îòðàçèòü íà ãðà-
ôå âñþ èíôîðìàöèþ ïî ñðàâíåíèþ îáúåêòîâ.
    Ñîâìåñòèâ îäíîèìåííûå âåðøèíû ãðàôîâ Gn, n = 1, N , ïîëó÷èì ìóëü-
òèãðàô GV, îòðàæàþùèé èíôîðìàöèþ äëÿ ñðàâíåíèÿ ìíîæåñòâà îáúåê-
òîâ V ïî ìíîæåñòâó êðèòåðèåâ ..
                                   Ïðèìåð
Íà îñíîâå ðàíæèðîâàííîé ìàòðèöû îöåíîê R4×6, ïîëó÷åííîé â ïðåäû-
äóùåì ïðèìåðå äëÿ ÷åòûðåõ îáúåêòîâ ñðàâíåíèÿ, íà ðèñ. 4.1 ïîñòðîåíû
                                                                        59


÷àñòíûå ãðàôû G n äëÿ êðèòåðèåâ fn (n= 1,6 ) ïî ÷åòûðåì âåðøèíàì
(îáúåêòàì – v1,v2,v3,v4), ãäå ÷èñëà ïðè âåðøèíàõ – ýòî çíà÷åíèÿ ðàí-
æèðîâàííûõ îöåíîê îáúåêòîâ ñðàâíåíèÿ. Ïîñëå ñîâìåùåíèÿ âåðøèí
è íàëîæåíèÿ äóã ïîëó÷èì ìóëüòèãðàô GV (ðèñ. 4.2,à), ãäå ÷èñëà ïðè
äóãàõ ïîêàçûâàþò êîëè÷åñòâî ïàðàëëåëüíûõ äóã äàííîãî íàïðàâëå-
íèÿ.
         v             v!          v             v!        v              v!
     1                  5         7               10       9                   4

     3                 10         1                  7     1                   10
         v           v"           v           v"         v            v"
              v→G                     v →G                     v!→G!


         v            v!          v             v!        v              v!
 10                    1      6                      1    1                    6

 9                     10     2                      10   10                   8
         v           v"          v            v"         v            v"
              v"→G"                     v#→G#                   v$→G$
                            Ðèñ.4.1. ×àñòíûå ãðàôû Gn

    Â ìóëüòèãðàôå GV íàðóøàåòñÿ òðàíçèòèâíîñòü îòíîøåíèÿ íåðàçëè-
÷èìîñòè, âñëåäñòâèå íåîáõîäèìîñòè ñðàâíèâàòü ïî íåñêîëüêèì êðèòå-
ðèÿì. Íåîáõîäèìî ââåñòè íîâîå îòíîøåíèå, êîòîðîå òðàíñôîðìèðîâàëî
áû ìóëüòèãðàô GV â ãðàô G=(V,U), âîñïðîèçâîäÿùèé êâàçèïîðÿäîê íà
ìíîæåñòâå V ñ ó÷åòîì îöåíîê ïî âñåì êðèòåðèÿì.
    Ïðåîáðàçîâàíèå GV → G=(V,U) ñâîäèòñÿ ê óñòàíîâëåíèþ ïðàâèëà,
êîòîðîå ïîçâîëÿåò çàìåíèòü ìíîæåñòâî äóã ìåæäó âåðøèíàìè v è v' â
GV ê äóãå (v,v')∈U èëè (v',v)∈U â ãðàôå G.
    Ñàìîå ïðîñòîå ïðàâèëî ïðåîáðàçîâàíèÿ GV→G ñâîäèòñÿ ê ïðèí-
öèïó ãîëîñîâàíèÿ (áîëüøèíñòâà), ïî êîòîðîìó â ãðàôå G ïðîâîäèòñÿ
äóãà (v,v'), åñëè â ãðàôå GV êîëè÷åñòâî äóã (v,v') ïðåâûøàåò ÷èñëî
äóã (v',v), à â ñëó÷àå ðàâåíñòâà ïðîâîäÿòñÿ âñòðå÷íûå äóãè (v,v') è
(v',v), ïðè ýòîì âåñà äóã ïîëàãàþòñÿ îäèíàêîâûìè, ò. å. èãíîðèðóåòñÿ

60



    

Минпросвещения России

ФГАУ ГНИИ ИТТ «Информика»

Рособрнадзор

Федеральная университетская компьютерная сеть РФ

Федеральный портал "Российское образование"

Единое окно доступа к образовательным ресурсам