Рефетека.ру / Эк.-мат. моделирование

Курсовая работа: Сравнительный анализ методов оптимизации

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет


Кафедра САПР


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине «Теория принятия решений»


Тема: «Сравнительный анализ методов оптимизации»


Караганда 2009

Введение


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

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


1. Основы теории оптимизации


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

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

Построение математических моделей оптимизации можно условно разбить на следующие основные этапы.

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

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

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


f(xi) ®min (max), хiО U


где f(xi) – целевая функция, а U – допустимое множество, заданное ограничениями на управляемые переменные. Значение параметров f(xi) ®min (max) при которых достигается min (max), называется оптимальным решением.


2. Численные методы одномерной безусловной оптимизации


Число х* О U называется точкой глобального (абсолютного) минимума функции f (x) на множестве U, если f (x*) Ј f (x) для всех хО U.

Значение f * = f (x*) = Сравнительный анализ методов оптимизации называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.

Множество всех точек минимума f (x) на U будем в дальнейшем обозначать через U*.

Число Сравнительный анализ методов оптимизации ОU называется точкой локального минимума функции f (x), если Сравнительный анализ методов оптимизациидля всех xОU, достаточно близких к Сравнительный анализ методов оптимизации, т.е. если существует e > 0 такое, что это неравенство выполняется для любогоСравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации.

Глобальный минимум f (x) является и локальным минимумом, а обратное, неверно.

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

Функция f (x) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа a и b, Сравнительный анализ методов оптимизации, такие, что:

1) если а < a, то на отрезке [a; a] функция f (x) монотонно убывает;

2) если b < b, то на отрезке [b; b] функция f (x) монотонно возрастает;

3) при х О [a; b] f (x) =f * = Сравнительный анализ методов оптимизации.

Возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на.

Основные свойства унимодальных функций:

1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].

2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] Сравнительный анализ методов оптимизации [а; b].

3. Пусть f (x) Сравнительный анализ методов оптимизацииQ [а; b] и Сравнительный анализ методов оптимизации. Тогда:

если Сравнительный анализ методов оптимизации, то x* Сравнительный анализ методов оптимизации [a; x2];

если Сравнительный анализ методов оптимизации, то x* Сравнительный анализ методов оптимизации [x1; b],

где х* – одна из точек минимума f (x) на отрезке [a; b].

Из численных методов одномерной безусловной оптимизации рассмотрим два:

метод дихотомии

метод золотого сечения


2.1 Метод дихотомии


В этом методе точки x1 и х2 располагаются близко к середине очередного отрезка [а; b], т.е:


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


где d > 0 – малое число. При этом отношение длин нового и исходного отрезков Сравнительный анализ методов оптимизации близко к 1/2, этим и объясняется название метода.

Отметим, что для любых точек x1 и х2 величина t > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска х*.

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство Сравнительный анализ методов оптимизации.

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить x1 и х2 по формулам (2.11). Вычислить f (x1) и f (x2).

Шаг 2. Сравнить f (x1) и f (x2). Если Сравнительный анализ методов оптимизации, то перейти к отрезку [а; x2], положив b = x2 , иначе – к отрезку [x1; b], положив а = x1 .

Шаг 3. Найти достигнутую точность Сравнительный анализ методов оптимизации Если Сравнительный анализ методов оптимизации, то перейти к следующей итерации, вернувшись к шагу 1. Если Сравнительный анализ методов оптимизации, то завершить поиск х*


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


Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1–t (рис.2.2).


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

Рис. 2.2.-Определение пробных точек в методе золотого сечения

Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2ў = 1–t нового отрезка [0; т]. Чтобы точки х2 = t, и х2ў = 1–t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство Сравнительный анализ методов оптимизации или Сравнительный анализ методов оптимизации, откуда находим положительное значение Сравнительный анализ методов оптимизации… Таким образом, х1 = 1–t = Сравнительный анализ методов оптимизации, Сравнительный анализ методов оптимизации.

Для произвольного отрезка [а; b] выражения для пробных точек примут вид


Сравнительный анализ методов оптимизации; Сравнительный анализ методов оптимизации.


1. Точки x1 и х2 обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b].

