Динамическое программирование

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

Федеральное государственное образовательное учреждение высшего  
профессионального образования

«Уральский государственный университет путей сообщения»

(УрГУПС)

 

 

Кафедра «Высшей и прикладной математики»

 

КОНТРОЛЬНАЯ РАБОТА

«Динамическое программирование»

Вариант №10

 

 

 

Проверил:	Разработал:
преподаватель	студент группы Лэ-410
Пирогова Ирина Николаевна	Тушков Иван

 

 

 

 

 

Екатеринбург

2014

В определённый момент времени на предприятии, планирующем свою работу на ближайшие 5 лет,  установлено новое оборудование. Зависимости производительности r(t), затрат u(t) на содержание и ремонт оборудования и остаточной стоимости s(t) при различном времени его использования приведены в таблице. Затраты Р на приобретение и установку нового оборудования составляют 12 у.е.

Таблица 1

Условия задачи

	Время t, в течение которого используется оборудование (лет)
	0	1	2	3	4	5
Годовой выпуск продукции r(t) в стоимостном выражении (у.е.)	40	39	38	36	35	32
Ежегодные затраты u(t), связанные с содержанием и ремонтом оборудования (у.е.)	8	8	7	7,2	7,8	9
Остаточная стоимость s(t) при различном времени  использования (у.е.).	-	6	5	4,5	4,3	4

Составить план замены оборудования, при котором  общая прибыль за данный период времени была бы максимальна.

Решение

Поиск оптимального решения включает 5 этапов (по числу запланированных лет работы). Движемся от начала 5 года к началу первого.

Условная оптимизация:

  5 этап. Вычислим максимальный доход за последний год работы предприятия. Для каждого допустимого состояния оборудования найдём условное оптимальное решение. Согласно условию задачи, предприятие начинает свою работу на новом оборудовании, поэтому к началу пятого года его возраст  может составлять 1, 2, 3 или 4 года. Заменяемое оборудование продается, остаточная стоимость s(t) в зависимости от количества лет эксплуатации приведена в таблице 1.

Рекуррентные соотношения с учётом продажи бывшего в эксплуатации механизма имеют вид:

, следовательно:

;

;

;

.

Все полученные данные запишем в виде вспомогательной таблицы.

Таблица 2

Условно оптимальные решения 4 этапа

возраст механизма  t (лет)	максимальный доход за последний год F1(t) (тыс. долл.)	условно оптимальное решение
1 2 3 4	36 35,5 33,1 31,2	С С С С

 

4 этап. Вычислим максимальный доход за последние два года работы предприятия. К началу четвёртого года допустимыми состояниями являются t = 1, 2 или 3 года.  Для каждого из них определяем условно оптимальное решение и соответствующее значение F2(t). Рекуррентные уравнения Беллмана имеют вид:

, значения F1 (t) берём из таблицы 2, получим:

;

;

.

Все полученные данные 3 этапа занесём в таблицу 3.

Таблица 3

Условно оптимальные решения 3 этапа

возраст механизма  t (лет)	максимальный доход за последние 2 года F2(t) (тыс. долл.)	условно оптимальное решение
1 2 3	66,5 64,1 60,5	С С З

 

3 этап. Вычислим максимальный доход за последние три года работы предприятия. К началу третьего года допустимыми  состояниями будут t = 1 и

t = 2. Для каждого из них определяем условно оптимальное решение и соответствующее значение F3(t). Рекуррентные уравнения Беллмана имеют вид:

, значения F3 (t) берём из таблицы 3, получим:

;

.

Если прибыль от нового оборудования равна прибыли от старого, что в нашем конкретном случае и произошло, то старое лучше сохранить ещё на год.

Максимальную прибыль за последние три года работы компании и условно оптимальные решения запишем таблично.

Таблица 4

Условно оптимальные решения 2 этапа

возраст механизма  t (лет)	значения функции F3(t) (тыс. долл.)	условно оптимальное решение
1 2	95,1 91,5	С С

 

2 этап. Вычислим максимальный доход за последние четыре года работы предприятия. К началу второго года допустимым  состоянием будет лишь t = 1. Для этого состояния определим условно оптимальное решение и соответствующее значение F4(t). Рекуррентные уравнения Беллмана имеют вид:

 значения F3 (t) берём из таблицы 4, получим:

.

Данные 2 этапа запишем таблично.

Таблица 5

Условно оптимальные решения 2 этапа

возраст механизма  t (лет)	значения функции F3(t) (тыс. долл.)	условно оптимальное решение
1	122.5	С

1 этап. Начало первого года работы предприятия. Вычислим максимальную прибыль за пять лет. Согласно условию, в начальный момент установлено новое оборудование (t = 0), поэтому проблемы выбора между его сохранением и заменой не существует: оборудование надо сохранять. Поэтому Рекуррентные уравнения Беллмана примут вид:

, следовательно:

,

.

Таким образом, максимальная прибыль предприятия за 5 лет работы может составить 142,5 у. е. Определим политику замены оборудования.

Безусловная оптимизация:

Поднимаемся снизу вверх. Для первого года работы  решение – сохранить, тогда к началу второго года возраст оборудования составит 1 год, следовательно, по таблице 5 находим условно-оптимальное решение для t = 1 – сохранить. К началу третьего года возраст оборудования составит  два года, по таблице 4 находим условно-оптимальное решение для t = 2 – сохранить или заменить. Допустим – сохранить, тогда к началу четвёртого года наработка оборудования составит 3 года, и согласно таблице 3 для t = 3 принимаем решение – заменить. Таким образом, к началу последнего – пятого года возраст оборудования составит 1 год, а согласно таблице 2 для t = 1 принимаем решение о сохранении оборудования.

Итак, оптимальной стратегией управления, т.е. такой совокупности управлений , при которой предприятие получит максимальную прибыль F = 142,5 у. е., является следующая политика замены оборудования: ,

Ответ. Для получения максимальной прибыли в размере 142,5 у. е. оборудование необходимо заменить на четвёртом году работы.