Решение задач оптимизации с применением пакетов прикладных программ

Пусть имеется функция

Ее линия уровня при f=0 представляет собой известную в геометрии кривую - декартов лист. Подключим к программе вычисления значения функции операторы для нахождения градиента g и гессиана H. Сообщим об этом в списке управляющих параметров для функций минимизации:

Options = optimset('Display','final','GradObj','on','Hessian','on');

Значение параметра Display = final означает, что все промежуточные выдачи, кроме заключительной, блокируются. Возьмем стартовую точку для поиска минимума x0=[2; 2]. Обращения к функции fminunc выполним в форме, позволяющей получить на выходе также значения градиента и гессиана.

[x, f1, e_flag, out, grad, hes] = fminunc(@Descartes,x0,options)

Построение линий уровня, фиксация начальной точки и найденного минимума (рисунок 30) выполнены с помощью программы prog 3.m (см. Приложение 2).

Условная минимизация. Если при поиске минимума вещественной функции векторного аргумента на аргумент наложены те или иные ограничения в виде уравнений и/или неравенств, говорят об условной минимизации. Основной метод решения таких задач основан на использовании множителей Лагранжа. Каждое неравенство вида превращается в уравнение (слагаемое заведомо неотрицательно) [30]. Затем левая часть каждого уравнения добавляется к целевой функции с некоторым множителем, эти множители и величины включаются в число переменных. Для модифицированной таким образом функции решается задача безусловной минимизации.

Рисунок 30. Декартов лист

Функция fmincon. Для решения задачи условной минимизации функции fun(x) при наличии линейных ограничений оптимизации (А - матрица, b - вектор) используется функция fmincon, обращение к которой требует здания начальной точки x0:

x=fmincon(fun,x0,A,b)

Найдем минимум функции Розенброка при ограничении , задающем полуплоскость.

Определим матрицу , вектор , начальную точку (эта точка удовлетворяет ограничению) и обратимся к функции fmincon.

Графические результаты представлены на рисунке 31. Они получены с помощью программы ros_tst.m (см. Приложение 2).

Рисунок 31. Минимум функции Розенброка

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

Заключение

Система MATLAB представляет собой уникальный сплав универсальных программных и алгоритмических средств с широкой гаммой специализированных приложений. Входной язык и среда программирования MATLAB очень близки к современным системам визуального программирования на базе универсальных алгоритмических языков типа Basic, C++, Java, Object Pascal. По ряду аспектов MATLAB уступает указанным системам (режим интерпретации, небольшой запас визуальных компонентов). Однако с его библиотекой численных методов ни по объему, ни по качеству не может сравниться ни одна из систем программирования. Кроме того, в пакете MATLAB тщательно отработаны средства визуализации результатов вычислений и отображения различных графических объектов. На базе ядра MATLAB созданы многочисленные расширения, обеспечивающие моделирование и анализ систем в разнообразных сферах человеческой деятельности.

Для современного инженера и научно-технического работника MATLAB является незаменимым инструментом моделирования и исследования различных систем, прежде всего, за счет готовых решений. Но не менее важным является создание новых приложений с привлечением программных и алгоритмических средств MATLAB.

Первый раздел дипломной работы посвящен системе MATLAB, здесь рассматриваются такие вопросы, как:

- вычисления в интерактивном режиме;

- графика в системе MATLAB;

- программирование М-функций;

- создание приложений.

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

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

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

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

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

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

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

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

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

Многие оптимизационные экономические задачи можно решить сведением к задаче линейного программирования. В свою очередь, решение задачи линейного программирования можно автоматизировать с помощью надстройки "Поиск решения" в MS Excel.

Традиционными задачами, решаемыми с помощью настройки «Поиск решений» являются:

- Ассортимент продукции. Сколько можно выпустить определенного товара при ограничении сырья.

- Штатное расписание. Как составить штатное расписание для достижения лучшего результата и при наименьших расходах.

- Планирование перевозок. Как минимизировать затраты на перевозки.

- Составление смеси. Как составить смесь заданного качества при наименьших затратах.

Во втором разделе дипломной работы решены некоторые экономические задачи с применением данной надстройки в табличном процессоре MS Excel 2010.

