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

Вернемся в диалоговое окно "Поиск решения". Изменим запись, приравняв в окне ограничений искомое количество продукции поставкам по договорам (рисунок 21):

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

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

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

По команде на ленте "Данные" - Анализ "что если" - Диспетчер сценариев - Отчет получим отчет по сценариям. Отредактируем отчет вручную по примеру, приведенному на рисунке 22:

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

Задача 2. Цех алкидных красок с производительностью 450 тонн продукта в месяц способен производить три разновидности красок: белой, синей и красной. Согласно договорам цех должен изготовить 40 тонн белой, 60 тонн синей и 80 тонн красной красок за месяц. Избыток краски сверх этого количества поступает в свободную продажу. В качестве сырья для изготовления красок используются четыре мастики в различных соотношениях. Цех располагает следующими запасами мастики: первой - 100 тонн, второй - 150 тонн, третьей - 120 тонн и четвертой - 180 тонн. Данные о расходе мастики на производство одной тонны каждой разновидности краски сведены в таблицу 4.

Таблица 4. Данные о расходе мастики

Требуется найти оптимальное (в смысле максимизации прибыли) количество каждого вида изготавливаемых красок при условии, что стоимости красок равны: белой - 13500 руб. , синей - 11300 руб. и красной 8200 руб. за тонну.

С помощью сценариев построить гистограммы и определить, насколько уменьшится прибыль, если цех будет работать не на полную мощность, а по договорному минимуму? Каков будет расход мастики в обоих случаях?

Решение. Таблица Excel формируется для этой задачи стандартным образом (рисунок 23):

Рисунок 23. Формирование таблицы данных

Неизвестные переменные помещаем в ячейки H3:H5, а целевую функцию - в ячейку G6. Ограничения вводим из условия задачи (рисунок 24):

Рисунок 24. Параметры поиска решений

Сохраним сценарий этого решения под именем "Краски_450". Далее во втором ограничении поставим знак "=" и сохраним сценарий под именем "Краски_180". По команде Данные - Анализ "что если" - Диспетчер сценариев - Отчеты - Структура выведем на лист отчет сценариев. Отредактированный отчет выглядит следующим образом (рисунок 25):

Рисунок 25. Отчет сценариев

Из отчета следует, что договорные поставки загружают мощности предприятия лишь на 40% и дают лишь 56,38% возможной выручки. При этом остаются невостребованными со склада запасы мастики, хранение которой также требует существенных расходов. По данным отчета построим гистограммы расхода мастики для двух вариантов производственного плана (рисунок 26):

Рисунок 26. Гистограмма расхода мастики

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

На примере рассмотренных экономических задач была продемонстрирована автоматизация их решения при помощи инструмента Поиск решения табличного процессора MS Excel.

2.2 Решение задач оптимизации с применением MATLAB

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

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

методы исследования функций классического анализа;

методы, основанные на использовании неопределенных множителей Лагранжа;

вариационное исчисление;

динамическое программирование;

принцип максимума;

линейное программирование;

нелинейное программирование.

В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

Минимизация унимодальной функции одной переменной. Функция одного переменного  называется унимодальной на отрезке , если имеется единственное значение  такое, что [25], [26]:

· -минимум  на ;

· строго убывает при ;

· строго возрастает при .

Для отыскания минимума унимодальной функции используется функция fminbnd. Алгоритм, реализованный ею, представляет собой комбинацию метода золотого сечения и обратной параболической интерполяции [27]. В простейшем варианте вызова кроме указателя на минимизируемую функцию fun задаются начало и конец интервала поиска: x=fminbnd(fun, a, b).

Пример 1. Использование функции fminbnd для поиска минимума функции humps (переводится как «горб»), входящей в ядро MATLAB. Данная функция задается формулой

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

>>fplot (@humps, [0, 3])

Из рисунка 27 следует, что минимум функции humps существует на отрезке [0.5, 1].

Для нахождения минимума функции нужно выполнить команду

>> fminbnd (@humps, 0.5, 1)

ans =

.63701067459059

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

>> [x, y]= fminbnd(@humps, 0.5, 1)=

0.63701067459059

y =

.25275412656431

Рисунок 27. График функции humps

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

[xmin, val, flag, output] = fminbnd (@humps, 0.5, 1)

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

>>[xmin, val, flag, output] = fminbnd (@humps, 0.5, 1)=

.63701067459059=

