• Author / Uploaded
• Miriam Reyes

Citation preview

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

Título:

METODO DUAL SIMPLEX

Autor:

Eloy Chambi Lenis José O. Ferrufino Vargas

Fecha:

05/10/2016

Carrera:

Ingeniería en Telecomunicaciones

Asignatura:

Investigación Operativa

Grupo:

A

Docente:

Ing. Edwin Jara Arias

Periodo Académico: 2/2016 Subsede:

Cochabamba

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

MÉTODO DUAL SIMPLEX El método dual-simplex se aplica para resolver problemas que empiezan con factibilidad dual, es decir, óptimos pero infactibles.

Un problema se puede resolver por el método dual-simplex, cuando, después de igualar acero la función objetivo y convertir las restricciones en ecuaciones, agregando las variables de holgura necesarias, al menos uno, cualquiera de los elementos del vector b (vector de disponibilidades) es negativo y la condición de optimalidad se satisface.

Un comparativo entre el método simplex y el método dual-simplex.

El método dual-simplex requiere de la aplicación de dos criterios para su solución: El criterio de optimalidad que asegura que la solución permanecerá óptima todo el tiempo y el criterio de factibilidad que forza las soluciones básicas hacia el espacio factible.

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

DUALIDAD El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual. La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta Aporta

varias elementos

que

aumentan

sustancialmente

utilidades: la

compresión

de

la

PL.

El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.

El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.

La forma estándar general del primal se defina como; para maximizar o minimizar.

CRITERIO DE FACTIBILIDAD. La variable saliente será aquella variable básica que tenga el valor más negativo en el vector bi. Si todas las variables básicas son positivas o sea 0 se tiene la solución final, óptima y factible.

CRITERIO DE OPTIMALIDAD. La variable entrante se selecciona de entre las variables nobásicas como sigue:

Dividir los coeficientes de la ecuación cero entre los coeficientes de la ecuación asociada con la variable saliente, ignorando denominadores positivos y/o ceros. La variable entrante será aquella cuyo cociente sea el menor, si el problema es de minimizar, ó el de menor valor absoluto si es de maximizar. Si todos los denominadores son 0, el problema no tendrá solución factible.

La aplicación del método dual-simplex es especialmente útil para el tema de análisis de sensibilidad. El procedimiento del método dual-simplex se explicara más objetivamente con los siguientes ejemplos:

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

PLANTEAMIENTO DE DUALIDAD Todo problema de programación lineal tiene asociado con él otro problema de programación lineal llamado DUAL. El problema inicial es llamado PRIMAL y el problema asociado (sombra) es llamado el problema PRIMAL. Los dos juntos son llamados problemas duales ya que ambos están formados por el mismo conjunto de datos. La solución básica factible óptima de estos problemas es tal que una puede fácilmente ser usada para la solución de la otra. La dimensión del problema de programación lineal influencia la elección del cálculo del primo o del dual. Si el primo tiene mas ecuaciones que variables, es frecuentemente mas fácil obtener la solución del dual ya que menor numero de iteraciones son requeridas. Además si el primo tiene solución, el dual tendrá procedimiento

de

solución.

Una

vez

que

el problema

dual es formulado,

el

solución es exactamente el mismo que para cualquier problema de

programación lineal.

MECÁNICAMENTE EL DUAL ES FORMULADO PARTIENDO DEL PROBLEMA PRIMO EN LA SIGUIENTE FORMA:

Si el primo es un problema de Maximización, el dual es un problema de Minimización y viceversa. 1. Los coeficientes de la función objetivo del primo se convierten en las restricciones constantes de las ecuaciones del dual. 2. Las restricciones de las ecuaciones del primo

se convierten en los coeficientes de la

función objetivo del dual. 3. Los coeficientes de las variables del dual en las ecuaciones restrictivas son obtenidas sacando la transpuesta de la matriz de coeficientes del primo ( los arreglos de los coeficientes en las columnas del primo se convierten en los coeficientes de las filas en el dual y viceversa ). 4. Los signos de la desigualdad son invertidos. 5. Las Xn variables del primo son remplazadas por Wm variables en el dual.

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

Notación matemática: Primo

Contiene m ecuaciones y n variables.

Dual

Contiene n ecuaciones y m variables.

FORMULAS

 Elección de la fila que sale: Cuando una variable se vuelve básica, es decir, entra en la base, comienza a formar parte de la solución. Observando los costes reducidos en la fila Z, se decide que entra a la base la variable de la columna en la que éste sea el de menor valor (o de mayor valor absoluto) entre los negativos. FILA QUE SALE = (coeficiente del lado derecho más negativo)

 Elección de la variable que entra: Una vez obtenida la fila que sale, se determina que columna entra es la que se encuentre en aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente positivos (teniendo en cuenta que esta operación se hará únicamente cuando Pj sea superior a 0). 𝒇𝒊𝒍𝒂 𝒁

Columna que ingresa = Es el valor absoluto más cercano a 1 de ( 𝒇𝒊𝒍𝒂 𝒒𝒖𝒆 𝒔𝒂𝒍𝒆)

 Elemento pivote:

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

