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

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

Пример 10.4.1

Предприятие обрабатывающей промышленности выпускает два вида продукции. Производственный процесс составляет 430 минут в день. Для производства единицы продукции первого вида требуется 2 минуты, а второго - 1 минута. На дневной объем производства продукции первого вида ограничений нет (кроме возможностей производственного процесса), максимальный ежедневный спрос на второй вид продукции равен 230 единиц. Реализация единицы продукции первого вида приносит прибыль в 2 долл., а второго- 5 долл. Необходимо найти оптимальное решение задачи максимизации прибыли методами динамического программирования.

Данная задача является следующей задачей линейного программирования.

Максимизировать г = 2х1 + 5хг

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

2х, + х2<430, х2<230, х х2>0.

Элементы модели динамического программирования таковы.

1. Этап / соответствует продукции /, /=1,2.

2. Альтернативой х, на /-м этапе является объем производства продукции /,/=1,2.

3. Состояние (vb wx) представляет количество ресурсов, необходимое для производства продукции вида 1 и 2 (производственное время и ограничение на спрос) и используемое на этапах 1 и 2.

4. Состояние (v2, w2) представляет количество ресурсов, необходимое для производства продукции вида 1 и 2 (производственное время и ограничение на спрос) и используемое на этапе 2.

Этап 2. Пусть /2(v2, w2) представляет максимальную прибыль для этапа 2 (прибыль от выпуска продукции вида 2) при заданном состоянии (v2, w2). Тогда

/2(v2, w2)= max{5x2}.

Следовательно, max{5x2} имеет место при x2 = min{v2, w2). Имеем следующее решение для второго этапа.

Этап 1.

/i(vi,vvi)= 0max + У2(v, - 2jCj,w,)} = max {2jc, +5min(v,-2xvw,)}.

Оптимизация на первом этапе требует решения минимаксной задачи, что в общем случае является достаточно сложным делом. Для рассматриваемой задачи имеем у, = 430 и wt = 230, что дает 0 < 2х, < 430. Так как min(430 - 2xv 230) представляет собой нижнюю огибающую двух пересекающихся прямых (проверьте!), то

[230, 0<х<100,

min(430-2x 230)= \ 1

1 [430 - 2* 100<л-, <215

(2х. +1150, 0<х<100, /,(430,230)= тах{

J1K * \-8дг, +2150, 100<л-,<215.

Графически можно легко проверить, что функция/,(430, 230) достигает максималь-

Для определения оптимального значения х2 заметим, что

v2 = и, - 2х, = 430 - 200 = 230, w2 = w1 - 0 = 230.

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

х2 = min{v2, w2) = 230. Итак, оптимальное решение имеет вид: х, = 100 единиц, х2 = 230 единиц, г = 1350 долл.

УПРАЖНЕНИЯ 10.4

1. Решите следующие задачи линейного программирования методами динамического программирования.

a) Максимизировать г = 4х, + Ых2 при ограничениях

2х, + 7х2<21, 7х1 + 2х2<21, x *2>0.

b) Максимизировать z = 8х, + 1х2 при ограничениях

2х, + х2 < 8, 5х, + 2х2<15, jc х2 > 0 и целые.

с) Максимизировать г = 7 х\ + 6х, + 5 х; при ограничениях

х, + 2х2 < 10, х,-3х2<9, х х2>0.

2. Пусть в задаче из примера 10.3.1 о загрузке предметов п наименований ограничения самолета по весу и объему представлены величинами W и V соответственно. Величины wh Vj и г, представляют соответственно вес, объем и прибыль, отнесенные к одному предмету наименования г. Необходимо записать рекуррентное уравнение обратной прогонки для алгоритма динамического программирования решения сформулированной задачи.

ЛИТЕРАТУРА

1. Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N.J., 1987.

2. Denardo E. Dynamic Programming Theory and Application, Prentice Hall, Upper Saddle River, N.J., 1982.

3. Dreyfus S., Law A. The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.

4. Sniedovich M. Dynamic Programming, Marcel Dekker, New York, 1991.

Литература, добавленная при переводе

1. Беллман Р. Динамическое программирование. - М.: ИЛ, 1960.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.: Наука, 1965.

3. Вентцель Е. С. Исследование операций. - М.: Сов. радио, 1972.

4. Романовский И. В. Алгоритмы решения экстремальных задач. - М.: Наука, 1977.

КОМПЛЕКСНАЯ ЗАДАЧА

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