Файл: Падалко Л.П. Математические методы оптимального планирования развития и эксплуатации энергосистем учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 04.07.2024

Просмотров: 129

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Г л а в а З

Д И Н А М И Ч Е С К О Е П Р О Г Р А М М И Р О В А Н И Е

Динамическое программирование

в отличие

от

ли­

нейного и нелинейного не выделяет

среди .всех з а д а ч ма­

тематического программирования

таких, которые

обла­

д а ю т определенной математической

записью,

а

дает

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

текающих во времени. Однако

область

его применения

не ограничивается з а д а ч а м и , в

которых

фигурирует

вре­

мя . Динамическое программирование оказывается

при­

менимым т а к ж е и к з а д а ч а м

статического типа, проце­

д у р а решения которых может

быть представлена

в ви­

де многошагового процесса.

 

 

 

В данной главе будут рассмотрены

вычислительный

метод динамического программирования, области приме ­

нимости

этого метода и типы задач, которые могут быть

решены с его помощью .

§ 3 . 1 . Математическая постановка задачи

Рассмотрим

следующую задачу:

 

п

 

min

V A M ;

 

 

1=1

 

^ д - .

= Л;

 

i=I

 

 

* z > 0 .

 

Эта

з а д а ч а

может интерпретироваться к а к з а д а ч а

такого оптимального распределения заданного однород­ ного ресурса м е ж д у различными видами работ, процес-

144

сов (i =

l , 2,

п), чтобы суммарные

з а т р а т ы

были ми­

нимальны . В экономике к такой

формулировке сводится

з а д а ч а

оптимального

распределения

заданного фонда

капитальных

в л о ж е н и й

імежду

различными

объектами .

П р и этом ставится требование либо минимизации после ­ дующих эксплуатационных расходов, либо максимиза ­ ции дохода-

Р и с . 3.1.

Н а первый взгляд кажется возможным использовать д л я решения приведенной математической модели аппа­

рат

классического математического анализа, в частно­

сти

метод неопределенных множителей

Л а г р а н ж а . Од­

нако

в реальных ситуациях такой подход не всегда мо­

ж е т

быть оправданным .

Это объясняется следующими

причинами:

 

 

1) обращение в нуль

производной

'Оптимизируемой

функции есть только необходимое, но недостаточное ус­ ловие минимума ( м а к с и м у м а ) . Например, д л я кривой, изображенной на рис. 3.1, производная равна н у л ю в

точках

Яі

и а% относительного

максимума,

Ъ\ и

Ь2

отно­

сительного

минимума и в точке с перегиба

функции. По ­

нятно,

если функция не удовлетворяет условию

выпук­

лости

(точка экстремума о д н а ) ,

то для нахождения аб­

солютного

м и н и м у м а необходимо

исследовать все

точки

экстремумов, что для многомерных з а д а ч связано

с

боль­

шими

трудностями;

 

 

 

 

 

2)

применение методов

математического

анализа

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

10 Л. П. П а д а л к о

145

Н а л и ч ие таких ограничении требует

проверки

решений

во всех граничных точках, что т а к ж е

связано с

больши­

ми вычислительными трудностями для з а д а ч многомер­ ного типа;

3) аппарат классического математического а н а л и з а приспособлен к решению з а д а ч оптимизации с непрерыв­

ным изменением независимых

переменных,

оптимизация

ж е по дискретным

переменным

находится

вне сферы его

досягаемости;

 

 

 

 

4) применение

классического анализа

 

предполагает

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

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

Нетрудно убедиться

т а к ж е в

том, что

методы

линей­

ного

н нелинейного программирования

т а к ж е не

всегда

могут быть попользованы для решения

сформулирован ­

ной

задачи (например, їв случаях

дискретности перемен­

ных,

отсутствия непрерывности

функции

п ее

первых

п р о и з в о д н ы х ) .

 

 

 

 

 

М о ж н о попытаться

использовать

прямой

перебор

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

силу огромного числа вариантов . В самом

деле,

если

считать,

что к а ж д о е из

-V,- может принимать

т

значений

от 0 до А,

то число

всех

вариантов решений при

п р я м о м

переборе

составит

N — т" (п — число

переменных) .

 

П р и

п. — 20 и

/ я = 1 0

будем иметь N=\Q20-

Д а ж е

если

ориентироваться

на

Э Ц В М , способную

в одну

миллисе­

кунду рассчитывать один вариант, то д л я перебора

всех

вариантов

потребуется

приблизительно

3-Ю3

лет.

Д л я

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

§ 3.2. Рекуррентные соотношения

Особенностью вычислительной схемы метода динами ­ ческого программирования является то, что одиовремен-

146

ная оптимизация п о всем переменным

Х \ ,

х%,

 

хп заме ­

няется

многошаговой

оптимизацией, причем в

п р е д е л а х

к а ж д о г о

ш а г а оптимизация осуществляется

по

одной

переменной. Сказанное вытекает из вида