El elemento pivote de la tabla queda marcado por la intersección entre la columna de la variable entrante y la fila de la variable saliente.

 Actualización de la tabla: Las filas correspondientes a la función objetivo y a los títulos permanecerán inalteradas en la nueva tabla. El resto de valores deberán calcularse como se explica a continuación:  En la fila del elemento pivote cada nuevo elemento se calcula como:

Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote.  En el resto de las filas cada elemento se calcula:

Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote). De esta forma se consigue que todos los elementos de la columna de la variable entrante sean nulos salvo el de la fila de la variable saliente cuyo valor será 1. (Es análogo a utilizar el método de Gauss-Jordan para resolver sistemas de ecuaciones lineales). PROBLEMAS PROPUESTOS 1.- considere el siguiente problema de programación lineal 𝑀𝑎𝑥 𝑍 = 5𝑋1 + 4𝑋2 + 5𝑋3 s.a. 6𝑋1 + 2𝑋2 + 3𝑋3 ≤ 350 5𝑋1 + 3𝑋2

≤ 150 𝑋3 ≥ 20

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

2. considere el siguiente problema de programación lineal

3. Considere el siguiente modelo de PL y determine su solución por el método dual-simplex. Maximizar. Z= -4X1 -12 X2 -18 X3 S.A. X1 +3X3 3 +2X2 +2X3 5 X10 ,

X20 X30

4. Considere el siguiente modelo de PL y determine su solución por el método dual-simplex. Maximizar.

Max Z = 4X1 +5 X2 +5 X3 S.A. 2X1 +3X2 +4X3 ≤50 5X2 +2X3 +X3 ≤120 3X1 +2X3 ≥30

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

PREGUNTAS IMPORTANTES: ¿ Por qué se plantea el programa dual?. Por una parte permite resolver problemas lineales donde el número de restricciones es mayor que el número de variables. Gracias a los teoremas que expondremos a continuación la solución de unos de los problemas ( primal o dual) nos proporciona de forma automática la solución del otro programa.

¿ Qué significado tiene su solución?. La dualidad permite realizar importantes interpretaciones económicas de los problemas de programación lineal.

¿ La solución del dual se puede obtener desde el primal?. La dualidad permite generar métodos como el método dual del simplex de gran importancia en el análisis de post- optimización y en la programación lineal parametrica.Otra de las ventajas de la dualidad, es la posibilidad de resolver gráficamente algunos problemas. Consideremos el siguiente problema lineal: Min Z(x) = 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5 s.a: x1 + x2 + 2 x3 + x4 + 3 x5 ≥ 4 2 x1 - x2 + 3 x3 + x4 + x5

≥3

x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x4 ≥ 0 , x5 ≥ 0 Dado que se trata de un programa lineal en forma canónica, ello nos proporciona un dual en forma simétrica como el siguiente: Max G() = 4 1 + 3 2 s.a: 1 + 2 2  2 1 - 2

3

2 1 + 3 2  5 1 + 2

2

3 1 + 2

3

1  0 , 2  0

Asignatura: Investigación Operativa Carrera: Ingeniería en Telecomunicaciones

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

CONCLUSIONES  La dualidad permite realizar importantes interpretaciones económicas de los problemas de programación lineal y así como también generar métodos como el método dual del simplex de gran importancia en el análisis de postoptimización y en la programación lineal paramétrica.  La resolución de los problemas duales respecto a los primales se justifica dada la facilidad que representan dados problemas, donde el número de restricciones supere al número de variables. Además de tener gran aplicación en el análisis económico del problema.  La diferencia principal del método simplex y el método dual, es que el simplex se inicia con una solución factible y la mantiene mientras busca conseguir la optimización. El método dual inicia con una solución óptima pero no factible y busca la factibilidad manteniendo la optimización.  En conclusión bajo ciertas hipótesis, los problemas primal y dual dan lugar al mismo valor óptimo de la función objetivo, y por tanto se puede resolver indirectamente el problema primal resolviendo el problema dual.

Asignatura: Investigación Operativa Carrera: Ingeniería en Telecomunicaciones

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

BIBLIOGRAFÍA Web http://www.gestiondeoperaciones.net/programacion_lineal/como-resolver-un-modelode-programacion-lineal-con-el-metodo-simplex-dual/ http://inv-oper4rmb.blogspot.com/2008/04/metodo-dual.html https://www.clubensayos.com/Historia/Metodo-Dual/2257585.html https://inveoperaciones.wordpress.com/el-problema-dual-y-el-metodo-dual-simplex/ http://www.phpsimplex.com/simplex/page4.php?f=0&l=es file:///C:/Users/Usuario/Pictures/Investigacion%20de%20Operaciones_%20Metodo% 20Simplex%20Dual.html http://cdigital.dgb.uanl.mx/la/1020082518/1020082518_008.pdf

Asignatura: Investigación Operativa Carrera: Ingeniería en Telecomunicaciones