Динамическое программирование. (Семинар 3) презентация

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

Задача динамического программирования Рассмотрим динамическую систему, которая последовательно за n шагов переходит из состояния в состояние Промежуточные состояния определяют состояния системы после i-го шага. Как правило, состояния системы определяются несколькими числами, поэтому предполагается, что являются векторами, т.е.

Переход системы из состояния в состояние определяется параметрами (управлениями) при помощи уравнения состояний Переход системы из состояния в состояние определяется параметрами (управлениями) при помощи уравнения состояний Эффективность каждого шага оценивается функциями . Таким образом, эффективность всего процесса характеризуется суммой

Задача состоит в том, чтобы найти набор управлений , оптимизирующий (далее предполагается, что решается задача на максимум): Задача состоит в том, чтобы найти набор управлений , оптимизирующий (далее предполагается, что решается задача на максимум): Процесс решения разбивается на n шагов. Введём функцию: - эта функция характеризует эффективность перехода от состояния к .

Последовательно оптимизируем По формулам, называемым уравнениями Беллмана

находим максимальное решение задачи.

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

Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере . Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере . Аналогично, для второй отрасли прибыль составляет , а возврат

В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если n = 4, а

Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли. Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли. В силу того же условия уравнения состояний имеют вид: А прибыль на i-м году равна:

Решение задачи начинается с оптимизации функции : Решение задачи начинается с оптимизации функции : Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому: при

Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере . Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере . Аналогично, для второй отрасли прибыль составляет , а возврат

В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если n = 4, а

Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли. Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли. В силу того же условия уравнения состояний имеют вид: А прибыль на i-м году равна:

Решение задачи начинается с оптимизации функции : Решение задачи начинается с оптимизации функции : Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому: при

Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль . Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .

Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль . Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .

Методы оптимизации Функция спроса D(p) определяет спрос (количество купленного товара) при цене p за единицу продукции. Функция предложения S(p) задает количество товара, которое поставщик может предложить по рыночной цене p.

Методы оптимизации Говорят, что рынок находится в равновесии, если покупатели могут купить столько товара, сколько им необходимо, а продавец может реализовать весь товар, который он намерен продать. Равновесная цена р0 товара на рынке находится из условия S(р0) = D(р0), а количество q0 проданного товара q0 = D(р0).

Предположим, что на продукцию компании вводится (дополнительный) фиксированный налог t на каждую единицу реализованного товара. Предположим, что на продукцию компании вводится (дополнительный) фиксированный налог t на каждую единицу реализованного товара. Если ставка налога достаточно велика, то производство товара будет невыгодно, и это приведет его к остановке. Возникает вопрос о такой ставке налога, чтобы итоговый сбор был максимальным.

Пусть доход от продажи (выручка): Пусть доход от продажи (выручка): а затраты на выпуск продукта в зависимости от количества q: Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор. Как уменьшится количество выпускаемой продукции?

Пусть доход от продажи (выручка): Пусть доход от продажи (выручка): а затраты на выпуск продукта в зависимости от количества q: Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор. Как уменьшится количество выпускаемой продукции?

Для товаров X1 и X2 известны функции спроса: Для товаров X1 и X2 известны функции спроса: Фирма-монополист имеет функцию издержек: Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план.

Для товаров X1 и X2 известны функции спроса: Для товаров X1 и X2 известны функции спроса: Фирма-монополист имеет функцию издержек: Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план.

Задачи многокритериальной оптимизации Задача вида: где i > 1, - допустимое множество; fi(x) – гладкие функции на D, называется задачей многокритериальной оптимизации. Область допустимых решений D задается системой уравнений и неравенств.

Пусть X и Y – два допустимых решения. Говорят, что X доминирует Y, если для всех Пусть X и Y – два допустимых решения. Говорят, что X доминирует Y, если для всех i = 1, 2, …, n выполняется неравенство fi(X) ≥ fi(Y) и найдется такое k, что fk(X) > fk(Y). Решение Z называется недоминируемым (эффективным), если нет решения X, которое бы доминировало Z.

Множество эффективных (недоминируемых) решений называется множеством Парето. Множество эффективных (недоминируемых) решений называется множеством Парето. Геометрическое изображение множества Парето называется Парето-эффективной границей (Парето-оптимальной границей). В задаче многокритериальной оптимизации наилучшее решение следует искать в множестве Парето.

Алгоритм построения Парето-эффективной границы: Алгоритм построения Парето-эффективной границы: 1. Строим допустимое множество D, заданное системой ограничений как пересечение полуплоскостей, соответствующих каждому неравенству, входящему в эту систему. 2. Для каждой функции строим линию уровня как прямую, перпендикулярную соответствующему вектору нормали .

Каждая из этих линий разбивает плоскость XOY на две полуплоскости. Каждая из этих линий разбивает плоскость XOY на две полуплоскости. Пусть Пi – полуплоскости, содержащие вектор градиента целевой функции fi, а их пересечение 3. Перемещая данную область П по границе допустимого множества D, находим те точки границы, которые являются единственными точками пересечения областей П и D. Данные точки - оптимальные по Парето, а множество всех таких точек – Парето-эффективная граница.

Найти Парето-эффективную границу задачи: Найти Парето-эффективную границу задачи:

Найти Парето-эффективную границу задачи: Найти Парето-эффективную границу задачи:

Метод идеальной точки Метод идеальной точки является геометрическим методом для многокритериальных задач.

Решить задачу многокритериальной оптимизации методом идеальной точки: Решить задачу многокритериальной оптимизации методом идеальной точки:

Решить задачу многокритериальной оптимизации методом идеальной точки: Решить задачу многокритериальной оптимизации методом идеальной точки:

Спасибо за внимание!