PDF de programación - Optimizacion Matematica con R Volumen I

Optimización Matemática

con R



Volumen I: Introducción al
modelado y resolución de

problemas



Enrique Gabriel Baquela



Andrés Redchuk



Madrid, Marzo de 2013





Dedicatorias


A Clementina Augusta, por existir.
A Flavia Sabrina, por ayudarme a ser lo que soy.
A mis padres y hermanos, por estar siempre.
A Isidoro Marín, Horacio Rojo,
Silvia Ramos y Gloria Trovato,
por el empujón inicial.
A mi directora de Doctorado, Ana Carolina Olivera,
y a mi codirectora, Marta Liliana Cerrano
por aceptar el desafío de ayudarme
a formarme en investigación.
A mis amigos y compañeros del GISOI,
por apoyarme desde el principio.
A Juan Cardinalli, por sus apreciaciones
diarias dentro del trabajo de Furgens Research.
A Andrés, por animarme y ser mi socio
en esta aventura.

Enrique Gabriel Baquela



A las tres hijas que Rita me dio
Sophie, Vicky, Érika,
y a los tres ahijados que la vida regaló
Leo, Fede y Alejo.

Andrés Redchuk

i





ii

Autores



Enrique Gabriel Baquela

Enrique Gabriel Baquela es Ingeniero Industrial por la Universidad
Tecnológica Nacional de San Nicolás de los Arroyos (UTN-FRSN), y
alumno de Doctorado en la Universidad Nacional de Rosario (UNR).

Es coordinador del Grupo de Investigación en Simulación y Optimización
Industrial (GISOI), investigador del departamento de Ingeniería Industrial
de UTN-FRSN, profesor de Simulación de procesos y sistemas y de
Optimización Aplicada en el mismo centro, y co-fundador de Furgens
Research.



Andrés Redchuk

Andrés Redchuk es Ingeniero Industrial por la Universidad de Lomas de
Zamora en Buenos Aires, Master en Calidad Total y en Ingeniería
Matemática de
III de Madrid; Master en
Tecnologías de la Información y Sistemas Informáticos y Doctor en
Informática y Modelización Matemática de la Universidad Rey Juan
Carlos en España.

la Universidad Carlos

la Facultad de Ciencias Empresariales de

Andrés Redchuk es Master Black Belt de la Asociación Española para la
Calidad, profesor de
la
Universidad Autónoma de Chile, Profesor de la Facultad de Ingeniería de
la Universidad Nacional de Lomas de Zamora, miembro del
departamento de Estadística e Investigación Operativa de la Universidad
Rey Juan Carlos en Madrid, España y Director del Grupo de Investigación
en Lean Six Sigma.



iii





iv

Prologo


Los problemas del mundo real son, en general, no lineales enteros mixtos
y de gran dimensión. Poder resolver esa clase de problemas es de vital
importancia para todo profesional. Encontrar la solución óptima a estos
problemas suele ser nuestro principal objetivo, aunque muchas veces
nos alcanza con encontrar soluciones con ciertas características, aunque
se trate de un resultado subóptimo y conocer la “calidad” de esta
solución.
Es conveniente tener disponibles algoritmos eficientes y robustos para la
resolución es esa clase de problemas.
El software R, ha demostrado ser muy eficiente para programar e
implementar las técnicas estadísticas y los algoritmos de Optimización
más tradicionales.
Mediante este
la
programación de los algoritmos más tradicionales y conocidos de
optimización. Además presentamos su implementación en R. Para
encontrar soluciones óptimas desarrollamos algoritmos de optimización
y para encontrar soluciones cuasi óptimas desarrollamos algoritmos
metaheurísticos.
El libro está pensado para estudiantes de carreras universitarias y de
cursos de posgrado que quieran trabajar en el campo de la Optimización,
de la Programación Matemática, los Métodos Cuantitativos de Gestión y
la Investigación Operativa. Presenta herramientas para utilizar a modo de
caja negra, como también el diseño de algoritmos específicos.



libro pretendemos divulgar el desarrollo y

Los autores



v





vi

¿Cómo leer este libro?



Referencias
Este libro es principalmente de aplicación práctica. Gran parte de su
contenido consiste en código para transcribir directo a la consola de R.
Por lo tanto, hemos adoptado una convención respecto a la tipografía
para que las partes de este libro sean fácilmente identificables:

Cada vez que el Texto tenga este formato, entonces es texto explicatorio
y formará parta del hilo conductor del libro.

Texto con este formato, es código R, ya sea para ingresar a
la consola o bien para grabar en un script. Los comentarios,
que se indican con #, se pueden suprimir. R no termina una
sentencia hasta que no cerremos sintácticamente a la misma,
así que podemos escribirlas en varias líneas como a veces,
por cuestión de espacio, aparece en este libro.

