Тема 6. Использование методов динамического программирования в задачах оптимизации
Общая постановка задачи динамического программирования. Интерпретация управления в фазовом пространстве. Принцип оптимальности Беллмана. Различные формулировки принципа оптимальности. Задача о наборе высоты и скорости летательным аппаратом. Задача
о распределении ресурсов. Рекуррентное соотношение Беллмана. Решение задачи динамического программирования с учетом предыстории процесса. Задачи динамического программирования, не связанные со временем. Задачи динамического программирования с мультипликативным критерием.
Тема 7. Прямые методы отыскания экстремума функции одной переменной
Понятие прямых методов поиска экстремума. Понятие унимодальной функции. Пассивный или параллельный поиск экстремума. Оптимальная стратегия пассивного поиска экстремума. Эффективность пассивного поиска. Последовательный или активный поиск экстремума. Стратегии поиска экстремума методом дихотомии, Фибоначчи и золотого сечения. Сравнительная эффективность данных методов. Эквивалентность задачи нахождения экстремумов функции и задачи нахождения нулей функции. Метод Ньютона и метод секущих в задаче нахождения нулей функции.
Тема 8. Численные методы поиска экстремума функции многих переменных
Понятие многомерного поиска экстремума. Метод наискорейшего спуска поиска экстремума. Метод покоординатного спуска. Овражный метод поиска экстремума. Метод поиска экстремума в условиях помех. Метод Ньютона в задаче нахождения нулей функции многих переменных.
Тема 9. Задачи линейного программирования в задачах оптимизации
Классическая задача линейного программирования. Примеры задач линейного программирования. Транспортная задача. Задача о рациональном питании. Задача о загрузке транспорта. Геометрическая интерпретация задачи линейного программирования. Задача линейного программирования с ограничениями-неравенствами и сведение ее к классической задаче линейного программирования. Прямая и двойственная задача линейного программирования.
Тема 10. Методы решения задач линейного программирования
Простейший метод решения задачи линейного программирования в случае небольшого числа переменных. Симплекс-метод решения задачи линейного программирования. Понятие свободной и базисной переменной. Табличный алгоритм замены базисных переменных. Отыскание опорного решения задачи линейного программирования. Отыскание оптимального решения задачи линейного программирования.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Тема 10. Поиск наилучших решений методами динамического программирования Лекция 10. Поиск наилучших решений методами динамического программирования
При поиске наилучших решений в оптимизационных задачах методами классического математического анализа предполагается следующее:
1. Этот анализ предназначен для непрерывных функций (переменных) и их производных. В действительности переменные могут быть дискретными (булевыми, целочисленными).
2. Обращение в нуль первой производной есть необходимое, но недостаточное условие наличия экстремума (существуют точки перегиба).
3. Отсутствие ограничений в виде неравенств. Во всех темах, где мы встречались с задачами оптимизации, ограничения обязательно присутствуют.
4. Требование единственной точки экстремума (обязательного условия выпуклости функций) может и не выполняться.
Преимущества динамического метода оптимизации Гамильто- на – Якоби – Беллмана перед методами классического математического анализа состоят в следующем.
1. Решаются оптимизационные задачи любого вида (функции выпуклые, вогнутые, с наличием нескольких экстремумов).
2. Наличие ограничений на переменные не усложняет, а упрощает определение экстремума, поскольку сокращается число анализируемых вариантов.
3. Метод пригоден и для непрерывных переменных, если заранее оговорить точность отыскиваемого решения.
4. Безусловность выполнения принципа оптимальности: оптимальное решение на каждом последующем шаге ищется относительно решения, найденного на предыдущем шаге.
5. Возможность получения не единственного оптимального решения, что позволяет лучше учесть особенности экономической ситуации.
6. Возможность использования метода для многомерных задач (например, при распределении множества ресурсов).
Метод Гамильтона – Якоби – Беллмана носит и другое название метода динамического программирования (МДП).
Приведем конкретный пример использования этого метода МДП.
Пример. Самолет загружается неделимыми предметами трех типов, каждый весом: P1 = 34, P2 = 28, P3 = 25 кг, и стоимостью, соответственно, С1 = 100, С2 = 70, С3 = 65 денежных единиц за предмет. Грузоподъемность самолета Pс=100 кг. Сколько предметов каждого типа Xj надо загрузить, чтобы суммарная стоимость перевозки была максимальной?
- Если самолет загружать только предметами первого типа (вариант, для которого n = 1), то максимальная стоимость груза составит:
Естественно, что P1X1 Pс и тогда X1 Pc/ P1. Значит, для первого варианта (n = 1) максимальную стоимость груза можно будет записать, равной:
- При загрузке самолета предметами и первого X1, и второго типа X2 (вариант n = 2) в самолет нельзя взять больше, чем разницу (Pс P2X2) предметов первого типа. Тогда стоимость предметов первого типа будет:
Отсюда максимальная стоимость груза для предметов первого и второго типа ( для варианта n = 2) составит значение:
Обращаем ваше внимание на то, что число предметов можно интерпретировать, как число шагов по объектам любой природы. Это значит, что в рекуррентной формуле (8) заложен алгоритм решения любых распределительных задач. К их числу относятся: транспортные перевозки, планирование производственной программы, распределение и замена оборудования, производство и хранение продукции, поставки сырья, распределение нагрузки по генераторам электростанций и другие.
Полученные результаты по этому алгоритму для нашей задачи следует сопоставить с решением этой же задачи для линейной целевой функции:
Ограничение относится только к грузоподъемности самолета:
Решение задачи (10) – (11) дает следующее: Для нецелочисленных переменных значение Z = 294,12 денежных единиц. Оптимальные значения переменных X1 = 2,941; X2 = 0; X3 = 0.
Для целочисленных переменных значение Z = 270 денежных единиц. Оптимальные значения переменных X1 = 2; X2 = 1; X3 = 0. Причем, в запасе остается еще 4 кг груза.
Метод Гамильтона – Якоби – Беллмана имеет глубокие математические обоснования [9]. Различают два понятия: программа управления и синтез. Программа управления отождествляется с принятием решений на перспективу и возможной потери свойств оптимальности. Синтез – отслеживание и принятие оперативных решений без потери свойств оптимальности. Синтез обеспечивает определение оптимального управления экономикой в каждый момент времени для любого состояния экономики и для любых начальных условий.
Для непрерывных переменных метод Гамильтона – Якоби Беллмана позволяет отыскивать оптимальные решения путем решения задачи Коши для системы обыкновенных дифференциальных уравнений. Весь вычислительный процесс при этом опирается на теорему о достаточных условиях оптимальности.
Для дискретных переменных (и многошаговых процедурах) используются рекуррентные функциональные уравнения типа (8). Приведем следующий пример решения оптимизационной задачи и покажем ее преимущества для качества информационных ресурсов.
Пример. Управление ресурсами для экономического развития четырех заводов.
Каждому из четырех заводов (n = 4) запланирован прирост продукции в количестве gi (x) в зависимости от суммы выделенного капитала . Требуется распределить общую сумму выделенного капитала между заводами так, чтобы общий прирост выпуска продукции был максимальным.