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

Полезная модель относится к автоматизированным системам и предназначена для решения задач распределения ресурсов (военных, экономических, технических, биологических) систем, имеющих в своей структуре множество объектов, при исследовании, разработке и проектировании имитационных моделей различного назначения.
Известна система распределения ресурсов (патент RU, №2189073, публ. 10.09.2002 г.), содержащая блок назначения, центр распределения ресурсов, n объектов. Данная система производит последовательный опрос n объектов об избытке или недостатке ресурса у каждого объекта и распределяет ресурс каждому объекту. Недостатками данной системы являются отсутствие блока ранжирования и низкое быстродействие из-за реализации на устаревшей элементной базе.
Известна система распределения ресурсов, которая осуществляет решение задачи назначения с помощью точного венгерского метода и приближенного метода минимального элемента [1]. Недостатками данной системы являются невозможность пересчета матрицы эффективностей на каждом шаге работы алгоритма, отсутствие ранжирования объектов системы по значимости согласно выбранным критериям, а также недостаточное быстродействие алгоритмов.
Известна система распределения ресурсов, которая осуществляет классический вариант метода анализа иерархий Саати на основе экспертного сравнения на всех уровнях иерархической модели (альтернативы и критерии) [2]. Однако недостатками данной системы являются невозможность решения задачи назначения с максимально возможной эффективностью из-за отсутствия автоматизированной процедуры формирования коэффициентов значимости критериев и отсутствия анализа иерархий с выделением
необходимого набора критериев значимости объектов, а также недостаточно высокое быстродействие.
Задачей предлагаемой полезной модели является устранение всех перечисленных выше недостатков и создание быстродействующей автоматизированной системы распределения ресурсов для оптимального решения целевых задач, содержащей блок ранжирования, формирующий модифицированный метод анализа иерархий с выделением необходимого набора критериев оценки опасности объектов и использованием реальной информации при парном сравнении их между собой и реализующий автоматизированную процедуру, позволяющую уйти от экспертных оценок относительной значимости критериев в случае неопределенности, и блок назначения, реализованный на варианте венгерского метода - методе Мака, который ускоряет процедуру определения базисных столбцов и создает ранжированную последовательность выбора по строкам/столбцам матрицы эффективностей на основе средней эффективности с возможным ее пересчетом на каждом шаге работы алгоритма.
Поставленная задача решается автоматизированной системой распределения ресурсов для оптимального решения целевых задач, которая содержит блок ввода данных, блок формирования вектора значимости, блок формализации конфигурации системы, блок ранжирования, блок назначения, блок формирования матрицы распределения, блок вывода результатов. При этом первый выход блока ввода данных соединен с входом блока формирования вектора значимости, второй выход блока ввода данных соединен с первым входом блока назначения, первый выход блока формирования вектора значимости соединен с входом блока формализации конфигурации системы, второй выход блока формирования вектора значимости соединен со вторым входом блока назначения, первый выход блока формализации конфигурации системы соединен с входом блока ранжирования, второй выход блока формализации конфигурации системы
соединен с третьим входом блока назначения, первый выход блока ранжирования соединен с четвертым входом блока назначения, второй выход блока ранжирования соединен с первым входом блока формирования матрицы распределения, выход блока назначения соединен со вторым входом блока формирования матрицы распределения, выход блока формирования матрицы распределения соединен с входом блока вывода результатов.
В частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок назначения выполнен в виде блока точной оценки.
В другом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок назначения выполнен в виде блока приближенной оценки.
В третьем частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок назначения выполнен в виде блока комбинированной оценки.
В четвертом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок ввода данных выполнен в виде клавиатуры.
В пятом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок ввода данных выполнен в виде блок ввода данных с локальных дисков.
В шестом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок ввода данных выполнен в виде сервера базы данных.
В седьмом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок вывода результатов выполнен в виде принтера.
В восьмом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок вывода результатов выполнен в виде дисплея.
В девятом частном случае в автоматизированной системе распределения ресурса для оптимального решения целевых задач блок вывода результатов выполнен в виде сервера базы данных.
Сущность полезной модели поясняется чертежами, на которых представлены:
фиг.1 - структурная схема системы;
фиг.2 - структурная схема реализации блока назначения, выполненного в виде блока комбинированной оценки;
фиг.3 - блок-схема основных этапов алгоритма распределения ресурсов системы.
Предлагаемая автоматизированная система распределения ресурсов для оптимального решения целевых задач, схема которой представлена на фиг.1, в общем случае содержит: блок ввода данных, блок формирования вектора значимости, блок формализации конфигурации системы, блок ранжирования, блок назначения, блок формирования матрицы распределения, блок вывода результатов. При этом первый выход блока ввода данных соединен с входом блока формирования вектора значимости, второй выход блока ввода данных соединен с первым входом блока назначения, первый выход блока формирования вектора значимости соединен с входом блока формализации конфигурации системы, второй выход блока формирования вектора значимости соединен со вторым входом блока назначения, первый выход блока формализации конфигурации системы соединен с входом блока ранжирования, второй выход блока формализации конфигурации системы соединен с третьим входом блока назначения, первый выход блока ранжирования соединен с четвертым входом блока назначения, второй выход блока ранжирования соединен с первым входом блока формирования
матрицы распределения, выход блока назначения соединен с вторым входом блока формирования матрицы распределения, выход блока формирования матрицы распределения соединен с входом блока вывода результатов.
Предлагаемая полезная модель решает практическую задачу оптимизации управления многообъектными системами путем нахождения компромисса между свойствами стабильности и эффективности, поэтому управляющие силы в общем виде представлены в виде параметризованных программно-корректируемых законов управления с процедурами решения на основе оперативного управления и численных методов математического программирования. Требования к решению данной задачи: некая совокупность целей и некая совокупность ограничений. Решение данной задачи осуществляют путем сочетания теории дифференциальных игр и традиционных подходов теории оптимального управления (вариационные подходы, принцип максимума, динамическое программирование, численные методы математического программирования). Составной частью этой задачи является создание системы распределения ресурсов для оптимального решения целевых задач. Данная система является однокритериальной, т.е. распределение ресурсов по объектам системы осуществляют по какому-либо одному критерию. Данная система имеет возможность работы с базами данных (получение и сохранение данных).
Блок ввода данных может быть выполнен в виде клавиатуры, или в виде блока ввода данных с локальных дисков, или в виде сервера базы данных. Блок ввода данных задает ресурсы, количество объектов и параметры объектов и ресурсов. Блок ввода данных передает конфигурационные характеристики каждого объекта системы в блок формирования вектора значимости.
Блок формирования вектора значимости формирует вектор значимости критериев при расчете суммарной значимости объектов {х, у, z,...,n}, где х, у, z,..., n - параметры объекта на основе экспертной информации. В
рассматриваемом частном случае n=7. На основе информации об объектах системы задают необходимое число критериев значимости, по которым производят оценку значимости объектов системы друг относительно друга. Также в блоке формирования вектора значимости вводят весовые коэффициенты значимости критериев. Блок формирования вектора значимости разделяет объекты на обслуживаемые и необслуживаемые. Объекты, на которые произошло распределение ресурса, считаются обслуживаемыми, и дальнейшее распределение ресурса идет по необслуживаемым объектам. Таким образом, при формировании исходных данных для ранжирования учитываются только необслуживаемые объекты.
Блок формализации конфигурации системы производит расчет значений для введенных в блоке ввода данных критериев по известным характеристикам системы для каждого объекта системы.
Блок ранжирования производит расстановку объектов системы по значимости согласно выбранным критериям. В качестве математического аппарата ранжирования используют метод ранжирования многокритериальных альтернатив Саати, сущность которого состоит в парном сравнении всех объектов системы с дальнейшим формированием собственных векторов значимости по каждому критерию. Введенные в блоке формализации конфигурации системы весовые коэффициенты значимости критериев позволяют получить суммарную многофакторную значимость каждого объекта. Коэффициенты значимости критериев задаются экспертно заранее либо вычисляются автоматически, используя полученную ранее информацию о ранжировании объектов по каждому критерию. В предлагаемой полезной модели процедура расчета автоматизирована. Блок ранжирования формирует матрицу эффективностей (стоимостей) по каждой связи между объектами системы для дальнейшей передачи матрицы эффективностей в блок назначения. Наиболее важный объект в группе из n объектов имеет порядковый номер ранжирования - 1, наименее важный - n.
Блок назначения может состоять из блока точной оценки, или блока приближенной оценки, или блока комбинированной оценки. Выбор одного из блоков зависит от численности объектов, входящих в каждую систему, необходимой точности формируемого решения, скорости вычисления в процессе имитации взаимодействия систем и других факторов.
Блок точной оценки производит преобразование матрицы эффективностей с помощью одного из точных методов (метод Мака, венгерский метод).
Блок приближенной оценки производит преобразование матрицы эффективностей с помощью приближенных методов (метод минимального элемента и его различные модификации).
Блок комбинированной оценки производит преобразование матрицы эффективностей с помощью комбинированных методов на основе сопряжения точных и приближенных методов, в результате чего достигается компромисс по точности и быстродействию.
Матрица назначения представляет собой матрицу {Jy}, элементами которой являются значения 0 или 1, характеризующие назначения ресурса системы на объект. Так как назначение рассматривают на текущий момент времени, следовательно, проведенное ранее назначение хранится в базе данных. Обращение к данной базе данных производят для «отсеивания» объектов при вводе конфигурации системы для назначения, а также на этапе ввода полученного назначения. На данной стадии рассматривают распределение одной единицы ресурса на каждый объект. Если имеется n объектов, то размерность матрицы - n×7. Объекты выбираются на основании сформированного ряда ранжирования объектов по приоритетам. Если количество каналов nк больше количества объектов n, то все объекты будут обслужены при первом распределении.
Блок точной оценки, или блок приближенной оценки, или блок комбинированной оценки решают задачу оптимального распределения
дефицитных ресурсов по множеству объектов системы. Максимум эффективности распределения ресурсов обеспечивают путем преобразования матрицы эффективностей, полученной в блоке формализации конфигурации системы с помощью информации блока ранжирования. После выбора необходимого числа наиболее важных объектов взаимодействующей системы производят назначение.
Выбор метода зависит от численности объектов, входящих в систему, необходимой точности формируемого решения, скорости вычисления в процессе имитации взаимодействия системы и других факторов.
Блок формирования матрицы распределения производит формирование матрицы распределения ресурсов системы на основании полученного решения задачи распределения ресурсов в форме назначения-ранжирования.
Блок вывода результатов производит окончательный анализ полученного оптимального решения и вывод его в соответствующей форме на каждый объект системы как результат распределения ресурсов.
Блок вывода результатов может быть выполнен в виде дисплея ПЭВМ, или в виде принтера. Также блок вывода результатов может быть выполнен в виде сервера базы данных.
Рассмотрим работу автоматизированной системы распределения ресурсов для оптимального решения целевых задач на примере работы схемы системы, представленной на фиг.1. в соответствии с алгоритмом распределения ресурсов системы, представленным на фиг.3.
На первом этапе на основании исходных данных формируются конфигурационные характеристики каждого объекта, которые представляют вектор n параметров.
На втором этапе данные по конфигурации объектов поступают в процедуру назначения. Здесь отсеивают те объекты, по которым уже произведено назначение ресурса и в процедуру назначения передают только те данные, которые касаются необслуживаемых объектов.
На третьем этапе производится ранжирование, когда для каждого объекта формируется набор критериев, по которым оценивается его значимость. На основе парных сравнений объектов по каждому критерию формируются собственные векторы значимостей, а затем путем выбора весовых коэффициентов вычисляется суммарная многофакторная значимость. Данный этап можно разбить на три части: формирование матриц значимостей объектов по критериям, проведение расчета собственного вектора значимости объектов по каждому фактору с их нормированием, и формирование многофакторной значимости. Весовые коэффициенты значимости факторов в классическом методе Саати формируют путем экспертного парного сравнения их значимости. В предлагаемой полезной модели коэффициенты значимости факторов вычисляются автоматически. Формирование собственного ряда ранжирования состоит в том, что объекту, имеющему большее значение многофакторной значимости, присваивается меньший порядковый номер. Наиболее значимый объект имеет порядковый номер ранжирования 1, наименее значимый - n.
На четвертом этапе рассматривают соотношение числа объектов n и числа каналов nк, по которым производят распределение ресурсов. Если n>nк, то запускают процедуру выбора объектов с целью выбора объектов, которые будут обслужены при первом распределении; если n<nк, то необходимость в данном выборе отпадает, так как все объекты будут обслужены при первом распределении. Далее для выбранных объектов рассчитывают обобщенные эффективности обслуживания каждого объекта каждым каналом. Матрица этих значений является выходным параметром данного этапа; размерность матрицы - nк×nк.
На пятом этапе формируют матрицу назначения на основе модификации метода минимального элемента. Может быть предложено четыре варианта последовательного выбора назначения: по убыванию эффективностей, по возрастанию эффективностей, с расчетом по строкам, с расчетом по
столбцам. В данной полезной модели рассматриваем первый вариант, когда для наихудшего по вероятности канала выбирается наилучший объект, и затем расчет ведется для каналов с последовательным улучшением характеристик воздействия.
На шестом этапе передают команду на распределение ресурсов согласно сформированной на пятом этапе матрице назначения. Одновременно идет заполнение базы данных о распределении ресурсов. Эту база данных используют при формировании данных для второго этапа алгоритма. Предлагаемый алгоритм обладает достаточно высоким быстродействием.
С помощью предлагаемой автоматизированной системы распределения ресурсов можно решать конфликтные задачи распределения ресурсов (военные, экономические, технические, биологические) при взаимодействии систем, имеющих в своей структуре множество объектов с достижением при этом достаточно высокого быстродействия.
Источники информации:
1. Волков И.К., Загоруйко Е.А. Исследование операций: Учебник для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 436 с.
2. Ларичев О.И. Теория и методы принятия решения, а также Хроника событий в Волшебных странах: Учебник. 2-е издание, перераб. и доп.- М.: Логос, 2002. - 392 с.
3. Воронов Е.М. Методы оптимизации управления многообъектными многокритериальными системами на основе стабильно-эффективных игровых решений. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 576 с.