Optimización Programación Lineal
Enviado por Evelyn Grau Monzon • 11 de Septiembre de 2015 • Ensayo • 1.932 Palabras (8 Páginas) • 282 Visitas
Optimización Programación Lineal
Wagner Hugo Gonzales Montes
“La Programación Lineal es una pequeña parte de una teoría matemática que se ha consolidado en el siglo XX con el nombre de Optimización. En general, se trata de un conjunto de técnicas matemáticas que intentan obtener el mayor provecho posible de sistemas económicos, sociales, tecnológicos, cuyo funcionamiento se puede describir matemáticamente de modo adecuado”.
“Una terminología establecida desde los primeros tiempos de la Optimización, denominaba a la solución óptima un programa de acción a poner en práctica; de ahí que la búsqueda de un tal programa de acción utilizando métodos matemáticos se llamase Programación Matemática. Según las características de las funciones del problema y de las variables se tienen diferentes tipos de problemas de Programación Matemática”.
Programación Lineal es un conjunto de métodos racionales de análisis y sobre todo de resolución de diferentes problemas que tiene por objeto el ayudar a los responsables en cada uno de las decisiones sobre los asuntos en los que participan un gran número de variables.
El nombre de programación lineal no resulta de la creación de diferentes programas de ordenadores, sino de un término miliciano, si no que programar significa realizar los diferentes planes o propuestas de tiempo para el adiestramiento de la logística o el despliegue de las unidades.
La programación lineal es una de las técnicas utilizadas con una sola función que es el objetivo lineal, a un conjunto de variables lineales no negativas. Se enfoca en dar soluciones de problemas ya elaborados parta tomar una buena toma de decisión. Se entiende que en el ambiente actual de los negocios, se encontrara diversas aplicaciones en gran cantidad para ser aplicada. |
La función objetivo de un modelo de programación lineal, ve la manera de maximizar o minimizar según la cantidad a definir, una de sus restricciones es limitar o reducir los grados a perseguirse el objetivo. La programación lineal constituye un muy importante sobre todo en el campo de la optimización por diversas razones, que ha conllevado a muchos problemas en las prácticas cuando se está realizando una investigación de operaciones pueden ser planteadas como un problema de programación lineal. Para algunos casos muy especiales en lo que respecta la programación lineal, ya sean como problemas de flujo de redes y además los problemas de flujo de mercancías se pueden considerarar el desarrollo de los estudios matemáticos como lo suficientemente y sobre todo de suma importancia como para poder generar una investigación en la que implique algoritmos especializados en su solución. “El algoritmo simplex está diseñado para localizar la solución óptima concentrándose en un número seleccionado de las soluciones básicas factibles del problema. Siempre empieza en una solución básica factible y después trata de encontrar otra solución básica factible que mejorará el valor del objetivo”. Las ideas de programación lineal se han inspirado mucho en teorías de optimización en las cuales se encuentra la dualidad, la descomposición y la importancia de la convexidad. De tal modo, que la programación lineal es usada en la microeconomía y sobre todo en la administración de empresas, ya que sirve para el aumento del máximo de los ingresos o también al reducir al mínimo los costos de un sistema de producción. “Si todas las funciones del problema, objetivo y restricciones son lineales, se tiene un problema de Programación Lineal.En esta unidad didáctica, diseñada para el curso 2º de Bachillerato de Ciencias Sociales, vamos a estudiar Programación Lineal para dos variables. En este caso particular, todas las actividades pueden ser representadas y estudiadas gráficamente y utilizar el Proyecto Descartes para su resolución”. “Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas”. Según (Stigler, 1945) nos habla del problema de las dietas en la cual, “consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer requerimientos nutricionales. La cantidad de alimentos a considerar, sus características nutricionales y los costos de éstos, permiten obtener diferentes variantes de este tipo de modelos”. El problema de dimensionamiento de lotes en la cual (Wagner y Whitin, 1958), “consiste en hallar una política óptima de producción para satisfacer demandas fluctuantes en el tiempo, de modo de minimizar los costos de producción e inventario, considerando la disponibilidad de recursos escasos”. Es uno de los métodos más famosos en la cual está basado en la localización de una solución básica y el paso de una a otra hasta encontrar la óptima. Para poder verificar que un problema de programación lineal tiene diversas soluciones, se tiene que ver en la tabla final del método simplex ya que cuando un costo reducido está asociado a una variable no básica igual a cero, esto es verificado cuando el valor de la función objetivo termina en la fase uno y es distinto de cero. Se considera como variable no básica con costo reducido negativo cuando se selecciona como variable entrante a las bases de aquella variable no básica, de tal manera que a menos interacción se podrá alcanzar si es que existiera una óptima rapidez de convergencia. La región factible es la que está formada por la intersección o la región común de las soluciones de las diversas inecuaciones. Como sucede con todos los sistemas de ecuaciones lineales, la cual presentan varias opciones con respecto a sus soluciones: ya que puede no existir solución, en el caso de que existiera el conjunto de solución puede ser acotado y a la vez no. Si la región factible está verdaderamente acotada, su representación será gráfica y a la vez es un polígono convexo con una cantidad de números de lados menores o iguales que el número de restricciones. Esto también incluye los lados y los vértices, ya sea según las desigualdades en un sentido amplio o en sentido estricto. Una solución óptima son los puntos de la región factible donde su función objetivo es alcanzar el valor óptimo, ya sea el máximo o el mínimo. Si la solución óptima fuese única, es uno estos vértices de la región factible. “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”. “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”. Para un problema de programación lineal se formula matrices de estándar en la cual A es una matriz de m filas (restricciones) y n columnas (variables), siendo esta “n” mayor igual que “m”. Por lo general las restricciones siempre aparecen en forma de desigual y estas son convertidas en igualdad al incluir las variables de amplitud, esto hace que la hipótesis de que “n” es mayor igual a “m” esté siempre justificada. Se supone que la matriz A tiene un rango m; lo que significa que pueden seleccionarse m columnas de A de tal manera que la matriz que esta formada tenga determinante no nulo. Al requerir que el rango de la matriz A sea m conlleva a evitar que en el problema aparezcan restricciones redundantes o contradictorias. Las restricciones insistentes pueden eliminarse de cada una de la formulación del problema y las discordantes provocan que el espacio de soluciones factibles sea vacío y el problema no tenga solución. Obteniendo dos variables en una programación lineal, si en este caso la región factible existe y sobre todo fuese acotada, el valor óptimo alcanzara uno de los vértices del polígono que limita la región. Si hubiera el caso en el que la región factible no es acotada, necesariamente no alcanza un valor óptimo concreto, si este lo hiciera, éste se encontrara en uno de los vértices de la región. Con una región acotada lo único que se puede hacer es calcular el valor de la función objetivo en cada uno de los vértices del polígono, y necesariamente en aquel valor donde su función sea mayor (o menor) alcanzando el punto óptimo requerido, de esta manera los valores correspondientes a dos vértices coinciden y éstos serán adyacente. Cualquier problema de programación lineal puede disminuir la búsqueda de los conjuntos finitos de punto. Para encontrar todas las soluciones básicas a emplear en un programa lineal se debe de requerir de grandes esfuerzos de cálculo, esto resulta sencillo sobre todo en problemas con mínimas variables de decisión. Dentro de los aspectos de la computación, es la magnitud de los problemas lineales que siempre aparecen en la gran mayoría de las situaciones reales y esto hace impensable su tratamiento mediante el método simplex de forma manual. En diferentes situaciones se debe recurrir al uso de los computadores. Al ser empleado el método Simplex no resulta muy económico viéndolo desde un punto de vista computacional, ya que esta almacenan y calculan muchos números que no son necesarios para la elaboración de dichos problemas. Es de suma importancia resaltar la diferencia entre variables de holgura y variables artificiales. La primera se introducen para convertir desigualdades en igualdades, mientras que las variables artificiales se introducen para facilitar el comienzo del método simplex. La base canónica inicial la configuraremos con las variables de holgura más las variables artificiales necesarias hasta tener esa base canónica. 2.12. Resolución mediante programa de ordenador Si el programa requiere que todas las variables sean no negativas, se pondrán de manera que cumplan esta condición. Las modificaciones deben ser hechas antes de introducir los datos en el programa. Todas las variables de las restricciones deben aparecer en el primer miembro, en tanto que todos los términos constantes (recursos) aparecerán a la derecha. En la columna de variables de holgura (SLACK OR SURPLUS) vienen los resultados de esas variables (por restricción), las de valor cero indicarán que el recurso se ha consumido en su totalidad. El número de variables positivas (decisión + holgura) al finalizar el Simplex debe ser igual al número de restricciones, de lo contrario el problema es degenerado. Conclusión La Programación Lineal es un procedimiento o algoritmomatemático mediante el cual se resuelve un problema indeterminado,formulado a través de ecuaciones lineales, optimizando la funciónobjetivo, también lineal. Como pudimos observar en el desarrollo de este trabajo la programaciónlineal cuenta con diferentes métodos que nos permiten reducir el estode un envió, o bien sea asignar maquinas a trabajos o hombres atrabajos, esta abarca muchos aspectos, permitiéndole a la empresareducir los costos, para así obtener mejores ganancias. La programación lineal no puede ser puesta en práctica sin antes tener nociones de conocimiento y practica básicas de los sistemas lineales, ya que éstos son las bases de las programaciones lineales. La programación lineal se resuelve mediante los sistemas lineales. La programación lineal no solo es utilizada en ámbitos relacionados con las matemáticas sino en situaciones de la vida diaria, en los cuales uno desea desenvolverse y prosperar; es uno de los métodos más eficientes. Referencias
|
...