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.

Tips para la modelación y formulación de problemas de programación lineal

La modelación

Es el proceso completo de abstracción del sistema real al modelo cuantitativo y tiene como resultado un modelo matemático del sistema real bajo estudio. Incluye actividades como la definición del sistema y la determinación de sus fronteras, la identificación de las actividades más importantes para el logro del objetivo, es decir la conceptualización del sistema simplificado y finalmente la elaboración del modelo. Es quizás la parte más importante de la Investigación de Operaciones y se le considera como una mezcla de arte y de ciencia. La modelación no puede enseñarse, sino motivarse, se aprende con la práctica y con la experimentación.

Puede dividirse en dos fases: Subjetiva y la objetiva. La parte subjetiva consiste en la definición del sistema supuesto o simplificado. Mientras que la objetiva es la construcción del modelo a partir del sistema simplificado.

La formulación

Es la componente objetiva de la modelación y consiste en convertir el sistema simplificado en un modelo cuantitativo que lo describa. En esta sección ahondaremos un poco en la actividad de formulación, para lo cual supondremos que ya se realizó la etapa previa que nos permitió definir el sistema simplificado.

Debe tenerse en cuenta que en la vida profesional el estudiante si se vera afrontado a la necesidad de derivar sus propios sistemas supuestos, a partir de los problemas reales que se le presenten. El éxito obtenido dependerá de factores tales como su capacitación general, su habilidad y experiencia en la modelación y la comprensión que tenga del área particular del problema a modelar.

Metodología para construir modelos de Programación Lineal

Una buena metodología para construir modelos matemáticos de los problemas, a partir del problema simplificado (problema supuesto), parece ser la siguiente:

1. Leer atentamente el enunciado de la situación con el fin de comprender sus principales características.

Como resultado de la lectura estaremos en capacidad de realizar los dos pasos siguientes.

2. Organizar en cuadros o tablas toda la información cuantitativa que suministra el enunciado del problema.

De esta manera será más fácil identificar, interpretar y utilizar la información. Debe prestarse especial atención a las unidades de todos los datos utilizados.

3. Dibujar un esquema de la situación.

Este nos permitirá visualizar y comprender mejor las características del problema. En especial el diagrama es útil para llevar a cabo los tres pasos siguientes.

4. Identificar los elementos del problema.

Los elementos son las entradas (recursos), las salidas (productos) y las actividades (variables de decisión) del proceso al cual se reduce el problema. La grafica o esquema del paso tres, es de gran ayuda en esta tarea.

Las actividades son las que convierten una o más entradas en una o más salidas. La esencia del problema de P.L. es la determinación del sub conjunto de actividades que deben llevarse a cabo para optimizar el logro del objetivo.

5. Expresar el objetivo relacionado con el problema, indicando las unidades en las cuales se medirá.

Recordemos que en los problemas de programación lineal el objetivo será maximizar o minimizar alguna medida de eficiencia, que puede ser un costo, un tiempo, una probabilidad, un número de personas o de elementos, etc. En todos los casos se deben dar explícitamente las unidades de medición.

6. Definir las variables de decisión.

A cada una de las actividades que pueden realizarse se le asocia una variable que indicara el nivel o medida de su ejecución.

En algunos problemas las variables de decisión se pueden tomar en más de una forma posible. Una buena guía para determinar la más conveniente es buscar que las variables correspondan a aquellas actividades que permiten medir el grado de logro de la función objetivo.

7. Formular la función del objetivo del modelo matemático.

Teniendo una correcta comprensión del objetivo y definidas las variables que cuantifican las actividades que conforman el proceso, podemos escribir una función matemática que mida el logro del objetivo. Es la expresión que nos permitirá conocer la eficiencia de la decisión que se tome. 8. Formular las funciones de las restricciones

De la misma manera deben escribirse funciones para expresar las diferentes limitantes que se presentan en el proceso, ya sea en lo referente a valores permitidos para las variables, disponibilidad de recursos, producción total máxima o mínima y muchas otras.

Variables

Las variables son números reales mayores o iguales a cero. $\ X_i >= 0$

En caso que se requiera que el valor resultante de las variables sea un número entero, el procedimiento de resolución se denomina Programación entera.

Restricciones

Las restricciones pueden ser de la forma:

Tipo 1: $A_j = \sum_{i=1}^N a_{i,j} \times X_i$

Tipo 2: $B_j \leq \sum_{i=1}^N b_{i,j} \times X_i$

Tipo 3: $C_j \geq \sum_{i=1}^N c_{i,j} \times X_i$

Donde:

A = valor conocido a ser respetado estrictamente;
B = valor conocido que debe ser respetado o puede ser superado;
C = valor conocido que no debe ser superado;
j = número de la ecuación, variable de 1 a M (número total de restricciones);
a; b; y, c = coeficientes técnicos conocidos;
X = Incógnitas, de 1 a N;
i = número de la incógnita, variable de 1 a N.

En general no hay restricciones en cuanto a los valores de N y M. Puede ser N = M; N > M; ó, N < M.

Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser determinado, y puede no tener sentido una optimización.

Los tres tipos de restricciones pueden darse simultáneamente en el mismo problema.

Principales tipos de restricciones

Aunque para la infinidad de problemas que pueden modelarse para ser resueltos mediante la Programación Lineal se presentan muy diferentes restricciones, podemos decir que las limitantes de un modelo de P.L. se agrupan en seis tipos principales, que son:

Restricciones de capacidad: Relacionadas con los recursos de infraestructura del sistema, como son las horas de mano de obra, de máquina, el espacio, etc.

Restricciones de entradas: Limitan el valor de las variables debido a la disponibilidad de recursos como: materia prima, dinero, etc.

Restricciones de mercado: Son reflejo de los valores máximos o mínimos en las ventas o en el uso del producto o en el nivel de la actividad a realizar.

Restricciones de composición: Son expresiones de las mezclas de los ingredientes, que definen usualmente la calidad de los productos o resultados.

Restricciones de balance de materiales: Expresan las salidas de un proceso en función de las entradas, tomando en cuenta generalmente cierto porcentaje de merma o desperdicio en el proceso.

Restricciones internas: Son las que se escriben para definir el valor de una variable que surge en la formulación del problema, no siendo variable de decisión, sino una variable auxiliar creada para hacer más expedita la construcción del modelo.

Restricciones por políticas administrativas: No hacen parte de la tecnología del problema, sino que obedecen a decisiones administrativas, como por ejemplo no invertir más de cierta cantidad de dinero en alguna opción. Nuevamente se recalca la importancia de tener muy claras las unidades de los datos que se usarán. Esta consideración nos permitirá controlar la homogeneidad en las unidades de los términos de la función del objetivo y en las de las funciones de las restricciones.

En especial debe constatarse que las unidades resultantes al evaluar la expresión del lado izquierdo de una restricción, coincidan con las unidades del lado derecho de la misma. Obviamente cuando un modelo tiene varias restricciones de un mismo tipo, basta con verificar la consistencia en una de ellas.