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

А п п а р а т динамического

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

к решению з а д а ч

аз случае

'непрерывного

изменения пе­

ременных. П р а в д а ,

решение

оказывается

п р и б л и ж е н н ы м

жет быть

достигнута л ю б а я

требуемая

точность

путем

дискретизации переменных со

все 'более

мелким

шагом..

К а к и м

требованиям д о л ж н а удовлетворять

задача,,

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

п р о г р а м м и р о в а н и я ?

И з

вида

целевой

функции можно

сделать вывод, что

она

д о л ж н а

у д о в л е ­

ее їв виде

суммы

функций, к а ж д а я из

которых в ы р а

ж а ­

ется через

одну

переменную . О д н а к о

это требование

не­

Рекуррентное

соотношение д л я

заданной

задачи з а п и ­

сывается так:

hn(X) = min

( / ! n - i ( ^ - a » W l .

где

л— 1

/і„_і(Х — Хп) =

ГЛІП П / / Л - ; ) .

1=1

Н и ж е будет

показан пример задачи

мультипликативного-

вида.

Главное

требование к з а д а ч е

—

условие

выполнимо ­

ного состояния, от результата решения

н а п р е д ы д у щ е м

шаге, относительно которого ищется

решение з а д а ч и

шагах, начиная от начального . Иначе говоря,

пусть на

первые

/г процессов отпущено В ресурсов, тогда

опти­

мальное

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

оставшихся

ресурсов

А—В

на

п—k

процессах не д о л ж н о

зависеть

от того, к а к

В ресур ­

сов

распределены м е ж д у

k

процессами, а будет

зависеть

ределяет т а к ж е и высокую эффективность

метода.

Следует заметить, что д л я выполнимости

этого требо ­

в а н и я весьма часто приходится многошаговый

процесс

решения осуществлять не с начального момента

протека ­

орбиту

в

качестве отправной

точки,

с которой

развора ­

чивается

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

процесс, принимается

конечная

точка в ы в о д а ракеты на

орбиту.

Если з а д а ч а удовлетворяет

указанным выше

требова­

ниям,

то

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

программирование гарантирует

достижение абсолютного

минимума

( м а к с и м у м а ) .

В заключение следует

обратить внимание н а

достоин­

су. В с а м о м деле, как

видно из табл . 3.1, в результате

по­

следнего шага получается

серия оптимальных

решений

Л„. Вполне возможно,

что

некоторые из

этих

решений

равны и л и ж е весьма

близки п о величине затрат, хотя

их

структура, т. е. распределение ресурсов м е ж д у процесса­

ми, разная . Н а л и ч и е равноценных оптимальных

решений

позволяет в ы б р а т ь среди них то, .которое

в большей сте­

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

за­

дачи, не нашедшим по тем

или иным причинам

отраже ­

сти, то в выбранном решении можно

учесть т а к и е требо­

вания, к а к надежность,

удобство

эксплуатации .

§ 3.6. Многомерные задачи динамического

программирования

Р а с с м о т р е н н а я

нами

з а д а ч а относилась

к классу

од­

номерных

задач,

т а к к а к требовалось

найти

распределе­

ние одного вида

ресурсов. З а д а ч и , в

которых требуется

распределить несколько

видов

ресурсов,

относятся

к

классу

многомерных.

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

изложенного

стандартного решения

применительно к

многомерным

з а д а ч а м возникают

значительные

вычислительные труд ­

» = 1

і = і

З д е с ь

xt

и

yt —

'количество ресурсов двух

видов, вы­

деляемых д л я

і-го

процесса.

Отметим, что

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

соотношения

Б е л л м а н а

д л я случая

одномерных з а д а ч полностью переносятся на

многомерные задачи . Д л я

нашей

з а д а ч и

они

будут

иметь

в и д

hn(X,

У) min

min [hn^(X-xn,

Y-yn)

+

fn{xn,yn)}.

Д а н н а я

з а д а ч а

снова

может

р а с с м а т р и в а т ь с я

к а к

я - шаговый процесс принятия решений, но теперь на

к а ж ­

дом ш а г е

необходимо в ы б и р а т ь значения

и xh

и yt.

Од ­

нако

при

применении изложенного

р а н е е стандартного

метода к решению многомерной з а д а ч и в о з н и к а ю т

зна­

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

трудности.

П р е д п о л о ж и м , что переменные

xt

и у1

могут прини­

мать

по

100 дискретных

значений.

Т а к

к а к

функцию

hk(X,

У)

необходимо запоминать

на

k-м

шаге д л я

всех

в о з м о ж н ы х 'комбинаций X и У, то возникает

необходи­

мость в вычислении и 'запоминании

10 ООО значений функ­

ции. Таким

о б р а з о м , объем вычислений возрастает

в 100

еще в ы ш е , т а к

к а к д л я определения к а ж д о г о из 10 000

значений hk(X,

У) с целью выбора оптимального необхо­

10 000 комбинаций значений xk

и

ук.

Помимо увеличения о б ъ е м а

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

еще и

д р у г а я трудность, вызванная необходимостью

запомина ­

ния

громадного числа

значений

функции hk{X,

У)

в

па­

мяти

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

машины .

Если учесть;

что

объем

оперативной п а м я т и существующих

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

ма-

шин не превосходит нескольких тысяч

ячеек, то д а ж е д л я

запоминания

одной таблицы

значений

hk(X,

Y)

может

потребоваться

обращение

к

внешней

п а м я т и машины .

Это существенно сокращает скорость вычислений.

Е щ е в большей степени

возрастает

объем

вычислений

для трехмерных задач . Число функций

hk(X,

Y,

Z),

необ­

ходимых

для

запоминания

на к а ж д о м

шаге,

составит

у ж е

1003

= 106 . Объем вычислений увеличивается

не

ме­

нее

чем в

10 000 іраз. Если

двумерные

задачи

могут

быть

ные т а к ж е иногда

могут быть решены за счет

укрупне­

ния шага дискретизации, то четырехмерные

и в ы ш е за ­

дачи превосходят

возможности

современных

вычисли­

тельных

машин . Д л я решения

таких з а д а ч

необходимо

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

других

математических

методов

или ж е

специальных

приемов,

позволяющих

зируемых

(вариантов.

§ 3.7.

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

множителей

Л а г р а н ж а

д л я понижения размерности

Н и ж е

мы

п о к а ж е м ,

что использование

множителей

Л а г р а н ж а

позволяет

понизить размерность

задачи .

Предположим,

что

переменные

Х[ непрерывны и что

функции

/,-(-V()

выпуклы . Тогда рассмотрим

следующую

задачу:

minify

fa,

yi)-xfy\;

U = l

(=1

J

x i

+ x 2

+

••• +xn

=

A;

Уі>0.

К а к видно,

на

y-t

ограничения сверху не н а к л а д ы в а ю т с я .

Ц е л е в а я

функция

может быть

представлена т а к ж е ©

следующем

виде:

п

Г Ш " 2

[/;(*/>

Уй

—

Ьу,].

/=1

две переменных —

X; и t/j.

Д л я

того чтобы

'избавиться

от двумерности, в в о д а м новую функцию:

У;>0.

Тогда з а д а ч а

при

фиксированном

К будет

сводиться к

следующей:

п

У,х(=А,

х , > 0 .

/=1

Д а н н а я з а д а ч а

является

одномерной, и

ее решение

hk(X)

=

min

-

хк)

+

gk(xk)}.

Таким образом, д л я

решения

необходимо

знание

функций g;(x() и

hi(X

— х(-). Функции

gs

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

следующим

образом .

З а д а е м с я

допустимым

значением

х(. из интервала

0, 1, 2,

X. Д л я

данного

х1

определя ­

ем минимальное

значение функции

f^xl%

у,)

—

%yt

при

всех допустимых

значениях

yt

из

интервала

0,

1,

2,

У. Если

число значений

хг

и yt

по

100, то потребуется

ко

100 значений функции g/x.)

(для

всего

и н т е р в а л а

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

Таким образом,

при

заданном фиксированном значе­

нии

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

п

функций

gi(Xi),

после

чего опти­

мизация осуществляется обычным

методом динамическо­

го программирования д л я случая

одномерной

задачи .

Однако полученное решение еще не

будет

оконча­

тельным, т а к к а к значения переменных

х-р yt будут оп­

этому

по окончании расчета необходимо проверить

ус-

ловие

п

Если это условие д л я рассчитанных

yt

У1УІ=В-

i = i

вновь повторить

решение. Корректировка коэффициента

Я, п р о д о л ж а е т с я

до тех пор, п о к а не будет выполнено