Нелинейное и динамическое программирование; понятие об имитационном моделировании

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

(3.37)

(3.38)

(3.39)

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

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

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

o Локальный max или min является также глобальным max или min целевой функции на множестве допустимых решений, т.е. не существует локального оптимума целевой функции, отличного от глобального оптимума.

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

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

Пример 3.8. Найти шах и min функции при ограничениях

Решение. Линии уровня целевой функции (Z = const) представляют собой окружности с центром в начале координат; область допустимых решений не является выпуклой и состоит из двух отдельных частей (на рис. 3.6 эти части заштрихованы, линии уровня показаны пунктиром). Минимальное значение функции Z = 17 достигается в точках А(1; 4) и L(4; 1). Функция Z имеет два локальных максимума: в точке £>(2/3; 6), где функция , и в точке M(7; 4/7), в которой функция Z(M) = 2417/49.

Точка М - точка глобального максимума (рис. 3.6).

Особое место занимают задачи типа

(3.40)

(3.41)

для решения которых можно воспользоваться классическим методом оптимизации Лагранжа, или методом разрешающих множителей. При этом предполагают, что функции f и gi (i = 1,m) непрерывны вместе со своими первыми частными производными. Для решения задачи составляют функцию Лагранжа

определяют частные производные этой функции по переменным и множителям Лагранжа , приравнивают их нулю и получают систему уравнений:

Рис. 3.6

(3.42)

В основе метода Лагранжа решения классической задачи оптимизации (3.40), (3.41) лежит утверждение, что если функция в точке имеет экстремум, то существует такой вектор , что точка является решением системы (3.42). Следовательно, решая систему (3.42), получаем множество стационарных точек, в которых функция Z может иметь экстремальные значения. При этом, как правило, неизвестен способ определения точек глобального максимума или минимума. Однако если решения системы найдены, то для определения глобального максимума или минимума достаточно найти значения функции в соответствующих точках области определения.

Пример 3.9. Найти экстремум функции при ограничениях

Решение. Составляем функцию Лагранжа

дифференцируем ее по переменным .г),х2,ХзД)Д2 и полученные выражения приравниваем нулю:

Из первого и третьего уравнений следует, что поэтому

откуда . Поскольку, например, точка (0; 2; 0) принадлежит допустимой области и в ней Z = 0, то делаем вывод, что точка (1; 1; 1) - точка глобального максимума.

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

найти ,

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

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

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

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

(3.43)

(3.44)

(3.45)

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

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

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

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

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

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

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

o Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления un, под воздействием которого система переходит из одного состояния Sn в другое . Поскольку процесс марковский, то иn = un(Sn) зависит только от текущего состояния.

o Каждый шаг (выбор очередного решения) связан с определенным эффектом, который зависит от текущего состояния и принятого решения: φn(Sn, un).

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

Требуется найти такое решение un для каждого шага (п = 1, 2, 3,..., N), т.е. последовательность (u1,..., uN), чтобы получить максимальный эффект (доход) за N шагов.

Любая возможная допустимая последовательность решений (u1,..., uN) называется стратегией управления. Стратегия управления, доставляющая максимум критерию оптимальности, называется оптимальной.

В основе общей концепции метода ДП лежит принцип оптимальности Беллмана.

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

где un(Sn) - все допустимые управления при условии, что система находится в состоянии Sn;

φn(Sn, un) - эффект от принятия решения un;

fn(Sn) - эффект за оставшиеся п шагов.

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

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

В качестве примера построения РДП рассмотрим использование принципа оптимальности для реализации математической модели задачи оптимального распределения некоторого ресурса в объеме х:

где xj - количество ресурса, используемое j-м способом;

φn(xj) - доход от применения способа .

Рекуррентные соотношения, с помощью которых находится решение этой задачи, имеют вид:

Пример 3.10. Найти максимум функции при ограничениях

Решение. Целевая функция задачи является аддитивной, так как ее можно представить в виде суммы функций fj(xj), каждая из которых зависит только от одной переменной хj.

где

Находим Поскольку на переменные xj накладываются условия целочисленности и неотрицательности, то знак (знак [] обозначает целую часть числа, т.е. наибольшее целое число, не превосходящее данное); таким образом, x1 Î {0,1,2}. Для каждого фиксированного значения l вычисляем значение функции f1(l) выбираем среди них максимальное, при этом в соответствии с ограничениями задачи X может принимать все целые значения от 0 до 8. Далее вычисляем:

для всех ;

для всех

Все вычисления приведены в табл.3.16.

Таким образом, max Оптимальную стратегию находим следующим образом. Сначала устанавливаем, что (соответствует максимальному значению 192). Значение находим из соответствующих граф табл. 3.16 для при ).

Далее находим значение для при ). Таким образом, оптимальная стратегия имеет вид (0; 0; 4).

Таблица 3.16

Результаты расчетов в соответствии с РДП

l

f1(l)

f2(l)

f3(l)

x1 = 0

x1 = 1

x1 = 2

x2 = 0

x2 = 1

x2 = 2

x3 = 0

x3 = 1

x3 = 2

x3 = 3

x3 = 4

0

0

0

1

0

0

2

0

0

3

0

0

-4

4

0

3

0

-4

5

0

3

0

-4

6

0

3

0

-4

-8

7

0

3

0

-1

-8

8

0

3

12

0

-1

-8

12

6

27

81

192*

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

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

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

1. Формирование проблемы: описание исследуемой проблемы и определение целей исследования.

2. Разработка модели: логико-математическое описание моделируемой системы в соответствии с формулировкой проблемы.

3. Подготовка данных: идентификация, спецификация и сбор данных.

4. Трансляция модели: перевод модели со специальных имитационных языков, используемых на этапе 2 (СИМУЛА, СЛАМ и др.), на язык, приемлемый для используемой ЭВМ.

5. Верификация: установление правильности машинных программ.

6. Валидация: оценка требуемой точности и адекватности имитационной модели.

7. Планирование: определение условий проведения машинного эксперимента с имитационной моделью.

8. Экспериментирование: многократный прогон имитационной модели на ЭВМ для получения требуемой информации.

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

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

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

В этом случае в основе имитационного моделирования лежит метод статистического моделирования (метод Монте-Карло). Этот метод позволяет воспроизводить на компьютере случайные величины (с.в.) с заданными законами распределения. Так как отдельные реализации этих с.в. получены искусственно, то их реализации называют псевдослучайными числами. Процедуры получения псевдослучайных чисел называют генераторами (датчиками) псевдослучайных чисел.

Например, при проведении имитационных экспериментов в среде MS Excel (при использовании стандартных офисных средств) могут быть использованы встроенные датчики, генерирующие семь типов распределений: равномерное, Пуассона, нормальное, Бернулли, биномиальное, модельное и дискретное (опции Инструменты анализа/Генерация случайных чисел надстройки Пакет анализа).

Примеры имитационного моделирования систем управления запасами и массового обслуживания средствами MS Excel приведены, например, в литературе.

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

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

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

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