рекуррентных

соотношений, которые мы сейчас приведем.

 

 

 

Пусть

л-„(0 < ; хп <; А)

—

количество

ресурсов,

назна ­

ченное

для

п-то процесса.

Тогда

количество

ресурсов

А — хп

будет

использовано

так, чтобы

минимизировать

затраты

на остающихся п—1 процессах. Обозначим

 

n—i

 

 

/!„_, (А — л-,,),

 

 

 

 

 

 

min

V

 

=

 

 

 

 

 

 

 

і

і

 

 

 

 

 

 

 

 

 

 

 

 

где

 

 

 

 

 

 

 

 

 

 

 

 

 

 

X-L

+

х2

+

... +

Хп-1

=

А —

хп.

 

 

 

 

 

С у м м а р н ы е з а т р а т ы

будут

р а в н ы

 

 

 

 

А„_, ( Л - * „ ) + /„(*„).

 

 

 

 

 

 

 

 

Ясно,

что

оптимальным

будет

такой

выбор

хп,

кото­

рый минимизирует эту функцию. В результате м ы полу­ чаем рекуррентное соотношение

hn(A) = min {«„_, (А - хп) + /„(*„)}.

Отметим, что смысл слова «рекуррентность» означа­ ет зависимость последующего от предыдущего . Если бы

вид функции

hn-i(A

—

хп),

выраженной только

через

одну переменную хп,

был известен, то з а д а ч а

свелась

бы

к оптимизации

функции

hn

по одной переменной

хп.

В

этом, собственно, и

з а к л ю ч а е т с я у к а з а н н а я

ранее

осо­

бенность динамического программирования, когда, распо­

л а г а я и н ф о р м а ц и е й

о виде

функции

л „ _ і , мы из

рекур ­

рентного соотношения 'можем определить функцию

hn,

при

этом

оптимизация н а

к а ж д о м

шаге

осуществляется

по одной

переменной.

 

 

 

 

 

§3.3. Вычислительная схема

 

 

 

 

 

Вычислительная

схема

динамического

программиро ­

вания сводится 'К получению последовательности

функ­

ций

hk{X)

для

k=\,

2,

п. И д е я метода

сводится

к

то­

му,

что, з н а я

hk—i, можно

легко т о

рекуррентному

соот­

ношению определить

hu:

 

 

 

 

 

Ю*

 

 

 

 

 

 

 

 

147

h„(X) =

min { A A _ , (X

- xk) +

.

Смысл

в ы р а ж е н и я

таков:

гори заданном количестве

ресурсов, равном X, распределяемом м е ж д у k процес­

сами, минимальные затраты

равны

hk(X).

 

 

 

Решение начинается с

k=l.

Т а к

к а к здесь

не требу­

ется

распределение,

то

решение

определяется

однознач­

но, а

именно:

 

 

 

 

 

 

 

 

 

 

 

h1(X)

=

f1(X).

 

 

 

 

 

 

 

 

 

 

Д а л е е в

соответствии

с рекуррентными

'соотношения­

ми будем иметь:

 

 

 

 

 

 

 

 

 

 

1и(Х)

=

min

{hx{X

 

х2)

+

/ 2 ( А - 2

) } ;

 

 

 

 

h3(X)

=

min

{h2(X

-

х 3 )

+

/ З ( А - 3

) } ;

 

 

 

 

ВД

=

min [hk^(X-x,)

 

 

+

/,(хА ,)};

 

 

 

кп(Х)

=

min {пп^(Х-хп)

 

+

 

fn(xn)}.

 

 

 

Величина

hn(A)

определяет

оптимальные

затраты .

 

Рассмотрим

вычислительную

процедуру

более

об­

стоятельно,

пояснив

одновременно,

как в пределах

к а ж ­

дого шага осуществляется оптимизация п о одной пере­

менной.

 

 

 

 

 

 

 

 

 

Пусть Х[ определяется множеством дискретных зна­

чений 0, 1, 2, 3,

А.

 

 

 

 

 

 

Первый

шаг.

Определяется множество значений функ­

ции

h\(xi)=fi(xi)

д л я всех

точек Х\=0, 1, 2, 3,

А.

З а ­

поминаются эти значения функции.

 

 

 

 

Второй

шаг.

Определяются из рекуррентного соотно­

шения значения

функции h2

(X).

Это осуществляется

сле­

д у ю щ и м

образом . Д л я к а ж д о г о значения

X из

интервала

О,

1, 2,

3,

А

определяется серия значений

h2(X)

при

всех

допустимых значениях

х2 из интервала 0,

1, 2,

3

А.

В

результате

получается следующая

последователь­

ность:

 

 

 

 

 

 

 

 

 

M X ) =

 

- 0) + Ш,

хй

= 0;

 

 

 

 

/l2 (X)

=

/ l 1 ( X - l ) + / 2 ( l ) ,

х 8

= 1;

 

 

 

148

Смотрите также файлы