В состав приложения Excel 2010 входит новая версия надстройки "Поиск решения", позволяющая выполнять анализ "что если" и находить оптимальные решения. Последняя версия этой надстройки обладает улучшенным пользовательским интерфейсом Evolutionary Solver, основанным на алгоритмах генетического анализа, для работы с моделями, в которых используются любые функции Excel. В ней предусмотрены новые глобальные параметры оптимизации, улучшенные методы линейного программирования и нелинейной оптимизации, а также новые отчеты о линейности и допустимости.

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

- Изучение функциональных возможностей MS Excel.

- Изучение вычислительных возможностей системы MATLAB.

- Изучение графических возможностей системы MATLAB.

- Освоение средств программирования в системе MATLAB.

- Изучение численных методов решения задач одномерной оптимизации.

- Изучение численных методов решения задач многомерной оптимизации.

- Построение математических моделей некоторых экономических задач оптимизации.

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

- Численная реализация построенной математической модели в табличном процессоре MS Excel 2010.

- Численная реализация методов оптимизации в системе MATLAB.

В Приложении 1 представлены этапы решения оптимизационной задачи производства при помощи надстройки Поиск решения в табличном процессоре MS Excel. В Приложении 2 представлены следующие программы, написанные в среде MATLAB:

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

2. Многомерная безусловная минимизация. Программа поиска минимума и построения линий уровня функции Розенброка.

3. Многомерная условная минимизация. Программа поиска минимума функции Розенброка на полуплоскости.

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

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

1 Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1988. - 552 с.

2 Аладьев В.З., Шишаков М.Л. Введение в среду пакета Mathematica 2.2 - М.: Информационно-издательский дом "Филинъ", 2011. - 368 с.

3 Говорухин В.Н., Цибулин В.Г. Введение в Maple. Математический пакет для всех. - М.: Мир, 2007. - 208 с.

4 Дьяконов В.П. Справочник MathCAD PLUS 6.0 PRO - М.: “СК Пресс”, 2010. - 336 с.

5 Эрдниев П.М. Эрдниев Б.П. Укрупнение дидактических единиц в обучении математике: книга для учителя. - М.: Просвещение, 2008. - 271с.

6 И.Семакин, Л.Залогова и др. Информатика и ИКТ, базовый курс, 9 класс. М.: БИНОМ. Лаборатория знаний, 2007. - 32 с.

7 Решение уравнений средствами MS Excel. Методические указания к лабораторным работам по дисциплине "Математика и информатика". - М.: БИНОМ. Лаборатория знаний, 2012. - 282 с.

8 Курицкий Б. Поиск оптимальных решений средствами MS Excel 7.0. - СПб.: BHV - Санкт-Петербург, 2011. - 384 с.

9 Гусева О.Л., Миронова Н.Н. Практикум по MS Excel. - М.: Финансы и статистика, 2009. - 160 с.

10 Ануфриев И.Е. MATLAB 5.3/6.х. - Санкт-Петербург: БХВ-Петербург, 2002. - 444 с.

11 Потемкин В.Г. MATLAB 5 для студентов. - М.: ДИАЛОГ-МИФИ, 1998. - 314 с.

12 Дьяконов В.П. MATLAB 6. - СПб.: Питер, 2001. - 592 с.

13 Мартынов Н.Н. Иванов А.П. MATLAB 5.x. Вычисления, визуализация, программирование. - М.:КУДИЦ-ОБРАЗ, 2000. - 332 с.

14 Потемкин В.Г. Инструментальные средства MATLAB 5.х. - М.: ДИАЛОГ-МИФИ, 2000. - 333 с.

15 Гультяев А. Визуальное моделирование в среде MATLAB: учебный курс. СПб.: Питер, 2000. - 430 с.

16 Мартынов Н.Н. Введение в MATLAB 6.x. - М.:КУДИЦ-ОБРАЗ, 2002. - 352 с.

17 Начало работы с MATLAB - http://matlab.exponenta.ru/ml/book3/index.php

18 Минько А.А. Принятие решений с помощью Excel. Просто, как дважды два. - М.:Эксмо, 2007. - 240 c.

19 Волоскар А. Задачи оптимизации в MS Excel - http://exsolver.narod.ru/

20 Пакулин В. Решение задач оптимизации управления с помощью MS Excel 2010 - http://www.intuit.ru/studies/courses/4751/1020

21 Литвинова О.Н, Цыганкова С.А. Экономико-математические методы и модели - http://softacademy.lnpu.edu.ua/Programs/EMM/1_1_1.html

22 Айсагалиев С.А., Айсагалиева С.С. Лекции по методам оптимизации. - Алматы: Гылым, 1996. - 379 с.

