Planteamiento matemático del problema
Función objetivo, restricciones y solución óptima. Teorema fundamental de la programación lineal
Llamaremos función objetivo a la función lineal F(x,y)=ax +bx+c. Se trata de una función de dos variables que pueden ser enteras o reales, es decir que toman valores enteros o decimales.
Las restricciones son un sistema de inecuaciones lineales. La solución de dicho sistema se llama región factible. Esta siempre será un polígono convexo, acotado o no. Un conjunto es convexo cuando no tiene laterales metidos hacia adentro como los que tienen forma de estrella. Formalmente un conjunto es convexo cuando si se toman dos puntos A y B dentro de él, entonces todo el segmento AB que los une también está dentro del conjunto.
Estos problemas son muy variados, según que:
- la región factible sea acotada, no acotada o infactible (esto último significa que el sistema de inecuaciones no tienen solución)
- la solución óptima sea única, múltiple, infinita o inexistente.
- si existe solución única esta se da en un vértice de la región factible
- se asegura la existencia de solución cuando el polígono esté acotado y siempre estará en la frontera, un vértice o todos los puntos de un lado
- si la región factible es no acotada, las soluciones, si las hay, también están en la frontera, bien en algún vértice si es única, o bien en algún lado si no es única.
- si la región factible se queda vacía, tampoco hay solución óptima
- si el problema tiene las variables enteras y las soluciones están en un lado del polígono, serán varias pero en número finito, mientras que si las variables son reales las soluciones óptimas serán infinitas, todos los puntos del segmento.