Programación Lineal. Métodos de Resolución

·         Modelados matemáticos.

·         Métodos gráficos.

·         Método Simplex.

·         Método de dos fases.

·         Método de transporte.

·         Método Vogel.

     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 Kantoróvich, un matemático de origen ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975.

     La Programación Lineal (PL) es una de las principales ramas de la Investigación Operativa. La programación lineal es el campo de la optimización matemática dedicado a maximizar o minimizar (optimizar) 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 expresadas mediante un sistema de ecuaciones o inecuaciones también lineales.

     Modelo de Programación Lineal:

El modelo se construye con tres elementos: variables, restricciones y función objetivo. Una vez obtenido todos estos elementos se procede a presentar el modelo usando una estructura estándar, donde la función objetivo y las restricciones se presentan de forma lineal y todos los términos que contengan variables se colocan al lado izquierdo del operador, siguiendo el orden del subíndice de las variables.

En el modelado de PL (Programación Lineal),  por lo general, se emplea la siguiente terminología:

·         Recurso: Se suele dar este nombre a la materia prima que se tiene para elaborar un producto, pero también se utiliza para indicar la demanda de un producto, el nivel de riesgo, en fin se utiliza para referirse a aquel elemento del problema que debe ser asignado o distribuido entre varias actividades y que posee límites para su uso.

·         Actividades: Se refiere entre que se debe distribuir el recurso, ya sean productos, tareas, entre otros. Están representadas por las variables de decisión y es los que se quiere determinar.

     La estructura matemática general de la programación lineal es la siguiente:

    

Como podemos ver en el modelo la función que se va maximizar o minimizar es la función objetivo, sujeta a (s.a.) las restricciones.  Xj >= 0, es la condición de no – negatividad.

     Las Xj son las variables de decisión  cuyo valor se desea conocer. Aij, bi, cj son parámetros. El vector Cj  [C1, C2,...Cn] se llama “vector de costos” o “vector de precios”.

Aplicaciones Típicas de la Programación Lineal:

     Aparentemente, las estructuras de organización complejas propias de la sociedad moderna han reconocido interesantes problemas de optimización tales como la manera más eficiente de manejar la economía de un país o también la mezcla de ingredientes de un fertilizante para satisfacer las especificaciones agrícolas a costo mínimo. Ambos problemas utilizan el modelo de programación lineal (PL), para optimizar una función lineal condicionada a restricciones lineales, que es sencillo en su estructura matemática, pero poderoso por su gran adaptación a una amplia variedad de problemas.

     La programación lineal es una técnica matemática de resolución de problemas, su desarrollo representa una ayuda a los administradores para tomar decisiones en la asignación de recursos. A continuación aparecen algunas aplicaciones típicas de la PL:

·         Un fabricante desea desarrollar un programa de asignación en producción y una política de inventario que satisfagan la demanda de ventas de periodos futuros. Así se podría cumplir la demanda con mínimo costo total de producción y de inventario.

·         Un analista financiero debe seleccionar una cartera de inversiones a partir de una diversidad de alternativas en acciones y bonos. Se debe establecer la cartera que maximice el rendimiento sobre la inversión asignada.

·         Un administrador de mercadotecnia desea determinar la mejor manera de asignar un presupuesto de publicidad como radio, televisión, periódicos y revistas. Al gerente le gustaría determinar la combinación de medios que maximice la efectividad de la publicidad.

·         Una empresa tiene almacenes en varias. ubicaciones en todo el país. Para un conjunto de demandas de sus productos por parte de sus clientes, la empresa desearía determinar cuánto debe asignar en embarques a cada uno de los almacenes y a cada cliente, de manera que los costos totales de transporte resulten mínimos.

     Estas aplicaciones representan unas cuantas situaciones en las que se ha utilizado con éxito la programación lineal, pero ilustran su potencial en la solución de problemas. Un estudio detallado revela las características comunes de ellas. En el ejemplo 1, el fabricante desea minimizar costos; en el 2, el analista financiero desea maximizar el rendimiento sobre la inversión; en el 3, el gerente de mercadotecnia desea maximizar la efectividad de la publicidad, y en el ejemplo 4, la empresa desea minimizar los costos totales de transporte. 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.

     Los problemas de programación lineal se caracterizan, además, por las condiciones impuestas o restricciones de recursos, que limitan el grado en que se puede cumplir algún objetivo. En el ejemplo 1, el fabricante está limitado por restricciones que requieren que la demanda de producto quede satisfecha y por restricciones respecto a la capacidad de producción. El problema de la cartera del analista financiero está limitado por la cantidad total de fondos de inversión disponibles y las cantidades máximas que se pueden invertir en cada acción o bono. La decisión en la selección de medios del gerente de mercadotecnia, está restringida por un presupuesto de publicidad fijo y por la disponibilidad de los varios medios. En el problema de transportación, el programa de embarques de costo mínimo está restringido al suministro de productos disponibles en cada almacén. La diversidad de condiciones mencionadas, es parte de lo que puede esperar aquel que decida enfrentar un problema, pues las restricciones son otra característica general en todo problema de programación lineal.

Ejemplo Práctico: (Bajo Certidumbre):

     El ejercicio a continuación se considera que es bajo certidumbre puesto que se dispone de toda la información necesaria, se conoce todos los datos y variables, por lo tanto se sabe qué soluciones se puede tomar y se comprenden las repercusiones de las diferentes alternativas entre las que se puede elegir. Con estas condiciones, la probabilidad de tomar una decisión acertada aumenta de manera considerable.

     Una empresa manufacturera está considerando dedicar su capacidad a fabricar 3 productos; llamémoslos productos 1, 2 y 3. La capacidad disponible de las máquinas que podría limitar la producción se resume en la siguiente tabla:

                   

Tipo de Máquina	Tiempo Disponible (horas máquina)
Fresadora	500
Torno	350
Rectificadora	150

El número de horas requeridas por cada unidad de los productos respectivos es:

Tipo de Máquina	Producto 1	Producto 2	Producto 3
Fresadora	9	3	5
Torno	5	4	0
Rectificadora	3	0	2

     El departamento de ventas indica que el potencial de ventas para los productos 1 y 2 es mayor que la tasa de producción máxima y que el potencial de ventas para el producto 3 es de 20 unidades por semana. La utilidad unitaria sería de 30, 12 y 15 UM, respectivamente, para los productos 1, 2 y 3.

     Formúlese el modelo de programación lineal para determinar cuánto debe producir la empresa de cada producto para maximizar la utilidad.

Objetivo: Maximizar la utilidad

Max Z= 30X1 + 12X2 + 15X3

Variable de decisión:

Cantidad a fabricar del producto 1. (X1).

Cantidad a fabricar del producto 2. (X2).

Cantidad a fabricar del producto 3. (X3).

Restricciones:

Capacidad disponible para producción de cada máquina (3 restricciones)

Potencial de ventas para el producto 3. (1 restricción)

No negatividad (1 restricción).

Sujeto a:

     Cualquier valor de X que satisfaga todas las restricciones del modelo es una solución factible.

     Un modelo matemático de decisión, por muy bien formulado que esté, no sirve de nada sino podemos encontrar una solución satisfactoria. Una de las características de la programación lineal es que, gracias a sus propiedades matemáticas, se consigue la solución óptima sin muchas dificultades.

     Otro modelo que se puede aplicar para la resolución de una toma de decisión bajo certidumbre sería el análisis del punto de equilibrio.