Función objetivo[editar]
La función objetivo puede ser:
o
Donde:
= coeficientes
Existencia de soluciones óptimas[editar]
Geométricamente, las restricciones lineales definen la región factible, que es
un poliedro convexo. Una función lineal es una función convexa, por lo que un mínimo
local es un mínimo global; una función lineal es también una función cóncava, así que todo
máximo local es también un máximo global.
Como las funciones lineales no son ni estrictamente convexas ni estrictamente cóncavas,
las soluciones óptimas no son necesariamente únicas.
Si la región factible es acotada y no vacía, entonces existirá al menos una solución óptima,
puesto que una función lineal es continua y por lo tanto alcanza un máximo en cualquier
región cerrada y acotada. Sin embargo, puede no existir una solución óptima en dos
situaciones. En primer lugar, si la región factible es vacía, es decir, si ningún punto verifica
todas las restricciones, entonces el problema es inviable. En segundo lugar, si la región
factible no está acotada en la dirección del gradiente de la función objetivo, el problema
es no acotado, y se pueden encontrar puntos que verifican todas las restricciones y con
un valor tan alto como queramos de la función objetivo.
Programación entera[editar]
En algunos casos se requiere que la solución óptima se componga de valores enteros para
algunas de las variables. La resolución de este problema se obtiene analizando las
posibles alternativas de valores enteros de esas variables en un entorno alrededor de la
solución obtenida considerando las variables reales. Muchas veces la solución del
programa lineal truncado está lejos de ser el óptimo entero, por lo que se hace necesario
usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el
método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de
Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de
decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo
entero.
Aplicaciones[editar]
La programación lineal constituye un importante campo de la optimización por varias
razones, muchos problemas prácticos de la investigación de operaciones pueden
plantearse como problemas de programación lineal. Algunos casos especiales de
programación lineal, tales como los problemas de flujo de redes y problemas de flujo de
mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente
importantes como para generar por sí mismos mucha investigación sobre algoritmos
especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos
de problemas de optimización constituyen casos particulares de la más amplia técnica de
la programación lineal. Históricamente, las ideas de programación lineal han inspirado
muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la
descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo
modo, la programación lineal es muy usada en la microeconomía, la ingeniería y la
administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al
mínimo los costos de un sistema de producción. El aprendizaje de la metodología
programación lineal es importante en la formación del ingeniero industrial y el
administrador porque le da herramientas para mejorar la toma de decisiones en las
empresas, lo que llevará a mejorar los procesos de las mismas. Algunos ejemplos son la
mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la
asignación de recursos humanos y recursos de máquinas, la planificación de campañas de
publicidad, etc.
Otros son:
Optimización de la combinación de cifras comerciales en una red lineal de
distribución de agua.
Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año
con afluencias caracterizadas por corresponder a una determinada frecuencia.
Soporte para toma de decisión en tiempo real, para operación de un sistema de
obras hidráulicas;
Solución de problemas de transporte.
