Que Es Programación Lineal.docx

QUE ES PROGRAMACIÓN LINEAL

La programación lineal u optimización lineal, es un método matemático para determinar la forma de lograr el mejor resultado (por ejemplo, el máximo beneficio o el costo más bajo) de un modelo matemático dado por alguna lista de requisitos representados por relaciones lineales. La programación lineal es un caso particular de programación matemática. La técnica matemática conocida por programación lineal se utiliza para obtener una solución óptima a un problema condicionado por unas variables de partida sujetas a ciertas restricciones. Un problema clásico de la programación sería el siguiente: teniendo n productos del tipo A y m del tipo B, que pueden envasarse en dos clases de paquetes en diferentes proporciones y con un precio distinto para cada paquete, cuántos paquetes de cada tipo deberán formarse para obtener una cantidad máxima de ingresos. En el planteamiento del problema se manejan varios conceptos esenciales:  Las variables.  Las restricciones que se imponen, expresadas por inecuaciones lineales.  La función objetivo, de tipo lineal, que describe el problema. El grupo de las soluciones posibles recibe el nombre de conjunto restricción o conjunto solución factible. La solución debe situarse en el área definida por las inecuaciones de restricción, que se conoce por región factible.

Región factible del sistema de inecuaciones lineales: La región factible puede estar acotada, como en la figura, o no acotada. Cuando está acotada, se representa gráficamente como un polígono con un número de lados menor o igual que el de restricciones (en la figura, el polígono acotado tiene cuatro lados, y las restricciones también son cuatro). Se llama solución óptima a la que maximiza o minimiza la función objetivo. Esta solución si es única siempre se encuentra en un vértice o punto extremo de la región factible.

METODOS DE RESOLUCION DE PROGRAMACION LINEAL

Clasificación de los métodos

MÉTODO

CARACTERÍSTICAS

VENTAJAS

DESVENTAJAS

GRÁFICO

*Solo trabaja con dos o tres variables * Gráfica la función objetivo y las restricciones *Ubica en la región factible solución óptima, no factible, múltiple o no acotada *Se trabaja directamente en la forma canónica *Encuentra la solución en la gráfica directamente

*Es relativamente fácil de hacer y entender *Ubica todos los puntos extremos que son una solución factible *No hay que pasar a la forma estándar.

*Solo funciona con 2 ó 3 variables *Puede ser inexacto al tener muchas restricciones

ALGEBRAICO *Es parecido al método simplex *Se mueve entre puntos extremos empezando en el origen *Se trabaja en la forma estándar. *Encuentra la solución cuando z ya no puede o empeora en una siguiente iteración

*Trabaja rápido en modelos sencillos * Describe en cada iteración como se comportan las variables y que valor tiene z *Funciona par modelos de n variables

*Requiere revisar constantemente que se esta moviendo correctamente. *El álgebra o como elegir las variables de entrada puede llegar a ser confuso * Realizar todo el proceso puede ser mucho mas tardado que el método simplex

SIMPLEX

*Trabaja muy rápido para encontrar la solución óptima *Funciona para modelos de n variables

*Requiere un cuidado muy grande del álgebra *No funciona si el origen no es parte del conjunto de soluciones factibles *Puede caer en un ciclo si no se tienen consideraciones, pero es muy raro

*Trabaja en la forma estándar *El origen tiene que ser una solución factible *Se mueve a través de los puntos extremos *Describe cómo aumenta o disminuye z y dice que ocurre con las variables *A través de los coeficientes describe si se llega a una solución óptima, no factible, no restringida o múltiple

DE LA GRAN M

*Trabaja con el modelo ampliado *Tiene variables artificiales que están multiplicadas por un valor muy grande denominado por M *Las variables artificiales son poco atractivas para elegirlas como variable de entrada *Trabaja con modelos donde la solución inicial no tiene que ser el origen. *Si no se puede eliminar a M, entonces no hay solución factible *Se considera primera al factor multiplicativo más negativo para maximización y después al aditivo

*Funciona con cualquier tipo de modelo lineal donde las variables son reales. *Facilita distinguir a las variables duales en el análisis de decisiones

*El álgebra llega a complicarse demasiado con las M. *Es difícil de introducir en una computadora

DE LAS DOS FASES

*Trabaja con la forma ampliada *Trabaja con cualquier modelo. *Tiene dos fases: en la primera se plantea una función de minimización donde las variables son las v. artificiales y las restricciones son las mismas que en el modelo ampliado para ubicar la solución inicial *En la segunda fase se continua el método quitando las v. artificiales y retomando la función objetivo original pero con los valores ya dados en las restricciones de la anterior fase *Si existe una v. artificial en la base al final de la primera fase, entonces se fuerza a esta a salir de la base.

*Evita muchos problemas del método de la gran M *Se pasa fácilmente del modelo ampliado a la forma estándar

*Resulta confuso el momento en el cual hay que cambiar de la función objetivo modificada a la función original. *Requiere realizar dos tablas simplex por separado o una donde se juntan las dos funciones objetivo *Es complicado o imposible visualizar lo que esta pasando en este modelo de una forma gráfica durante la primera fase

SIMPLEX REVISADO

*Es una diferente forma de realizar el método simplex *Se realiza tomando solamente los cálculos necesarios que se ocupan en toda la tabla del método simplex y expresándolo en forma de matrices *Requiere el uso de matrices inversas

*Encuentra soluciones mas rápido porque no requiere tantos cálculos *Es mas sencillo de programar *Puede aceptar cualquier tipo de modelo bajo ciertos

*Tiene los mismo inconvenientes que el método simplex: normalmente no acepta funciones que no tengan solución en el origen. *Puede complicarse el calculo de la inversa o la multiplicación entre matrices *Requiere demasiadas tablas a

y multiplicación de matrices *Puede aplicarse ciertos criterios a este método para hacerlo parecido al método de las dos fases.

criterios especiales

comparación del método de la M grande