Matemáticas/Programación Lineal/Texto completo

Programación Lineal

La Programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.

Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

• Prólogo
• Fundamentación
• Definiciones
• Antecedentes históricos

Definición de Programación Lineal

Es una de las técnicas agrupadas como programación matemática, aplicable a problemas de asignación de recursos limitados, con actividades competitivas hacia un objetivo común, que puede ser de maximizar beneficios (por ejemplo utilidades o bien rendimientos); también se puede desear minimizar el esfuerzo (por ejemplo los costos, el personal asignado a tareas, o el desperdicio en procesos). Se usa un modelo matemático con representación válida de la problemática en estudio; sus relaciones deben ser lineales o de "línea recta", que significa utilizar, sólo una variable de primer grado en cada término.

En todos los problemas de programación lineal, el objetivo es el máximo o bien el mínimo de alguna cantidad en la acción de asignar recursos.

Inicio de sus desarrollo

El desarrollo de la programación lineal se considera entre los avances científicos más importantes del siglo XX, pues su impacto ha sido extraordinario. Actualmente es una herramienta de uso común que ha beneficiado a muchas organizaciones en distintos países con ahorros de cualquier índole, por lo que su uso se está ampliando rápidamente a todos los sectores de la sociedad. Una gran mayoría de los cálculos científicos en computadoras usan la programación lineal proliferando las publicaciones y libros sobre esta materia de gran aplicación.

Antecedentes

Uno de sus antecedentes se registra con el método de análisis de insumo-producto que desarrolló el economista W. Leontief; también se debe reconocer al economista y matemático soviético L.V. Kantorovich, quien ya en 1939 formuló y resolvió un problema de programación lineal para la organización y planeación de la producción; otro antecedente es, la interpretación de Hitchcock a "un problema de tipo de transportación" en 1941. El problema de la dieta, fue analizado por Stigler en 1945. El gran impulso de la programación lineal para la industria y los negocios se identifica con el doctor George Dantzig, matemático norteamericano de origen, que desarrolló el algoritmo Simplex, un método sistemático de resolución para problemas modelados con programación lineal. Esto ocurrió en 1947 cuando se ocupó, con Marshal Wood y asociados, de un proyecto para la Fuerza Aérea de los Estados Unidos. Se organizó un grupo de investigación con el título de Proyecto SCOOP (Scientific Computation of Optimum Programs). Actualmente las principales aplicaciones de la PL son del área industrial; también, aunque en menor parte, en el campo urbano y social.

Los años cincuenta

A partir de 1950, un número cada vez mayor de investigadores (matemáticos y economistas) aislados o constituyendo grupos contribuyen al desarrollo de las diferentes ramificaciones de la programación lineal; en particular, la "Rand Corporation" con G. B. Dantzig y W. Orchard-Hays, después L. R. Ford, D. R. Fulkerson, y D. Gale; el departamento de matemáticas de la Universidad de Princenton con A. W. Tucker y H. W. Kun; la "Graduate School of Industrial Administration" del "Carnegie Institute of Technology" con A. Charnes y W. Cooper. Los dos primeros grupos trabajan en la teoría matemática de los programas y su instalación en computadoras; los resultados se publicaron en la "Rand Corporation" en la serie de "Rand notes on linear programming and extensions" (desde 1953 a 1961); se deben mencionar las de Dantzig sobre los desarrollos teóricos, las de W. Orchard_Hays sobre la instalación de los programas de cálculo en máquinas, las de L. R Ford y D. R. Fulkerson sobre las redes de transporte; es necesario citar especialmente en el activo del grupo de Princenton, el método "húngaro" de H. W. Kun, para los problemas de asignación, la publicación de la notable colección de notas "Linear Inequalities and Related Systems" en 1956 y el método de Gomory para el cálculo de los problemas lineales en números enteros a finales del año 1958. El equipo del "Carnegie Tech" desarrolló la PL en aplicaciones industriales, se interesó en aspectos teóricos particulares como: degeneración, errores de redondeo, el Simplex revisado, variables acotadas.

Años recientes

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria.

Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal.

El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas.

En los últimos años, lo notable y más prometedor parece ser: La programación lineal en números enteros por R. Gomory, el principio de descomposición de Dantzig y Wolfe, los programas lineales estocásticos, el algoritmo de punto interior de Narendra Karmarkar, con aportaciones importantes de un matemático ruso I. Dikin en 1967, redescubierto, después de la publicación de Karmarkar por varios investigadores: E.R.Barnes, T. M.Cavalier y A.L.Soyster. Además R.J.Vanderbei, M.S.Meketon y B.A.Freedman publicaron en 1986, "A modification of Karmarkar's Linear Programming Algorithm". Al inicio la programación lineal se llamó "programación en estructura lineal". En 1948, Tjalling Koopmans sugirió a George Dantzing simplificar el nombre.