Методы оптимизации. 2

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГ ОБРАЗОВАНИЯ

Московский государственный  университет имени В.П. Горячкина.

Кафедра

Эксплуатация машинно-транспортного парка 
 

 

                

 

 

Реферат по оптимизации процессов и принятию решений

на тему:

«Методы оптимизации».

 

 

 

 

 

 

Выполнил: студент 26 гр. факультета ПРИМА 

Шергин Д.К.

                                                      Преподователь:                       Майстренко Н.А.

 

 

 

 

 

 

 

Москва 2013

 Содержание.

Введение…………………………………………………………………………………...3

1.Основные понятия и определения…………………………………………………..…4

2.Линейная оптимизация…………………………………………………………………6

2.1.Симплекс – метод……………………………………………………………………..6

2.2.Задача о распределении ресурсов……………………………………………………7

2.3.Транспортная задача…………………………………………………………………..8

3.Нелинейная оптимизация……………………………………………………………...10

3.1 Метод золотого сечения……………………………………………………………..10

3.2 Метод Ньютона………………………………………………………………………12

3.3 Метод потенциалов………………………………………………………………….14

Заключение……………………………………………………………………………….27

Список использованной литературы………………………………..………………….28

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

В повседневной жизни перед  человеком постоянно возникает  проблема принятия решения. Особенно остро  эта проблема стоит перед менеджерами, управляющими и инженерами разного  уровня. Зачастую только наиболее важные и трудные решения становятся предметом детального анализа. Даже в сложных ситуациях многие специалисты  считают, что справятся с ситуацией  на интуитивном уровне. В действительности это далеко не всегда так. Неоптимальность решений, принимаемых в жизненных и производственных ситуациях на основе интуитивных соображений, приводит к значительным потерям прибыли, ресурсов и т.п. И чем сложнее ситуация, тем больше могут быть потери.

Методы оптимизации  позволяют решить задачи оптимально, наилучшим образом. Они являются одним из наиболее развивающихся разделов прикладной математики в силу большого многообразия и важности их приложений. В качестве примеров можно указать следующие области применения методов оптимизации:

• технико-экономические системы: планирование, управление, транспортные задачи, распределение кадров, ресурсов;
• численный анализ: аппроксимация, регрессия, решение систем уравнений, численные методы решения задач математической физики;
• технические системы: распознавание образов, оптимальное управление, роботы, управление производством, проектирование систем связи;
• математическая экономика: анализ больших макроэкономических моделей, микроэкономических моделей или моделей предпринимательства, теория принятия решений, теория игр.

Целью данного реферата является  рассмотрение методов оптимизации  и их практическое применение.

 

 

 

 

1.Оптимизация  задач.

1.1.Основные понятия и определения.

Обычно человек хочет  сделать _«как лучше “, но, чтобы не получить плохой результат при самых хороших намерениях, для решения задачи оптимизации нужно прежде всего найти ответы на следующие вопросы:

• Что значит лучше “?
• Что конкретно нужно улучшить?
• За счет чего можно добиться улучшения, что можно изменить?
• В каких пределах можно производить изменения?

Отвечая на первый вопрос, необходимо сформулировать

критерий  оптимальности, т.е. определить те признаки и предпочтения, по которым следует провести сравнительную оценку альтернатив и выбрать среди них наилучшую с точки зрения поставленной цели оптимизации. Именно с этой точки зрения можно ответить на второй вопрос: что конкретно нужно улучшить? Это может быть повышение производительности станка или срока службы технического устройства, снижение массы конструкции летательного аппарата или затрат на его производство и т.п.

Для ответа на два последних  вопроса необходимо располагать математической моделью объекта оптимизации. Эта модель описывает объект при помощи соотношений между величинами, характеризующими его свойства. Обычно хотя бы часть этих величин можно изменять в некоторых пределах, что и порождает множество альтернатив, среди которых и предстоит выбрать наилучшую. Изменяемые при оптимизации величины, входящие в математическую модель объекта оптимизации, называют параметрами оптимизации, а соотношения, устанавливающие пределы возможного изменения этих параметров, — ограничениями. Эти ограничения могут быть заданы в форме равенств или неравенств. Их называют соответственно ограничениями типа равенства или ограничениями типа неравенства.

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

Если целевая функция  и ограничения являются линейными  относительно параметров оптимизации, то говорят о задаче линейного программирования.

При нелинейной зависимости  целевой функции или ограничений  от параметров оптимизации говорят  о задаче нелинейного программирования.

 

 

 

 

 

 

 

 

 

 

2.Линейная оптимизация.

