Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

§ 4. Модификация метода для случая непрерывности переменных, выпуклости или вогнутости функции цели

Вычислительный метод динамического программирования может быть применен также при решении задач с непрерывными переменными xj. Посмотрим, к чему приведет отбрасывание требования целочисленности xj, aj и b в задаче (3.1).

Формально ничто не мешает начать решение этой задачи точно так же, как и в случае целочисленных переменных. Ври этом, как показано выше, следует определить последовательность функций Fk (ξ) (3.11). Теперь, однако, xk меняется до ξ/ak, а не до [ξ/ak] и, вообще говоря, может принимать любые значения в интервале 0≤xk≤b/ak. По-скольку в любом таком интервале содержится бесконечное Множество чисел, то, как правило, функцию Fk (ξ) можно найти только приближенно. Выше (гл. II, §5) мы уже Встречались с методом приближенного определения макси-шума непрерывной функции. Этот метод можно применять и в данном случае.

Рассмотрим задачу определения Fk (ξ) при фиксированном ξ:


где


и считается, что Fk-1 (ξ) уже определена ранее. Функция Ωk (xk, ξ) также определена для всех xk из интервала 0≤xk≤b/ak, и ее можно, например, изобразить в виде некоторой кривой аналогично тому, как это сделано на рис. 2.4. Для того чтобы определить значение k (ξ), при котором Ωk (xk, ξ) достигает своего максимального значения, необходимо найти все относительные максимумы Ωk и затем Убрать значения xk, при которых Ωk имеет абсолютный Максимум. Поскольку в отличие от случая, рассмотренного в гл. II, § 5, мы имеем здесь задачу только с одним переменным xk, для приближенного определения максимума можно воспользоваться так называемым методом сеток, т. е. вычислять значения Ωk при фиксированных и равноотстоящих значениях xk из интервала 0≤xk≤b/ak. Повторяя процесс уменьшения шага сетки необходимое число раз в случае непрерывной функции Ωk, всегда можно получить желаемую точность определения k (ξ) и Fk (ξ). Конечно, при этом объем вычислений будет значительным. Поэтому в отличие от других методов вычислительный метод динамического программирования более подходит для задач с целочисленными (дискретными) переменными.

Процесс определения k и Fk (ξ) может быть существенно упрощен, если fj (xj) являются выпуклыми или вогнутыми функциями. Сначала рассмотрим случай, когда fj (xj) являются выпуклыми функциями (определение выпуклости и вогнутости функций см. гл. II, § 3). Покажем,что при этом Fk (ξ) также являются выпуклыми функциями ξ.

Прежде всего покажем, что если f1 (x1) является выпуклой функцией, то и F1 (ξ) также является выпуклой функцией. Напомним, что для этого мы должны показать справедливость неравенства


где λ - некоторое число (0≤λ≤1) и использовано представление ξ = λξ1 + (1 - λ)ξ2. Для простоты записи предположим, что все aj = 1. Тогда можем написать:


Разобьем x1 также на два слагаемых следующим образом:

x1 = λx'1 + (1 - λ)x"1,

где λ - то же самое число, которое использовано в представлении ξ. Тогда при отыскании максимума изменение x1 между 0 и λξ1 + (1 - λ)ξ2 можно производить путем независимого изменения x'1 и x"1 соответственно в пределах 0≤x"1≤ξ1 и 0≤x"1≤ξ2 Поэтому выражение (3.17) можно переписать в виде


(3.18)

Однако вследствие выпуклости функции f1 (x1) мы имеем право написать:


(3.19)

Если теперь в (3.19) обозначить


то в силу (3.18) можем переписать (3.19) в виде неравенства


(3.20)

что и требовалось доказать. Следовательно, F1 (ξ) также является выпуклой функцией.

Допустим теперь, что, проводя аналогичные рассуждения, доказали выпуклость функции Fk-1 (ξ). Докажем, что Fk(ξ) (3.11) также выпуклая функция.

Действительно, так как Fk-1 (ξ) - выпуклая функция по предположению при любом ξ, то Fk-1 (ξ-akxk) также выпуклая функция от xk и ξ. Функция fk(xk) - выпуклая по определению. Таким образом,


есть также выпуклая функция от xk и ξ. Поступая так же как при доказательстве выпуклости F1 (ξ), запишем:


(3.21)

Из выпуклости Ωk (xk, ξ) следует:


(3.22)

Опять поступая аналогично тому, как при получении неравенства (3.20), и учитывая (3.21), перепишем (3.22) в виде


(3.23)

откуда следует выпуклость Fk (ξ). Таким образом, можно утверждать, что из выпуклости функций fj (xj) следует выпуклость всех функций Fk (ξ).

Аналогично можно показать, что из вогнутости функций fj (xj) следует вогнутость всех функций Fk (ξ).

После того как мы убедились, что при наличии выпуклости fj (xj) все функции Ωk (xk, ξ) также являются выпуклыми, можно воспользоваться доказанным в § 3 гл. II свойством выпуклых функций и утверждать, что максимум функций Ωk (xk, ξ) на интервале 0≤xk≤ξ (ξ - заданное число) достигается в одной из крайних точек этого интервала, т. е.


Ясно, что это приводит к существенному упрощению процесса определения k (ξ) и Fk (ξ), о котором говорилось выше, поскольку необходимо только выбрать наибольшую из этих двух величин. При этом, однако, может случиться, что при xk = 0 и xk = 1 максимумы совпадают. Если Ωk не зависит от xk, то максимум достигается в любой внутренней точке интервала 0≤xk≤ξ.

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

предыдущая главасодержаниеследующая глава



ИНТЕРЕСНО:

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru