Programacion lineal

Programación Lineal

se refiere a varias técnicas matemáticas empleadas para asignar, de forma óptima, los recursos limitados a distintas demandas, tareas, operaciones o productos que compiten entre ellos, es decir, la programación de actividades para obtener un resultado óptimo. La programación lineal utiliza un modelo matemático para describir y formular el problema; y el aspecto de lineal se refiere a que todas la funciones matemáticas del modelo deben ser funciones lineales (Ecuaciones o Inecuaciones).

Aplicaciones típicas:

Planeación de operaciones y ventas para encontrar el programa de producción que tenga el costo mínimo.

Análisis de la productividad en la producción o servicios, considerar el grado de eficiencia con el cual los establecimientos de servicios y de manufactura están utilizando sus recursos en comparación con la unidad que tiene mayor desempeño.

Planeación de los productos, encontrar la mezcla óptima de productos, considerando que varios productos requieren diferentes recursos y tienen distintos costos.

Rutas de los productos se refiere a encontrar el camino óptimo para fabricar un producto que debe ser procesado en secuencia.

Programación de vehículos (método de transporte), encontrar la ruta óptima para utilizar los recursos de transporte que involucren el movimiento de productos o materiales de varios puntos llamados origen hacia otros puntos llamados destinos.

Control de procesos, minimizar el volumen de desperdicio de material generado en los procesos de producción, tales como cortes de acero, pieles o telas.

Control de inventario, encontrar la combinación óptima de productos a mantener en existencia dentro de una red de almacenes para garantizar el abastecimiento de las demandas de las líneas de producción.

Otras aplicaciones que se pueden mencionar están la programación de la distribución de embarques, los estudios para ubicar una planta entre distintas alternativas y los programas de manejo de materiales con un costo mínimo.

Construcción de un modelo de programación lineal

Cualquier modelo de PL se compone de tres elementos básicos:

Variables de decisión, que se trata de determinar.

Función objetivo (meta), que se busca optimizar ya sea maximizar (beneficios) o minimizar (costos).

Restricciones que se deben satisfacer.

MÉTODOS PARA LA RESOLUCIÓN DE PROBLEMAS EN PROGRAMACIÓN

LINEAL

4.1. MÉTODO DE REPRESENTACIÓN GRÁFICA.

Consiste en representar las restricciones sobre unos ejes de coordenadas, para delimitar la región dónde se encuentran las soluciones factibles.

Las soluciones óptimas se encontrarán en el perímetro del polígono resultante.

Si nuestra función objetivo es una maximización y la línea que delimita nuestro dominio no es convexa, entonces nuestro problema, bajo estas condiciones, no tiene solución.

4.2. MÉTODO SIMPLEX.

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.

MÉTODO SIMPLEX DE 2 FASES

Esta estrategia se utiliza cuando no es inmediata una solución básica factible inicial en las variables originales del modelo.

FASE 1: Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex

...