2.1.Симплекс –  метод.

Симплекс-метод является основным численным методом решения  задачи ЛП. Дадим его описание для канонической задачи линейной оптимизации

(c, x) → max, Ax = b, x > O_n; 

Будем считать, что rank A = m, m < n.

В соответствии со сложившейся  в ЛП традицией будем называть векторы x ∈ Ω = {x ∈ Rⁿ |Ax = b, x > O_n} допустимыми планами задачи . Допустимые планы, на которых целевая функция (c, x) принимает максимальное значение, будем называть оптимальными планами задачи.

Очень важным для дальнейшего  является понятие базисного плана. Допустимый план x = (x₁, x₂,..., x_n)^T называется базисным планом задачи, если у него найдется n — m нулевых компонент и при этом остальным компонентам xj₁ ,xj₂,, xj_m будут соответствовать линейно независимые столбцы Aj₁, Aj₂,..., Aj_m матрицы A. Набор этих векторов называется базисом этого базисного плана. Если у базисного плана m положительных компонент, то есть xj₁ > 0, xj₂ > 0, ..., xj_m > 0, то он называется невырожденным. В противном случае, то есть если у него положительных компонент меньше m, его называют вырожденным.

Можно доказать, что в  геометрическом смысле базисный план является вершиной многогранного множества Ω. Известно, что если Ω ≠ 0, то у него имеется, по крайней мере, одна вершина. Кроме того, как следует из геометрической интерпретации задачи ЛП, если задача (2.6) разрешима, то, по крайней мере, одна вершина Ω является оптимальным планом. Следовательно, если найти все базисные планы и подсчитать на них значения целевой функции, то найдем и оптимальные планы.

Симплекс-метод представляет собой вычислительную процедуру, которая по исходному базисному плану x генерирует последовательность базисных планов x¹,x²,...,x^p вместе с их базисами. На очередной p-ой итерации в зависимости от текущего значения параметров делается один из выводов:

1. либо x^p есть решение задачи (2.6),
2. либо задача (2.6) не имеет решения (неограничена),
3. либо строится следующий базисный план x^p+1.

Если при этом в последнем  случае базисный план x^p будет невырожденным,                   то (c,x^p+1) > (c,x^p). 

Если же x^p - вырожденный базисный план, то либо выполняется (??), либо x^p+1 = x^p, а итогом итерации является замена одного базиса плана x^p на другой. Перебор базисов может продолжаться несколько итераций, но обязательно появится базис, при котором осуществляется переход к новому базисному плану с большим значением целевой функции. Эта процедура за конечное число итераций обязательно приводит либо к выводу 1), либо к выводу 2), поскольку число базисных планов конечно.

2.2.Задача о  распределении ресурсов.

Многие практические задачи начинаются оптимизацией распределения  ресурсов. Пусть необходимо производить товары ……'Г_п (, j=1,¯n).Для этого имеются ресурсы (эл. энергия, оборудование, рабочая сила и т.д.) в количествах ,…,(,=1,¯m)единиц. Стоимость единицы ресурса равна д.е. Для производства одной единицы товара надо единиц ресурса . Каждая единица товара может быть реализована по цене .Известно, что рынок не может поглотить более, чем единиц товара .Необходимо составить план производства товара , таким образом, чтобы, хватило ресурсов, а полученная прибыль была максимальной.

Составим математическую модель. Обозначим , j=1, ¯n количество товара j-го типа, которое надо произвести. Тогда, по условию

≥0,≤                                                       (2.1)

                                                                                                              

причём ресурсов должно хватать, т.е.

, (i=1,2,…m)                                       (2.2)                                                                         

Себестоимость единицы товара, равна 

Чистая прибыль от одной  единицы товара есть =- а общая

прибыль будет равна:

                                    (2.3)                                                                             

Задача состоит в следующем: необходимо выбрать такие значения переменных, которые удовлетворяют неравенствам (2.1), (2.2) и обращают в максимум функцию п переменных z из (2.3).

 

2.3 Транспортная задача.

 

Имеется т складов и п пунктов потребления ,, ...,. На складах имеются запасы товаров одного типа в количествах ,,,...,а_т единиц. Пункты потребления подали заявки соответственно на ,,…,,единиц товара. Заявки выполнимы, т.е. сумма всех заявок не превосходит суммы всех имеющихся запасов

 

 

Стоимость перевозки одной  единицы товара со склада в пункт равна ,

i=1,¯m

Требуется составить план перевозок таким образом, чтобы все заявки были выполнены, а общие расходы на перевозки были бы минимальными.

