Научный журнал
Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955
ИФ РИНЦ = 0,580

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

Шукаев Д.Н. 1 Ергалиева Н.О. 1 Ламашева Ж.Б. 1 Абдикадырова А.А. 1
1 Казахский национальный технический университет им. К.И. Сатпаева
Статья посвящена анализу параметров задач распределения ресурсов и построению его имитационной модели. В работе приведена общая структура имитационной модели для улучшения найденных ранее оптимальных режимов технологических процессов, характеризуемых нестационарностью ряда параметров. На примере линейной и квадратичной задач распределения ресурсов рассмотрена процедура поиска оптимальных значений. Для преодоления проблемы распределения различных ресурсов, и в том числе, ресурсов, из которых формируются параллельные материальные или информационные потоки, в статье подробно описывается метод расширения и на основе данного метода разрабатывается алгоритм поиска оптимального значения в задачах распределения ресурсов. Результаты данной работы были использованы при разработке информационной системы крупной компании по хранению, переработке и реализации зерна.
распределение ресурсов
оптимизация
имитационное моделирование
нестационарные параметры
анализ параметров
1. Pervozvanskyi A. A. Optimization of system with weak coupling, Systems Science, V. 1-2, 1979, Vol. 2, P. 23-32.
2. Shukayev D.N. Computer Simulation – Almaty: KazNTU, 2004, 148 p.
3. Shukayev D.N., Kim E.R. Extension method in location problem with discrete objects. Proceedings of the 21st IASTED International Conference “Modelling and Simulation (MS 2010)”, Banff, Alberta, Canada, 2010, P. 270-274.
4. Shukayev D.N., Kim E.R., Shukayev M.D., Ergalieva N.O. Modeling resource flows and allocations in systems with parallel structure. /Applied Simulation and Modelling (ASM 2012). Proceedings of the IASTED International Conference June 25 – 27, 2012 Napoli, Italy.
5. Tikhonov A.N., Arsenin V.Y. Methods for solving ill posed problems (M.: Science, 1996).
6. Первозванский А.А., Гайцгори В.Г. Декомпозиция, агрерирование и приближенная оптимизация. – М.: Наука, 1979. – 344 с.
7. Cannon S, Rehman S, Mendez A, Vo V., Ordonez A, Singh A. Optimization of resource distribution in the George Mason university. Parking system: http://seor.gmu.edu/projects/capstone_2002/parking.pdf.
8. Nikolouzou E.G., Sampatakos P.D., Venieris I.S. Evaluation of an algorithm for dynamic resource distribution in a differentiated services network. Proceedings of the IEEE International conference on networking, Colmar, France, July 9-13, 2001.
9. Weikard H-P., Seyhan D. Distribution of phosphorus resources between rich and poor countries: the effect of recycling. Ecological economics, 2009, № 8, P.1749-1755.

Одной из важных задач, возникающих при оптимизации различных технологических процессов является выявление условий или параметров, сдерживающих дальнейшую оптимизацию технологического режима, и установление областей более благоприятных значений этих параметров. Существующие методы, например, не пригодны для задач с базисной матрицей ограничений, близкой к вырожденной, характерных для задач с «возмущенными» или слабо различающимися между собой значениями параметров [5]. Само решение таких оптимизационных задач связано с проблемой неустойчивости полученных решений и рассматривалась многими исследователями [1, 6-9]. В частности, в предшествующих работах руководителя авторского коллектива предлагаемой статьи и его коллег [2-4] предложен метод решения оптимизационных задач распределения и размещения ресурсов между параллельными объектами с учетом возможной, но не обязательной вырожденности матриц ограничений, основанный на расширении множества допустимых значений этих задач.

1. Общая постановка задачи и структура имитационной модели

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

shuka2.wmf (1)

shuka3.wmf (2)

shuka4.wmf (3)

где х – n-мерный вектор, b – m-мерный вектор, g(x) – векторная функция.

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

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