2. На каждой итерации исключения отрезков с пробными точками одна из них Сравнительный анализ методов оптимизации переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х2], то на него переходит пробная точка Сравнительный анализ методов оптимизации исходного отрезка, становясь его второй пробной точкой (х2’= х1) (рис. 2.2). В случае перехода к отрезку [х1; b] пробная точка Сравнительный анализ методов оптимизации исходного отрезка становится первой пробной точкой отрезка [х1; b].

3. Легко проверить, что х1=а+b–х2 , и x2=а+b–х1. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания.

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

На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении Сравнительный анализ методов оптимизации, поэтому в результате п итераций его длина становится Сравнительный анализ методов оптимизации. Таким образом, точность en определения точки х* после п итераций находят из равенстваСравнительный анализ методов оптимизации, а условием окончания поиска точки х* с точностью e служит неравенство en Ј e.


2.3 Пример решения методами дихотомии и золотого сечения


Дана функция Сравнительный анализ методов оптимизации, где d=2, e=1

Необходимо найти минимум на отрезке [a,b], где Сравнительный анализ методов оптимизации, Сравнительный анализ методов оптимизации, т.е. на отрезке [7.23,8.21]

Составить программу, которая выдаст число итераций при точности ε=0,001

Решить двумя методами: дихотомии и золотого сечения


Решение методом дихотомии:


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

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

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

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

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

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

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

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

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

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

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

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

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


Шаг 1:


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

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



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

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



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

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


Шаг 2:


Так как f1<f2


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

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



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


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


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

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



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

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



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

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


Шаг 3:

Так как f1<f2

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

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

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


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


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


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


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

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



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

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


Решение методом золотого сечения:


Шаг 1:

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

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

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

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

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

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

Шаг 2:

Так как f1<f2

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

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

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

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

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

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

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

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

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

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

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

Шаг 3:

Так как f1<f2

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

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

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

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

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

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

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

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

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

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

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



Так как f1<f2

Листинг программы реализующей методы дихотомии и золотого сечения представлен в приложении А


3. Численные методы многомерной безусловной оптимизации


Рассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х) ® min, xО En, которые опираются только на вычисление значений функции f (х), т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишь иметь возможность вычислять или измерять значения f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.


3.1 Поиск точки min методом правильного симплекса


В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 – правильного тетраэдра.

Если х0 – одна из вершин правильного симплекса в En то координаты остальных n вершин х1 ,..,хn можно найти, например, по формулам:


Сравнительный анализ методов оптимизации (3.1)


где d1 Сравнительный анализ методов оптимизации, d2 Сравнительный анализ методов оптимизации, a– длина ребра. Вершину х0 симплекса, построенного по формулам (3.1), будем называть бaзовой.

По известному симплексу можно построить новый симплекс отрaжением какой–либо вершины, например, хk симметрично относительно центра тяжести хc остальных вершин симплекса.


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


Пусть задана функция f(x,y) ® min и начальный базис (x0,y0).

Новая и старая вершины связаны соотношением:


Сравнительный анализ методов оптимизации, где xcСравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации, где уcСравнительный анализ методов оптимизации(3.2)


Вычисляем значение функции в точках f(A), f(B), f(D) (пусть f(A)<f(B)<f(D)) и присваиваем им номера в порядке возрастания A-1, B-2, D-3.

Вершину с наибольшим номером отражаем относительно центра тяжести стороны 1-2

Координаты вершины Е:


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

Сравнительный анализ методов оптимизации(3.3)


Затем вычисляем f(E) и сравниваем f(E) и f(D). Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми.


3.2 Поиск точки min методом деформируемого симплекса


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


Сравнительный анализ методов оптимизации(3.5)


Так как величина a О (0; 1), то выбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi: a = 1/2, b = 1 и g =2.


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


Рис. 3.2. Пробные точки z1,z2,z3,z4 для перехода к новому симплексу


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


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



Рис. 3.3. Новые симлексы полученные в результате процедур сжатия (а,б); отражения (в); растяжения(г).


Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг 0 – Шаг 3 Аналогичны методу правильного симплекса.

Шаг 4. Найти Сравнительный анализ методов оптимизациии пробные точки zk , k=1, …, 4 пo формулам (3.5). Найти f (z*)= min f (zk). Если f (z*) < f (zn). то положить xn=z* и перейти к шагу 2. Иначе – перейти к шагу 5.


