Please enable JavaScript.
Coggle requires JavaScript to display documents.
DIFERENTES MÈTODOS PARA LA RESOLUCIÒN DE PROBLEMAS LINEALES, finalidad,…
DIFERENTES MÈTODOS PARA LA RESOLUCIÒN DE PROBLEMAS LINEALES
El método simple de 2 fases
Concepto
Una estrategia algorítmica que se aplica cuando luego de llevar un modelo de programación lineal a su forma estándar no se dispone de una solución básica factible inicial.
Como alternativa al Método de la Gran M
El uso de la constante M
Características
Modelo amplio
Tiene dos faces
Fases
Fase 2
Resolver a través del Método Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase 1
Fase 1
Se determina una solución básica de la ecuación resultante que siempre minimice la suma de las variables artificiales, independientemente de si el modelo de programación lineal es de maximización o de minimización
Si el valor mínimo de la suma es positivo, el problema de PL no tiene una solución factible; de lo contrario prosiga con la fase
Ventajas y desventajas
Desventajas
Se pueden generar confusiones al momento de utilizar las dos funciones objetivo o requerir dos tablas
Ventajas
Evita problemas que se generan en la M grande
Fácil identificación de soluciones no factibles
Método simplex revisado
Concepto
Un algoritmo de George Dantzig para resolver problemas de optimización (de la rama de programación lineal).
Características
Trabaja con muchas matrices
Variable de entrada/ salida
Entrada: Se escoge el valor mas negativo (Maximización)
Salida: Escoge el valor mas pequeño de la operación conocida como "Razón"
Las variables de decisión tienen que ser mayor a 0
Pasos
2.- Calculamos la variable de entrada con lo que seria la fila Zj-Cj, utilizando: Zj-Cj=(CB)(B^-1)(aj)-Cj
Donde:
Cb: Vector de los coeficientes de la función objetivo de las variables XB
aj: Es una matriz de valores en las restricciones que corresponden a las variables no básicas
XB: Vector de variables de decisión básicas
Cj: Son los valores de las variables no básica que en la función objetivo
3.- Calculamos la variable de salida con:
Yi=(B^-1)(ai)
B: Matriz base
ai: Vector que corresponde a los valores de las restricciones de la variable de entrada
-Pasar el modelo a la forma matricial entandar y encontrar una primera solución básica factible
Donde:
A: Matriz de coeficientes tecnológicos
x: Vector columna de n variables de decisión
xs: Vector columna de m variables de holgura
C: Vector renglón de n coeficientes de costo
b: Vector columna de m recursos
I: Matriz identidad de m*m
4.-Por ultimo hay que calcular el nuevo valor de las variables básicas, para eso hay que cambiar la matriz B, pues el vector de las variables básicas cambio
Tenemos que calcular el nuevo valor de Xb con:
Xb=B^-1(b)
Ventajas
Programable
Origen de la matriz identidad
Numérico
Desventajas
Muchas operaciones numéricas
Programación lineal
Conjunto de técnicas racionales de análisis y resolución de problemas
Método Simplex
Origen
Creado en el año de 1947 por el matemático George Dantzing
Resolver problemas de programación lineal, en los cuales intervienen tres o mas variables
Mejorar las respuestas paso a paso, con el fin de alcanzar la solución optima de un problema
¿Qué es ?
Es un método iterativo (repetir varias veces un proceso) que permite ir mejorando la solución en cada paso.
La razón matemática de esta mejora, consiste en
caminar del vértice de un poliedro a un vértice vecino de manera que maximice o minimice
Desventajas
-Converge más lentamente que otros métodos pues requiere mayor número de iteraciones (repeticiones).
Proceso
Paso 3: Definir la solución básica inicial
El Método Simplex parte de una solución básica inicial para realizar todas sus
iteraciones, esta solución básica inicial se forma con las variables de coeficiente
diferente de cero (0) en la matriz identidad.
Paso 4: Definir la tabla simplex inicial
Solución: (segundo término)= En esta fila se consigna el segundo término de la
solución, es decir las variables,
Cj = La fila "Cj" hace referencia al coeficiente que tiene cada una de las variables
de la fila "solución" en la función objetivo
Variable Solución = En esta columna se consigna la solución básica inicial, y a
partir de esta en cada iteración se van incluyendo las variables que formarán parte
de la solución final.
Cb = En esta fila se consigna el valor que tiene la variable que se encuentra a su
derecha "Variable solución" en la función objetivo.
Zj = En esta fila se consigna la contribución total, es decir la suma de los productos
entre término y Cb
Cj - Zj = En esta fila se realiza la diferencia entre la fila Cj y la fila Zj, su significado
es un "Shadow price", es decir, la utilidad que se deja de recibir por cada unidad de
la variable correspondiente que no forme parte de la solución.
Paso 2: Convertir las inecuaciones en ecuaciones.
El objetivo es asignar a cada recurso una variable
Paso 5: Realizar las iteraciones necesarias
Consiste
en realizar intentos mientras el modelo va de un vértice del poliedro objetivo a otro.
Paso 1: Modelación mediante programación lineal
Variables, Restricciones, Función objetivo
Ventajas
--Se basa en consideraciones geométricas y no requiere el uso de derivadas de la función objetivo.
-Es de gran eficacia incluso para ajustar gran número de parámetros.
--Es fácil de implementar y usar, y sin embargo tiene una alta eficacia.
--Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente
Metido grafico
¿Qué es?
Un procedimiento de solución de problemas de programación lineal
Consiste en la representación geométrica de las restricciones para formar la región factible y trazar la función objetivo en el punto óptimo
Características
Se encuentra limitado a problemas de dos o tres variables de decisión
2 si es un gráfico 2D y 3 si es 3D)
Es muy rico en materia de interpretación de resultados e incluso análisis de sensibilidad
Consiste en representar cada una de las restricciones
Pasos
Paso 3: Determinar la región factible
La zona que se genera de la intersección de las restricciones se conoce como región factible.
Esta región puedes ser acotada o no acotada, asimismo en algunos casos las restricciones no forman ninguna región factible.
Paso 4: Trazar la función objetivo
La función objetivo es una recta. Una forma de graficarla es dándole un valor aleatorio como resultado y calcular su dirección en el plano.
Paso 2: Trazar el gráfico de las restricciones
Cada una de las restricciones deben representarse en el gráfico.
Para ello deben determinarse los puntos de intersección con cada eje y sombrear el área correspondiente (de ser el caso). Se debe incluir las restricciones de no negatividad.
Paso 5: Encontrar la solución visual
Ubicar el punto óptimo donde pasará la función objetivo dependiendo si el problema es de maximización o minimización.
El punto óptimo se encontrará en uno de los vértices de la región factible.
Paso 1: Plantear el problema de Programación Lineal
Es un correcto planteamiento matemático.
Paso 7: Determinar el valor óptimo
Finalmente reemplazamos las coordenadas calculadas en el paso anterior en la función objetivo para determinar su valor óptimo
Paso 6: Calcular las coordenadas del punto óptimo
Para calcular las coordenadas del punto óptimo, debes resolver algebraicamente el sistema de ecuaciones que generan las restricciones que cruzan el punto óptimo
Ventajas
Solución rápida
Es visual
Fácil aplicación
Desventajas
Solo es conveniente para dos variables
Método de la M grande
Una derivada del mètodo simplex usado para resolver problemas donde el origen no forma parte de la región factible de un problema de programación lineal.
Pasos Básicos
Pasar al modelo básico del problema.
Agregar ecuaciones variables a aquellas que no tengan de holgura.
Se deben penalizar las variables artificiales en la función objetivo asignándoles conocimientos positivos muy grandes
Con la solución inicial se aplica método simplex acostumbrado.
Características
Variables artificiales
Solución no factible M
Forma amplia
Ventajas y desventajas
Ventaja:
Uso del método simplex
Desventaja
Uso de la M
Convertir vectores unitarios
Uso de pre-etapas para eliminar la M de las variables artificiales
Método Algebraico
Concepto
Es un procedimiento algebraico (aunque sus conceptos fundamentales son geométricos)
Utilizado para resolver problemas de programación lineal
Pasos
2.-Identificar una solución básica factible inicial
Generalmente la primera solución es el origen (si es que pertenece la región factible) si todas las restricciones son menor o igual <=
3.-Determinar si existe una solución factible mejor. Si es así, pasar al siguiente paso, si no la solución actual es la optima.
Identifica cuales son las variables básicas y no básicas
Se despeja el modelo en función a las variables no básicas
Para determinar la nueva variable básica nos fijamos en la función z se toma la variable con el mayor coeficiente (en caso de max) o al menor coeficiente (min)
1.- Pasar el modelo original a su forma estándar
Sumando variables de holgura si la restricción es <=
Identificar el número de variables básicas y no básicas
Características
Procedimiento general para resolver problemas
Desarrollado en 1947
Es expresado con los términos de otra variable
Modalidad
Es aplicable a modelos PL con función objetivo de n
Ventajas
Es más claro entender la razón
Se pueden resolver modelos con cualquier número de variables y ecuaciones.
Desventajas
Despejes de ecuaciones y sustituciones
No es el método utilizado en la práctica para resolver modelos de programación lineal
finalidad
permite
es
es
es
es
ANA FÀTIMA SÀNCHEZ CADENA
