Упражнения 4.5,а

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

а) Максимизировать z = 4x₁ + 14х₂

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

b) Максимизировать z = 8x₁ + 7х₂

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

c) Максимизировать z = 7x₁² +6x₁ +5х₂²

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

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

4.6. Заключение

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

Литература

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

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

Dreyfus S., Law A. The Art and Theory of Dynamic Programming, Academic Press, N. Y., 1977.

Sniedovich M. Dynsmic Programming, Marcel Dekker, N. Y., 1991.

Комплексная задача

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

Год покупки	Стоимость покупки ($)	Стоимость содержания ($) для данного возраста (лет)			Стоимость продажи ($) для данного возраста (лет)
		0	1	2	1	2	3
1	10000	200	500	600	9000	7000	5000
2	12000	250	600	680	11000	9500	8000
3	13000	280	550	600	12000	11000	10000
4	13500	320	650	700	12000	11500	11000
5	13800	350	590	630	12000	11800	11200
6	14200	390	620	700	12500	12000	11200
7	14800	410	600	620	13500	12900	11900
8	15200	430	670	700	14000	13200	12000
9	15500	450	700	730	15500	14500	13800
10	16000	500	710	720	15800	15000	14500