3.3 Поиск точки min методом циклического покоординатного спуска


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


Этот метод заключается в последовательной минимизации целевой функции f (x) сначала по направлению первого базисного вектора е1, затем второго – е2 и т.д. После окончания минимизации по направлению последнего базисного вектора еn цикл повторяется.

Опишем этот алгоритм.

Шаг 0. Выбрать х О En , критерий достижения точности, величину e. Найти f (x), положить j= 1.

Шаг 1. Решить задачу одномерной минимизации Ф(a) = f (х + aеj)® min, a О R, т.е. найти a*. Положить Сравнительный анализ методов оптимизации= х +a*еj, вычислить f (х).

Шаг 2. Если j < п, то положить х =Сравнительный анализ методов оптимизации, j=j+1 и перейти к шагу 1, иначе – перейти к шагу 3.

Шаг 3. Проверить условие достижения точности ||х–Сравнительный анализ методов оптимизации|| < e


3.4 Поиск точки min методом Хука – Дживса


Этот алгоритм содержит две основные процедуры:

а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);

б) перемещение в направлении убывания.

Опишем алгоритм исследующего покоординатного поиска из заданной точки х с приращениями по каждой координате Dj , j = 1, …, n

Шаг 1. Положить Сравнительный анализ методов оптимизации = x , i = 1.

Шаг 2. Сделать пробный шаг y=Сравнительный анализ методов оптимизации– Dje j, где e j –j–й базисный вектор. Если f (Сравнительный анализ методов оптимизации) Ј f (y), то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Сделать пробный шаг y=Сравнительный анализ методов оптимизации+Dje j . Если f (Сравнительный анализ методов оптимизации) Ј f (y), то перейти к шагу 5, иначе – к шагу 4.

Шаг 4. Положить Сравнительный анализ методов оптимизации= у.

Шаг 5. Положить j = j + 1. Если j Ј n, то перейти к шагу 2. В противном случае исследующий поиск окончен – получена точка Сравнительный анализ методов оптимизации для которой f (Сравнительный анализ методов оптимизации) < f (y), если Сравнительный анализ методов оптимизации № х.


3.5 Пример решения методами правильного симплекса, деформируемого симплекса, покоординатного спуска, Хука – Дживса


Дана функция Сравнительный анализ методов оптимизации, с=7; d=7.

Найти минимум функции с точностью ε=0,001

Метод правильного симплекса

Выбираем длину стороны треугольника l=10ε=0,0001

Вершины треугольника находим следующим образом:


A(Сравнительный анализ методов оптимизации);

B(Сравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации);

D(Сравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации).

A(1,065; 0,918);

B(1,07,0,927);

D(1,075,0,918).


Шаг 0


F(A)=10,903; F(B)=11,081; F(D)=11,051.

F1<F2<F3:

F1=F(A); F2=F(D); F3=F(B).

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


Отражаем вершину 3 относительно центра тяжести.


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

F(E)=10,873.


Значение функции в найденной точке меньше, значения функции в точке 1, поэтому принимаем новый симплекс (1,2,E).

Шаг 1

F(1)=10,903; F(2)=11,081; F(E)=10,873.

F1<F2<F3:

F1=F(E); F2=F(1); F3=F(2).

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


Отражаем вершину 3 относительно центра тяжести.


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

F(E)=10,726.


Значение функции в найденной точке меньше, значения функции в точке 1, поэтому принимаем новый симплекс (1,2,E).


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

Сравнительный анализ методов оптимизации.


В результате получаем x1=0,125, x2=0,208, f(x1, x2)=-0,41.

Метод деформируемого симплекса

Выбираем длину стороны треугольника l=5ε=0,005

Вершины треугольника находим следующим образом:


A(Сравнительный анализ методов оптимизации);

B(Сравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации);

D(Сравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации).

A(1,065; 0,918);

B(1,07,0,927);

D(1,075,0,918).


Принимаем коэффициенты выбора пробных точек k1=0,5, k2=1, k3=2.

Шаг 0


F(A)=10,903; F(B)=11,081; F(D)=11,051.

F1<F2<F3:

F1=F(A); F2=F(D); F3=F(B).


Находим центр тяжести вершины 3 относительно вершин 1 и 2:


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


Выбираем пробные точки:


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

F(z1)=10,966.

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

F(z2)=11,018.

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

