230 подписчиков

ТЕХНОЛОГИИ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ В MATLAB

9 декабря 20199 дек 2019

868

5 мин

В задачах оптимизации вычисляются значения параметров некоторой функции y=f(x1,x2,…,xn), при которых она принимает наилучшее значение (максимальное или минимальное). При этом предполагается, что на значения аргументов функции (x) наложены ограничения. Эту функцию называют целевой функцией, а набор количественных значений между переменными, выражающих определенные требования к параметрам задачи в виде уравнений или неравенств называют системой ограничений.

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

f(x) = a1x1+ a2x2+ … anxn> max (min)

при условии, что Аx ≤ b ,

lb≤ x ≤ ub,

где f(x) – целевая функция, x – аргументы функции, a - коэффициенты при аргументах, A – матриц

f(x) = a1x1+ a2x2+ … anxn> max (min)

при условии, что Аx ≤ b ,

lb≤ x ≤ ub,

где f(x) – целевая функция, x – аргументы функции, a - коэффициенты при аргументах, A – матриц

В задачах оптимизации вычисляются значения параметров некоторой функции y=f(x1,x2,…,xn), при которых она принимает наилучшее значение (максимальное или минимальное). При этом предполагается, что на значения аргументов функции (x) наложены ограничения. Эту функцию называют целевой функцией, а набор количественных значений между переменными, выражающих определенные требования к параметрам задачи в виде уравнений или неравенств называют системой ограничений.
Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называют математической моделью задачи оптимизации.

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

В общем виде математическая модель задачи может быть представлена в виде:
f(x) = a1x1+ a2x2+ … anxn> max (min)
при условии, что Аx ≤ b ,
lb≤ x ≤ ub,
где f(x) – целевая функция, x – аргументы функции, a - коэффициенты при аргументах, A – матрица коэффициентов, b – вектор, содержащий значения ограничений, lb и ub – вектора ограничений на значения аргументов целевой функции.

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

В зависимости от характера решаемой задачи функция linprog может применяться в различных синтаксических вариантах. Эти варианты отличаются набором входных и выходных аргументов. Варианты синтаксиса, различающиеся набором входных аргументов:
- x = linprog(f,A,b) - вычисляет min f *x при условии, что A*x <= b;
- x = linprog(f,A,b,Aeq,beq) - решает указанные выше задачу при условии дополнительных ограничений в виде равенств Aeq*x = beq, если таких равенств нет, то параметры не указываются;
- x = linprog(f,A,b,Aeq,beq,lb,ub) – выполняет решение при условии ограничений на нижние и верхние границ для вычисляемых переменных х, так что решение всегда находится в диапазоне lb <= x <= ub. Если нет неравенств, то устанавливается Aeq=[] и beq=[];
- x = linprog(f,A,b,Aeq,beq,lb,ub,x0) - выполняет решение с использованием начальной точки х0.;
- x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) – выполняет решение с определенными в параметре options параметрами оптимизации.

Структурный аргумент options содержит параметры оптимизационных опций, используемых в linprog. Часть параметров применимы ко всем алгоритмам, некоторые используются только для крупномасштабного алгоритма, а другие применимы только к среднемасштабным алгоритмам:
- LargeScale - в случае установки 'on' используется крупно-масштабный алгоритм, если это возможно, для использования средне-масштабного алгоритма устанавливается 'off';
- Medium-Scale и Large-Scale - используются как для средне-масштабного, так и крупно-масштабного алгоритмов.

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

Варианты синтаксиса, различающиеся набором выходных аргументов:
- [x,fval] = linprog(...)
- [x,fval,exitflag] = linprog(...)
- [x,fval,exitflag,output] = linprog(...)
- [x,fval,exitflag,output,lambda] = linprog(...)

Описание выходных параметров:
- [x,fval] = linprog(...) - возвращает значение целевой функции fun как решение от х: fval = f'*x;
- [x,lambda,exitflag] = linprog(...) - возвращает значение exitflag, которое содержит описание выходных условий;
- [x,lambda,exitflag,output] = linprog(...) - возвращает данные с информацией о параметрах оптимизации;
- [x,fval,exitflag,output,lambda] = linprog(...) - возвращает параметр lambda, который содержит множители Лагранжа как решение от х.
Подробное описание выходных аргументов функции linprog приведено ниже:

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

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

Суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, известно, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 ден. ед., шоколадного – 14 ден. ед. Требуется определить в каком количестве мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным.

Решение

Представим математическую модель решаемой задачи в матричном виде:
- целевая функция представляется вектором значений коэффициентов при x :

- ограничения

Для решения задачи применим функцию linprog в конструкции вида
x = linprog(f,A,b,Aeq,beq,lb,ub). Код инструкции и полученный результат оптимизации приведен ниже.

Решение в командном окне Matlab приведено на рис. 1.

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