1 Содержание:
TOC o «1-2» h z u Введение. PAGEREF _Toc154915412 h 3
1.Основные понятия. 4
1.1Определения. 4
1.2Задачи оптимизации. 5
2.Одномерная оптимизация. 6
2.1Задачи па экстремум. 6
2.2Методы поиска. 7
2.3Метод золотого сечения. 8
2.4Метод Ньютона. 11
3.Многомерные задачи оптимизации. 13
3.1Минимум функции нескольких переменных. 13
3.2 Метод покоординатного спуска. 14
3.3 Метод градиентного спуска. 14
4.Задачи с ограничениями. 16
4.1Линейное Программирование. 16
4.2Геометрический метод. 17
4.3 Задача о ресурсах. 19
5.Практическая часть. 23
Списоклитературы. 27Введение
Эта курсовая работа описывает задачи оптимизации иметоды их решения необходимые для тех или иных видов деятельности, в частностив производстве.
Оптимизацией называют процесс выбора наилучшеговарианта из всех возможных. В производстве необходимо знать какой из видовпродукции наиболее оптимален для выпуска, и который принесет больше прибыли. Вмаркетинге тоже используется методы оптимизации.
Маркетинг – это комплексная система организациипроизводства и сбыта товаров и услуг основанное на предвидении и удовлетворенииспроса потребителей. В маркетинге необходимо изучать потребность покупателей втом или ином товаре, передача о потребностях на предприятие и производствонаиболее выгодных товаров.
1. Основныепонятия1.1 Определения.
Под оптимизациейпонимают процесс выбора наилучшего варианта из всех возможных. С точки зренияинженерных расчетов методы оптимизации позволяют выбрать наилучший вариантконструкции, наилучшее распределение ресурсов и т.д.
В процессе решения задачи оптимизации обычнонеобходимо найти оптимальные значения некоторых параметров, определяющих даннуюзадачу. При решении инженерных задач их принято называть проектными параметрами, а в экономических задачах их обычноназывают параметрами плана. Вкачестве проектных параметров могут быть, в частности, значения линейныхразмеров объекта, массы, температуры и т.п. число n проектных параметров x1,x2,…,xn характеризует размерность( и степень сложности) задачи оптимизации.
Выбор оптимальногорешения или сравнение двух альтернативных решений проводится с помощьюнекоторой зависимой величины (функции), определяемой проектными параметрами.Эта величина называется целевой функцией(или критерием качества). В процессерешения задачи оптимизации должны быть найдены такие значения проектныхпараметров, при которых целевая функция имеет минимум (или максимум). Такимобразом, целевая функция – это глобальный критерий оптимальности вматематических моделях, с помощью которых описываются инженерные илиэкономические задачи.
Целевую функцию можнозаписать в виде
U=F(x1, x2,…,xn). (1.1)
Примерами целевойфункции, встречающимися в инженерных и экономических расчетах, являютсяпрочность и масса конструкции, мощность установки, объем выпуска продукции, стоимость перевозокгруза и т.п.
В случае одногопроектного параметра целевая функция (1.1)является функцией одной переменной, и се график — некоторая кривая наплоскости. При целевая функцияявляется функцией двух переменных, и ее график — поверхность в трехмерномпространстве.
Следует отметить, что целевая функция не всегдаможет быть представлена в виде формулы.Иногда она может принимать только некоторые значения, задаваться в виде таблицыи т. п. Во всех случаях она должна быть однозначной функцией проектных параметров.
Целевых функций может быть несколько. Например, при проектированииизделий машиностроения одновременно требуется обеспечить, максимальнуюнадежность, минимальную материалоемкость, максимальный полезный объем (илигрузоподъемность). Некоторые целевые функции могут оказаться несовместимыми. Втаких случаях необходимо вводить приоритет той или иной целевой функции.1.2 Задачи оптимизации.
Можновыделить два типа задач оптимизации — безусловные и условные. Безусловнаязадача оптимизации состоит в отыскании максимума или минимума действительной функции (1.1) придействительных переменных и определении соответствующих значений аргументов нанекотором множестве σ n-мерного пространства. Обычнорассматриваются задачи минимизации; к ним легко сводятся и задачи на поиск максимумапутем замены знака целевой функции на противоположный.
Условные задачи оптимизации, или задачи сограничениями, это такие, при формулировке которых задаются некоторые условия(ограничения) на множестве
Ограничения-равенствавыражают зависимость между, проектными параметрами, которая должна учитываться принахождении решения. Эти ограничения отражают законы природы, наличие ресурсов т.п.
в результате ограниченийобласть проектирования , определяемая всеми проектными параметрами,может быть существенно уменьшена в соответствии с физической сущностью задачи.
При наличие ограничений оптимальное решение можетсоответствовать либо локальному экстремуму в нутрии области проектирования,либо значению целевой функции на границе области. Если ограничения отсутствуютто ищется оптимальное решение на всей области проектирования, то естьглобальный экстремум. 2. Одномернаяоптимизация2.1 Задачи па экстремум.
Одномерная задача оптимизации в общемслучае формулируется следующим образом. Найти наименьшее (или наибольшее)значение целевой функции y=х,заданной на множестве σ, и определить значениепроектного параметра х Є σ,при котором целевая функция принимает экстремальное значение. Существование решения поставленнойзадачи вытекает из следующей теоремы.
ТеоремаВейерштрасса. Всякая функция F(х), непрерывная на отрезке[а, b], принимает наэтом отрезке наименьшее и наибольшее значения, т.е. на отрезке [а, b] существуют такие точки х1в х2, что для любого х Є [а, b] имеют место неравенства
Этатеорема не доказывает единственности решения. Не исключена возможностьдостижения равных экстремальных значений сразу в нескольких точках данногоотрезка. В частности, такая ситуация имеет место для периодической функции, рассматриваемойна отрезке, содержащем несколько периодов.
Будемрассматривать методы оптимизации для разных классов целевых функций. Простейшимиз них является случай дифференцируемой функции F(х) на отрезке [а, b], причем функция задана в виде аналитическойзависимости у = F(х), иможет быть найдено явное выражение для ее производной ‚ экстремумов таких функций можно проводитьизвестными из курса высшей математики методами дифференциального исчисления. Напомнимвкратце этот путь.
Функция‚ может достигать своегонаименьшего и наибольшего значений либо в граничных точках отрезка [а, b], либо в точках минимума и максимума.Последние точки обязательно должны быть критическими, т. е. производная в этих точкахобращается в нуль, — это необходимое условие экстремума. Следовательно, дляопределения наименьшего или наибольшего значений функции ‚ на отрезке [а, b] нужно вычислить еезначения во всех критических точках данного отрезка и в его граничных точках исравнить полученные значения; наименьшее или наибольшее из них и будет искомымзначением.
Случай,когда целевая функция задана в табличном виде или может быть вычислена принекоторых дискретных значениях аргумента, используются различные методы поиска. Они основаны на вычислениицелевой функции в отдельных точках и выборе среди них наибольшего илинаименьшего значений. Существует ряд алгоритмов решения данной задачи.Рассмотрим некоторые из них.2.2 Методы поиска.
Численныеметоды поиска экстремальных значений функции рассмотрим на примере нахожденияминимума функции на отрезке [а., b]. Будем предполагать, чтоцелевая функция унимодальна, т.е. наданном отрезке она имеет только один минимум. Отметим, что в инженернойпрактике обычно встречаются именно такие целевые функции.
Погрешность приближенногорешения задачи определяется разностью между оптимальным значением x проектногопараметра и приближение к нему х.Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимогозначения а:
(2.1)
Процессрешения задачи методом поиска состоит в последовательном сужении интервалаизменения проектного параметра, называемого интерваломнеопределенности. В начале процесса оптимизации его длина равна
Наиболеепростым способом сужения интервала является деление его на некоторое число равныхчастей с последующим вычислением значений целевой функции в точках разбиения. Пусть- число элементарных отрезков, - шаг разбиения. Вычислим значения целевой функции в узлах
Число на отрезке зависит от числаточек, и для непрерывной функции
т. е. с увеличением числаточек разбиения погрешность минимума стремится к нулю.
Вданном методе, который можно назвать методом перебора, главная трудностьсостоит в выборе и оценке погрешности. Можно,например, провести оптимизацию с разными шагами и исследовать сходимость такогоитерационного процесса. Но это трудоемкий путь.
Болееэкономичным способом уточнения оптимального параметра является использованиесвойства унимодальности целевой функции, это позволяет построить процесс суженияинтервала неопределенности. Пусть, как и ранее, среди всех значенийунимодальной функции
то его снова можно уменьшитьпутем нового разбиения. Получится интервал, равный двум длинам нового шага разбиенияи т. д. Процесс оптимизации продолжается до достижения заданного размераинтервала неопределенности.
Существует ряд специальныхметодов поиска оптимальных решений разными способами выбора узлов и сужения интерваланеопределенности — метод деления отрезка пополам, метод золотого сечения и др. Рассмотримодин из них. 2.3 Метод золотого сечения.
Припостроении процесса оптимизации стараются сократить объем вычислений и времяпоиска. Этого достигают обычно путем сокращения количества вычислений (илиизмерений — при проведении эксперимента) значений целевой функции достигается наилучшаяточность, является метод золотого сечения.Он состоит в построении последовательности отрезков проводится лишь водной точке. Эта точка, называемая золотымсечением, выбирается специальным образом.
Пояснимсначала идею метода геометрически, а затем выведем необходимые соотношения. Папервом шаге процесса оптимизации внутри отрезка выбираем некоторыевнутренние точки и и отрезков: или можно отбросить, сузивтем самым первоначальный интервал неопределенности.
Второйшаг проводим на отрезке осталась изпредыдущего шага, поэтому достаточно выбрать лишь одну точку и провести сравнение.Поскольку здесь не станет меньшезаданной величины
Теперьрассмотрим способ размещения внутренних точек на каждом отрезке l, а точка деления разбиваетего на части
(2.2)
Изэтого соотношения можно найти точку деления, вычислив отношения
Преобразуем,выражение (2.2) и найдем значения
Посколькупас интересует только положительное решение, то
Очевидно,что интервал неопределенности можно разделить в соотношении золотого сечениядвояко: в пропорциях и и выбираются с учетомэтих пропорций. В данном случае имеем
(2.3)
Аналогично,
(2.4)
Начальнаядлина интервала неопределенности составляет
На втором шаге отрезок также делится всоотношении золотого сечения. При этом одной из точек деления будет точка
Последнееравенство следует из соотношения
Втораяточка деления выбирается так же, каквыбирается точка при деления отрезка
Поаналогии с соотношениями (2.3), (2.4) можно записать координаты точек деления и на k-м шаге оптимизация
Вычислению,естественно, подлежит только одна из координат
(2.5)
Как я вобщем случае метода поиска, процесс оптимизации заканчивается при выполненииусловия или
(2.6)
Методзолотого сечения (как и, например, метод решения нелинейных уравнений делениемотрезка пополам) относится к тем немногим численным методам, для которых можногарантировать, что требуемая точность достигнута.2.4 Метод Ньютона.
Какбыло отмечено в п. 2.1, задача одномерной оптимизации дифференцируемой функции сводится к нахождениюкритических точек этой функции, определяемых уравнением
(2.7)
Когдауравнение (2.7) нельзя решить аналитически, для его решения можно применитьчисленные методы, например метод Ньютона. В этом случае говорят о методе Ньютона решения задачи оптимизации.
Пусть - решение уравнения(2.7), а некоторое начальное
приближение к
подставим вместо производную и получим тем самым формулудля
(2.8)
для использования этойформулы необходимо, чтобы качестве критерияокончания итерационного процесса можно применить условия близости двухпоследовательных приближений
или близости значений целевойфункции на этих приближениях
Достаточноеусловие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующаятеорема.
Теорема. Пусть и непрерывна. Тогдасуществуют окрестность корня такая, что еслиначальное приближение принадлежит этойокрестности, то для метода Ньютона (2.8) последовательность значений сходится к при
Заметим,что точка может являться как точкой минимума, так и точкоймаксимума, а может (при имеет как минимумы,так и максимум то она может сходиться и к точкам минимума, и к точкам максимумав зависимости от того, из окрестности какой критической точки взято начальноеприближение. При этом, в отличие от других методов оптимизации, формула дляпоиска максимума функции совпадает с формулой для поиска минимума.
Формулуметода Ньютона решения задачи оптимизации можно получить и из другихсоображений. Разложим функцию в ряд Тейлора вокрестности точки
(2.9)
Вкачестве следующего приближения к оптимальномузначению проектного параметра возьмем точкуэкстремума функции
что совпадает с (2.8). Разложение (2.9) вокрестности точки заменяется параболой графикомфункции
Относительносходимости метода Ньютона решения задачи оптимизации можно сделать замечания.Метод Ньютона обладает более быстрой сходимостью по сравнению с методами,которые не используют дифференциальные свойства функции (например, с методомзолотого сечения). Однако сходимость метода Ньютона не гарантирована, принеудачном выборе начального приближения он может расходиться.3. Многомерныезадачи оптимизации3.1 Минимум функции нескольких переменных.
Впункте 2 мы рассмотрели одномерные задачи оптимизации, в которых целеваяфункция зависит лишь от одного аргумента. Однако в большинстве реальных задачоптимизации, представляющих практический интерес, целевая функция зависит от многихпроектных параметров.
Минимумдифференцируемой функции многих переменных можно найти, исследуяее значения в критических точках, которые определяются из решения системыдифференциальных уравнений
(3.1)
Рассмотренныйметод можно использовать лишь для дифференцируемой целевой функции. Но и в этомслучае могут возникнуть серьезные трудности при решении систем нелинейныхуравнений (3.1).
Вомногих случаях никакой формулы для целевой функции нет, а имеется лишьвозможность определения ее значений в произвольныхточках рассматриваемой области с помощью некоторого вычислительного алгоритмаили физических измерений. Задача состоит в приближенном определении наименьшегозначения функции во всей области при известных ее значениях в отдельных точках.
Длярешения подобной задачи в области проектирования, в которой ищетсяминимум целевой функции на части с шагам
В полученныхузлах можно вычислить значения целевой функции и среди этих значений найтинаименьшее.
Такой методаналогичен методу перебора для функции одной переменной. Однако в многомерныхзадачах оптимизации, где число проектныхпараметров достигает пяти и более, этот метод потребовал бы слишком большогообъема вычислений.3.2 Методпокоординатного спуска.
Пустьтребуется найти наименьшее значение целевой функции в фукция однойпеременной в направлении убыванияфункции от точки до некоторой точки дифференцируемая, тозначение может быть найдено
(3.2)
Зафиксируемтеперь все координаты кроме от точки до точки можно найти
Аналогичнопроводится спуск по координатам до
Налюбом k-том шаге этотпроцесс можно прервать. И значение функции в точке k принимается вкачестве наименьшего значения целевой функции в рассматриваемой области.
Методпокоординатного спуска сводит задачу о нахождении наименьшего значения функциимногих переменных к многократному.3.3 Методградиентного спуска.
Вприроде мы нередко наблюдаем явления, сходные с решением задачи на нахождениеминимума. К ним относится, в частности, стекание воды с берега котлована надно. Упростим ситуацию, считая, что берега котлована унимодальные, т. е. онигладкие, а не содержат локальных углублений или выступов. Тогда вода устремитсявниз в направлении наибольшей крутизны берега в каждой точке.
Переходяна математический язык, заключаем, что направление наискорейшего спускасоответствует направлению наибольшего убывания функции. Из курса математикиизвестно, что направление наибольшего возрастания функции двух переменных характеризуется ее градиентом
Где единичные векторы(орты) в направлении координатных осей. Следовательно, направление, противоположноеградиентному, укажет направление наибольшего убывания функции. Методы,основанные на выборе пути оптимизации с помощью градиента, называются градиентными. Идея метода градиентногоспуска состоит в следующем. Выбираем некоторую начальную точку
Врезультате приходим в точку
Процесспродолжается до получения наименьшего значения целевой функции. Строго говоря,момент окончания поиска наступит тогда, когда движение из полученной точки слюбым шагом приводит к возрастанию значения целевой функции. Если минимум функциидостигается внутри рассматриваемой области, то в этой точке градиент равеннулю, что также может служить сигналом об окончании процесса оптимизации. Приближенномомент окончания поиска можно определить аналогично тому, как это делается вдругих итерационных методах.
Формулыдля частных производных можно получить в явном виде лишь в том случае, когдацелевая функция задана аналитически. В противном случае эти производные вычисляютсяс помощью численного дифференцирования:
При использованииградиентного спуска в задачахоптимизации основной объем вычислений приходится обычно па вычисление градиентацелевой функций в каждой точке траектории спуска. Поэтому целесообразно уменьшитьколичество таких точек без ущерба для самого решения. Это достигается в некоторыхметодах, являющихся модификациями градиентного спуска. Одним из них является метод наискорейшего спуска. Согласноэтому методу, после определения в начальной точке направления, противоположногоградиенту целевой функция, решают одномерную задачу оптимизации, минимизируяфункцию вдоль этого направления. А именно, минимизируется функция
Дляминимизации можно использоватьодин из методов одномерной оптимизации. Можно и просто двигаться в направлении,противоположном градиенту, делая при этом не один шаг, а несколько шагов до техпор, пока целевая функция не перестанет убывать. В найденной новой точке сноваопределяют направление спуска (с помощью градиента) и ищут новую точку минимумацелевой функции и т. д. В этом методе спуск происходит гораздо более крупнымишагами, и градиент функции вычисляется в меньшем числе точек.
Заметим,что сведение многомерной задачи оптимизации к последовательности одномерныхзадач на каждом шаге оптимизации рассмотрено в п.3.2 для метода покоординатного спуска. Разница состоитв том, что здесь направление одномерной оптимизации определяется градиентомцелевой функции, тогда как покоординатный спуск проводится на каждом шаге вдольодного из координатных направлений.4. Задачи сограничениями4.1 Линейное Программирование.
До сихпор при рассмотрении задач оптимизации мы не делали никаких предположений охарактере целевой функции и виде ограничений. Важным разделом математическогопрограммирования является линейное программирование,изучающее задачи оптимизации, в которых, целевая функция является линейнойфункцией проектных параметров, а ограничения задаются в виде линейных уравненийи неравенств.
Стандартная(каноническая) постановка задачи линейного программирования формулируетсяследующим образом: найти значения переменных, которые
1)
(4.1)
2) являются неотрицательными, т. е.
(4.2)
3) обеспечивают наименьшее значение линейнойцелевой функции
(4.3)
Всякоерешение системы уравнений (4.1), удовлетворяющее системе неравенств (4.2),называется допустимым решением. Допустимоерешение, которое минимизирует целевую функцию (4.3), называется оптимальным решением.4.2 Геометрический метод.
Областьюрешения линейного неравенства с двумя переменными
(4.4)
является полуплоскость.Для того чтобы определить, какая из двух полуплоскостей соответствует этомунеравенству, нужно привести его к виду или (4.4)имеет вид - левую полуплоскость.
Областью решений системы являетсяпересечение конечного числа полуплоскостей, описываемых каждым отдельнымнеравенством вида (4.4). Это пересечение представляет собой многоугольную область
Областьрешений обладает важнымсвойством выпуклости. Область называетсявыпуклой, если произвольные две ееточки можно соединить отрезком, целиком принадлежащим данной области.
Опорной прямой называется прямая,которая имеет с областью по крайней мере одну общую точку, при этом вся областьрасположена но одну сторону от этой прямой.
Аналогичноможно дать геометрическую интерпретацию системы неравенств с тремя переменными.В этом случае каждое неравенство описывает полупространство, а вся система — пересечениеполупространств, т. е. многогранник, который также обладает свойством выпуклости.Здесь опорная плоскость проходит через вершину, ребро или грань многограннойобласти.
Основываясьна введенных понятиях, рассмотрим геометрическийметод решения задачи линейного программирования. Пусть заданы линейная целеваяфункция двух независимых переменных,а также некоторая совместная система линейных неравенств, описывающих областьрешений найти такое, прикотором линейная целевая функция принимает наименьшеезначение.
Положимфункцию равной некоторомупостоянному значению
(4.5)
Припараллельном переносе этой прямой в положительном направлении вектора нормали линейная функция будет возрастать, апри переносе прямой в противоположном направлении — убывать.
Действительно,пусть при параллельном переносе точка
Поскольку
Есливектор сонаправлен с вектором и
Предположим,что прямая, записанная в виде (4.5), при параллельном переносе в положительномнаправлении вектора первый развстретится с областью допустимых решений в некоторой еевершине, при этом значение целевой функции равно будет минимальным,поскольку дальнейшее движение прямой в том же направлении приведет к увеличениюзначения
Если взадаче оптимизации нас интересует максимальное значение целевой функции, топараллельный перенос прямой (4.5) осуществляется в направлении, противоположном
Такимобразом, оптимизация линейной целевой функции на многоугольнике допустимых решенийпроисходит в точках пересечения этого многоугольника с опорными прямыми, соответствующимиданной целевой функции. При этом пересечение может быть в одной точке (в вершине многоугольника) либов бесконечном множестве точек (на ребре многоугольника).В последнем случае имеется бесконечное множество оптимальных решений.4.3 Задача оресурсах.
Враспоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м2 стекла,160 чел.-ч. (человеко-часов) рабочего времени. Бригаде поручено изготовить два наименованияизделий: А и Б. Цена одного изделия А -1 тыс. р., для его изготовлениянеобходимо 4 кгметалла, 2 м2стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1,2 тыс. для егоизготовления необходимо 5 кгметалла, 1 м2стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимостьбыла максимальной.
Сначаласформулируем задачу математически. Обозначим через и количество изделий А иБ, которое необходимо запланировать (т.е. это искомые величины). Имеющиеся ресурсысырья и рабочего времени зададим в видеограничений-неравенств: