• Author / Uploaded
• Gustavo Mendoza

Citation preview

INSTITUTO POLITECNICO NACIONAL ESCUELA SUPERIOR INGENIERIA Y ARQUITECTURA UNIDAD ZACATENCO INGENIERIA EN SISTEMAS METODO DUAL SIMPLEX PROFESORA: ANGELICA MENDOZA EURASMO ALUMNOS: AGUILAR GUITIERREZ EDGAR MENDOZA CRUZ GUSTAVO VENTURA CERRITEÑO FRANCISCO

1

GRUPO: 6CV14 FECHA DE ENTREGA: 21/ABRIL/2016

ÍNDICE Pág.

Método Dual Simplex……………….. ……………………….................3 Relaciones Primal-Dual………. ………………………….....................3 Tabla de TUCKER. ……………………………………............................5 ¿Por qué se plantea el programa dual? ………………………………6 ¿Qué significado tiene su solución?…. ………………......………….7 ¿La solución del dual se puede obtener desde el primal?....7 Teorema de Existencia…………………………………………. …………..7 Teorema de Dualidad…………………………………………………… …..8 Teorema de Holgura complementaria……………………………….8 2

Relaciones entre las soluciones del programa primal y del programa dual………………………………………………………… ………..8 Interpretación Económica de las variables Duales…………….8 Ejercicio paso a paso………………………………………………………… 9 Aplicación en la Ingeniería Civil………………………………………..13 Conclusión………………………………………………… …………………….14 Bibliografía……………………………………………… ……………………….14

Método Dual Simplex Este método se aplica a problemas óptimos pero infactibles. En este caso, las restricciones se expresan en forma canónica (restricciones). La función objetivo puede estar en la forma de maximización o de minimización. Después de agregar las variables de holgura y de poner el problema en la tabla, si algún elemento de la parte derecha es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse por el método dual simplex. Note que un elemento negativo en el lado 3

derecho significa que el problema comienza óptimo pero infactible como se requiere en el método dual simplex. En la iteración donde la solución básica llega a ser factible esta será la solución óptima del problema. CONDICION DE FACTIBILIDAD. La variable que sale es la variable básica que tiene el valor más negativo (los empates se rompen arbitrariamente si todas las variables básicas son no negativas, el proceso termina y esta última tabla es la solución óptima factible). CONDICION DE OPTIMIDAD. La variable que entra se elige entre las variables no básicas como sigue. Tome los cocientes de los coeficientes de la función objetivo entre los coeficientes correspondientes a la ecuación asociada a la variable que sale. Ignore los cocientes asociados a denominadores positivos o cero. La variable que entra es aquella con el cociente más pequeño si el problema es de minimizar o el valor absoluto más pequeño si el problema es de maximización (rompa los empates arbitrariamente). Si los denominadores son ceros o positivos el problema no tiene ninguna solución factible.

Relaciones Primal-Dual Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual (PD) , que posee importantes propiedades y relaciones notables con respecto al problema lineal original, problema que para diferencia del dual se denomina entonces como problema primal (PP). Las relaciones las podemos enumerar como siguen: • a) El problema dual tiene tantas variables como restricciones tiene el programa primal. 4

• b) El problema dual tiene tantas restricciones como variables tiene el programa primal • c) Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal. • d) Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal. • e) La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal. • f) El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del sentido de las restricciones del mismo problema. (tabla de TUCKER) • g) Si el programa primal es un problema de maximización, el programa dual es un problema de minimización. • h) El problema dual de un problema dual es el programa primal original.

TABLA DE TUCKER RESTRICCIONES

≤

≥

≥

≤

=

> 
 
< 0, es decir, variables libres.

¿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 pos optimización y en la programación lineal paramétrica. 7

Teorema de existencia La condición necesaria y suficiente para que un problema de programación lineal tenga solución es que, tanto el conjunto de oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos problemas sean factibles. • ∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅ Corolario del teorema de existencia • Una vez analizadas las condiciones que han de cumplirse para que exista solución óptima, vamos a ver los diferentes casos posibles: • a) S ≠ ∅ ∧ S’ ≠ ∅ Ambos problemas tienen solución óptima finita. • b) S = ∅ ∧ S’ ≠ ∅ El programa primal es infactible, y el programa dual es no acotado. • c) S ≠ ∅ ∧ S’ = ∅ El programa dual es infactible, y el programa primal es no acotado. • d) S = ∅ ∧ S’ = ∅ Ambos problemas son infactibles.

Teorema de la Dualidad La condición necesaria y suficiente para que exista solución óptima del primal ( x* ), es que exista una solución óptima para el dual ( λ* ) y que valor de la función objetivo de ambos programas sea igual, es decir Z(x* ) = G(λ* ). •

∃ x* ←→ ∃ λ* / Z(x* ) = G(λ* )

Teorema del Holgura complementaria 8

La condición necesaria y suficiente para que (x* , λ* ) sean soluciones óptimas del programa primal y dual, es que satisfagan las condiciones de holgura complementaria: • ( c - λ* A ) x* = 0 • λ* ( b - A x* ) = 0

Relaciones entre las soluciones del programa primal y del programa dual. Tanto el programa primal como el programa dual son dos formas de abordar el mismo problema, y por lo tanto, si tienen solución, tienen la misma solución. Entonces, cabe preguntarse cuál es la relación entre las soluciones de ambos problemas.

