Programacion lineal

INTRODUCCIÓN:

A pesar de que la programación lineal se empezó a estudiar desde finales del siglo XIX no fue hasta mediados del presente siglo en que tuvo auge como técnica matemática aplicable a los problemas de la empresa.

El Dr. G. Damtzing desarrolló el método simplex y con ello hizo posible la solución de grandes problemas modelados con programación lineal que solo quedaban en la situación de estudios. Paralelamente a la invención de este método a partir de mediados del siglo se desarrollo la computación digital y se pudo tener resultados óptimos a los problemas estudiados que se quedaron como modelos.

La programación lineal es actualmente la técnica matemática mas utilizada gracias a que el algoritmo simplex es muy eficiente y al desarrollo de la computación.

Lo que se busca con la aplicación de la programación lineal es resolver problemas comunes y a la vez muy variados de la empresa en donde en general se tienen necesidades por satisfacer con cierto número de recursos limitados o escasos y con el objetivo de lograrlo en forma óptima. Esto significa la búsqueda de un valor máximo cuando se trata de beneficios; o bien la búsqueda de un mínimo cuando se trata de esfuerzos a desarrollar.

Un modelo de programación lineal es un conjunto de expresiones matemáticas las cuales deben cumplir la característica de linealidad que puede cumplirse siempre y cuando las variables utilizadas sean de primer grado. Además un modelo de P.L debe tener las propiedades de:

• Proporcionalidad

• Aditividad (adición)

• Divisibilidad

• Certidumbre(certeza)

1.- FORMULACIÓN Y APLICACIÓN DE MODELOS DE PROGRAMACIÓN LINEAL

Los modelos de programación lineal son muy variados y sus modelos adoptan muchas formas. Esta diversidad puede confundir y hace difícil reconocer cuándo puede aplicarse la programación lineal para estudiar problemas administrativos.

La capacidad para reconocer la aplicabilidad de la programación lineal es una aptitud administrativa y desarrollar esta aptitud es el objetivo de la presente unidad.

La formulación y análisis de un modelo de programación lineal proporciona información para ayudar a los gerentes a tomar decisiones. Esto significa que el modelo refleja con precisión la perspectiva administrativa del problema. La programación lineal es una técnica determinista de análisis para elegir la mejor entre muchas alternativas. Con frecuencia, seleccionar una alternativa incluye satisfacer varios criterios al mismo tiempo. Por ejemplo, cuando se compra una pieza de pan se tiene el criterio de frescura, tamaño, tipo (blanco, de centeno u otro), costo y rebanado o sin rebanar. Se puede ir un paso más adelante y dividir estos criterios en dos categorías; restricciones y el objetivo.

Las restricciones son las condiciones que debe satisfacer una solución que está bajo consideración. Si más de una alternativa satisface todas las restricciones, el objetivo se usa para seleccionar entre todas las alternativas factibles. Cuando se elige una pieza de pan, puede quererse un paquete de pan blanco rebanado y hecho no antes del día anterior. Si varias marcas satisfacen estas restricciones, puede aplicarse el objetivo de un costo mínimo y escoger el más barato.

Existen muchos problemas en la empresa que se ajustan a este molde de tratar de minimizar o maximizar un objetivo que está sujeto a una lista de restricciones. Un corredor de inversiones, por ejemplo, trata de maximizar el rendimiento sobre los fondos invertidos pero las posibles inversiones están restringidas por las leyes y las políticas bancarias. Un hospital debe planear que las comidas para los pacientes satisfagan ciertas restricciones sobre sabor, propiedades nutritivas, tipo y variedad, al mismo tiempo que se trata de minimizar el costo. Un fabricante, al planear la producción futura, busca un costo mínimo al mismo tiempo cómo cumplir restricciones sobre la demanda del producto, la capacidad de producción, los inventarios, el nivel de empleados y la tecnología. La programación lineal se ha aplicado con éxito a estos y otros problemas. El objetivo y cada una de las restricciones en la (PL) se deben expresar como una relación lineal, de ahí el nombre de programación lineal.

