Пример 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. Что такое принцип оптимальности и как записываются уравнения Беллмана?