Анализ очередности выполнения запросов в информационно-поисковых системах

A^k - k-я степень матрицы А

tr(A^k) - след матрицы A^k (сумма диагональных элементов)

Собственный вектор квадратной матрицы А – это такой ненулевой  вектор W, который удовлетворяет  уравнению  , то есть матрицей линейного преобразования А он преобразуется в коллинеарный вектор λ*W. Величина λ, соответствующая такому преобразованию, называется собственным значением матрицы А.

Каждый собственный вектор определяется с точностью до постоянного  множителя. W = (W₁, W₂, W₃)

Собственный вектор обладает одним замечательным свойством: если в n-мерном пространстве выбрать  в качестве базиса систему, состоящую  из n собственных векторов линейного  преобразования, то матрица А этого  преобразования принимает следующий  диагональный вид:

С учетом этого след матрицы  равен

Определитель матрицы 

A²W = A(AW) = A(λW) = λ(AW) = λ²W

По индукции можно доказать, что A^kW = λ^kW , следовательно, след матрицы равен

e = (l,l,...,1)T, T - знак транспонирования

W - собственный вектор  матрицы А, соответствующий ее главному собственному значению λ = λ_max

С - постоянная.

Отношение согласованности  ОС вычисляется по формуле:

ОС = ИС/СИ;

где: ОС - отношение согласованности, ИС - индекс согласованности:

ИС = (λ_max - n)/(n-1), где СИ - случайный индекс.

Если ОС > 0,1, то матрица  противоречива, иначе непротиворечивость матрицы считается удовлетворительной.

Результаты  программного расчёта:

λ_max = 3,16

W (W₁, W₂, W₃) = (0,709; 0,212; 0,0791)

Количество итераций равно 5

Отношение согласованности = 0,141

так как ОС > 0,1 следовательно матрица противоречива.

 

Интерфейс программы и  результаты расчёта представлены на рисунке 3.2.1

Рисунок 3.2.1 - Интерфейс программы

 

3.3  Оценка согласованности  мнений экспертов при групповой  экспертизе

Групповым выбором называется принятие согласованного группового решения  о порядке или степени предпочтения рассматриваемых объектов на основе индивидуальных мнений членов группы экспертов.

Данная часть курсовой работы была выполнена с помощью программы №3 (Листинг программного кода представлен в приложении 3).

Данная программа:

-   Вычисляет коэффициент конкордации матрицы X и оценивает его  значимость на уровне значимости a.

- Вычисляет коэффициенты ранговой корреляции Спирмена и Кендалла между всеми парами экспертов. Оценивает их значимость на уровне значимости a.

-   Делает вывод о степени согласованности всей группы, а также по каждой паре экспертов.

-  Вычисляет по каждому запросу:

- групповой средний ранг

- медиану распределения рангов.

 

Алгоритмы, используемые при  написании программы:

 

1. Конкордация.

Результаты опроса М экспертов  относительно N объектов даны в ранговой шкале, т.е. X_ij – это ранг, который i-тый эксперт приписал j-тому объекту. В результате получается следующая матрица:

X=||X_ij||_MXN,

коэффициент конкордации  для этой матрицы будет равен:

Оценить значимость коэффициента конкордации на уровне значимости a можно, используя распределение x² с параметрами a=0,05; ν=N-1=9

(x² =16,9). (Если N≥10, то WM(N-1)~ x².)

Если  x²> x²_кр, то согласие считается удовлетворительным на заданном уровне значимости a, в противном случае - нет.

 

2.  Коэффициент  ранговой корреляции Спирмена.

Коэффициент ранговой корреляции Спирмена рассчитывается следующим образом: 

- разность рангов между объектами. Если N≥9, то оценивать его значимость на уровне значимости a нужно, используя Т-распределение Стьюдента с ν=N-2=8 степенями свободы:

, где  =1,86 (a=0,05; ν=8).

При этом если R_s набл > T_кр, то можно считать, что согласие удовлетворительное на заданном уровне значимости; в противном случае – нет.

3.  Коэффициент  ранговой корреляции Кендалла.

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