F(z3)=11,044.

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

F(z3)=11,097.

Значение функции в z1 точке меньше, значения функции в точке 3, поэтому принимаем новый симплекс (1,2,z1).

Шаг 1


F(1)= 10,903; F(2)= 11,051; F(z1)=10,966.

F1<F2<F3:

F1=F(1); F2=F(z1); F3=F(2).

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


Выбираем пробные точки:


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

F(z1)=10,955.

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

F(z2)=10,998.

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

F(z3)=11,019.

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

F(z3)=11,062.

Значение функции в точке z1 меньше, значения функции в точке 3, поэтому принимаем новый симплекс (1,2,z1).


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

Сравнительный анализ методов оптимизации.


В результате получаем x1=-0,012, x2=0,419, f(x1, x2)=-0,014.

Метод покоординатного спуска


(1,065; 0,918).

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

α=5ε=0,005.


Шаг 1

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


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

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

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


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


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

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

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

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


Получим x1=0,012, Сравнительный анализ методов оптимизации

Шаг 2

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


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

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

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

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

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

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

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

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


Получим x2=0,199, Сравнительный анализ методов оптимизации

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

В результате получаем x1=0,117, x2=0,189, f(x1, x2)=-0,411.

Метод Хука-Дживса


x0: (1,065; 0,918).

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

Δ1=5*ε=5*0,001, Δ2=5*ε=5*0,001.

λ=2.


Шаг 1

Принимаем k1=-1, k2=-1 – коэффициенты, определяющие направление поиска.


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

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

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


В данном направлении функция убывает.

Шаг 2

Принимаем k1=-1, k2=-1.


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

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

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


В данном направлении функция убывает.

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

В результате получаем x1=0,115, x2=0,198, f(x1, x2)=-0,411.


4. Основы линейного программирования


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


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


Примечание: если переменных две, то задача может быть решена и геометрически.

Точка оптимального решения является крайней точкой пересечения выпуклых множеств,


4.1 Симплекс-метод решения задачи ЛП


Допустим, что есть базисное решение. Не трудно заметить, что в качестве базисного решения можно принять:


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


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

Предполагаем, что базисная точка найдена, тогда:


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

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

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

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

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

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

Сравнительный анализ методов оптимизации – значение функции в базисной точке (базисе).


Тогда значение функции:


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

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


Тогда в скалярной форме:


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


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


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

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


Если Сравнительный анализ методов оптимизации, то Сравнительный анализ методов оптимизации быть не может, следовательно Сравнительный анализ методов оптимизации, т.к. при отрицательном коэффициенте Сравнительный анализ методов оптимизации может стать отрицательным.

Это условие необходимое.

Max значение базисной переменной определяется:

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

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


где Сравнительный анализ методов оптимизации – номер столбца, который выводится из базиса.

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

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

по известному базисному решению строятся матрицы и находим Сравнительный анализ методов оптимизации;

вычисляется симплекс-разности. Из них выделяются положительные наибольшие. Соответствующая переменная вводится в базис;

для выбора выводимой переменной из базиса вычисляется Сравнительный анализ методов оптимизации и max значение новой базисной переменной Сравнительный анализ методов оптимизации

Вычисляются значения новых базисных переменных:


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


4.2 Пример решения задач ЛП симплекс – методом


Дана функция Сравнительный анализ методов оптимизации и ограничения


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


a=3, b=6, c=4, k подобрать таким образом, чтобы область была пятиугольной.

Графическое решение задачи линейного программирования

Чтобы получить пятиугольную область допустимых значений выберем k=11.2.

Подставив коэффициенты a, b, c, k, получим функцию


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

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


Построим область допустимых значений


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


Рисунок 4.1 – Область допустимых значений


Чтобы получить максимум целевой функции будем ее переносить параллельно самой себе до пересечения с крайней точкой области допустимых значений. В данном случае максимум находится в точке пересечения функций 6x1+x2=12 и 2x1+4x2=11,2.

Решим систему уравнений:

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

Получим точку максимума целевой функции:

Значение функции в этой точке f(x1,x2)=15,927

Решение задачи линейного программирования симплекс-методом

Приведем задачу к стандартной форме записи:


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

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


Начальный базис y0(0 0 8 12 11.2).

Процедура поиска оптимальной точки симплекс-методом сведена в таблицу 1.