Interpretación económica de las variables duales El significado de las variables duales es el mismo que en el caso de los multiplicadores de Lagrange, es decir miden la sensibilidad de la función objetivo respecto a cambios (infinitesimales) de los términos independientes de cada restricción.

Ejercicio Paso a Paso • F.O. • Min. Z = 4X1 + 12X2 + 18X3 • S.A. • X1 + 3X3 ≥ 3 • 2X2 + 2X3 ≥ 5 • X1, X2, X3 ≥ 0 9

PASO 1: Convertir el problema de minimización en uno de maximización. La función objetivo se multiplica por -1 • F.O. • Max. Z = - 4X1 - 12X2 - 18X3 • Las restricciones se multiplican por -1 • S.A. • X1 - 3X3 ≤ -3 • 2X2 - 2X3 ≤ -5 •

X1, X2, X3 ≥ 0

PASO 2: Se ecuaciones.

convierten

las

inecuaciones

en

• F.O. • Z + 4X1 + 12X2 + 18X3 = 0 • S.A. • - X1- 3X3 + S1 = -3 • – 2X2 - 2X3 + S2 = -5 PASO 3: Se determinan las variables básicas y no básicas. • Básicas: S1 y S2 • ·No Básicas: X1, X2 y X3 PASO 4: Elaborar la tabla inicial del simplex. Variab le

Variab les 10

Soluci ón

Básica X1

X2

X3

S1

S2

S1

-1

0

-3

1

0

-3

S2

0

-2

-2

0

1

-5

Z

4

12

18

0

0

0

PASO 5: Determinar la variable que sale (fila pivote) Es el número más negativo de la solución de las restricciones = fila de S2 Varia ble Básic a

Variab les

Soluci ón

X1

X2

X3

S1

S2

S1

-1

0

-3

1

0

-3

S2

0

-2

-2

0

1

-5

Z

4

12

18

0

0

0

PASO 6: Determinar la variable que entra (columna pivote). • Razón = Coeficiente de Z / coeficiente fila pivote. • Razón Mayor = Columna X2 (-12 / 2) Varia ble

Variab les 11

Soluci ón

Básic a

X1

X2

X3

S1

S2

S1

-1

0

-3

1

0

-3

S2

0

-2

-2

0

1

-5

Z

4

12

18

0

0

0

Razón -

-6

-9

-

0

PASO 7: Elaborar la nueva tabla del simplex. • A) Nueva fila pivote = Fila pivote / elemento pivote • Fila Pivote •

0

-2

-2

0

1

-5

•

-2

-2

-2

-2

-2

-2 Elemento Pivote

•

0

1

1

0 -0,5 2,5 Nueva Fila Pivote

• B) Nuevas filas = fila anterior - coeficiente de la columna pivote x nueva fila pivote

• Nueva Fila (S1) • -1 • •

0 -3

1

0

-3 Fila Anterior

0

0

0

0

0 Coeficiente

0 1

1

0 -0,5 2,5 Nueva Fila Pivote

0 X

• -1

0 -3

1

0

-3 Nueva Fila

• Nueva Fila (Z) 12

• 4 12

18 0

• 12 12

12 12 12 12

•

0 1

• 4 0

1 6

0 0

0

0

-0,5 2,5 6 -30

Nueva Tabla del Simplex Variab le Básica

Variab les

Soluci ón

X1

X2

X3

S1

S2

S1

-1

0

-3

1

0

-3

X2

0

1

1

0

-1

2,5

Z

4

0

6

0

6

-30

-

-2

0

-

Razón -4

Se realizan nuevamente los pasos obteniendo como solución final: Variabl e Básica

del

Variabl es

5

al

7

Soluci ón

X1

X2

X3

S1

S2

X3

0,33

0

1

-0,33

0

1

X2

-0,33

1

0

0,33

-0,5

1,5

Z

2

0

0

2

6

-36

13

NOTA: No hay más iteraciones cuando no existan soluciones con coeficientes negativos. R\ El valor mínimo se alcanza para un X 2 = 3/2 y X3 = 1, para un Z = 36

Aplicación en la Ingeniería Civil En nuestro entorno muchas cosas se piensan sobre la ingeniería en sistemas, como muchos o la mayoría de métodos, tienen como fin el mismo, la aplicación de modelos de optimización, ya sea para empresas productivas o para otro tipo de medios. De esta forma la importancia de la ingeniería en sistemas, programación lineal y en nuestro caso, el método dual simplex, no solo radica en el procedimiento matemático, sino en la herramienta financiera que sirve como soporte en la toma de decisiones de cualquier organización.

Conclusión Aunque es un método muy fácil, se hace enredado encontrar los resultados de las incógnitas ya que para llegar a ellos se necesita de la realización de tablas o matrices, y si no se tiene el cuidado y no se le presta la atención al proceso, se podría obtener un resultado incorrecto. Pero si se tiene cuidado en su realización no se tendrá inconveniente en maximizar o minimizar cualquier problema por el método Dual – Simplex.

Bibliografía

14

© 2012 Método Dual Simplex http://oromeroio.blogcindario.com/ficheros/MetodoSim plexDual.pdf © 2016 UV. Blasco Ibáñez Dualidad en Programación Lineal http://www.uv.es/~sala/Clase11.pdf

15