1. Решение задачи описанной выражениями (1)-(3).

2. Моделирование возможных изменений параметров модели оптимизационной задачи [2].

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

В соответствии с приведенной структурой имитационной модели можно предложить следующий алгоритм поиска shuka7.wmf.

Шаг 1. Решение задачи (1)-(3).

Шаг 2. Вычисление значений shuka8.wmf правых частей ограничения (2), соответствующих полученному оптимальному решению задачи (1)-(3). При условииповторного решения задачи (1)-(3) вычисление значения shuka9.wmf правых частей ограничения (2) и переход к шагу 6.

Шаг 3. Определение эффективных ограничений задачи.

Шаг 4. Моделирование shuka10.wmf для эффективных ограничений.

Шаг 5. Вычисление новых значений эффективных ограничений: shuka11.wmf.

Шаг 6. Определение области изменения параметров задачи shuka12.wmf.

Шаг 7. Конец алгоритма.

Для задачи распределения ресурсов [3] в силу особенности её математической модели (наличие ограничения – равенства) процедура поиска оптимальных значений ∆b* может быть упрощена. Рассмотрим это на примере линейной и квадратичной задач распределения ресурсов.

2. Поиск оптимальных shuka14.wmf в задачах распределения ресурсов

Рассмотрим задачу распределения ресурсов в линейной постановке:

shuka15.wmf (4)

shuka16.wmf (5)

shuka17.wmf (6)

shuka18.wmf (7)

Здесь с учетом слабых различий параметров моделей параллельных процессов коэффициенты ограничений (5) могут быть представлены в виде: shuka19.wmf.

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

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

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

В статьях [3,4] авторов данной работы предложен метод решения оптимизационных задач распределения ресурсов между параллельными объектами с учетом возможной «плохой обусловленности» их матриц ограничений, основанный на расширении множества допустимых значений этих задач.

Суть этого подхода состоит в том, что решение исходной оптимизационной задачи (4-7) определяется путем направленного перехода к ее оптимальному решению из точки, соответствующей решению некоторой вспомогательной задачи (8)-(10) с расширенным множеством допустимых значений:

shuka20.wmf (8)

shuka21.wmf (9)

shuka22.wmf (10)

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

Общая структура этапов решения задачи распределения ресурсов методом расширения имеет вид:

1. Решение расширенной задачи (8-10).

2. Проверка полученного решения на допустимость по ограничениям (5) исходной задачи. Если решение допустимо, то оно оптимально.

3. В противном случае переход к новому решению, для которого выполняются ограничения (5).

Обоснование и алгоритмы решения задачи (4)-(7) и приведенной ниже задачи с квадратичной целевой функцией (14)-(17) методом расширения приведены в статьях [3,4].

Установим, что в задаче (4)-(7) нестационарными параметрами являются ресурсы shuka23.wmf. Разложим целевую функцию (4) в ряд Тейлора в окрестности точки shuka24.wmf:

shuka25.wmf (11)

где shuka26.wmf и shuka27.wmf – соответственно, оптимальное решение и значение целевой функции расширенной задачи (12-14), полученные из исходной путем исключения «неудобных» ограничений (5) с возмущенными параметрами, shuka28.wmf – значения правых частей ограничений (5), соответствующие решению shuka29.wmf

shuka30.wmf (12)

shuka31.wmf (13)

shuka32.wmf (14)

Установим связь между множествами решений shuka33.wmf и shuka34.wmf соответственно исходной и расширенной задач. Предположим, что исходная задача имеет единственное решение.

Очевидным является лемма 1 [3]: «Допустимое множество решений shuka35.wmf исходной задачи (4)-(7) всегда является подмножеством множества решений расширенной задачи (12)-(14), т.е. shuka36.wmf».

Однако их оптимальные решения совпадут при выполнении условий следующей леммы 2 [3]: «Оптимальное решение исходной задачи совпадает с оптимальным решением расширенной задачи только тогда, когда:

1. Множества допустимых решений этих задач эквивалентны;

2. Оптимальное решение расширенной задачи принадлежит множеству shuka37.wmf, т.е. shuka38.wmf». Доказательство приведено в [3].

Суть метода расширения [3,4] состоит в том, что решение исходной задачи (4)-(7) получается путем направленного перехода к ее оптимальному решению из точки, соответствующей решению расширенной задачи (12)-(14).

Поскольку анализ модели задачи (4)-(7) на чувствительность производится относительно ресурсов, то параметры shuka39.wmf и shuka40.wmf а также shuka41.wmf предполагаются постоянными. Следовательно, постоянными будут и величины shuka42.wmf и shuka43.wmf. Это, в свою очередь, приводит к линейной зависимости значения целевой функции от вектора b (см. рис. 1). Здесь shuka44.wmf – вектор правых частей ограничений (5), соответствующий оптимальному решению задачи (4)-(7).

Из рис. 1 видно, что областью изменения ресурса b, в которой возможно улучшение найденного решения, является интервал shuka45.wmf, т.е. при выборе нового значения b не должно нарушаться условие

shuka46.wmf. (15)

Очевидно, что условие справедливо и для каждой эффективной составляющей вектора b:

shuka47.wmf (16)

где shuka48.wmf – множество индексов эффективных ограничений.

Для квадратичной задачи распределения ресурсов вида:

shuka49.wmf (17)

shuka50.wmf (18)

shuka51.wmf (19)

shuka52.wmf (20)

Вышеприведенные рассуждения также останутся справедливыми за исключением того, что зависимость F(b) примет нелинейный вид (рис. 2):

shuk.tiff

Рис. 1. Область изменения ресурса для линейной задачи

shuk2.tiff

Рис. 2. Область изменения ресурса для нелинейной задачи

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

3. Алгоритм поиска оптимальных shuka53.wmf в задачах распределения ресурсов

Алгоритм состоит из следующих шагов.

Шаг 1. Решение расширенной задачи (12)-(14).

Шаг 2. Переход к решению исходной задачи распределения ресурсов.

Шаг 3. Определение эффективных ограничений задачи. Если эффективное ограничение одно, то определение области изменения параметров по формуле: shuka54.wmf. Процесс вычислений на этом заканчивается, на шаг 6. Если же эффективных ограничений несколько, то переход к следующему шагу.

Шаг 4. Изменение основного ресурса в пределах: shuka55.wmf.

Шаг 5. Вычисление новых значений остальных ресурсов по формуле (21), на шаг 4.

Шаг 6. Конец алгоритма.

Заключение

Результаты работы были использованы при разработке информационной системы крупной компании по хранению, переработке и реализации зерна «Цесна-Астык», характеризующейся разветвленной последовательно-параллельной технологической структурой, где на каждом технологическом этапе переработка зерна осуществляется на нескольких параллельно включенных агрегатах со слабо отличающимися характеристиками. Поэтому при построении моделей этапов переработки была получена система уравнений с малыми параметрами. Экспериментальная реализация имитационного анализа эффективных значений нестационарных параметров данного производства на основе компьютерной имитации характеристик производственного процесса позволила выявить дополнительные производственные ресурсы и увеличить производственные мощности до 5,0%. Численная реализация задачи распределения ресурсов в процессе имитационного анализа также показала эффективность использованного для ее решения метода расширения допустимых значений [3,4] для моделей с малыми параметрами.


Библиографическая ссылка

Шукаев Д.Н., Ергалиева Н.О., Ламашева Ж.Б., Абдикадырова А.А. ИМИТАЦИОННАЯ МОДЕЛЬ АНАЛИЗА ПАРАМЕТРОВ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 6-2. – С. 214-217;
URL: http://www.applied-research.ru/ru/article/view?id=6875 (дата обращения: 19.04.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074