Составим математическую модель. Обозначим через  количество товара, отправленного со склада в пункт . Решение (план перевозок) будет состоять из тхп чисел, т.е. является матрицей:

Х =

 

 

Необходимо выбрать такие  неотрицательные значения переменных, чтобы были выполнены следующие условия:

1. Ёмкость склада не должна быть превышена

 

, (i=1, ¯m)                                            (2.4)

 

2. Поданные заявки должны быть удовлетворены, т.е.

 

, (j=1, ¯n)                                             (2.5)

 

Общая стоимость перевозок  будет равна:

z=+ + …++

+ + + …++

………………………………

++ + …+

 

Необходимо составить  план перевозок, т.е. найти матрицу  такую,

чтобы переменныебыли неотрицательными и удовлетворяли условиям

(2.4) и (2.5), а при этом функция z принимала минимальное значение.

Если сумма всех заявок равна сумме запасов, то из каждого склада будут вывезены все 
                                                 (2.6)

 товары и неравенства  (1.4) обращаются в равенства.

Задача (1.4)-(1.6) называется транспортной задачей

 

3.Нелинейная оптимизация.

3.1  Метод золотого сечения.

Для построения конкретного  метода одномерной минимизации, работающего по принципу последовательного сокращения интервала неопределенности, следует задать правило выбора на каждом шаге двух внутренних точек. Конечно, желательно, чтобы одна из них всегда использовалась в качестве внутренней и для следующего интервала. Тогда число вычислений функции сократится вдвое и одна итерация потребует расчета только одного нового значения функции. В методе золотого сечения в качестве двух внутренних точек выбираются точки золотого сечения.

Говорят, что точка производит «золотое сечение» отрезка, если отношение длины всего отрезка к большей части равно отношению большей части к меньшей.

На отрезке , имеются две симметричные относительно его концов точки и :

 

≅1,618

Кроме того точка  производит  золотое   сечение  отрезка ,, а точка

- отрезка .

Метод относится  к последовательным стратегиям. Задается начальный интервал неопределенности и требуемая точность. Алгоритм уменьшения интервала опирается на анализ значений функции в двух точках. В качестве точек вычисления функции выбираются точки золотого сечения. Тогда с учетом свойств золотого сечения на каждой итерации, кроме первой, требуется только одно новое вычисление функции. Условия окончания процесса поиска стандартные: поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины.

Алгоритм.

1.Задать начальный  интервал неопределенности =, , точность

2.Положить к=0.

3.Вычислить =+(); =+()

4.Вычислить f(), f().

5. Сравнить f(), f():

5a. Если f() ≤ f(), то положить =, = и =+ - , =. Перейти к п.6

5б. Если f() > f(), то положить =, = и ; =, Перейти к п.6

6. Вычислить Δ=││и проверить условия окончания:

6а. Если Δ ≤ l, процесс поиска завершается и х*∈. В качестве приближенного решения можно взять середину последнего интервала:

х*≅

6б. Если Δ > l положить к=к+1 и перейти к п. 4.

Для метода золотого сечения  характеристика относительно уменьшения   начального    интервала   неопределенности    находится   по    формуле

R(N) = , где N- количество вычислений функции.

Текущие интервалы неопределенности имеют следующий вид: , Они отражают тот факт, что на первой итерации производится два вычисления функции, на последующих - по одному. Сокращение длины интервала неопределенности постоянно: = ... = 1,618.

Если задана величина R(N), то требуемое для достижения желаемой точности количество вычислений функции находится как наименьшее целое число, удовлетворяющее условию N > 1 + .

 

3.2 Метод Ньютона

Стратегия метода Ньютона  состоит в построении последовательности

