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

h2(X)

=

h±(X

—

2) +

/2 (2),

хй

=

2;

h0_(X)

=

Лх (1) +

f2(X

-

1),

хг

=

X -

1;

/і2 (Х) =

Лх (0) +

/ 2 (Х),

* а

=

X .

Сопоставляя все приведенные выше значения

h2(X),

выбираем

и запоминаем

наименьшее

из

них.

Все

ос­

тальные

значения

л а м

больше

не 'понадобятся. З а м е т и м ,

что т р и

определении

1г2(Х)

мы вычисляем только значе­

ния /2(^2), в то

в р е м я

« а к

значения 1г{(Х—х2)

у ж е были

определены на предыдущем шаге и хранятся

в п а м я т и

машины .

П р и д а в а я X (все допустимые

значения

от

1 до Л,

мы

указанным

в ы ш е методом

определяем

серию

оптималь ­

ных значений функции /і2(Х).

В

ходе этого процесса

оп­

ределяются

т а к ж е

и

соответствующие

оптимальные

зна­

чения х2

д л я к а ж д о г о

X.

Третий

шаг.

Функция

h3(X)

получается

аналогично.

Н а последнем

шаге

имеем

следующее

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

соотношение:

К{Х)

= min {n„_,(X -

хп) +

/„(*„)}.

Вычисления на последнем шаге существенно сокра ­

щаются,

т а к к а к значение

Х=А

з а д а н о в

условии з а д а ­

чи, и им

в а р ь и р о в а т ь

не надо .

Варьируя

различными

значениями

хп

от 0 до А,

мы выбираем то значение, д л я

которого

функция hn(A) приобретает

минимальное

зна ­

чение. Таким образом,

оптимальное значение

функции

найдено.

Результаты

расчета

н а

основе указанной

многошаго­

цы (см. табл . 3.1). Все цифры

этой таблицы, определен­

ные в многошаговом процессе,

хранятся їв п а м я т и

вычи­

слительной машины .

После н а х о ж д е н и я минимального

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

следует в ы б р а т ь из т а б л и ц ы значения

переменных

хи

х2,

хп, доставляющих оптимум

задаче . Методику

их

вы­

бора проиллюстрируем на т а б л . 3.1. Оптимальное

значе­

ние х„ нам известно из последнего шага .

Следовательно,

на оставшихся процессах будет израсходовано А—хп

ре­

сурсов. И щ е м в третьем столбце с конца

соответствую-

Таблица 3.1

X

X,

Л'2

7

><

7

•«Г

0

1

2

3

А'

щее значение

функции hn-\{A—

х„). Слава, из соседнего

столбца той ж е строки, извлекаем

'Оптимальное значение

переменной

хп—\.

Следовательно,

на п—2 процессах бу­

дет

израсходовано

А—хп—хп—\

ресурсов. И щ е м значе­

ние

функции

h„—2{A — ,v„ — л ' „ _ 0 и

соответствующее

значение переменной л'„_о . Такой

«ход

назад» осуществ­

найдены. Следовательно, з а д а ч а

решена.

§ 3.4. Случай непрерывности переменных

Рассмотрим обобщение метода для с л у ч а я

непрерыв­

ности

переменных

Xj. Если

мы

н е будем

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

дискретизацию

переменных,

то,

очевидно,

необходима

иная

процедура

формирования

значений ht(X),

чем это

было

раньше .

Если в и д к а ж д о й функции

задан -

аналитиче­

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

не будет

с в я з а н

с

какими-

либо

вычислениями

д л я hi (X).

Второй

шаг

д о л ж е н сво­

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

функции

h2(X) = min [Ъ(Х — х2) +

f2(x2)}.

Н е вдаваясь в

детали

методики определения

этой функ­

ции, отметим,

что она

д о л ж н а

быть з а д а н а в

интервале

h3(X)

=

min {Л2 (Х -

х 3 ) + /з(л-3 )},

т а к ж е

заданной на указанном интервале .

Функция

hn{X),

'полученная в

конце

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

процесса, сразу дает оптимальную величину

з а т р а т

п р и

Х—А.

Теперь

следует

определить

структуру

з а т р а т

по

процессам и соответствующие значения переменных

х[ш

П р и аналитическом в и д е .функций процедура

р е ш е н и я

выглядит

несколько иначе, чем п р и табличном

задании .

В н а ч а л е определяется переменная

хп. С

этой

целью

об­

р а щ а е м с я

к рекуррентному соотношению

hn(A)

=

min [hn-i(A

-

*„) +

/,,(х„)].

Т а к

как аналитический в и д функций

п,г _і(Х) и

fn(xn)

нам известен,

то,

п о д с т а в л я я

найденное

численное

зна­

чение

hn(A),

мы

получаем уравнение с

одним

неизвест­

ным хп. Р е ш и в это уравнение, находим

хп.

Д а л е е

о б р а щ а е м с я к следующему рекуррентному

со­

отношению

/г„_і(А — х„) =

min {/г„_2(Л — хп — x„_i) +

fn-\(xn-i)}

•

З д е с ь в и д

функций

/г,,_2 и

/„ _ i

известен. Значение хп

мы определили раньше . Известно

т а к ж е

численное

зна­

чение

функции

hn— \{А — х„), р а в н о е

hn(A)

—

f„(xn).

В

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

одним

неизвест­

ным, решив которое, находим

x„_i.

dxn

<КА-х„)

П р а в д а , такой

подход, т а к ж е к а к и предыдущий,

Д(х(-). В противном

случае

необходимо

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

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

функции h и

f з а д а в а т ь в

§ 3.5. Эффективность динамического

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

Эффективность

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

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

Из

принципа оптимальности вытекает,

что

решение

на последующем

шаге р а с с м а т р и в а е т с я только относи­

тельно

результата

решения, достигнутого

на

предыду ­

шагов не имеют

значения.

Оценим эффективность метода д л я случая, рассмот­

ренного ранее,

когда п = 20 и / п = 1 0 . М о ж н о подсчитать,

hp<),

составит

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

Если

предполо ­

жить, что одна

'операция

выполняется

со

скоростью

сек,

то в р е м я ,

необходимое для решения

задачи ме-

103

тодом

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

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

составит

1,25 сек.

Отметим,

что время,

затрачиваемое

н а

решение

задачи,

находится

в прямой

пропорциональной

зависи­

мости

от числа шагов

многошагового процесса. В част­

ности,

для / г = 4 0

и т =

1 0 оно

составит всего 2,5 сек. От­

сюда

ясно,' что

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

п р о г р а м м и р о в а н и е пред­

К а к о в ы

ж е достоинства и границы

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

намического

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

Р а н е е

были

перечисле­

ны особенности реальных задач,

которые

делают

невоз­

м о ж н ы м использование классического

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

анализа для их решения . Рассмотренный

нами

метод

преодолевает ївсе препятствия, о

которых

мы

говорили.

чи с функциями

любого

вида. В и д

функции

(вы­

пуклость, вогнутость,

наличие

нескольких

экстремумов)

не вызывает затруднений.

Дополнительные условия в форме ограничений на пе­

ременные не усложняют, а, напротив, у п р о щ а ю т

реше­

ние задачи, т а к как

с о к р а щ а е т с я число

анализируемых

вариантов.