Optimizacion

Optimizaci´n Lineal o Teor´ M´todos y Modelos ıa, e
´ Miguel Angel Goberna, Valent´ Jornet y Rub´n Puente ın e

ii

Pr´logo o
Aunque los f´ ısicos del Siglo XIX ya hab´ optimizado funciones lineales ıan bajo unas pocas condiciones expresadas como ecuaciones e inecuaciones lineales, la optimizaci´n (o programaci´n) lineal nace como disciplina indeo o pendiente a mediados del Siglo XX, trasla publicaci´n del primer m´todo o e eficiente para este tipo de problemas (el simplex de Dantzig, 1947) y del teorema de dualidad (Gale, Khun y Tucker, 1951). La comercializaci´n de o grandes ordenadores durante los a˜os 70 y, sobre todo, la popularizaci´n de n o las computadoras personales desde los 80 han dado lugar a la proliferaci´n o de aplicaciones a los campos m´s diversos: planificaci´n delas actividades a o econ´micas (producci´n, transporte, gesti´n de carteras de valores, etc.), o o o administraci´n p´blica, an´lisis de datos, c´lculo num´rico, etc. De ah´ la o u a a e ı presencia de la optimizaci´n lineal -como asignatura independiente o como o parte de asignaturas de ´lgebra lineal, optimizaci´n, investigaci´n operativa a o o o econom´ de empresa- en el curriculum dematem´ticos, economistas e inıa a genieros, y el inter´s por el tema de los investigadores, cuyas contribuciones a e la optimizaci´n lineal, sin tener en cuenta las aplicaciones, han evolucionado o de la forma que muestra la siguiente tabla, que recoge el n´mero de trabajos u rese˜ados en Zentralblatt Math durante las pasadas d´cadas: n e 1950-59 47 1960-69 353 1970-79 2519 1980-89 4143 1990-99 5098

Sehan publicado tambi´n muchos libros sobre el tema (229 rese˜ados por e n la mencionada base de datos), pero casi todos ellos tienen como piedra angular la versi´n tabular del m´todo simplex, a partir de la cual se desarrollan o e la teor´ de la dualidad (verdadero n´cleo te´rico de la disciplina) y la teor´ ıa u o ıa de los sistemas lineales que, adem´s de ser equivalente en muchos sentidos a a laoptimizaci´n lineal, tiene inter´s propio al ser directamente aplicable o e en econom´ f´ ıa, ısica y estad´ ıstica. Este libro ha sido escrito a partir de las notas elaboradas por los autores para cursos dictados en las Universidades de Alicante y de San Luis, notas que fueron redactadas con dos prop´sitos o b´sicos: a (i) Invertir la ordenaci´n mencionada, que pone -contra toda l´gica- el o ocarro (los m´todos num´ricos) por delante de los bueyes (los sistemas lineales e e y la geometr´ anal´ ıa ıtica de poliedros). Es m´s, puesto que la versi´n para a o iii

iv

´ PROLOGO

tablas del m´todo simplex se nos antoja poco did´ctica (por ocultar las ideas e a geom´tricas subyacentes) y anacr´nica (pues s´lo permite resolver problemas e o o diminutos), el lector no encontrar´ en estelibro ni una sola de las habituales a tablas del simplex. (ii) Capacitar a los estudiantes para explotar la poderosa herramienta que es la optimizaci´n lineal en su futura actividad profesional, no siendo o suficiente para ello la habitual presentaci´n de una muestra de ejemplos. o Exponemos ahora brevemente la organizaci´n y objetivos del libro, que o consta de tres partes: modelaci´n, teor´ ym´todos num´ricos. o ıa e e El objetivo principal de la primera parte es desarrollar en el lector la habilidad para modelar, analizar, resolver y validar problemas de decisi´n, de o variada naturaleza (Cap´ ıtulo 1). El segundo objetivo es convencer al lector de la gran utilidad pr´ctica de la optimizaci´n lineal mediante una adecuaa o da selecci´n de aplicaciones, mostrando estrategias que permitenformular o este tipo de modelos (Cap´ ıtulo 2). Es aconsejable -pero no imprescindibleque el lector resuelva num´ricamente los problemas propuestos mediante e una librer´ de programas a su alcance (como MATLAB), utilizada como ıa ‘caja negra’ (los enunciados correspondientes utilizan el verbo “computar”). Dada la generalidad de los problemas abordados en el Cap´ ıtulo 1, su lectura requiere, en...