точек {х^k},k = 0,1,…, таких, что  f() < f(, k= 0,1,… .Точки последовательности вычисляются по правилу

=+, k=0,1,…,                                            (3.1)

где - задается пользователем, а направление спуска   определяется для каждого значения k по формуле

  f()                                      (3.2)

Выбор   гарантирует выполнение требования  f() < f(, при

условии, что >0. Формула для получена из следующих соображений:

1. Функция f(х) аппроксимируется в каждой точке последовательности

 квадратичной функцией F_к = f()+ f(),+ 0.5( .

2. Направлениеопределяется из необходимого условия экстремума

первого порядка:   Таким  образом,  при выполнении требования

>0 последовательность является последовательностью точек минимумов квадратичных функций F_к, k= 0,1,… , Чтобы обеспечить

выполнение требования    что  f() < f(, k= 0,1,… , даже в тех случаях, когда для каких-либо значений матрица Гессе не окажется положительно определенной, рекомендуется для соответствующих значений k вычислить точку по методу градиентного спуска = с выбором величины шага из условия    f( f()) < f(.

Построение последовательности {}   заканчивается в точке , для которой      f() <, где – заданное малое положительное число, или при k≥M (M – предельное число итераций), или при двухкратном одновременном выполнении двух неравенств <, │f() = f(, где – малое положительное число.

Рис. Геометрическая интерпретация  метода Ньютона

Алгоритм.

1. Задать  ,,,М - предельное число итераций. Найти градиентf()

и матрицу Гессе .

2. Положить к = 0.
3. Вычислить f()
4. Проверить выполнение критерия окончания f() <. Если неравенство выполнено, расчет окончен и =, в противном случае перейти к п. 5

5.   Проверить   выполнение   неравенства k ≥ M. Если неравенство выполнено, расчет окончен и = , в противном случае перейти к п.6

6. Вычислить матрицу .

7. Вычислить матрицу   ..

8. Проверить выполнения  условия  >0. Если > 0, то перейти к п.9. В противном случае перейти к п.10, положив = f().

9. Определить = f().

10. Найти точку = + , положив =1,

 = f() или выбрав из условия f() < f(, если =f().

11. Проверить выполнение условий

ǁǁ < , │f() = f(:

11а. Если оба условия выполнены при текущем значении k и k=k – 1, то расчет окончен, = ;

11б. В противном случае положить k=k + 1 и перейти к п.3.

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

а) анализировать матрицу  на выполнение условия > 0

  k= 0,1… и заменять формулу = f() на формулу = f() в случае его невыполнения;

б) производить анализ точки  с целью выяснения, является ли она найденным приближением искомой точки .

 

3.3 Метод потенциалов.

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

 Для описания алгоритма  используем формульно-словесный  способ. Рассмотрим пример транспортной задачи (табл. 1).

Исходная транспортная матрица 

Таблица 1.  

В табл. 2.2 по строкам  матрицы представлены пункты (станции) отправления от А₁ до А₄ и объемы погрузки в тоннах – 100, 150, 90, 30 т, а по столбцам – пункты (станции) назначения от В₁ до В₅ и объемы выгрузки – 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (a_i = b_j = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А₁ и станцией выгрузки В₁, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом – 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, – оптимальным планом перевозок.   

 Алгоритм решения транспортной  задачи линейного программирования  будем описывать по операциям  с присвоением номера и названия.

Операция 1. Построение опорного плана.

Опорным, называется любой допустимый, как правило, не оптимальный план, который является исходным для последующего решения. Для построения опорного плана существует ряд методов. Самый простой из них – метод северо-западного  угла (табл. 2).

Метод северо-западного угла

Таблица 2   

Берем «северо-западную»  клетку матрицы – это клетка А₁В₁ и записываем в нее максимально возможную поставку – 40 т (объем выгрузки 40 т, ресурсы станции погрузки 100 т). Поскольку ресурсы станции погрузки А₁ не исчерпаны, следуем по первой строке вправо и записываем в клетку А₁В₂ корреспонденцию равную максимально возможной величине – 60 т. Таким образом получается, что ресурсы станции А₁ полностью использованы, однако спрос станции выгрузки В₂ не удовлетворен. Тогда от клетки А₁В₂ опускаемся вниз до клетки А₂В₂ и записываем в нее поставку равную 20 т. Описанным способом следуем далее до последней «юго-западной» клетки матрицы. В результате получаем допустимый план перевозок груза. Грузооборот или функционал транспортной задачи (сумма произведений корреспонденций на расстояние, рассчитанная по табл. 2) составит:

F_{сев-зап.} = 40 ∙ 10 + 60 ∙ 9 + 20 ∙ 7 + 110 ∙ 13 + 20 ∙ 6 + 30 ∙ 7 + 60 ∙ 1 + + 30 ∙ 2 = 2960 ткм

После расстановки корреспонденции  матрица проверяется на вырождение, т. е. должно выполняться условие

,                                                  (3.3) 

где m – количество строк, n – количество столбцов, N_баз – количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно  сумме строк и столбцов без  единицы. В нашем случае это условие  соблюдается: 8 = 4 + 5 – 1. План транспортной задачи, отвечающий условию (n + m – 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

Метод северо-западного  угла имеет существенный недостаток. При его использовании не учитываются  значения показателей критерия оптимальности  в клетках матрицы. Поэтому поставки могут попасть в «дорогие»  клетки с заведомо высокой ценой  или большим расстоянием. Опорный  план, полученный с использованием данного метода, как правило, далек  от оптимального, что обусловливает большой объем последующих расчетов для доведения его до оптимального. Описанный метод обычно не применяется.

Наиболее предпочтительным при ручном решении транспортных задач считается метод минимальной  стоимости или, как его еще  называют, метод наименьшего элемента в матрице. Суть его в следующем. В транспортной матрице выбирается клетка с минимальной стоимостью (расстоянием). В нашем случае это  клетка А₃В₅. В нее записывается максимально возможная поставка – это 90 т (табл. 4).

Метод наименьшего элемента в матрице

Таблица 3

Далее отыскиваются клетка, имеющая следующее по величине расстояние. В нашей матрице это две  клетки с расстоянием 2 км в пятом  столбце. Однако в эти клетки поставки корреспонденцию грузов ставить  нельзя, поскольку спрос станции  В₅ полностью удовлетворен со станции А₃. Поэтому столбец 5 из дальнейшего построения плана исключаем. Следующие по величине показателя критерия оптимальности клетки с расстоянием 4 км это клетки А₂В₁ и А₄В₂. Выбираем одну из них, например, А₂В₁ и записываем в нее поставку 40 т. Далее идет клетка А₄В₂ – поставка 30 т, потом А₁В₄ – 50 т, А₂В₂ – 50 т. Все оставшиеся ресурсы по станциям погрузки распределяем между клетками третьего столбца в клетки А₁В₃ и А₂В₃. После составления опорного плана во избежание ошибок целесообразно проверить балансы погрузки, выгрузки и суммы корреспонденций по строкам и по столбцам матрицы. Функционал F плана, составленного методом наименьшей стоимости, равен 2150 ткм. Таким образом, построенный план значительно лучше плана, построенного методом северо-западного угла. Однако число базисных клеток в плане – 7. Это не соответствует условию (4), т. е. меньше требуемого на единицу. Такой план математики назвали вырожденным (случай вырождения). Случай вырождения «лечат» путем введения в матрицу недостающего количества базисных клеток с нулевыми поставками. Нулевую поставку необходимо вводить в матрицу рядом с базисной клеткой, которая обусловила «пропажу» базисной клетки.

Для того чтобы понять, почему «пропадают» поставки, обратимся  к методу северо-западного угла. Из табл. 2следует, что как только была заполнена «северо-западная»  клетка, рядом с ней сразу появляется соседняя базисная клетка, потом еще  одна и т.д. Цепочка базисных клеток без разрыва следует до «юго-восточного угла» матрицы. Однако если бы в этой цепочке появилась клетка, связывающая  поставщика и потребителя с равными  объемами погрузки и выгрузки, и  в нее была бы записана такая же поставка, то это привело бы к  пропаже базисной клетки. Описанная  ситуация имела место в табл. 3, когда в клетку А₃В₅ была введена корреспонденция объемом 90 т, равная объемам погрузки и выгрузки по соответствующим станциям. Поэтому необходимо ввести в план дополнительную базисную клетку с нулевой поставкой. Эта клетка должна стоять рядом с клеткой А₃В₅. Из трех соседних клеток следует выбрать клетку с минимальным расстоянием, например, А₂В₅. Записываем в нее корреспонденцию, равную «0» (табл. 4).

Добавление нулевой поставки

Таблица 4

 

Таким образом, причиной вырождения плана транспортной задачи является наличие поставщиков и  потребителей с равными объемами погрузки и выгрузки или равными  объемами сумм погрузки и выгрузки по нескольким станциям в разнообразных  комбинациях. Такие случаи необходимо уметь находить для того, чтобы  правильно определять места для  нулевых поставок. В процессе решения  задачи возможны случаи, когда число  базисных клеток превышает величину «n + m – 1». Это означает появление ошибки вследствие того, что при построении опорного плана в какую-то клетку была введена не максимально возможная поставка.

Операция 2. Проверка плана на оптимальность.

Операция 2.1. Расчет потенциалов.

Проверка плана  транспортной задачи в описываемом  методе на оптимальность осуществляется с помощью потенциалов. Потенциалы – это такие числа, которые  по определенным правилам назначаются  каждой строке и каждому столбцу. Потенциалы строк обозначим u_i, потенциалы столбцов – v_j. Они могут принимать любые значения. Однако удобнее работать с положительными, целыми и относительно небольшими числами. Такой потенциал первоначально назначается любой строке или столбцу. Рекомендуем поступать следующим образом. Выберем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А₂В₃. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u₃ = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле

,                                                            (3.4)