Решение обобщенной задачи о назначениях в системно-когнитивном анализе

Размещено на http://www.allbest.ru/

Решение обобщенной задачи о назначениях в системно-когнитивном анализе

Различные варианты задачи о назначениях См.: http://slovari.yandex.ru/dict/lopatnikov/article/lop/lop-0407.htm&stpar1=1.8.1 часто встречаются в самых различных предметных областях, от управления запасами на стационарных складах и воздушных, водных и подводных судах до управления очередями заданий в различных системах массового обслуживания (СМО), например в супермаркетах и многопроцессорных системах.

Рассмотрим на уровне неформальной постановки и алгоритмов решения различные варианты задачи о назначениях (рюкзаках или ранцах http://slovari.yandex.ru/dict/lopatnikov/article/lop/lop-0409.htm&stpar1=1.10.1) во все более общих постановках, учитывающих:

Задача-1: различные размеры грузов и объемы рюкзаков;

Задача-2: различную полезность http://slovari.yandex.ru/dict/lopatnikov/article/lop/lop-1102.htm грузов, зависящую только от грузов и различные затраты на их размещение, а также ограничения на ресурсы, связанные с рюкзаками, затрачиваемые на грузы при их размещении;

Задача-3: различную полезность каждого груза для разных рюкзаков, различные затраты на размещение грузов и различные ресурсы хозяев рюкзаков.

Задача-4: тоже, что в 3-й задаче, плюс автоматическое прогнозирование степени полезности грузов для разных рюкзаков на основе признаков этих грузов путем решения задачи распознавания с применением модели, основанной на базе прецедентов.

Для решения 4-й задачи, впервые встречающейся в литературе, применим технологию и методику системно-когнитивного анализа и его инструментарий - систему «Эйдос».

Задача-1.

Дано: размеры грузов и объемы рюкзаков;

Необходимо: разместить грузы по рюкзакам так, чтобы для размещения наиболее важные грузы были размещены в первую очередь и при этом было использовано минимальное количество рюкзаков, причем рюкзаки были максимально заполнены (т.е. остатки пустого места минимальны). Будем считать, что важность грузов пропорциональна их размерам.

Алгоритм решения (LPT-longest processing time): Заполняем рюкзак грузами в порядке убывания их размера до тех пор, пока не превышен объем рюкзака, иначе берем самый большой новый пустой рюкзак и продолжаем процесс, или подробнее по шагам:

Шаг-1. Сортируем рюкзаки в прядке убывания их размеров.

Шаг-2. Сортируем грузы по порядку убывания их размера.

Шаг-3. Организуем цикл по рюкзакам в порядке убывания их размера.

Шаг-4. Размещаем самый большой предмет из еще не размещенных, который помещается в оставшемся свободном месте текущего рюкзака. Вычисляем остаток свободного места в рюкзаке.

Шаг-5. Если остаток свободного места в текущем рюкзаке позволяет разместить в нем по крайней мере самый маленький груз из еще не размещенных, то переход на шаг-4, иначе - на шаг-6.

Шаг 6. Остались еще остались незаполненные рюкзаки? Если да, то переход на шаг-7, иначе - на шаг-8.

Шаг-7. Берем следующий (очередной) рюкзак, самый большой и оставшихся и переходим на шаг-4.

Шаг-8. Выход.

Задача-2

Дано:

- различная полезность грузов;

- различные затраты на размещение грузов;

- ограничения на ресурсы, связанные с рюкзаками, затрачиваемые на грузы при их размещении.

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

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

Шаг-1. Находим удельную полезность каждого груза (полезность/затраты) Необходимо отметить, что идея об использовании «удельной полезности» (или аналогичная), не принадлежит авторам статьи и не раз встречается в Internet , т.е. полезность единицы затрат при размещении данного груза.

Шаг-2. Сортируем грузы в порядке убывания удельной полезности.

Шаг-3. Сортируем рюкзаки в прядке убывания их ресурсов.

Шаг-3. Организуем цикл по рюкзакам в порядке убывания их ресурсов.

Шаг-4. Организуем цикл по грузам в порядке убывания их удельной полезности.

Шаг-5. Размещаем груз с наибольшей удельной полезностью из еще не размещенных, на который в текущем рюкзаке есть ресурсы. Вычисляем остаток ресурсов рюкзака (вычитаем из его текущих ресурсов затраты на размещение текущего груза).

Шаг-6. Если остаток ресурсов текущего рюкзака позволяет разместить в нем по крайней мере груз с наименьшими затратами из еще не размещенных, то переход на шаг-5, иначе - на шаг-7.

Шаг 7. Остались еще остались незаполненные рюкзаки? Если да, то переход на шаг-8, иначе - на шаг-9.

Шаг-8. Берем следующий очередной рюкзак, самый большой по ресурсам из оставшихся и переходим на шаг-4.

Шаг-9. Выход.

Задача-3

Дано:

- различная полезность каждого груза для разных рюкзаков;

- различные затраты на размещение грузов;

- ограничения на ресурсы, связанные с рюкзаками, затрачиваемые на грузы при их размещении.

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

Алгоритм: Помещаем грузы в рюкзаки, для которых их удельная полезность максимальна, до тех пор, пока не распределены все грузы и это позволяют ресурсы рюкзаков, или подробнее по шагам:

Шаг-1. Находим удельную полезность каждого груза для каждого рюкзака: (полезность для рюкзака)/затраты, т.е. полезность единицы затрат для каждого варианта размещении каждого груза в каждом рюкзаке.

Шаг-2. Сортируем варианты размещения грузов в порядке убывания удельной полезности для всех грузов и рюкзаков. В этой базе данных каждый груз будет встречаться столько раз, сколько есть рюкзаков, но размещаться будет только один из них.

Шаг-3. Организуем цикл по вариантам размещения грузов в порядке убывания их удельной полезности.

Шаг-5. Размещаем груз с наибольшей удельной полезностью из еще не размещенных, в рюкзаке, для которого удельная полезность максимальна при условии, что это позволяют ресурсы рюкзака. Иначе данный вариант размещения больше не рассматривается. Вычисляем остаток ресурсов рюкзака (вычитаем из его текущих ресурсов затраты на размещение текущего груза).

Шаг-6. Остались еще не рассмотренные варианты размещения грузов по рюкзакам? Если да - то переход на шаг-5, иначе - на шаг 7.

Шаг-7. Выход.

Задача-4

Дано:

- различные признаки грузов и база прецедентов, в которой содержится информация о том, на сколько грузы с теми или иными признаками ранее были полезными (или нет) и для тех или иных рюкзаков;

- различные затраты на размещение грузов;

- ограничения на ресурсы, связанные с рюкзаками, затрачиваемые на грузы при их размещении.

Необходимо:

- на основе базы прецедентов (обучающей выборки) разработать модель, которая отражала бы влияние признаков грузов на степень их полезности для различных рюкзаков;

- на основе созданной модели определить или спрогнозировать степень полезности каждого груза для каждого из рюкзаков, т.е. для каждого варианта размещения;

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

Обобщенный алгоритм:

Этап-1. Синтез модели, отражающей влияние признаков грузов на их полезность для разных рюкзаков.

Этап-2. Прогнозирование степени полезности грузов для разных рюкзаков на основе признаков этих грузов путем решения задачи распознавания с применением модели, основанной на базе прецедентов.

Этап-3. Размещение грузов в рюкзаки, для которых их удельная полезность максимальна, до тех пор, пока не распределены все грузы и это позволяют ресурсы рюкзаков, или подробнее по шагам:

Возможны различные подходы к решению этой задачи. Первые два этапа могут быть реализованы с помощью различных технологий искусственного интеллекта [2, 3]. Известно См.: http://slovari.yandex.ru/dict/lopatnikov/article/lop/lop-0407.htm&stpar1=1.8.1, что третий этап может быть реализован с применением методов линейного, нелинейного и динамического программирования.

Однако у этих подходов есть свои проблемы:

1. Труднодоступность или фактическое отсутствие программного обеспечения, позволяющего строить на основе прецедентов и применять для прогнозирования модели влияния признаков объектов на их полезность для различных применений.

2. Очень значительные затраты вычислительных ресурсов (прежде всего времени) при решении подобных задач, даже при очень ограниченных размерностях, весьма и далеких от реальных.

По поводу 1-й проблемы можно сказать, что не вполне ясен, даже чисто в научном плане, общий подход к определению полезности, тем более в количественной форме, тем более при большом количестве объектов и их применений (классов). Таким образом, полезность даже определить трудно, но ясно одного определения самого по себе еще совершенно недостаточно, т.к. для решения задачи на практике необходимо еще и ввести эту полезность в соответствующие базы данных, что вручную сделать в большинстве реальных случаев практически невозможно. Следовательно, необходимо специальное программное обеспечение, позволяющее не только количественно определять полезность большого количества объектов для значительного количества их применений на основе признаков этих объектов, но и автоматически вводить эту информацию (наряду с другой, указанной в условиях задачи) в соответствующие базы данных, а также имеющее режимы, непосредственно обеспечивающие решение задачи о назначениях в универсальной форме, независящей от предметной области.

Дано:

У Мальвины есть ящик разных яблок: больших и маленьких, красных и зеленых, сладких и кислых, блестящих и матовых, ароматных и не очень и т.д.

Буратино любит большие сладкие, ароматные и блестящие красные яблоки, т.к. они веселят его, а Пьеро больше нравятся маленькие, кислые, матовые, зеленые и не очень ароматные яблоки, т.к. от них он становится еще более грустным.

Но яблок, практически полностью удовлетворяющих этим идеальным для Буратино и Пьеро стандартам, в ящике всего несколько, а остальные занимают промежуточное между ними положение.

Мальвина решила немного подзаработать на этой ситуации и для каждого яблока объявила свою цену по своему усмотрению.

Остается добавить, что и у Буратино, и у Пьеро еще оставалось по нескольку золотых, которые они еще просто не успели или забыли зарыть в стране дураков.

Необходимо: так распределить яблоки между Буратино и Пьеро, чтобы на имеющиеся у каждого из них деньги он получил максимум удовлетворения, т.е. чтобы суммарная польза от распределения яблок была максимальна, а затраты минимальны.

Решение:

При попытке решения этой задачи методом прямого перебора всех возможных вариантов распределения блок между Буратино и Пьеро даже при небольшом количестве яблок возникает сложноразрешимая проблема комбинаторного взрыва:

- если бы яблоко было одно, то было бы всего два варианта, кому его отдать (по числу подсистем);

- если появляется еще одно яблоко, то количество вариантов удваивается, т.к. каждый из ранее существовавших вариантов «расщепляется» на два в зависимости от того, кому отдано второе яблоко;

- третье яблоко приводит к расщеплению на два каждого из вариантов, возникших на предыдущем этапе;

- и вообще, если дано N объектов, которые необходимо распределить на две подсистемы, то получается 2 в степени N различных вариантов этого распределения.

Если же еще появится Некто (с котором Буратино не хотел делиться яблоками), то каждый предыдущий варианта будет расщепляться не на 2, а на 3 варианта. И вообще, если имеется K подсистем, по которым распределяется N объектов, то возможно K^N (K в степени N) различных вариантов распределения. Это очень много даже для сравнительно небольшого количества подсистем и распределяемых объектов. Например, существует 5¹⁰=9765625 различных вариантов распределить 10 объектов по 5 классам. Поэтому необходим какой-то нетривиальный подход, не основанный на полном переборе вариантов, чтобы решить эту задачу.

Для решения сформулированных проблем в данной работе все эти этапы, включая и 3-й, предлагается осуществлять с помощью системно-когнитивного анализа (СК-анализ) и его инструментария - универсальной когнитивной аналитической системы «Эйдос» (система «Эйдос») [1-10]. Алгоритм 3-го этапа не отличается от алгоритма задачи-3.

Сформулируем (на неформальном уровне) общую постановку задачи о назначениях в традиционной терминологии СК-анализа. Размещаемые грузы будем называть объектами или элементами, а рюкзаки классами или подсистемами. В качестве количественной меры «пользы» от размещения объекта в классе (для самого класса и системы в целом) будем рассматривать сходство образа данного конкретного объекта с обобщенным образом класса, т.е. по сути количество информации, содержащееся в системе признаков объекта о его принадлежности к данному классу.

Дано:

1. Элементы имеют свойства и в разной степени подходят для различных подсистем, но в какой именно степени подходят - это надо еще определить (это задача распознавания).

2. На включение элементов в состав подсистем затрачиваются определенные ресурсы подсистем, т.е. каждому элементу соответствуют затраты, а подсистемам - ресурсы.

3. Все элементы различны.

4. Каждый элемент может быть назначен единственной подсистеме.

Необходимо: максимизировать суммарный системный эффект (пользу) от распределения элементов по подсистемам и желательно при этом минимизировать суммарные затраты.

Далее на условном примере небольшой размерности рассмотрим подробнее как реализуются все эти этапы в системе «Эйдос». Размерность примера выбрана таким образом, чтобы необходимые базы данных можно было полностью привести в статье.

В режиме _154 (рисунок 1) сгенерируем случайную модель с параметрами, представленными на рисунке 2:

Рисунок 1. Экранная форма вызова режима _154 системы «Эйдос»

Рисунок 2. Параметры случайной модели

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

Таблица 1 - СПРАВОЧНИК КЛАССОВ

KOD	NAME
1	Klass_1
2	Klass_2
3	Klass_3
4	Klass_4
5	Klass_5

Таблица 2 - СПРАВОЧНИК ПРИЗНАКОВ

KOD	NAME
1	Atr_1
2	Atr_2
3	Atr_3
4	Atr_4
5	Atr_5
6	Atr_6
7	Atr_7
8	Atr_8
9	Atr_9
10	Atr_10

Таблица 3 - ОБУЧАЮЩАЯ ВЫБОРКА (БАЗА ПРЕЦЕДЕНТОВ)

Код объекта	Наименование объекта	Коды классов	Коды признаков
		Klass1	Klass2	Klass3	Atr1	Atr2	Atr3	Atr4	Atr5
1	Ist-00001	2	3	4	2	3	5	6	8
2	Ist-00002	1	2	4	1	7	8	9	10
3	Ist-00003	1	3	5	1	2	3	4	6
4	Ist-00004	1	3	5	3	4	6	9	10
5	Ist-00005	1	2	4	5	6	7	8	10
6	Ist-00006	1	2	5	2	3	6	7	8
7	Ist-00007	1	4	5	1	3	5	6	9
8	Ist-00008	2	3	5	5	6	7	9	10
9	Ist-00009	2	3	5	1	3	5	6	8
10	Ist-00010	1	3	4	1	2	5	7	10
11	Ist-00011	1	3	4	1	2	3	8	9
12	Ist-00012	1	3	5	1	2	3	6	9
13	Ist-00013	2	3	4	1	4	5	7	10
14	Ist-00014	1	2	3	1	2	3	4	5
15	Ist-00015	1	2	5	1	3	7	9	10
16	Ist-00016	2	3	5	2	4	6	9	10
17	Ist-00017	1	2	4	4	6	8	9	10
18	Ist-00018	1	4	5	3	4	7	9	10
19	Ist-00019	1	3	4	1	2	4	7	8
20	Ist-00020	1	4	5	1	2	3	6	8
21	Ist-00021	1	3	5	2	3	4	8	10
22	Ist-00022	3	4	5	2	3	5	6	7
23	Ist-00023	1	3	5	4	6	8	9	10
24	Ist-00024	2	3	4	1	2	6	8	9
25	Ist-00025	2	4	5	1	3	4	6	7
26	Ist-00026	2	3	4	3	5	6	9	10
27	Ist-00027	2	3	4	1	4	5	7	10
28	Ist-00028	1	3	5	1	2	6	8	10
29	Ist-00029	1	2	5	1	2	3	6	8
30	Ist-00030	1	2	4	1	4	6	8	10
31	Ist-00031	1	3	4	1	6	7	8	9
32	Ist-00032	1	2	3	1	2	7	8	10
33	Ist-00033	2	3	5	1	3	5	8	9
34	Ist-00034	1	4	5	1	2	5	7	8
35	Ist-00035	1	4	5	3	5	6	7	10
36	Ist-00036	1	2	4	1	2	5	6	7
37	Ist-00037	1	3	4	5	7	8	9	10
38	Ist-00038	1	3	4	2	4	5	7	10
39	Ist-00039	1	2	3	1	2	6	9	10
40	Ist-00040	1	2	4	1	3	5	7	8
41	Ist-00041	1	3	5	3	4	7	8	9
42	Ist-00042	1	2	4	3	5	8	9	10
43	Ist-00043	2	4	5	2	6	8	9	10
44	Ist-00044	2	4	5	1	4	5	9	10
45	Ist-00045	1	2	5	1	2	4	6	8
46	Ist-00046	2	3	5	1	2	3	4	7
47	Ist-00047	2	3	5	1	2	5	7	8
48	Ist-00048	1	2	5	3	4	5	7	10
49	Ist-00049	3	4	5	3	4	6	8	9
50	Ist-00050	1	2	5	1	4	5	6	10
51	Ist-00051	1	2	5	2	4	5	6	10
52	Ist-00052	1	3	5	3	7	8	9	10
53	Ist-00053	2	4	5	1	3	8	9	10
54	Ist-00054	1	2	3	4	5	6	8	10
55	Ist-00055	1	2	5	2	3	4	5	9
56	Ist-00056	1	3	4	2	3	4	8	10
57	Ist-00057	2	3	5	2	3	4	6	9
58	Ist-00058	1	2	4	2	5	6	7	8
59	Ist-00059	1	2	3	3	4	8	9	10
60	Ist-00060	2	4	5	2	3	4	7	8
61	Ist-00061	1	3	4	2	4	8	9	10
62	Ist-00062	2	3	5	1	5	7	9	10
63	Ist-00063	1	2	3	2	6	8	9	10
64	Ist-00064	1	4	5	1	5	6	8	10
65	Ist-00065	1	3	5	2	3	7	8	10
66	Ist-00066	1	2	5	3	5	7	8	9
67	Ist-00067	1	2	3	5	6	8	9	10
68	Ist-00068	1	2	5	3	4	6	7	10
69	Ist-00069	2	3	5	3	4	5	6	10
70	Ist-00070	1	4	5	1	3	6	7	8
71	Ist-00071	1	4	5	1	3	4	7	10
72	Ist-00072	1	3	5	1	4	5	7	10
73	Ist-00073	1	2	3	4	5	6	7	8
74	Ist-00074	1	3	4	2	3	7	8	9
75	Ist-00075	2	3	5	1	3	4	8	10
76	Ist-00076	2	3	5	1	2	4	6	7
77	Ist-00077	3	4	5	3	4	5	8	9
78	Ist-00078	1	2	3	3	5	6	8	10
79	Ist-00079	1	2	3	1	5	6	8	9
80	Ist-00080	2	4	5	1	4	7	8	10
81	Ist-00081	1	2	4	1	4	5	6	7
82	Ist-00082	1	2	3	1	3	4	8	9
83	Ist-00083	2	3	4	1	3	7	9	10
84	Ist-00084	1	2	5	1	4	5	7	8
85	Ist-00085	3	4	5	2	3	6	7	8
86	Ist-00086	1	4	5	2	3	4	7	8
87	Ist-00087	1	3	5	5	6	7	8	9
88	Ist-00088	1	2	5	4	5	6	9	10
89	Ist-00089	1	3	5	1	2	3	9	10
90	Ist-00090	1	3	5	1	2	3	6	8
91	Ist-00091	1	3	4	1	2	6	8	10
92	Ist-00092	2	4	5	1	2	7	8	10
93	Ist-00093	2	3	5	1	4	5	9	10
94	Ist-00094	2	3	5	2	3	4	5	9
95	Ist-00095	2	3	4	1	2	4	5	7
96	Ist-00096	2	4	5	1	3	4	6	10
97	Ist-00097	1	2	4	2	4	5	7	10
98	Ist-00098	1	2	3	1	2	3	7	10
99	Ist-00099	1	4	5	1	3	8	9	10
100	Ist-00100	2	3	5	6	7	8	9	10

После формализации предметной области, т.е. формирования баз данных, представленных в таблица 1-3, был запущен режим _25 системы «Эйдос» (рисунок 3), который сформировал базу абсолютных частот (таблица 4), базу знаний (таблица 5), а также базу данных результатов идентификации образов конкретных объектов с обобщенными образами классов (таблица 6):

Рисунок 3. Экранная форма выбора режима _25 системы «Эйдос»

Таблица 4 - БАЗА АБСОЛЮТНЫХ ЧАСТОТ

Коды признаков	Коды классов
	1	2	3	4	5
1	34	35	30	28	32
2	31	25	31	22	26
3	34	28	31	24	39
4	30	33	28	21	32
5	29	34	26	22	24
6	34	33	29	22	32
7	33	30	26	29	29
8	43	33	35	31	32
9	28	27	31	19	27
10	39	37	33	27	32

Таблица 5 - БАЗА ЗНАНИЙ (в сантибитах: БитЧ0,01)

Коды признаков	Коды классов
	1	2	3	4	5
1	-1,380	1,495	-1,850	2,390	-0,326
2	0,883	-3,993	4,386	-0,072	-1,723
3	-0,775	-4,985	-0,204	-1,900	6,560
4	-2,207	2,773	-0,894	-3,598	2,820
5	-1,235	5,770	-1,198	-0,072	-4,264
6	0,470	1,477	-1,076	-3,417	1,524
7	0,164	-0,908	-3,902	5,995	-0,960
8	3,214	-3,235	0,182	2,759	-3,188
9	-1,635	-0,836	5,100	-4,013	0,189
10	1,228	1,511	-0,572	-0,513	-2,074

Таблица 6 - БАЗА ДАННЫХ РЕЗУЛЬТАТОВ ИДЕНТИФИКАЦИИ ОБРАЗОВ КОНКРЕТНЫХ ОБЪЕКТОВ С ОБОБЩЕННЫМИ ОБРАЗАМИ КЛАССОВ В таблице базе данных придан вид, удобный для статьи

Результаты идентификации объектов с 1-м классом	Результаты идентификации объектов со 2-м классом	Результаты идентификации объектов с 3-м классом	Результаты идентификации объектов с 4-м классом	Результаты идентификации объектов с 5-м классом
Код объекта	Код класса	Сходство	Факт	Код объекта	Код класса	Сходство	Факт	Код объекта	Код класса	Сходство	Факт	Код объекта	Код класса	Сходство	Факт	Код объекта	Код класса	Сходство	Факт
65	1	61,8	v	50	2	76,6	v	61	3	56,8	v	34	4	72,0	v	25	5	62,1	v
28	1	58,4	v	44	2	63,5	v	43	3	55,6		47	4	72,0		57	5	60,6	v
91	1	58,4	v	93	2	63,5	v	63	3	55,6	v	32	4	69,4		4	5	58,5	v
43	1	55,4		88	2	63,4	v	11	3	52,8	v	92	4	69,4	v	3	5	57,5	v
63	1	55,4	v	13	2	63,1	v	57	3	50,7	v	40	4	61,3	v	96	5	55,4	v
32	1	54,8	v	27	2	63,1	v	55	3	49,8		10	4	52,7	v	49	5	51,8	v
92	1	54,8		72	2	63,1		94	3	49,8	v	19	4	51,2	v	68	5	51,6	v
6	1	53,1	v	81	2	62,9	v	16	3	48,1	v	84	4	51,2		18	5	43,6	v
85	1	53,1		54	2	49,8	v	89	3	47,6	v	80	4	48,6	v	46	5	42,6	v
5	1	51,7	v	51	2	45,5	v	24	3	46,7	v	2	4	46,2	v	12	5	41,7	v
58	1	47,7	v	62	2	42,6	v	12	3	44,1	v	65	4	44,1		82	5	40,7
100	1	47,1		64	2	42,5		39	3	41,5	v	98	4	42,0		71	5	40,5	v
78	1	40,9	v	8	2	42,5	v	74	3	38,6	v	70	4	41,5	v	41	5	36,9	v
1	1	36,9		69	2	39,8	v	59	3	25,1	v	58	4	37,8	v	69	5	31,8	v
20	1	35,2	v	84	2	36,1	v	42	3	23,0		36	4	35,6	v	59	5	30,2
29	1	35,2	v	73	2	36,0	v	49	3	21,6	v	5	4	35,2	v	75	5	27,1	v
90	1	35,2	v	38	2	31,9		77	3	20,8	v	95	4	34,6	v	7	5	26,5	v
21	1	34,4	v	97	2	31,9	v	21	3	20,1	v	13	4	32,0	v	70	5	26,0	v
56	1	34,4	v	95	2	31,8	v	56	3	20,1	v	27	4	32,0	v	55	5	25,8	v
64	1	33,9	v	67	2	29,3	v	17	3	19,0		72	4	32,0		94	5	25,8	v
52	1	32,7	v	79	2	29,2	v	23	3	19,0	v	37	4	31,7	v	60	5	25,4	v
67	1	30,9	v	5	2	28,9	v	53	3	18,5		62	4	29,5		86	5	25,4	v
74	1	28,7	v	48	2	26,3	v	99	3	18,5		31	4	29,1	v	15	5	24,7	v
37	1	27,4	v	30	2	25,5	v	67	3	16,9	v	6	4	27,0		83	5	24,7
70	1	26,9	v	10	2	24,7		4	3	16,4	v	85	4	27,0	v	14	5	22,8
34	1	26,4	v	36	2	24,5	v	82	3	16,2	v	60	4	26,0	v	20	5	21,4	v
47	1	26,4		26	2	19,3	v	1	3	14,6	v	86	4	26,0	v	29	5	21,4	v
2	1	25,7	v	7	2	19,2		26	3	14,3	v	46	4	23,8		90	5	21,4	v
24	1	25,3		35	2	18,9		33	3	14,1	v	66	4	23,5		89	5	20,1	v
61	1	24,5	v	37	2	15,7		20	3	10,0		74	4	23,5	v	21	5	18,7	v
54	1	24,3	v	96	2	15,5	v	29	3	10,0		71	4	21,2	v	56	5	18,7
30	1	22,7	v	87	2	15,5		90	3	10,0	v	52	4	20,9		6	5	17,6	v
60	1	22,1		17	2	12,2	v	88	3	9,5		15	4	18,7		85	5	17,6	v
86	1	22,1	v	23	2	12,2		79	3	8,1	v	83	4	18,7	v	77	5	17,0	v
17	1	19,7	v	80	2	11,9	v	28	3	7,5	v	38	4	17,4	v	48	5	16,8	v
23	1	19,7	v	14	2	8,7	v	91	3	7,5	v	97	4	17,4	v	26	5	16,0
80	1	19,1		16	2	7,9	v	7	3	5,4		73	4	17,0		11	5	13,4
45	1	18,7	v	76	2	7,4	v	45	3	5,3		76	4	14,8		98	5	13,2
87	1	18,7	v	78	2	5,7	v	51	3	4,6		81	4	14,8	v	76	5	12,4	v
31	1	17,0	v	9	2	5,6	v	52	3	4,3	v	87	4	14,6		53	5	11,3	v
42	1	16,6	v	4	2	2,3		44	3	4,1		28	4	14,0		99	5	11,3	v
19	1	15,1	v	71	2	2,0		93	3	4,1	v	64	4	14,0	v	22	5	11,2	v
53	1	14,9		68	2	1,9	v	3	3	2,6	v	91	4	14,0	v	74	5	9,6
99	1	14,9	v	25	2	1,8	v	41	3	2,0	v	100	4	12,0		35	5	9,1	v
73	1	12,0	v	39	2	0,7	v	14	3	1,8	v	22	4	10,3	v	16	5	8,8	v
11	1	10,9	v	77	2	-0,3		66	3	-0,1		35	4	7,7	v	52	5	7,5	v
9	1	10,8		34	2	-2,3		65	3	-0,7	v	48	4	6,7		9	5	6,2	v
98	1	8,7	v	47	2	-2,3	v	100	3	-1,8	v	9	4	5,8		17	5	-0,0
75	1	8,3		58	2	-2,4	v	37	3	-2,6	v	20	4	5,8	v	23	5	-0,0	v
40	1	7,2	v	55	2	-4,6	v	60	3	-2,9		29	4	5,8		45	5	-1,0	v
35	1	5,7	v	94	2	-4,6	v	86	3	-2,9		90	4	5,8		33	5	-1,9	v
59	1	5,3	v	45	2	-5,8	v	18	3	-3,2		25	4	4,1	v	1	5	-2,2
66	1	4,3	v	42	2	-7,4	v	6	3	-4,1		41	4	2,7		81	5	-2,9
10	1	3,4	v	33	2	-7,5	v	85	3	-4,1	v	11	4	2,3	v	30	5	-3,1
39	1	2,3	v	40	2	-7,9	v	87	3	-6,1	v	33	4	2,3		65	5	-4,0	v
22	1	1,7		2	2	-8,6	v	2	3	-7,1		75	4	2,1		78	5	-4,3
79	1	0,8	v	100	2	-8,7	v	15	3	-9,8		53	4	-0,3	v	66	5	-5,7	v
51	1	-2,6	v	31	2	-8,8		83	3	-9,8	v	99	4	-0,3	v	88	5	-6,5	v
49	1	-3,4		75	2	-11,2	v	31	3	-10,6	v	45	4	-4,2		40	5	-8,8
8	1	-4,3		18	2	-11,2		58	3	-11,0		8	4	-4,7		50	5	-9,6	v
36	1	-5,3	v	22	2	-12,3		8	3	-11,3	v	24	4	-6,7	v	39	5	-10,1
68	1	-5,6	v	28	2	-13,0		32	3	-12,0	v	79	4	-6,7		31	5	-12,3
38	1	-6,1	v	91	2	-13,0		92	3	-12,0		30	4	-6,8	v	42	5	-12,4
97	1	-6,1	v	3	2	-15,7		22	3	-13,7	v	1	4	-8,7	v	19	5	-16,0
41	1	-7,0	v	15	2	-18,5	v	19	3	-14,3	v	78	4	-11,3		24	5	-16,8
16	1	-7,2		83	2	-18,5	v	98	3	-14,7	v	14	4	-12,0		44	5	-17,6	v
84	1	-9,3	v	61	2	-18,8		38	3	-15,0	v	21	4	-12,4		93	5	-17,6	v
89	1	-12,0	v	19	2	-19,3		97	3	-15,0		56	4	-12,4	v	51	5	-18,0	v
33	1	-13,6		66	2	-21,2	v	34	3	-16,4		68	4	-13,0		80	5	-18,1	v
26	1	-15,1		59	2	-24,5	v	47	3	-16,4	v	42	4	-14,8	v	61	5	-19,6
76	1	-16,6		82	2	-24,6	v	62	3	-16,7	v	18	4	-16,6	v	73	5	-20,1
15	1	-20,3	v	49	2	-24,7		46	3	-16,9	v	89	4	-17,0		95	5	-22,4
83	1	-20,3		1	2	-25,6	v	78	3	-19,7	v	82	4	-18,5		100	5	-22,8	v
12	1	-20,8	v	43	2	-26,2	v	10	3	-21,6	v	54	4	-21,3		13	5	-24,5
69	1	-21,7		63	2	-26,2	v	76	3	-23,0	v	50	4	-23,5		27	5	-24,5
77	1	-23,1		24	2	-26,3	v	75	3	-23,0	v	43	4	-23,8	v	72	5	-24,5	v
96	1	-23,4		32	2	-26,5	v	95	3	-23,8	v	63	4	-23,8		54	5	-26,8
82	1	-24,8	v	92	2	-26,5	v	54	3	-24,5	v	67	4	-23,8		43	5	-27,3	v
48	1	-25,3	v	57	2	-29,0	v	36	3	-25,1		61	4	-24,9	v	63	5	-27,3
62	1	-25,7		46	2	-29,3	v	69	3	-27,2	v	39	4	-26,0		8	5	-29,2	v
4	1	-26,4	v	53	2	-31,7	v	9	3	-28,6	v	44	4	-27,0	v	36	5	-30,2
71	1	-27,0	v	99	2	-31,7		30	3	-29,0		93	4	-27,0		28	5	-30,4	v
3	1	-27,4	v	70	2	-32,3		64	3	-31,1		3	4	-31,7		91	5	-30,4
50	1	-28,7	v	89	2	-36,0		96	3	-31,7		77	4	-33,0	v	84	5	-31,2	v
18	1	-29,9	v	12	2	-36,2		50	3	-38,6		7	4	-34,1	v	79	5	-32,1
57	1	-30,4		98	2	-36,4	v	5	3	-45,3		12	4	-34,1		38	5	-32,9
46	1	-30,9		41	2	-38,2		68	3	-45,9		96	4	-34,3	v	97	5	-32,9
88	1	-31,7	v	21	2	-42,4		48	3	-46,7		59	4	-35,6		2	5	-33,9
13	1	-32,3		56	2	-42,4		70	3	-47,3		51	4	-38,0		87	5	-35,9	v
27	1	-32,3		52	2	-45,4		73	3	-47,6	v	17	4	-44,6	v	62	5	-40,3	v
72	1	-32,3	v	20	2	-49,9		35	3	-48,0		23	4	-44,6		67	5	-42,6
25	1	-35,7		29	2	-49,9	v	40	3	-48,1		69	4	-48,8		32	5	-45,4
95	1	-36,3		90	2	-49,9		80	3	-48,6		55	4	-49,7		92	5	-45,4	v
81	1	-41,0	v	60	2	-56,1	v	71	3	-51,3		94	4	-49,7		64	5	-45,7	v
7	1	-45,3	v	86	2	-56,1		84	3	-52,9		26	4	-51,2	v	58	5	-47,4
14	1	-47,1	v	11	2	-63,0		25	3	-54,7		49	4	-52,7	v	5	5	-49,5
55	1	-50,1	v	65	2	-63,3		13	3	-58,1	v	16	4	-61,3		10	5	-51,8
94	1	-50,1		6	2	-63,5	v	27	3	-58,1	v	88	4	-61,3		37	5	-57,5
44	1	-53,1		85	2	-63,5		72	3	-58,1	v	57	4	-69,4		34	5	-58,5	v
93	1	-53,1		74	2	-76,6		81	3	-61,6		4	4	-72,0		47	5	-58,5	v

В нашем примере режим _25 автоматически скопировал обучающую выборку в распознаваемую выбору, но при реальном решении задачи о назначениях она вручную вводится в режиме _41, а распознавание ее, т.е. количественное определение меры сходства всех объектов со всеми классами, что осуществляется в режиме _42 (рисунок 4):

Рисунок 4. Экранная форма выбора режима _42 системы «Эйдос»

Когда эти базы сформированы, запускается режим _47, обеспечивающий решение задачи о назначениях (рисунок 5):

Рисунок 5. Экранная форма выбора режима _47 системы «Эйдос»

Далее в режиме _471 (рисунок 6) вводятся вручную или автоматически ресурсы классов, а в режиме _472 (рисунок 7), также вручную или автоматически, затраты на объекты в результате чего формируются базы данных, представленные в таблицах 7 и 8:



Рисунок 6. Экранная форма режима _471 ввода-корректировки ресурсов классов

Рисунок 7. Экранная форма режима _472 ввода-корректировки затрат объектов

Таблица 7 - БАЗА ДАННЫХ РЕСУРСОВ КЛАССОВ

Код класса	Наименование класса	Ресурс
1	Klass_1	89,000
2	Klass_2	32,000
3	Klass_3	46,000
4	Klass_4	42,000
5	Klass_5	37,000
	Сумма по классам:	246,000
	Среднее на класс:	49,200

Таблица 8 - БАЗА ДАННЫХ ЗАТРАТ НА ОБЪЕКТЫ

KOD	NAME	ZATRATI	KOD	NAME	ZATRATI
1	Ist-00001	7	51	Ist-00051	9
2	Ist-00002	3	52	Ist-00052	10
3	Ist-00003	5	53	Ist-00053	6
4	Ist-00004	6	54	Ist-00054	8
5	Ist-00005	4	55	Ist-00055	10
6	Ist-00006	2	56	Ist-00056	9
7	Ist-00007	5	57	Ist-00057	4
8	Ist-00008	5	58	Ist-00058	2
9	Ist-00009	7	59	Ist-00059	4
10	Ist-00010	7	60	Ist-00060	10
11	Ist-00011	6	61	Ist-00061	3
12	Ist-00012	4	62	Ist-00062	6
13	Ist-00013	3	63	Ist-00063	4
14	Ist-00014	3	64	Ist-00064	4
15	Ist-00015	6	65	Ist-00065	8
16	Ist-00016	7	66	Ist-00066	4
17	Ist-00017	9	67	Ist-00067	7
18	Ist-00018	5	68	Ist-00068	7
19	Ist-00019	3	69	Ist-00069	10
20	Ist-00020	6	70	Ist-00070	3
21	Ist-00021	1	71	Ist-00071	4
22	Ist-00022	3	72	Ist-00072	5
23	Ist-00023	8	73	Ist-00073	5
24	Ist-00024	3	74	Ist-00074	5
25	Ist-00025	6	75	Ist-00075	8
26	Ist-00026	7	76	Ist-00076	10
27	Ist-00027	6	77	Ist-00077	8
28	Ist-00028	5	78	Ist-00078	9
29	Ist-00029	5	79	Ist-00079	6
30	Ist-00030	5	80	Ist-00080	3
31	Ist-00031	6	81	Ist-00081	3
32	Ist-00032	5	82	Ist-00082	10
33	Ist-00033	8	83	Ist-00083	5
34	Ist-00034	4	84	Ist-00084	3
35	Ist-00035	8	85	Ist-00085	5
36	Ist-00036	5	86	Ist-00086	5
37	Ist-00037	7	87	Ist-00087	5
38	Ist-00038	7	88	Ist-00088	8
39	Ist-00039	7	89	Ist-00089	7
40	Ist-00040	8	90	Ist-00090	1
41	Ist-00041	7	91	Ist-00091	9
42	Ist-00042	2	92	Ist-00092	3
43	Ist-00043	2	93	Ist-00093	5
44	Ist-00044	5	94	Ist-00094	3
45	Ist-00045	7	95	Ist-00095	1
46	Ist-00046	8	96	Ist-00096	7
47	Ist-00047	4	97	Ist-00097	1
48	Ist-00048	9	98	Ist-00098	9
49	Ist-00049	1	99	Ist-00099	4
50	Ist-00050	4	100	Ist-00100	10

Варианты автоматического формирования и ввода в базы данных ресурсов и затрат в этих режимах видны из рисунков 6 и 7.

После ввода ресурсов классов и затрат на объекты запускается режим _473 (рисунок 8), который собственно и осуществляет назначения объектов на классы согласно алгоритма задачи 4, т.е. максимизируя пользу по классам и в целом по системе и при этом минимизируя остатки ресурсов классов, затраты по классам и общие затраты.

В результате работы данного режима формируются выходные формы, представленная в таблицах 9 и 10:

Таблица 9 - БАЗА ДАННЫХ РЕСУРСОВ КЛАССОВ

Код класса	Наименование класса	Ресурс	Остаток ресурса	Количество объектов	Суммарная польза	Сумма затрат	Средне- взвешенная удельная польза	Средняя польза	Средние затраты
1	Klass_1	89,000	0,000	17,000	712,5022397	89,000	8,0056431	41,9118965	5,235
2	Klass_2	32,000	2,000	8,000	467,2168469	30,000	15,5738949	58,4021059	3,750
3	Klass_3	46,000	0,000	11,000	518,6988525	46,000	11,2760620	47,1544411	4,182
4	Klass_4	42,000	2,000	11,000	617,5542042	40,000	15,4388551	56,1412913	3,636
5	Klass_5	37,000	0,000	9,000	408,5936439	37,000	11,0430715	45,3992938	4,111
	Сумма по классам:	246,000	4,000	56,000	2724,5657872	242,000	61,3375266	249,0090286	20,914
	Среднее на класс:	49,200	0,800	11,200	544,9131574	48,400	12,2675053	49,8018057	4,183

Рисунок 8. Экранная форма режима _473 назначения объектов на классы

Таблица 10 - РЕЗУЛЬТАТЫ НАЗНАЧЕНИЙ ОБЪЕКТОВ РАСПОЗНАВАЕМОЙ ВЫБОРКИ НА КЛАССЫ

\\

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

Теперь остается рассмотреть вопрос об эффективности этого назначения, как по времени, затраченному на расчет, так и по его результатам. Ведь не нужно забывать о том, что для него использован эвристический, а не оптимизизационный алгоритм, т.е. ожидается хороший, рациональный вариант назначения, но его оптимальность строго не доказана и неизвестно, реализуется ли она.

Что касается времени расчета при той размерности задачи, которая используется в качестве примера в статье, т.е. 5 классов и 100 объектов, то оно занимает не более нескольких десятых долей секунды (субъективно оценивается как «мгновенно»). Более точную оценку времени исполнения мы дадим чуть позже. Необходимо отметить, что количество вариантов распределения 100 объектов по 5 классам составляет огромное число 5¹⁰⁰, которое настолько велико, что даже не может быть вычислено стандартными средствами (например в Excel или на калькуляторе).

Конечно, наиболее убедительную оценку качества результатов распределения согласно предложенного алгоритма могло быть дать их сравнение с результатами распределения с использованием оптимизационного метода. Однако, сделать это не представляется возможным из-за ранее сформулированных проблем: труднодоступности соответствующего программного обеспечения и очень больших затрат времени на расчет. Поэтому предлагается сравнить результаты распределения с случайными распределениями (которые используются в качестве «контрольной группы» или «базы сравнения»), когда объекты назначаются на классы случайным образом. С целью осуществления такого сравнения в системе «Эйдос» реализован специальный режим _474 (рисунок 9):

Рисунок 9. Экранная форма режима _474 системы «Эйдос»

С использованием данного режима сгенерировано 100 случайных распределений 100 объектов по 5 классам. При этом затраты на объекты и ресурсы классов взяты из баз данных рассматриваемого в статье примера.

Генерация этих 100 случайных примеров назначения проводилось в режиме _474 практически по тому же алгоритму, что и реальное назначение в режиме _473 с тем лишь отличием, что вместо пользы объектов для классов, определенной системой «Эйдос» на основе базы прецедентов по признакам объектов, использовалась равномерно распределенная случайная величина. Обобщенные результаты случайных распределений и их сравнение с результатами работы LC-алгоритма приведены в таблицах 11 и 12:

Таблица 11 - СУММАРНЫЕ РЕЗУЛЬТАТЫ СЛУЧАЙНЫХ РАСПРЕДЕЛЕНИЙ И ИХ СРАВНЕНИЕ С РЕЗУЛЬТАТАМИ РАБОТЫ LC-АЛГОРИТМА

Наименование	Ресурс	Остаток ресурса	Количество объектов	Суммарная польза	Сумма затрат	Средне- взвешенная удельная польза	Средняя польза	Средние затраты
Сумма по классам RND-распределения 1:	246,00	1,00	48,00	1337,55	245,00	28,47	141,30	25,06
Сумма по классам RND-распределения 2:	246,00	5,00	47,00	1333,13	241,00	26,93	140,92	26,55
Сумма по классам RND-распределения 3:	246,00	1,00	47,00	1335,69	245,00	27,48	147,26	27,02
Сумма по классам RND-распределения 4:	246,00	2,00	48,00	1319,55	244,00	27,67	135,57	26,52
Сумма по классам RND-распределения 5:	246,00	0,00	48,00	1082,86	246,00	23,28	113,05	24,86
Сумма по классам RND-распределения 6:	246,00	1,00	46,00	1184,75	245,00	24,19	129,85	26,83
Сумма по классам RND-распределения 7:	246,00	0,00	49,00	1392,75	246,00	28,86	144,68	25,53
Сумма по классам RND-распределения 8:	246,00	1,00	45,00	1433,77	245,00	30,07	164,93	27,60
Сумма по классам RND-распределения 9:	246,00	2,00	45,00	1144,47	244,00	24,32	124,96	26,59
Сумма по классам RND-распределения 10:	246,00	1,00	46,00	1235,11	245,00	23,74	126,54	27,15
Сумма по классам RND-распределения 11:	246,00	3,00	47,00	1235,82	243,00	25,05	131,00	26,68
Сумма по классам RND-распределения 12:	246,00	2,00	46,00	1150,55	244,00	25,19	126,40	26,04
Сумма по классам RND-распределения 13:	246,00	0,00	46,00	1443,05	246,00	31,34	162,17	26,15
Сумма по классам RND-распределения 14:	246,00	2,00	47,00	1377,03	244,00	30,07	153,09	25,84
Сумма по классам RND-распределения 15:	246,00	4,00	45,00	1071,00	242,00	21,57	113,22	27,27
Сумма по классам RND-распределения 16:	246,00	2,00	48,00	1352,60	244,00	28,64	141,21	25,08
Сумма по классам RND-распределения 17:	246,00	0,00	46,00	1192,05	246,00	24,38	132,99	27,34
Сумма по классам RND-распределения 18:	246,00	4,00	47,00	1305,87	242,00	25,90	131,19	27,66
Сумма по классам RND-распределения 19:	246,00	4,00	48,00	1276,37	242,00	26,19	130,96	25,08
Сумма по классам RND-распределения 20:	246,00	0,00	47,00	1364,36	246,00	28,74	148,78	26,62
Сумма по классам RND-распределения 21:	246,00	1,00	49,00	1467,36	245,00	32,90	153,76	24,74
Сумма по классам RND-распределения 22:	246,00	3,00	46,00	1263,43	243,00	25,27	135,44	27,24
Сумма по классам RND-распределения 23:	246,00	2,00	47,00	1483,08	244,00	28,89	152,49	27,24
Сумма по классам RND-распределения 24:	246,00	4,00	47,00	1350,79	242,00	29,40	146,97	25,90
Сумма по классам RND-распределения 25:	246,00	5,00	42,00	912,46	241,00	18,68	108,12	29,21
Сумма по классам RND-распределения 26:	246,00	2,00	47,00	1453,99	244,00	31,79	170,61	27,18
Сумма по классам RND-распределения 27:	246,00	6,00	50,00	1474,66	240,00	32,06	148,25	23,43
Сумма по классам RND-распределения 28:	246,00	3,00	47,00	1354,09	243,00	29,53	156,32	26,93
Сумма по классам RND-распределения 29:	246,00	2,00	45,00	1194,80	244,00	26,17	131,29	27,18
Сумма по классам RND-распределения 30:	246,00	3,00	49,00	1320,09	243,00	27,27	132,84	24,75
Сумма по классам RND-распределения 31:	246,00	0,00	46,00	1375,79	246,00	26,50	142,02	27,87
Сумма по классам RND-распределения 32:	246,00	1,00	47,00	1245,26	245,00	26,04	133,22	26,50
Сумма по классам RND-распределения 33:	246,00	1,00	49,00	1241,44	245,00	25,27	124,00	24,71
Сумма по классам RND-распределения 34:	246,00	1,00	46,00	1433,66	245,00	29,70	156,91	26,99
Сумма по классам RND-распределения 35:	246,00	1,00	48,00	1308,69	245,00	28,40	140,32	25,49
Сумма по классам RND-распределения 36:	246,00	3,00	47,00	1186,47	243,00	22,82	122,27	27,22
Сумма по классам RND-распределения 37:	246,00	3,00	50,00	1405,86	243,00	28,23	133,53	24,77
Сумма по классам RND-распределения 38:	246,00	2,00	45,00	1131,40	244,00	24,44	131,54	26,98
Сумма по классам RND-распределения 39:	246,00	1,00	48,00	1286,78	245,00	25,38	130,82	26,19
Сумма по классам RND-распределения 40:	246,00	0,00	51,00	1419,23	246,00	29,27	139,29	23,92
Сумма по классам RND-распределения 41:	246,00	1,00	45,00	1181,37	245,00	24,75	135,71	27,88
Сумма по классам RND-распределения 42:	246,00	0,00	49,00	1259,25	246,00	25,89	123,92	25,23
Сумма по классам RND-распределения 43:	246,00	3,00	48,00	1200,58	243,00	23,36	117,87	26,13
Сумма по классам RND-распределения 44:	246,00	1,00	46,00	1296,91	245,00	27,31	143,35	26,52
Сумма по классам RND-распределения 45:	246,00	2,00	48,00	1204,11	244,00	25,06	129,57	26,10
Сумма по классам RND-распределения 46:	246,00	1,00	47,00	1270,15	245,00	26,50	135,34	25,89
Сумма по классам RND-распределения 47:	246,00	3,00	41,00	977,97	243,00	19,75	110,34	30,81
Сумма по классам RND-распределения 48:	246,00	0,00	47,00	1361,09	246,00	26,91	139,57	26,80
Сумма по классам RND-распределения 49:	246,00	1,00	48,00	1369,46	245,00	28,07	143,21	25,94
Сумма по классам RND-распределения 50:	246,00	2,00	50,00	1474,56	244,00	30,75	149,38	24,44
Сумма по классам RND-распределения 51:	246,00	1,00	51,00	1440,30	245,00	32,61	153,54	23,81
Сумма по классам RND-распределения 52:	246,00	2,00	46,00	1207,79	244,00	24,99	132,45	27,07
Сумма по классам RND-распределения 53:	246,00	2,00	46,00	1339,79	244,00	28,04	145,81	27,00
Сумма по классам RND-распределения 54:	246,00	0,00	46,00	1230,21	246,00	23,26	125,24	27,10
Сумма по классам RND-распределения 55:	246,00	0,00	52,00	1568,95	246,00	33,32	153,27	23,67
Сумма по классам RND-распределения 56:	246,00	1,00	47,00	1367,95	245,00	26,09	135,18	27,04
Сумма по классам RND-распределения 57:	246,00	3,00	47,00	1233,70	243,00	25,71	130,14	26,00
Сумма по классам RND-распределения 58:	246,00	0,00	42,00	1293,03	246,00	26,50	152,81	29,75
Сумма по классам RND-распределения 59:	246,00	2,00	49,00	1286,35	244,00	26,89	131,97	24,65
Сумма по классам RND-распределения 60:	246,00	0,00	50,00	1374,77	246,00	28,67	143,03	24,83
Сумма по классам RND-распределения 61:	246,00	2,00	47,00	1421,14	244,00	31,38	153,01	25,30
Сумма по классам RND-распределения 62:	246,00	2,00	50,00	1427,58	244,00	29,72	144,71	25,81
Сумма по классам RND-распределения 63:	246,00	4,00	47,00	1034,05	242,00	21,56	109,90	26,63
Сумма по классам RND-распределения 64:	246,00	0,00	47,00	1442,41	246,00	30,42	153,76	25,40
Сумма по классам RND-распределения 65:	246,00	1,00	49,00	1562,19	245,00	30,90	155,11	25,42
Сумма по классам RND-распределения 66:	246,00	3,00	43,00	1101,76	243,00	20,12	117,85	29,59
Сумма по классам RND-распределения 67:	246,00	3,00	49,00	1419,75	243,00	30,31	150,90	24,96
Сумма по классам RND-распределения 68:	246,00	2,00	46,00	1461,10	244,00	30,12	158,81	26,37
Сумма по классам RND-распределения 69:	246,00	0,00	45,00	1283,34	246,00	25,78	137,29	27,21
Сумма по классам RND-распределения 70:	246,00	2,00	50,00	1390,90	244,00	28,43	135,46	25,18
Сумма по классам RND-распределения 71:	246,00	3,00	47,00	1318,17	243,00	25,93	130,03	27,62
Сумма по классам RND-распределения 72:	246,00	0,00	43,00	1199,83	246,00	22,94	131,41	29,54
Сумма по классам RND-распределения 73:	246,00	1,00	49,00	1499,65	245,00	31,64	158,98	25,19
Сумма по классам RND-распределения 74:	246,00	1,00	48,00	1268,48	245,00	25,77	129,26	26,32
Сумма по классам RND-распределения 75:	246,00	0,00	47,00	1338,61	246,00	27,70	141,88	26,98
Сумма по классам RND-распределения 76:	246,00	0,00	46,00	1134,79	246,00	20,81	114,72	27,87
Сумма по классам RND-распределения 77:	246,00	2,00	48,00	1310,69	244,00	26,47	134,37	25,74
Сумма по классам RND-распределения 78:	246,00	3,00	45,00	1122,43	243,00	24,73	127,79	26,44
Сумма по классам RND-распределения 79:	246,00	2,00	46,00	1206,27	244,00	23,69	127,57	27,27
Сумма по классам RND-распределения 80:	246,00	0,00	49,00	1469,15	246,00	30,29	155,41	26,19
Сумма по классам RND-распределения 81:	246,00	0,00	46,00	1253,88	246,00	26,63	139,59	26,76
Сумма по классам RND-распределения 82:	246,00	1,00	45,00	971,91	245,00	18,91	102,90	27,55
Сумма по классам RND-распределения 83:	246,00	0,00	44,00	1302,34	246,00	26,76	148,66	28,24
Сумма по классам RND-распределения 84:	246,00	1,00	46,00	1304,72	245,00	26,53	147,42	27,49
Сумма по классам RND-распределения 85:	246,00	5,00	48,00	1364,88	241,00	26,97	136,91	25,97
Сумма по классам RND-распределения 86:	246,00	3,00	48,00	1255,29	243,00	26,90	132,98	25,57
Сумма по классам RND-распределения 87:	246,00	1,00	51,00	1323,92	245,00	26,35	129,54	24,75
Сумма по классам RND-распределения 88:	246,00	3,00	49,00	1405,94	243,00	30,77	141,11	25,13
Сумма по классам RND-распределения 89:	246,00	1,00	45,00	1361,47	245,00	29,55	152,78	26,78
Сумма по классам RND-распределения 90:	246,00	1,00	44,00	1036,20	245,00	22,66	121,81	27,89
Сумма по классам RND-распределения 91:	246,00	1,00	48,00	1401,40	245,00	29,46	147,33	25,25
Сумма по классам RND-распределения 92:	246,00	0,00	45,00	1385,08	246,00	27,94	150,72	26,91
Сумма по классам RND-распределения 93:	246,00	3,00	49,00	1183,22	243,00	26,38	128,46	25,08
Сумма по классам RND-распределения 94:	246,00	2,00	48,00	1417,80	244,00	27,81	144,07	26,38
Сумма по классам RND-распределения 95:	246,00	2,00	46,00	1227,37	244,00	24,68	133,60	27,87
Сумма по классам RND-распределения 96:	246,00	3,00	48,00	1343,12	243,00	27,93	143,96	25,82
Сумма по классам RND-распределения 97:	246,00	0,00	50,00	1543,65	246,00	32,33	155,89	24,40
Сумма по классам RND-распределения 98:	246,00	3,00	49,00	1633,35	243,00	33,88	169,17	25,45
Сумма по классам RND-распределения 99:	246,00	0,00	46,00	1187,66	246,00	24,67	131,48	26,60
Сумма по классам RND-распределения 100:	246,00	0,00	48,00	1097,35	246,00	22,49	110,71	25,78
Сумма по всем RND-распределениям:	24600,00	165,00	4711,00	130228,78	24435,00	2692,84	13799,08	2635,23
Среднее сумм по всем RND-распределениям:	246,00	1,65	47,11	1302,29	244,35	26,93	137,99	26,35
Ср.кв.откл. сумм по всем RND-распределениям:	0,00	1,40	2,02	135,97	1,40	3,21	13,96	1,33
Сумма из LC-распределения:	246,00	4,00	56,00	2724,57	242,00	61,34	249,01	20,91
Эффективность LC-алгоритма по сравнению с RND в %:	100,00	242,42	118,87	209,21	99,04	227,78	180,45	79,36

Таблица 12 - СРЕДНИЕ РЕЗУЛЬТАТЫ СЛУЧАЙНЫХ РАСПРЕДЕЛЕНИЙ И ИХ СРАВНЕНИЕ С РЕЗУЛЬТАТАМИ РАБОТЫ LC-АЛГОРИТМА

Наименование	Ресурс	Остаток ресурса	Количество объектов	Суммарная польза	Сумма затрат	Средне- взвешенная удельная польза	Средняя польза	Средние затраты
Среднее на класс RND-распределения 1:	49,20	0,20	9,60	267,51	49,00	5,69	28,26	5,01
Среднее на класс RND-распределения 2:	49,20	1,00	9,40	266,63	48,20	5,39	28,18	5,31
Среднее на класс RND-распределения 3:	49,20	0,20	9,40	267,14	49,00	5,50	29,45	5,40
Среднее на класс RND-распределения 4:	49,20	0,40	9,60	263,91	48,80	5,53	27,11	5,31
Среднее на класс RND-распределения 5:	49,20	0,00	9,60	216,57	49,20	4,66	22,61	4,97
Среднее на класс RND-распределения 6:	49,20	0,20	9,20	236,95	49,00	4,84	25,97	5,37
Среднее на класс RND-распределения 7:	49,20	0,00	9,80	278,55	49,20	5,77	28,94	5,11
Среднее на класс RND-распределения 8:	49,20	0,20	9,00	286,75	49,00	6,01	32,99	5,52
Среднее на класс RND-распределения 9:	49,20	0,40	9,00	228,89	48,80	4,86	24,99	5,32
Среднее на класс RND-распределения 10:	49,20	0,20	9,20	247,02	49,00	4,75	25,31	5,43
Среднее на класс RND-распределения 11:	49,20	0,60	9,40	247,16	48,60	5,01	26,20	5,34
Среднее на класс RND-распределения 12:	49,20	0,40	9,20	230,11	48,80	5,04	25,28	5,21
Среднее на класс RND-распределения 13:	49,20	0,00	9,20	288,61	49,20	6,27	32,43	5,23
Среднее на класс RND-распределения 14:	49,20	0,40	9,40	275,41	48,80	6,01	30,62	5,17
Среднее на класс RND-распределения 15:	49,20	0,80	9,00	214,20	48,40	4,31	22,64	5,46
Среднее на класс RND-распределения 16:	49,20	0,40	9,60	270,52	48,80	5,73	28,24	5,02
Среднее на класс RND-распределения 17:	49,20	0,00	9,20	238,41	49,20	4,88	26,60	5,47
Среднее на класс RND-распределения 18:	49,20	0,80	9,40	261,17	48,40	5,18	26,24	5,53
Среднее на класс RND-распределения 19:	49,20	0,80	9,60	255,27	48,40	5,24	26,19	5,02
Среднее на класс RND-распределения 20:	49,20	0,00	9,40	272,87	49,20	5,75	29,76	5,32
Среднее на класс RND-распределения 21:	49,20	0,20	9,80	293,47	49,00	6,58	30,75	4,95
Среднее на класс RND-распределения 22:	49,20	0,60	9,20	252,69	48,60	5,05	27,09	5,45
Среднее на класс RND-распределения 23:	49,20	0,40	9,40	296,62	48,80	5,78	30,50	5,45
Среднее на класс RND-распределения 24:	49,20	0,80	9,40	270,16	48,40	5,88	29,39	5,18
Среднее на класс RND-распределения 25:	49,20	1,00	8,40	182,49	48,20	3,74	21,62	5,84
Среднее на класс RND-распределения 26:	49,20	0,40	9,40	290,80	48,80	6,36	34,12	5,44
Среднее на класс RND-распределения 27:	49,20	1,20	10,00	294,93	48,00	6,41	29,65	4,69
Среднее на класс RND-распределения 28:	49,20	0,60	9,40	270,82	48,60	5,91	31,26	5,39
Среднее на класс RND-распределения 29:	49,20	0,40	9,00	238,96	48,80	5,23	26,26	5,44
Среднее на класс RND-распределения 30:	49,20	0,60	9,80	264,02	48,60	5,45	26,57	4,95
Среднее на класс RND-распределения 31:	49,20	0,00	9,20	275,16	49,20	5,30	28,40	5,58
Среднее на класс RND-распределения 32:	49,20	0,20	9,40	249,05	49,00	5,21	26,64	5,30
Среднее на класс RND-распределения 33:	49,20	0,20	9,80	248,29	49,00	5,05	24,80	4,94
Среднее на класс RND-распределения 34:	49,20	0,20	9,20	286,73	49,00	5,94	31,38	5,40
Среднее на класс RND-распределения 35:	49,20	0,20	9,60	261,74	49,00	5,68	28,06	5,10
Среднее на класс RND-распределения 36:	49,20	0,60	9,40	237,29	48,60	4,56	24,45	5,45
Среднее на класс RND-распределения 37:	49,20	0,60	10,00	281,17	48,60	5,65	26,71	4,95
Среднее на класс RND-распределения 38:	49,20	0,40	9,00	226,28	48,80	4,89	26,31	5,40
Среднее на класс RND-распределения 39:	49,20	0,20	9,60	257,36	49,00	5,08	26,16	5,24
Среднее на класс RND-распределения 40:	49,20	0,00	10,20	283,85	49,20	5,85	27,86	4,78
Среднее на класс RND-распределения 41:	49,20	0,20	9,00	236,27	49,00	4,95	27,14	5,58
Среднее на класс RND-распределения 42:	49,20	0,00	9,80	251,85	49,20	5,18	24,78	5,05
Среднее на класс RND-распределения 43:	49,20	0,60	9,60	240,12	48,60	4,67	23,57	5,23
Среднее на класс RND-распределения 44:	49,20	0,20	9,20	259,38	49,00	5,46	28,67	5,30
Среднее на класс RND-распределения 45:	49,20	0,40	9,60	240,82	48,80	5,01	25,91	5,22
Среднее на класс RND-распределения 46:	49,20	0,20	9,40	254,03	49,00	5,30	27,07	5,18
Среднее на класс RND-распределения 47:	49,20	0,60	8,20	195,59	48,60	3,95	22,07	6,16
Среднее на класс RND-распределения 48:	49,20	0,00	9,40	272,22	49,20	5,38	27,91	5,36
Среднее на класс RND-распределения 49:	49,20	0,20	9,60	273,89	49,00	5,61	28,64	5,19
Среднее на класс RND-распределения 50:	49,20	0,40	10,00	294,91	48,80	6,15	29,88	4,89
Среднее на класс RND-распределения 51:	49,20	0,20	10,20	288,06	49,00	6,52	30,71	4,76
Среднее на класс RND-распределения 52:	49,20	0,40	9,20	241,56	48,80	5,00	26,49	5,41
Среднее на класс RND-распределения 53:	49,20	0,40	9,20	267,96	48,80	5,61	29,16	5,40
Среднее на класс RND-распределения 54:	49,20	0,00	9,20	246,04	49,20	4,65	25,05	5,42
Среднее на класс RND-распределения 55:	49,20	0,00	10,40	313,79	49,20	6,66	30,65	4,73
Среднее на класс RND-распределения 56:	49,20	0,20	9,40	273,59	49,00	5,22	27,04	5,41
Среднее на класс RND-распределения 57:	49,20	0,60	9,40	246,74	48,60	5,14	26,03	5,20
Среднее на класс RND-распределения 58:	49,20	0,00	8,40	258,61	49,20	5,30	30,56	5,95
Среднее на класс RND-распределения 59:	49,20	0,40	9,80	257,27	48,80	5,38	26,39	4,93
Среднее на класс RND-распределения 60:	49,20	0,00	10,00	274,95	49,20	5,73	28,61	4,97
Среднее на класс RND-распределения 61:	49,20	0,40	9,40	284,23	48,80	6,28	30,60	5,06
Среднее на класс RND-распределения 62:	49,20	0,40	10,00	285,52	48,80	5,94	28,94	5,16
Среднее на класс RND-распределения 63:	49,20	0,80	9,40	206,81	48,40	4,31	21,98	5,33
Среднее на класс RND-распределения 64:	49,20	0,00	9,40	288,48	49,20	6,08	30,75	5,08
Среднее на класс RND-распределения 65:	49,20	0,20	9,80	312,44	49,00	6,18	31,02	5,08
Среднее на класс RND-распределения 66:	49,20	0,60	8,60	220,35	48,60	4,02	23,57	5,92
Среднее на класс RND-распределения 67:	49,20	0,60	9,80	283,95	48,60	6,06	30,18	4,99
Среднее на класс RND-распределения 68:	49,20	0,40	9,20	292,22	48,80	6,02	31,76	5,27
Среднее на класс RND-распределения 69:	49,20	0,00	9,00	256,67	49,20	5,16	27,46	5,44
Среднее на класс RND-распределения 70:	49,20	0,40	10,00	278,18	48,80	5,69	27,09	5,04
Среднее на класс RND-распределения 71:	49,20	0,60	9,40	263,63	48,60	5,19	26,01	5,52
Среднее на класс RND-распределения 72:	49,20	0,00	8,60	239,97	49,20	4,59	26,28	5,91
Среднее на класс RND-распределения 73:	49,20	0,20	9,80	299,93	49,00	6,33	31,80	5,04
Среднее на класс RND-распределения 74:	49,20	0,20	9,60	253,70	49,00	5,15	25,85	5,26
Среднее на класс RND-распределения 75:	49,20	0,00	9,40	267,72	49,20	5,54	28,38	5,40
Среднее на класс RND-распределения 76:	49,20	0,00	9,20	226,96	49,20	4,16	22,94	5,57
Среднее на класс RND-распределения 77:	49,20	0,40	9,60	262,14	48,80	5,29	26,87	5,15
Среднее на класс RND-распределения 78:	49,20	0,60	9,00	224,49	48,60	4,95	25,56	5,29
Среднее на класс RND-распределения 79:	49,20	0,40	9,20	241,25	48,80	4,74	25,51	5,45
Среднее на класс RND-распределения 80:	49,20	0,00	9,80	293,83	49,20	6,06	31,08	5,24
Среднее на класс RND-распределения 81:	49,20	0,00	9,20	250,78	49,20	5,33	27,92	5,35
Среднее на класс RND-распределения 82:	49,20	0,20	9,00	194,38	49,00	3,78	20,58	5,51
Среднее на класс RND-распределения 83:	49,20	0,00	8,80	260,47	49,20	5,35	29,73	5,65
Среднее на класс RND-распределения 84:	49,20	0,20	9,20	260,94	49,00	5,31	29,48	5,50
Среднее на класс RND-распределения 85:	49,20	1,00	9,60	272,98	48,20	5,39	27,38	5,19
Среднее на класс RND-распределения 86:	49,20	0,60	9,60	251,06	48,60	5,38	26,60	5,11
Среднее на класс RND-распределения 87:	49,20	0,20	10,20	264,78	49,00	5,27	25,91	4,95
Среднее на класс RND-распределения 88:	49,20	0,60	9,80	281,19	48,60	6,15	28,22	5,03
Среднее на класс RND-распределения 89:	49,20	0,20	9,00	272,29	49,00	5,91	30,56	5,36
Среднее на класс RND-распределения 90:	49,20	0,20	8,80	207,24	49,00	4,53	24,36	5,58
Среднее на класс RND-распределения 91:	49,20	0,20	9,60	280,28	49,00	5,89	29,47	5,05
Среднее на класс RND-распределения 92:	49,20	0,00	9,00	277,02	49,20	5,59	30,14	5,38
Среднее на класс RND-распределения 93:	49,20	0,60	9,80	236,64	48,60	5,28	25,69	5,02
Среднее на класс RND-распределения 94:	49,20	0,40	9,60	283,56	48,80	5,56	28,81	5,28
Среднее на класс RND-распределения 95:	49,20	0,40	9,20	245,47	48,80	4,94	26,72	5,57
Среднее на класс RND-распределения 96:	49,20	0,60	9,60	268,62	48,60	5,59	28,79	5,16
Среднее на класс RND-распределения 97:	49,20	0,00	10,00	308,73	49,20	6,47	31,18	4,88
Среднее на класс RND-распределения 98:	49,20	0,60	9,80	326,67	48,60	6,78	33,83	5,09
Среднее на класс RND-распределения 99:	49,20	0,00	9,20	237,53	49,20	4,93	26,30	5,32
Среднее на класс RND-распределения 100:	49,20	0,00	9,60	219,47	49,20	4,50	22,14	5,16
Сумма средних по всем RND-распределениям:	4920,00	33,00	942,20	26045,76	4887,00	538,57	2759,82	527,05
Среднее средних по всем RND-распределениям:	49,20	0,33	9,42	260,46	48,87	5,39	27,60	5,27
Ср.кв.откл. средних по всем RND-распределениям:	0,00	0,28	0,40	27,19	0,28	0,64	2,79	0,27
Среднее из LC-распределения:	49,20	0,80	11,20	544,91	48,40	12,27	49,80	4,18
Эффективность LC-алгоритма по сравнению с RND в %:	100,00	242,42	118,87	209,21	99,04	227,78	180,45	79,37

Из таблиц 11 и 12 видно, что использование LC-алгоритма более чем в 2 раза повышает среднюю пользу по системе по сравнению со случайным назначением. В реальных примерах это превышение может быть значительно большим, т.к. в примере, рассматриваемом в данной статье, объекты обладают случайными признаками и случайным образом отнесены к классам.

Кратко рассмотрим возможные применения задачи о назначениях в области педагогики и психологии. СК-анализ и система «Эйдос» позволяют разработать профессиограммы, т.е. на основе ретроспективной базы данных определить, какие признаки респондентов (первичные, устанавливаемые непосредственно, вторичные, т.е. расчетные) наиболее характерны для работников, успешно работающих по тем или иным должностям [1, 4, 6, 8-10]. Аналогично, могут быть разработаны профессиограммы, отражающие успешность обучения по тем или иным специальностям, дисциплинам и циклам дисциплин [1-3, 6, 7]. Во всех этих случаях можно и решить задачу о назначениях, т.е. распределить кандидатов, претендующих на ту или иную оплату труда (затраты), на должности, в соответствии с ограничениями на фонд оплаты труда по эти должностям, причем сделать это таким образом, что и для каждого работника, и по каждой должности, и по организации в целом, будет получена максимальная польза.

Выводы. На основе вышеизложенного на наш взгляд можно обоснованно предположить, что системно-когнитивный анализ и его инструментарий - система «Эйдос» являются адекватным средством для решения для решения ранее не встречавшегося в литературе обобщения задачи о назначениях, учитывающего не только различную полезность одного и того же груза для разных рюкзаков, различные затраты на грузы и ресурсы рюкзаков, но и обеспечивающего автоматическое определение степени этой полезности на основе признаков груза путем решения задачи распознавания.