Texto con este formato se usa para mostrar la salida de consola. Es
lo que nos debería devolver R tras ingresar los comandos indicados.
No siempre se incluye la salida de consola, cuando se considera que
su inclusión es redundante la omitimos en este libro.


TEXTO CON ESTE FORMATO ES UN FORMULA O MODELO MATEMÁTICO

Como comentario extra, los bloques de código no son independientes
unos de otros. Al inicio de cada capítulo tenemos siempre el siguiente
código:

rm(list=ls())
setwd("D://Proyectos//IOR//scripts")

La primera línea borra la memoria, mientras que la segunda línea
declarara cual es el directorio de trabajo. Adicionalmente, podemos
encontrar este código de borrado repartido por el código de un mismo
capítulo.

rm(list=ls())

Cuando encontramos esta línea, borrando la memoria de trabajo,
significa que todo el código posterior a esa sentencia es independiente
del anterior, así que podemos trabajar tranquilos. Pero, si buscando por
el libro encontramos un código que nos interesa sin la llamada a

vii

rm(list=ls()), debemos buscar la llamada inmediata anterior y tipear todo
el código que existe a partir de ella (incluyendo el rm(list=ls()) ).



viii

Estructura del libro



Este volumen tiene dos partes bien diferenciadas, ocupando cada una un
50 por ciento del mismo. La primera, dedicada a la introducción al
entorno y al lenguaje R, puede ser omitida por quien ya tenga
conocimientos del mismo. Si no es el caso, aconsejamos su lectura y la
ejecución de todo el código proporcionado, siguiendo el orden prefijado
por el libro. R tiene una sintaxis y una filosofía propia y diferente a la que
nos tienen acostumbrados los lenguajes similares a C/C++ y Pascal.
Pensado para el uso en problemas matemáticos en general, y estadísticos
en particular, tiene una expresividad enorme que ayuda a no alejarnos
de los problemas que estamos intentando resolver. Particularmente
importante son los conceptos de vectorización y reciclado, a los que el
usuario tendrá que acostumbrarse para sacar el máximo provecho de
esta herramienta.

Por otro lado, la segunda parte está enfocada a la implementación y
ejecución de distintas técnicas algorítmicas para resolución de problemas
de programación matemática. Cada capítulo es independiente de los
demás, pudiéndose leer en cualquier orden. Sin embargo, sin importar el
algoritmo que se requiera utilizar, aconsejamos la lectura del apartado
“Optimizando en base a muestras” del capítulo “Algoritmos para
programación Lineal”, ya que allí se muestra un puente entre el
procesamiento estadístico de datos, el armado de modelo lineales y su
posterior optimización (que, con un poco de esfuerzo, pueden ser
migrados a otros algoritmos de optimización e incluso a problemas no
lineales).



ix





x

Índice de contenido



¿Cómo leer este libro?

Referencias
Estructura del libro

Índice de contenido

Introducción

1.1. ¿Qué es un problema de optimización?
1.2. Modelado de sistemas Vs Resolución de modelos
1.3. Clasificación de problemas de optimización
1.4. Clasificación de métodos de resolución

vii

xi

13

vii
ix

13
14
14
15

Resolución mediante cálculo
Resolución mediante técnicas de búsquedas
Resolución mediante técnicas de convergencia de soluciones

15
16
16

1.5. Optimización Convexa

Introducción al uso de R

2.1 Actividades previas.
2.2. Utilizando R
2.3. Acerca del trabajo con matrices en R
2.4. Arrays
2.5. Listas

Un poco más de R

3.1. Utilizando funciones en R
3.2. Guardando nuestras funciones
3.3. Armando scripts

Gráficos con R

4.1. Trabajando con el paquete graphics
4.2. Trabajando con layouts

Implementando nuestras primeras búsquedas

5.1. Acerca de las búsquedas por fuerza bruta
5.2. Búsqueda aleatoria
5.3. Búsqueda dirigida por gradientes

Algoritmos para programación lineal

6.1. Introducción a la Programación Lineal

xi

17

19
21
40
48
50

53
58
59

61
75

83
89
91

93

19

53

61

83

93

6.2. Cómo resolver problemas de PL
6.3. Otros paquetes de PL: lpSolve
6.4. Otros paquetes de PL: lpSolveAPI
6.5. Optimizando en base a muestras

Algoritmos para programación no lineal

7.1. La función OPTIM
7.2. Optimizando con restricciones
7.3. Armando nuestra propia versión de OPTIM

Algoritmos genéticos

8.1. Algoritmos genéticos
8.2. Armando nuestras propias funciones

Anexo I: Interacción con RStudio

¿Por qué utilizar RStudio?
Configurando el layout de visualización
Trabajando con paquetes
Consultando la ayuda
Visualizando gráficos
Monit