Таблица 1. Симплекс-таблица

Номер итерации Базисные переменные Значение y1 y2 y3 y4 y5 отношения
0 y3 8 1 3 1 0 0 0,125

y4 12 6 1 0 1 0 0,5

y5 11,2 2 4 0 0 1 0,17857143

-f' 0 6 3 0 0 0
1 y3 6 0 2,833333 1 -0,16667 0 0,4722

y1 2 1 0,166667 0 0,166667 0 0,0833

y5 7,2 0 3,666667 0 -0,33333 1 0,5093

-f' -12 0 2 0 -1 0
2 y3 0,436363636 0 0 1 0,090909 -0,77273

y1 1,672727273 1 0 0 0,181818 -0,04545

y2 1,963636364 0 1 0 -0,09091 0,272727

-f' -15,92727273 0 0 0 -0,81818 -0,54545

На шаге 2 нет положительных коэффициентов в симплекс разности, значит, решение прекращаем.

Получаем оптимальное значение целевой функции


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


5. Определение оптимальных параметров технического объекта


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


Рисунок 5.1-Модель сосуда


Параметры сосуда (рис.5.1):

Высота цилиндров – h1

Высота параллелепипеда – h2

Высота усеченного конуса – h3

Длина параллелепипеда – а

Ширина параллелепипеда – а

Радиус нижнего основания усеченного конуса – R

Радиус верхнего основания усеченного конуса – r

Соотношения параметров:


2h1 = 2h2 = h3 = H

a = 2R = 4r = x


Для того, чтобы рассчитать максимальный объем при заданной площади поверхности надо найти общую площадь сосуда

Площадь поверхности цилиндра: Сравнительный анализ методов оптимизации

Площадь поверхности параллелепипеда: Сравнительный анализ методов оптимизации

Площадь поверхности усеченного конуса:

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

Общая площадь боковой поверхности:


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


При заданной площади поверхности S=10 м2 выразим H из последнего уравнения


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


Найдем объем сосуда

Объем цилиндра: Сравнительный анализ методов оптимизации

Объем параллелепипеда: Сравнительный анализ методов оптимизации

Объем усеченного конуса: Сравнительный анализ методов оптимизации


Общий объем сосуда равен:


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


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

Рисунок 5.2


Подставив H в последнее уравнение, получим зависимость объема сосуда от одного параметра x. Зависимость и график функции представлен на рисунке 2. Область определения функции 1 четверть, т.к. объем и радиус – положительные величины. Для нахождения максимума функции воспользуемся методом золотого сечения.

Таким образом, максимальный объем при площади поверхности равной

10 м2 равен 1,19 м3


Заключение


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

проведен анализ методов однопараметрический безусловной оптимизации;

проведен анализ методов многопараметрический безусловной оптимизации;

были разобраны основы линейного программирования;

был смоделирован и оптимизирован трёхмерный объект;


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


Дегтярев Ю.И., «Исследование операций», Москва 1986;

Турчак Л.И., «Основы численных методов», Москва 1987;

Мудров А.Е., «Численные методы», Томск 1991;

Щетинин Е.Ю., «Математические методы оптимизации»;

40


Похожие работы:

  1. • Сравнительный анализ методов оптимизации
  2. • Сравнительный анализ методов оптимизации
  3. • Линейное и нелинейное программирование
  4. • Продвижение программного продукта на рынке
  5. • Вопросы выбора асcортимента товара для универмагов и торговых ...
  6. • Анализ и оценка эффективности производства
  7. • Управление процессами обслуживания на предприятиях питания
  8. • Внутренний финансовый контроль отраслей, предприятий ...
  9. • Производственно-экономическая деятельность ...
  10. • Учет и анализ денежных средств на примере ...
  11. • Государственное управление в современной России
  12. • Анализ и оценка процесса управления денежными ...
  13. • Анализ и оценка предпринимательской деятельности ...
  14. • Экзаменационные билеты по методам оптимизации за весенний ...
  15. • Методология сравнительного правоведения
  16. • Методы сравнительного анализа деятельности посреднических ...
  17. • Сравнительный анализ численных методов
  18. • Сравнительное правоведение: общая характеристика
  19. • Сравнительный исторический метод в языкознании
Рефетека ру refoteka@gmail.com