PDF de programación - Optmización de Funciones Lineales con Restricciones en MATLAB: Teoría y Ejemplos

Reporte de Investigación

2007-09

Optimización de Funciones Lineales con

Restricciones en MATLABTM:

Teoría y Ejemplos

Responsables: William Marchena

Carlos Ornelas

Supervisor: Francisco M. González-Longatt



Línea de Investigación:

Fuentes Alternas de Energía

Y

Generación Distribuida

27-Feb-2007

Optimización de Funciones Lineales con Restricciones en MATLABTM: Teoría y Ejemplos

2

Optimización en MATLABTM
La caja de herramientas de optimización o denominado Toolbox extiende la capacidad de MATLAB®,
acercándolo a un ambiente numérico computacional. Toolbox incluye rutinas de muchos tipos, incluyendo
la optimización [1]:


− Minimización no lineal sin restricciones.
− Minimización no lineal con restricciones, problemas de minimizar y maximizar, y problemas de

minimización semi-infinitos.

− Programación cuadrática y lineal.
− No lineal, mínimos cuadrados y curvas adecuadas.
− Solución de ecuaciones de sistemas no lineales.
− Restricciones lineales de mínimos cuadrados.
− Problemas de larga escala.

Funciones de Optimización
Todas las funciones de la caja de herramientas son (m-files) de MATLAB, haciendo de MATLAB un
instrumento especializado en algoritmos de optimización. Se puede ver de MATLAB los códigos de las
funciones usando la presentación [1]:

type function_name

Se puede extender la capacidad de optimización de la caja de herramientas escribiendo sus propios m-files,
o usando la caja de herramienta con otras cajas de herramientas, o con MATLAB o Simulink®.
Caja de Herramienta de Optimización GUI
La herramienta de optimización (optimtool), es un GUI (Grafics Unit Interface), para seleccionar la
solución, especificando las opciones de optimización y los problemas corrientes. Se puede definir y
modificar los problemas rápidamente con GUI [1].
Usando Funciones de Optimización
Aquí se describirá como se deberá realizar la utilización de cada una de estas funciones de optimización:
Definición de la Función Objetivo
Muchas de las funciones de optimización requieren que se cree una función de MATLAB que calcule la
función objetivo. La función, en la entrada debe aceptar vectores, y retornar a la salida un escalar de tipo
doble.

Existen dos maneras de crear la función objetivo:


1) Se crea una función anónima en la línea de comando. Por ejemplo, si se crea una función anónima

para x2, se coloca:


square = @ [(x)]* x.^2;


Y se llama a la función de optimización con el cuadrado del primer argumento de la entrada. Se puede usar
este método si la función objetivo es relativamente sencilla, y no requiera ser utilizada en una sesión futura
de MATLAB.


2) Si se escribe un M-file para la función, por ejemplo, para escribir la función x2

debe abrir un nuevo archivo en el editor MATLAB y se deberá colocar el siguiente código:

como un m-file, se

W. Marchena, C Ornelas. F. Gonzalez-Longatt, Febrero 2007 REPORTE 2007-09


.
s
e
r
o
t
u
a

s
o
l

e
d
o
t
n
e
i
m



i
t
n
e
s
n
o
c


n
i
s

o
t
n
e
m
u
c
o
d

e
t
s
e

e
d

l
a
i
c
r
a
p
o

l
a
t
o
t



n
ó
i
c
c
u
d
o
r
p
e
r

a
l


o
d
i
b
i
h
o
r
P


.
s
o
c
i
m
é
d
a
c
a


o


,

n
ó
i
c
a
u
l
a
v
e

e
d
o
v
i
t
e
j
b
o
n
o
c



o
d
a
e
l
p
m
e

r
e
s

a
r
a
p
o
l
o
S



Optimización de Funciones Lineales con Restricciones en MATLABTM: Teoría y Ejemplos

3



.
s
e
r
o
t
u
a

s
o
l

e
d
o
t
n
e
i
m

function y = square(x)
y = x.^2;

Se puede llamar la función de optimización con @ al cuadrado como el primer argumento de entrada. El
signo @ crea una función manejable al cuadrado. Este método se emplea si la función objetiva es
complicada o si se sospecha que tal función será utilizada en una próxima sesión de MATLAB.
Maximización
Las funciones de optimización fminbnd, fminsearch, fminunc, fmincon, fgoalattain, fminimax, lsqcurvefit, y
lsqnonlin todas realizan la minimización de la función objetivo f(x). La maximización es alcanzada
sustituyendo en las rutinas con – f(x). Asimismo para alcanzar la maximización para quadprog se sustituye
-H y -f, y para linprog -f [2].
Restricciones Mayores que Cero
La Caja de herramientas de Optimización (Toolbox) asume que las restricciones de desigualdad no lineales
son de la forma Ci(x)≤0. Las restricciones mayores que cero son expresadas como menores que cero
multiplicándolas por -1. Por ejemplo, una restricción de la forma Ci(x)≥0 es equivalente a la restricción
(-Ci(x))≤0); una restricción de la forma Ci(x)≥b es equivalente a la restricción (-Ci(x) + b)≤0 [2].
Maximización vs Minimización
La optimización funciona en la caja de herramienta minimizando la función objetivo. Para maximizar la
función f se aplica una optimización para minimizar la función -f. El punto resultante donde el máximo f
ocurre también es el punto donde el mínimo de -f ocurre.
Problemas Cubiertos por la Caja de Herramientas
Las siguientes tablas muestran las funciones disponibles para la minimización y maximización de las
funciones a utilizar en este trabajo especial de grado, donde la función objetivo es una ecuación lineal con
restricciones lineales o no lineales de desigualdad.


