• Author / Uploaded
• Pavel Echegaray

• Categories
• Programación lineal
• Álgebra
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas

Citation preview

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

Título:

METODO DUAL SIMPLEX

Autor:

Leydy Flores Callejas Enrrique Arrazola Espinoza

Fecha:

24/04/2017

Carrera:

Ingeniería en Sistemas

Asignatura:

Investigación Operativa

Grupo:

A

Docente:

Ing. Edwin Jara Arias

Periodo Académico: 1/2017 Subsede:

Campus-Cochabamba

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

Índice INTRODUCCIÓN................................................................................................................. 1 1. MÉTODO DUAL SIMPLEX .............................................................................................. 2 2. DUALIDAD ...................................................................................................................... 2 2.1. CRITERIO DE FACTIBILIDAD. ................................................................................... 2 2.2. CRITERIO DE OPTIMALIDAD. ................................................................................... 2 3. PLANTEAMIENTO DE DUALIDAD ................................................................................. 4 4. NOTACIÓN ..................................................................................................................... 5 5. FORMULAS .................................................................................................................... 5 6. APLICACIONES: ............................................................................................................. 6 7. PROBLEMAS PROPUESTOS ........................................................................................ 6 8. PREGUNTAS IMPORTANTES: ........................................................................................ 9. CONCLUSIONES ..............................................................................................................

Materia: investigación operativa Carrera: Ingeniería de sistemas

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

Introducción Teoría de la dualidad. El dualismo es una teoría que surge como consecuencia de una profundización en el estudio de la Programación lineal. Esto no es algo nuevo, el problema fue propuesto en el siglo XVII por Fermat. El problema establecía que si tenemos los puntos P1, P2 y P3 en un mismo plano, buscáramos un punto P que minimice la suma de distancias. Esta suma de distancias es, las distancias desde dicho punto P hasta P1, P2 y P3. Dos siglos pasaron y un famoso profesor de Geometría de la universidad de Berlín, Jacob Steiner tomó el problema y lo hizo más práctico, el buscó encontrar un sistema de carreteras que uniera tres aldeas llamadas A, B y C con una longitud mínima. El problema de Fermat está resuelto desde hace siglos, sin embargo aún siguen surgiendo extensiones del mismo, el problema básico se utiliza para encontrar soluciones de mayor complejidad.En 1775, a un siglo de haber resuelto el problema de Fermat surgió un nuevo problema que aparentemente no tenía relación y que resultó ser el primer caso de problema dual en optimización. Se trataba de tomar un triángulo de vértices P1, P2 y P3, se tenía que encontrar el triángulo equilátero circunscrito de mayor área, la solución fue encontrada en 1810 por Vecten utilizando regla y compás. El concepto de dualidad en optimización apareció por primera vez en un trabajo publicado en 1963 por John von Neuman. Problema dual Cada problema de programación lineal (Primal) está estrechamente relacionado con otro problema simétrico a él, denominado problema dual. El dualismo es una teoría que surge como consecuencia de una profundización en el estudio de la programación lineal porque la distribución de los recursos y la formación de los precios son dos aspectos del mismo problema. Entonces la doble formulación de la programación lineal no se debe considerar como un simple ejercicio matemático, sino que una y otra versión del problema viene a explicar dos aspectos económicos distintos para una misma situación polémica. Una propiedad fundamental de la relación entre el primal y el dual es que la solución óptima de cualquiera de estos problemas proporciona la solución óptima para el otro. La importancia de la teoría de la dualidad se puede resumir, entre otros aspectos, en lo siguiente: 

Permite resolver problemas de programación lineal de forma más rápida y sencilla.



Es otra vía para resolver un problema de programación lineal.



Facilita profundizar en el contenido económico del problema original (primal).

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

1

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

1. 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.

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

2

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

2. 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.

2.1. 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.

2.2. 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:

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

3

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

3. 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.

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

4

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

4.Notación matemática: Primo

Contiene m ecuaciones y n variables.

Dual

Contiene n ecuaciones y m variables.

5. 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: Asignatura: Investigación Operativa Carrera: Ingeniería en Sistemas

5

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).

6. Aplicaciones: 6.1. Sistemas y telecomunicaciones: con el método dual simplex podemos resolver problemas relacionados con el control de las organizaciones o sistemas (hombre – maquina). A fin de que se produzcan soluciones que mejor sirvan a los objetivos de la organización. 7. 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

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

≤ 150 𝑋3 ≥ 20

6

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

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

7

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

8. 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 Sistemas

8

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

9. 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 post-optimizació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 Sistemas

9

Título: METODO DUAL SIMPLEX

__________________________________________________________________________________________________________

BIBLIOGRAFÍA Web http://www.gestiondeoperaciones.net/programacion_lineal/como-resolver-un-modelo-deprogramacion-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%20 Simplex%20Dual.html http://cdigital.dgb.uanl.mx/la/1020082518/1020082518_008.pdf

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

10