Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.
La programación matemática constituye un campo amplio de estudio que se ocupa de la teoría, aplicaciones y métodos computacionales para resolver los problemas de optimización condicionada. En estos modelos se busca el extremo de una función objetivo sometida a un conjunto de restricciones que deben cumplirse necesariamente. Las situaciones que pueden afrontarse con la programación matemática se suelen presentar en ingeniería, empresas comerciales y en ciencias sociales y físicas.
Con carácter general, un programa matemático (ver Minoux, 1986) consiste en un problema de optimización sujeto a restricciones en de la forma:
El vector x tiene como componentes x1,x2,…, xn, que son desconocidas en el problema. La función es la función objetivo y el conjunto de condiciones , y son las restricciones. La función objetivo muestra la calidad de la solución para un problema específico: es una expresión que sirve para reducir cada opción a un valor o cifra de mérito en términos de beneficio, coste o cualquier otro. Se ha considerado en la formulación la minimización, ya que en el caso de maximizar basta el cambio .
El modelo más antiguo y más ampliamente desarrollado en el campo de la programación matemática es el lineal. La programación lineal estudia la optimización de una función lineal que satisface un conjunto de restricciones lineales de igualdad o desigualdad. Fue George B. Dantzig quien en 1947 concibió el método simplex para resolver este problema cuando trabajaba como consejero de los controladores de la Fuerza Aérea de los Estados Unidos, si bien en 1939 el matemático y economista soviético L.V. Kantorovich plateó y solucionó un problema de estas características relacionado con la organización y la planificación, aunque su trabajo permaneció sin conocerse hasta 1959. En realidad el término programación lineal fue acuñado por el también economista y matemático T.C. Koopmans en el verano de 1948, mientras paseaba con Dantzig cerca de la playa de Santa Mónica en California (ver Bazaraa et al., 1998). Los trabajos de Dantzig se recogieron en 1951 en el libro Activity Analysis of Production and Allocation editado por Koopmans.
La idea del método simplex se basa en recorrer el poliedro formado por las restricciones del programa lineal, vértice a vértice, a lo largo de las aristas, hasta alcanzar el vértice óptimo. Esta idea se remonta a Fourier (1826) (ver Schrijver, 1986), si bien la mecanización algebraica del algoritmo fue propuesta por Dantzig. Sin embargo, cuando las variables que intervienen en un modelo son muchas, el tiempo de respuesta de este algoritmo no es operativo para alcanzar la solución óptima. Se resuelven con la programación lineal problemas típicos de asignación de recursos, de planificación de mano de obra, la necesidad de equipos en ejecución de proyectos, etc.
La programación entera trata de optimizar aquellos problemas que en algunas o todas las variables de decisión se restringen a un conjunto de valores discretos. Es a partir de la publicación del primer algoritmo de programación lineal entera de Gomory en 1958, cuando se sientan las bases para su desarrollo, aunque ya en la década de los cuarenta se resolvió el problema del transporte (Hitchcock, 1941). Algunas aplicaciones de la programación entera solventan problemas clásicos como el de la mochila, el del viajante, la programación proyectos, la localización de recursos, etc. (Yepes, 2002).
El requerimiento entero sobre las variables a menudo significa que aun cuando la función objetivo y las restricciones sean lineales, el problema no pueda ser resuelto por un algoritmo de programación lineal. La razón es que no existe garantía de que los valores de las variables en la solución más favorable sean enteros. Una forma de conseguir una solución entera óptima es redondear los valores de las variables de decisión obtenidas por la programación lineal. En algunos casos, este método brinda como resultado una solución entera óptima. Sin embargo, el redondeo puede ofrecer una opción viable con un valor de función objetivo significativamente peor que el óptimo. Peor aún, puede aparecer una solución infactible. Por ello, se han desarrollado algoritmos especializados que alcanzan resultados óptimos cuando algunas variables de decisión presentan valores enteros.
Os dejo a continuación un vídeo explicativo sobre la programación lineal y el método Simplex.
REFERENCIAS
BAZARAA, M.S.; JARVIS, J.J.; SHERALI, H.D. (1998). Programación lineal y flujo en redes. Ed. Limusa. 2ª edición. México. 781 pp.
HITCHCOCK, F.L. (1941). The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics, 20: 224-230.
MINOUX, M. (1986). Mathematical Programming. Theory and Algorithms. John Wiley and Sons. 489 pp.
SCHRIJVER, A. (1986). Theory of linear and integer programming. John Wiley & Sons. 471 pp.
YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)