Пример 3

Компания по прокату автомобилей разрабатывает план по обновлению парка своих машин на следующие пять лет. Каждый автомобиль должен проработать не менее 2-х и не более 4-х лет. В следующей таблице приведена стоимость замены автомобиля в зависимости от года покупки и срока эксплуатации.

	Стоимость замены в зависимости от срока эксплуатации
Год покупки
			-
		-	-

Решение

Сведем задачу к задаче нахождения кратчайшего пути в сети:

 

Получаем кратчайший путь 2000→2002→2005.

К наименьшим затратам приведет замена автомобиля в 2002 и 2005 годах.

 

 

Тесты

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

а) отсутствие последействия;

б) наличие обратной связи;

в) управление зависит от бесконечного числа переменных.

2. Вычислительная схема метода динамического программирования:

а) зависит от способов задания функций;

б) зависит от способов задания ограничений;

в) связана с принципом оптимальности Беллмана.

3. Какую задачу можно решить методом динамического программирования:

а) транспортную задачу;

б) задачу о замене оборудования;

в) принятия решения в конфликтной ситуации.

4. Что из себя представляет динамическое программирование?

а) особый метод оптимизации решений, специально приспособленный к так называемым “одношаговым” (или “одноэтапным”) операциям;

б) особый метод оптимизации решений, специально приспособленный к так называемым “многошаговым” (или “многоэтапным”) операциям;

в) особый метод оптимизации состава предприятия;

г) особый метод оптимизации решений, специально приспособленный к задачам линейного программирования;

д) все вышеперечисленное.

5. Что предполагает принцип динамического программирования?

а) что каждый шаг оптимизируется отдельно, независимо от других;

б) шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем;

в) выбор на данном шаге управления, при котором эффективность этого шага максимальна;

г) выбор на данном шаге управления, при котором эффективность этого шага минимальна;

д) все вышеперечисленное.

6. К какой задаче относится задача распределение средств по предприятиям и по годам?

а) задачи линейного программирования;

б) задачи целочисленного программирования;

в) задачи нелинейного программирования;

г) задачи стохастического программирования;

д) задачи динамического программирования.

7. К какой задаче относится задача прокладки наивыгоднейшего пути между двумя пунктами?

а) задачи линейного программирования;

б) задачи целочисленного программирования;

в) задачи нелинейного программирования;

г) задачи стохастического программирования;

д) задачи динамического программирования.

8. Каким методом лучше всего решить экономическую задачу о распределении ресурсов?

а) методом линейного программирования;

б) методом динамического программирования;

в) методом целочисленного программирования;

г) методом нелинейного программирования;

д) методом стохастического программирования.

9. В чем метод динамического программирования отличается от метода линейного программирования?

а) не сводится к какой-либо стандартной вычислительной процедуре;

б) оно может быть передано на машину только после того, как записаны соответствующие формулы, а это часто бывает не так-то легко;

в) сводится к какой-либо стандартной вычислительной процедуре;

г) содержание п. а и б;

д) содержание п. а, б и в.

10. Что необходимо делать, когда планировать операцию приходится не на строго определенный, а на неопределенно долгий промежуток времени?

а) необходимо рассмотреть в качестве модели явления бесконечношаговый управляемый процесс, где не существует “особенного” по сравнению с другими последнего шага (все шаги равноправны);

б) для этого, разумеется, нужно, чтобы функции выигрыша и функции изменения состояния не зависели от номера шага;

в) необходимо рассмотреть в качестве модели явления одношаговый управляемый процесс;

г) необходимо рассмотреть в качестве модели явления бесконечношаговый неуправляемый процесс;

д) содержание п.а и б.

Ответы к тестам

1) а	6) д
2) в	7) д
3) б	8) а
4) б	9) г
5) в	10) д

Контрольные вопросы

1. Как поставить общую задачу динамического программирования?

2. Как формулируется задача динамического программирования и в чем ее отличие от задач линейного программирования?

3. В чем заключается особенности математической модели ДП?

4. Что лежит в основе метода ДП?

5. Сформулируйте задачу определения кратчайших расстояний по заданной сети. На сколько этапов разбивается задача? Сколько шагов содержится в каждом этапе и в чем суть этапа и шага?

6. Что является переменной управления и переменной состояния в задаче выбора оптимальной стратегии обновления оборудования?

7. Запишите функциональные уравнения Беллмана, используемые на каждом шаге управления в задаче выбора оптимальной стратегии обновления оборудования.

8. Запишите математическую модель оптимального распределения инвестиций и рекуррентное соотношение Беллмана для ее реализации.

9. Что такое принцип оптимальности и как записываются уравнения Беллмана?