Методы оптимальных решений (вариант 3, АлтИЭ)

Введение 3 1 Классическая задача оптимизации, решение методом множителей Лагранжа 4 2. Метод динамического программирования 6 Заключение 10 Список используемых источников 11

1. Бардаков, В.Г. Методы оптимальных решений: учебное пособие / В.Г. Бардаков, О.В. Мамонов. – Новосибирск: Новосибирский государственный аграрный университет, 2013. – 230 c. 2. Галкина, М.Ю. Методы оптимальных решений: учебно-методическое пособие / М.Ю. Галкина. – Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2016. – 89 c. 3. Майорова, Н.Л. Методы оптимизации: учебное пособие / Н.Л. Майорова, Д.В. Глазков; Яросл. гос. ун-т им. П. Г. Демидова. – Ярославль: ЯрГУ, 2015. – 112 с. 4. Порублев И.Н. Алгоритмы и программы. Решение олимпиадных задач / И.Н. Порублев, А.Б. Ставровотский. – М.: ООО «И.Д. Вильямс» , 2016. – 456 с. 5. Условная оптимизация. Метод множителей Лагранжа [Электронный ресурс]. – URL: http://simenergy.ru/math-analysis/solution-methods/88-lagrange-method (дата обращения: 20.11.18).

При большом количестве подзадач сложно понять, как решать такую задачу. Как правило, решить одну малую задачу проще, чем решить большую задачу, состоящую из маленьких. Поэтому ДП предлагает следующее: берем одну подзадачу с переменной X1. Например, завод производит только стулья. У директора стоит задача получения максимальной прибыли с продажи стульев. После того, как найдем оптимальное решение для первой подзадачи, берем подзадачу для двух переменных Х1 и Х2, и решаем ее с помощью уже найденного решения для первой подзадачи. Получаем решение уже для большей подзадачи, где фигурируют переменные Х1 и Х2. Затем, используя полученное решение, берем подзадачи, охватывающие X1, X2 и Х3. И так продолжаем пока не получим решение для всей общей задачи. Ключевым моментом здесь является использование выполненного решения для малой подзадачи при решении очередного шага – большей подзадачи. Часто при постановке задачи кажущимся оптимальным решением является перебор всех возможных вариантов. Однако, вследствии очень большого количества таких вариантов и, как результат, перегрузки памяти компьютера, такой способ не всегда приемлем. В основе динамического программирования лежит идея решения поставленной задачи путем деления ее на отдельные части (подзадачи, этапы), решение этих подзадач и последующего объединения этих решений в одно общее решение. Часто большинство из подзадач абсолютно одинаковы