Если N≥11, то оценивать его  значимость на уровне значимости a нужно, используя стандартное нормальное распределение. При этом:

, где z_кр =1,64(a=0,05).

При этом если R_k набл > T_кр, то можно считать, что согласие удовлетворительное на заданном уровне значимости; в противном случае – нет.

4.  Медиана распределения рангов.

Алгоритм нахождения медианы  базируется на определении.

Медиана – это такое  число, что количество оценок, меньших  этого числа, равно количеству оценок, большему этого числа.

Т.к. общее количество оценок, которые присваиваются объекту, равно четырем, то алгоритм сводится к следующему: программа располагает  эти оценки в порядке возрастания  рангов, начиная с наименьшего. На следующем этапе программа находит  второй элемент списка, упорядоченного таким образом, и прибавляет к  этому значению 0,5.

 

5. Средний  групповой ранг.

Групповой средний ранг находится  по формуле:

, где N = [1..10], M = [1..4].

 

В результате программного расчёта для матрицы представленной таблицей 3.3.1 ниже были получены:

 

Таблица 3.3.1 - Матрица X

Эксперты	Объекты
	1	2	3	4	5	6	7	8	9	10
1	6	8	10	1	3	5	7	9	2	4
2	8	10	1	3	5	7	9	2	4	6
3	10	1	3	5	7	9	2	4	6	8
4	1	3	5	7	9	2	4	6	8	10

 

Коэффициент конкордации  W=0.076

Оценка значимости коэффициента конкордации на уровне значимости a=0.05:

 x²_набл = 2.7273

Так как x²_набл < x²_кр, то следовательно можно сделать вывод о несогласованности выводов экспертов.

Коэффициенты ранговой корреляции Спирмена и Кендалла между всеми парами экспертов а так же оценка их значимости на уровне значимости a представлены в таблицах 3.3.2 и 3.3.3 соответственно.

 

Таблица 3.3.2 - Коэффициенты ранговой корреляции Спирмена

Пара экспертов	Rs	Tкр.	Согласие экспертов
1 и 2	0.018	0.658	Неудовлетворительное
1 и 3	-0.479	0.577	Неудовлетворительное
1 и 4	-0.491	0.573	Неудовлетворительное
2 и 3	0.018	0.658	Неудовлетворительное
2 и 4	-0.479	0.577	Неудовлетворительное
3 и 4	0.018	0.658	Неудовлетворительное

 

 

Таблица 3.3.3  - Коэффициенты ранговой корреляции Кендалла

Пара экспертов	Rк	Tкр.	Согласие экспертов
1 и 2	0.244	0.407	Неудовлетворительное
1 и 3	-0.156	0.407	Неудовлетворительное
1 и 4	-0.200	0.407	Неудовлетворительное
2 и 3	0.244	0.407	Неудовлетворительное
2 и 4	-0.156	0.407	Неудовлетворительное
3 и 4	0.244	0.407	Неудовлетворительное

 

Медиана распределения рангов представлена в таблице 3.3.4.

 

Таблица 3.3.4  - Медиана распределения рангов

1	2	3	4	5	6	7	8	9	10
7	5.5	4	4	6	6	5.5	5	5	7

 

Средний групповой ранг представлен  в таблице 3.3.5.

Таблица 3.3.5 - Средний групповой ранг

1	2	3	4	5	6	7	8	9	10
6.25	5.5	4.75	4	6	5.75	5.5	5.25	5	7

 

Интерфейс программы представлен  на рисунке 3.3.1

Рисунок 3.3.1 - Интерфейс программы.

 

4 ВЫБОР ПРОГРАММНЫХ СРЕДСТВ  ДЛЯ РЕШЕНИЯ ЗАДАЧИ

 

Для программной реализации данного проекта выбрана среда  программирования Borland Delphi 7.

Cистема объектно-ориентированного программирования Delphi производства корпорации Borland предназначена для операционных систем семейства Windows. Интегрированная среда Delphi обеспечивает скорость визуальной разработки, продуктивность повторно используемых компонент в сочетании с мощью языковых средств Delphi, усовершенствованными инструментами и разномасштабными средствами доступа к базам данных.