23 Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. - М.: Высшая школа, 2002. - 542 с.

24 Абрамов Л.М., Капустин В. Ф. Математическое программирование. - Л.: Изд. ЛГУ, 1979. - 183 с.

25 Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 436 с.

26 Кетков Ю.Л., Кетков А.Ю., Шульц М.М. MATLAB 7: программирование, численные методы. - СПб.: БХВ-Петербург, 2005. - 752 c.

27 Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. - М.: Мир, 1985. - 509 с.

Приложение 1

Решение задач оптимизации управления с помощью MS Excel 2010

Этапы решения задачи 1.

1. Вставка формул в таблицу MS Excel

2. Сформированная таблица MS Excel

3. Заполнение диалога "Параметры поиска решения"

4. Результаты поиска решения

5. Решение для обязательных поставок

6. Отредактированный отчет по двум сценариям остатков материалов

7. Остатки материалов на складе для двух вариантов плана, %

Приложение 2

Программы решения задач оптимизации в среде MATLAB

1. Программа prog2.m:

function prog2

X0=-3:0.1:3; Y0=-2:0.1:5;

[X Y]=meshgrid(X0,Y0);

s=size(X); Z=zeros(s);

for i = 1:s(1)

for j = 1:s(2)

Z(i,j)=Rosenbrock([X(i,j); Y(i,j)]);

end

end

axes('Xlim', [-3 3], 'Ylim',[-2 5]);

axis equal; grid off; hold on;

v=1:2:10; V=10:4:20;

contour (X,Y,Z,[v V]);

xlabel('x1'); ylabel('x2')

x0=[-2; 2];

line(x0(1),x0(2),'Marker','.','MarkerSize',10);

[x,f]=fminsearch('5*(x(2)-x(1)^2)^2+(1-x(1))^2',x0)

line(x(1),x(2),'Marker','.','MarkerSize',20);

plot([x0(1),x(1)],[x0(2),x(2)],'k-');

colormap copper

2. Программа prog 3.m:

function prog3

axes('Xlim', [-1.5 2.5],'Ylim',[-1.5 2.5]);

axis equal; grid off; hold on;

xlabel('x1'); ylabel('x2'); colormap copper

X0=-1.5:0.05:2.5;

[X Y]=meshgrid(X0);

s=size(X); Z=zeros(s);

for i=1:s(1)

for j=1:s(2)

Z(i,j)=Descartes([X(i,j); Y(i,j)]);

end

end

V=-0.8:0.2:1; contour(X,Y,Z,V);

options=...

optimset('Display','final','GradObj','on','Hessian','on');

x0=[2; 2];

line(x0(1),x0(2),'Marker','.','MarkerSize',10);

[x, f1, e_flag, out, grad, hes] = fminunc(@Descartes,x0,options);

line(x(1),x(2),'Marker','.','MarkerSize',20);

plot([x0(1),x(1)],[x0(2),x(2)],'k-');

function [f, g, H]=Descartes(x)

f=x(1)^3+x(2)^3-3*x(1)*x(2);

if nargout>1

g=[3*(x(1)^2-x(2)); 3*(x(2)^2-x(1))];

end

if nargout>2

H=[6*x(1) -3; -3 6*x(2)];

End

End

3. Программа ros_tst.m:

function ros_tst

X0=-5:0.1:3;

Y0=0:0.1:7;

[X Y]=meshgrid(X0,Y0);

s=size(X); Z=zeros(s);

for i=1:s(1)

for j=1:s(2)

x=[X(i,j); Y(i,j)];

z=Rosenbrock(x);

Z(i,j)=z;

end

end

V=1:10;

contour(X,Y,Z,V);

hold on; grid off;

x1=-5:5; x2=0:7;

xlabel('x1'); ylabel('x2')

plot([-4 3], [0 7], 'k-');

x0=[-3; 4]; graf(x0) %#1

x0=[0; 1]; graf(x0) %#2

function graf (x0)

A=[1 -1]; b=[-4];

options=[];

line(x0(1),x0(2), 'Marker','.','MarkerSize',10 );

[x, fval]=fmincon(@Rosenbrock,x0,A,b)

line(x(1),x(2),'Marker','.','MarkerSize',20);

plot([x0(1),x(1)],[x0(2),x(2)],'k-');

function f=Rosenbrock(x)

f=5*(x(2)-x(1)^2)^2+(1-x(1))^2;x(1)^2;

Размещено на Allbest.ur