Introducción a la Programación Lineal (PL)

La programación lineal (PL) es "el procedimiento mediante el cual, se obtienen los máximos y mínimos de un problema expresado como una función lineal, cuya solución esta restrigida por un sistema de inecuaciones lineales".

En otras palabras, son procedimientos de optimización de funciones matemáticas lineales. Ahora, la idea es que esas "funciones matemáticas lineales" representen un problema de la vida real, como las compras de materiales para la contrucción de una casa. Para esto tenemos que hacer la "formulación" del problema en un modelo matemático, y si este modelo resulta ser una función lineal, puede ser resuleto con algoritmos de PL.

NOTA: recuerda que una función lineas es aquella cuyas variables tienen exponente uno (1) . Ej: f(x,y,z) = x + 2y + 2z + 3


¿Qué NO es programación lineal?

Muchos principiantes confunden la palabra "programación" con muchas otras actividades (como codificación) asi que aquí listo algunos de estos errores de interpretación que he apreciado.

• Codificación o implementación de software. En Investigación de Operaciones, cuando se refiere a "Programación Lineal", debe interpretarse como "Planificación Lineal". Esto se debe a que la naturaleza de la mayoria de los problemas de PL son de toma de desiciones para planificar actividades.
• Resolución secuencial de un problema. El termino "Lineal" se refiere a la forma de la función matemática a optimizar, no a una secuencia de pasos o tareas.
• Modelación matemática de un problema. La modelación matematica (formulación) es un paso previo a la resolución de problemas de PL. Recuerda que es posible que la modelación matemática del problema te de una función matemática NO lineal.

¿Cuándo un problema es de Programación Lineal?

Puedes guiarte con estas dos sencillas caractrísticas:

1. El objetivo del estudio es maximizar o minimizar (optimizar)
2. Si el modelo matemático que representa el problema solo tiene expresiones lineales

Si un modelo matemático cumple con estas dos características, es un candidato para ser optimizado mediante algoritmos de PL. Ahora, es posible que el modelo matematico sea de PL, pero por su particularidad, exista otro tipo de técnicas para su resolución (EJ: Modelo de Asignación, que es un caso particular de PL)

Forma general de un problema de Programación Lineal (PL)

Los problemas de optimización siempre tienen algo que maximizar o minimizar (función objetivo) y un grupo de limitantes (restricciones) que enmarcan la optimización. Esto es necesario, porque si no se limita el problema, no habrá soluciones factibles.

Ejemplo: Si defines como un problema de PL tus compras del mercado, quieres minimizar tus gastos y no pones ninguna limitación, la respuesta al problema sera que no compres NADA, ya que asi tu gasto será mínimo ... pero ¿eso tiene sentido? Obviamente no, ya que si vas al mercado es porque tienes unas necesidades mínimas que cubrir, como por ejemplo, tu dieta diaria debe tener como mínimo 2000 calorias. Esta ultima parte del problema, es una restricción.

Asi que un problema de PL esta expresado como:

1. Función objetivo. Expresión matemática lineal a optimizar.
2. Restricciones. Conjunto de inecuaciones lineales que limitan la optimización.

Supuestos de Programación Lineal (PL)

Las "suposiciones" deben ser entendidas por la persona que trabaje sobre un problema de PL, ya que son estas la que definen formalmente a un problema de este tipo. Si alguno de estos supuestos no tienen sentido en el problema a solucionar, no puede ser resuelto por PL, o va a requerir un post-procesamiento y análisis para que el resultado tenga sentido.

NOTA: En mi opinión, la idea de usar IO es obtener resultados deterministicos. Así que debe ser meta de todo investigador de operaciones, tratar de evitar situaciones que requieran interpretaciones adicionales, mientras las circuntacias lo permitan (El mundo real es bien complicado, y modelarlo matemáticamente es muy difícil).

Vamos a enumerar aquí los tres (3) supuestos mas importantes de la programación lineal.

1. Suposición de proporción. La contribución al objetivo de cualquier variable de desición "X" es proporcional al valor de "X".
2. Suposición de adición. La contribución al objetivo de cualquier variable de desición "X" es independiente a la contribución de cualquier otra variable "Y".
3. Suposición de divisibilidad. Los valores numéricos de las variable de desición deben tener sentido incluso con valores fraccionados (Ej: X = 2,3).

NOTA: Hay más suposiciones, pero estas son las tres más resaltantes en mi opinión.