Математические модели операций.

Как уже говорилось выше, под математическими моделями операции будем понимать всякие формальные соотношения, устанавливающие количественную связь между управляемыми переменными xÎX (yÎY), неуправляемыми и неизменяемыми в ходе операции факторами, технологическими параметрами элементов, систем и устройств, используемых в операции (а), неконтролируемыми факторами Z и показателем (показателями) эффективности операции W, характеризующим ее результат. Т.е.

                                       а

                x, y                                          W (a, x, y, z)             

                                              Z        

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

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

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

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

В наиболее сложных случаях, когда развитие операции и ее исход зависят от большого числа сложно переплетающихся между собой факторов, часть из которых случайна и аналитические методы исследования вообще отказываются служить, широкое применение находит метод имитационного моделирования, суть которого заключается в следующем. Процесс развития операции с учетом всех случайных факторов (подлежащих учету) воспроизводится (моделируется) на ЭВМ. В результате получается одна “реализация” случайного протекания операции со случайным ее исходом. При многократном повторении хода операции, за счет ее случайности получим множество различных реализаций, обработав которые как обычный статистический материал можно найти средние арифметические процесса, получить представление как в среднем влияют на результат операции те или другие характеристики и управляющие переменные. Такие модели часто называют имитационными.

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

Изучением таких операций занимается специальный раздел ИО – теория игр.

При разработке модель должна отвечать ряду общих требований.

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

2. Математическая модель с одной стороны должна учитывать все существенные факторы, влияющие на ход операции, но с другой стороны, быть по возможности простой, не “засоренной” массой мелких деталей (второстепенных), которые лишь усложняют исследования и затрудняют выявление основных закономерностей, делая подчас их применение для анализа операций практически невозможным.

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

4. Кроме того точность (детальность) модели должна быть соизмерима с точностью информации о значениях параметров a и z, которой мы располагаем. В противном случае мы можем получать недостоверные результаты даже при казалось бы чрезвычайно подробной, детальной модели.

Разновидность задач ИО.

Все задачи ИО можно условно разбить на две категории: прямые и обратные.

Прямые задачи отвечают на вопрос “что будет, если в заданных условиях будет принято какое-то конкретное решение x*ÎX. В частности – при заданном решении x* и заданных детерминированных значениях неуправляемых факторов а чему будет равен выбранный показатель эффективности операции W(a,x*) или ряд показателей при векторном критерии эффективности

                                               W = W(a, x*).

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

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

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

Обратные задачи отвечают на вопрос – какое необходимо выбрать решение xÎX (оптимальное или рациональное) для того, чтобы обеспечить при этом наилучшее значение показателя эффективности W.

В случае скалярного критерия эффективности W под наилучшим будем понимать максимальное значение показателя. Тогда обратная задача ИО может быть записана следующим образом:

При заданном комплексе условий а найти такое решение

                                        x = x° (xÎX),

которое обращает показатель эффективности операции W в максимум

                                       W° (x°) = мах W(a, x)

                                                          xÎX

(см. Рисунок)

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

Если число возможных вариантов решения, образующих множество X невелико, то для поиска оптимального решения необходимо, для каждого из возможных значений xÎX, решая прямую задачу определить значение показателя W. Сравнив их между собой, можно указать одно или несколько решений, при которых W достигает максимума. Такой способ называется простым перебором.

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

С формальной точки зрения задачи поиска оптимального решения (в случае скалярного показателя W) относятся к классу задач математического программирования. Термин программирование от английского programming – составление плана или программы действий, здесь следует понимать в смысле “поиска наилучших планов”, а не в смысле разработки программного обеспечения для ЭВМ.

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

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

                                        мax U = U(W),