Para las aplicaciones más reales es necesaria una computadora para resolver el modelo. A pesar de sus limitaciones, la programación lineal, (PL) es una de las técnicas más poderosas y útil para la solución de los problemas en las organizaciones.

Conceptos de formulación de modelos

Ya sea simple o complejo, un modelo es una representación que idealiza, simplifica y abstrae selectivamente la realidad, y esta representación es construida por individuos, por lo que la creación de modelos incluye una gran cantidad de arte e imaginación así como de conocimientos técnicos. A manera de guía, podemos dividir el proceso de construcción de un modelo cuantitativo en tres etapas:

1. Se estudia el ambiente. La experiencia puede ser el ingrediente más esencial del éxito, la experiencia tanto en construcción de modelos como en el trabajo en el ambiente que se estudia.

2. Se formula una representación selectiva de la realidad. Implica un análisis conceptual básico en el que se deben hacer conjeturas y simplificaciones. El proceso de formulación requiere que el constructor del problema seleccione o aísle del ambiente aquellos aspectos de la realidad que sean relevantes dentro del ámbito del problema. Puesto que los problemas que nos interesan implican decisiones, restricciones y objetivos, deben ser explícitamente identificados y definidos. Una vez que se ha realizado la formulación lógica se debe elaborar una forma simbólica del modelo. En cierto sentido, formulación y construcción son procesos integrados, siendo la formulación el aspecto lógico conceptual y la construcción la expresión de las relaciones lógicas en el lenguaje simbólico de las matemáticas.

3. Se formula una representación simbólica (es decir con expresiones matemáticas) del modelo. Las interacciones entre la formulación y la construcción simbólica por lo común son críticas. Por lo que se requiere que los modelos sean construidos por grupos heterogéneos o interdisciplinarios de expertos en varios campos.

2.- MÉTODO GRÁFICO

El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones).

La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema.

EJEMPLO 1:

Una compañía de auditores se especializa en preparar liquidaciones y auditorías de empresas pequeñas. Tienen interés en saber cuantas auditorías y liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de liquidaciones mensuales disponibles es de 60.

OBJETIVO: Maximizar el ingreso total.

VARIABLE DE DECISION: Cantidad de auditorías (X1).

Cantidad de liquidaciones (X2).

RESTRICCIONES: Tiempo disponible de trabajo directo

Tiempo disponible de revisión

Número máximo de liquidaciones.

Maximizar

Sujeto a:

La solución óptima siempre se encuentra en uno de los vértices del conjunto de soluciones factibles. Se analizan estos valores en la función objetivo. El vértice que representa el mejor valor de la función objetivo será la solución óptima.

3.- MÉTODO SIMPLEX

El método simplex

Hasta ahora se han resuelto problemas de programación lineal a través de un método geométrico. Este método no resulta práctico cuando el número de variables se aumenta a tres, y con más variables resulta imposible de utilizar. Ahora se examinará una técnica diferente, el método simplex, cuyo nombre está asociado en análisis más avanzados a un objeto geométrico al que se denomina simplex.

El método simplex comienza con una solución factible y prueba si es o no óptima. Si no lo es, el método sigue a una mejor solución. Se dice mejor en el sentido de nueva solución no es óptima, entonces se repite el procedimiento. En algún momento el método simplex conduce a una solución óptima, si es que existe.

Además de ser eficiente, dicho método tiene otras ventajas. Es completamente mecánico (se utilizan matrices, operaciones elementales sobre renglones y aritmética básica). Asimismo, no implica el uso de geometría. Esto permite resolver problemas de programación lineal que tiene cualquier número de restricciones y variables.

El problema normal de programación lineal es de la forma.

Maximizar Z = C 1 X 1 + C 2 X 2 +...................+ C n X n

Sujeto a: a 11x 1 + a 12 x 2 +............................ a 1 n x n

b 1

A 12x 1 + a 22 x 2 +............................

...