Алгоритм решения обратной задачи распределения неоднородных ресурсов

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

Итак, необходимо найти такое минимальное значение средств {ni }, i=1,N* и так распределить их по единицам продукта {тi}, j = 1,М, чтобы эффект обслуживания каждой из единиц Pj был не менее некоторого заданного значения Pj3.

План распределения средств будем характеризовать матрицей h={hij), где:

Таким образом, необходимо найти такие значения N* и h*, которые являются решением задачи:

Pij -- вероятность выполнения задачи i-м средством по j-й единице продукта; H -- множество возможных планов распределения средств.

Множество Н может быть задано ограничениями, записываемыми, например, в виде:

-- каждое средство может быть назначено не более чем на одну единицу продукта:

-- за каждой единицей может быть закреплено не более V средств.

Наиболее распространенные методы решения обратных задач -- различные модификации метода случайного поиска, метод динамического программирования и др. [1]. Однако применение этих методов в ряде случаев, особенно для задач большой размерности, не является эффективным, что связано со значительным числом итерационных вычислений для определения решения, а, следовательно, увеличением времени решения задачи на ЭВМ [2].

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

Рассмотрим матрицу эффективности распределения P={Pij}, ; :

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

Матрица Н* может быть представлена, например, следующим образом:

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

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

Соотношение (5) перепишем в следующем виде:

где nk* --минимальное число средств, которое необходимо назначить на k-ю единицу продукта для выполнения условия (2) без учета ограничения (3). обратный задача неоднородный ресурс

Таким образом, значения h*ik , а следовательно, и n*k () могут быть определены путем решения M следующих задач:

при условии:

где Pk3 -- заданный уровень эффективности обслуживания k-й единицы продукта, или:

При назначении одного из средств на каждом шаге распределительного процесса будем использовать принцип наименьшего отклонения величины наряда средств, полученного с учетом назначения средства i* на единицу продукта j*, от нижней границы критерия N_.

Это означает, что для реального назначения следует выбирать элемент (i*, j*), обеспечивающий выполнение условия

nk ij -- минимальное число средств, выделяемых на k-ю единицу продукта с учетом назначения средства i на единицу продукта j. Наряд средств, соответствующий назначению определенного средства i* на определенную единицу продукта j*, характеризуется планом распределения H i* j* и вектором { nk i* j * } (), которые также находятся путем решения М задач:

при условии:

или:

Таким образом, на каждом шаге процесса оптимизации требуется поддержание такого порядка распределения средств, который обеспечивает наименьшее приращение критерия [3 - 10].

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

1. Вычислить элементы nk * (0), удовлетворяющие условию

2. Вычислить элементы удовлетворяющие условию

где N(t) -- множество средств, не использованных к t-му шагу вычислительного процесса;

M(t) -- множество единиц продукта, не обслуженных к t-му шагу вычислительного процесса;

Pk3(t) -- заданная вероятность обслуживания k-й единицы продукта к t-му шагу вычислительного процесса.

3. Вычислить элементы матрицы по соотношениям

4. Закрепить средство i* за j* единицей продукта согласно условию:

5. Пересчитать Pj3

6. Пересчитать nj*:

7. Проверить условие

8. Проверить условие M(t+1)=0:

9. Проверить условие

10. Конец.

При выборе элементов (i*, j*) в п. 5 возможны случаи существования нескольких пар индексов, которые реализуют условие:

Другими словами, появляется неоднозначность в выборе элементов (i*, j*). Возникшую неоднозначность можно разрешить следующим образом. Назовем оптимальным элементом матрицы ? элемент, соответствующий индексам, определяемым из условия (10). Обозначим: N i* j -- число оптимальных элементов, вычеркиваемых из столбца матрицы ? при выборе оптимального элемента (i*, j*); N i j* -- число оптимальных, элементов, вычеркиваемых из строки матрицы ? при выборе оптимального элемента (i*, j*).

Тогда Ni* j* = N i* j + N i j* -- число оптимальных элементов, вычеркиваемых из матрицы ? при назначении оптимального элемента (i*, j*).

Поставив в соответствие каждому оптимальному элементу величину Ni*j*, будем производить назначение этих элементов в порядке возрастания Ni*j*, начиная с оптимальных элементов, соответствующих наименьшим значениям этого показателя. Оптимальные элементы, оказавшиеся в строке или столбце назначенного оптимального элемента, из дальнейшего рассмотрения на данном шаге распределительного, процесса исключаются.

Литература

1. Борисов А.Н., Алексеев А.В., Меркурьева Г.В. Обработка нечеткой информации в системах принятия решений // Радио и связь. 1989. 304 с.
2. Белоусов В.Е., Гайдук А.В., Золоторев В.Н. К проблеме решения задач многокритериальной оптимизации // Системы управления и информационные технологии. 2006. № 3(25). С. 34-43.
3. Баркалов С.А., Белоусов В.Е., Урманов И.А. Алгоритм построения частных решающих правил при анализе систем организационного управления // Вестник Воронеж. гос. техн. ун-та. 2009. №Т.5, №2. С. 129-133.
4. Шеина С.Г., Миненко А.Н Концепция экосистемного подхода управления строительным объектом на проектной фазе жизненного цикла // Научное обозрение. 2014. №7-2. С. 580-582.
5. Шеина С.Г., Хамавова А.А Систематизация информации о состоянии территориального развития субъекта Российской Федерации // Научное обозрение. 2014. №8-3. С. 881-887.
6. Сеферян Л.А., Зильберова И.Ю. Стимулирование предприятий сферы управления при отсутствии рыночных мотиваций // Научное обозрение. 2014. №10-2. С. 508-511.
7. Зильберова И.Ю., Героева А.М. Прогнозирование и диагностика технического состояния объектов коммунальной инфраструктуры // Инженерный вестник Дона, 2012
8. Зильберова И.Ю., Высоковская Л.В. Особенности проектирования в России // Инженерный вестник Дона, 2012
9. Lootsma, F.A. (1993) Scale sensitivity in the Multiplicative AHP and SMART, Journal of Multi-Criteria Decision Analysis, Vol. 2, pp. 87-110.
10. Lootsma F.A., Schuijt H. (1997) The multiplicative AHP, SMART and ELECTRE in a common contex.- J. Multi-Criteria Decision Analysis, Vol. 6, pp. 185-186