- либо решения (одно из решений), отвечающее условию, что нельзя найти другое решение, позволяющее улучшить любой из показателей Wi (i = 1,к) не ухудшая при этом значения других показателей Wx (x¹i) (хотя бы одно из них).  Такие решения называются эффективными или паретовскими (xпÎXп ).

 

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

 

              U = SaiWi  n£ ai £1 ,     Sai = 1 ( i = 1,k)  

                       i                            i

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

      0 £ a_i £1 ,          Sa_i = 1 ( i = 1, k)  

                             i

Поиск решения при выбранной функции свертки U(W) аналогичен поиску оптимального решения по скалярному критерию эффективности.   

 Во втором случае (не свернутый векторный критерий) поиск эффективных (паретовских) решений xпÎXп может быть осуществлен путем прямого перебора всех возможных решений xÎX (если оно конечно) с процедурой сравнения показателей

                                               W(x).

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

Следует подчеркнуть, что выбор наилучшего решения среди множества найденных xÎXп производится ЛПР.

 

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

Остановимся несколько подробнее на их постановке и методах решения.
Постановка и классификация задач математического программирования.

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

Формально задача мат. программирования в общем случае сводится к следующей:

найти значения переменных x₁,…x_n, доставляющие максимум (минимум) заданной скалярной функции f(x₁,…x_n; a)

при условиях g_i (x₁,…x_n) ≤ (≥, =) b_i , где i=1,…,m.

Здесь  a и b_i – константы , определяемые из физических условий задачи.

Условия g_i(x₁,…x_n) ограничивают возможность выбора значений переменных x₁,…x_n из множества всех возможных значений. Множество точек Х= { x₁,…x_n }, удовлетворяющих системе ограничений g_i (i=1,…,m) есть область определенияXпоставленной задачи.

Функция f(x₁,…x_n; a) называется целевой функцией, которая может достигать экстремальных значений в одной или нескольких точках области X, которые предстоит найти (в конкретных задачах ИО в качестве целевой функции используют критерий эффективности, вычисляемый на основе модели операции).

Обычно вид функций f и g известен, константы͞a и b_i, вытекающие из параметров исследуемой системы и целей, стоящие перед ней – заданы, число переменных n и ограничений m – определено. Кроме того, при необходимости, специально оговариваются ограничения на не отрицательность и целочисленность переменных x_i (i=1,…,n) исходя из их физической природы, которые также входят в систему ограничений на переменные.

 

Исходя из вышесказанного формальная запись задачи математического программирования имеет вид:

Параметр a входит в вид самой целевой функции и в дальнейшем может быть опущен.

В зависимости от вида целевой функции и ограничений можно выделить следующие классы задач:

1. Задачи линейного программирования. В них целевая функция и ограничения линейны относительно переменных x_i (наиболее изученный класс задач).

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

3. Задачи выпуклого программирования. Это такие задачи, когда целевая функция f и множество возможных решений X – выпуклые.

Множество X называется выпуклым, если для любых двух точек x₁,x₂ Î X оно содержит в себе весь отрезок, их соединяющий:

 

Функция f(x) называется выпуклой (выпуклой вниз) на интервале [x_1,x₂], если для любой точки  ( внутри этого интервала выполняется условие f( ) ≤ .

 

Здесь

(1)

(2)

(3)

 

Если f( ) ≥ , то функция называется вогнутой или выпуклой вверх.

 

Выпуклость целевой функции и ограничений позволяют формулировать и использовать условия существования оптимальных решений (экстремума) вне зависимости от их конкретного вида и формы задания.

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

4. По ограничениям, накладываемым на переменные x_i можно выделить задачи с непрерывными и дискретными переменными. Дискретность переменных нарушает выпуклость множества X и приводит, как правило, к необходимости либо полного, либо направленного перебора всех возможных решений xÎX, что значительно увеличивает трудоемкость решения задачи. При высокой размерности множества X точное решение задачи бывает практически невозможным за приемлемое время.

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

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

Рассмотрим более подробно ряд задач математического программирования и методов их решения.

⇐ Предыдущая12345678910Следующая ⇒