Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
HannaBury,DariuszWagner
InstytutBadańSystemowychPANwWarszawie
EFEKTYWNEMETODYWYZNACZANIA
MEDIANYKEMENY’EGO
Wprowadzenie
Istniejewielesposobówupraszczaniazadaniawyznaczaniamediany
Kemeny,ego,którewprzypadkuogólnymstanowiproblemNP-trudny.Wpra-
cyprzedstawionojednąztakichmetod.
Założymy,żedanyjestzbiórobiektówO={O1,…,On}orazzbióreks-
pertówK={1,...,K}.Zadaniemekspertówjestuporządkowaniezbioru
obiektówzgodniezprzyjętymkryteriumlubzbioremkryteriów.Zakładamy
również,żewszystkieobiektyzezbioruOsąporównywanezesobąoraz,że
wopiniachekspertówmogąwystępowaćobiektyrównoważne.Wdotychcza-
sowychrozważaniachposługiwanosięprzedewszystkimmacierzamiporównań
paramiorazwyznaczanąnaichpodstawietzw.macierząstratR.Celempracy
jestzwrócenieuwaginafakt,żemożnauzyskaćinteresującewynikiwpro-
wadzającdorozważańmacierzrozkładugłosówekspertówL.
ZaproponowanametodawykorzystujetwierdzenieLitvaka[3]podające
warunekkoniecznyidostateczny,którymusispełniaćuporządkowanie,abysta-
nowiłomedianę.Możnapokazać–wykorzystująctotwierdzenieorazzależ-
nościmiędzymacierzamiRiL–żewyznaczaniemedianysprowadzasiędo
wyznaczeniarelacjiwiększości,jakąpowinnyspełniaćobiektytworząceszu-
kaneuporządkowanie.Następnienależydokonaćeliminacjizezbioruwszyst-
kichmożliwychuporządkowańnobiektówtychuporządkowań,wktórychwy-
maganerelacjewiększościmiędzyobiektaminiesąspełnione.Jeżeliwwyniku
tegopostępowaniaotrzymanowięcejniżjednouporządkowanie,należywybrać
to,któregoodległość(wsensieKemeny,ego)odzbioruuporządkowańpo-
danychprzezekspertówjestnajmniejsza.
1.DefinicjemedianyKemeny’ego.Podejścieklasyczne[1]
Ocenyparyobiektówpodaneprzezekspertówmogąmiećpostać(dla
uproszczeniazapisupominiętoindekseksperta)
