Programación lineal

Programación lineal

La programación lineal es actualmente la técnica matemática utilizada más actualmente 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)

Método simplex.

El método simplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal.

El algoritmo denominado simplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss-Jordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo.

Las definiciones siguientes fundamentadas en 3 importantes teoremas, ayudan a entender la filosofía de este eficiente algoritmo.

Teoremas de la Programación Lineal.

El conjunto de soluciones factibles para un problema de P.L. es un conjunto convexo.

La solución óptima del problema de programación lineal, si existe, es un punto extremo (vértice) del conjunto de soluciones factibles. Si dicha solución óptima se tiene para más de un punto extremo, entonces también optimiza en cualquier punto que sea combinación convexa lineal entre los dos vértices que optimiza.

Modelo de asignación

El problema de la asignación es encontrar un matching de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática.

Una descripción apropiada de lo que trata de lograr el modelo de asignación es: “La mejor persona para el trabajo”

El problema de asignación tiene que ver con la designación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas, etc. En otras palabras, a la disposición de algunos recursos (maquinas o personas) para la realización de ciertos productos a costo mínimo.

Una definición más formal pudiera ser:

Problema de Asignación: Caso particular del problema de Transporte donde los asignados son recursos destinados a la realización de tareas, los asignados pueden ser personas, máquinas, vehículos, plantas o períodos de tiempo. En estos problemas la oferta en cada origen es de valor 1 y la demanda en cada destino es también de valor 1.

En su forma más general, el problema es como sigue:

Hay un número de agentes y un número de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar dependiendo del agente y la tarea asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignación sea minimizado.

Este tipo de problemas son lineales, con una estructura de transporte, sólo que la oferta en cada origen es de valor uno y la demanda en cada destino es también de valor uno. Sería muy ineficiente resolver este tipo de problemas por medio del método simplex o por medio del de transporte. Debido a la estructura propia de los problemas de asignación, existen métodos de solución llamados algoritmos de asignación que son más eficientes que el simplex o que el método de transporte.

Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino. La restricción importante para cada agente es que será designado a una y solo una tarea.

Características

El problema de asignación presenta las siguientes características:

El Problema de Asignación debe estar equilibrado, es decir, que las ofertas y las demandas sean igual a 1. Un elemento importante para el problema de asignación es la matriz de costos, si el número de renglones o columnas no son iguales el problema esta desbalanceado y se puede obtener una solución incorrecta, para obtener una solución correcta la matriz debe ser cuadrada.

Si el número de agentes y tareas son iguales y el coste total de la asignación para todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema de asignamiento lineal. Normalmente, cuando hablamos de problema de asignación sin ninguna matización adicional, nos referimos al problema de asignamiento lineal.

Oferta: Cantidad que representa la disponibilidad del artículo en la fuente/fabrica de donde proviene.

Demanda: Cantidad de artículos que necesita recibir el destino para cumplir sus necesidades.

Diferencias con el Modelo de Transporte y Asignación

Los problemas de asignación son un caso particular de los problemas de transporte y constituyen la clase más sencilla de los problemas lineales, en el cual los trabajadores representan las fuentes y los puestos representan los destinos.

En el problema de transporte existen m orígenes y n destinos, y el flujo se realiza desde un origen hacia cada uno de los diferentes

...