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

gt (^, х2,..., хп), г = 1, т являются нелинейными:

max(min )f(x1,x2,...,xn), (3.38)

giix^x2,...,*„) {<,=,>}&і, і = 1,/n, (3.39)

Xj > 0, j = T~n. (3.40)

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

Множество допустимых решений выпукло.

Множество всех точек jcnj n-мерного пространства, в

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

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

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

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

L Пример 7.

• х2 < 4

+ х2 > 5 ? х1 <7 х2 <6

х1 > О, х2 > О.

Линии уровня целевой функции (Z ~ const) представляют собой окружности с центром в начале координат; область допустимых решений не является выпуклой и состоит из двух отдельных частей (на рис. 3.4 эти части заштрихованы, линии уровня показаны пунктиром). Минимальное значение функции Z = 17 достигается в точках А( 1;4) и Д4;1). Функция Z имеет два локальных максимума: в точке

328

D(2/3;6), где функция Z(D) = , и в точке М(7;4/7), в которой функция Z(M) = 2417/49 .

Точка М — точка глобального максимума (рис. 3.4). (3.41) (3.42)

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

max(min)Z = f(x1,x2,...,xn), gi(x1,x2,...,xп) = 0, і = 1,т, для решения которых можно воспользоваться классическим методом оптимизации Лагранжа, или методом разрешающих множителей. При этом предполагают, что функции f

и gi (і = 1, т) непрерывны вместе со своими первыми частными производными.

Для решения задачи составляют функцию Лагранжа

1' ? " * ' Л7П

т

+YJXigi{xl,x2,...,xn),

i=1

определяют частные производные этой функции по переменным Xj (j = l,n) и множителям Лагранжа А; (і = 1, т. \ приравнивают их нулю и получают систему уравнений:

8F _ 8f дЄі

0Х1 0Х1 ы і oxi (3.43) dF дХі

= gi(x 1,х2,...,хп) = 0,і = 1,т. В основе метода Лагранжа решения классической задачи оптимизации (3.41), (3.42) лежит утверждение, что если

Z = f(xltx2,---,xn) В точке Х° = ,Х2,...,Х°)ИМЄЄТ экстремум, то существует такой вектор (A,®, А,®,.. •, Х°т), что точка (Х°,Х2 ."'і^Ді Д°2,...Д°т) является решением системы (3.43). Следовательно, решая систему (3.43), получаем множество стационарных точек, в которых функция Z может иметь экстремальные значения. При этом, как правило, неизвестен способ определения точек глобального максимума или минимума. Однако если решения системы найдены, то для определения глобального максимума или минимума достаточно найти значения функции в соответствующих точках области определения.

к.

х\ + х2 = 2,

при ограничениях

х2 + х3 = 2.

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

F(Xl гх2,х3,Хі,Х2) - х±х2 + х2х3 + -а^*! + х2 - 2) + А,2 (х2 + х3 - 2),

дифференцируем ее по переменным j Х21 х3, , 7^2 и полученные выражения приравниваем нулю:

4- Х2 — О,

Х1 + х3 + + = О.

? Х2 + =

xl + х2 ~ 2 = О»

х2 + х3 - 2 = О.

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

Xj — 2Х2 + Хд = О, Х\ + х2 = 2, х2 + х3 = 2,

откуда xj* = х2 = х3 = 1 и Z0 = 2 . Поскольку, например, точка (0;2;0) принадлежит допустимой области и в ней Z = О, то делаем вывод, что точка (1;1;1) — точка глобального максимума. Л

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

найти max(min)Z = /(х1,х2,...,х„),

п

?aijXj (<,=,>}Ь4, і = 1,т;

і=і

Xj > О, j = 1, п.

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

Z - /(х1,х2,...,хл) = /і(л:і) + f2(x2)+...+fn(xn).

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

п п п

Z = f(xltx2,...,xn) = =

і=і І=іj=і

= Сі*! + c2x2+...+cnxn + dnxf + dl2xlx2+...+dlnxlxn+...+dnnx*.

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

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

min/?(*!,...,*„), (3.44)

gi(x1,x2,...,xn) <Ьиі = 1,т, (3.45)

Xj>0,j = hn. (3.46)

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

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

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

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

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

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

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

если система находится в некотором состоянии Sn є Sn, то дальнейшее развитие процесса зависит только от данного состояния и не зависит от того, каким путем система приведена в это состояние. •

Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления ип, под

воздействием которого система переходит из одного состояния Sn в другое Sn+1: Sn ^ S"*1. Поскольку процесс

марковский, то ип =un(Sn) зависит только от текущего состояния. •

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

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

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

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

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

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

fn (Sn) = max {ф „ (Sn ,un) + fn_x (Sn~l, u")j,

un eu"(S"), Sn zSn,

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

9„(Sn,un)— эффект от принятия решения ип; fn(Sn)— эффект за оставшиеся п шагов.

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

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

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

тах{фі(*і) + Фг^гН* • -+(?n(xN)}'

Xj > 0; у = UN,

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

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

fi(x) = max^ (*!)}, О < *!< х,

/„(*) = тах{фл(*л) + /л_і(х - *„)}, n = 2,N, О < *„< х.

L. Пример 3.9. Найти максимум функции

f(X) = 3xf - 4*2 + 3*f при ограничениях

4*! + 3*2 + 2*з < 8,

Xj > 0, Xj — целые; у = 1,2,3.

Решение. Целевая функция задачи f(X) является аддитивной, так как ее можно представить в виде суммы функций fj (Xj), каждая из которых зависит только от одной ПереМеННОЙ Xj'.

f(X) = /!(*!) + f2(x2) + /з(*з),

где f1(x1) = 3xf\ f2(x2) = -4*2; /з(*з) = 3*3.

Находим fi (А.) = max 3xf . Поскольку на переменные Xj накладываются условия целочисленности и неотрицательности,

(знак [ ] обозначает целую часть числа, т.е.

то 0 < х\ <

V

4

наибольшее целое число, не превосходящее данное); таким образом, є {0,1,2]. Для каждого фиксированного значения X вычисляем значение функции Д (А.) и выбираем среди

них максимальное, при этом в соответствии с ограничениями задачи X может принимать все целые значения от 0 до 8. Далее вычисляем:

f2(X) = max{-4*2 + Ш - 3*2)},

для всех 0 < х2 < — 3

/3(8) = тах|з*| + /2 (8 - 2*3)}

g

для всех 0 < *з < — 2

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

— &

Таким образом, max f(X) = max fc(X) = /3 (8) = 192. Оптимальную стратегию находим следующим образом. Сначала устанавливаем, что х? = 4 (соответствует максимальному значению 192). Значение х? = 0 находим из соответствующих граф табл. 3.14 для X = 8 - 2*д = 8 - 2 • 4 = 0 (f2(X) = /2(0) = О при х2 = 0). * * *

Далее находим значение хх = 0 для X = 8 - 2х3 - Зх2 =

= 8-2-4-3-0=0 (/і(Л.) = Д(0) = 0 при = 0). Таким образом, оптимальная стратегия имеет вид (0; 0; 4).

Таблица 3.14 X f\(X) f2(X) ш Х!=0 «1-1 Х!=2 х2=0 *2=1 *2=2 х3=0 *з=1 *з=2 *з=3 *з=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.

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