Delphi включает обширный набор средств, которые повышают производительность труда программистов и сокращают продолжительность цикла разработки. Многофункциональная интегрированная среда разработки Delphi включает компилятор, удовлетворяющий стандарта ANSI/ISO, встроенный дизайнер форм, богатый набор средств для работы с компонентами, инструмент Object Inspector, менеджер проектов и отладчик.

 

5 БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Конспект лекций по курсу «Теория принятия решений» (Лектор-доцент Данилов Г.В.).
2. Конспект лекций по курсу «Системный анализ» (Лектор-доцент Данилов Г.В.).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЯ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ А

 

Программа "Определение по Парето групповой очередности выполнения запросов в автоматизированной информационно-поисковой системе".

Листинг программного модуля "Unit1.pas":

unit Unit1;

 

interface

 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Grids, Spin, ExtCtrls, Buttons;

 

type

  TForm1 = class(TForm)

    StringGrid1: TStringGrid;

    StringGrid2: TStringGrid;

    Button1: TButton;

    Button2: TButton;

    Button3: TButton;

    SpinEdit1: TSpinEdit;

    SpinEdit2: TSpinEdit;

    Label1: TLabel;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    ListBox1: TListBox;

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

var

  Form1: TForm1;

  m{Кол-во критериев},n{Кол-во задач}: integer;

  a{матрица оценок}: array of array of integer;

  b{Булева матрица}: array of array of integer;

  flag: array of integer;

  k:integer;

implementation

 

{$R *.dfm}

 

procedure TForm1.Button1Click(Sender: TObject);

var

  i,j :integer;

begin

  Randomize;

  m := SpinEdit1.Value;

  n := SpinEdit2.Value;

  StringGrid1.RowCount := m + 1;

  StringGrid1.ColCount := n + 1;

  StringGrid2.ColCount := n + 1;

  StringGrid2.FixedCols:=1;

  StringGrid2.RowCount := n + 1;

  StringGrid2.FixedRows:=1;

 

  ListBox1.Clear;

  SetLength(a,n,m);

  m := m - 1;

  n := n - 1;

  for i := 0 to n do{Заполняем матрицу показателей}

    begin

      StringGrid1.Cells[i+1,0] := inttostr(i+1);

      for j := 0 to m do

        begin

          a[i,j] := random(11)+(j div 5)+1;;

          StringGrid1.Cells[0,j+1] := inttostr(j+1);

          StringGrid1.Cells[i+1,j+1] := inttostr(a[i,j]);

        end;

    end;

  Button2.Enabled:=True;

end;

 

procedure TForm1.Button2Click(Sender: TObject);

var

  i,j:integer;

begin

  SetLength(flag,n + 1);

  SetLength(b,n + 1,n + 1);

  for k := 0 to n do

    begin

      for j := 0 to n do

        begin

          b[k,j] := 1;

          {если хотя бы один критерий k строки меньше критерия j столбца, то 0}

          for i := 0 to m do

            if a[k,i] < a[j,i] then

              b[k,j] := 0;

          if j = k then

            b[k,j] := 0;

          StringGrid2.Cells[j + 1,k + 1] := inttostr(b[k,j]);

        end;

      StringGrid2.Cells[0,k + 1] := inttostr(k + 1);

      StringGrid2.Cells[k + 1,0] := inttostr(k+1);

    end;

  for i := 0 to n do

    flag[i] := 0;

  k := 0;

  Button3.Enabled:=True;

end;

 

procedure TForm1.Button3Click(Sender: TObject);

var

  i, j, c, d: integer;

  f2:boolean;

  s:string;

begin

  if k < n then

    begin

      c := 0;

      s:='';

      {вывод булевы матрицы}

      for i := 0 to n do if flag[i] = 0 then inc(c);

      StringGrid2.ColCount := c + 1;

      StringGrid2.RowCount := c + 1;

      c := 1;

      for i := 0 to n do

        if flag[i] = 0 then

          begin

            StringGrid2.Cells[c,0] :=  IntToStr(i + 1);