Моделирование системы распределения ресурсов

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

Рассмотрим модель задачи распределения ограниченных ресурсов S между параллельными объектами в линейной постановке:

 

 

                             (1)

 

             (2)

 

                                      (3)

 

                                    (4)

 

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

1)         возможное изменение вектора правых ограничений (2) ресурсов si  на некоторую величину ds:

    (5)

2)         возможное изменение параметров целевой функции:

                    (6)

Если не существует неопределенности в отношении ограничений, но ставится под сомнение целевая функция (случай 2), то можно использовать метод, основанный на теории двойственности с использованием симплекс-таблиц. Существующий аппарат анализа моделей оптимизационных задач на чувствительность к их параметрам является по своей сути весьма простым, хотя и отличается некоторой громоздкостью. Однако существует широкий класс задач, для решения которых применяются принципиально другие методы, учитывающие специфику поставленных задач. К ним относится и задача распределения ограниченных ресурсов в параллельных системах с учетом возможной, но не обязательной врожденности матрицы ограничений. Поэтому в данной работе анализируется возможность использования компьютерной модели для анализа и улучшения найденных ранее оптимальных режимов процессов распределения, характеризуемых не стационарностью ряда параметров [28].

 

 

 

 

                                                рисунок 1.

 

Аппарат компьютерного моделирования позволит осуществлять анализ параметров, используя последовательную диагностику показателей системы (рис.1).

Идентификация стохастической модели изменения ресурсов является одной из существенных задач имитационной системы [29]. Случайный характер изменения некоторых параметров, например, объемов ресурса, является причиной необходимости определения (идентификации) законов распределения случайных величин, характеризующих изменение объемов ресурса. При этом необходимо использовать известные методы и алгоритмы идентификации [8]. Затем производится имитирование по полученным законам распределения фактических изменений параметров с помощью соответствующих алгоритмов моделирования случайных закономерностей.

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

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

Рассмотрим случай s = s'+ds.

Предположим, что вектор правых частей ограничения (2) -ресурсы St, в течение некоторого интервала времени может целенаправленно изменяться на некоторую величину AS. Тогда модель задачи представим в следующем виде:

 

 

 

 

 

                              (7)

 

 

При решении вопроса о том, запас какого из ресурсов следует увеличивать в первую очередь, обычно используют теневые цены [27]. Заметим, что теневая цена - это термин, который экономисты используют при характеристике ценности ресурсов. Теневая цена характеризует интенсивность улучшения оптимального значения F. Однако при этом не фиксируется интервал значений увеличения запасов ресурса, при которых интенсивность улучшения целевой функции остается постоянной. Для большинства практических ситуаций логично предположить наличие верхнего предела увеличения запасов, при превышении которого соответствующее ограничение становится избыточным, что в свою очередь приводит к новому решению и соответствующим теневым ценам. Следовательно, следует определить интервал значений запасов ресурса, при которых соответствующее ограничение не становится избыточным, т. е. теневая цена данного ресурса остается неизменной.

Структура модели задачи (7) позволяет выявить следующие аналитические выкладки

Разложим целевую функцию в ряд Тейлора в окрестности точки xp.

 

(8)

 

где xp и Fp - соответственно оптимальное решение и значение целевой функции расширенной задачи (9):

 

 

 

                               (9)

 

 

                         

 

sp - значения правых частей ограничений (2), соответствующие решению xр.

Поскольку анализ модели задачи на чувствительность проводится относительно ресурсов, то параметры также Sm предполагаются постоянными. Следовательно, постоянными будут и величины fp и sp. Это в свою очередь приводит к зависимости значения целевой функции от вектора S (рис. 2).

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

Из рис. 2 видно, что областью изменения ресурса S, в которой возможно улучшение найденного ранее решения, является интервал [S°, SP], при выборе нового значения S не должно нарушаться условие

 S=S0+dS≤Sp   (10)

Это условие справедливо и для каждой эффективной компоненте вектора S:

 (11)

Таким образом, при имитационном поиске области изменения

параметров исходной модели с целью улучшения найденных ранее оптимальных решений ЗРР, необходимо при моделировании dS учитывать неравенство (11).

 

                         рисунок 2

 

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

Рассмотрим случай с двумя эффективными ограничениями. Пусть этим ограничениям соответствуют ресурсы Sk и Sl . Кроме того, предположим, что один из этих ресурсов, например Sk, является основным. Изменим значения этих ресурсов:  (рис. 3.).

Такому изменению ресурсов на графике (рис.3) соответствует точка А. Значение целевой функции улучшилось: F=F1.

Пусть теперь, где . В этом случае (точка В на рис. 3) F= F2 (<F1) и ограничение, соответствующее основному ресурсу , становится неэффективным. Сказанное можно резюмировать как утверждение: "Наибольший эффект от изменения ресурсов будет достигнут, если в новом решении ограничения, эффективные прежде, будут также эффективны". Формула

                   (12)

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

 

                          рисунок 3

 

 

Наряду с увеличением возможно и уменьшение некоторых видов -ресурсов. Очевидно, что любое изменение в меньшую сторону ресурса S влечет неизбежное ухудшение значения целевой функции. Однако структура модели рассматриваемых задач позволяет сделать следующие выводы. Напомним, что для решения задач данного класса мы применяем метод расширения [28]. Данный метод предполагает решение ЗРР путем направленного перехода к ее оптимальному решению из точки, соответствующей решению более простой задачи с расширенной областью допустимых решений. При этом оптимальным является направление (k, I), минимизирующее выражение

       (13)           по всем возможным направлениям спуска

 

 

Величина шага спуска

                                                                                        (14)

найденная из условия (13), обеспечивает минимальное отклонение F (х) от F (хР), но гарантирует выполнение только ограничения с индексом t. Чтобы не было нарушено ни одно из ограничений, выбирается такое направление, которому соответствует наибольшее из выражений (13) по всем , где - множество индексов ограничении (13.2), которые были нарушены при подстановке в них хp, т. е.

                                (15)

 

Следовательно, ограничение с номером τ, по параметрам которого вычисляется шаг спуска, становится эффективным, т. е. aτx=S, тогда как для других ограничений очевидно следующее соотношение:

                                                                          (16)

т. е. возможное уменьшение Si до значения Si не влияет на полученное ранее оптимальное решение.

Рассмотрим случай с = с' + σ. Рассмотрим случай, когда возможно изменение параметров целевой функции F.

 

 

 

 

 

                                                                                   (17)

 

 

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