Компания по прокату автомобилей разрабатывает план по обновлению парка своих машин на следующие пять лет. Каждый автомобиль должен проработать не менее 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. Что такое принцип оптимальности и как записываются уравнения Беллмана?