Tabla 1. Tabla representativa de las funciones disponibles para la minimización y maximización de

n
i
s

o
t
n
e
m
u
c
o
d

e
t
s
e

e
d

l
a
i
c
r
a
p
o

l
a
t
o
t


n
ó
i
c
c
u
d
o
r
p
e
r

a
l


i
t
n
e
s
n
o
c



las funciones a utilizar en este trabajo especial de grado

Tipo

Programación lineal

Minimización de restricciones

Ax

≤

Ax

≤

Función

Linprog

Fmincon

min
x

Notación
xf T
=
x
)(

bxAb
,

eq
f
min
x
x
c
)(
,0
≤
b,
Aeq.x

ux


ux



,

=
l

≤≤

tal que
l
eq
tal que
x
ceq
0
)(
beq
=
≤≤



o
d
i
b
i
h
o
r
P


.
s
o
c
i
m
é
d
a
c
a


o


,

n
ó
i
c
a
u
l
a
v
e

e
d
o
v
i
t
e
j
b
o
n
o
c



o
d
a
e
l
p
m
e

r
e
s

a
r
a
p
o
l
o
S



W. Marchena, C Ornelas. F. Gonzalez-Longatt, Febrero 2007 REPORTE 2007-09

Optimización de Funciones Lineales con Restricciones en MATLABTM: Teoría y Ejemplos

4

≤



(1)

T
xf

ta
que
l



eq
ub

Ax
b


bxA


=
eq

x
lb

≤≤

Linprog [1]
Propósito
Resolver problemas de programación lineal.
Ecuación
Encuentra el mínimo de un problema especificado por:

min



Donde: f, x, b, beq, lb, y ub son vectores y A y Aeq son matrices
Sintaxis

x = linprog(f,A,b)
x = linprog(f,A,b,Aeq,beq)
x = linprog(f,A,b,Aeq,beq,lb,ub)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
[x,fval] = linprog(...)
[x,lambda,exitflag] = linprog(...)
[x,lambda,exitflag,output] = linprog(...)
[x,fval,exitflag,output,lambda] = linprog(...)
Descripción
Linprog soluciona problemas de programación lineal

x = linprog(f,A,b): soluciona min f'*x tales que A*x≤b

x = linprog(f,A,b,Aeq,beq): soluciona el problema descrito inicialmente (1), mientras que
además satisface la igualdad de las restricciones Aeq*x = beq. Se coloca A=[ ] y b=[ ] si no existen
desigualdades

x = linprog(f,A,b,Aeq,beq,lb,ub): Se definen los limites inferior y superior sobre la variable
de diseño en x, de modo que la solución este siempre entre el rango lb ≤ x ≤ ub. Se coloara Aeq = [ ] y beq
= [ ] si no existen igualdad.

x = linprog(f,A,b,Aeq,beq,lb,ub,x0): fija el punto de partida x0. Esta opción esta solamente
disponible con el algoritmo a media escala (la opción de Larga Escala, se fija a “off” usando optimización).
El defecto del algoritmo a larga escala y del algoritmo simplex es que ignoran los puntos de partida.

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options): Reduce al mínimo con las opciones de
optimización especificadas en la estructura options. Se utiliza optimset para fijar estas opciones.

[x,fval] = linprog(...): Retorna el valor de la función objetivo fun en la solución x: fval = f'*x.

[x,lambda,exitflag] = linprog(...): devuelve un valor exitflag que describe la condición de
salida.


W. Marchena, C Ornelas. F. Gonzalez-Longatt, Febrero 2007 REPORTE 2007-09


.
s
e
r
o
t
u
a

s
o
l

e
d
o
t
n
e
i
m



i
t
n
e
s
n
o
c


n
i
s

o
t
n
e
m
u
c
o
d

e
t
s
e

e
d

l
a
i
c
r
a
p
o

l
a
t
o
t



n
ó
i
c
c
u
d
o
r
p
e
r

a
l


o
d
i
b
i
h
o
r
P


.
s
o
c
i
m
é
d
a
c
a


o


,

n
ó
i
c
a
u
l
a
v
e

e
d
o
v
i
t
e
j
b
o
n
o
c



o
d
a
e
l
p
m
e

r
e
s

a
r
a
p
o
l
o
S



Optimización de Funciones Lineales con Restricciones en MATLABTM: Teoría y Ejemplos

5

[x,lambda,exitflag,output] = linprog(...): Devuelve una estructura output que contiene
información acerca de la optimización.

[x,fval,exitflag,output,lambda] = linprog(...): Devuelve una estructura lambda
donde contiene los campos de los multiplicadores de Lagrange en la solución x. [1]
Entrada de Argumentos
A continuación se muestra una descripción general de los argumentos pasados en linprog [1]:


Tabla 2. Representativa de los argumentos de entrada para las funciones linprog y fmincon.

Descripción

Usada por las funciones:

el vector beq

La matriz Aeq y
son,
respectivamente, los coeficiente de las restricciones
de la inecuaciones lineales y al correspondiente al
lado derecho del vector: Aeq*x = beq
El vector de los coeficientes para el termino lineal
en la ecuación lineal f’*x o la ecuación cuadrática
x*H*x + f’*x.
La función para optimizar. fun es una función
manipulada por una función m-file o por una
función anónima.



fgoalattain, fminco