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

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

Функция 1 inp год обеспечивает решение типовой задачи линейного программирования:

х = linprog(f,A,b,Aeq,beq,lb,ub,xO,options)

[x, fval, exitflag, output, lambda ] = linprog(...)

В этой функции введен дополнительный аргумент f — вектор коэффициентов линейной целевой функции. Функция может использовать алгоритм большой размерности LTPSOL или алгоритм средней размерности (метод проекций).

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

/(х) = -5х, - 4х₂ - 6х₃,

х₍ - х₂ + х₃ < 20

Зх, + 2х, + 4х₃ < 42,

Зх_{ + 2х₂ < 30

0 < х,, 0 < х₂, 0 < х₃.

Решение задачи приведено ниже.

» f=[-5; -4; -6]; А=[1 -1 1;3 2 4;3 2 0];

» Ь=[20; 42; 30]; lb = zeros (3,1);

>> [х,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)

x =

• 0.0000
• 15.0000
• 3.0000

fval = -78.0000

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

Функция quadprog возвращает решение задачи квадратичного программирования:

х = quadprog(Н,f,A,b,Aeq,beq,lb,ub,x0,options)

[x, fval, exitflag, output, lambda] = quadprog (...)

Аргументы (за исключением матрицы н) и возвращаемые величины аналогичны рассмотренным для функции fmincon.

Найдем решение задачи квадратичного программирования, имеющей описание

/(х) = — х² + х² - х₍х₂ - 2Х] - 6х₂,

X' + х₂ < 2,

• -х, + 2х₂ < 2,
• 2х, + х₂ < 3,
• 0 < X], 0 < х₂.

В данном случае

I -1

Х|

х₂

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

» Н=[1 -1; -1 2]; f=[-2; -6] ;

» А= [ 1 1; -1 2; 2 1]; Ь= [ 2; 2; 3]; lb = zeros (2,1);

>> [х,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb) Приведем основную часть вывода:

• 0.6667
• 1.3333 fval =
• -8.2222

Из опущенной выходной информации следует, что количество выполненных итераций равно 3 и использован алгоритм средней размерности.

Дополнительные примеры решения типовых оптимизационных задач

Минимизация без ограничений

Рассмотрим задачу нахождения значений переменных х, и х₂, обеспечивающих решение задачи минимизации

min /(х) = е^х' (4х² + 2х₂ + 4х,х₂ + I).

Нахождение решения производится в соответствии со следующими этапами.

Составим m-файл с именем objfun, реализующий вычисление значения целевой функции: function f = objfun(x) f = exp(x(1))*(4*x(1)^л2+2*х(2)^л2 + 4*х(1)*x(2)+2*x(2)+1) ;

Решим задачу с использованием подходящей функции пакета fminunc:

>> х0=[-1,1]; options = optimset('LargeScale', 'off ' ); » [x,fval,exitflag,output] = fminunc('objfun',xO,options) Optimization terminated successfully:

Current search direction is a descent direction, and magnitude of directional derivative in search direction less than 2*options.To1Fun x = 0.5000 -1.0000 fval = 1.3028e-010 exitflag = 1 output = iterations: 7 funcCount: 40 stepsize: 1

firstorderopt: 8.1997е-004 algorithm: 'medium-scale: Quasi-Newton line search'

Значениях = [0.5000 -1.0000] и fval = 1.3028e-010 — искомое решение задачи. Значение exitflag=l дает информацию, что найдена точка минимума (возможно, локального). Остальные характеристики выхода вполне очевидны.