.25275412656431=

=: 7: 8: 'golden section search, parabolic interpolation': [1x112 char]

Пример 2. График функции  представлен на рисунке 28. На каждом из интервалов  и  эта функция унимодальна. Для нахождения ее минимумов на указанных интервалах и построения графика с выделением точек минимума составлена программа prog1.m:

function prog1=-2:0.1:3; yy=fun(xx);(xx, yy,'k-')on; grid;('x'); ylabel('y');

[x,f] = fminbnd(@fun,-2,0)(x,f, 'Marker', '.', 'MarkerSize', 20);

[x,f] = fminbnd(@fun,0,3)(x,f,'Marker', '.', 'MarkerSize', 20);

y=fun(x)=3*x.^4-4*x.^3-12*x.^2;

Запуск этой программы выдает следующие результаты:

x=

.0000

f=

.0000

x=

.0000

f=

.0000

Рисунок 28. Поиск минимума унимодальной функции

Многомерная безусловная минимизация. Задач поиска минимума вещественной функции векторного аргумента  называется безусловной, если на ее аргумент не наложено никаких ограничений. В противном случае, когда вектор x должен удовлетворять каким-то уравнениям и/или неравенствам, говорят об условной минимизации [28].

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

Функция fminsearch. Для поиска минимума функции нескольких переменных применяется функция fminsearch:

fminsearch (hFunction, x0)

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

В функции fminsearch используется так называемый алгоритм симплексного поиска, идея которого заключается в следующем. В окрестности стартовой точки n-мерного пространства строится симплекс - (n+1) точка в общем положении (никакие 3 точки не лежат на одной прямой, никакие 4 не лежат в одной плоскости и т. д.). Целевая функция измеряется в этих точках и та точка, в которой значение функции максимально, отбрасывается, а вместо нее в симплекс по определенным правилам вставляется другая точка. Процесс завершается, когда диаметр симплекса становится меньше заданного порога. Целевая функция может быть негладкой и даже разрывной [29]. Использование данной функции продемонстрировано в следующем примере.

Пример 3. Найти минимум функции

>> f2 = inline ('x(1)^2+x(2)^2', 'x')=function:(x) = x(1)^2+x(2)^2

>> xmin = fminsearch(f2, [1 1])=

.0e-004 *

-0.21023529262365 0.25484564932795

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

[xmin, val, flag, output] = fminsearch(hFun, x0)

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

>> [xmin, val, flag, output] = fminsearch(f2, [1 1])=

.0e-004 *

.21023529262365 0.25484564932795

=

.0915e-009

=

=: 38: 69: 'Nelder-Mead simplex direct search'

message: [1x196 char]

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

Банан Розенброка. Графически он представляет собой овраг с очень крутыми склонами, дно которого при «взгляде сверху» имеет форму параболы (рисунок 29) и плавно спускается к точке минимума x=[1;1], которой z=0. Ее линии уровня представляют собой изогнутые овалы (отсюда «банан»).

function f = Rosenbrock(x)

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

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

Для поиска минимума и построения линий уровня функции Розенброка была написана программа prog2.m (см. Приложение 2).

Найденный минимум:

x=

.0000

.0000

f=

.8161e-009

Функция fminunc. В том случае, когда функция fun(x) является достаточно гладкой, для поиска ее минимума можно воспользоваться функцией fminunc. Идея поиска минимума с помощью производных принадлежит Коши и заключается в следующем: градиент функции fun(x) в любой точке x есть вектор g, направленный в сторону наибольшего локального увеличения функции fun(x). Следовательно, для достижения минимума надо двигаться в направлении наискорейшего спуска - g. В более развитом варианте этого алгоритма используются также вторые производные, которые образуют так называемую матрицу Гессе (гессиан) H. При помощи формулы Тейлора строится локальная квадратичная аппроксимация целевой функции в окрестности текущей точки :

.

Минимум выражения в правой части (если он существует) достигается при векторе смещения , который удовлетворяет системе уравнений . Такой способ выбора направления называется методом Ньютона [30]. Иногда на вектор смещения накладывается ограничение  при специально подобранном  - в этом случае говорят о методе доверительного интервала.

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

Ее линия уровня при 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]. Затем левая часть каждого уравнения добавляется к целевой функции с некоторым множителем, эти множители и величины  включаются в число переменных. Для модифицированной таким образом функции решается задача безусловной минимизации.